Clustering

Clasificación

Objetivo

Clustering en Scikit-Learn

La agrupación de datos sin etiquetar se puede realizar con el módulo sklearn.cluster, el cual cuenta con varios métodos diferentes:

Método K-Means (algoritmo de Lloyd)

El algoritmo, explicado

El algoritmo k-means (k-medias) agrupa los datos tratando de separar las muestras en n grupos de igual varianza, minimizando un criterio conocido como inercia o suma de cuadrados dentro del grupo:

Actúa dividiendo un conjunto de N muestras X en K grupos (clústeres) C, cada uno descrito por la media de las muestras en el cluster. Las medias se denominan comúnmente “centroides” del grupo.

En términos básicos, el algoritmo tiene tres pasos:

• Inicialización. En primer lugar, el usuario escoge el número de grupos, k, que quiere formar. En función de este número, el algoritmo escoge los k centroides iniciales, siendo el método más básico escoger muestras aleatorias del conjunto de datos.
• Asignación de muestras a los centroides. Después, se asigna cada muestra a su centroide más cercano.
• Actualización de centroides. Se crean nuevos centroides tomando el valor medio de todas las muestras asignadas a cada centroide anterior y se calcula la diferencia entre los centroides antiguo y nuevo. El algoritmo repite los dos últimos pasos hasta que esta diferencia es menor que un umbral. En otras palabras, se repite hasta que los centroides no se mueven significativamente.

Por tanto, el algoritmo k-means resuelve un problema de optimización, cuya función a optimizar (minimizar) es la inercia, que ya definimos más arriba como la suma de las distancias cuadráticas de cada objeto al centroide de su cluster.

Parámetros

class sklearn.cluster.KMeans(n_clusters=8, *, init=‘k-means++’, n_init=10, max_iter=300, tol=0.0001, precompute_distances=‘deprecated’, verbose=0, random_state=None, copy_x=True, n_jobs=‘deprecated’, algorithm=‘auto’)

n_clusters

Es el número de clústeres que se formarán, así como el número de centroides que se generarán. Tiene que ser un número entero, que por defecto es 8.

Como es difícil escoger este valor desde un principio (a menos que tengamos claro el número de grupos que queremos obtener), puede ser una buena opción recurrir al método del codo (elbow method) o al de la silueta (silhouette method), que se explican más abajo en este mismo notebook.

init

Es el método de inicialización, que tiene que se una opción de las siguientes:

{‘k-means++’, ‘random’, ndarray, callable}

Por defecto es ‘k-means ++’.

Con el tiempo suficiente, K-medias siempre llegará a una solución, sin embargo, puede no ser la mejor. Esto depende en gran medida de la inicialización de los centroides. Como resultado, el cálculo a menudo se realiza varias veces, con diferentes inicializaciones de los centroides.

• ‘k-means++’: selecciona los centros de clústeres iniciales para el clustering de k-mean de una manera inteligente para acelerar la convergencia, de tal forma que estén (generalmente) distantes entre sí, lo que conduce a resultados demostrablemente mejores que la inicialización aleatoria.

• ‘random’: elige n_clusters observaciones (filas) al azar de los datos para los centroides iniciales.

• Si se pasa un ndarray, debería tener forma (n_clusters, n_features) y proporcionar los centros iniciales.

• Si se pasa un invocable (callable), debe tomar los argumentos X, n_clusters y un random_state y devolver una inicialización.

n_init

Es el número de veces que se ejecutará el algoritmo de k-medias con diferentes semillas de centroide. Los resultados finales serán el mejor resultado de n_init ejecuciones consecutivas en términos de inercia.

Tiene que ser un número entero, que por defecto es 10.

tol

Es la tolerancia relativa con respecto a la diferencia en los centros de los clústeres de dos iteraciones consecutivas para declarar convergencia, es decir, para declarar que los centroides ya no se han movido significativamente.

Tiene que ser un float, que por defecto es 0.0001.

algorithm

Es el algoritmo de K-means a utilizar, que tiene que ser una opción de las siguientes:

{“auto”, “full”, “elkan”}

Por defecto es “auto”.

El algoritmo clásico es “full”. La variación “elkan” es más eficiente en datos con grupos bien definidos, pero consume más memoria. Por ahora, “auto” elige “elkan”, pero podría cambiar en el futuro.

Recomendaciones

Debido a que los grupos se forman a partir de distancias, es conveniente escalar los datos para que todos los valores de cada característica se encuentren en escalas similares. Si hay variables con escalas muy diferentes, las de mayor escala dominarán las distancias.

Además, la inercia no es una métrica normalizada: solo sabemos que los valores más bajos son mejores y que el cero es el óptimo. Sin embargo, en espacios de muy alta dimensión, las distancias euclidianas tienden a crecer demasiado (este es un ejemplo de la llamada “maldición de la dimensionalidad”). La ejecución de un algoritmo de reducción de dimensionalidad como el análisis de componentes principales (PCA) antes de la agrupación de k-medias puede aliviar este problema y acelerar los cálculos.

El método del codo

Este método permite comparar los valores de inercia obtenidos tras aplicar K-means a diferente número de clústeres, representando en una gráfica la inercia respecto del número de clústeres. La idea detrás de este método se basa en que, en cierto punto, se suele producir un cambio brusco en la evolución de la inercia, y por tanto la línea toma una forma parecida a la de un brazo y su codo. Ese punto indica el número óptimo de clústeres a escoger para el conjunto de datos dado, es decir, el “codo” corresponde al número óptimo de clústeres.

Ejemplo de código para aplicar este método:

kmeans_instances = [KMeans(n_clusters=i) for i in range(1, test_clusters_number)]

scores = [kmeans_instances[i].fit(my_matrix).score(my_matrix) for i in range(len(kmeans_instances))]

El método de la silueta

El método de la silueta se puede utilizar para estudiar la distancia de separación entre los clústeres resultantes. El gráfico de silueta muestra una medida de lo cerca que está cada punto en un clúster con respecto a los clústeres vecinos, la cual se expresa como un número dentro del rango [-1, 1].

Los coeficientes de silueta (como se denominan estos valores) cercanos a +1 indican que la muestra está lejos de los clústeres vecinos. Un valor de 0 indica que la muestra está muy cerca del límite de decisión entre dos clústeres vecinos y los valores negativos indican que esas muestras podrían haber sido asignadas al clúster incorrecto.

Ejemplo:

https://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_silhouette_analysis.html

Métodos de agrupamiento jerárquico (hierarchical clustering)

Una de los problemas que tiene el método k-means es que necesita definir un número de clústeres desde un primer momento. Existen otras técnicas que no tienen este requisito, como por ejemplo la agrupación jerárquica. Además, la agrupación jerárquica genera siempre los mismos clústeres, mientras que el agrupamiento de k-means puede dar lugar a grupos distintos dependiendo de cómo se inicien los centroides.

La agrupación jerárquica es una familia general de algoritmos de clustering que actúan construyendo grupos anidados, fusionándolos o dividiéndolos sucesivamente. Hay dos tipos de agrupación jerárquica:

• Agrupación aglomerativa: comienza haciendo un grupo de cada punto individual y va fusionando iterativamente los grupos similares para formar grupos cada vez más grandes.
• Agrupación divisiva: al contrario que en el caso anterior.

La jerarquía de grupos se representa como un árbol (o dendrograma). La raíz del árbol es el grupo único que reúne todas las muestras, mientras que las hojas son los grupos con una sola muestra.

Agrupación aglomerativa (agglomerative clustering)

Funcionamiento

La técnica de Agglomerative Clustering realiza una agrupación jerárquica utilizando un enfoque de abajo hacia arriba: cada observación comienza en su propio grupo y los grupos se van fusionando sucesivamente.

Criterios de agrupamiento

Existen muchos métodos diferentes que se pueden utilizar para ir vinculando los grupos en base a la similitud entre unos y otros. Scikit Learn cuenta con los 4 métodos siguientes:

• Vinculación de Ward: minimiza la suma de diferencias cuadradas dentro de los grupos. Es un enfoque que minimiza la varianza y, en este sentido, es similar a la función objetivo de k-medias, pero se aborda con un enfoque jerárquico aglomerativo.
• Vinculación de enlace máximo o completo: minimiza la distancia máxima entre observaciones de pares de grupos.
• Vinculación de promedio: minimiza el promedio de las distancias entre todas las observaciones de pares de grupos.
• Vinculación de enlace mínimo, simple o único: minimiza la distancia entre las observaciones más cercanas de pares de grupos.

Los enlaces mínimos, promedio y máximos se pueden combinar con una variedad de distancias (o afinidades), como la distancia euclidiana (l2) o la distancia de Manhattan (o Cityblock, o l1). La distancia l1 suele ser buena para características escasas o ruido escaso: es decir, muchas de las características son cero, como en la minería de texto que analiza apariciones de palabras raras. Lógicamente, es conveniente utilizar una métrica de distancia que maximice la distancia entre muestras de diferentes clases y la minimice dentro de cada clase.

Criterios de parada

Para evitar llegar a combinar todos los puntos de datos en un único grupo, hay que dejar de combinar clústeres en algún momento. Scikit-learn cuenta con dos opciones para esto:

• Detenerse después de alcanzar un número concreto de clústeres (hiperparámetro n_clusters).
• Establecer un valor de umbral para la vinculación (hiperparámetro distance_threshold). Si la distancia entre dos grupos está por encima del umbral, estos grupos ya no se fusionarán.

Hiperparámetros

class sklearn.cluster.AgglomerativeClustering(n_clusters=2, *, affinity=‘euclidean’, memory=None, connectivity=None, compute_full_tree=‘auto’, linkage=‘ward’, distance_threshold=None)

Hiperparámetro n_clusters

El número de grupos que se van a encontrar. Debe ser None si el hiperparámetro distance_threshold no es None, es decir, solo se puede utilizar uno de los dos criterios de parada.

Hiperparámetro affinity

Métrica utilizada para calcular la similitud. Puede ser “euclidean”, “l1”, “l2” o “manhattan”, entre otras opciones. Si el hiperparámetro “linkage” es “ward”, solo se acepta “euclidean”.

Hiperparámetro linkage

Es el criterio de vinculación a utilizar para formar los grupos.

Puede ser una opción de las siguientes: {“ward”, “complete”, “average”, “single”}. Por defecto es ”ward”.

Este hiperparámetro determina qué criterio de distancias se va a utilizar entre grupos de puntos. El algoritmo combinará pares de clústeres que minimicen este criterio.

• “ward” utiliza el criterio de vinculación de Ward.
• “complete” utiliza el criterio de vinculación de enlace máximo o completo
• “average” utiliza el criterio de vinculación de vinculación de promedio.
• “single” utiliza el criterio de vinculación de enlace mínimo, simple o único

Hiperparámetro distance_threshold

Permite especificar el threshold o límite por encima del cual los clústeres no serán combinados. Si es distinto de “None”, el hiperparámetro n_clusters debe ser “None” y compute_full_tree debe ser “True”.

Agrupación divisiva

Funciona de manera opuesta al agrupamiento aglomerativo. Como no se suele utilizar, en este curso no profundizaremos en esta técnica.