Capítulo 4 K-Means Clustering
Marcela Díaz
2023-05-10
K-Means Clustering
La agrupación K-means es un algoritmo de aprendizaje automático no supervisado utilizado para dividir un conjunto de datos en un número predefinido de grupos, llamados clusters. El objetivo es clasificar los objetos en clusters de manera que los objetos dentro de un mismo cluster sean similares entre sí y diferentes de los objetos en otros clusters. En el algoritmo, cada cluster se representa por su centroide, que es la media de los puntos asignados a ese cluster. K-means es ampliamente utilizado en diversas aplicaciones de análisis de datos.
La idea básica de la agrupación de k-means consiste en definir clústeres de modo que se minimice la variación total intraclúster (conocida como variación total dentro del clúster).
K-means algorithm
El algoritmo de K-means puede ser explicado de la siguiente manera:
Especificar el número de clusters (K) a crear.
Seleccionar aleatoriamente k objetos del conjunto de datos como centros o medias iniciales de los clusters.
Asigna cada observación a su centroide más cercano, en función de la distancia entre el objeto y el centroide
Para cada uno de los k clusters actualiza el centroide del cluster calculando los nuevos valores medios de todos los puntos de datos del cluster. El centroide de un cluster K es un vector de longitud p que contiene las medias de todas las variables para las observaciones en el cluster ke; p es el número de variables.
Repetitivamente minimizar el total dentro de la suma de cuadrados. Es decir, repita los pasos 3 y 4 hasta que las asignaciones de cluster dejen de cambiar o se alcance el número máximo de repeticiones. Por defecto, el software R utiliza 10 como valor por defecto para el número máximo de repeticiones.
Computing k-means clustering in R
Data
Utilizaremos el conjunto de datos de demostración “USArrests”. Los datos deben contener sólo variables continuas, ya que el algoritmo k-means utiliza medias variables. Como no queremos que el algoritmo k-means dependa de una unidad de variable arbitraria, empezamos escalando los datos usando la función de R scale() como sigue:
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.042878388library(factoextra)## Warning: package 'factoextra' was built under R version 4.2.3## Loading required package: ggplot2## Welcome! Want to learn more? See two factoextra-related books at https://goo.gl/ve3WBaEstimating the optimal number of clusters
El clustering de k-means requiere que los usuarios especifiquen el número de clusters que deben generarse. Para saber el número de clusters que deben generarse se ofrece una solución sencilla. La idea es calcular la agrupación k-means utilizando diferentes valores de conglomerados k. A continuación, se traza el WSS en función del número de conglomeradosEl WSS es la suma de las distancias entre los puntos y sus centros correspondientes para cada cluster. La ubicación de una curva (rodilla) en el trazado se considera generalmente un indicador del número adecuado de conglomerados. La función de R fuiz_nbclust() proporciona una solución conveniente para estimar el número óptimo de conglomerados.
library(factoextra)
fviz_nbclust(df, kmeans, method = "wss") + geom_vline(xintercept = 4, linetype = 2)
Compuing k-means clustering
Como el algoritmo de agrupamiento k-means comienza con k centroides seleccionados aleatoriamente, siempre se recomienda utilizar la función set.seed() con el objetivo de hacer reproducibles los resultados, de forma que el lector de este artículo obtenga exactamente los mismos resultados que los que se muestran a continuación.
El código R que se muestra a continuación realiza la agrupación k-means con k = 4:
# Compute k-means with k = 4
set.seed(123)
km.res <- kmeans(df, 4, nstart = 25)Como el resultado final del agrupamiento k-means es sensible a las asignaciones aleatorias de inicio, especificamos nstart = 25. Esto significa que R probará 25 asignaciones aleatorias de inicio diferentes y luego seleccionará el mejor resultado correspondiente a la que tenga la menor variación dentro del cluster. El valor por defecto de nstart en R es uno. Pero siempre se recomienda calcular el agrupamiento de k-means con un valor grande de nstart, como 25 o 50, para obtener un resultado más estable.
# 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 muestra - los centros de los clusters: una matriz, cuyas filas son el número de cluster (1 a 4) y las columnas son variables. - el vector de clusterización: Un vector de enteros (de 1:k) que indica el cluster al que se asigna cada punto.
Es posible calcular el centro de cada variable por conglomerados 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.19231Tambièn se pueden añadir las clasificaciones de puntos a los datos originales:
dd <- 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 4Accesing to the results of k-means() function
La función kmeans() devuelve una lista de componentes, incluyendo:
- Cluster: Un vector de enteros (de 1:k) que indica el cluster al que se asigna cada punto
- Centros: Una matriz de centros de conglomerados.
- TSS: La suma total de cuadrados (TSS). TSS mide la varianza total de los datos.
- Withinss: Vector de la suma de cuadrados dentro del cluster.
- tot.withinss: Suma total de cuadrados dentro del grupo, es decir, sum(withinss)
- Betweenss: La suma de cuadrados entre conglomerados.
- Tamaño: El número de observaciones en cada conglomerado.
Se puede 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.27693964Visualizing k-means clusters
Es una buena idea representar gráficamente los resultados de los conglomerados. Estos pueden utilizarse para evaluar la elección del número de conglomerados, así como para comparar dos análisis de conglomerados diferentes. Ahora, queremos visualizar los datos en un diagrama de dispersión con el color de cada punto de datos en función de su asignación a un conglomerado.
El problema es que los datos contienen más de 2 variables y la cuestión es qué variables elegir para el gráfico de dispersión xy.
Una solución es reducir el número de dimensiones aplicando un algoritmo de reducción de dimensionalidad, como el Análisis de Componentes Principales (ACP), que opera sobre las cuatro variables y produce dos nuevas variables (que representan las variables originales) que se pueden utilizar para hacer el gráfico.
La función fuiz_cluster() puede utilizarse para visualizar fácilmente los clusters de k-means. Toma como argumentos los resultados de k-means y los datos originales. En el gráfico resultante, las observaciones se representan por puntos, utilizando componentes principales si el número de variables es superior a 2. También es posible dibujar una elipse de concentración alrededor de cada cluster.
fviz_cluster(km.res, data = df,
palette = c("#2E9FDF", "#00AFBB", "#E7B800", "#FC4E07"),
ellipse.type = "euclid", # Concentration ellipse
star.plot = TRUE, # Add segments from centroids to items
repel = TRUE, # Avoid label overplotting (slow)
ggtheme = theme_minimal())