Question

K-Means 聚类原理

Answer 1

K-Means 是聚类算法中的最常用的一种，算法最大的特点是简单，好理解，运算速度快，但是只能应用于连续型的数据，并且一定要在聚类前需要手工指定要分成几类。

假设有一些点分散在直线上，现在需要对这些点进行聚类分析。

第一步，想一下我们希望最终将这些点聚为多少类？

假设我们希望聚为3类

第二步，在这些点中随机选择3个点，作为初始簇(initial cluster)

第三步，计算第一个点f分别到这3个initial cluster的距离

第四步，将第一个点归属为距离最近的那个cluster

重复第三/四步

一一判断所有点的归属

第五步，计算每一个cluster的均值

然后像之前一样，通过计算每个点到这些均值的距离，重新判断每个点归属于哪个cluster

判断完每个点的归属之后，重新计算均值……判断归属……计算均值……判断归属……直到聚出来的cluster不再变化

很明显，上面的聚类效果很差，还不如我们肉眼聚类出来的效果。是否有办法判断不同聚类结果的好坏呢？

第一步，计算每一个cluster的总变差(total variation)

第二步，重新选择3个initial cluster，并且多次迭代判断cluster，计算total variation

第三步，多次重复上一步的内容，选择total variation最小的聚类结果

在本文的案例中，我们通过肉眼可以判断出K选择3比较好。但是如果我们自己无法判断时，如何处理？

一种方法是直接尝试不同的K值进行聚类

K=1是最差的一种结果，total variation此时最大

K=2的效果会稍微好些

随着K值增大，total variation也逐渐减小；当K=N(样本数)时，total variation降至0。

绘制total variation随K值变化的elbow plot

可以看出，K>3时，variation的降低速率明显降低。所以K=3是较好的选择。

二维平面上的点，可以通过欧式距离来判断聚类

然后同之前一般，计算平面上同一cluster的中心，重新判断点的归属，寻找中心……判断归属……

对于热图相关数据，也可以通过欧式距离来判断样本的聚类

https://blog.csdn.net/huangfei711/article/details/78480078

https://www.biaodianfu.com/k-means-choose-k.html

https://www.youtube.com/watch?v=4b5d3muPQmA&feature=youtu.be