Un lugar para el clustering de K-means

Un espacio para el agrupamiento de K-means

¿Cómo agrupar puntos de datos similares de manera que tenga sentido? Bueno, K-Means es una de las respuestas. Este artículo resume prácticamente todo sobre el agrupamiento K-Means. Dicho esto, no escribí el código 🙂

ESQUEMA —

1. ¿Qué es el agrupamiento K-Means?
2. Propiedades de los grupos
3. Algoritmo para el agrupamiento K-Means
4. Criterio de convergencia/detención
5. Inicialización de centroides: K-Means ++
6. Elegir un K óptimo
7. Evaluación de la calidad del grupo

~Las aves de la misma pluma vuelan juntas

• Top importantes Documentos de Visión por Computadora de la semana del 9/10 al 15/10
• Tendencias futuras en la integración de datos
• ChatGPT vs. BARD

1. ¿Qué es el agrupamiento K-Means?

El agrupamiento K-Means es un algoritmo de aprendizaje no supervisado que nos ayuda a agrupar puntos de datos similares en nuestros datos en grupos. Estos grupos representan las características compartidas por los puntos de datos, que marcan su similitud.

En términos simples, K-Means es casi como KNN, donde miramos los K puntos más cercanos para encontrar similitud. En el agrupamiento K-Means, formamos K grupos de manera que los puntos agrupados en un grupo sean similares y compartan características comunes. El diagrama a continuación lo dejará más claro:

K-Means nos ayuda a lograr un gráfico como el que se muestra arriba simplemente pasando nuestros datos como parámetro de entrada. Dado que solo estamos formando grupos basados en los puntos de datos que tenemos, no necesitamos una etiqueta y para estos puntos. Por lo tanto, el agrupamiento es un algoritmo de aprendizaje no supervisado, donde no requerimos la etiqueta de los puntos de datos.

Aplicaciones del agrupamiento —

1. Segmentación de clientes2. Segmentación de documentos3. Segmentación de imágenes4. Sistemas de recomendación, etc.

2. Propiedades de los grupos

Ahora, estos grupos tienen algunas propiedades, las cuales los hacen significativos.

1. Todos los puntos de datos dentro de un grupo deben ser lo más similares posible — Los puntos de datos dentro de un grupo están muy cerca entre sí. Esto significa que en el espacio de características, los puntos de datos representan características similares. Además, los puntos similares se agruparían mejor. Por lo tanto, los puntos dentro de un grupo deben ser lo más similares posible para que el grupo tenga sentido.
2. Los puntos de datos de diferentes grupos deben ser lo más diferentes posible — Los puntos de datos de diferentes grupos están lejos entre sí. Esto significa que en el espacio de características, estos puntos representan características muy diferentes. Además, los puntos diferentes nunca formarían grupos. Por lo tanto, los puntos de diferentes grupos deben ser lo más diferentes posible para que los grupos tengan sentido.
3. Cada grupo tiene un centroide — Cada grupo que formamos tiene un centroide alrededor del cual todos los puntos están asociados. Este centroide es el punto que nos ayuda a formar los grupos y se ajusta según la media de los puntos dentro del grupo.

~Bueno, no te preocupes demasiado por las propiedades, es solo una teoría aburrida. La parte divertida viene a continuación

3. Algoritmo para el agrupamiento

Este es el lugar donde profundizamos en cómo este algoritmo genera hermosos grupos.

Algo —

• [Paso 1] — Elegir el número de grupos que queremos (K) — Esto puede ser elegido arbitrariamente por ahora, ya que decidiremos cómo elegir el valor K más adelante. El valor K = 3 se elige más comúnmente al inicio del algoritmo.
• [Paso 2] — Seleccionar K puntos aleatorios como K-centroides — Estos puntos también se seleccionan al azar para formar los centroides de cada grupo. Estos puntos pueden ser elegidos al azar de nuestros datos o de otro lugar.
• [Paso 3] — Asignar cada punto de datos al centroide más cercano — Luego calculamos la distancia de cada punto en nuestro conjunto de datos desde todos los K-centroides. El punto se asigna al centroide que tiene la menor distancia desde ese centroide. Esto se puede visualizar como se muestra a continuación:

Esto se repite para cada punto y eventualmente, cada punto se asigna a uno u otro centroide. De esta manera, terminamos con K grupos. Normalmente utilizamos la distancia euclidiana para calcular la distancia entre puntos y centroides.

• [Paso 4] — Calcular los nuevos centroides — Después de asignar cada punto a uno u otro centroide, calculamos los nuevos centroides para cada grupo tomando un promedio de todos los puntos en cada grupo. Los nuevos centroides se pueden calcular tomando el promedio de las coordenadas x y las coordenadas y de todos los puntos de datos por separado.

Aquí ‘m’ es el número de puntos de datos en un grupo en particular.

• [Paso 5] — Repetir los pasos 3 y 4 hasta alcanzar la convergencia/condición de parada

Vamos a visualizar :

1. [Paso 1] — Digamos que elegimos k = 22. [Paso 2] —

3. [Paso 3] —

4. [Paso 4] —

5. [Paso 5] —

4. Convergencia/Condición de Parada

El algoritmo anterior si no ha convergido, se repetiría infinitamente. Por lo tanto, necesitamos algún criterio de parada para el algoritmo anterior. Hay algunos criterios de parada, al encontrarlos el algoritmo debe detenerse. Estos son:

1. Los puntos de datos asignados en un clúster específico siguen siendo los mismos: ejecutamos el algoritmo hasta que los puntos de datos no se asignen a nuevos clústeres. Esto es muy lento de lograr y puede llevar mucho tiempo.
2. Los centroides siguen siendo los mismos: ejecutamos el algoritmo hasta que los nuevos centroides calculados sean iguales a los anteriores. Esto es muy lento de lograr y puede llevar mucho tiempo.
3. La distancia de los puntos de datos al centroide es mínima: establecemos un umbral para la distancia de los puntos de datos al centroide. Cuando se alcanza este umbral, el algoritmo se detendrá. Esto es rápido, pero debemos seleccionar el umbral de distancia con mucho cuidado.
4. Se ha alcanzado un número fijo de iteraciones: establecemos un umbral para el número de iteraciones y nos detenemos cuando se alcanza este umbral. Esto es rápido, pero una configuración de umbral imprudente puede llevar a una formación deficiente de clústeres.

Podemos implementar estas condiciones de parada en nuestro algoritmo para una convergencia temprana y una agrupación adecuada.

5. Inicialización del Centroide

En K-Means, inicializamos los centroides de forma aleatoria. Esto puede tener algunos problemas y puede llevar a una formación deficiente de clústeres.

• Si el centroide es un punto lejano (un valor atípico), es posible que no haya ningún punto de datos asignado a este centroide. Esto puede llevar a que se asignen más de un clúster al mismo centroide.
• Si dos o más centroides se inicializan muy cerca uno del otro, esto puede llevar a que se asignen más de un centroide al mismo clúster.

Ambos problemas se pueden visualizar en el siguiente diagrama:

Por lo tanto, necesitamos un mejor método para la inicialización del centroide. Podemos usar uno de los dos enfoques mencionados:

1. Repetir K-Means varias veces hasta obtener los mejores clústeres
2. Usar el algoritmo K-Means ++

El primero es muy ineficiente en términos de complejidad temporal por razones obvias. Por lo tanto, utilizamos el algoritmo K-Means++ para la inicialización del centroide.

K-Means ++

Esto es solo un algoritmo para la inicialización de los centroides, el resto del proceso es igual que el del algoritmo K-Means.

Algoritmo:

1. Seleccionar el primer centroide al azar
2. Ahora calcular la distancia de cada punto desde el centroide más cercano (el primer centroide al comienzo del algoritmo)
3. Ahora asignar valores de probabilidad a cada punto. Los valores de probabilidad son proporcionales a la distancia del punto desde el centroide anterior. Esto significa que un punto con la distancia máxima desde el centroide tendrá el mayor valor de probabilidad de ser seleccionado como el siguiente centroide.
4. Repetir estos pasos hasta tener K centroides.

Con esta inicialización, se garantiza que cada centroide esté lo más alejado posible de los demás. Por lo tanto, no se asigna más de un centroide al mismo clúster y no se asigna más de un clúster al mismo centroide.

Después de esto, el algoritmo K-Means se reanuda y los puntos de datos se asignan al centroide más cercano y así sucesivamente.

6. Elección de un K óptimo

Elegir un valor óptimo de K es muy importante, ya que esto puede llevar a clústeres estructurados de manera hermosa o a clústeres desorganizados y poco útiles.

Hay varias formas de elegir el valor de K, pero la forma más óptima es mediante un método llamado el método del codo. Nuestro objetivo aquí es encontrar el valor de K para el cual el error de suma de cuadrados intraclase (WCSSE) sea el menor.

WCSSE representa la suma de las distancias al cuadrado de los puntos de datos desde el centroide dentro del mismo clúster.

Método del Codo

El Método del Codo es una técnica con la cual podemos seleccionar un valor de K al observar el resultado dado por cada K.

El WCSSE se calcula para todos los clusters y se representa en función de diferentes valores de K. El punto en el gráfico donde el WCSSE disminuye bruscamente es el punto que estamos buscando. Este punto nos indica el valor particular de K, para el cual el WCSSE disminuye bruscamente y se vuelve casi constante. Después de este punto, incrementar el valor de K no reduce mucho el WCSSE y por lo tanto este punto es el valor óptimo de K.

Los pasos para el método del Codo son los siguientes:

• Elegimos un valor de K en un rango (por ejemplo, de 1 a 10)
• Para cada valor de K en este rango, encontramos el WCSSE para todos los clusters.
• Luego representamos el WCSSE en función de K, donde K está en el eje X.
• El valor de K en el cual el WCSSE disminuye bruscamente y forma una forma de codo, es el valor óptimo de K que elegimos.

Del gráfico anterior, podemos ver que para un valor de K de 5, el WCSSE disminuye bruscamente y se vuelve casi constante después. Por lo tanto, más allá de 5 clusters, el WCSSE no está disminuyendo mucho. Por lo tanto, elegimos K=5.

7. Evaluación de la Calidad del Cluster

Para que los clusters tengan sentido, debemos evaluar la calidad de cada cluster. Por calidad, me refiero a qué tan bien nuestros clusters explican nuestros datos. Para esto, debemos volver a nuestras propiedades del cluster. Un cluster que cumple todas las propiedades se considera un buen cluster. Entonces, ¿cómo podemos evaluar matemáticamente las propiedades del cluster?

Hay dos formas: 1. Inercia 2. Índice de Dunn

1. INERCIA

La inercia se refiere a la suma total de las distancias entre los puntos y el centroide del cluster para un cluster en particular. Esto también se puede considerar como la distancia intra-cluster ya que estamos calculando la distancia entre puntos dentro del cluster. Para un centroide de cluster C1, podemos definir la inercia como:

donde i varía de 1 a m(número de puntos en ese cluster)

La imagen anterior muestra la distancia inter-cluster o inercia.

Para que un cluster sea significativo, la distancia entre sus puntos y el centroide debe ser lo más pequeña posible. Así el cluster podría cumplir la primera propiedad.

Por lo tanto, el valor de inercia debe ser lo más pequeño posible para un buen cluster.

2. ÍNDICE DE DUNN

El índice de Dunn es la medida de la segunda propiedad de los clusters. Mide qué tan lejos están los clusters entre sí, lo que indica la diferencia entre las propiedades de dos clusters. El índice de Dunn lo hace calculando la distancia inter-cluster así como la distancia intra-cluster.

La distancia inter-cluster se refiere a la distancia entre dos clusters. Ahora, esta diferencia también puede depender de cómo la medimos.

— Puede ser la diferencia entre los centroides de los dos clusters — Puede ser la diferencia entre los puntos más alejados de los dos clusters — Puede ser la diferencia entre los puntos más cercanos de los dos clusters.

Independientemente del criterio elegido para medir la distancia inter-cluster, el índice de Dunn se puede representar como:

Para que dos grupos sean lo más diferentes / lejanos posible, el numerador debe ser muy grande y el denominador debe ser muy pequeño. Por lo tanto,

• La menor distancia entre dos grupos [distancia mínima entre grupos] debe ser muy grande para que el numerador sea un valor grande.
• La mayor distancia entre los puntos y el centroide de un grupo [distancia máxima dentro de un grupo] debe ser un número muy pequeño para que el denominador sea un valor pequeño.

Para que un grupo sea significativo, la distancia entre grupos debe ser lo más grande posible. Por lo tanto, el grupo podría cumplir la segunda propiedad.

Por lo tanto, el Índice Dunn debe ser lo más grande posible para un buen grupo.

Bueno, eso fue casi todo sobre K-Means Clustering, en teoría. Lo codificaré.

Échale un vistazo a esto también—

1. KNN
2. Regresión Logística
3. Máquina de Vectores de Soporte
4. Naive Bayes
5. Métricas de Evaluación – Clasificación

We will continue to update Zepes; if you have any questions or suggestions, please contact us!