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

Question

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

algorithmmachine-learningcluster-analysisdata-miningk-means

26

我有一百万个五维点需要分成 k 个簇，其中 k <<100 万。在每个簇中，任何两个点都不应该离得太远（例如，它们可以是具有指定半径的边界球）。这意味着可能必须有许多大小为1的簇。

但是！我需要运行时间明显低于n ^ 2。 n log n左右就可以了。我做这个聚类的原因是为了避免计算所有n个点的距离矩阵（需要n ^ 2时间或数小时），而是只想计算集群之间的距离。

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

切割空间为每个维度的20个部分（因此总共有20 ^ 5个部分）。我将按照它们的质心将簇存储在这些网格盒中。

对于每个点，请检索在r（最大边界球半径内）的网格盒。如果有足够接近的簇，则将其添加到该簇中，否则创建一个新簇。

然而，这似乎给了我比我想要的更多的簇。我还实现了类似此的方法两次，并且它们给出了非常不同的答案。

有没有标准的聚类方法可以更快地达到n ^ 2时间以下？概率算法可以使用。

- John Hawksley

2

你可以探索BIRCH：http://people.cs.ubc.ca/~rap/teaching/504/2005/slides/Birch.pdf - Dr. belisarius

谢谢，我会看一下的。它似乎基本上使用了多阶段方法，这也是我接下来想做的事情。例如，首先删除远离所有其他点的点，然后进行一些单遍聚类，然后进行重新平衡等操作。每个步骤都很快。但实现起来很麻烦。 - John Hawksley

也许这里可以使用双 KD 树算法？ - Jules

也许这个链接有用：http://www.cs.cmu.edu/~avrim/Papers/bbg-clustering.pdf - Thomas Ahle

这是IEEE的一篇相对较新的调查论文：https://mospace.umsystem.edu/xmlui/bitstream/handle/10355/29297/Survey_Of_Clustering_Algorithms.pdf（Xu＆Wunsch，IEEE Trans。神经网络卷16号3，2005年5月） - tripleee

1

我找到的三维像素数据（C++源代码）最快的方法可以在此处找到：http://www.modejong.com/blog/post17_divquant_clustering。 - MoDJ

6个回答

6

你可能会对我的研究项目 K-tree 感兴趣。它在处理大输入数据时比 k-means 更为高效，并形成了一种层次化的聚类结构。但是，它产生的聚类失真度较高。其平均情况下的运行时间为 O(n log n)，最坏情况下为 O(n**2)，只有在拓扑结构很奇特的情况下才会出现最坏情况。更多复杂性分析的细节请参见我的Masters thesis。我已经将其用于非常高维的文本数据，并且没有遇到任何问题。

有时，树中会发生所有数据都被划分到一侧（聚类）的不良分裂情况。SVN 中的主干与当前版本的处理方式不同。如果出现不良分裂，它会随机分割数据。以前的方法可能会强制使树变得过深，如果存在不良分裂的话。

- Chris de Vries

1

K-means的规模为O(nki)，你确定你的方法真的更优吗？ - Has QUIT--Anony-Mousse

它似乎也与二分k均值算法密切相关（应该在O（ni）中运行，即更好地适用于大的k）。 - Has QUIT--Anony-Mousse

5

将数据存放在一个索引中，例如R*-tree (维基百科)，然后你就可以在 O(n log n) 的时间复杂度内运行许多基于密度的聚类算法（如DBSCAN (维基百科)或OPTICS (维基百科)）。基于密度的聚类算法 (维基百科)似乎正是你想要的（“不太远离”）。

- Has QUIT--Anony-Mousse

1

R/R+/R*-Tree和KD-tree似乎非常相似。如果您要自己实现数据结构，那么KD-Tree可能会更容易。另一方面，R-Tree适用于连续添加数据，因为它是自平衡的，而KD-Tree在添加新数据后如果没有完全重新计算可能会变得效率低下。请参见此SO问题。 - akraf

3

以下是一个小测试平台，用于查看scipy.spatial.cKDTree在您的数据上的速度，并对附近点之间的距离散布情况有一个大致的了解。

运行各种K簇的好方法是建立最近对的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

- denis

3

人们普遍认为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。

- user1149913

2

我有一个Perl模块可以完成您想要的功能Algorithm::ClusterPoints。首先，它使用您在帖子中描述的算法将多维点分为各个小区域，然后使用暴力方法查找相邻区域内点之间的聚类。在非常恶化的情况下，复杂度从O（N）到O（N ** 2）不等。 更新 :对于 d 个维度，扇区（或小超立方体）的大小 s 被确定为其对角线长度< l >是允许在不同簇之间的两个点之间的最小距离。

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的超立方体。

考虑到“属于同一簇”的双射关系，我们还可以将需要检查的扇形部门数量减半。

具体来说，当d=5时，算法::ClusterPoints只需检查3903个扇形部门。

- salva

谢谢！听起来你正在将空间划分为网格，然后使用比我的贪婪算法更智能的方法在局部找到聚类。可惜我只是个平庸的程序员，不会Perl，所以我只能用Python。另外，如果能够运行我的算法来处理完整的100万个点集，并且稍后能够快速查看如果我只使用各种子集（比如50万）最佳聚类将是什么，那就更好了。前面回答中讨论的哈希风格方法可能可以实现这一点，因为我只需要重新进行后处理。 - John Hawksley

每个扇区（小超立方体）在5D中查看242个邻居，是通过3^5-1计算得出的。 - denis

哇，使用dim真快啊。实际的运行时间会很有趣。 - denis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Steve Tjoa · Accepted Answer

14

考虑使用近似最近邻（ANN）算法或局部敏感哈希（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手册。ANN在精神上类似；David Mount在这里提供了相关信息，或者尝试FLANN（具有Matlab和Python绑定）。

- Steve Tjoa

嗯，这非常有帮助。所以，假设我有一个近似最近邻算法（我实际上认为scipy kdtree具有此功能，尽管我不知道它是否快速），您是否建议使用以下算法：

对于每个点，近似计算半径小于r的所有最近邻居。
将点按最少接近邻居到最多接近邻居排序。
制作一个列表，其中包含每个点的整数簇编号。
通过排序的邻居集列表进行迭代，将集合中的所有点分配给新的簇。（一种反向贪心算法）

- John Hawksley

好的，我看到你的版本了，使用哈希函数。如果我能找到 LSH 的 Python 实现，我一定也会尝试这种方法。 - John Hawksley

1

更新：据我估计，那个软件包似乎并不真正有效。而且我认为它没有实现欧几里得哈希。你肯定想要史蒂夫提供的原始链接：http://www.mit.edu/~andoni/LSH/。这里链接到Matlab代码：http://www.vision.caltech.edu/malaa/software/research/image-search/。 - John Hawksley

1

Denis：由于与Python兼容，我首先尝试了FLANN。如果我没记错的话，它的接口很容易使用。一旦我更好地理解了概念，我就自己编写了一个，这并不太难。在为解决ANN提供的众多数据结构中，FLANN会选择最适合输入数据的那个。我知道我有哪些输入，所以我为自己编写了一个。但是为了灵活性和易用性，FLANN也很不错。 - Steve Tjoa

1

对不起，但在我看来LSH并不是正确的解决方案。 LSH是为高维空间设计的（您不需要参考任何论文，每篇讨论LSH的论文都会说明这一点）。否则，已经证明kd树要好得多。实际上，LSH的复杂度是伪多项式，而kd树是O（logn）。在这里，我们使用5维点，kd-tree应该更好。 - justHelloWorld

显示剩余2条评论