快速(<n ^ 2)聚类算法 [英] Fast (&lt; n^2) clustering algorithm

问题描述

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

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

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

1. 在每个维度上将空间切成20个片段. (因此，总共有20 ^ 5件).我将根据群集的质心将群集存储在这些网格框中.

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

但是，这似乎给了我比我想要的更多的集群.我还两次实施了与此类似的方法，它们给出了截然不同的答案.

有没有比n ^ 2更快的集群聚类标准方法?概率算法还可以.

解决方案

请考虑采用近似最近邻居(ANN)算法或位置敏感的哈希(LSH)算法.他们不能直接解决聚类问题，但可以告诉您哪些点彼此接近".通过更改参数，可以将close定义为所需的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手册.人工神经网络在精神上是相似的. David Mount在此处有信息，或尝试 解决方案

Consider an approximate nearest neighbor (ANN) algorithm or locality sensitive hashing (LSH). They don't directly solve the clustering problem, but they will be able to tell you which points are "close" to one another. By altering the parameters, you can define close to be as close as you want. And it's fast.

More precisely, LSH can provide a hash function, h, such that, for two points x and y, and distance metric 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. So yes, it is probabilistic. You can postprocess the retrieved data to arrive at true clusters.

Here is information on LSH including the E2LSH manual. ANN is similar in spirit; David Mount has information here, or try FLANN (has Matlab and Python bindings).

这篇关于快速(<n ^ 2)聚类算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！