clusters

Tabla de contenidos

K-Means

Es un algoritmo no supervisado de tipo geométrico traducido como “K medias” donde buscamos encontrar un número K (previamente definido) de agrupaciones generadas en base a similitudes entre los atributos de las observaciones del dataset. Para medir esta similitud se utiliza la clásica distancia euclídea:

Ilustración para dos dimensiones (atributos)

El proceso de generación de estos grupos o clústers consiste en inventar K observaciones (centroides) hipotéticas e ir ajustándolas hasta que sean las más representativas, es decir, aquellas que contengan los atributos más característicos de K agrupaciones. Las observaciones de un clúster deberán ser lo más homogéneas posibles entre sí y lo más heterogéneas posible con respecto a las de los otros clústers.

Por tanto, si consideramos que la similitud entre estos centroides y el resto de observaciones es proporcional a la distancia que los separa, entonces buscamos minimizar las distancias de las observaciones con respecto a sus centroides asociados. El proceso de deducción de grupos es el siguiente:

  1. Tras una asignación inicial aleatoria de K centroides (puntos, o más bien, vectores en el plano), de manera iterativa, cada muestra de datos se asocia a su centro de agrupación más cercano.
  2. Al final de cada iteración, los centroides se ajustan para reubicarse en el centro de todas las muestras asociadas a ellos, es decir, en el punto más equidistante con respecto a las observaciones que han caído en su clúster.

Estos pasos se repiten hasta que se cumple un determinado criterio: iteraciones máximas o cambio mínimo entre las dos últimas iteraciones.

source

Nota: Aunque el conjunto de datos que he utilizado en este artículo es de tipo texto, el código que expondré en apartados posteriores es extrapolable a otros datasets de tipo estructurado, a excepción de la carga de datos y vectorización que adjunto a continuación (transformación de datos no estructurados en vectores interpretables por el algoritmo). Para mayor información sobre esta transformación puedes echar un ojo a este artículo.

1.1 Búsqueda de la K óptima: Basado en distancias

Para saber el número ideal de clases en los que deberíamos agrupar los datos sin utilizar el “ground truth”, es decir, sin conocer las clases asigandas a cada observación, deberemos basarnos en la cohesión intra-clúster (distancias entre las observaciones de un mismo cluster) o la separación inter-clúster (distancias entre las observaciones de un cluster con respecto a las observaciones del resto de clústers):

Coeficiente de Silhouette (Silhouette score): Su resultado está limitado entre -1 y 1:

  • Un valor cercano a -1 indica que la mínima distancia media inter-clúster es muy inferior a la distancia media intra-clúster. Es decir, que existen muchas observaciones que son más similares a las de otros clusters que a las de su propio cluster.
  • Un valor cercano a 1 indica que el algoritmo logró un muy buen nivel de cohesión interna y separación entre grupos, ya que la mínima distancia inter-clúster es muy superior a la distancia media intra-clúster. Dicho de otro modo, no hay ninguna o casi ninguna observación que sea más parecida a una observación de un grupo diferente, que a una observación de su propio grupo.

La siguiente fórmula calcula el coeficiente de Silhouette para una sola observación del conjunto de datos:

source

  1. Para cada observación, i, calculamos la distancia promedio entre esta y todas las demás observaciones en el mismo grupoai.
  2. Calculamos las distancias medias entre esta misma observación y todas las observaciones en cada uno de los otros grupos; la distancia promedio más baja será bi.
  3. Restamos bi menos ai y dividimos por el número máximo de entre ai y bi.

Este proceso se repite para todas las observaciones del conjunto de datos.

Para dar con la K óptima entrenaremos K veces el modelo, calculando la puntuación de Silhouette para cada diferente valor de K.

Los valores óptimos de K vienen dados por la curvatura de mayor convergencia de la función, marcada por el círculo amarillo; el número ideal de K ronda las 15–20 agrupaciones.

La idea es que los primeros grupos generados agregarán mucha información (varianza), pero una vez que el número de grupos excede el número real u óptimo de grupos la información agregada cae bruscamente, ya que solo está subdividiendo los grupos reales. Este hecho se manifiesta en la representación gráfica en forma de “codo” o cambio más brusco de la pendiente.

Método de error de inercia (Inertia error method): Cuanto más variedad haya entre las observaciones del dataset mayor serán sus distancias respecto a sus centroides asociados. La inercia o intertia, en el contexto del K-Means, es la suma de todas las distancias de las observaciones de un clúster a su centroide. Suponiendo que el objetivo es reducir la suma de distancias (cuadrados) de puntos con sus respectivos centroides, cuanto menor sea esta suma total, mejor, ya que indicará una mayor homogeneidad en las observaciones pertenecientes a los clústers creados.

source

Vemos, de nuevo, que el “codo” (elbow) de la curva parece ubicarse en K ∈ [10–20]. En este caso es más complicado de observar ya que la pendiente es mucho más suave. Aunque dicha distancia parece reducirse indefinidamente, no hace falta decir que acabará pecando de overfitting, ajustándose en exceso a los atributos de las muestras y perdiendo la capacidad de generalizar adecuadamente la pertenencia de una muestra a un determinado grupo, por tanto, buscamos un punto de equilibrio.

1.2 Búsqueda de la K óptima: Basado en Ground Truth

Para evaluar el desempeño también podemos recurrir al “ground truth”, es decir, a las clases asignadas de manera supervisada. Como es lógico, no es habitual contar con ellas en los conjuntos de datos empleados para algoritmos no supervisados, pero en caso de tenerlas existen métricas que evalúan el resultado mediante una comparativa de las etiquetas predichas con las etiquetas reales:

  • Coeficiente de homogeneidad: Esta métrica se basa en la premisa de que un clúster o grupo debería contener solo muestras que pertenezcan a una única clase. Es decir, mide la heterogeneidad en la distribución de clases reales (asignadas de forma supervisada) de las observaciones pertenecientes a un determinado clúster. Su resultado está acotado entre 0 y 1, siendo más homogéneo (mejor) cuanto más cerca del 1 esté.
  • Coeficiente de completitud: Esta otra métrica se basa en la premisa de que el algoritmo debería asignar el mismo clúster a las mismas observaciones que lo compartían en el etiquetado real. Su resultado está también limitado entre -1 y 1, siendo 1 el valor óptimo.
  • Coeficiente Rand ajustada (adjusted rand score): De nuevo, está limitado entre -1 y 1; un valor cercano a -1 indica una prevalencia de asignaciones a un clúster incorrecto, mientras que un valor cercano a 1 indica que el algoritmo de agrupamiento está reproduciendo correctamente la distribución de la verdad fundamental (ground truth distribution).

Del mismo modo que en las anteriores métricas, vamos a iterar un entrenamiento y acumular el error de cada una de estas puntuaciones para cada valor de K.

2. Entrenamiento con K óptima

A continuación, entrenamos el algoritmo no supervisado con el número de grupos K = 20 y echamos un ojo a la distribución de observaciones por cada clúster generado.

Para atenuar la variabilidad del resultado usaremos la validación cruzada. Si no conoces este concepto puedes echar un ojo a este artículo.

El método “score” para el caso de K-Means con la librería Sklearn calcula la media de las distancias de todas las observaciones del dataset a sus respectivos clústers, en negativo, como criterio para evaluar el modelo. Este cálculo es conocido como distorsión o distortion y es similar al error de inercia, con la salvedad de que realiza un promedio en vez de acumular las distancias de cada observación a su respectivo centroide.

Accuracy per fold: [-71.14549414 -72.67791944 -71.04928676 -71.97185517 -72.90843598   -69.61543214 -70.40156191 -69.85335418 -72.07096672 -72.12241503]  Mean accuracy: -71.382  Std. deviation: +- 2.188

Si te ha gustado el artículo puedes clicar 👏 tantas veces como quieras. Además, puedes seguir mi cuenta para estar al tanto de futuras publicaciones.

Por Guzman Gomez

Ingeniero de Machine Learning especializado en Chatbots

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *