2.3 k-均值算法的局限性

k-均值算法是一种既简单又好用的方法，基本上可以拿来即用。对于 k-均值算法存在的不足已经讨论了半个多世纪，下面把一些主要的局限和可能的解决思路列出， 供读者参考。因为本书只是一本入门级图书，所以不会就各种改良算法和高级算法进行详细的介绍，有兴趣的读者可以参考相关文献和资料。

k-均值最后聚类的结果对初始 k 个簇的代表点选择很敏感

也就是说，不同的初始条件下得到的聚类结果可能很不一样。

我们先来做一个数学游戏（希望各位读者以后学东西和做学问的时候，要培养这种从最简单的例子入手进行分析的习惯）， 如图 2-16 所示，考虑最简单的一种情况，就是在一个 1 维空间中（d=1），把三个数据点聚成两个类（k=2）。令最左边和最右边的两个数据点的位置为 0 和 1，中间的数据点位置为 x，不失一般性，令 x ≤ 0.5 。两个代表点的初始选择都限定在区间[0,1]之间。如果 x 恰好为 0.5，由对称性可知，初始点的选择正好有 50%的可能性让 0 和 x 分到一组， 1单独为一组；另有 50%的可能性让 0 单独为一组，x 和 1 分到一组。那么，如果 x=0.4 呢？这时有两个稳定的收敛态：第一种情况下收敛后的代表点为(0.2,1)，使得 0 和 x 分到一组，1 单独为一组，代价 S=0.08；第二种情况下，收敛后的代表点为(0,0.7)，使得 0 单独为一组，x 和 1 分到一组，代价 S=0.18。

图 2-16 k-均值算法对初始簇代表点选择敏感性的简单示例

第一种情况好得多，代价要小一半不止。这也与我们的直觉相符合，因为0.4 距离 0 比 1 近。如果两个初始代表点都在[0,1]上随机分布（这是我们选择初始代表点时最常用的方法），那么最佳方案有多大可能性能够最终胜出呢？

显然，有 0.16 的概率两个代表点都落在区间[0, 0.4]，很遗憾，情况二胜出； 有 0.36 的概率两个代表点都落在区间[0.4, 1]，则最佳方案（情况一）胜出。剩下 0.48 的概率，一个点落在区间[0,0.4]，一个点落在区间[0.4,1]，如果左边点所在的位置为 t（t≤0.4），则右边点能够比左边点更接近 x 的概率是(0.4-t)/0.6，所以情况二胜出的概率为

综上，情况二的胜出率为

也就是说，在最优方案明显占优（最优方案的代价仅为 0.08，而差方案代价为 0.18）的情况下，随机分配初始代表点的位置，差的方案竟然有 32%概率会胜出。只有当 x<1/3 的情况下，才可以保证最优方案是唯一收敛的方案。

为了避免初始化带来的可能偏差，实践中最常见的办法是做很多次随机的 初始化，然后执行 k-均值算法，最后选取 S 最小的结果作为算法的结果。尽管这种方法能够部分解决这个问题，但显然是一种无可奈何之举。如果读者对自己有更高的要求，建议阅读 Celebi 的综述^[12]，其中有很多初始化的方法，能够获得明显好于随机初始化的结果。

k-均值只能收敛到局部最优解

优化目标函数(2-1)可不简单，现已证明，对于一般的 d，即便 k=2 问题都是 NP 困难的，对于一般的 k，也是 NP 困难的（关于 P 类问题、NP 类问题、NP 完全问题、NP 困难等概念，如果读者不了解，建议自行查阅相关资料）。对于固定的 d 和 k，如果有 N 个数据对象，精确获得全局最优解的时间复杂度是 ^[8] ，一般会看做一个不可思议的天文数字。用 k-均值算法非常快， 时间复杂度是线性的，其中 k 和 d 一般远小于 N，i 是收敛需要的迭代次数。尽管在一些变态的例子中^[13] ，i 可以非常大，但一般情况下 i 非常小。

虽然快，但是 k-均值本质上是一个爬山法^[14]，很容易陷入局部最优出不来。例如上面的例子中，算法有 32%的可能性陷入某种局部最优中（尽管只有 2 个坑，就有 1/3 的机会选到错误的那个坑）。如刚才针对初始敏感性的思路，一种有效而简单的方法就是多选择一些不同的初始条件，从中选择最好的结果。另外，可以在已经获得收敛解的前提下，进行一些局部的搜索，尽可能提高算法的效果^[15]。

不知道如何确定一个合适的 k 值

我们一开始就做了说明，在基本的 k-均值算法中，k 是给定的，不是通过数据学习出来了。显而易见，k 值大小对于算法的结果至关重要，因此，如何选择最合适的 k 就成了实践中让人头痛的问题。你可能一拍脑袋说，这个容易，我们每次选择不同的 k，每个 k 多做几次实验，看看平均而言什么样的 k 可以得到最小的 S 值，就选这样的 k。方法虽然朴实，听起来没毛病，但是随着 k 的增大，S 的趋势是下降的，当 k=N 时，每个簇只有一个数据对象，此时 S=0。但是，这 种平凡的每个对象一个簇的划分方式是没有实际价值的。所以，我们必须在不 那么大的 k 和小的 S 值之间选择一个平衡，一种直观的方法是在目标函数 S 上加一个惩罚项，随着k值的增大而增大。k-均值算法类中有一个非常著名的算法，称为x-均值（x-means）^[16]，就是具有自动学习k值的功能，其思路与上面是一样的。在实际应用k-均值算法时，如果已经知道k值（如已经确定要修5个消防站），或者根据需要知道k值比较紧凑的一个范围（如预算显示新消防站数据在3～5个），那么大家可以一个一个试，否则建议使用x-均值，而不是直接用k-均值算法。

k-均值算法还存在一些其他问题。例如，k-均值算法对于噪音点特别是偏离很远的异常点非常敏感，这是因为它采用了距离的平方作为相似性的度量。要克服这个问题， 就需要采用不同的相似性定义， 如距离的绝对值， 但这时就不能用 k-均值的方法来做优化，所以这里不展开介绍。另外，k-均值只擅长处理凸形的数据点分布，对于长相怪异的非凸数据分布常常无能为力，这时我们往往需要使用基于密度的方法。这些方法超出了本书的范围，有兴趣的读者可以参考相关教材和文献^[8] 。如果只能推荐一篇，那就是 Jain 最近的一篇综述^[16] ，可以作为一个导引手册，帮助读者了解这个领域的全貌和前沿。