K-means怎么选K?

  统计/机器学习 无监督学习 开放问题
14

我们都知道K-means的主要缺点就是在做聚类前,必须要先确定K,也就是样本里聚类的个数。一般有哪些方法呢?我知道手肘法,但是也没有明白这个手肘到底怎么用。

 

道画师   2017-03-03 11:50



   2个回答 
31

对于K-means中K的选择,通常有四种方法。

  • 按需选择
  • 观察法
  • 手肘法
  • Gap Statistics方法

一、按需选择

简单地说就是按照建模的需求和目的来选择聚类的个数。比如说,一个游戏公司想把所有玩家做聚类分析,分成顶级、高级、中级、菜鸟四类,那么K=4;如果房地产公司想把当地的商品房分成高中低三档,那么K=3。按需选择虽然合理,但是未必能保证在做K-Means时能够得到清晰的分界线。

二、观察法

就是用肉眼看,看这些点大概聚成几堆。这个方法虽然简单,但是同时也模棱两可。


左上角是原始点。右上角分成了两类。左下角是三类,左下角是四类。至于K到底是选3还是选4,可能每个人都有不同的选择。

观察法的另一个缺陷就是:原始数据维数要低,一般是两维(平面散点)或者三维(立体散点),否则人类肉眼则无法观察。对于高维数据,我们通常利用PCA降维,然后再进行肉眼观察。

三、手肘法

手肘法本质上也是一种间接的观察法。这里需要一点K-Means的背景知识。当K-Means算法完成后,我们将得到K个聚类的中心点$M_i$, $i=1,2,\cdots,K$。以及每个原始点所对应的聚类$C_i$,$i=1,2,\cdots,K$。我们通常采用所有样本点到它所在的聚类的中心点的距离的和作为模型的度量,记为$D_K$。

$$D_K=\sum_{i=1}^K\sum_{X\in C_i}\|X-M_i\|$$

这里距离可以采用欧式距离。

对于不同的K,最后我们会得到不同的中心点和聚类,所有会有不同的度量。

我们把上面的例子用不同的K去计算,会得到不同的结果。把K作为横坐标,$D_K$作为纵坐标,我们可以得到下面的折线。

很显然K越大,距离和越小。但是我们注意到K=3是一个拐点,就像是我们的肘部一样,K=1到3下降很快,K=3之后趋于平稳。手肘法认为这个拐点就是最佳的K。

手肘法是一个经验方法,而且肉眼观察也因人而异,特别是遇到模棱两可的时候。相比于直接观察法,手肘法的一个优点是,适用于高维的样本数据。有时候人们也会把手肘法用于不同的度量上,如组内方差组间方差比。

四、Gap Statistic方法

这个方法是源自斯坦福几个machine learning大牛的paper Estimating the number of clusters in a data set via the gap statistic 。

这里我们要继续使用上面的$D_K$。Gap Statistic的定义为

$$Gap(K)=\text{E}(\log D_k)-\log D_k$$

这里$\text{E}(\log D_k)$指的是$\log D_k$的期望。这个数值通常通过蒙特卡洛模拟产生,我们在样本里所在的矩形区域中(高维的话就是立方体区域)按照均匀分布随机地产生和原始样本数一样多的随机样本,并对这个随机样本做K-Means,从而得到一个$D_K$。如此往复多次,通常20次,我们可以得到20个$\log D_K$。对这20个数值求平均值,就得到了$\text{E}(\log D_K)$的近似值。最终可以计算Gap Statisitc。而Gap statistic取得最大值所对应的K就是最佳的K

用上图的例子,我们计算了K=1,2,..9对应的Gap Statisitc. 


Gap Statistic的优点是,我们不再需要肉眼了。我们只需要找到最大gap statistic所对应的K即可。所以这种方法也适用于“批量化作业”。如果我们要做1000次聚类分析,不需要肉眼去看1000次了。所以我个人也倾向于这种方法。





高代兄   2017-03-07 13:33

长见识了,方法一我倒是没想到,方法四我是头一次听说。谢谢分享! - 起个好名字   2017-03-07 14:04
这个赞! - Alfred   2017-03-08 11:13
图文并茂! - 擒贼先擒鱼   2017-03-09 13:19
1

有一种叫X-mean的方法可以从2个Cluster开始自动develop新的cluster,直到总体的BIC不能改善。Paper link

Jeremy   2017-05-02 05:12



相关问题

二分法K Means的算法是什么?和普通的K Means有什么区别?   2回答

一维的数据可以做聚类吗?   3回答

层次聚类中的Ward's method是什么意思   0回答

关于小批量K均值(mini-batch K Means)的问题   2回答

K-MEANS初始点选择的问题   1回答

层次聚类里的linkage是什么意思?   1回答

什么是K-Modes(K众数)聚类法?   1回答

软聚类,硬聚类?   1回答

怎么评价一个聚类算法?   1回答

sklearn.cluster.KMeans用的哪种距离?   1回答

进行K-Means聚类前,需要对数据做怎样的预处理?   1回答

可视化K Means的时候怎么把聚类的中心点和样本点连起来?   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!