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

我正在尝试开发一种聚类算法,其任务是在一组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.