6

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

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

问题：

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

算法的思想很简单：

  • 用数据集做一个完整的图，边的权重是这对之间的欧几里得距离。
  • 按权重对边缘列表进行排序。
  • 对于每条边（按顺序），如果它不形成循环，则将其添加到生成林中。当所有的边都被遍历完或者剩余的森林有 k 棵树时停止。

在此处输入图像描述

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

(1)：Gionis, A.、H. Mannila 和 P. Tsaparas，聚类聚合。ACM Transactions on Knowledge Discovery from Data (TKDD)，2007.1(1)：p.1-30。

4

3 回答 3

5

这被称为单链接效应。

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工作得很好。

于 2013-12-06T09:36:14.410 回答
2

应该不同的集群之间的桥梁是 Kruskal 出错的典型例子。对于每个点，您可以尝试用距该点的第二短距离覆盖距该点的最短距离 - 这可能会增加桥梁的长度而不增加其他长度。

肉眼看来，这看起来像是 K-means 可能做得很好的东西——除了左上角，这些簇几乎是圆形的。

于 2013-12-05T05:50:30.210 回答
0

您可以尝试曼哈顿距离，但要获得更好的效果，您可以尝试经典的直线和圆检测算法。

于 2013-12-05T05:37:59.303 回答