Escalando la Agrupación Aglomerativa para Grandes Volúmenes de Datos

Escalando Agrupación Aglomerativa para Grandes Volúmenes de Datos

Aprende cómo usar Reciprocal Agglomerative Clustering (RAC) para realizar agrupamiento jerárquico de conjuntos de datos grandes

Foto de Nastya Dulhiier en Unsplash.

Introducción

El agrupamiento aglomerativo es una de las mejores herramientas de agrupamiento en ciencia de datos, pero las implementaciones tradicionales no escalan bien con conjuntos de datos grandes.

En este artículo, te guiaré a través de algunos conceptos básicos sobre el agrupamiento aglomerativo, una introducción al agrupamiento aglomerativo recíproco (RAC) basado en una investigación de Google en 2021, una comparación de rendimiento entre RAC++ y AgglomerativeClustering de scikit-learn, y finalmente una breve explicación de la teoría detrás de RAC.

Antecedentes sobre el Agrupamiento Aglomerativo

En ciencia de datos, es frecuentemente útil agrupar datos no etiquetados. Con aplicaciones que van desde la agrupación de resultados de motores de búsqueda, clasificación de genotipos, hasta la detección de anomalías bancarias, el agrupamiento es una pieza esencial en el conjunto de herramientas de un científico de datos.

El agrupamiento aglomerativo es uno de los enfoques de agrupamiento más populares en ciencia de datos y por una buena razón, ya que:

✅ Es fácil de usar con poca o ninguna afinación de parámetros✅ Crea taxonomías significativas✅ Funciona bien con datos de alta dimensionalidad✅ No necesita conocer el número de grupos de antemano✅ Crea los mismos grupos cada vez

En comparación, los métodos de particionamiento como K-Means requieren que el científico de datos adivine el número de grupos, el método basado en densidad muy popular DBSCAN requiere algunos parámetros alrededor del radio de cálculo de densidad (epsilon) y el tamaño mínimo del vecindario, y los modelos de mezcla gaussiana hacen suposiciones fuertes sobre la distribución de los datos de los grupos subyacentes.

Con el agrupamiento aglomerativo, todo lo que necesitas especificar es una métrica de distancia.

A un nivel alto, el agrupamiento aglomerativo sigue el siguiente algoritmo:

  1. Identificar las distancias entre grupos para todos los pares de grupos (cada grupo comienza como un solo punto)
  2. Fusionar los dos grupos que están más cercanos entre sí
  3. Repetir

El resultado: un hermoso dendrograma que luego se puede particionar en función de la experiencia en el dominio.

En campos como la biología y el procesamiento de lenguaje natural, los grupos (de células, genes o palabras) siguen naturalmente una relación jerárquica. Por lo tanto, el agrupamiento aglomerativo permite una selección más natural y basada en datos del punto de corte de agrupamiento final.

A continuación se muestra un ejemplo de agrupamiento aglomerativo del famoso conjunto de datos Iris.

Agrupamiento del famoso conjunto de datos Iris por longitud del sépalo y ancho del sépalo. Gráficos producidos por el coautor Porter Hunley.

Entonces, ¿por qué no utilizar el agrupamiento aglomerativo para cada problema de clasificación no supervisada?

❌ El agrupamiento aglomerativo tiene un tiempo de ejecución terrible a medida que los conjuntos de datos aumentan de tamaño.

Desafortunadamente, el agrupamiento aglomerativo tradicional no escala bien. El tiempo de ejecución es O(n³) o O(n²log(n)) si se implementa con una min-heap. Aún peor, el agrupamiento aglomerativo se ejecuta secuencialmente en un solo núcleo y no se puede escalar con cómputo.

En el campo del procesamiento de lenguaje natural, el agrupamiento aglomerativo es un rendimiento destacado… para conjuntos de datos pequeños.

Agrupamiento Aglomerativo Recíproco (RAC)

El Agrupamiento Aglomerativo Recíproco (RAC) es un método propuesto por Google para escalar los beneficios del agrupamiento aglomerativo tradicional a conjuntos de datos más grandes.

RAC disminuye la complejidad del tiempo de ejecución y también paraleliza las operaciones para utilizar una arquitectura multicore. A pesar de estas optimizaciones, RAC produce los mismos resultados exactos que el agrupamiento aglomerativo tradicional cuando los datos están completamente conectados (ver abajo).

Nota: Los datos totalmente conectados significan que se puede calcular una métrica de distancia entre cualquier par de puntos. Los conjuntos de datos no totalmente conectados tienen restricciones de conectividad (generalmente proporcionadas en forma de una matriz de enlace) en las que algunos puntos se consideran desconectados.

¡RAC produce los mismos resultados exactos que el agrupamiento aglomerativo tradicional cuando los datos están totalmente conectados! (Arriba) y a menudo continúa haciéndolo con restricciones de conectividad (Abajo). Gráficos producidos por el coautor Porter Hunley.

Incluso con restricciones de conectividad (datos que no están totalmente conectados), RAC y el agrupamiento aglomerativo siguen siendo típicamente idénticos, como se ve en el segundo ejemplo de conjunto de datos Swiss Roll mencionado anteriormente.

Sin embargo, pueden surgir grandes discrepancias cuando hay muy pocos grupos posibles. El conjunto de datos Noisy Moons es un buen ejemplo de esto:

Resultados inconsistentes entre RAC y sklearn. Gráficos producidos por el coautor Porter Hunley.

RAC++ se escala a conjuntos de datos más grandes que scikit-learn

Podemos comparar RAC++ (una implementación de agrupamiento aglomerativo recíproco) con su contraparte, AgglomerativeClustering, en scikit-learn.

Generemos algunos datos de ejemplo con 25 dimensiones y probemos cuánto tiempo tarda el agrupamiento aglomerativo usando racplusplus.rac vs. sklearn.cluster.AgglomerativeClustering para conjuntos de datos que van desde 1,000 hasta 64,000 puntos.

Nota: Estoy utilizando una matriz de conectividad para limitar el consumo de memoria.

import numpy as npimport racplusplusfrom sklearn.cluster import AgglomerativeClusteringimport timepoints = [1000, 2000, 4000, 6000, 10000, 14000, 18000, 22000, 26000, 32000, 64000]for point_no in points:  X = np.random.random((point_no, 25))  distance_threshold = .17  knn = kneighbors_graph(X, 30, include_self=False)  # La matriz debe ser simétrica - se hace internamente en scikit-learn  symmetric = knn + knn.T  start = time.time()  model = AgglomerativeClustering(    linkage="average",    connectivity=knn,    n_clusters=None,    distance_threshold=distance_threshold,    metric='cosine'    )sklearn_times.append(time.time() - start)start = time.time()rac_labels = racplusplus.rac(  X, distance_threshold, symmetric,  batch_size=1000, no_cores=8, metric="cosine"  )rac_times.append(time.time() - start)

Aquí hay un gráfico de los resultados de tiempo de ejecución para cada tamaño de conjunto de datos:

El tiempo de ejecución se dispara para conjuntos de datos grandes cuando se utiliza sklearn en comparación con racplusplus. Gráfico producido por el coautor Porter Hunley.

Como podemos ver, hay diferencias drásticas en el tiempo de ejecución entre RAC++ y el agrupamiento aglomerativo tradicional.

Con poco más de 30,000 puntos, ¡RAC++ es aproximadamente 100 veces más rápido! Aún más importante, el agrupamiento aglomerativo de scikit-learn alcanza un límite de tiempo en ~35 mil puntos, mientras que RAC++ podría escalar a cientos de miles de puntos antes de alcanzar un límite de tiempo razonable.

RAC++ puede escalar a altas dimensiones

También podemos comparar qué tan bien escala RAC++ en datos de alta dimensión en comparación con su contraparte tradicional.

Complejidad temporal escalada por dimensionalidad de datos para RAC++ y sklearn. Gráfico por coautor Porter Hunley.

Tiempo necesario para generar grupos vs dimensionalidad para 3,000 puntos

Para 3,000 puntos podemos ver que el agrupamiento aglomerativo tradicional es más rápido pero escala linealmente, mientras que RAC++ es casi constante. Trabajar con incrustaciones de 768 o 1536 dimensiones se ha vuelto la norma en el campo de NLP, por lo que escalar la dimensionalidad para cumplir con esos requisitos es importante.

RAC++ tiene un tiempo de ejecución mejor

Investigadores de Google demostraron que RAC tiene un tiempo de ejecución de O(nk) donde k es la restricción de conectividad y n es el número de puntos, es decir, un tiempo de ejecución lineal. Sin embargo, esto excluye el cálculo inicial de la matriz de distancias que tiene un tiempo de ejecución cuadrático, O(n²).

Nuestros resultados, ejecutando una restricción constante de conectividad de 30 vecinos, confirman un tiempo de ejecución cuadrático O(n²):

+ — — — — — — -+ — — — — — +| Puntos de datos | Segundos |+ - - - - - - -+ - - - - - +| 2000 | 0.051 || 4000 | 0.125 || 6000 | 0.245 || 10000 | 0.560 || 14000 | 1.013 || 18000 | 1.842 || 22000 | 2.800 || 26000 | 3.687 || 32000 | 5.590 || 64000 | 22.499 |+ - - - - - - -+ - - - - - +

Duplicar los puntos de datos supone un aumento de 4 veces en el tiempo.

Un tiempo de ejecución cuadrático limita el rendimiento de RAC++ a medida que los conjuntos de datos se vuelven realmente masivos, sin embargo, este tiempo de ejecución ya supone una gran mejora sobre el tiempo de ejecución tradicional O(n³) o el tiempo de ejecución optimizado con min-heap O(n²log(n)).

Nota: los desarrolladores de RAC++ están trabajando en pasar la matriz de distancias como parámetro, lo que daría a RAC++ un tiempo de ejecución lineal.

Cómo funciona RAC

¿Por qué RAC++ es tan rápido? Podemos reducir el algoritmo subyacente a unos pocos pasos:

  1. Asociar grupos con vecinos más cercanos recíprocos
  2. Fusionar los pares de grupos
  3. Actualizar los vecinos

Observa que la única diferencia entre esto y el algoritmo de agrupamiento aglomerativo tradicional es que nos aseguramos de asociar vecinos más cercanos recíprocos. De ahí viene el nombre Reciprocal Agglomerative Clustering (RAC). Como verás, esta asociación recíproca nos permite paralelizar el paso más computacionalmente costoso del agrupamiento aglomerativo.

Asociar grupos con vecinos más cercanos recíprocos

Primero recorremos para encontrar grupos con vecinos más cercanos recíprocos, lo que significa que sus vecinos más cercanos son el uno para el otro (recuerda, la distancia puede ser direccional).

Identificar vecinos más cercanos recíprocos. Figura por coautor Porter Hunley.

Fusionar pares

RAC es paralelizable porque no importa en qué orden se fusionen los vecinos más cercanos recíprocos, siempre y cuando el método de enlace sea reducible.

Un método de enlace es la función que determina la distancia entre dos grupos, basada en las distancias por pares entre los puntos contenidos en cada grupo. Un método de enlace reducible garantiza que el nuevo grupo fusionado no esté más cerca de ningún otro grupo después de la fusión.

ab_c no estará más cerca que a_c o b_c si se utiliza un método de enlace reducible. Figura por coautor Porter Hunley.

Afortunadamente, los cuatro métodos de enlace más populares son reducibles:

  • Enlace simple – distancia mínima
  • Enlace promedio – promedio de las distancias
  • Enlace completo – distancia máxima
  • Enlace de Ward – minimizando la varianza
Representación visual de los 4 métodos de enlace reducibles. Figuras dibujadas por mí, inspiradas en http://www.saedsayad.com/clustering_hierarchical.htm.

Dado que sabemos que nuestros pares recíprocos identificados son el vecino más cercano entre sí, y sabemos que las fusiones de enlaces reducibles nunca acercarán a un nuevo clúster fusionado a otro clúster, podemos fusionar de manera segura todos los pares recíprocos de vecinos más cercanos juntos de una vez. Cada par de vecinos más cercanos se puede colocar en un hilo disponible para fusionarse según el método de enlace.

¡El hecho de que podamos fusionar vecinos más cercanos recíprocos al mismo tiempo es fantástico, porque fusionar clústeres es el paso más costoso computacionalmente!

Visualización de clústeres listos para fusionar. Figura del coautor Porter Hunley.

Actualizar vecinos más cercanos

Con el enlace reducible, el orden en que se actualizan los vecinos más cercanos después de la fusión tampoco importa. Por lo tanto, con un diseño inteligente, también podemos actualizar los vecinos relevantes en paralelo.

Identificación de nuevos vecinos más cercanos después de la fusión. Imagen del coautor Porter Hunley.

Conclusión

Con algunos conjuntos de datos de prueba, hemos demostrado que RAC++ produce los mismos resultados exactos que el Agrupamiento Aglomerativo tradicional (es decir, sklearn) para conjuntos de datos totalmente conectados en un tiempo de ejecución mucho mejor. Con una comprensión de las métricas de enlace reducible y una comprensión básica de la programación paralela, podemos entender la lógica que hace que RAC++ sea mucho más rápido.

Para una comprensión más completa (y prueba) del algoritmo que RAC++ ha adoptado en el código abierto, eche un vistazo a la investigación original de Google en la que se basó.

El futuro

Porter Hunley comenzó a construir RAC++ para crear taxonomías para puntos finales de términos clínicos producidos a través de incrustaciones BERT ajustadas. Cada una de estas incrustaciones médicas tenía 768 dimensiones y, de los muchos algoritmos de agrupamiento que probó, solo el agrupamiento aglomerativo dio buenos resultados.

Todos los demás métodos de agrupamiento a gran escala requirieron reducir la dimensionalidad para dar resultados coherentes. Desafortunadamente, no hay una forma infalible de reducir la dimensionalidad, siempre perderá información.

Después de descubrir la investigación de Google sobre RAC, Porter decidió construir una implementación personalizada de agrupamiento de código abierto para respaldar su investigación de agrupamiento de términos clínicos. Porter lideró el desarrollo y yo co-desarrollé partes de RAC, en particular envolví la implementación en C++ en Python, optimicé el tiempo de ejecución y empaqueté el software para su distribución.

RAC++ permite toneladas de aplicaciones de agrupamiento que son demasiado lentas utilizando el agrupamiento aglomerativo tradicional, y eventualmente será escalable a millones de puntos de datos.

Aunque RAC++ ya se puede utilizar para agrupar conjuntos de datos grandes, hay mejoras por hacer… ¡RAC++ aún está en desarrollo, por favor contribuye!

Autores colaboradores:

  • Porter Hunley, Ingeniero de Software Senior en Daceflow.ai: github
  • Daniel Frees, Estudiante de MS en Estadísticas y Ciencia de Datos en Stanford, Científico de Datos en IBM: github

GitHub – porterehunley/RACplusplus: Una implementación de alto rendimiento de Reciprocal Agglomerative…

We will continue to update Zepes; if you have any questions or suggestions, please contact us!

Share:

Was this article helpful?

93 out of 132 found this helpful

Discover more

Inteligencia Artificial

Construyendo sistemas complejos utilizando ChatGPT

Introducción La inteligencia artificial ha evolucionado más allá de las expectativas con LLMs como ChatGPT. GPT-4, un...

Inteligencia Artificial

Jina AI presenta 'jina-embeddings-v2' los primeros modelos de incrustación de texto de código abierto 8k del mundo.

Jina AI revela su último avance en su modelo de incrustación de texto de segunda generación: jina-embeddings-v2. Este...

Inteligencia Artificial

La mano biónica se integra con los nervios, huesos y músculos de la mujer

Un equipo internacional de investigación informó que una mano robótica adjunta a una mujer sueca en 2017 se ha integr...

Inteligencia Artificial

La ciudad más avanzada tecnológicamente de Estados Unidos tiene dudas sobre los coches autónomos

Los funcionarios y residentes de San Francisco no están impresionados por los autos autónomos, subrayando los desafío...

Ciencia de Datos

Conoce AnythingLLM Una Aplicación Full-Stack Que Transforma Tu Contenido en Datos Enriquecidos para Mejorar las Interacciones con Modelos de Lenguaje Amplio (LLMs)

Desde el lanzamiento del revolucionario ChatGPT de OpenAI, el número de proyectos relacionados con la IA, especialmen...