K-means怎么选K?

对于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次了。所以我个人也倾向于这种方法。

类似于回归里的AIC，K Means里的AIC也可以用来选K。

$$AIC=\text{argmin}_K RSS_K + 2pK$$

其中$RSS_K$是在聚类个数为$K$的时候，root of sum of squares，$p$是特征的个数。

我们选$AIC$最小的那个$K$

可以用MeanShift，它不需要预设cluster的个数，而是自己学习cluster的个数。

相反的，可以先利用MeanShift得到cluster个数，再用K Means。

定K一直是聚类算法的一个研究方向，k-means作为经典算法， 也是解决不了这个问题，如上面那位大神的讲解，之外，还可以根据adjust-R²，CCC值和伪F值判断，都是越大越好，画图来分析寻找合理的聚类个数，如图，进行了6次分群，类数为：3，4，5，6，7，8，最终选择6类，因为在这个值的时候，各项指标已经很好了，后面增加的不是很大，按照奥卡姆剃刀原理，另外，还可以看业务，假如聚类过多，每多一类，那造成的商业成本是很高的，要为每一类做营销方案，每增加一类，成本上升，综合来选，其实这个定k就是结合算法结果和业务，算法只能给我们准确的模型，但是给不出正确的模型。

RPCL算法可以了解一下，可以认为某种程度上不需要设定K，而是自动选择合适的K。

Lei Xu, Adam Krzy˙zak, and Erkki Oja. Rival penalized competitive learning for clustering analysis, rbf net, and curve detection. Neural Networks, IEEE Transactions on, 4(4):636–649, 1993.

在这篇论文中有用到RPCL算法：

Automatic False Positive Canceling for Indoor Human Detection, ICIA2017

以及，我比较naive的重现这篇论文的代码（部分涉及RPCL算法）：https://github.com/zchrissirhcz/dfp

补充一个方法，silhouette score

具体可以参考这篇文章以及sklearn里的例子

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