06-k均值聚类算法问题及其扩展

6.5　k均值聚类算法问题及其扩展

如果实现k均值聚类算法时用了随机起点，则数据集里有意义的划分点可能会被完全错过。这通常会让操作人员经历大量的试错才能得出结果。如果操作人员无法看出数据的分组数，那么找出正确的“k”值（聚类簇的数量）也是困难且容易出错的。

k均值聚类算法还存在比较复杂的版本，可以利用它们尝试对造成困难的变量进行有依据的猜测或自动试错。k-means++（k 均值++）就是一种比较流行的变体算法，它不是完全随机地选择形心，而是基于到各点距离的概率分布来选择形心，以解决形心初始化的问题。对很多应用程序而言，更好的选择是根据提前知晓的数据信息选择合适的起始区域，以获取各个形心值。换句话说，这种k均值聚类算法是由用户来选取初始的各个形心。

k均值聚类操作的运行时间与数据点的数量、聚类簇的数量和数据点的维度数成正比。如果数据点数量很多，数据点的维度数也很多，那么基础版的k均值聚类算法将不再具有可用性。有些扩展版本的算法试图在每个数据点和每个形心之间不进行尽可能多的计算，方法是在计算之前首先评估一下某数据点是否真有可能会移到别的聚类簇中去。对于多点或高维度的数据集还有一种选择，就是只对数据点的采样数据进行k均值聚类操作，对采样数据运行的结果将会近似于完整算法可能求得的聚类簇。

数据集里的野值可能会导致奇怪的k均值聚类结果。如果初始形心恰好落在野值附近，就可能会形成一个聚类簇（迈克尔·杰克逊示例中的HIStory专辑就有可能发生）。如果去除了野值，k均值聚类算法将能运行得更好。

良好的形心判断方案并不一定要通过均值。k-medians算法将判断每个维度的中位数，k-medoids算法则使用数据集中的实际点值作为每个聚类簇的中心。若是选用这些方法来确定中心点，对统计学知识的要求已超出了本书的范围，但常识说明对于棘手的问题可能值得用每一种算法去尝试，并对结果进行抽样。其实这些算法的实现代码并没有很大的差别。