K-Means算法以及实现

机器学习 算法

聚类

聚类是一种无监督的学习，它将相似的对象归到同一个簇中。有点像全自动分类，聚类方法几乎可以应用于所有对象，簇内的对象越相似，聚类的效果越好。簇识别（cluster identification）给出聚类结果的含义。
聚类分析试图将相似对象归入同一簇，将不相似对象归到不同簇。相似这一概念取决于所选择的相似度计算方法。

K-均值聚类

K均值聚类方法有如下特点：

• 优点：容易实现
• 缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢
• 适用数据类型：数值型数据

实现伪代码

• 创建k个点作为起始质心（经常是随机选择）
• 当任意一个点的簇分配结果发生变化时
  
  • 对数据集中的每个数据点
    
    • 对每个质心
      
      • 计算质心与数据点之间的距离
    • 将数据点分配到距其最近的簇
  • 对每一个簇，计算簇中所有点的均值并将均值作为质心

提高聚类性能

K均值收敛但是聚类效果差的原因是，K-均值算法收敛到了局部最小值，而非全局最小值。

用于度量聚类效果的指标是SSE（Sum of Squared Error，误差平方和），SSE值越小表示数据点越接近于它们的质心，聚类效果也越好。对误差取了平方，因此更加重视那些远离中心的点。可以通过降低SSE值的方法是增加簇的个数，但违背聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。

将具有最大SSE值的簇划分成两个簇。具体实现时可以将最大簇包含的点过滤出来并在这些点上运行K-均值算法，k为2.

• 合并最近的质心
• 合并两个使得SSE增幅最小的质心

二分K-均值算法

首先将所有点作为一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值，上述划分过程不断重复，直到用户指定的簇数目为止

伪代码：

• 将所有点看成一个簇
• 当数目小于k时
  
  • 对于每一个簇
    
    • 计算总误差
    • 在给定的簇上面进行K-均值聚类（k=2）
    • 计算将该簇一分为二后的总误差
  • 选择使得误差最小的那个簇进行划分操作

两种选择方法

1.选择总误差降低量最大的簇进行划分
2.选择SSE最大的簇进行划分

Python实现

GitHub: https://github.com/spiritwiki/codes/tree/master/kmeans
coding.net: https://coding.net/u/spiritwiki/p/codes/git/tree/master/kmeans