聚类算法（二）——K-means聚类

简介

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算法描述容易，实现简单，快速，但存在以下不足：

1. k需要提前给定
2. 算法对初始值选取依赖性极大以及算法常陷入局部最优解
3. 离群点和噪声点会影响簇质心偏离
4. 不能处理分类属性的簇

变体

为了解决K-means算法的缺点，还提出了包括二分-K-means算法，k-modes算法，k-prototypes算法，k-summary算法，k-medoids算法等。

Ref

深入浅出聚类算法之k-means算法

• https://blog.csdn.net/llh_1178/article/details/81633396
• 《数据挖掘原理与实践》