Algoritmos de agrupamiento: desde el inicio hasta el estado del arte

No es un mal momento para ser un científico de datos. Las personas serias pueden encontrar interés en ti si cambias la conversación hacia "Big Data", y el resto de la gente de la fiesta quedará intrigada cuando menciones "Inteligencia artificial" y "Aprendizaje automático". Incluso Google piensa que no eres malo y que estás mejorando aún más. Hay muchos algoritmos "inteligentes" que ayudan a los científicos de datos a hacer su magia. 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 generalmente comenzarán con la agrupación, porque es simple y ú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, aquí es donde el usuario no nos dio mucha información sobre cuál es el resultado esperado. El algoritmo solo tiene los datos y debe hacer lo mejor que pueda. En nuestro caso, debería realizar un agrupamiento, separando los datos en grupos (clusters) que contienen puntos de datos similares, mientras que la disimilitud entre los grupos es lo más alta posible. Los puntos de datos pueden representar cualquier cosa, como nuestros clientes. La agrupación en clústeres puede ser útil si, por ejemplo, queremos agrupar usuarios similares y luego ejecutar diferentes campañas de marketing en cada clúster.

Agrupación de K-Means

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

El algoritmo comienza seleccionando k puntos como centroides iniciales ('centros' de grupos). Podemos simplemente seleccionar cualquier k puntos aleatorios, o podemos usar algún otro enfoque, pero elegir puntos aleatorios es un buen comienzo. Luego, iterativamente repetimos dos pasos:

1. Paso de asignación: cada uno de los m puntos de nuestro conjunto de datos se asigna a un grupo 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 grupo, se calcula un nuevo centroide como la media de todos los puntos del grupo. Del paso anterior, tenemos un conjunto de puntos que se asignan a un grupo. Ahora, para cada uno de esos conjuntos, calculamos una media que declaramos un nuevo centroide del grupo.

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

El resultado final del agrupamiento puede depender de la selección de los centroides iniciales, por lo que se ha pensado mucho en este problema. Una solución simple es simplemente ejecutar K-Means un par de veces con asignaciones iniciales aleatorias. Luego, podemos seleccionar el mejor resultado tomando el que tiene la suma mínima de distancias desde cada punto a su grupo: el valor de error que estamos tratando de minimizar en primer lugar.

Otros enfoques para seleccionar puntos iniciales pueden basarse en la selección de puntos distantes. Esto puede conducir a mejores resultados, pero es posible que tengamos un problema con los valores atípicos, esos puntos raros que solo están "apagados" y que pueden ser solo algunos errores. Dado que están lejos de cualquier grupo significativo, cada uno de esos puntos puede terminar siendo su propio "grupo". Un buen equilibrio es la variante K-Means++ [Arthur y Vassilvitskii, 2007], cuya inicialización aún elegirá puntos aleatorios, pero con probabilidad proporcional a la distancia al cuadrado de los centroides previamente asignados. Los puntos que están 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 se seleccione un punto del grupo también aumenta a medida que se suman sus probabilidades, resolviendo el problema de valores atípicos que mencionamos.

K-Means++ también es la inicialización predeterminada para la implementación de Scikit-learn K-Means de Python. Si está utilizando Python, esta puede ser su biblioteca preferida. Para Java, la biblioteca Weka puede ser un buen comienzo:

Java (Weka)

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

Python (Scikit-aprender)

 > >> 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[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

En el ejemplo de Python anterior, usamos un conjunto de datos de ejemplo estándar 'Iris', que contiene las dimensiones de pétalos y sépalos de flores para tres especies diferentes de iris. Los agrupamos en tres grupos y comparamos los grupos obtenidos con la especie real (objetivo), para ver que coincidieran perfectamente.

En este caso, sabíamos que había tres grupos (especies) diferentes, y K-Means reconoció correctamente cuáles van juntos. Pero, ¿cómo elegimos un buen número de conglomerados k en general? Este tipo de preguntas son bastante comunes en Machine Learning. Si solicitamos 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 simplemente establecer una k más grande? Podemos terminar teniendo k = m, es decir, cada punto tiene su propio centroide, y cada grupo tiene un solo punto. Sí, el error total es 0, pero no obtuvimos una descripción más simple de nuestros datos, ni es lo suficientemente general como para cubrir algunos puntos nuevos que pueden aparecer. Esto se llama sobreajuste, y no queremos eso.

Una forma de lidiar con este problema es incluir alguna penalización para una mayor cantidad de clústeres. Entonces, ahora estamos tratando de minimizar no solo el error, sino también el error + penalización . El error simplemente convergerá hacia cero a medida que aumentamos el número de clústeres, pero la penalización aumentará. En algunos puntos, la ganancia de agregar otro clúster será menor que la penalización introducida y obtendremos el resultado óptimo. Una solución que usa el Criterio de Información Bayesiano (BIC) para este propósito se llama X-Means [Pelleg and Moore, 2000].

Otra cosa que tenemos que definir correctamente es la función de distancia. A veces, esa es una tarea sencilla, 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 mucho conocimiento del dominio. O bien, podemos llamar a Machine Learning para obtener ayuda. De hecho, podemos tratar de aprender la función de distancia. Si tenemos un conjunto de puntos de entrenamiento que sabemos cómo deben agruparse (es decir, puntos etiquetados con sus grupos), podemos usar 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 alternos, se asemeja a un método de Expectativa-Maximización (EM). En realidad, puede considerarse una versión muy simple de EM. Sin embargo, no debe confundirse con el algoritmo de agrupamiento EM más elaborado, aunque comparte algunos de los mismos principios.

Agrupación de ME

Entonces, con el agrupamiento de K-Means, cada punto se asigna a un solo grupo, y un grupo se describe solo por su centroide. Esto no es demasiado flexible, ya que podemos tener problemas con clústeres que se superponen o que no tienen forma circular. Con EM Clustering, ahora podemos ir un paso más allá y describir cada grupo por su centroide (media), covarianza (para que podamos tener grupos elípticos) y peso (el tamaño del grupo). La probabilidad de que un punto pertenezca a un grupo ahora viene dada por una distribución de probabilidad gaussiana multivariante (multivariante - dependiendo de múltiples variables). Eso 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 grupo.

Ahora comenzamos el procedimiento EM calculando, para cada punto, las probabilidades de que pertenezca a cada uno de los grupos actuales (que, de nuevo, pueden crearse aleatoriamente al principio). Este es el paso E. Si un grupo es realmente un buen candidato para un punto, tendrá una probabilidad cercana a uno. Sin embargo, dos o más conglomerados pueden ser candidatos aceptables, por lo que el punto tiene una distribución de probabilidades entre conglomerados. Esta propiedad del algoritmo, de puntos que no pertenecen restringidos a un grupo, se llama "agrupamiento suave".

El paso M ahora vuelve a calcular los parámetros de cada grupo, utilizando las asignaciones de puntos al conjunto anterior de grupos. Para calcular la nueva media, covarianza y peso de un conglomerado, cada dato de punto se pondera por su probabilidad de pertenecer al conglomerado, tal como se calculó en el paso anterior.

La alternancia de estos dos pasos aumentará la probabilidad logarítmica total hasta que converja. Nuevamente, el máximo puede ser local, por lo que podemos ejecutar el algoritmo varias veces para obtener mejores agrupaciones.

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

Propagación de afinidad

Affinity Propagation (AP) fue publicado por Frey y Dueck en 2007, y se está volviendo cada vez 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 grupos y elegir el conjunto inicial de puntos. Affinity Propagation, en cambio, toma como entrada medidas de similitud entre pares de puntos de datos y simultáneamente considera todos los puntos de datos como ejemplos potenciales. Los mensajes de valor real se intercambian entre puntos de datos hasta que emerge gradualmente un conjunto de ejemplares de alta calidad y los grupos correspondientes.

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

1. Similitudes entre puntos de datos, que representan qué tan adecuado es un punto para ser el ejemplo de otro. Si no hay similitud entre dos puntos, ya que no pueden pertenecer al mismo grupo, esta similitud se puede omitir o establecer en -Infinito según la implementación.

2. Preferencias, que representan la idoneidad de cada punto de datos para ser un ejemplo. Es posible que tengamos información a priori de qué puntos se pueden favorecer para este rol, y así podemos representarlo a través de preferencias.

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

Luego, el algoritmo se ejecuta a través de una serie de iteraciones, hasta que converge. Cada iteración tiene dos pasos de paso de mensajes:

1. Cálculo de responsabilidades: la responsabilidad r(i, k) refleja la evidencia acumulada de qué tan adecuado es el punto k para servir como ejemplo del punto i, teniendo en cuenta otros posibles ejemplos del punto i. La responsabilidad se envía desde el punto de datos i al punto de ejemplo candidato k.

2. Cálculo de disponibilidades: La disponibilidad a(i, k) refleja la evidencia acumulada de cuán apropiado sería que el punto i eligiera 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 similitudes y disponibilidades originales calculadas en la iteración anterior (inicialmente, todas las disponibilidades se establecen en cero). Las responsabilidades se establecen en la similitud de entrada entre el punto i y el punto k como su ejemplar, menos la suma más grande de similitud y disponibilidad entre el punto i y otros ejemplares candidatos. La lógica detrás de calcular qué tan adecuado 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 un buen candidato, por lo que hay un ' competencia' entre los dos hasta que uno se decida en alguna iteración.

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

Finalmente, 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 brinda la información de agrupación que necesitamos: para el punto i, la k con el máximo r(i, k) + a(i, k) representa el punto soy ejemplar O, si solo necesitamos el conjunto de ejemplares, podemos escanear la diagonal principal. Si r(i, i) + a(i, i) > 0, el punto i es un ejemplo.

Hemos visto que con K-Means y algoritmos similares, decidir la cantidad de clústeres puede ser complicado. Con AP, no tenemos que especificarlo explícitamente, pero aún puede necesitar algunos ajustes si obtenemos más o menos clústeres de los que consideramos óptimos. Por suerte, con solo ajustar las preferencias podemos bajar o subir el número de clusters. Establecer preferencias en un valor más alto conducirá a más grupos, ya que cada punto está 'más seguro' de su idoneidad para ser un ejemplo y, por lo tanto, es más difícil de 'superar' e incluirlo bajo el 'dominio' de algún otro punto. Por el contrario, establecer preferencias más bajas dará como resultado tener menos grupos; como si dijeran “no, no, por favor, eres un mejor ejemplo, me uno a tu grupo”. Como regla general, podemos establecer todas las preferencias en la similitud mediana para un número medio a grande de conglomerados, o en la similitud más baja para un número moderado de conglomerados. Sin embargo, es posible que se necesiten un par de ejecuciones con preferencias de ajuste 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 al dividir el conjunto de datos en un par de subconjuntos, agruparlos por separado y luego realizar el segundo nivel de agrupamiento.

En el final…

Hay toda una gama de algoritmos de agrupamiento, cada uno con sus pros y sus contras con respecto a qué tipo de datos tienen, complejidad de tiempo, debilidades, etc. Para mencionar más algoritmos, por ejemplo, está el agrupamiento aglomerativo jerárquico (o agrupamiento de vinculación), bueno para cuando no necesariamente tenemos clústeres circulares (o hiperesféricos) y no sabemos la cantidad de clústeres de antemano. Comienza con cada punto como un grupo separado y funciona uniendo dos grupos más cercanos en cada paso hasta que todo esté en un gran grupo.

Con el agrupamiento aglomerativo jerárquico, podemos decidir fácilmente el número de grupos después cortando el dendrograma (diagrama de árbol) horizontalmente donde lo consideremos 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).

Luego, DBSCAN (agrupación espacial basada en la densidad de aplicaciones con ruido) también es un algoritmo que vale la pena mencionar. Agrupa los puntos que están muy juntos, expandiendo los grupos en cualquier dirección donde haya puntos cercanos, tratando así con diferentes formas de grupos.

Estos algoritmos merecen un artículo propio, y podemos explorarlos en una publicación separada más adelante.

Se necesita experiencia con algo de prueba y error para saber cuándo usar un algoritmo u otro. Afortunadamente, tenemos una variedad de implementaciones en diferentes lenguajes de programación, por lo que probarlas solo requiere un poco de disposición para jugar.