algorithm - mineria - Algoritmo de agrupamiento rápido(<n ^ 2)

clustering ejemplos

Question

Tengo 1 millón de puntos en 5 dimensiones que necesito agrupar en k clusters con k << 1 millón. En cada grupo, no hay dos puntos muy separados (por ejemplo, podrían estar delimitando esferas con un radio específico). Eso significa que probablemente tiene que haber muchos grupos de tamaño 1.

¡Pero! Necesito que el tiempo de ejecución sea muy inferior a n ^ 2. n log n or so debería estar bien. La razón por la que hago este agrupamiento es evitar calcular una matriz de distancia de todos los n puntos (lo que lleva n ^ 2 veces o muchas horas), en su lugar, quiero calcular las distancias entre los clústeres.

Probé el algoritmo pycluster k-means, pero rápidamente me di cuenta de que es demasiado lento. También probé el siguiente enfoque codicioso:

1. Corte el espacio en 20 piezas en cada dimensión. (entonces hay 20 ^ 5 piezas en total). Almacenaré clusters en estas gridbox, de acuerdo con sus centroides.

2. Para cada punto, recupere las cajas de malla que están dentro de r (radio máximo de la esfera límite). Si hay un clúster casi suficiente, agréguelo a ese clúster; de lo contrario, cree un nuevo clúster.

Sin embargo, esto parece darme más clusters de lo que quiero. También implementé enfoques similares a esto dos veces, y dan respuestas muy diferentes.

¿Hay algún enfoque estándar para la agrupación en un tiempo más rápido que n ^ 2? Algoritmos probabilísticos están bien.

Answer 1

A continuación hay un pequeño banco de pruebas para ver qué tan rápido scipy.spatial.cKDTree está en sus datos, y para tener una idea aproximada de cómo se dispersan las distancias entre los puntos cercanos.

Una buena forma de ejecutar el K-cluster para varios K es construir un MST de los pares más cercanos y eliminar el K-1 más largo; ver Wayne, Algoritmos Codiciosos .

Visualizar los clusters sería divertido: ¿proyecto 2d con PCA?

(Solo curiosidad, ¿es tu K 10, 100, 1000?)

Agregado el 17 de diciembre: tiempos de ejecución reales: 100000 x 5 10 segundos, 500000 x 5 60 segundos

#!/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 

Answer 2

Coloque los datos en un índice como un árbol R * (Wikipedia) , luego puede ejecutar muchos algoritmos de agrupamiento basados ​​en la densidad (como DBSCAN (Wikipedia) u OPTICS (Wikipedia) ) en O(n log n) .

La agrupación basada en la densidad (Wikipedia) parece ser exactamente lo que desea ("no demasiado lejos")

Answer 3

Considere un algoritmo de aproximación más cercano (ANN) o hash sensible a la localidad (LSH). No resuelven directamente el problema de agrupamiento, pero podrán decirle qué puntos están "cerca" uno del otro. Al modificar los parámetros, puede definir lo más cerca posible para que esté lo más cerca posible. Y es rápido.

Más precisamente, LSH puede proporcionar una función hash, h , tal que, para dos puntos y , y distancia métrica d ,

d(x,y) <= R1  =>  P(h(x) = h(y)) >= P1
d(x,y) >= R2  =>  P(h(x) = h(y)) <= P2

donde R1 < R2 y P1 > P2 . Entonces sí, es probabilístico. Puede postprocesar los datos recuperados para llegar a clusters verdaderos.

Aquí hay información sobre LSH incluido el manual de E2LSH . ANN es similar en espíritu; David Mount tiene información here , o prueba FLANN (tiene enlaces de Matlab y Python).

Answer 4

La gente tiene la impresión de que k-means es lento, pero la lentitud es realmente solo un problema para el algoritmo EM (Lloyd''s). Los métodos de gradiente estocástico para k-means son órdenes de magnitud más rápidos que EM (ver www.eecs.tufts.edu/~dsculley/papers/fastkmeans.pdf).

Una implementación está aquí: http://code.google.com/p/sofia-ml/wiki/SofiaKMeans

Answer 5

Quizás quieras probar mi proyecto de investigación llamado K-tree . Se escala bien con grandes entradas con respecto a los k-means y forma una jerarquía de clusters. La desventaja es que produce conglomerados con mayor distorsión. Tiene un tiempo medio de ejecución de casos de O (n log n) y el peor caso de O (n ** 2) que solo ocurre si tiene alguna topología extraña. Más detalles del análisis de complejidad están en mi tesis de maestría . Lo he usado con datos de texto muy altos y no tuve problemas.

A veces, pueden producirse divisiones erróneas en el árbol donde todos los datos van a un lado (clúster). El tronco en SVN trata esto de manera diferente a la versión actual. Al azar divide los datos si hay una mala división. El método anterior puede forzar al árbol a ser demasiado profundo si hay divisiones incorrectas.

Answer 6

Tengo un módulo Perl que hace exactamente lo que quiere Algorithm::ClusterPoints .

En primer lugar, utiliza el algoritmo que ha descrito en su publicación para dividir los puntos en sectores multidimensionales y luego utiliza la fuerza bruta para encontrar agrupaciones entre puntos en sectores adyacentes.

La complejidad varía de O (N) a O (N ** 2) en casos muy degradados.

actualización :

@Denis: no, es mucho peor:

Para d dimensiones, el tamaño del sector (o pequeño hipercubo) s se determina de modo que su diagonal l es la distancia mínima c permitida entre dos puntos en diferentes conglomerados.

l = c
l = sqrt(d * s * s)
s = sqrt(c * c / d) = c / sqrt(d)

Luego, debe considerar todos los sectores que tocan la hiperesfera con un diámetro r = 2c + l centrado en el sector de pivote.

Aproximadamente, tenemos que considerar ceil(r/s) filas de sectores en todas las direcciones y eso significa n = pow(2 * ceil(r/s) + 1, d) .

Por ejemplo, para d=5 y c=1 obtenemos l=2.236 , s=0.447 , r=3.236 n=pow(9, 5)=59049

En realidad, tenemos que verificar sectores menos vecinos ya que aquí estamos considerando aquellos que tocan el hipercubo de tamaño (2r+1)/s y solo necesitamos verificar aquellos que tocan la hiperesfera circunscrita.

Considerando la naturaleza biyectiva de la relación "están en el mismo grupo" también podemos tener la mitad del número de sectores que deben verificarse.

Específicamente, Algorithm :: ClusterPoints para el caso donde d=5 verifica 3903 sectores.