Breathing KMeans 与 KMeans 的对比

Breathing KMeans vs KMeans

KMeans 因其作为聚类算法的简洁与有效而被广泛使用。然而我们都知道，它的表现完全取决于质心初始化这一步。因此，我们很可能会得到不准确的簇，如下图所示：

当然，使用不同的初始化重新运行有时确实有帮助。但我从来都不喜欢它带来的不必要的运行时开销。本章中，让我们来学习 KMeans 的一个强力升级版，它在解决这一问题的同时还能产生更好的聚类结果。它叫做 Breathing KMeans 算法。

首先，我们只运行一次常规的 KMeans 聚类，即不再用不同的初始化重新运行算法。

KMeans 在不重复运行、并迭代至收敛（convergence）后得到的聚类结果。这给我们得到了“k”个质心的位置，它们可能准确，也可能不准确。

在第 1 步得到的“k”个质心基础上，我们再加入“m”个新质心。根据 Breathing KMeans 的研究论文，m=5 是一个不错的取值。现在你可能会想，这“m”个质心要加在哪里呢？新质心的加入是根据质心所关联的误差来决定的。简单来说，一个质心的误差是它到与其相关联的数据点之间距离的平方和。

因此，我们在误差较高的质心附近加入“m”个质心。让我们更直观地理解一下这样做为什么合理。

在上面的 KMeans 聚类结果中：

• 顶部的那个质心误差很高。
• 所有其他质心的误差都相对较低。

直观地说，如果一个质心的误差非常高，那么可能有多个簇都与它相关联。因此，我们希望把这个簇拆分开。在误差高的簇附近添加新质心，正好能够实现这一目标。在加入“m”个新质心后，我们总共得到“k+m”个质心。最后，我们用这“k+m”个质心只再运行一次 KMeans，得到“k+m”个质心的位置。

接下来，我们要从上面得到的“k+m”个质心中移除“m”个。你可能会想，应该移除哪“m”个质心呢？质心的移除取决于一个质心的“效用（utility）”。简单来说，一个质心的效用与它到所有其他质心的距离成正比。距离越大，它就越孤立，因而效用越高。

这在直观上同样讲得通。如果两个质心靠得很近，它们的效用就会很低。因此，它们很可能处在同一个簇中，我们必须移除其中一个。

下面展示了这一过程：

移除其中一个低效用质心后，另一个质心就会变得非常有用。所以在实践中，移除一个质心之后，我们会更新所有其他质心的效用值。我们重复该过程，直到所有“m”个低效用质心都被移除，从而重新得到“k”个质心。最后，我们用这“k”个质心只再运行一次 KMeans。

完成了！这些反复的“呼吸”周期（吸气与呼气步骤）几乎总能比带重复的标准 KMeans 更快、更好地给出解。在每个周期中：

• 在“好的”位置上添加新质心。这有助于拆分由单个质心占据的簇。
• 移除低效用的质心。这有助于剔除那些很可能处在同一簇中的质心。

因此，它有望更快地收敛（convergence）到最优解。Breathing KMeans 相对于 KMeans 的有效性从下图中可以明显看出：

• KMeans 产生了两个放错位置的质心。
• Breathing KMeans 准确地对数据进行了聚类，运行时间还提升了 50%。此外还有一个 Breathing KMeans 的开源实现，提供了类似 sklearn 的 API。要开始使用，先安装 bkmeans 库：

Python pip install bkmeans

接下来，按如下方式运行该算法：

Python from bkmeans import BKMeans bkm = BKMeans(n_clusters = 100) bkm.fit(X)