聚类算法-基于划分-K-Means

vlambda
2020-05-21

聚类算法-基于划分-K-Means

一、聚类和分类

聚类：数据无标签，不了解每一类的特点。聚类算法根据自己的规则来判断数据之间的相似性，认为相似的数据归为一类，特点需要人工分析。

分类：有标签的数据，已知待分类数据可以分为哪几类，算法研究被标记数据的特点，对待分类数据进行判断，分类目标已知。

聚类算法-基于划分-K-Means

二、K-Means

K-Means是最常用的基于划分聚类算法；

优点：简单、运行速度快。

缺点：只能用于连续型的数据、需要指定分类数K和初始质心。

K-Means聚类步骤：

1、给类别数K（期望聚类算法能将数据分为K组）；

2、随机选择K个初始点（质心）；

3、分别计算待聚类数据到K个质心的距离（相似度），更新质心（让质心更精确的描述该簇的特征）；

4、当新的质心与上一质心的距离小于某阈值，我们认为聚类算法已经趋于收敛或稳定，可以停止聚类；

5、若距离还是比较大，需要继续计算3-4，直到质心收敛。

三、需要的公式

距离计算公式（相似度）：

1、欧几里得距离（欧氏距离）：任意维度空间两个点的真实距离。

聚类算法-基于划分-K-Means

x=(x1,x2,......,xn)，y=(y1,y2,......,yn)

2、余弦相似度：余弦相似度通过计算两个数据之间的夹角来判断其相似度。

余弦值为-1：两个数据含义完全相反；

1：含义完全一样；

0：没有任何关系。

聚类算法-基于划分-K-Means

其中A,B为两个向量（A1，A2......,An），（B1，B2......,Bn）。

还有其他的一些计算距离的方法，但是都是欧氏距离和余弦相似度的衍生，简单罗列如下：明可夫斯基距离、切比雪夫距离、曼哈顿距离、马哈拉诺比斯距离、调整后的余弦相似度、Jaccard相似系数……

四、注意事项

1、K的确定，一般来说都是去经验值，即多次运行之后取效果最好的K值，也可以通过判断不同K值聚类后，簇内误差平法和（SSE）来判断簇内是否紧凑来选择K。

2、初始质心的确定，随机，经验值。也有很多优化算法。

3、数据需要标准化处理，保证单位一致，标准化计算后忽略单位，数据统一度量，一般用Z-Score或Min-Max算法。

4、更新时的质心时通过计算簇内已有数据的平均值获得的，也有改进算法。

四、K-Means Python实现

数据集：80*2

聚类算法-基于划分-K-Means

numpy+pandas:

import numpy as npimport matplotlib.pyplot as pltimport pandas as pd
def Kmeans(data,n,k): showtable(data) plt.show() #k:k个类别 cls = np.zeros((n), dtype=np.int) # 定义数组cls，存放每一个数据的类别，初始值为0 Knum=np.random.random(size=k)#随机选择K数据，(0-1)之间 Knum=np.floor(n*Knum)#初始化K个质心在数据中的索引，floor取小于参数的最大整数 Knum=Knum.astype(int)#将下标转换为整数，得到索引 Kcenter=data[Knum]#初始化质心的值 print('初始center=\n', Kcenter)
 run=True time=0 while run: time=time+1 for i in range(n): temp=data[i]-Kcenter#求数据data[i]与质心的差值 temp=np.square(temp)#求差值平方 temp=np.sum(temp,axis=1)#按行求和 cls[i]=np.argmin(temp)#将列表展平，输出最小值的索引号 run=False #没有修改质心，则退出
 for i in range(k): club=data[cls==i]#找出属于类i的数据data newCenter=np.mean(club,axis=0)#按列求均值，获得新的质心。axis=1按列 error=np.abs(newCenter-Kcenter[i])#求新质心与原始质心的距离abs()取绝对值，得到的是向量形式 if np.sum(error,axis=0)>1e-4:#判断新老质心误差是否小于阈值 Kcenter[i]=newCenter run=True print("新质心：",newCenter) print("迭代次数：",time) #绘图 for i in range(k): club=data[cls==i] showtable(club) showtable(Kcenter)
def showtable(data): x=data.T[0] y=data.T[1] plt.scatter(x,y)
if __name__ == "__main__": data = pd.read_csv("./Kmeans.txt") Kmeans(data.values,80,4)#调用kmeans函数 plt.show()

原始数据：

聚类算法-基于划分-K-Means

聚类后：

python sklearn实现Kmeans

sklearn-kmeans手册：

https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html#sklearn.cluster.KMeans

#使用sklearn实现Kmeansimport pandas as pdfrom sklearn.cluster import KMeansdata=pd.read_csv("./Kmeans.txt")#直接调用KMeans()#常用参数：n_clusters K类, #max_inter 最大迭代次数 #init 初始化质心选择，默认为K-means++ （让初始质心尽量远） # {‘k-means++’, ‘random’, ndarray, callable}, default=’k-means++’kmeans = KMeans(n_clusters=3,max_iter=5).fit(data)center=kmeans.cluster_centers_print("聚类结束后质心：",center)#用训练好的模型对新数据进行预测pre=kmeans.predict([[0, 0], [12, 3]])print(pre)print(kmeans.labels_)