为什么 K-means 算法优于 Kruskal 的聚类算法

Why is K-means algorithm preferred over Kruskal's algorithm for Clustering

我正在学习 Andrew Ng 在 Coursera 上的机器学习课程。在讨论聚类时,他告诉我们,K-均值聚类算法是使用最广泛的。 我之前还使用了 Kruskal 的聚类算法,这是一种非常有效的算法,具有路径压缩和基于等级的联合。 是什么让 K-means 优于 Kruskal 算法?

Kruskal 算法和 k-means 聚类通常会生成非常不同的聚类,因为它们经过优化可以找到不同的东西。

举个例子,考虑一条线上的 n 个点,这些点或多或少均匀分布,除了每个点离右边的点比左边的点稍微远一点。也就是说,如果缩小,您或多或少会看到 n 个均匀分布的点,但在放大时,您会发现距离并不完全相同,而是从左到右增加。

Kruskal 算法找到了一个最大分离聚类,这意味着它将节点分开,使得聚类之间的距离为尽可能大。在这种情况下,k=2 的最大分离聚类会是什么样子?由于距离随着我们从左向右移动而增加,它会找到“除了最右边的节点之外的所有内容”和“最右边的节点”的聚类。

另一方面,

K 均值聚类发现 最小化簇内方差 的聚类,这意味着它分组节点,以便集群节点通常彼此靠近。 运行 上述数据集上的 k-means 会将点沿中心线大致分成两半,返回大小大致相同的两个簇。

那么哪个是“更好”的聚类?这取决于您的应用程序。我怀疑我们更喜欢第二个集群是因为我们希望集群中的节点尽可能彼此相似。这就是为什么我们经常看到 k-means 聚类比 Kruskal 算法使用得更多,尽管在某些情况下 Kruskal 还是很不错的。

请注意,此问题与效率正交。是的,Kruskal 的算法非常快,但它计算的东西与 k-means 计算的不同。

希望对您有所帮助!