本篇文章主要讲解聚类分析中的一种常用的算法k-means，它的全称叫作k均值算法。
k-means原理
k-means算法是一种基于原型的、划分的聚类技术。
基于原型可以理解为基于质心，也就是说，每个对象到定义该簇质心的距离比到其他簇质心的距离更近。当质心没有意义时，原型可以视为最靠近中心的点。当然，还有其它的基于图的、基于密度的、基于概念的簇。
基于划分的意思是，可以将数据对象集合划分成不重叠的子集，使得每个对象恰在一个子集中。与之相对应的是，基于层次的聚类，例如说，将整个集合看成是一个簇，然后从中分成两个子簇，这样不断地划分子簇，直到类别个数达到所要求的标准。类似于一棵决策树，不断地划分节点，直到满足类别要求。
k-means算法随机选择k个点作为初始质心repeat将每个点指派到最近的质心，形成k个簇重新计算每个簇的质心until 质心不再发生变化
简单来说，这个算法完成的是这样的一个过程：首先，随机选择k个质心，然后将每个点按照距离分到离它最近的那个簇，这样的话，每个簇上都有若干个点，根据这些点，求它们的质心，然后再次进行分配点，重复这个过程，知道质心不再发生变化。
python实现k-means算法
首先，我们假定有四类数据，每类数据都有一个中心点，我们看若干次迭代后是否可以将所有的数据完全分开。在本次实验中，我们采用经典的欧氏距离作为衡量两个点之间差距的指标。
1.生成数据：假设四类点的中心分别是(2,2)，(4,3)，(3,5)，(1,4)，以它们为中心，各自生成100个方差在0.5左右的点，它们的分布如下图所示：
import matplotlib.pyplot as pltimport numpy as npimport mathN = 100x1 = np.random.normal(2,0.5,N)y1 = np.random.normal(2,0.4,N)plt.scatter(x1,y1,c='r',marker='o')x2 = np.random.normal(4,0.3,N)y2 = np.random.normal(3,0.6,N)plt.scatter(x2,y2,c='r',marker='o')x3 = np.random.normal(3,0.5,N)y3 = np.random.normal(5,0.4,N)plt.scatter(x3,y3,c='r',marker='o')x4 = np.random.normal(1,0.3,N)y4 = np.random.normal(4,0.6,N)plt.scatter(x4,y4,c='r',marker='o')plt.xlim(0,6)plt.ylim(0,6)plt.show()
2.随机选择四个点作为初始的k个点。(x1_pre,y1_pre)，(x2_pre,y2_pre)，(x3_pre,y3_pre)，(x4_pre,y4_pre)
x1_pre = np.random.random(1)*5y1_pre = np.random.random(1)*5x2_pre = np.random.random(1)*5y2_pre = np.random.random(1)*5x3_pre = np.random.random(1)*5y3_pre = np.random.random(1)*5x4_pre = np.random.random(1)*5y4_pre = np.random.random(1)*5
3.将所有点分配到这四个簇中去，我这里用不同的颜色标出。
for i in range(0,len(x_data)):x = x_data[i]y = y_data[i]dis1 = math.sqrt((x-x1_pre)**2+(y-y1_pre)**2)dis2 = math.sqrt((x-x2_pre)**2+(y-y2_pre)**2)dis3 = math.sqrt((x-x3_pre)**2+(y-y3_pre)**2)dis4 = math.sqrt((x-x4_pre)**2+(y-y4_pre)**2)dis_min = min(dis1,dis2,dis3,dis4)if dis_min==dis1:plt.scatter(x,y,color='b',marker='+')x1.append(x)y1.append(y)elif dis_min==dis2:plt.scatter(x,y,color='y',marker='^')x2.append(x)y2.append(y)elif dis_min==dis3:plt.scatter(x,y,color='g',marker='s')x3.append(x)y3.append(y)else:plt.scatter(x,y,color='r',marker='o')x4.append(x)y4.append(y)plt.show()
4.然后是根据每个簇中的所有点，求它们的中心点，之后是分配所有点的过程。
完整代码如下：
import matplotlib.pyplot as pltimport numpy as npimport mathN = 100x1 = np.random.normal(2,0.5,N)y1 = np.random.normal(2,0.4,N)plt.scatter(x1,y1,c='r',marker='o')x2 = np.random.normal(4,0.3,N)y2 = np.random.normal(3,0.6,N)plt.scatter(x2,y2,c='r',marker='o')x3 = np.random.normal(3,0.5,N)y3 = np.random.normal(5,0.4,N)plt.scatter(x3,y3,c='r',marker='o')x4 = np.random.normal(1,0.3,N)y4 = np.random.normal(4,0.6,N)plt.scatter(x4,y4,c='r',marker='o')plt.xlim(0,6)plt.ylim(0,6)plt.show()x1_pre = np.random.random(1)*5y1_pre = np.random.random(1)*5x2_pre = np.random.random(1)*5y2_pre = np.random.random(1)*5x3_pre = np.random.random(1)*5y3_pre = np.random.random(1)*5x4_pre = np.random.random(1)*5y4_pre = np.random.random(1)*5x_data = []for num in x1:x_data.append(num)for num in x2:x_data.append(num)for num in x3:x_data.append(num)for num in x4:x_data.append(num)y_data = []for num in y1:y_data.append(num)for num in y2:y_data.append(num)for num in y3:y_data.append(num)for num in y4:y_data.append(num)for index in range(10):x1 = []y1 = []x2 = []y2 = []x3 = []y3 = []x4 = []y4 = []for i in range(0,len(x_data)):x = x_data[i]y = y_data[i]dis1 = math.sqrt((x-x1_pre)**2+(y-y1_pre)**2)dis2 = math.sqrt((x-x2_pre)**2+(y-y2_pre)**2)dis3 = math.sqrt((x-x3_pre)**2+(y-y3_pre)**2)dis4 = math.sqrt((x-x4_pre)**2+(y-y4_pre)**2)dis_min = min(dis1,dis2,dis3,dis4)if dis_min==dis1:plt.scatter(x,y,color='b',marker='+')x1.append(x)y1.append(y)elif dis_min==dis2:plt.scatter(x,y,color='y',marker='^')x2.append(x)y2.append(y)elif dis_min==dis3:plt.scatter(x,y,color='g',marker='s')x3.append(x)y3.append(y)else:plt.scatter(x,y,color='r',marker='o')x4.append(x)y4.append(y)plt.show()x1_pre = float(sum(x1))/len(x1)y1_pre = float(sum(y1))/len(y1)x2_pre = float(sum(x2))/len(x2)y2_pre = float(sum(y2))/len(y2)x3_pre = float(sum(x3))/len(y3)y3_pre = float(sum(y3))/len(y3)x4_pre = float(sum(x4))/len(x4)y4_pre = float(sum(y4))/len(y4)
大约是迭代了9次左右，簇内的所有的点都不在变化，算法结束。
k-means算法的优缺点：
优点：算法比较简单，易于实现，并且适用于各种数据类型
缺点：k值需要提前确定；对异常点敏感；不能处理非球形簇、不同尺寸和不同密度的簇。
如果觉得《k-means算法及python实现》对你有帮助，请点赞、收藏，并留下你的观点哦！
