algorithm - 快速 (< n^2) 聚类算法

Question

我有 100 万个 5 维点，我需要将它们分组为 k 个簇，其中 k << 100 万。在每个集群中，任何两个点都不应相距太远(例如，它们可以是具有指定半径的边界球体)。这意味着可能必须有许多大小为 1 的簇。

但是!我需要运行时间远低于 n^2。 n log n 左右应该没问题。我进行此聚类的原因是为了避免计算所有 n 个点的距离矩阵(这需要 n^2 时间或许多小时)，而我只想计算聚类之间的距离。

我尝试了 pycluster k-means 算法，但很快意识到它太慢了。我还尝试了以下贪心方法:

1. 在每个维度上将空间分成 20 block 。 (所以总共有 20^5 件)。我将根据它们的质心将簇存储在这些网格框中。

2. 对于每个点，检索在 r(最大包围球半径)内的网格框。如果有一个足够接近的集群，则将其添加到该集群，否则创建一个新集群。

但是，这似乎给我提供了比我想要的更多的集群。我也实现了两次类似的方法，但他们给出了截然不同的答案。

有没有比 n^2 时间更快的聚类标准方法？概率算法还可以。

Answer 1

考虑近似最近邻 (ANN) 算法或局部敏感散列 (LSH)。它们不会直接解决聚类问题，但它们能够告诉您哪些点彼此“接近”。通过更改参数，您可以将 close 定义为尽可能接近。而且速度很快。

更准确地说，LSH 可以提供一个散列函数，h ，这样，对于两个点 x和 y和距离度量 d ,

d(x,y) <= R1  =>  P(h(x) = h(y)) >= P1
d(x,y) >= R2  =>  P(h(x) = h(y)) <= P2

哪里R1 < R2和 P1 > P2 .所以是的，这是概率性的。您可以对检索到的数据进行后处理以获得真正的聚类。

这里是关于 LSH 的信息包括 E2LSH manual . ANN 在精神上是相似的；大卫芒特有资料here ，或尝试 FLANN (具有 Matlab 和 Python 绑定(bind))。