algorithm - 为什么Kruskal聚类会生成次优类？

我正在尝试开发一种聚类算法，该算法的任务是使用一组经过稍微修改的Kruskal算法来查找k个生成树而不是一个，从而在一组2D点上找到k个类(输入k个)。

我将我的输出与使用rand指数的建议最佳值(1)进行了比较，对于k = 7，结果为95.5％。可以在下面的链接上看到比较。

问题:

该集合具有5个明显隔开的簇，可以通过算法轻松分类，但是当k> 5时，结果变得令人失望，这是事情开始变得棘手的时候。我相信我的算法是正确的，也许对于Kruskal方法而言，数据特别糟糕。众所周知，诸如Kruskal的单链接聚集聚类在某些问题上表现不佳，因为它将聚类质量的评估降低为一对点之间的单个相似性。

该算法的思想非常简单:

使用数据集以及边缘的权重制作完整的图形
是这对之间的欧几里得距离。

按权重对边缘列表进行排序。

对于每个边缘(按顺序)，如果不形成循环，则将其添加到生成林中。遍历所有边缘或剩余的森林有k棵树时停止。

底线:
为什么算法会那样失败？是克鲁斯卡尔的错吗？如果是这样，为什么呢？有什么建议可以在不放弃Kruskal的情况下改善结果吗？

(1):Gionis，A.，H。Mannila和P.Tsaparas，聚类聚集。进行ACM交易
从数据中发现知识(TKDD)，2007.1(1):p.1-30。

最佳答案

这被称为单链接效果。

Kruskal似乎是计算单链接集群的一种半巧妙的方法。 “分层聚类”的幼稚方法是O(n^3)，由于必须对O(n^2 log n)边缘进行排序，因此Kruskal方法应该是n^2。

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

您是否尝试过加载数据集，例如放入ELKI，并将您的结果与单链接聚类进行比较。

要获取bette结果，请尝试其他链接(通常在O(n^3)运行时中)或基于密度的集群，例如DBSCAN(在没有索引的O(n^2)中和在有索引的O(n log n)中)。在此玩具数据集上，epsilon=2和minPts=5应该可以正常工作。