▷ Algoritmo KMeans - Funcionamiento y Código en Python

Dentro del ampli mundo del Aprendizaje No Supervisado hay muchos algoritmos para encontrar clusters. Hoy vamos a explicar y a entender KMeans, el algoritmo de agrupamiento particional más famoso.

¿Cómo Funciona el Algoritmo KMeans?

Teniendo un conjunto de datos, el objetivo es agruparlos de forma que los puntos pertenecientes a un mismo cluster estén lo más juntos posible, y a la vez estén lo más lejos posible del resto de clusters. Con términos estadísticos, esto quiere decir que KMeans se basa en minimizar la varianza intracluster y maximizar la varianza intercluster.

La medida de bondad del agrupamiento, es decir, el medidor que nos indica cómo de bien se han ajustado los datos es la inercia y haremos experimentos con ella durante el ejemplo. La inercia indica el nivel de cohesión, por lo que un valor pequeño de la inercia implica un mejor agrupamiento.

Esquema:

Datos de entrada: Dataset
Hiperparámetro: k = Número de clusters que queremos encontrar
Resultado: k centroides definitivos junto con el agrupamiento final.

Pasos de KMeans

Asigna aleatoriamente cada uno de los puntos del dataset a un cluster aleatorio.
Para cada uno de los k clusters, calcula su centroide.
Asigna cada dato del dataset al centroide más cercano.
Se repiten los pasos 2 y 3 hasta que en la asignación no haya cambios o hasta la variación de la inercia no sea significativa.

El objetivo final, que comparte con todos los algoritmos de agrupamiento, es encontrar la estructura interna de un conjunto de datos, descubriendo sus propiedades intrínsecas.

Cómo Programar KMeans en Python

Vamos a probar ahora con un ejemplo sintético en Python propuesto en el libro Python Data Science Handbook (disponible en Amazon). Antes de empezar, es importante cargar las librerías necesarias para el ejercicio.

%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns; sns.set()  #Para el estilo de los gráficos
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

Hay que tener en cuenta que, al ser un ejemplo sintético, la agrupación es muy evidente, pero en los casos reales no lo es tanto. Empezaremos creando nuestro propio dataset en dos dimensiones con el método <make_blobs>. Crearemos 4 clusters y simularemos 400 datos.

X, y_true = make_blobs(n_samples=400, centers=4,
                       cluster_std=0.60, random_state=0)
plt.scatter(X[:, 0], X[:, 1], s=50);

A continuación, usamos KMeans con k=4, que es el valor evidente a partir de la visualización de datos. Como la salida de KMeans son los centroides resultantes y el agrupamiento final, podemos representar gráficamente a qué cluster pertenece cada punto del dataset. Además, calcularemos la inercia para comprobar la validez del agrupamiento.

#Entrenamos el modelo KMeans
kmeans = KMeans(n_clusters=4)
kmeans.fit(X)  #Procesa los datos
y_kmeans = kmeans.predict(X) #Asigna etiquetas

#Representamos gráficamente los datos y la pertenencia a cada grupo
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis')

centers = kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='black', s=200, alpha=0.5);
plt.title("Inercia = {:0.2f}".format(kmeans.inertia_))
plt.show()

El siguiente paso es experimentar con el código. ¿Cuánto influye el hiperparámetro k en el algoritmo? ¿Cómo cambiará la inercia si busco 8 clusters? ¿Y si busco 2? Pues vamos a probar.

Partimos del mismo dataset anterior y volvemos a llamar a la función KMeans pero esta vez especificamos en primer lugar 8 y luego 3. Representamos gráficamente las agrupaciones resultantes.

#Creamos 4 clusters, pero le mandamos buscar 8. La inicialización es con kmeans++.

X, y_true = make_blobs(n_samples=300, centers=4,
                       cluster_std=0.60, random_state=0)
plt.scatter(X[:, 0], X[:, 1], s=50);

kmeans = KMeans(n_clusters=8)
kmeans.fit(X)  
y_kmeans = kmeans.predict(X) 

plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis')

centers = kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='black', s=200, alpha=0.5);
plt.title("Inercia = {:0.2f}".format(kmeans.inertia_))
plt.show()

#Para el resto de ejemplos, el código es el mismo pero cambiando el parámetro n_clusters

Nos fijamos en la inercia:

Ejemplo 1: 4 conjuntos, buscamos 4 clusters. Inercia = 212.01.
Ejemplo 2: 4 conjuntos, buscamos 8 clusters. Inercia = 132.12.
Ejemplo 3: 4 conjuntos, buscamos 2 clusters. Inercia = 1190.78.

La conclusión que se extrae es la siguiente: el agrupamiento con mejor inercia corresponde al de 8 clusters. Esto se debe a que al haber menos puntos por cluster, están más compactos, y la inercia baja. En el caso con 2 clusters pasa al contrario: clusters más grandes generan inercias más grandes, porque sus puntos están más dispersos.

¿Esto quiere decir que debo buscar más clusters de los necesarios para reducir la inercia? ¡No! Es necesario buscar el número de clusters que mejor modelice nuestros datos. En este caso es evidente que el valor del hiperparámetro k es 4, pero cuando no sea tan evidente, nos valdremos de la variación de la inercia explicada anteriormente para encontrar el valor óptimo.

Otra prueba que podemos realizar es la ejecución paso a paso del algoritmo para observar cómo converge. Para ello, añadimos el parámetro <random_state = 0> tanto en las llamadas de las funciones de <make_blobs> y <random_state = 666> en la llamada de KMeans. Esto fija la semilla aleatoria para que no varíen los resultados con cada ejecución. Otro parámetro que debemos alterar es la inicialización, que será aleatoria. Por último, hemos de cambiar el número de iteraciones máximas a 1, 2, 3… Para ir visualizando paso a paso el algoritmo.

Observamos la primera iteración:

Observamos la segunda iteración:

Observamos la tercera iteración:

Observamos la cuarta iteración:

Como la inercia no ha cambiado apenas entre las iteraciones 4 y 5; diríamos que la condición de parada se cumple y esos serían los clusters definitivos. Vemos que a lo largo de las iteraciones, los centroides cambian de posición sutilmente y la inercia va bajando.

Lo que cabría esperar es que pasara como con el ejemplo anterior, que 4 agrupaciones para 8 posibles clusters se agruparan de forma que cada conjunto de datos se dividiera en 2. Pero como aquí la inicialización es aleatoria, un conjunto de datos se divide en 3.

Llegamos, pues, a otra de las problemáticas más famosas de KMeans, su inicialización.

Problemas de KMeans: la Inicialización

Hemos visto que la inicialización es otra parte importante para KMeans. Mismas ejecuciones del algoritmo con idénticos parámetros podrían dar resultados distintos. Esto se debe, principalmente, al primer punto del algoritmo, la inicialización aleatoria. Hay varias formas de paliar esta aleatoriedad:

Ejecutar repetidas veces el algoritmo con distintas condiciones de inicialización y guardarnos el mejor resultado (GRASP).
Realizar previamente un Agrupamiento Jerárquico para tener una inicialización con criterio.
Una inicialización personalizada con conocimiento propio del problema, por ejemplo si conocemos alguna etiqueta.
Finalmente, la más utilizada es usar un algoritmo para la inicialización que suele asegurar una buena convergencia, el algoritmo KMeans++.

El Algoritmo KMeans++

La clave de esta inicialización es que no elimina por completo la aleatoriedad, pero facilita el hecho de encontrar una inicialización lo más óptima posible.

Esquema:

Datos de entrada: Dataset.
Hiperparámetro: k = Número de clusters que queremos encontrar.
Resultado: k centroides iniciales.

Pasos de KMeans++

Selecciona un centroide aleatorio.
Calcula la distancia de cada punto a cada centroide.
Selecciona el nuevo centroide tal que la probabilidad es directamente proporcional a la distancia al centroide más cercano.
Se repiten los pasos 2 y 3 hasta haber asignado los k centroides.

El objetivo es que los centroides iniciales estén los más separados posibles y envuelvan el dataset, de forma que cuando el algoritmo KMeans comience, no caiga en mínimos locales no óptimos.

¿Cómo Encontrar el Número de Clusters para KMeans?

La elección del hiperparámetro k es vital para el buen funcionamiento del algoritmo. Es lo que indica de qué forma se va a buscar la estructura interna de los datos. Como ha de explicitarse en la llamada del algoritmo, es un valor que hay que determinar por métodos externos a KMeans. Hay dos métodos clásicos para hallar el valor óptimo de k en función de los datos de lo que disponemos:

Elbow Curve o Curva de Codo

Es la representación más utilizada. Es una curva que expresa la inercia propia del agrupamiento en función del número de clusters que buscamos. Lo que hay que buscar en la curva es lo que se denomina <codo de la función>, es decir, el cambio brusco en la inercia. Nos indica que, a partir de ese k, el valor de la inercia se estabiliza e indica los mejores valores de k. Puede ser que la curva no marque un codo muy evidente, por lo que se suele probar varios valores de k.

Para nuestro caso, hemos simulado una búsqueda de 1 a 8 clusters y vemos un codo evidente en el número 4. Esto nos indica que, según este método, el mejor k que podemos probar es 4, a partir de ese valor, la inercia se estabiliza.

#Recorremos los valores de la posible k
Nc = range(1, 9)
score = []
for i in Nc:
    kmeans = KMeans(n_clusters=i, init='k-means++', n_init=10, max_iter=100, random_state=42)
    kmeans.fit(X)
    inercia = kmeans.inertia_
    score.append(inercia)

#Este código visualiza la curva
plt.plot(Nc,score)
plt.xlabel('Number of Clusters')
plt.ylabel('Score')
plt.title('Elbow Curve')
plt.show()

Coeficiente de Silhouette

Es una medida similar a la inercia que mide la variación intracluster pero, además, también mide lo seguro que se está de que un punto pertenezca a un cluster. Así se identifican puntos mal asignados o puntos que se encuentran en medio de dos clusters. Lo que se hace es hacer un bucle que pase por todos los posibles valores de k, representar el coeficiente de Silhouette y quedarse con el mejor agrupamiento. Cuanto más alto es el coeficiente de Silhouette, mejor es el agrupamiento. Nota: Entre los valores de k no puede estar el valor 1, porque da error.

En nuestro caso, el coeficiente de Silhouette también nos indica que el mejor valor de k es 4 porque tiene el valor del coeficiente más alto y no hay presencia de datos en el lado negativo del gráfico.

from sklearn import metrics
from sklearn.metrics import silhouette_score
from yellowbrick.cluster import SilhouetteVisualizer
from sklearn.metrics import silhouette_samples, silhouette_score

#instrucción que define el número de gráficas a representar y su tamaño
fig, ax = plt.subplots(4, 2, figsize=(15,8))
plt.subplots_adjust(hspace = 0.5)
for i in [2,3,4,5,6,7,8,9]:

    #Create KMeans instance for different number of clusters

    km = KMeans(n_clusters=i, init='k-means++', n_init=10, max_iter=100, random_state=42)
    q, mod = divmod(i, 2)
    
    km.fit(X)
    score = silhouette_score(X, km.labels_, metric='euclidean')
    visualizer = SilhouetteVisualizer(km, colors='yellowbrick', ax=ax[q-4][mod])
    score = silhouette_score(X, km.labels_, metric='euclidean')
    visualizer.set_title(f"Valor Promedio Coeficiente{score:.3}, k = {i}" )
    #Fit the visualizer
    visualizer.fit(X)

Los Problemas de KMeans

Además de los problemas comentados en apartados anteriores, KMeans tiene un listado, no precisamente corto, de problemas basados en asunciones.

Es muy sensible a la inicialización.
Sensible al ruido.
Asume clusters con formas esféricas o circulares.
Asume densidades parecidas.
Asume tamaños de clusters parecidos.
Se necesita determinar el número k de clusters.

Podemos concluir que KMeans es un algoritmo muy útil tanto para entender el mundo del agrupamiento como para usarlo en un análisis riguroso de datos. Es cierto que tiene muchos inconvenientes, pero los algoritmos posteriores los van solucionando. ¡Aunque eso es tema para otro artículo!

Esperamos haber aclarado todas tus posibles dudas sobre el algoritmo más común de agrupación. Como siempre, comparte este artículo si te ha sido útil o si puede aclarar dudas de otras personas. Y si tienes cualquier pregunta, déjanosla en los comentarios. ¡Un saludo!