Algoritmos de Clustering: From Start To State Of The Art

No es un mal momento para ser un Científico de Datos. La gente seria puede encontrar interés en ti si giras la conversación hacia el «Big Data», y el resto de la gente de la fiesta estará intrigada cuando menciones la «Inteligencia Artificial» y el «Machine Learning». Incluso Google piensa que no estás mal, y que estás mejorando aún más. Hay un montón de algoritmos «inteligentes» que ayudan a los científicos de datos a hacer sus magias. Todo puede parecer complicado, pero si entendemos y organizamos un poco los algoritmos, ni siquiera es tan difícil encontrar y aplicar el que necesitamos.

Los cursos sobre minería de datos o aprendizaje automático suelen empezar por el clustering, porque es tan sencillo como útil. Es una parte importante de un área algo más amplia de aprendizaje no supervisado, donde los datos que queremos describir no están etiquetados. En la mayoría de los casos, esto ocurre cuando el usuario no nos da mucha información sobre cuál es el resultado esperado. El algoritmo sólo tiene los datos y debe hacer lo mejor que pueda. En nuestro caso, debe realizar un clustering, es decir, separar los datos en grupos (clusters) que contengan puntos de datos similares, mientras que la disimilitud entre los grupos sea lo más alta posible. Los puntos de datos pueden representar cualquier cosa, como nuestros clientes. El clustering puede ser útil si, por ejemplo, queremos agrupar usuarios similares y luego ejecutar diferentes campañas de marketing en cada cluster.

K-Means Clustering

Después de la necesaria introducción, los cursos de Minería de Datos siempre continúan con K-Means; un algoritmo de clustering eficaz y ampliamente utilizado. Antes de ejecutarlo, tenemos que definir una función de distancia entre los puntos de datos (por ejemplo, la distancia euclidiana si queremos agrupar puntos en el espacio), y tenemos que establecer el número de clusters que queremos (k).

El algoritmo comienza seleccionando k puntos como centros de partida (‘centros’ de los clusters). Podemos seleccionar cualquier k puntos al azar, o podemos utilizar algún otro enfoque, pero elegir puntos al azar es un buen comienzo. A continuación, repetimos iterativamente dos pasos:

1. Paso de asignación: cada uno de los m puntos de nuestro conjunto de datos se asigna a un clúster que está representado por el más cercano de los k centroides. Para cada punto, calculamos las distancias a cada centroide, y simplemente elegimos el menos distante.

2. Paso de actualización: para cada cluster, se calcula un nuevo centroide como la media de todos los puntos del cluster. Desde el paso anterior, tenemos un conjunto de puntos que se asignan a un cluster. Ahora, para cada uno de esos conjuntos, calculamos una media que declaramos nuevo centroide del cluster.

Después de cada iteración, los centroides se mueven lentamente, y la distancia total de cada punto a su centroide asignado es cada vez menor. Los dos pasos se alternan hasta la convergencia, es decir, hasta que no haya más cambios en la asignación de clusters. Después de un número de iteraciones, se asignará el mismo conjunto de puntos a cada centroide, lo que conducirá de nuevo a los mismos centroides. Se garantiza que K-Means converge a un óptimo local. Sin embargo, no necesariamente tiene que ser la mejor solución global (óptimo global).

El resultado final de la agrupación puede depender de la selección de los centroides iniciales, por lo que se ha pensado mucho en este problema. Una solución sencilla es ejecutar K-Means un par de veces con asignaciones iniciales aleatorias. Entonces podemos seleccionar el mejor resultado tomando el que tenga la mínima suma de distancias de cada punto a su cluster – el valor de error que estamos tratando de minimizar en primer lugar.

Otros enfoques para la selección de puntos iniciales pueden basarse en la selección de puntos distantes. Esto puede conducir a mejores resultados, pero podemos tener un problema con los valores atípicos, esos raros puntos aislados que están simplemente «fuera» y que pueden ser sólo algunos errores. Como están lejos de cualquier cluster significativo, cada uno de esos puntos puede acabar siendo su propio «cluster». Un buen equilibrio es la variante K-Means++ , cuya inicialización seguirá eligiendo puntos al azar, pero con una probabilidad proporcional a la distancia al cuadrado de los centroides previamente asignados. Los puntos más alejados tendrán una mayor probabilidad de ser seleccionados como centroides iniciales. En consecuencia, si hay un grupo de puntos, la probabilidad de que un punto del grupo sea seleccionado también aumenta a medida que sus probabilidades se suman, resolviendo el problema de los valores atípicos que mencionamos.

K-Means++ es también la inicialización por defecto para la implementación de K-Means de Scikit-learn de Python. Si estás usando Python, esta puede ser tu biblioteca de elección. Para Java, la biblioteca Weka puede ser un buen comienzo:

Java (Weka)

// Load some dataInstances data = DataSource.read("data.arff");// Create the modelSimpleKMeans kMeans = new SimpleKMeans();// We want three clusterskMeans.setNumClusters(3);// Run K-MeanskMeans.buildClusterer(data);// Print the centroidsInstances centroids = kMeans.getClusterCentroids();for (Instance centroid: centroids) { System.out.println(centroid);}// Print cluster membership for each instancefor (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point));}

Python (Scikit-learn)

> >> from sklearn import cluster, datasets> >> iris = datasets.loadiris()> >> Xiris = iris.data> >> yiris = iris.target> >> kmeans = cluster.KMeans(nclusters=3)> >> kmeans.fit(Xiris)KMeans(copy_x=True, init='k-means++', ...> >> print(kmeans.labels)> >> print(yiris)

En el ejemplo de Python anterior, utilizamos un conjunto de datos de ejemplo estándar ‘Iris’, que contiene dimensiones de pétalos y sépalos de flores para tres especies diferentes de iris. Los agrupamos en tres clusters, y comparamos los clusters obtenidos con las especies reales (objetivo), para ver que coinciden perfectamente.

En este caso, sabíamos que había tres clusters diferentes (especies), y K-Means reconoció correctamente cuáles van juntos. Pero, ¿cómo elegimos un buen número de clusters k en general? Este tipo de preguntas son bastante comunes en el aprendizaje automático. Si pedimos más clusters, serán más pequeños, y por tanto el error total (total de distancias de los puntos a sus clusters asignados) será menor. Entonces, ¿es una buena idea establecer una k más grande? Podemos acabar teniendo k = m, es decir, que cada punto sea su propio centroide, y que cada cluster tenga sólo un punto. Sí, el error total es 0, pero no conseguimos una descripción más sencilla de nuestros datos, ni es lo suficientemente general como para cubrir algunos puntos nuevos que puedan aparecer. Esto se llama sobreajuste, y no queremos eso.

Una forma de tratar este problema es incluir alguna penalización por un mayor número de clusters. Así, ahora estamos tratando de minimizar no sólo el error, sino el error + la penalización. El error convergerá hacia cero a medida que aumentemos el número de conglomerados, pero la penalización crecerá. En algunos puntos, la ganancia de añadir otro cluster será menor que la penalización introducida, y tendremos el resultado óptimo. Una solución que utiliza el Criterio de Información Bayesiano (BIC) para este propósito se llama X-Means .

Otra cosa que tenemos que definir correctamente es la función de distancia. A veces esa es una tarea sencilla, una tarea lógica dada la naturaleza de los datos. Para puntos en el espacio, la distancia euclidiana es una solución obvia, pero puede ser complicado para características de diferentes «unidades», para variables discretas, etc. Esto puede requerir un gran conocimiento del dominio. O bien, podemos pedir ayuda al aprendizaje automático. Podemos intentar aprender la función de distancia. Si tenemos un conjunto de entrenamiento de puntos que sabemos cómo deberían agruparse (es decir, puntos etiquetados con sus clusters), podemos utilizar técnicas de aprendizaje supervisado para encontrar una buena función, y luego aplicarla a nuestro conjunto objetivo que aún no está agrupado.

El método utilizado en K-Means, con sus dos pasos alternados se asemeja a un método de maximización de expectativas (EM). En realidad, puede considerarse una versión muy simple de EM. Sin embargo, no debe confundirse con el algoritmo de clustering EM, más elaborado, aunque comparta algunos de los mismos principios.

Clustering EM

Así, con el clustering K-Means cada punto se asigna a un solo cluster, y un cluster se describe sólo por su centroide. Esto no es demasiado flexible, ya que podemos tener problemas con los clusters que se solapan, o con los que no tienen forma circular. Con el EM Clustering, ahora podemos ir un paso más allá y describir cada cluster por su centroide (media), covarianza (para que podamos tener clusters elípticos), y peso (el tamaño del cluster). La probabilidad de que un punto pertenezca a un conglomerado viene dada ahora por una distribución de probabilidad gaussiana multivariante (multivariante: depende de múltiples variables). Esto también significa que podemos calcular la probabilidad de que un punto esté bajo una «campana» gaussiana, es decir, la probabilidad de que un punto pertenezca a un clúster.

Ahora comenzamos el procedimiento EM calculando, para cada punto, las probabilidades de que pertenezca a cada uno de los clústeres actuales (que, de nuevo, pueden ser creados aleatoriamente al principio). Este es el paso E. Si un clúster es un candidato realmente bueno para un punto, tendrá una probabilidad cercana a uno. Sin embargo, dos o más clusters pueden ser candidatos aceptables, por lo que el punto tiene una distribución de probabilidades sobre los clusters. Esta propiedad del algoritmo, de que los puntos no pertenezcan de forma restringida a un clúster, se denomina «agrupación suave».

El paso M recalcula ahora los parámetros de cada clúster, utilizando las asignaciones de puntos al conjunto anterior de clústeres. Para calcular la nueva media, covarianza y peso de un cluster, cada dato de punto se pondera por su probabilidad de pertenecer al cluster, tal y como se calculó en el paso anterior.

Alternando estos dos pasos se incrementará la log-verosimilitud total hasta que converja. De nuevo, el máximo puede ser local, por lo que podemos ejecutar el algoritmo varias veces para obtener mejores clusters.

Si ahora queremos determinar un único cluster para cada punto, podemos simplemente elegir el más probable. Teniendo un modelo de probabilidad, también podemos usarlo para generar datos similares, es decir, para muestrear más puntos que sean similares a los datos que observamos.

Propagación por afinidad

La Propagación por afinidad (AP) fue publicada por Frey y Dueck en 2007, y cada vez es más popular debido a su simplicidad, aplicabilidad general y rendimiento. Está cambiando su estatus de estado del arte a estándar de facto.

Los principales inconvenientes de K-Means y algoritmos similares son tener que seleccionar el número de clusters, y elegir el conjunto inicial de puntos. La propagación de afinidad, en cambio, toma como entrada medidas de similitud entre pares de puntos de datos, y considera simultáneamente todos los puntos de datos como ejemplares potenciales. Se intercambian mensajes de valor real entre los puntos de datos hasta que surge gradualmente un conjunto de ejemplares de alta calidad y los correspondientes clusters.

Como entrada, el algoritmo requiere que proporcionemos dos conjuntos de datos:

1. Similitudes entre los puntos de datos, que representan lo adecuado que es un punto para ser el ejemplar de otro. Si no hay similitud entre dos puntos, ya que no pueden pertenecer al mismo clúster, esta similitud puede omitirse o fijarse en -Infinito dependiendo de la implementación.

2. Preferencias, que representan la idoneidad de cada punto de datos para ser un ejemplar. Podemos tener alguna información a priori sobre qué puntos podrían ser favorecidos para este papel, y así podemos representarlo a través de las preferencias.

Tanto las similitudes como las preferencias se suelen representar a través de una única matriz, donde los valores de la diagonal principal representan las preferencias. La representación matricial es buena para conjuntos de datos densos. Cuando las conexiones entre los puntos son escasas, es más práctico no almacenar toda la matriz n x n en la memoria, sino mantener una lista de similitudes con los puntos conectados. Detrás de la escena, ‘intercambiar mensajes entre puntos’ es lo mismo que manipular matrices, y es sólo una cuestión de perspectiva e implementación.

El algoritmo entonces se ejecuta a través de un número de iteraciones, hasta que converge. Cada iteración tiene dos pasos de paso de mensajes:

1. Calcular las responsabilidades: La responsabilidad r(i, k) refleja la evidencia acumulada sobre lo adecuado que es el punto k para servir como ejemplar para el punto i, teniendo en cuenta otros ejemplares potenciales para el punto i. La responsabilidad se envía desde el punto de datos i al punto ejemplar candidato k.

2. Calcular disponibilidades: La disponibilidad a(i, k) refleja la evidencia acumulada de lo apropiado que sería para el punto i elegir el punto k como su ejemplar, teniendo en cuenta el apoyo de otros puntos de que el punto k debería ser un ejemplar. La disponibilidad se envía desde el punto ejemplar candidato k al punto i.

Para calcular las responsabilidades, el algoritmo utiliza las similitudes originales y las disponibilidades calculadas en la iteración anterior (inicialmente, todas las disponibilidades se fijan en cero). Las responsabilidades se fijan a la similitud de entrada entre el punto i y el punto k como su ejemplar, menos la mayor de las sumas de similitud y disponibilidad entre el punto i y otros ejemplares candidatos. La lógica detrás del cálculo de lo adecuado que es un punto para un ejemplar es que se favorece más si la preferencia inicial a priori era más alta, pero la responsabilidad se reduce cuando hay un punto similar que se considera a sí mismo un buen candidato, por lo que hay una «competencia» entre los dos hasta que uno se decide en alguna iteración.

El cálculo de las disponibilidades, entonces, utiliza las responsabilidades calculadas como evidencia de si cada candidato sería un buen ejemplar. La disponibilidad a(i, k) se fija en la autorresponsabilidad r(k, k) más la suma de las responsabilidades positivas que el ejemplar candidato k recibe de otros puntos.

Por último, podemos tener diferentes criterios de parada para terminar el procedimiento, como cuando los cambios en los valores caen por debajo de algún umbral, o se alcanza el número máximo de iteraciones. En cualquier punto a través del procedimiento de Propagación de Afinidad, la suma de las matrices de Responsabilidad (r) y Disponibilidad (a) nos da la información de clustering que necesitamos: para el punto i, el k con el máximo de r(i, k) + a(i, k) representa el ejemplar del punto i. O, si sólo necesitamos el conjunto de ejemplares, podemos explorar la diagonal principal. Si r(i, i) + a(i, i) > 0, el punto i es un ejemplar.

Hemos visto que con K-Means y algoritmos similares, decidir el número de clusters puede ser complicado. Con AP, no tenemos que especificarlo explícitamente, pero aun así puede ser necesario ajustarlo si obtenemos más o menos clusters de los que nos parecen óptimos. Por suerte, sólo ajustando las preferencias podemos bajar o subir el número de clusters. Si ajustamos las preferencias a un valor más alto, obtendremos más conglomerados, ya que cada punto está «más seguro» de su idoneidad para ser un ejemplar y, por tanto, es más difícil «vencerlo» e incluirlo bajo la «dominación» de algún otro punto. A la inversa, establecer preferencias más bajas dará lugar a tener menos clusters; como si dijeran «no, no, por favor, tú eres un mejor ejemplar, me uniré a tu cluster». Como regla general, podemos establecer todas las preferencias a la similitud media para un número de clusters medio o grande, o a la similitud más baja para un número moderado de clusters. Sin embargo, pueden ser necesarias un par de ejecuciones ajustando las preferencias para obtener el resultado que se adapte exactamente a nuestras necesidades.

También vale la pena mencionar la Propagación de Afinidad Jerárquica, como una variante del algoritmo que se ocupa de la complejidad cuadrática dividiendo el conjunto de datos en un par de subconjuntos, agrupándolos por separado, y luego realizando el segundo nivel de agrupación.

En fin…

Hay toda una gama de algoritmos de clustering, cada uno con sus pros y sus contras en cuanto al tipo de datos con los que trabajan, la complejidad temporal, los puntos débiles, etc. Por mencionar más algoritmos, por ejemplo está el Clustering Aglomerativo Jerárquico (o Linkage Clustering), bueno para cuando no tenemos necesariamente clusters circulares (o hiperesféricos), y no conocemos el número de clusters de antemano. Comienza con cada punto siendo un cluster separado, y trabaja uniendo dos clusters más cercanos en cada paso hasta que todo está en un gran cluster.

Con el Clustering Aglomerativo Jerárquico, podemos decidir fácilmente el número de clusters después cortando el dendrograma (diagrama de árbol) horizontalmente donde encontremos adecuado. También es repetible (siempre da la misma respuesta para el mismo conjunto de datos), pero también es de mayor complejidad (cuadrática).

Entonces, DBSCAN (Density-Based Spatial Clustering of Applications with Noise) es también un algoritmo digno de mención. Agrupa los puntos que están muy juntos, expandiendo los clusters en cualquier dirección en la que haya puntos cercanos, tratando así con diferentes formas de clusters.

Estos algoritmos merecen un artículo propio, y podemos explorarlos en un post separado más adelante.

Se necesita experiencia con algo de ensayo y error para saber cuándo usar un algoritmo u otro. Por suerte, tenemos un abanico de implementaciones en diferentes lenguajes de programación, por lo que probarlos sólo requiere un poco de ganas de jugar.