K-means算法又名k均值算法,K-means算法中的k表示的是聚类为k个簇，means代表取每一个聚类中数据值的均值作为该簇的中心，或者称为质心，即用每一个的类的质心对该簇进行描述。
其算法思想大致为：先从样本集中随机选取 k个样本作为簇中心，并计算所有样本与这 k个“簇中心”的距离，对于每一个样本，将其划分到与其距离最近的“簇中心”所在的簇中，对于新的簇计算各个簇的新的“簇中心”。
根据以上描述，我们大致可以猜测到实现K-means算法的主要四点：
（1）簇个数 k 的选择
（2）各个样本点到“簇中心”的距离
（3）根据新划分的簇，更新“簇中心”
（4）重复上述2、3过程，直至"簇中心"没有移动
基本K均值算法
1.选择K个点作为初始质心。
2.repeat
3. 将每个点指派到最近的质心，形成K个簇。
4. 重新计算每个簇的质心。
5. until 质心不再发生变化
K值的选择影响聚类效果，在进行离群点检测时，对象是否被认为是离群点可能依赖于聚类的个数。K 的选择一般是按照实际需求进行决定，或在实现算法时直接给定 K 值。
选择恰当的初始质心是基本K均值过程的关键步骤，常见的方法是随机选取，但是这样簇的质量往往很差，可能只能得到局部最优。
处理选取质心问题的一种常用技术是：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE的簇集。还有其他更加有效的技术，比如K-means++、二分K-means、使用后处理来“修补”所产生的簇集等，在文章最后的结论中有讲解。
在下面的实现中初始的质心是随机选取的。
将对象点分到距离聚类中心最近的那个簇中需要最近邻的度量策略，在欧式空间中采用的是欧式距离，在处理文档中采用的是余弦相似度函数，有时候也采用曼哈顿距离作为度量，不同的情况实用的度量公式是不同的。
欧氏距离：
曼哈顿距离：
余弦相似度函数：
对于分类后的产生的k个簇，分别计算到簇内其他点距离均值最小的点作为质心（对于拥有坐标的簇可以计算每个簇坐标的均值作为质心）。经过这一步会产生K个质心，继续作为上一步的聚类中心。
当质心不再改变，或给定loop最大次数loopLimit时结束算法。
calcDis函数用于计算欧拉距离，classify函数用于计算新的质心，kmeans函数用于kmeans分类，loadDataSet函数用于加载数据集。最初的k值为随机确定。
我要评论import random
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
# 计算欧拉距离
def calcDis(dataSet, centroids, k):
clalist = []
for data in dataSet:
diff = np.tile(data, (k, 1)) - centroids # 相减 (np.tile(data,(k,1))就是把data先沿x轴复制1倍，即没有复制，比如是 [0,1,2]。
# 再把结果沿y方向复制k倍得到array([[0,1,2],[0,1,2],...]))
squaredDiff = diff ** 2 # 平方
squaredDist = np.sum(squaredDiff, axis=1) # 和 (当axis为1时,是压缩列,即将每一行的元素相加,将矩阵压缩为一列)
distance = squaredDist ** 0.5 # 开根号
clalist.append(distance)
clalist = np.array(clalist) # 返回一个每个点到质点的距离len(dateSet)*k的数组
return clalist
# 计算质心
def classify(dataSet, centroids, k):
# 计算样本到质心的距离
clalist = calcDis(dataSet, centroids, k)
# 分组并计算新的质心
minDistIndices = np.argmin(clalist, axis=1) # axis=1 表示求出每行的最小值的下标
newCentroids = pd.DataFrame(dataSet).groupby(minDistIndices).mean() # DataFramte(dataSet)对DataSet分组，groupby(min)按照min进行统计分类，mean()对分类结果求均值
newCentroids = newCentroids.values
# 计算变化量
changed = newCentroids - centroids
# 返回变化量和新的质心
return changed, newCentroids
# 使用k-means分类
def kmeans(dataSet, k):
# 随机取质心，取k个
centroids = random.sample(dataSet, k)
# 更新质心 直到变化量全为0
changed, newCentroids = classify(dataSet, centroids, k)
while np.any(changed != 0):
changed, newCentroids = classify(dataSet, newCentroids, k)
centroids = sorted(newCentroids.tolist()) # tolist()将矩阵转换成列表 sorted()排序
# 根据质心计算每个集群
cluster = []
clalist = calcDis(dataSet, centroids, k) # 调用欧拉距离
minDistIndices = np.argmin(clalist, axis=1)
for i in range(k):
cluster.append([])
for i, j in enumerate(minDistIndices): # enymerate()可同时遍历索引和遍历元素
cluster[j].append(dataSet[i])
# 返回质心和集群
return centroids, cluster
# 加载数据集
def loadDatadet(infile,k):
f=open(infile,'r')
sourceInLine=f.readlines()
dataset=[]
for line in sourceInLine:
temp1=line.strip('\n')
temp2=temp1.split(' ')
dataset.append(temp2)
for i in range(0, len(dataset)):
for j in range(k):
dataset[i].append(float(dataset[i][j]))
del(dataset[i][0:k])
return dataset
if __name__ == '__main__':
dataset = loadDatadet('./西瓜数据集', 2)
centroids, cluster = kmeans(dataset, 3)
print('质心为：%s' % centroids)
print('集群为：%s' % cluster)
for i in range(len(cluster[0])):
plt.scatter(cluster[0][i][0], cluster[0][i][1], marker='o', color='yellow', s=40, label='集群1')
# 记号形状、颜色、点的大小、设置标签
for i in range(len(cluster[1])):
plt.scatter(cluster[1][i][0], cluster[1][i][1], marker='o', color='blue', s=40, label='集群1')
# 记号形状、颜色、点的大小、设置标签
for i in range(len(cluster[2])):
plt.scatter(cluster[2][i][0], cluster[2][i][1], marker='o', color='green', s=40, label='集群1')
# 记号形状、颜色、点的大小、设置标签
for j in range(len(centroids)):
plt.scatter(centroids[j][0], centroids[j][1], marker='x', color='red', s=50, label='质心')
plt.show()
使用的数据是西瓜数据集4.0，来自于西瓜书。第一列是密度，第二列是含糖量，两个变量都是连续变量，共计有30条记录。已经归一化到 [0,1] ，不用进行标准化处理，且无缺失项，异常值检测省略，直接作为模型输入即可。
经过测试，得出聚类结果如下图：
如果将聚类K值改为2和4，得到的结果如下所示：
多次执行后，由于初始质心为随机选择，会造成最终聚类效果不同。
二分K-means算法首先将所有数据点分为一个簇；然后使用K-means（k=2）对其进行划分；下一次迭代时，选择使得SSE（误差平方和）下降程度最大的簇进行划分；重复该过程，直至簇的个数达到指定的数目为止。算法流程如下：
二分K均值和初始化
1.初始化簇表，使之包含由所有点组成的簇。
2.repeat
3. 从簇表中取出一个簇。
4. {对选定的簇进行多次“二分”实验。}
5. for i=1 to 实验次数 do
6. 使用基本K均值，二分选定的簇。
7. end for
8. 从二分实验中选择具有最小总SSE的两个簇。
9. 将这两个簇添加到簇表中。
10.until 簇表中包含K个簇。
实验表明，二分K-means算法的聚类效果要好于普通的K-means聚类算法。通过记录K均值二份簇所产生的簇类序列，我们还可以使用二分K均值产生层次聚类。
K-means++的详解可见：https://blog.csdn.net/a19990412/article/details/89000149
一种明显降低SSE（这里的误差可以是欧式距离）的方法是找出更多的簇，即使用较大的K。然而在很多情况下，我们希望降低SSE，但是不想增加K的个数。这时我们可以选择采用多种技术来“修补”结果簇。策略是关注每一个簇，因为总的SSE不过是每个簇的SSE之和。一种常用的方法是交替地使用簇分裂和簇合并，使用这种方法，常常可以避开局部极小，并且仍然可以得到期望个数的簇。
通过增加簇的个数来降低总SSE的两种策略：
基本K-means算法的缺点很明显，有如下几点：
优点有：
本文地址：https://blog.csdn.net/weixin_43903564/article/details/107232617
如对本文有疑问， 点击进行留言回复！！
网友评论