K-Means算法

K-Means算法是聚类算法的一种,它是一种非监督学习.与其同样原理的还有学习向量化(LVQ)算法.

首先我们选取聚类中心,我们希望将模型分为几类就选取几个聚类中心.然后我们将所有的数据归类到离它最近的聚类中心,然后移动聚类中心,让每个数据到聚类中心的距离尽可能的小.

根据这个思路可以写出K-Means算法的损失函数,目标是让每个点到聚类中心的距离之和最小:

K-Means的迭代算法

K-Means算法的迭代其实非常简单:

只需重复这两步就可以完成K-Means算法的迭代.

你可能会发现K-Means非常简单,但是可能会生出一点疑惑,这样能保证一定找到最优解吗?它的原理是什么?

K-Means和高斯混合模型非常的像,高斯混合模型把数据分成若干"组",每一组是一个高斯分布.K-Means也是把数据分成若干"组",每一组是一个类.实际上K-Means就是高斯混合模型的极限情况.

知乎找到了简单的解释:

另外有paper证明当高斯混合模型的时,会简化为K-Means:
Revisiting k-means: New Algorithms via Bayesian Nonparametrics

最开始聚类中心位置可以随机选取,常见的做法是随机选取k个样本的位置.

聚类的最终结果很可能受到我们最开始选取的聚类中心的位置所影响.就像这样:

所以为了排除因为聚类中心初始化问题所造成的影响,我们会多次重复执行聚类算法,每次随机初始化聚类中心,例如执行100次,然后选取代价函数最小的结果作为最终结果.

聚类的个数k是算法的一个参数,需要我们指定,这里有一个选取方法:

我们可以画出代价函数随着k变化的图像,如果出现拐点,那么可以把k选在这里.这种方法叫肘部法则.

但是肘部法则并不是总管用,因为有的时候代价函数是一个光滑的曲线,很难找到拐点,这也是为什么不能自动判断k的原因.当遇到这种情况通常会根据业务逻辑决定k的大小.

编程实现:
https://www.kaggle.com/swimmingwhale/k-means

参考:
https://www.coursera.org/learn/machine-learning