如何正确使用“K均值聚类”？

本文首发于微调的知乎专栏「数据说」。

聚类算法中的第一门课往往是K均值聚类（K-means），因为其简单高效。本文主要谈几点初学者在使用K均值聚类时需要注意的地方。

1. 输入数据一般需要做缩放，如标准化。

原因很简单，K均值是建立在距离度量上的，因此不同变量间如果维度差别过大，可能会造成少数变量“施加了过高的影响而造成垄断”。

2. 如果输入数据的变量类型不同，部分是数值型（numerical），部分是分类变量（categorical），需要做特别处理。

方法1是将分类变量转化为数值型，但缺点在于如果使用独热编码（one hot encoding）可能会导致数据维度大幅度上升，如果使用标签编码（label encoding）无法很好的处理数据中的顺序（order）。方法2是对于数值型变量和分类变量分开处理，并将结果结合起来，具体可以参考Python的实现[1]，如K-mode和K-prototype。

3. 输出结果非固定，多次运行结果可能不同。

首先要意识到K-means中是有随机性的，从初始化到收敛结果往往不同。一种看法是强行固定随机性，比如设定sklearn中的random state为固定值。另一种看法是，如果你的K均值结果总在大幅度变化，比如不同簇中的数据量在多次运行中变化很大，那么K均值不适合你的数据，不要试图稳定结果 [2]。

我个人倾向于后者的看法，K均值虽然易懂，但效果一般，如果多次运行的结果都不稳定，不建议使用K均值。我做了一个简单的实验，用K均值对某数据进行了5次聚类：

km = MiniBatchKMeans(n_clusters=5)

fori inrange(5):

labels = km.fit_predict(seg_df_norm)

label_dist = np.bincount(labels)/seg_df_norm.shape[]*100

print(label_dist)

打印出每次簇中的数据量占比如下，可以看出几次运行中每次簇中的数据比例都有很大差别。此处我们明白顺序可以是随机的，但占比应该是相对固定的，因此K均值不适合当前数据集。

[24.60715.41425.487726.745117.7461]

[54.372819.08360.131426.31330.0988]

[12.995152.58794.657615.626814.1325]

[19.452744.20547.512124.90783.9221]

[21.304649.92332.188615.225511.358]

4. 运行时间往往可以得到优化，选择最优的工具库。

基本上现在的K均值实现都是K-means++，速度都不错。但当数据量过大时，依然可以使用其他方法，如MiniBatchKMeans [3]。上百万个数据点往往可以在数秒钟内完成聚类，推荐Sklearn的实现。

5. 高维数据上的有效性有限。

建立在距离度量上的算法一般都有类似的问题，那就是在高维空间中距离的意义有了变化，且并非所有维度都有意义。这种情况下，K均值的结果往往不好，而通过划分子空间的算法（sub-spacing method）效果可能更好。

6. 运行效率与性能之间的取舍。

但数据量上升到一定程度时，如>10万条数据，那么很多算法都不能使用。最近读到的一篇对比不同算法性能随数据量的变化很有意思 [4]。在作者的数据集上，当数据量超过一定程度时仅K均值和HDBSCAN可用。

作者还做了下图以供参考对比。在他的实验中大部分算法如果超过了10万条数据后等待时长就变得很高，可能会需要连夜运行。在我的实验中，还会发现不少算法（SpectralClustering，AgglomerativeClustering等）面临内存不够的问题（memory error）。

File"C:\Users\xyz\AppData\Local\Continuum\anaconda3\lib\site-packages\scipy\spatial\distance.py",line1652, in pdist

dm = np.empty((m* (m-1)) //2, dtype=np.double)

MemoryError

总结

因此不难看出，K均值算法最大的优点就是运行速度快，能够处理的数据量大，且易于理解。但缺点也很明显，就是算法性能有限，在高维上可能不是最佳选项。

一个比较粗浅的结论是，在数据量不大时，可以优先尝试其他算法。当数据量过大时，可以试试HDBSCAN。仅当数据量巨大，且无法降维或者降低数量时，再尝试使用K均值。

一个显著的问题信号是，如果多次运行K均值的结果都有很大差异，那么有很高的概率K均值不适合当前数据，要对结果谨慎的分析。

此外无监督聚类的评估往往不易，基本都是基于使用者的主观设计，如sklearn中提供的Silhouette Coefficient和 Calinski-Harabaz Index [5]。更多关于无监督学习如何评估可以参考 [6]。

[1] nicodv/kmodes

[2] Changes of clustering results after each time run in Python scikit-learn

[3] sklearn.cluster.MiniBatchKMeans - scikit-learn 0.19.1 documentation

[4] Benchmarking Performance and Scaling of Python Clustering Algorithms

[5] 2.3. Clustering - scikit-learn 0.19.1 documentation

[6] 微调：一个无监督学习算法，如何判断其好坏呢?