简介
k-means算法是1967年由MacQueen首次提出的一种经典算法，它是一种基于质心的划分方法，这种方法将簇中所有对象的平均值看作是簇的质心，根据一个数据对象与簇质心的距离，将该对象赋予最近的簇。在此类方法中，需要给定划分的簇个数k，首先得到k个初始划分的集合，然后采用迭代重定位技术，通过将对象从一个簇移到另一个簇来改进划分的质量。
算法
误差函数
对于k-means算法，通常使用SSE作为度量质量的目标函数，对于相同的k值，更小的SSE表示簇中对象越集中。对于不同的k值，越大的k值应该对应越小的SSE
Python实现
任意选择k个对象作为初始质心，并建立k个簇
def init_cluster(self):
for i in range(self.k):
c = clusterUnit()
initCentroid = random.choice(self.data)
c.add_node(initCentroid)
self.clusterList.append(c)
定义clusterChange变量，监控聚类是否变化
clusterChange = True
循环读取数据，通过比对每个数据到k个簇簇心的距离找出该数据所属的簇，并使用与数据等长的列表来记录该数据所属的簇。
for j in range(self.k):
distance = clusterUnit.distance(self.clusterList[j].centroid, data)
if distance < minDist:
minDist = distance
minIndex = j
if int(self.note[i]) != minIndex:
clusterChange = True
if int(self.note[i]) != -1:
self.clusterList[int(self.note[i])].remove_node(data)
self.clusterList[minIndex].add_node(data)
self.note[i] = minIndex
使用鸢尾花的数据，调用可视化方法，可视化每个循环后的结果
1，2，3，4次循环的结果
输出SSE值
def calcualte_SSE(self):
sum_SSE = 0
for i in self.clusterList:
sum_SSE += i.SSE()
return sum_SSE
分析
K-means算法描述容易，实现简单，快速，但存在以下不足：
- k需要提前给定
- 算法对初始值选取依赖性极大以及算法常陷入局部最优解
- 离群点和噪声点会影响簇质心偏离
- 不能处理分类属性的簇
变体
为了解决K-means算法的缺点，还提出了包括二分-K-means算法，k-modes算法，k-prototypes算法，k-summary算法，k-medoids算法等。
Ref
深入浅出聚类算法之k-means算法
