K-Means聚类算法

K-Means聚类算法是机器学习中一种常见的聚类算法，非常简单，但是用起来难免会有一些坑。

K-Means聚类算法

所谓聚类算法是指将一堆没有标签的数据自动划分成几类的方法，这个方法要保证同一类的数据有相似的特征，如下图所示：


K-Means聚类算法有两个重要特点，也是两个用起来容易出错的点：

• K-Means算法的特点是类别的个数K是人为给定的。
• K-Means的一个重要的假设是：数据之间的相似度可以使用欧氏距离度量，如果不能使用欧氏距离度量，要先把数据转换到能用欧氏距离度量，这一点很重要。

这两个特性决定了K-Means是否适用于待解决的问题。

K-Means算法的步骤比较简单：

1. 确定K个初始类簇中心点

   最简单的确定初始类簇中心点的方法是随机选择K个点作为初始的类簇中心点，但是该方法在有些情况下的效果较差。

2. 对于每个训练样本，度量其与所有类簇中心点的距离，将其分类到最近的中心的的簇中

3. 对于每个类簇，重新计算其中心

4. 重复2，3，直到收敛。

下图是K-Means的一个示例过程：


K-Means算法的几个讨论

1. 如何保证收敛

   这个问题是确保K-Means算法有效的必定条件，设置损失函数来训练：

   $$J(c,u)=sum_{i=1}^{m}||x^{(i)} - u_{c^{(i)}}||$$

   通过调整每个样本\(x\)所属的质心以及每个类簇质\(u\)位置来减少损失函数，使其loss降低，达到收敛，可以证明，这两个内循环是\(J\)单调递减。由于畸变函数\(J\)是非凸函数，意味着我们不能保证取得的最小值是全局最小值，也就是说K-Means对质心初始位置的选取比较感冒，但一般情况下K-Means达到的局部最优已经满足需求。

2. K值选取

   由于选择的初始K值非常非常重要，甚至影响收敛性，导致局部最优等问题，因此K值的选取非常值得讨论，可惜我自己在这方面并没有什么经验，一般是通过选择多个K值然后全部训练选择收敛最好的，也就是损失函数最小的K值。

   这里有一篇讨论，可以看一下：K-means聚类算法中K值如何选择？

代码示例

Github K-Means