Chapter 4 “K-means clustering”
Dariel Tejada
2023-05-28
Introducción
El algoritmo de clustering de K-means es ampliamente utilizado en el aprendizaje automático no supervisado para agrupar conjuntos de datos en k grupos (o clusters). El objetivo es dividir los datos en grupos que sean lo más similares posible entre sí.
En el proceso de K-means, el analista debe especificar previamente el número de grupos (k) que se desea obtener. El algoritmo clasifica los objetos en diferentes grupos, de manera que los objetos dentro de un mismo grupo sean lo más parecidos entre sí.
4. 1 Ideas básicas de K-means
La idea básica detrás de K-means es minimizar la variación total dentro de cada grupo, también conocida como variación intra-cluster. Esto se logra mediante el cálculo de la suma de las distancias euclidianas al cuadrado entre los elementos y el centroide correspondiente.
4. 2 Algoritmo K-means
El algoritmo de K-means se ejecuta en varios pasos. En primer lugar, se seleccionan aleatoriamente k objetos del conjunto de datos para que actúen como los centroides iniciales de los grupos. Estos objetos también se llaman centros de cluster o centroides.
4. 3 Cálculo de la agrupación k-means en R
4. 3. 1 Data
Para calcular la agrupación de K-means en R, se utiliza el conjunto de datos “USArrests” como ejemplo. Antes de aplicar el algoritmo, es necesario preparar los datos asegurándose de que solo contengan variables continuas, ya que K-means utiliza promedios de variables. Además, para evitar la dependencia de una unidad de variable arbitraria, los datos se escalan utilizando la función “scale()” en R.
data("USArrests") # Loading the data set
df <- scale(USArrests) # Scaling the data
# View the firt 3 rows of the data
head(df, n = 3)## Murder Assault UrbanPop Rape
## Alabama 1.24256408 0.7828393 -0.5209066 -0.003416473
## Alaska 0.50786248 1.1068225 -1.2117642 2.484202941
## Arizona 0.07163341 1.4788032 0.9989801 1.0428783884. 3. 2 Paquetes y funciones de R necesarios
#kmeans(x, centers, iter.max = 10, nstart = 1)La función “kmeans()” se utiliza para realizar el algoritmo de K-means en R. A continuación, se proporciona una explicación más detallada de los parámetros de entrada:
“x”: Puede ser una matriz numérica, un marco de datos numérico o un vector numérico. Representa los datos que se utilizarán para el clustering.
“centros”: Puede ser el número de clusters (k) que se desea obtener o un conjunto de centroides iniciales distintos. Si se especifica un número, se selecciona un conjunto aleatorio de filas distintas de “x” como centroides iniciales.
“iter.max”: Es el número máximo de iteraciones permitidas para el algoritmo. Por defecto, su valor es 10, lo que significa que el algoritmo intentará encontrar los clusters óptimos en un máximo de 10 iteraciones.
“nstart”: Es el número de particiones iniciales aleatorias que se generan cuando “centros” es un número. Se recomienda utilizar un valor mayor que 1 para obtener una mejor estimación de los clusters.
Para crear un gráfico visualmente atractivo de los clusters generados con la función “kmeans()”, se puede utilizar el paquete “factoextra”. Es necesario instalar dicho paquete antes de utilizarlo en R.
library(ggplot2)library(factoextra)## Welcome! Want to learn more? See two factoextra-related books at https://goo.gl/ve3WBa4. 3. 3 Estimación del número óptimo de conglomerados
La tarea de determinar el número óptimo de clusters es crucial en el clustering de K-means. A continuación, se presenta una solución sencilla para estimar este número utilizando la función “fviz_nbclust()” en el paquete “factoextra” de R.
El paquete “factoextra” proporciona una solución práctica para estimar el número óptimo de clusters. La función “fviz_nbclust()” se utiliza para realizar este cálculo. Se ejecuta el algoritmo de K-means utilizando diferentes valores para el número de clusters, y luego se evalúa el rendimiento de cada configuración de clusters.
La función “fviz_nbclust()” genera una gráfica que muestra los valores de un criterio de selección, como el índice de silueta o el método de la suma de cuadrados internos (SSB/SSW), en función del número de clusters. El objetivo es encontrar el punto en la gráfica donde el criterio de selección alcanza su valor máximo o donde se produce un cambio significativo. Este punto indica el número óptimo de clusters para el conjunto de datos.
Al utilizar la función “fviz_nbclust()”, se puede obtener una estimación del número óptimo de clusters, lo que ayuda a tomar una decisión informada al especificar el valor de “k” en el algoritmo de K-means.
library(factoextra)
fviz_nbclust(df, kmeans, method = "wss") + geom_vline(xintercept = 4, linetype = 2)
El gráfico anterior muestra la varianza dentro de los clusters en función del número de clusters (k). A medida que aumenta el valor de k, la varianza dentro de los clusters tiende a disminuir. Sin embargo, se observa una curva o “codo” en k = 4.
Este “codo” en el gráfico indica que más allá de k = 4, agregar más clusters tiene poco valor adicional en términos de reducir la varianza dentro de los clusters. Por lo tanto, se sugiere que el número óptimo de clusters para este conjunto de datos es 4.
En la siguiente sección del análisis, procederemos a clasificar las observaciones en 4 clusters utilizando el algoritmo de K-means.
4. 3. 4 Cálculo de la agrupación k-means
Cuando realizamos el clustering de K-means, es importante tener en cuenta que el resultado final puede verse afectado por las asignaciones aleatorias de los centros iniciales de los clusters. Para abordar esta sensibilidad, podemos especificar el parámetro “nstart” con un valor más alto, como 25.
# Compute k-means with k = 4
set.seed(123)
km.res <- kmeans(df, 4, nstart = 25)Al establecer “nstart = 25”, R realizará 25 asignaciones de inicio aleatorias y luego seleccionará los resultados que correspondan a la asignación con la variación más baja dentro de los clusters. Normalmente, el valor predeterminado de “nstart” en R es 1, lo que significa que solo se realiza una asignación aleatoria inicial.
Sin embargo, se recomienda encarecidamente aumentar el valor de “nstart” a un número más grande, como 25 o 50, para obtener un resultado más estable y confiable del clustering de K-means. Esto ayuda a mitigar la influencia de las asignaciones iniciales aleatorias y proporciona una mejor estimación de los clusters óptimos.
# Print the results
print(km.res)## K-means clustering with 4 clusters of sizes 8, 13, 16, 13
##
## Cluster means:
## Murder Assault UrbanPop Rape
## 1 1.4118898 0.8743346 -0.8145211 0.01927104
## 2 -0.9615407 -1.1066010 -0.9301069 -0.96676331
## 3 -0.4894375 -0.3826001 0.5758298 -0.26165379
## 4 0.6950701 1.0394414 0.7226370 1.27693964
##
## Clustering vector:
## Alabama Alaska Arizona Arkansas California
## 1 4 4 1 4
## Colorado Connecticut Delaware Florida Georgia
## 4 3 3 4 1
## Hawaii Idaho Illinois Indiana Iowa
## 3 2 4 3 2
## Kansas Kentucky Louisiana Maine Maryland
## 3 2 1 2 4
## Massachusetts Michigan Minnesota Mississippi Missouri
## 3 4 2 1 4
## Montana Nebraska Nevada New Hampshire New Jersey
## 2 2 4 2 3
## New Mexico New York North Carolina North Dakota Ohio
## 4 4 1 2 3
## Oklahoma Oregon Pennsylvania Rhode Island South Carolina
## 3 3 3 3 1
## South Dakota Tennessee Texas Utah Vermont
## 2 1 4 3 2
## Virginia Washington West Virginia Wisconsin Wyoming
## 3 3 2 2 3
##
## Within cluster sum of squares by cluster:
## [1] 8.316061 11.952463 16.212213 19.922437
## (between_SS / total_SS = 71.2 %)
##
## Available components:
##
## [1] "cluster" "centers" "totss" "withinss" "tot.withinss"
## [6] "betweenss" "size" "iter" "ifault"La salida impresa proporciona información sobre los siguientes elementos de un análisis de clustering:
Medias o centros de los clusters: Se muestra una matriz en la cual cada fila representa un número de cluster (del 1 al 4) y cada columna representa una variable. Los valores en esta matriz son las medias de cada variable dentro de cada cluster.
Vector de clusterización: Se muestra un vector de enteros (del 1 al k) que indica a qué cluster se asigna cada punto. Cada punto en los datos originales es asignado a uno de los clusters representados por los números en este vector.
Además, es posible calcular la media de cada variable para cada cluster utilizando los datos originales.
aggregate(USArrests, by=list(cluster=km.res$cluster), mean)## cluster Murder Assault UrbanPop Rape
## 1 1 13.93750 243.62500 53.75000 21.41250
## 2 2 3.60000 78.53846 52.07692 12.17692
## 3 3 5.65625 138.87500 73.87500 18.78125
## 4 4 10.81538 257.38462 76.00000 33.19231dd <- cbind(USArrests, cluster = km.res$cluster)
head(dd)## Murder Assault UrbanPop Rape cluster
## Alabama 13.2 236 58 21.2 1
## Alaska 10.0 263 48 44.5 4
## Arizona 8.1 294 80 31.0 4
## Arkansas 8.8 190 50 19.5 1
## California 9.0 276 91 40.6 4
## Colorado 7.9 204 78 38.7 44. 3. 5. Acceso a los resultados de la función kmeans()
Cuando se utiliza la función kmeans(), se obtiene una lista de componentes que incluye los siguientes elementos:
Cluster: Es un vector de enteros (del 1 al k) que indica a qué cluster se asigna cada punto. Cada punto en los datos es asignado a uno de los clusters representados por los números en este vector.
centros: Es una matriz que contiene los centros de cada cluster, es decir, las medias de cada variable dentro de cada cluster.
Totss: Es la suma total de cuadrados (SST), que mide la varianza total de los datos. Representa la suma de las diferencias al cuadrado entre cada punto y la media global de todos los puntos.
Withinss: Es un vector que contiene la suma de cuadrados dentro de cada cluster. Cada componente del vector corresponde a un cluster y representa la suma de las diferencias al cuadrado entre cada punto del cluster y la media del cluster.
Tot.withinss: Es la suma total de cuadrados dentro de los clusters, es decir, la suma de todos los valores en el vector withinss.
Betweenss: Es la suma de cuadrados entre los clusters, es decir, la diferencia entre la suma total de cuadrados y la suma total de cuadrados dentro de los clusters (totss - tot.withinss).
Tamaño: Es un vector que contiene el número de observaciones en cada cluster.
Puedes acceder a estos componentes de la siguiente manera:
# Cluster number for each of the observations
km.res$cluster## Alabama Alaska Arizona Arkansas California
## 1 4 4 1 4
## Colorado Connecticut Delaware Florida Georgia
## 4 3 3 4 1
## Hawaii Idaho Illinois Indiana Iowa
## 3 2 4 3 2
## Kansas Kentucky Louisiana Maine Maryland
## 3 2 1 2 4
## Massachusetts Michigan Minnesota Mississippi Missouri
## 3 4 2 1 4
## Montana Nebraska Nevada New Hampshire New Jersey
## 2 2 4 2 3
## New Mexico New York North Carolina North Dakota Ohio
## 4 4 1 2 3
## Oklahoma Oregon Pennsylvania Rhode Island South Carolina
## 3 3 3 3 1
## South Dakota Tennessee Texas Utah Vermont
## 2 1 4 3 2
## Virginia Washington West Virginia Wisconsin Wyoming
## 3 3 2 2 3head(km.res$cluster, 4)## Alabama Alaska Arizona Arkansas
## 1 4 4 1# Cluster size
km.res$size## [1] 8 13 16 13# Cluster means
km.res$centers## Murder Assault UrbanPop Rape
## 1 1.4118898 0.8743346 -0.8145211 0.01927104
## 2 -0.9615407 -1.1066010 -0.9301069 -0.96676331
## 3 -0.4894375 -0.3826001 0.5758298 -0.26165379
## 4 0.6950701 1.0394414 0.7226370 1.276939644. 3. 6. Visualización de k-means clusters
Si deseas visualizar los datos en un diagrama de dispersión y colorear cada punto de datos en función de su asignación a un cluster, pero te enfrentas al desafío de tener más de dos variables, puedes utilizar una solución que consiste en reducir la dimensionalidad aplicando un algoritmo de reducción de la dimensionalidad, como el Análisis de Componentes Principales (ACP).
El ACP es un algoritmo que opera en las variables originales y produce nuevas variables, conocidas como componentes principales, que capturan la mayor variabilidad en los datos. Estas nuevas variables se pueden utilizar para construir el gráfico de dispersión en un espacio de dos dimensiones.
Al aplicar el ACP a tus datos, obtendrás dos nuevas variables que representan una combinación de las variables originales. Estas nuevas variables son elegidas de tal manera que la primera componente principal capture la mayor varianza posible en los datos, y la segunda componente principal capture la varianza restante más significativa. Al utilizar estas dos componentes principales como ejes x e y en el gráfico de dispersión, podrás visualizar la estructura de los datos y cómo se distribuyen los puntos de datos en relación con los clusters.
De esta manera, podrás evaluar la elección del número de clusters y comparar diferentes análisis de clustering utilizando la información visual proporcionada por el diagrama de dispersión.
fviz_cluster(km.res, data = df,
palette = c("#FF0000", "#0000FF", "#000000", "#C870FF"),
ellipse.type = "euclid", # Concentration ellipse
star.plot = TRUE, # Add segments from centroids to items
repel = TRUE, # Avoid label overplotting (slow)
ggtheme = theme_minimal())
4. 4. Ventajas y desventajas de la agrupación K-means
4. 4. 1 Ventajas:
- Es un algoritmo sencillo y rápido de implementar.
- Es eficaz en el manejo de grandes conjuntos de datos.
- Produce resultados fácilmente interpretables, ya que asigna cada punto a un cluster y proporciona los centros de cada cluster.
4. 4. 2 Desventajas
- Requiere que se especifique previamente el número de clusters, lo cual puede ser un desafío en algunos casos.
- Es sensible a los valores iniciales de los centros de los clusters, lo que puede llevar a diferentes resultados en cada ejecución.
- No es adecuado para datos que contienen grupos con formas irregulares o tamaños desiguales.
- No es robusto frente a la presencia de valores atípicos o datos ruidosos.
4. 5 Alternativa a la agrupación K-means
Una alternativa robusta a K-means es el algoritmo PAM (Partitioning Around Medoids), el cual se basa en medoides en lugar de centroides. En el siguiente capítulo se puede encontrar información sobre la agrupación PAM, y se puede utilizar la función pam() del paquete “cluster” para calcularla. Además, la función pamk() del paquete “fpc” es una envoltura para PAM que también sugiere automáticamente el número óptimo de clusters basándose en la anchura media óptima de la silueta.
Resumen
El clustering K-means es una técnica utilizada para clasificar observaciones en k grupos en función de su similitud. Cada grupo está representado por el valor medio de los puntos del grupo, conocido como centroide del cluster.
El algoritmo K-means requiere que los usuarios especifiquen previamente el número de clusters a generar. La función kmeans() del paquete “stats” se puede utilizar para calcular el algoritmo K-means. El formato simplificado para su uso es kmeans(x, centers), donde “x” son los datos y “centers” es el número de clusters que se desean obtener.