0%

K-Means聚类算法

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

K-Means聚类算法

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

![聚类](/images/posts/ml/kmeans/cluster.jpg)

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

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

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

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

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

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

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

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

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

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

![聚类](/images/posts/ml/kmeans/kmeans-example.png)

K-Means算法的几个讨论

  1. 如何保证收敛

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

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

  2. K值选取

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

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

代码示例

Github K-Means