particionales mineria metodos means ejemplos datos cure clustering analisis algoritmos algoritmo agrupamiento algorithm machine-learning cluster-analysis data-mining k-means

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



clustering ejemplos (6)

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.

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

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).

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

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.

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.