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

Question

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

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

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

1. 每个维度将空间切成20块.(所以总共有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手册.ANN的精神相似; David Mount在这里提供信息,或者尝试FLANN(具有Matlab和Python绑定).

Answer 2

您可能想尝试我的名为K-tree的研究项目.它与k-means的大输入相比可以很好地扩展,并形成一个簇的层次结构.权衡是它产生具有更高失真的簇.它的平均情况运行时间为O(n log n),最差情况为O(n**2),只有在你有一些奇怪的拓扑时才会发生.复杂性分析的更多细节在我的硕士论文中.我使用它具有非常高的文本数据并且没有问题.

有时,可能会在树中发生错误拆分,其中所有数据都转移到一侧(集群).SVN中的中继处理与当前版本不同.如果存在错误的拆分,它会随机拆分数据.如果存在错误的分裂,则前一种方法可以强制树变得太深.

Answer 3

将数据放入索引(如R*-tree(维基百科)),然后您可以运行许多基于密度的聚类算法(如DBSCAN(维基百科)或OPTICS(维基百科))O(n log n).

基于密度的聚类(维基百科)似乎正是您想要的("不太远")