快速（<n ^ 2）聚类算法-Java 学习之路

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

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

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

每个维度将切片空间分成20个部分 . （所以总共有20 ^ 5件） . 我会根据它们的质心将簇存储在这些网格盒中 .
对于每个点，检索r（最大边界球半径）内的网格框 . 如果有足够的群集，请将其添加到该群集，否则创建新群集 .

但是，这似乎给了我比我想要的更多的集群 . 我也实现了两次类似的方法，它们给出了非常不同的答案 .

是否有任何标准的聚类方法比n ^ 2时间快？概率算法没问题 .

6 回答

5
考虑 approximate nearest neighbor （ANN）算法或 locality sensitive hashing （LSH） . 他们快得快 .

更确切地说，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的精神相似; David Mount有信息here，或者尝试FLANN（有Matlab和Python绑定） .
回复于 2024-05-06T15:42:44+08:00
3

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

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

回复于 2024-05-06T15:42:44+08:00
2

将数据放入索引（例如R*-tree (Wikipedia)），然后您可以在 O(n log n) 中运行许多基于密度的聚类算法（例如DBSCAN (Wikipedia)或OPTICS (Wikipedia)） .

Density-based clustering (Wikipedia)似乎正是你想要的（"not too far apart"）

回复于 2024-05-06T15:42:44+08:00

下面是一个小测试平台，可以看到scipy.spatial.cKDTree对您的数据有多快，并且可以大致了解附近点之间的距离是如何分散的 .

为各种K运行K-cluster的一个好方法是构建最近对的MST，并移除最长的K-1;见Wayne, Greedy Algorithms .

可视化集群会很有趣 - 用PCA计划到2d？

（只是好奇，你的K 10,100,1000？）

12月17日增加：实际运行时间：100000 x 5 10秒，500000 x 5 60秒

#!/usr/bin/env python
# time scipy.spatial.cKDTree build, query

from __future__ import division
import random
import sys
import time
import numpy as np
from scipy.spatial import cKDTree as KDTree
    # http://docs.scipy.org/doc/scipy/reference/spatial.html
    # $scipy/spatial/kdtree.py is slow but clean, 0.9 has cython
__date__ = "2010-12-17 dec denis"

def clumpiness( X, nbin=10 ):
    """ how clumpy is X ? histogramdd av, max """
        # effect on kdtree time ? not much
    N, dim = X.shape
    histo = np.histogramdd( X, nbin )[0] .astype(int)  # 10^dim
    n0 = histo.size - histo.astype(bool).sum()  # uniform: 1/e^lambda
    print "clumpiness: %d of %d^%d data bins are empty  av %.2g  max %d" % (
        n0, nbin, dim, histo.mean(), histo.max())

#...............................................................................
N = 100000
nask = 0  # 0: ask all N
dim = 5
rnormal = .9
    # KDtree params --
nnear = 2  # k=nnear+1, self
leafsize = 10
eps = 1  # approximate nearest, dist <= (1 + eps) * true nearest
seed = 1

exec "\n".join( sys.argv[1:] )  # run this.py N= ...
np.random.seed(seed)
np.set_printoptions( 2, threshold=200, suppress=True )  # .2f
nask = nask or N
print "\nkdtree:  dim=%d  N=%d  nask=%d  nnear=%d  rnormal=%.2g  leafsize=%d  eps=%.2g" % (
    dim, N, nask, nnear, rnormal, leafsize, eps)

if rnormal > 0:  # normal point cloud, .9 => many near 1 1 1 axis
    cov = rnormal * np.ones((dim,dim)) + (1 - rnormal) * np.eye(dim)
    data = np.abs( np.random.multivariate_normal( np.zeros(dim), cov, N )) % 1
        # % 1: wrap to unit cube
else:
    data = np.random.uniform( size=(N,dim) )
clumpiness(data)
ask = data if nask == N  else random.sample( data, sample )
t = time.time()

#...............................................................................
datatree = KDTree( data, leafsize=leafsize )  # build the tree
print "%.1f sec to build KDtree of %d points" % (time.time() - t, N)

t = time.time()
distances, ix = datatree.query( ask, k=nnear+1, eps=eps )
print "%.1f sec to query %d points" % (time.time() - t, nask)

distances = distances[:,1:]  # [:,0] is all 0, point to itself
avdist = distances.mean( axis=0 )
maxdist = distances.max( axis=0 )
print "distances to %d nearest: av" % nnear, avdist, "max", maxdist

# kdtree:  dim=5  N=100000  nask=100000  nnear=2  rnormal=0.9  leafsize=10  eps=1
# clumpiness: 42847 of 10^5 data bins are empty  av 1  max 21
# 0.4 sec to build KDtree of 100000 points
# 10.1 sec to query 100000 points
# distances to 2 nearest: av [ 0.07  0.08] max [ 0.15  0.18]

# kdtree:  dim=5  N=500000  nask=500000  nnear=2  rnormal=0.9  leafsize=10  eps=1
# clumpiness: 2562 of 10^5 data bins are empty  av 5  max 80
# 2.5 sec to build KDtree of 500000 points
# 60.1 sec to query 500000 points
# distances to 2 nearest: av [ 0.05  0.06] max [ 0.13  0.13]
# run: 17 Dec 2010 15:23  mac 10.4.11 ppc

回复于 2024-05-06T15:42:44+08:00

6

人们的印象是k-means是缓慢的，但是慢速实际上只是EM算法（Lloyd's）的一个问题 . k-means的随机梯度方法比EM快几个数量级（参见www.eecs.tufts.edu/~dsculley/papers/fastkmeans.pdf） .

这里有一个实现：http://code.google.com/p/sofia-ml/wiki/SofiaKMeans

回复于 2024-05-06T15:42:44+08:00
3
我有一个Perl模块，可以完全按照你想要的那样运行Algorithm::ClusterPoints .

首先，它使用您在帖子中描述的算法来划分多维扇区中的点，然后使用强力来查找相邻扇区中的点之间的聚类 .

在非常恶化的情况下，复杂性从O（N）到O（N ** 2）不等 .

update ：

@Denis：不，情况要糟糕得多：

对于 d 维度，确定扇区（或小超立方体）大小 s ，使其对角线 l 是不同簇中两点之间允许的最小距离 c .
```
l = c
l = sqrt(d * s * s)
s = sqrt(c * c / d) = c / sqrt(d)
```
然后你必须考虑所有触及超球面的扇区，直径 r = 2c + l 以枢轴扇区为中心 .

粗略地说，我们必须考虑 ceil(r/s) 行各个方向的部门，这意味着 n = pow(2 * ceil(r/s) + 1, d) .

例如，对于 d=5 和 c=1 ，我们得到 l=2.236 ， s=0.447 ， r=3.236 和 n=pow(9, 5)=59049

实际上我们必须检查较少的邻居扇区，因为我们正在考虑那些触及尺寸为 (2r+1)/s 的超立方体的那些，我们只需要检查触及限制超球面的那些 .

考虑到“在同一群集”关系的双射性质，我们也可以将需要检查的扇区数量减半 .

具体来说，算法:: ClusterPoints用于 d=5 检查3903个扇区的情况 .
回复于 2024-05-06T15:42:44+08:00

快速（<n ^ 2）聚类算法

6 回答

相关问题