K均值（K-Means）聚类算法简介

K均值算法

K均值算法是一个经典的，被广泛使用的聚类算法。

算法过程

K均值算法中首先选择K个初值。K是用户指定的参数，即希望聚成的簇的个数。每个点指派到最近的质心，指派到一个质心的点集为一个簇。然后更新每个簇的质心，直到簇不发生变化，或质心不发生变化（二者等价），结束算法。

算法：  K均值
--------------------
选择K个点作为初始质心。 （STEP 1）
repeat
    将每个点指派到最近的质心，形成K个簇。  （STEP 2）
    重新计算每个簇的质心。  （STEP 3）
until  质心不再发生变化

指派点到最近的质心

将每个点指派到“最近”的质心，需要一个邻近性度量（即距离函数）来量化这个“最近”的概念。通常在欧式空间中的点可以使用曼哈顿距离（L1）或者欧式距离（L2）；对于文档可以用余弦相似性或者Jaccard距离等。

目标函数

对于邻近性度量为欧氏距离的数据，我们使用误差平方和（Sum of the Squared Error, SSE）作为度量聚类质量的目标函数。我们计算每个点到最近所在簇的质心的欧氏距离（该距离也可以称作误差），然后计算误差的平方和。SSE的定义如下：
$$SSE=\sum _{i=1}^K\sum _{x\in C_i}dist(c_i,x{)}^2$$
其中，dist是欧几里得空间中两个对象之间的标准欧几里得距离（L2），$C_i$是第i个簇，$c_i$是簇$C_i$的质心。

使簇的SSE最小的质心是均值。

K均值是一种启发式算法，在算法的步骤中，STEP2和STEP3试图最小化SSE。然而这只能确保他们找到关于SSE的局部最优解，因为他们是对选定的质心和簇进行优化，而不是对所有可能的选择来优化SSE。

选择初始质心

K均值算法受选取的初始质心的影响很严重。选不同的初始质心会出现不同的结果。

一种常用的技术是多次运行，每次用一组不同的随机初始质心。然后选取具有最小SSE的簇集。

一种方法是使用层次聚类技术。从层次聚类中提取K个簇，用这些簇的质心作为初始质心。缺点：这只适用于样本相对较小同时K相对于样本大小较小的情况。

另一种方法是随机的选取一个点。然后对每个后继初始质心选择距离已经选取过初始质心最远的点。这样可以确保初始质心集合不是随机的，而且是散开的。不过这样的方法可能选中离群点。而不是稠密区域中的点。

K-Means++ 算法

K-Means++ 是对K-means的改进，主要是在初始点选取上的改进。基本思想就是K个初始质心离的越远越好。

算法步骤：
步骤一：随机选取一个样本作为第一个聚类中心 c1
步骤二：计算每个样本与当前已有簇中心最短距离（即与最近一个聚类中心的距离），用 D(x)表示；计算每个样本被选为下一个初始质心的概率 $\frac{D(x{)}^2}{\sum D(x{)}^2}$；最后，用轮盘法选出下一个聚类中心；
步骤三：重复步骤二，直到选出 K 个初始质心。

选出初始点后，就继续使用标准的 k-means 算法了。

时间和空间复杂性

空间复杂度： O((m+K)n)，m是点数，n是属性数。

时间复杂度： O(IKm*n)，I是收敛所需要的迭代次数。I通常很小。

实践的技巧

离群点的处理

在K均值算法中，离群点会影响簇的发现，导致簇的质心不如没有离群点时那样具有代表性，同时SSE也较高。

离群点的处理分为前处理和后处理，前处理是在聚类之前剔除一些离群点。后处理可以在聚类之后记录每个点对SSE的影响，删除那些具有特别大的影响力的点；同时还可以删除那些很小的簇，因为他们常常代表拥有离群点的簇。

后处理技术

聚类结束后，可以使用一些后处理的技术，常用的方法如分裂和合并技术，通过增加或者减少簇降低SSE。

增加簇：

1. 分裂一个簇： 分裂一个具有最大SSE的簇。或者选择在特定属性上具有最大标准差的簇。
2. 引进一个新的簇： 通常选择离所有质心最远的点作为一个新的质心，重新聚类。或者从具有最高SSE的簇中随机的选择一个点。

减少簇：

1. 拆散一个簇： 删除一个簇对应的质心，并将簇中的点指派到其他的簇中。理想情况下应该是使总SSE增加最少的簇。
2. 合并两个簇： 选择质心最接近的两个簇合并。

二分K均值

二分K均值是K均值算法的变种。二分K均值的思想是，为了得到K个簇。将所有的点的集合分裂成两个簇，从这些处中根据一些指标（如SSE）选取一个簇继续分裂，如此下去，直到产生K个簇为止。

算法：  二分K均值
--------------------
初始化簇表使之包含由所有的点组成的簇。
repeat
    从簇表中取出一个簇。
    for i=1 to 试验次数 do {对选定的簇进行多次二分试验}
        使用基本K均值二分选定的簇
    end for
    从二分试验中选择具有最小总SSE的两个簇
    将这两个簇添加到簇表中
until 簇表中包含K个簇。

二分K均值不太受初始化问题的影响。

K均值算法可以找到使SSE局部最小的聚类，但是二分K均值仅局部的使用了K均值算法（二分一个簇），最终的结果不代表使SSE局部最小的聚类。

K均值算法与K中心点算法

K均值算法中簇的质心一组点的均值。而K中心点算法使用一组点中最具有代表性的点作为质心，根据定义，K中心点中的质心必须是一个实际的数据点。而k均值中的质心不需要对应于一个实际的数据点。

优点与缺点

优点： K均值简单耗费空间小，多数情况下相当有效。K均值的某些变种（如二分K均值），不太受初始化问题的影响。

缺点： K均值的目标函数表明他是最小化等尺寸和等密度的球形簇或者可以明显分离的簇，所以他无法处理非球形、不同尺寸、不同密度的簇。对于数据中具有离群点，K君之也不能很好的处理。

参考

Pang-Ning Tan & Michael Steinbach, (2010). 数据挖掘导论. 人民邮电出版社