0

我正在尝试实现质量阈值聚类算法。下面列出了它的大纲（取自此处）：

  1. 初始化集群允许的阈值距离和最小集群大小
  2. 为每个数据点构建一个候选聚类，包括最近点、次最近点等，直到聚类的距离超过阈值
  3. 将点数最多的候选聚类保存为第一个真正的聚类，并将聚类中的所有点从进一步考虑中删除
  4. 用减少的点集重复，直到不能再形成具有最小集群大小的集群

我一直在阅读一些最近邻搜索算法和空间分区数据结构，因为它们似乎是我需要的那种东西，但我无法确定使用哪一个，或者我是否应该查看其他东西.

我想自己实现数据结构以用于教育目的，并且我需要一个可以连续返回某个点的最近点的数据结构。但是，由于我不知道需要查询的次数（即直到超过阈值），所以我不能使用 k-最近邻算法。我一直在研究四叉树和 kd 树。

此外，由于该算法不断构建新的候选集群，因此使用修改后的数据结构会很有趣，该数据结构使用缓存信息来加速后续查询（但也考虑到点删除）。

4

1 回答 1

2

该算法听起来像是DBSCAN (Wikipedia)的前身，众所周知，它与R*-Tree 索引 (Wikipedia)配合得很好。但当然，kd-trees 也是一种选择。这两者之间的主要区别在于 R*-trees 用于数据库 - 它们非常支持在线插入和删除，并且是面向块的 - 而 kd-trees 更多的是基于二进制拆分的内存数据结构。R*-trees 执行重新平衡，而 kd-trees 会慢慢变得不平衡，需要重建。我发现 R*-trees 中的最近邻搜索比 kd-trees 更容易理解，因为边界矩形非常直观。

DBSCAN 还从进一步考虑中“删除”点，但只需将它们标记为已分配。这样你就不需要更新索引了；并且在开始时批量加载一次就足够了。您也应该能够为 QT 执行此操作。因此，除非我弄错了，否则您可以通过运行 DBSCAN 并epsilon设置为 QT集群来有效地获得 QT 集群minPts=2（尽管人们更喜欢在适当的 DBSCAN 中使用更高的值）。

周围有许多 DBSCAN 实现。Weka中的那个特别糟糕，所以远离它。R 中的fpc实现还可以，但仍然可以快得多。ELKI好像是唯一一个全索引支持的，速度差别很大。他们的基准通过在该数据集上使用索引显示了 12 倍的速度增益，允许它们在 50 秒内而不是 603 秒（没有索引）内聚集。Weka 花了令人难以置信的 37917 秒，R fpc 4339 在那里。这与我的经验一致，Weka 以非常慢着称，而 R 只在矢量化操作方面表现出色，一旦 R 解释器必须工作，它比任何原生的都要慢得多。但这是一个很好的例子，说明当不同的人实现相同的算法时，它的表现会有多么不同。我原以为这是 2x-5x，但显然，从一个实现相同算法的程序员到另一个程序员，差异很容易达到 50 倍。

于 2012-12-17T07:37:59.940 回答