Cluster jerárquico
Jairo A. Ayala Godoy
Introducción
La palabra jerárquico se refiere a la construcción de jerarquías que este algoritmo crea para determinar los clusters. El algoritmo crea un listado de combinaciones posibles de acuedo a la jerarquía de las distancias entre puntos.
La idea de este procedimiento es construir una jerarquía de particiones del conjunto de casos y escoger la que mejor se ajuste. Supongamos que \(\{C_1,C_2,\dots,Cr\}\) es una partición del conjunto de observaciones. Dada esta partición, podemos calcular la matriz de dimensión \(r \times r\), en donde la posición \((i,j)\) guardará la distancia entre el conjunto \(C_i\) y \(C_j\), según alguna de las medidas de proximidad.
Algoritmo
En los siguientes pasos podemos resumir el trabajo que se realiza:
Paso 0: suponemos grupos unitarios formados por cada una de las observaciones. Esto es, \(C_i = \{i\}\) con \(i = 1,\dots,n\). En un principio, cada dato es un grupo.
Paso 1: calculamos la distancia entre los conjuntos de la partición, (para la primera iteración, sería calcular la distancia entre las observaciones).
Paso 2: agrupamos los dos conjuntos más cercanos y dejamos los demás conjuntos igual. Por lo tanto, tenemos ahora \(C_k\) grupos, con \(k<n\).
Paso 3: regresamos al paso 1 e iniciamos una nueva iteración.
Paso 4: si se logra obtener un solo conjunto en la partición paramos el procedimiento.
Para entender mejor el algoritmo, desarrollaremos paso a paso el proceso con un ejemplo inventado de datos.
Ejemplo paso a paso
Supongamos que tenemos una base de datos compuesta por 12 observaciones. en este paso 0, suponemos que cada observación es un grupo.
Para el paso 1, el algoritmo busca los dos puntos que esten cercanos, y los agrupa. Luego busca otros dos puntos con la menor distancia y pregunta: ¿la distancia entre estos dos nuevos puntos es menor que la distancia de estos puntos al grupo creado antes? Si la respuesta es sí los agrupa, sino agrupa el punto más cercano al primer grupo creado.
Notemos que los puntos 1 y 2 tienen la jerarquía más baja dado que tienen la distancia más corta. Luego el algoritmo busca por los siguientes dos puntos más cercanos (el punto 9 y el 12) y al comparar con el punto medio del 1 y 2 opta por crear un nuevo grupo con una jerarquía ligeramente más alta y así sucesivamente. Pero notemos que los puntos 7 y 11 no logran formar un grupo.
Sin embargo, ahora que tenemos el punto 7 y 11, calculamos su distancia y resulta que esa distancia no es la menor comparado a las distancias con los otros grupos existentes. Por ejemplo, el 7 está más cerca al punto medio del 1 y 2, y el 11 está más cerca al punto medio del 5 y 6. Así, el algoritmo crea una jerarquía más alta para esta agrupación.
El algoritmo continua hasta que finalmente crea un grupo que contempla a todos como la jerarquía más alta. En el siguiente gráfico no solo podemos apreciar ello sino también en el eje \(y\) la distancia entre cada punto o grupo de puntos.
Esta representación gráfica es muy utilizada para describir los resultados de un cluster jerárquico, denominada: dendograma , un dendograma muestra a qué valor de la medida de proximidad se produce la unión de los grupos y simultáneamente qué grupos se van uniendo.
También nos permite una valoración rápida de cuántos grupos puede haber en la base de datos. Simplemente trazando una linea horizontal a la altura que consideremos. Por ejemplo, para dos grupos, podemos trazar a la altura del valor 40.
si deseamos tener más grupos, podemos ahora pensar en hacer una línea horizontal a una distancia más baja, por ejemplo en 28 y ahora tendremos tres grupos.
Ahora tenemos tres clúster y así podríamos ir continuando hasta obtener los clústers que deseemos. Vale la pena resaltar que este modelo nos permite hacer cortes no solo por distancias sino también indicando cuántos clúster queremos y existen mecanismos automáticos para elegir este número de clúster óptimo.
Ejemplos en R
Ejemplo 1:
Para este primer ejemplo, generaremos tres conjuntos de datos normales multivariados.
# Datos simulados
library(mvtnorm)
set.seed(1234)
x1 <- rmvnorm(n = 10, mean = c(1, 1))
x2 <- rmvnorm(n = 10, mean = c(3.5, 4))
x3 <- rmvnorm(n = 10, mean = c(6, 5.5))
x <- rbind(x1,x2,x3)
gr <- gl(3,10,labels = c("x1","x2","x3"))
id <- as.numeric(gr)
plot(x,col=id,xlab=" ",ylab=" ",cex=1.2,pch=19)
Recordemos que un primer paso muy importante, antes de iniciar el
proceso es, escalar todas las variables numéricas. Escalar significa que
cada variable ahora tendrá una media cero y una desviación estándar uno.
Puede estandarizar los datos usando la función
scale de R:
dat <- scale(x)
plot(dat,col=id,xlab=" ",ylab=" ",cex=1.2,pch=19)
Hay varias funciones disponibles en R para realizar
Cluster jerárquicos. Trabajaremos con la librería que más se usa
regularmente, esta es:
hclust() .
Para
hclust() , se requiere ingresa la
matriz de distancias entre las observaciones. Estas se pueden calcular
mediante la función
dist() . El método predeterminado
es la distancia Euclidiana, sin embargo, hay otros métodos
programados. Por otra parte, también se necesita especificar el método
para calcular la distancia entre grupos (es decir,
“simple”,“completo”,“promedio”).
distancia <- dist(dat, method = "euclidean")
modelo <- hclust(distancia, method = "complete" )Una vez creado nuestro modelo, podemos visualizarlo utilizando la librería dendextend.
library(dendextend)
dend_modelo <- as.dendrogram(modelo)
plot(dend_modelo)
Hasta ahora solo hemos hecho la jerarquía, pero lo que nos interesa
es la agrupación. La agrupación se realiza por la distancia calculada
(parámetro h). Probemos con una distancia de 2. Usaremos
las funciones
color_branches y color_labels para
hacer visible los cambios.
corte <- 2
dend_modelo %>%
color_branches(h = corte) %>%
color_labels(h = corte) %>%
plot() %>%
abline(h = corte, lty = 2)
Este modelo nos permite hacer cortes no solo por distancias sino
también indicando cuántos clúster queremos, parámetro
k.
clusters_deseados <- 3
dend_modelo %>%
color_branches(k = clusters_deseados) %>%
color_labels(k = clusters_deseados) %>%
plot()
Otra alternativa de visualización, es dibujar rectángulos en los grupos.
plot(dend_modelo)
rect.hclust(modelo, k = clusters_deseados ,
border = 2:4)
Para determinar el número óptimo de clúster, en R,
tenemos la función
fviz_nbclust() de la librería factoextra.
library(factoextra)
fviz_nbclust(dat, FUN = hcut, method = "silhouette")
Aquí podemos conluir que para un valor de \(k=2\) tendremos el mejor promedio, con lo que éste se convierte en nuestro número de grupos óptimo. Aunque, vale la pena resaltar que estos datos fueron inventados pensando en tener tres grupos diferentes, pero al parecer el método encuentra que hay dos grupos bastante similares como para suponerlos como un sólo grupo. Esta última librería, también tiene una forma de gráficar los dendogramas, la cual los separa por colores y se les puede adicionar los rectángulos. Además, agregue el parámetro de horizontal, este se le puede agregar a cualquiera de las gráficas anteriores.
fviz_dend(modelo, k = 2, rect = TRUE,horiz = TRUE)
Ejemplo 2:
Para este segundo ejemplo, trabajaremos la base de datos USArrests , la cual contiene estadísticas de arrestos en los diferentes estados.
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.7Recordemos que debemos escalar los datos antes de hacer cualquier proceso.
data.scaled <- scale(x = USArrests,
center = TRUE,
scale = TRUE)
head(data.scaled)## 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.042878388
## Arkansas 0.23234938 0.2308680 -1.0735927 -0.184916602
## California 0.27826823 1.2628144 1.7589234 2.067820292
## Colorado 0.02571456 0.3988593 0.8608085 1.864967207Calculemos la matriz de distancias y veamos una forma de visualizarla.
dist <- dist(data.scaled,method = "euclidean")
# matriz de distancias
dist_mat <- as.matrix(round(dist,3))
as.dist(dist_mat[1:6,1:6])## Alabama Alaska Arizona Arkansas California
## Alaska 2.704
## Arizona 2.294 2.701
## Arkansas 1.290 2.826 2.718
## California 3.263 3.013 1.310 3.764
## Colorado 2.651 2.327 1.365 2.831 1.288Calculamos el número óptimo de clúster. Esta tarea la vamos a realizar por varios métodos para ejemplificar, pero en el próximo tema se explicará a detalle como funciona cada método.
fviz_nbclust(data.scaled, FUN = hcut, method = "silhouette")
Aquí, encontramos que el número óptimo de clúster sería \(k=2\). Vale la pena resaltar que además del
método de silueta, existen otros métodos ya programados en
R. Por ejemplo, si se usa el método wss ,
buscamos el número que consideremos estabiliza la suma de los cuadrados.
Este método siempre permite un número grande de clúster.
fviz_nbclust(data.scaled, FUN = hcut, method = "wss")
Por ejemplo, para estos datos, podríamos pensar en quedarnos con \(k=4\), ya que después de eso el cambio es mínimo.
También se podría usar el método
gap_stat . Este método igual que
con silueta automaticamente te da el valor óptimo.
fviz_nbclust(data.scaled, FUN = hcut, method = "gap_stat")
Entonces, por este método tendriamos que \(k=3\). En conclusión, es un tema de investigación aún y puede suceder como es este caso, donde para los mismos datos, los diferentes métodos no logran encontrar un único valor.
Calculamos ahora el modelo.
modelo2 <- hclust(dist, method = "complete")Veamos ahora, que podemos personalizar el dendograma de muchas formas.
fviz_dend(modelo2, cex = 0.8, lwd = 0.8, k = 4,
# Seleccionando manualmente los colores
k_colors = c("red", "green3", "blue", "magenta"),
rect = TRUE,
rect_border = "gray",
rect_fill = FALSE)
fviz_dend(modelo2, cex = 0.8, lwd = 0.8, k = 4,
# JCO fill color for rectangles
k_colors = c("jco"),
rect = TRUE,
rect_border = "jco",
rect_fill = TRUE)
# mejorando el tamaño de letra
fviz_dend(modelo2, cex = 0.5, k=4,
rect = TRUE,
k_colors = "jco",
rect_border = "jco",
rect_fill = TRUE,
horiz = TRUE)
# Agregando tema
fviz_dend(modelo2, cex = 0.5, k=4,
rect = TRUE,
k_colors = "jco",
rect_border = "jco",
rect_fill = TRUE,
horiz = TRUE,
ggtheme = theme_bw())
Tambien se puede cambiar el tipo de dendograma.
# filogenetico
fviz_dend(modelo2, cex = 0.5, k = 4,
rect = TRUE,
k_colors = "jco",
rect_border = "jco",
rect_fill = TRUE,
type = "phylogenic")
# circular
fviz_dend(modelo2, cex = 0.5, k = 4,
rect = TRUE,
k_colors = "jco",
rect_border = "jco",
rect_fill = TRUE,
type = "circular")
Finalmente, si ya estamos convencidos con la clasificación brindada, debemos agregar la nueva columna de clasificación a la base de datos.
grupos<-cutree(modelo2, k=4)
table(grupos)## grupos
## 1 2 3 4
## 8 11 21 10grupos_paises <- cbind(USArrests,grupos)
print(grupos_paises)## Murder Assault UrbanPop Rape grupos
## Alabama 13.2 236 58 21.2 1
## Alaska 10.0 263 48 44.5 1
## Arizona 8.1 294 80 31.0 2
## Arkansas 8.8 190 50 19.5 3
## California 9.0 276 91 40.6 2
## Colorado 7.9 204 78 38.7 2
## Connecticut 3.3 110 77 11.1 3
## Delaware 5.9 238 72 15.8 3
## Florida 15.4 335 80 31.9 2
## Georgia 17.4 211 60 25.8 1
## Hawaii 5.3 46 83 20.2 3
## Idaho 2.6 120 54 14.2 4
## Illinois 10.4 249 83 24.0 2
## Indiana 7.2 113 65 21.0 3
## Iowa 2.2 56 57 11.3 4
## Kansas 6.0 115 66 18.0 3
## Kentucky 9.7 109 52 16.3 3
## Louisiana 15.4 249 66 22.2 1
## Maine 2.1 83 51 7.8 4
## Maryland 11.3 300 67 27.8 2
## Massachusetts 4.4 149 85 16.3 3
## Michigan 12.1 255 74 35.1 2
## Minnesota 2.7 72 66 14.9 3
## Mississippi 16.1 259 44 17.1 1
## Missouri 9.0 178 70 28.2 3
## Montana 6.0 109 53 16.4 4
## Nebraska 4.3 102 62 16.5 4
## Nevada 12.2 252 81 46.0 2
## New Hampshire 2.1 57 56 9.5 4
## New Jersey 7.4 159 89 18.8 3
## New Mexico 11.4 285 70 32.1 2
## New York 11.1 254 86 26.1 2
## North Carolina 13.0 337 45 16.1 1
## North Dakota 0.8 45 44 7.3 4
## Ohio 7.3 120 75 21.4 3
## Oklahoma 6.6 151 68 20.0 3
## Oregon 4.9 159 67 29.3 3
## Pennsylvania 6.3 106 72 14.9 3
## Rhode Island 3.4 174 87 8.3 3
## South Carolina 14.4 279 48 22.5 1
## South Dakota 3.8 86 45 12.8 4
## Tennessee 13.2 188 59 26.9 1
## Texas 12.7 201 80 25.5 2
## Utah 3.2 120 80 22.9 3
## Vermont 2.2 48 32 11.2 4
## Virginia 8.5 156 63 20.7 3
## Washington 4.0 145 73 26.2 3
## West Virginia 5.7 81 39 9.3 4
## Wisconsin 2.6 53 66 10.8 3
## Wyoming 6.8 161 60 15.6 3