k means algorithm

algoritmo k-medias

Esta es una implementación en Python del algoritmo k-means que incluye el método del codo y el método de la silueta para seleccionar el K óptimo.

K-means es un algoritmo de agrupación popular que se utiliza para dividir datos en K grupos. Funciona asignando iterativamente cada punto de datos al centroide del grupo más cercano y luego recalculando el centroide de cada grupo en función de los puntos de datos que se le asignaron. El proceso se repite hasta la convergencia.

Algoritmo

• Seleccione aleatoriamente K centroides del grupo inicial de los puntos de datos.
• Asigne cada punto de datos al centroide del grupo más cercano.
• Vuelva a calcular el centroide de cada grupo en función de los puntos de datos que se le asignaron.
• Repita los pasos 2 y 3 hasta la convergencia (es decir, cuando las asignaciones de clústeres ya no cambien).

Función objetivo

El objetivo de k-medias es minimizar la suma de distancias al cuadrado entre cada punto de datos y su centroide de grupo asignado. La función objetivo se puede escribir como: $$J = sum_{j=1}^K sum_{i=1}^N||x_i^j - mu_j||^2$$ dónde $x_i^j$ es el i-th punto de datos dentro del grupo j , μj es el centroide del grupo j y N es el número total de puntos de datos.

Método del codo

El método del codo es una heurística que se utiliza para determinar el número óptimo de grupos en la agrupación de K-Means. El método traza la suma de distancias al cuadrado entre cada observación y su centroide asignado en función del número de grupos. El punto "codo" en el gráfico indica el número de grupos donde agregar grupos adicionales no da como resultado una reducción significativa en la suma de distancias al cuadrado.

El método del codo se puede resumir en los siguientes pasos:

• Ejecute la agrupación de K-Means para un rango de valores de k
• Calcula la suma de distancias al cuadrado para cada valor de k.
• Trazar la suma de distancias al cuadrado en función de k
• Identificar el punto del "codo" en la trama.

Método de silueta

El método Silhouette es otra heurística utilizada para determinar el número óptimo de conglomerados en la agrupación de K-Means. El método mide la calidad de la asignación de conglomerados de cada observación calculando su coeficiente de silueta. El coeficiente de silueta varía de -1 a 1, donde un valor de 1 indica que la observación está bien agrupada y un valor de -1 indica que la observación está mal clasificada. La fórmula para calcular el coeficiente de silueta para un punto de datos i es: $$s(i) = frac{(b(i) - a(i))}{max(a(i), b(i))}$$ donde a(i) es la distancia promedio entre i y todos los demás puntos de datos en su grupo, y b(i) es la distancia promedio mínima entre i y todos los demás grupos (es decir, el grupo con el siguiente centroide más cercano). El coeficiente de silueta para todo el agrupamiento es el promedio de los coeficientes de silueta para todos los puntos de datos.

El método Silhouette se puede resumir en los siguientes pasos:

• Ejecute la agrupación de K-Means para un rango de valores de k
• Para cada observación, calcule el coeficiente de silueta.
• Calcule el coeficiente de silueta promedio para cada valor k
• Trazar el coeficiente de silueta promedio en función de k
• Identifique el valor k con el coeficiente de silueta promedio más alto