我有 100 万个 5 维点，需要将它们分组为 k 个簇，其中 k
但！我需要运行时间远低于 n^2。 n log n 左右应该没问题。我进行此聚类的原因是为了避免计算所有 n 个点的距离矩阵（这需要 n^2 时间或多个小时），而是我只想计算聚类之间的距离。
我尝试了 pycluster k-means 算法，但很快意识到它太慢了。我还尝试了以下贪心方法：
将空间在每个维度上切成 20 块。 （所以总共有 20^5 块）。我将根据它们的质心将簇存储在这些网格框中。
对于每个点，检索 r（最大边界球体半径）内的网格框。如果有足够近的簇，则将其添加到该簇中，否则创建一个新簇。
然而，这似乎给了我比我想要的更多的集群。我也两次实施了类似的方法，但他们给出了截然不同的答案。
是否有任何标准方法可以比 n^2 时间更快地进行聚类？概率算法没问题。
考虑一个近似最近邻（ANN）算法或局部敏感哈希（LSH）。它们不直接解决聚类问题，但它们能够告诉您哪些点彼此“接近”。通过更改参数，您可以将 close 定义为您想要的接近程度。而且速度很快。
更准确地说，LSH可以提供哈希函数，h，这样对于两点x and y和距离度量d,
d(x,y) <= R1 => P(h(x) = h(y)) >= P1
d(x,y) >= R2 => P(h(x) = h(y)) <= P2
where R1 < R2 and P1 > P2。所以是的，这是概率性的。您可以对检索到的数据进行后处理以获得真正的聚类。
这里有关于LSH http://www.mit.edu/~andoni/LSH/包括E2LSH说明书 http://www.mit.edu/~andoni/LSH/manual.pdf。 ANN 在精神上是相似的；大卫·蒙特有信息here http://www.cs.umd.edu/~mount/ANN/，或者尝试FLANN http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN（具有 Matlab 和 Python 绑定）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
