为什么Kruskal聚类会产生次优类？

Question

我正在尝试开发一种聚类算法,其任务是在一组2D点上找到k类(使用k作为输入),使用轻微修改的Kruskal算法来找到k个生成树而不是一个.

我使用兰特指数将我的输出与建议的最优值(1)进行了比较,对于k = 7,我得到了95.5%.比较可以在下面的链接中看到.

问题:

该组具有5个明显间隔的簇,这些簇很容易被算法分类,但是当k> 5时结果相当令人失望,这就是事情开始变得棘手的时候.我相信我的算法是正确的,也许数据对于Kruskal方法特别糟糕.已知单链接聚类聚类(例如Kruskal)在某些问题上表现不佳,因为它将聚类质量的评估减少到一对点之间的单一相似性.

算法的想法很简单:

• 使用数据集制作完整的图形,边缘的权重是该对之间的欧氏距离.
• 按重量对边缘列表进行排序.
• 对于每个边(按顺序),如果它不形成循环,则将其添加到生成林.遍历所有边缘或剩余森林有k棵树时停止.

底线: 为什么算法失败了？这是Kruskal的错吗？如果是这样,为什么呢？有什么建议可以在不放弃Kruskal的情况下改善结果？

(1):Gionis,A.,H.Mannila和P. Tsaparas,聚类聚合.ACM数据知识发现交易(TKDD),2007.1(1):p.1-30.

Answer 1

这称为单链接效应。

Kruskal 似乎是计算单链接聚类的一种半聪明的方法。“层次聚类”的简单方法是O(n^3)，而 Kruskal 方法应该是O(n^2 log n)由于必须对n^2边缘进行排序。

O(n^2)请注意，SLINK 可以在运行时和内存中进行单链接聚类O(n)。

您是否尝试过将数据集加载到ELKI中，并将结果与​​单链接聚类进行比较。

为了获得更好的结果，请尝试其他链接（通常在O(n^3)运行时）或基于密度的聚类，例如DBSCAN（O(n^2)不带索引和O(n log n)带索引）。在这个玩具数据集上，epsilon=2应该minPts=5可以很好地工作。