26

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

但！我需要运行时间远低于 n^2。n log n 左右应该没问题。我进行此聚类的原因是避免计算所有 n 点的距离矩阵（这需要 n^2 时间或许多小时），而我只想计算聚类之间的距离。

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

  1. 在每个维度上将空间切成 20 块。（所以总共有 20^5 件）。我将根据它们的质心将集群存储在这些网格框中。

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

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

是否有任何标准方法可以比 n^2 时间更快地进行聚类？概率算法没问题。

4

6 回答 6

14

考虑近似最近邻(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 绑定）。

于 2010-12-10T03:55:30.083 回答
6

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

有时，所有数据都集中到一侧（集群）的树中可能会发生错误的拆分。SVN 中的主干处理此问题的方式与当前版本不同。如果拆分错误，它会随机拆分数据。如果有错误的分裂，前面的方法可能会迫使树变得太深。

于 2011-01-12T06:04:17.247 回答
5

将数据放入诸如R*-tree (Wikipedia)之类的索引中，然后您可以在.O(n log n)

基于密度的聚类（维基百科）似乎正是您想要的（“相距不远”）

于 2011-11-25T22:25:29.800 回答
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

于 2012-07-14T13:49:49.177 回答
3

下面是一个小测试台，用于查看 scipy.spatial.cKDTree 在您的数据上的速度，并大致了解附近点之间的距离如何分散。

为各种 K 运行 K-cluster 的一个好方法是构建最近对的 MST，并删除最长的 K-1；见 韦恩，贪心算法。

可视化集群会很有趣——使用 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
于 2010-12-14T15:01:30.047 回答
2

我有一个 Perl 模块，它完全符合您的要求Algorithm::ClusterPoints。

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

在非常退化的情况下，复杂度从 O(N) 到 O(N**2) 不等。

更新：

@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=5andc=1我们得到l=2.236, s=0.447, r=3.236andn=pow(9, 5)=59049

实际上，我们必须检查较少的相邻扇区，因为这里我们正在考虑那些接触大小超立方体的扇区，(2r+1)/s我们只需要检查那些接触外接超球面的扇区。

考虑到“在同一个簇上”关系的双射性质，我们还可以将必须​​检查的扇区数减半。

具体来说，Algorithm::ClusterPoints 用于d=5检查 3903 个扇区的情况。

于 2010-12-10T12:13:16.983 回答