Introducción

En esta sesión práctica de programación en R, realizaremos una introducción breve a dos de los modelos de agrupamiento o clustering más conocidos en el Machine Learning, como lo son el algoritmo de K-Medios o K-means, y el Agrupamiento Jerárquico o Hierarchical Clustering. Estos son consideramos modelos de clasificación no supervisados ya que (a diferencia de los modelos supervisados en donde los datos de entrada tienen tanto componentes o variables como etiquetas que los identifican cada uno a una clase particular) en este caso no se conoce de antemano las clases a la que pertenecen los datos, sino que es trabajo del modelo encontrar semejanzas entre ellos y así agruparlos o clasificarlos según las características intrínsecas de sus variables. A lo largo de la práctica, estudiaremos el cómo se implementan estos modelos en R, y analizaremos los resultados de clasificación a partir de un conjunto de datos artificiales generados para el caso.

Conjunto de Datos

A efectos de esta práctica, haremos uso de un conjunto de datos bidimensionales generado de manera artificial (obtenido en el siguiente link) con el fin de ilustrar de la mejor manera el funcionamiento de los modelos de agrupamiento. En este sentido, carguemos los datos, conozcamos su estructura y visualicemos los mismos:

setwd('D:/ProgramasR/Practicas/ModelosClustering')
dataset <- read.csv('AggregationClusters.csv')
str(dataset)
## 'data.frame':    788 obs. of  2 variables:
##  $ X: num  15.6 14.9 14.4 14.2 13.8 ...
##  $ Y: num  28.6 27.6 28.4 28.8 28.1 ...
summary(dataset)
##        X               Y         
##  Min.   : 3.35   Min.   : 1.950  
##  1st Qu.:11.15   1st Qu.: 7.037  
##  Median :18.23   Median :11.725  
##  Mean   :19.57   Mean   :14.172  
##  3rd Qu.:30.70   3rd Qu.:21.962  
##  Max.   :36.55   Max.   :29.150

Como podemos ver a partir de la información del dataset, el mismo está compuesto por 788 observaciones de 2 variables que abarcan un amplio rango numérico. Ya que se trata de un conjunto bidimensional, podemos graficar los datos en un scatterplot a fin de observar su distribución de manera más clara. Para ello, haremos uso de la librería ggplot2:

library(ggplot2)
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 5 a 7 grupos que se distribuyen en zonas particulares del rango de valores de las variables. El objetivo de los modelos de agrupamiento 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. Construyamos entonces nuestros modelos de agrupamiento.

Agrupamiento por K-Medios (K-Means Clustering)

El método de K-Medios basa su funcionamiento en agrupar los datos de entrada en un total de k conjuntos definidos por un centroide, cuya distancia con los puntos que pertenecen a cada uno de los datos es la menor posible. En términos generales, el algoritmo puede resumirse como:

  1. Definir un total de k centroides al azar.
  2. Calcular las distancias de cada uno de los puntos de entrada a los k centroides, y asignar cada punto al centroide cuya distancia sea menor.
  3. Actualizar la posición de los k centroides, calculando la posición promedio de todos los puntos que pertenecen a cada clase.
  4. Repetir los pasos 2 y 3 hasta que los centroides no cambien de posición y, por lo tanto, las asignaciones de puntos entre clases no cambie.

Sin embargo, 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 o Elbow Method 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 WCSS (Within Clusters Summed Squares).

Por otro lado, ya que los centroides iniciales se generan al azar, pueden obtenerse resultados distintos en cada corrida del algoritmo, e incluso debido a las ubicaciones iniciales de los centroides, obtenerse al final soluciones que son mínimos locales en vez del global real del conjunto de datos. Para solventar este problema, se propuso el algoritmo de k-means++ a fin de escoger los centroides iniciales que garantizaran la convergencia adecuada del modelo.

Entonces, a fin de implementar el modelo de K-Medios, comencemos por determinar la cantidad óptima de centroides a utilizar a partir del Método del Codo. Para ello, aplicaremos la función kmeans al conjunto de datos, variando en cada caso el valor de k, y acumulando los valores de WCSS obtenidos:

set.seed(1234)
wcss <- vector()
for(i in 1:20){
  wcss[i] <- sum(kmeans(dataset, i)$withinss)
}

Una vez calculados los valores de WCSS en función de la cantidad de centroides k, vamos a graficar los resultados:

ggplot() + geom_point(aes(x = 1:20, y = wcss), color = 'blue') + 
  geom_line(aes(x = 1:20, y = wcss), color = 'blue') + 
  ggtitle("Método del Codo") + 
  xlab('Cantidad de Centroides k') + 
  ylab('WCSS')

A partir de la curva obtenida podemos ver cómo a medida que se aumenta la cantidad de centroides, el valor de WCSS 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 WCSS al aumentar k. En este caso, vemos que esto se produce a partir de k >= 7, por lo que evaluaremos los resultados del agrupamiento, por ejemplo, con los valores de 7, 8 y 9 a fin de observar el comportamiento del modelo.

Finalmente, podemos aplicar el algoritmo con la cantidad de k seleccionada:

set.seed(1234)
kmeans <- kmeans(dataset, 7, iter.max = 1000, nstart = 10)

En donde iter.max son el máximo de iteraciones a aplicar al algoritmo, y nstart es la cantidad de conjuntos de centroides que emplea internamente el mismo para ejecutar sus cálculos.

Veamos el resultado del agrupamiento:

dataset$cluster <- kmeans$cluster
ggplot() + geom_point(aes(x = X, y = Y, color = cluster), data = dataset, size = 2) +
  scale_colour_gradientn(colours=rainbow(4)) +
  geom_point(aes(x = kmeans$centers[, 1], y = kmeans$centers[, 2]), color = 'black', size = 3) + 
  ggtitle('Clusters de Datos con k = 7 / K-Medios') + 
  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.

Como puede verse, con k = 7 el modelo asigna clases consistentes a los datos de entrada, en especial al observar los agrupamientos que existen en toda la zona superior y derecha de la gráfica en donde los grupos son evidentes. Mientras tanto, los datos del grupo inferior izquierdo son agrupados en 3 clases distintas pero se observa que la distribución de puntos es adecuada para cada grupo.

Al validar con k = 8 y 9 tenemos:

set.seed(1234)
kmeans <- kmeans(dataset, 8, iter.max = 1000, nstart = 10)
dataset$cluster <- kmeans$cluster
ggplot() + geom_point(aes(x = X, y = Y, color = cluster), data = dataset, size = 2) +
  scale_colour_gradientn(colours=rainbow(4)) +
  geom_point(aes(x = kmeans$centers[, 1], y = kmeans$centers[, 2]), color = 'black', size = 3) + 
  ggtitle('Clusters de Datos con k = 8 / K-Medios') + 
  xlab('X') + ylab('Y')

set.seed(1234)
kmeans <- kmeans(dataset, 9, iter.max = 1000, nstart = 10)
dataset$cluster <- kmeans$cluster
ggplot() + geom_point(aes(x = X, y = Y, color = cluster), data = dataset, size = 2) +
  scale_colour_gradientn(colours=rainbow(4)) +
  geom_point(aes(x = kmeans$centers[, 1], y = kmeans$centers[, 2]), color = 'black', size = 3) + 
  ggtitle('Clusters de Datos con k = 9 / K-Medios') + 
  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 izquierda de la gráfica cuando k = 9. Así, vemos cómo el algoritmo de K-Medios 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.

Agrupamiento Jerárquico (Hierarchical Clustering)

El Agrupamiento Jerárquico es un método de agrupamiento que basa su funcionamiento en encontrar jerarquías en los datos de entrada a partir de generar grupos basados en la cercanía o semejanza de tales datos. En el caso aglomerativo, se empiezan calculando los puntos de los datos de entrada que estén más cercanos y se crea un grupo entre ellos. Luego se calculan los siguientes pares más cercanos y de manera ascendente se van generando grupos de clases que, de manera visual podrán observarse a partir de la construcción de un Dendrograma. Las clases, entonces, estarán definidas por la cantidad de líneas verticales del dendrograma (como veremos más adelante), y la selección del número de clases óptima para el conjunto de datos se podrá estimar de este mismo diagrama.

Así, para implementar el agrupamiento jerárquico en R y construir el dendrograma, se hace uso de la función hclust. Además, usaremos la función ggdendrogram del paquete ggdendro para visualizar el dendrograma:

library(ggdendro)
dendrogram <- hclust(dist(dataset, method = 'euclidean'), method = 'ward.D')
ggdendrogram(dendrogram, rotate = FALSE, labels = FALSE, theme_dendro = TRUE) + 
  labs(title = "Dendrograma")

En el eje horizontal del dendrograma tenemos cada uno de los datos que componen el conjunto de entrada, mientras que en el eje vertical se representa la distancia euclídea que existe entre cada grupo a medida que éstos se van jerarquizando. Cada línea vertical del diagrama representa un agrupamiento que coincide con los puntos arropados por ésta, y como se ve en el dendrograma, estos van formándose progresivamente hasta tener un solo gran grupo determinado por la línea horizontal superior. Así, al ir descendiendo en la jerarquía, vemos que de un solo grupo pasamos a 2, luego a 3, luego a 6, y así sucesivamente. Una manera de determinar entonces la cantidad de clases adecuadas es cortando el dendrograma a aquella altura del diagrama que mejor representa los datos de entrada.

Así, para nuestros datos, veamos los resultados para k = 3, 4, 6 y 7. A fin de obtener los resultados del agrupamiento, se hace uso de la función cutree, incorporando como parámetro tanto el modelo de agrupamiento como la cantidad de clases k:

agrupamientoJ <- hclust(dist(dataset, method = 'euclidean'), method = 'ward.D')
clases_aj <- cutree(agrupamientoJ, k = 3)
dataset$cluster <- clases_aj
ggplot() + geom_point(aes(x = X, y = Y, color = cluster), data = dataset, size = 2) +
  scale_colour_gradientn(colours=rainbow(4)) +
  ggtitle('Clusters de Datos con k = 3 / Agrupamiento Jerárquico') + 
  xlab('X') + ylab('Y')

En el caso de k = 3, se observa que el algoritmo seleccionó de una manera adecuada los 3 grandes grupos generales que presenta el conjunto de datos. Ahora bien, en los otros casos:

clases_aj <- cutree(agrupamientoJ, k = 4)
dataset$cluster <- clases_aj
ggplot() + geom_point(aes(x = X, y = Y, color = cluster), data = dataset, size = 2) +
  scale_colour_gradientn(colours=rainbow(4)) +
  ggtitle('Clusters de Datos con k = 4 / Agrupamiento Jerárquico') + 
  xlab('X') + ylab('Y')

clases_aj <- cutree(agrupamientoJ, k = 6)
dataset$cluster <- clases_aj
ggplot() + geom_point(aes(x = X, y = Y, color = cluster), data = dataset, size = 2) +
  scale_colour_gradientn(colours=rainbow(4)) +
  ggtitle('Clusters de Datos con k = 6 / Agrupamiento Jerárquico') + 
  xlab('X') + ylab('Y')

clases_aj <- cutree(agrupamientoJ, k = 7)
dataset$cluster <- clases_aj
ggplot() + geom_point(aes(x = X, y = Y, color = cluster), data = dataset, size = 2) +
  scale_colour_gradientn(colours=rainbow(4)) +
  ggtitle('Clusters de Datos con k = 7 / Agrupamiento Jerárquico') + 
  xlab('X') + ylab('Y')

En efecto, vemos que al igual que el caso de K-Medios, progresivamente se van obteniendo agrupamientos que separan las clases visibles en el conjunto de datos de una manera adecuada, hasta producir divisiones de agrupamientos como en la estructura inferior de la gráfica. De cualquier modo, resulta claro que aún cuando el algoritmo no tiene información previa de etiquetas o clases predefinidas de los datos, este puede encontrar las clases naturales que existen en los datos a partir de las simulitudes entre ellos.

Conclusiones

En esta sencilla práctica de R vimos cómo es posible implementar tanto el método de agrupamiento por K-Medios como el Agrupamiento Jerárquico en un conjunto de datos bidimensionales, y cómo estos algoritmos son capaces entonces de encontrar las semejanzas intrínsecas de los datos y producir clases que, en efecto, reproducen lo que puede observarse de manera intuitiva a partir de la gráfica de los datos. Por supuesto, estos métodos y análisis son aplicables a conjuntos de datos con más dimensiones, solo que su visualización resultaría imposible. Sin embargo, en general puede trabajarse con conjuntos de datos de múltiples componentes y del mismo modo podrán obtenerse clases que agrupen los datos y, por lo tanto, sirvan como método de clasificación no supervisado cuando no se tiene información de etiquetas o clases previa de los datos.

Así, terminamos esta sesión práctica.