机器学习之聚类算法K-Means

K-Means算法是最简单的一种聚类算法，属于无监督学习算法。
假设我们的样本是

即它是一个n维向量。现在用户给定一个K值，要求将样本聚类(Clustering)成K个类簇(Cluster)。在这里我们把整个算法称为聚类算法，聚类算法的结果是一系列的类簇。

K-Means是一个迭代型的算法，它的算法流程是：

1. 随机选取K个聚类质心（Cluster Centroid），为
2. 重复下面过程，直到收敛：
   2.1 对于每个样本i, 计算它应该属于的类：
   
   2.2 对于每一个类别j，重新计算它的质心：
   

收敛是在上一次迭代到本次迭代中，每个样本隶属于同样的类别，每个类别的质心不再发生改变。

下面以一个实例展示K-Mean标准算法的执行过程。假设我们对样本进行K=3的聚类，下图的正方形是样本点，圆点（不同灰度）分别是三个类的质心。

K-Means算法实例
注意: 图中不同灰度的圆圈不是真实存在的数据点，而是某个类簇的虚拟质心

• 图(a)表示 - 由于K=3，所以算法开始在有效的数据域(Domain)里生成3个初始的(Initial)质心。
• 图(b)表示 - 所有的样本根据和质心的远近，分配到最近的质心，形成三个类别。这三个区域是基于三个质心的对平面的一个Voronoi Diagram划分，该划分把平面上的点根据三个质心的远近分配给各个划分。
• 图(c)表示 - 经过迭代计算，K个类簇的质心改变了。
• 图(d)表示 - 经过多次迭代(把样本分配到各个质心、重新计算各个类簇的质心)，各人类簇最终的质心，即聚类算法收敛的结果。

在K-Means算法中，涉及距离的计算，最常用的距离是欧式距离，欧式距离(Euclidean Distance)的公式为：

此外，还有闵可夫斯基距离,曼哈顿距离(也称为城市距离，City Block Distance)可以使用，它们的计算公式分别为：

K值的选择

在K-Means算法中，K值的选择是一个重要的问题。

我们希望所选择的K正好是数据里隐含的真实的类簇的数目；

• 当我们假设的类簇数目等于或大于真实的类簇的数目时，这个指标变化平缓；
• 当我们假设的类簇数目小于真实的类簇的数目时，这个指标急剧变化；

我们可以选择的类簇指标包括平均半径或者直径；

• 类簇直径 - 是指类簇中任意两点的距离的最大值；
• 类簇半径 - 是指类簇中所有点到类簇中心距离的最大值；

K-Means是可伸缩和高效的，方便处理大数据集，计算的复杂度为O(NKt)，其中
N为数据对象的数目，
t为迭代的次数。
一般来说，K<<N，t<<N。
当各个类簇是密集，且类簇与类簇之间区别明显时，K-Means算法可以取得较好的效果。

K-Means算法的缺点

1. 在K-Means算法中，K值是事先给定的，一个合适的K值难以估计；
2. 在K-Means算法中，首先需要根据初始类簇中心来确定一个初始划分，然后对初始划分进行优化。初始类簇中心的选择对聚类结果有较大的影响。不旦初始值选择的不好，可以无法得到有效的聚类结果。
3. 算法需要不断的进行样本分类调整，不断地计算调整后的新类簇中心，因此当数据量非常大时，算法的时间开销是非常大的。

优化处理

对于上面的三个缺点，我们可以做一些优化来规避这些缺点；

1. 使用遗传算法(Genetic Algorithm)，帮助选择合适的初始类簇中心。
2. 对于数据量大时，可以利用采样策略，改进算法效率。也就是初始点的选择，以及每一次迭代完成时对数据的调整，都是建立在随机采样的样本数据的基础之上，这样可以提高算法的收敛速度。