Iniciaremos revisando uno de los métodos de clasificación no supervisada más conocidos y empleados, el algoritmo k-means clustering. Este algoritmo de clasificación no supervisada o segmentación de tipo particional, es decir, que genera una estructura plana. El algoritmo está basado en la partición de un conjunto de \(n\) observaciones en \(k\) grupos en el que cada observación pertenece al grupo cuya distancia es menor.
Algunas consideraciones importantes respecto al algoritmo \(k-means\) (o \(k\)-medias) son:
El número de grupos o clústeres, denotado como \(k\), debe definirse antes de ejecutar el algoritmo.
Cada grupo o clúster está definido por un punto, generalmente identificado como el centro y llamado semilla o centroide del clúster, aunque puede recibir otros nombres en implementaciones concretas del algoritmo.
A grandes rasgos, el algoritmo funciona en dos fases principales, que corresponden a las dos tareas siguientes:
En primer lugar, la fase de inicialización, identifica \(k\) puntos como centroides iniciales. Aunque no es necesario que sean puntos del conjunto de datos, sí es importante que sean puntos dentro del mismo intervalo.
La segunda fase es iterativa, y consiste en
Estos dos pasos se repiten hasta que se satisface alguna condición de parar.
\(\underline{\hspace{15cm}}\)
Algoritmo \(k\)-medias: Pseudocódigo del algoritmo k-means.
\(\overline{\hspace{15cm}}\)
Entrada: \(D\) (conjunto de datos) y \(k\) (número de clústeres)
Inicializar los clústeres vacíos \(P = \{p_1, p_2,\dots,p_k\}\)
Seleccionar los centroides iniciales \(c_1,c_2,\dots,c_k\)
mientras (Condición de parada no satisfecha) hacer
para todo \(d_i \in D\) hacer
Asignar \(d_i\) al clúster \(p_j\), cuando \(d(d_i;c_j)\) es mínima
fin
para todo \(p_i\) P hacer
Recalcular \(c_i\) según los valores \(d_i \in p_i\)
fin
devolver El conjunto de clústeres \(P\).
\(\overline{\hspace{15cm}}\)
De los pasos anteriores se desprenden cuatro criterios importantes para definir el comportamiento del algoritmo:
¿Cómo podemos inicializar los centroides?
¿Cómo podemos calcular la distancia entre cada punto \(d_i\) y los centroides?
¿Cómo podemos recalcular los centroides a partir de las instancias que forman su grupo o partición?
¿Cómo podemos establecer la condición de parada del algoritmo?
Un primer enfoque, simple y ampliamente usado, consiste en inicializar los centroides con \(k\) puntos aleatorios del conjunto de datos. Una de las principales consecuencias derivadas de este tipo de inicialización de centroides es que implica que el proceso de clustering será no determinista. Es decir, diferentes ejecuciones del algoritmo pueden conducir a diferentes modelos y, lógicamente, a diferentes niveles de calidad del resultado.
Esta característica, que en principio podría parecer un inconveniente importante, puede ser superada gracias a la simplicidad y efectividad del método, que permite ejecutar el algoritmo múltiples veces con distintos centroides y escoger el mejor resultado.
El algoritmo \(k-means\) utiliza la inicialización de centroides aleatoria, pero existen otras aproximaciones más complejas que son utilizadas por métodos derivados del \(k-means\). Por ejemplo, se pueden seleccionar los centroides iniciales a partir de la distribución de probabilidades de las instancias de \(D\), intentando cubrir todo el rango de valores de los datos, especialmente las zonas con mayor concentración de instancias.
El algoritmo \(k-means\), generalmente, utiliza la distancia euclídeana. Aun así, es posible utilizar algún otro tipo de métrica de similitud vistas en la sección anterior.
El valor de cada centroide es calculado como la media de todos los puntos que pertenecen a este segmento (de aquí el nombre del algoritmo, \(k-means\)). Por lo tanto, este algoritmo solo es aplicable a atributos continuos. En caso de tener atributos no continuos en el conjunto de datos, deberemos aplicar una transformación previa.
La convergencia del algoritmo es la condición de parada natural y última. Esta se alcanza cuando no hay cambios en el recálculo de los centroides durante una iteración completa, provocando que no haya alteraciones en la distribución de las instancias en las distintas particiones o clústeres. Es decir, se llega a una situación de estabilidad en la distribución de las instancias. Esta condición se puede garantizar después de un número finito de iteraciones, dependiendo de la métrica empleada en el cálculo de la distancia y el recálculo de los centroides.
En la práctica, no es necesario que el método converja, y generalmente es suficiente cuando se tiene pequeños cambios en la pertenencia de las instancias en los distintos grupos o particiones, es decir, cuando estamos próximos a una situación de convergencia.
Una de las principales características de \(k-means\) es que se le deben indicar el número de particiones o clústeres a identificar. Aunque esto le permite mantener un nivel de simplicidad y eficiencia elevados, puede ser considerado un inconveniente importante. Identificar el número correcto de particiones \(k\) no es una tarea elemental, e incluso en muchas ocasiones se puede extraer directamente del conocimiento del dominio. Aun así, en muchos casos el rango de valores de \(k\) a no es muy grande, con lo cual se pueden probar diferentes valores y seleccionar el que proporcione mejores resultados.
Un criterio es minimizar la suma de residuos cuadrados, es decir, la suma de las distancias de cualquier vector o instancia a su centroide más cercano. Este criterio busca la creación de segmentos lo más compactos posibles. Otro criterio podría ser el de maximizar la suma de distancias entre segmentos, por ejemplo entre sus centros. En este caso estaríamos priorizando tener segmentos los más alejados posible entre sí, es decir, tener segmentos lo más diferenciados posible.
Como sucede en muchos problemas de maximización o minimización, es fácil intuir que el algoritmo no siempre alcanzará un óptimo global, puede darse el caso de que antes encuentre un óptimo local. Además, también es posible que el algoritmo no sea capaz de encontrar ningún óptimo, bien porque simplemente el juego de datos no presente ninguna estructura de segmentos, bien porque no se haya escogido correctamente el número \(k\) de segmentos a construir.
Los criterios anteriores (minimización de distancias intragrupo o maximización de distancias intergrupo) pueden usarse para establecer un valor adecuado para el parámetro \(k\). Valores \(k\) para los que ya no se consiguen mejoras significativas en la homogeneidad interna de los segmentos o la heterogeneidad entre segmentos distintos, deberían descartarse.
Otra aproximación para solucionar este problema consiste en permitir que el número \(k\) se modifique durante la ejecución del algoritmo. En este caso, se inicia el algoritmo con un valor proporcionado de \(k\), pero este se puede modificar (incrementar o disminuir) según ciertos criterios. Por ejemplo:
Si existen dos particiones con los centros muy juntos, quizás es mejor unir ambas particiones y reducir el número de particiones.
Si existe una partición con un nivel de diversidad muy elevado, se puede dividir esta en dos nuevas particiones, incrementando por tanto el valor de \(k\).
El uso de la distancia media para el cálculo de los centroides proporciona un modelo simple y eficiente, y además proporciona unos resultados muy fácilmente interpretables. Aun así, tiene sus limitaciones. Por ejemplo, cuando los datos están distribuidos de forma asimétrica y contienen valores extremos (outliers) en algunos atributos.
El algoritmo \(k\)-mediana (\(k-medians\)) es una variación del método anterior, donde se sustituye el cálculo basado en el valor medio, por el valor de la mediana. Aunque la obtención del valor de la mediana requiere mayor complejidad computacional, es preferible en determinados contextos.
Al igual que en el caso del \(k-means\), este método puede implementarse mediante distintas métricas de similaridad, aunque existe el riesgo de perder la garantía de convergencia. Una de las métricas de distancia más empleadas en este algoritmo es la distancia de Manhattan vista en la sección anterior.
El método \(k-medians\) presenta mejores resultados que el \(k-means\) cuando las distribuciones son asimétricas o existen valores outliers. Aun así, \(k-medians\) no garantiza que los centros sean similares a alguna instancia del conjunto de datos. Esto se debe a que, a menos que los atributos sean independientes, los vectores de atributos medianos pueden no parecerse a ninguna instancia existente del conjunto de datos ni del dominio completo.
El algoritmo \(k-medoids\) propone el recálculo de los centros a partir de instancias que presentan un valor de disimilitud mínimo respecto a las demás instancias de la partición o clúster. La identificación de estos puntos, conocidos como medoides, es computacionalmente más costosa que las aproximaciones vistas anteriormente.
Aunque esta aproximación sea considerablemente más costosa, a nivel de cálculo, que \(k-means\) o \(k-medians\), es preferible en algunos dominios donde puede ser interesante que los puntos de centro sean puntos del conjunto de datos. Además, este método es particularmente robusto al ruido y a los valores outliers.
Como ejemplo práctico en R, realizaremos algunos ejemplos de \(k\)-medias.
Como primer ejemplo, utilizaremos un conjunto de datos bidimensionales generado de manera artificial, con el fin de ilustrar de la mejor manera el funcionamiento de los modelos de agrupamiento.
library(mvtnorm)
# Generamos los datos
set.seed(198)
s1 <- matrix(c(1,.2,0.2,1), ncol=2)
x1 <- rmvnorm(n = 50, mean = c(2, 3),s1)
s2 <- matrix(c(1,0,0,2), ncol=2)
x2 <- rmvnorm(n = 50, mean = c(3, 9),s2)
s3 <- matrix(c(2,0.5,0.5,1.5), ncol=2)
x3 <- rmvnorm(n = 100, mean = c(10, 5),s3)
s4 <- matrix(c(3,0.8,0.8,1.5), ncol=2)
x4 <- rmvnorm(n = 100, mean = c(12, 10),s4)
s5 <- matrix(c(2,0.7,0.7,1.5), ncol=2)
x5 <- rmvnorm(n = 80, mean = c(5, 5),s5)
s6 <- matrix(c(1,0.5,0.5,1), ncol=2)
x6 <- rmvnorm(n = 100, mean = c(2, 12),s5)
x <- c(x1[,1],x2[,1],x3[,1],x4[,1],x5[,1],x6[,1])
y <- c(x1[,2],x2[,2],x3[,2],x4[,2],x5[,2],x6[,2])
dataset <-data.frame(cbind(x,y))
summary(dataset)
## x y
## Min. :-1.413 Min. : 0.7024
## 1st Qu.: 2.558 1st Qu.: 4.6474
## Median : 5.131 Median : 7.7828
## Mean : 6.391 Mean : 7.6652
## 3rd Qu.:10.442 3rd Qu.:10.6938
## Max. :16.919 Max. :14.6760
# Gráfica de los datos
library(ggplot2)
## Warning in as.POSIXlt.POSIXct(Sys.time()): unable to identify current timezone 'H':
## please set environment variable 'TZ'
ggplot() + geom_point(aes(x = x, y = y), data = dataset, alpha = 0.5) + ggtitle('Conjunto de Datos')
Como puede verse con claridad, en el conjunto de datos existen unos 2 a 6 grupos que se distribuyen en zonas particulares del rango de valores de las variables. El objetivo de los modelos de particionamiento será entonces identificar de manera precisa tales grupos y, sobre todo, las fronteras de cada uno, de manera que cada observación pueda ser asociada a una clase específica.
La función kmeans() del paquete stats
realiza K-means clustering. Entre sus argumentos destacan: centers
, que determina el número \(k\) de clusters que se van a generar, iter.max
, el número de iteraciones que se realizarán y nstart
, el número de veces que se va a repetir el proceso, cada vez con una asignación aleatoria inicial distinta. Es recomendable que este último valor sea alto, mayor a 25, para no obtener resultados malos debido a una iniciación poco afortunada del proceso.
Como los datos se han simulado sin considerar que todas las dimensiones tengan la misma magnitud, es necesario escalarlos.
data <-data.frame(scale(dataset))
ggplot() + geom_point(aes(x = x, y = y), data = data, alpha = 0.5) + ggtitle('Conjunto de Datos')
La cantidad óptima de centroides \(k\) a utilizar no necesariamente se conoce de antemano, por lo que es necesario aplicar una técnica conocida como el Método del Codo a fin de determinar dicho valor. Básicamente, este método busca seleccionar la cantidad ideal de grupos a partir de la optimización de la WSS (Total Within Sum of Square).
El paquete factoextra
contiene funciones que facilitan en gran medida la visualización y evaluación de los resultados de clustering. Por lo tanto, una forma sencilla de estimar el número \(k\) óptimo de clusters cuando no se dispone de información adicional en la que basarse, es aplicar el algoritmo de \(K\)-medias para un rango de valores de \(K\) e identificar aquel valor a partir del cual la reducción en la suma total de varianza entre cluster deja de ser sustancial. A esta estrategia se la conoce como método del codo. La función fviz_nbclust() automatiza este proceso y genera una representación de los resultados.
library(factoextra)
## Welcome! Want to learn more? See two factoextra-related books at https://goo.gl/ve3WBa
fviz_nbclust(data,kmeans, method = "wss",k.max=10,
diss = get_dist(data, method = "euclidean"), nstart = 50)+
labs(title= "Número optimo de cluster") +
xlab("k ") +
ylab("Suma de cuadrados internos")
A partir de la curva obtenida podemos ver cómo a medida que se aumenta la cantidad de centroides, el valor de WSS disminuye de tal forma que la gráfica adopta una forma de codo. Para seleccionar el valor óptimo de \(k\), se escoje entonces ese punto en donde ya no se dejan de producir variaciones importantes del valor de WSS al aumentar \(k\). En este caso, vemos que esto se produce a partir de \(k \geq 4\), por lo que evaluaremos los resultados del agrupamiento, por ejemplo, con los valores de 4, 5 6 y 7 a fin de observar el comportamiento del modelo.
Finalmente, podemos aplicar el algoritmo con la cantidad de \(k\) seleccionada:
set.seed(198)
kmedias <- kmeans(data[, c("x", "y")], iter.max = 1000, centers = 4, nstart = 50)
kmedias
## K-means clustering with 4 clusters of sizes 141, 137, 100, 102
##
## Cluster means:
## x y
## 1 -0.9326317 1.0255692
## 2 -0.6221428 -0.9935929
## 3 1.2965366 0.7063628
## 4 0.8537350 -0.7756794
##
## Clustering vector:
## [1] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [38] 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 2 2 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 2 1 1
## [75] 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 2 4 4 4 4 2 4 4 4 4 4 4
## [112] 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 2
## [149] 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 4 4 4 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
## [186] 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
## [223] 3 3 3 3 3 3 3 3 3 3 3 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
## [260] 3 3 3 3 3 3 3 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
## [297] 3 3 3 3 2 2 2 2 2 4 2 2 2 2 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 2 2 2
## [334] 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 2 2 2
## [371] 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [408] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [445] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##
## Within cluster sum of squares by cluster:
## [1] 45.38700 48.44790 26.20865 25.02331
## (between_SS / total_SS = 84.9 %)
##
## Available components:
##
## [1] "cluster" "centers" "totss" "withinss" "tot.withinss"
## [6] "betweenss" "size" "iter" "ifault"
El objeto devuelto por la función kmeans() contiene entre otros datos: la media de cada una de las variables para cada cluster (centers
), un vector indicando a que cluster se ha asignado cada observación (cluster
), la suma de cuadrados interna de cada cluster (withinss
) y la suma total de cuadrados internos de todos los clusters (tot.withinss
). Al imprimir el resultado también se muestra el cociente de la suma de cuadrados entre clusters entre la suma de cuadrados totales. Este cociente es equivalente al \(R^2\) de los modelos de regresión, que indica el porcentaje de varianza explicada por el modelo respecto al total de varianza observada. Puede utilizarse para evaluar el clustering obtenido pero, al igual que ocurre con \(R^2\) al incrementar el número de predictores, el cociente between_SS / total_SS aumenta con el número de clusters creados. Esto último se debe de tener en cuenta para evitar problemas de sobreajuste.
Veamos el resultado del agrupamiento:
data$cluster <- kmedias$cluster
ggplot() + geom_point(aes(x = x, y = y, color = cluster), data = data, size = 2) +
scale_colour_gradientn(colours=rainbow(4)) +
geom_point(aes(x = kmedias$centers[, 1], y = kmedias$centers[, 2]), color = 'black', size = 3) +
ggtitle('Clusters de Datos con k = 4') +
xlab('X') + ylab('Y')
En la gráfica se representa cada cluster con un color diferente, y además se muestra la posición de cada centroide en negro.
Al validar con \(k = 5,6\) y \(7\) tenemos:
set.seed(198)
kmedias <- kmeans(data, 5, iter.max = 1000, nstart = 50)
dataset$cluster <- kmedias$cluster
ggplot() + geom_point(aes(x = x, y = y, color = cluster), data = data, size = 2) +
scale_colour_gradientn(colours=rainbow(5)) +
geom_point(aes(x = kmedias$centers[, 1], y = kmedias$centers[, 2]), color = 'black', size = 3) +
ggtitle('Clusters de Datos con k = 5') +
xlab('X') + ylab('Y')
set.seed(198)
kmedias <- kmeans(data, 6, iter.max = 1000, nstart = 50)
dataset$cluster <- kmedias$cluster
ggplot() + geom_point(aes(x = x, y = y, color = cluster), data = data, size = 2) +
scale_colour_gradientn(colours=rainbow(6)) +
geom_point(aes(x = kmedias$centers[, 1], y = kmedias$centers[, 2]), color = 'black', size = 3) +
ggtitle('Clusters de Datos con k = 6') +
xlab('X') + ylab('Y')
set.seed(198)
kmedias <- kmeans(data, 7, iter.max = 1000, nstart = 50)
dataset$cluster <- kmedias$cluster
ggplot() + geom_point(aes(x = x, y = y, color = cluster), data = data, size = 2) +
scale_colour_gradientn(colours=rainbow(7)) +
geom_point(aes(x = kmedias$centers[, 1], y = kmedias$centers[, 2]), color = 'black', size = 3) +
ggtitle('Clusters de Datos con k = 7') +
xlab('X') + ylab('Y')
Al incrementar el valor de \(k\) tendremos entonces agrupamientos que recogen partes específicas de los datos de entrada, incluso llegando a dividir en dos grupos distintos a lo que inicialmente parece ser un solo grupo, como es el caso de los datos presentes en la parte superior derecha derecha de la gráfica cuando \(k = 7\). Así, vemos cómo el algoritmo de \(K\)-Medias es capas de producir de manera natural estos agrupamientos a partir de las semejanzas de los datos, y dichas clases generadas de hecho concuerdan con la intuición propia al observar los datos de entrada.
Si no deseas hacer este análisis exploratorio del número óptimo de cluster y prefieres buscar un método que te diga exactamente el valor óptimo de \(k\), se puede utilizr el método silhouette, el cual trabaja de forma similar que WSS, pero ahora busca es el máximo entre el ancho medio entre grupos. Lo interesante de este método es que si te da un valor exacto de \(k\). Pero es muy importante resaltar que sigue siendo un método de ajuste, y solo será bastante exacto cuando los grupos esten bastante alejados uno del otro, de lo contrario te dará un valor óptimo más pequeño de lo ideal. Esto se pude hacer con el siguiente código.
fviz_nbclust(data, kmeans, method = "silhouette",k.max = 10,
diss = get_dist(data, method = "euclidean"), nstart = 50)+
labs(title= "Número optimo de cluster") +
xlab("k ") +
ylab("Ancho medio entre grupos")
Concluyendo que debemos quedarnos con \(k=4\) grupos y la clasificación óptima de nuestros datos por este método sería:
set.seed(198)
kmedias <- kmeans(data, 4, iter.max = 1000, nstart = 50)
data$cluster <- kmedias$cluster
ggplot() + geom_point(aes(x = x, y = y, color = cluster), data = data, size = 2) +
scale_colour_gradientn(colours=rainbow(4)) +
geom_point(aes(x = kmedias$centers[, 1], y = kmedias$centers[, 2]), color = 'black', size = 3) +
ggtitle('Clasificación óptima') +
xlab('X') + ylab('Y')
El set de datos USArrests contiene información sobre el número de delitos (asaltos, asesinatos y secuestros) junto con el porcentaje de población urbana para cada uno de los 50 estados de USA. Se pretende estudiar si existe una agrupación subyacente de los estados empleando \(k\)-medias.
data("USArrests")
head(USArrests)
## Murder Assault UrbanPop Rape
## Alabama 13.2 236 58 21.2
## Alaska 10.0 263 48 44.5
## Arizona 8.1 294 80 31.0
## Arkansas 8.8 190 50 19.5
## California 9.0 276 91 40.6
## Colorado 7.9 204 78 38.7
Como la magnitud de los valores difiere notablemente entre variables, se procede a escalarlas.
datos <- scale(USArrests)
Ahora busquemos el número óptimo de cluster.
fviz_nbclust(datos, kmeans, method = "wss", k.max = 10,
diss = get_dist(datos, method = "euclidean"), nstart = 50)+
labs(title= "Número optimo de cluster") +
xlab("k ") +
ylab("Suma de cuadrados internos")
fviz_nbclust(datos, kmeans, method = "silhouette",k.max = 10,
diss = get_dist(datos, method = "euclidean"), nstart = 50)+
labs(title= "Número optimo de cluster") +
xlab("k ") +
ylab("Ancho medio entre grupos")
En este análisis, por el método WSS, observamos que a partir de 4 clusters la reducción en la suma total de cuadrados internos parece estabilizarse, indicando que \(K = 4\) es una buena opción, pero por el método silhouette nos indica un óptimo en \(k=2\), el cual quizás puede ser muy conservador.
El paquete factoextra
también permite obtener visualizaciones de las agrupaciones resultantes. Si el número de variables (dimensionalidad) es mayor de 2, automáticamente realiza un PCA y representa las dos primeras componentes principales.
set.seed(123)
km_clusters <- kmeans(datos, centers = 4, nstart = 50)
fviz_cluster(object = km_clusters, data = datos, show.clust.cent = TRUE,
ellipse.type = "euclid", star.plot = TRUE, repel = TRUE) +
labs(title = "Resultados con k=4 óptimo del método WSS") +
theme_bw() +
theme(legend.position = "none")
set.seed(123)
km_clusters <- kmeans(datos, centers = 2, nstart = 50)
fviz_cluster(object = km_clusters, data = datos, show.clust.cent = TRUE,
ellipse.type = "euclid", star.plot = TRUE, repel = TRUE) +
labs(title = "Resultados con k=2 óptimo del método silhouette") +
theme_bw() +
theme(legend.position = "none")
Para funciones prácticas y esto ya es apreciación personal, considero que \(k=4\) es un valor óptimo más recomendable para esta base de datos.