Agrupación de espacio eficiente

La mayoría de los algoritmos de agrupación que he visto comienzan con la creación de una distancia de cada uno entre cada punto, lo que se vuelve problemático en conjuntos de datos más grandes. ¿Hay alguno que no lo haga? ¿O lo hace en algún tipo de enfoque parcial / aproximado / escalonado?

¿Qué algoritmo / implementación de agrupamiento ocupa menos espacio de O (n ^ 2)?

¿Hay una lista de algoritmos y sus requisitos de tiempo y espacio en alguna parte?

K-Means y Mean-Shift usan los descriptores de muestra sin procesar (no es necesario calcular previamente una matriz de afinidad).

De lo contrario, para la agrupación espectral o la agrupación de iteración de potencia, puede usar una representación de matriz dispersa (por ejemplo, Filas dispersas comprimidas) de la matriz de afinidad k-vecinos más cercanos (para alguna métrica de distancia o afinidad). Si k es pequeño (digamos 5 o 10). Obtendrá una representación muy eficiente en el espacio (2 * n_muestras * k * 8 bytes para valores de coma flotante de doble precisión).

Algunos algoritmos de agrupamiento pueden usar estructuras de índice espacial. Esto permite, por ejemplo, que DBSCAN y OPTICS se ejecuten en tiempo (siempre que el índice permita consultas ).$O(n\log n)$$O(\log n)$

Obviamente, un algoritmo que se ejecuta en esta complejidad no construye una matriz de distancia .$O(n^2)$

Para algunos algoritmos, como la agrupación jerárquica con enlace único y enlace completo, existen algoritmos optimizados disponibles (SLINK, CLINK). Es solo que la mayoría de las personas usan lo que pueden obtener y lo que sea fácil de implementar. Y la agrupación jerárquica es fácil de implementar ingenuamente, usando iteraciones sobre una matriz de distancia (lo que resulta en un algoritmo ...).$n$$n^2$$O(n^3)$

No conozco una lista completa que compare algoritmos de agrupamiento. Probablemente hay más de 100 algoritmos de agrupación, después de todo. Hay al menos una docena de variantes de k-medias, por ejemplo. Además, hay complejidad en el tiempo de ejecución, así como la complejidad de la memoria; hay el caso promedio y el peor de los casos. Existen enormes diferencias de implementación (por ejemplo, enlace único mencionado anteriormente; e implementaciones de DBSCAN que no usan un índice, y por lo tanto están en , y aunque no necesitan almacenar la matriz de distancia , entonces todavía necesitan calcular todas las distancias por pares). Además, hay toneladas de parámetros. Para k significa,$O(n^2)$$n\times n$$k$es critico. Para casi cualquier algoritmo, la función de distancia hace una gran diferencia (muchas implementaciones solo permiten la distancia euclidiana ...). Y una vez que llegue a costosas funciones de distancia (más allá de cosas triviales como Euclidean), el número de cálculos de distancia puede ser rápidamente la parte principal. Entonces, necesitaría diferenciar entre el número total de operaciones y el número de cálculos de distancia necesarios. Entonces, un algoritmo que está en operaciones pero solo los cálculos de distancia pueden superar fácilmente un algoritmo que es en ambos, cuando las funciones de distancia son realmente caras (por ejemplo, la distancia la función en sí es ).$O(n^2)$$O(n)$$O(n \log n)$$O(n)$

Buena pregunta. Un método sencillo para decir 3 vecinos más cercanos es muestrear los vecinos de Nsample de cada punto de datos, manteniendo el 3. más cercano. Si bien es trivial, ejecutar esto para algunos valores de Nsample le dará una idea de la relación señal / ruido, ruido cercano / de fondo , fácilmente trazado para sus datos. Un truco adicional es verificar los vecinos de los vecinos, para ver si alguno de ellos está más cerca que los vecinos directos. Además, si los datos de entrada ya están bien barajados, muestree en bloques, de lo contrario la memoria caché se agitará.

(Agregado): vea fastcluster en R y creo en SciPy v0.11.
Para texto, vea google-all-pair-similarity-search .

Repita: "Una medida de disimilitud apropiada es mucho más importante para obtener éxito con la agrupación que la elección del algoritmo de agrupación": elegir el método de agrupación .