Clustering Jerárquico en R
Miguel Ángel Jiménez Cuadrillero
9 de mayo de 2018
Cómo realizar una agrupación jerárquica usando R
¿Qué es la agrupación jerárquica?
La agrupación es una técnica para agrupar puntos de datos similares en un grupo y separar las diferentes observaciones en diferentes grupos o grupos. En Hierarchical Clustering, los clusters se crean de manera que tengan un orden predeterminado, es decir, una jerarquía. Por ejemplo, considere la jerarquía de conceptos de una biblioteca. Una biblioteca tiene muchas secciones, cada sección tendría muchos libros, y los libros se agruparían según su tema, digamos. Esto forma una jerarquía. En Hierarchical Clustering, esta jerarquía de clústeres puede crearse de arriba a abajo o viceversa. Por lo tanto, son dos tipos a saber: Divisivo y Aglomerativo. Discutamos en detalle.
Método divisivo
En el método Divisivo suponemos que todas las observaciones pertenecen a un único grupo y luego dividimos el clúster en dos grupos menos similares. Esto se repite recursivamente en cada grupo hasta que haya un grupo para cada observación. Esta técnica también se llama DIANA, que es un acrónimo de Análisis Divisivo.
Método aglomerativo
También se lo conoce como aglomeración aglomerativa jerárquica (HAC) o AGNES (acrónimo de aglomeración de anidación). En este método, cada observación se asigna a su propio clúster. Luego, se calcula la similitud (o distancia) entre cada uno de los clusters y los dos clusters más similares se fusionan en uno. Finalmente, los pasos 2 y 3 se repiten hasta que solo quede un grupo.
Tenga en cuenta que el método divisivo es bueno para identificar clusters grandes, mientras que el método aglomerativo es bueno para identificar clusters pequeños. Continuaremos con Agglomerative Clustering para el resto del artículo. Desde entonces, HAC representa la mayoría de los algoritmos de agrupación jerárquica, mientras que los métodos divisivos rara vez se utilizan. Creo que ahora tenemos una visión general de Agrupación jerárquica. También vamos a familiarizarnos con el algoritmo para ello.
Algoritmo HAC
Dado un conjunto de N elementos a agrupar, y una matriz de distancia NxN (o similitud), el proceso básico del agrupamiento jerárquico de Johnson (1967) es:
- Asigne cada elemento a su propio clúster, de modo que si tiene N elementos, ahora tiene N clusters, cada uno con un solo elemento. Deje que las distancias (similitudes) entre los conglomerados sean iguales a las distancias (similitudes) entre los elementos que contienen.
- Encuentre el par más cercano (más similar) de clústeres y combínelos en un único clúster, de modo que ahora tenga un clúster menos.
- Calcule distancias (similitudes) entre el nuevo clúster y cada uno de los clusters antiguos.
- Repita los pasos 2 y 3 hasta que todos los elementos estén agrupados en un solo grupo de tamaño N.
En los Pasos 2 y 3 de este documento, el algoritmo habla sobre la búsqueda de similitud entre los clusters. Entonces, antes de realizar cualquier agrupamiento, se requiere determinar la matriz de distancia que especifica la distancia entre cada punto de datos usando alguna función de distancia (Euclidiana, Manhattan, Minkowski, etc.). Luego, la matriz se actualiza para especificar la distancia entre los diferentes clústeres que se forman como resultado de la fusión. Pero, ¿cómo medimos la distancia (o similitud) entre dos grupos de observaciones? Para esto, tenemos tres métodos diferentes como se describe a continuación. Estos métodos difieren en cómo se mide la distancia entre cada grupo.
Enlace completo
Este método también se llama diámetro o método máximo. En este método, consideramos la similitud del par más lejano. Es decir, la distancia entre un clúster y otro clúster se considera igual a la distancia más larga desde cualquier miembro de un clúster a cualquier miembro del otro clúster. Tiende a producir clusters más compactos. Una desventaja de este método es que los valores atípicos pueden provocar la fusión de grupos cercanos más tarde de lo que es óptimo.
Enlace promedio
En el método de vinculación promedio, tomamos la distancia entre un clúster y otro clúster para que sea igual a la distancia promedio desde cualquier miembro de un clúster a cualquier miembro del otro clúster. Una variación en la agrupación de enlaces promedio es el método UCLUS de D’Andrade (1978) que utiliza la distancia media en lugar de la distancia media.
El método de Ward
El método de Ward apunta a minimizar la varianza total dentro del grupo. En cada paso, se fusionan el par de clústeres con una distancia mínima entre los clústeres. En otras palabras, forma grupos de una manera que minimiza la pérdida asociada con cada grupo. En cada paso, se considera la unión de cada par de clústeres posible y se combinan los dos clusters cuya fusión da como resultado un aumento mínimo en la pérdida de información. Aquí, Ward define la pérdida de información en términos de un criterio de suma de cuadrados de error (ESS). Si quieres un tratamiento matemático de esto, visita este enlace .
La siguiente tabla describe las ecuaciones matemáticas para cada uno de los métodos:
Dónde,
X1, X2, Xk = Observaciones del clúster 1
Y1, Y2,, Yl = Observaciones del grupo 2
d (x, y) = Distancia entre un sujeto con el vector de observación x y un sujeto con un vector de observación y
||. || = Norma euclidiana
Implementando agrupamiento jerárquico en R
Preparación de datos
Para realizar la agrupación en R, los datos deben prepararse de acuerdo con las siguientes pautas:
Las filas deben contener observaciones (o puntos de datos) y las columnas deben ser variables. Verifique si sus datos tienen valores faltantes, si es así, elimínelos o imputelos. Los datos en las columnas deben estar estandarizados o escalados, para que las variables sean comparables. Utilizaremos un conjunto de datos llamado ‘Freedman’ del paquete ‘automóvil’. El marco de datos ‘Freedman’ tiene 110 filas y 4 columnas. Las observaciones son áreas metropolitanas de EE. UU. Con poblaciones de 1968 de 250,000 o más. Hay algunos datos faltantes. (Asegúrese de instalar el paquete de automóvil antes de proceder)
library(cluster)
library(purrr)
data <- car::Freedman
#To remove any missing value that might be present in the data, type this:
data <- na.omit(data)Esto simplemente elimina cualquier fila que contenga valores perdidos. Puede usar métodos más sofisticados para imputar valores perdidos. Sin embargo, omitiremos esto ya que está más allá del alcance del artículo. Además, utilizaremos variables numéricas aquí para simplemente demostrar cómo se realiza la agrupación en R. Las variables categóricas, por otro lado, requerirían un tratamiento especial, que tampoco está dentro del alcance de este artículo. Por lo tanto, hemos seleccionado un conjunto de datos con variables numéricas solo para la concisión.
A continuación, tenemos que escalar todas las variables numéricas. Escala significa que cada variable ahora tendrá una media cero y una desviación estándar uno. Lo ideal es que quieras que una unidad en cada coordenada represente el mismo grado de diferencia. La escala hace que la desviación estándar sea la unidad de medida en cada coordenada. Esto se hace para evitar que el algoritmo de agrupamiento dependa de una unidad variable arbitraria. Puede escalar / estandarizar los datos usando la escala de función R:
data <- scale(data)Implementando agrupamiento jerárquico en R
Hay varias funciones disponibles en R para clústeres jerárquicos. Aquí hay algunos de uso común:
‘hclust’ (paquete de estadísticas) y ‘agnes’ (paquete de clúster) para la agrupación jerárquica aglomerativa ‘diana’ (paquete de clúster) para la agrupación jerárquica divisiva
Agrupamiento jerárquico aglomerativo
Para la función ‘hclust’, se requieren los valores de distancia que se pueden calcular en R utilizando la función ‘dist’. La medida predeterminada para la función dist es ‘Euclidiana’, sin embargo, puede cambiarla con el argumento del método. Con esto, también necesitamos especificar el método de vinculación que queremos usar (es decir, “completo”, “promedio”, “único”, “sala.D”).
# Dissimilarity matrix
d <- dist(data, method = "euclidean")
# Hierarchical clustering using Complete Linkage
hc1 <- hclust(d, method = "complete" )
# Plot the obtained dendrogram
plot(hc1, cex = 0.6, hang = -1)
Otra alternativa es la función agnes. Ambas funciones son bastante similares; sin embargo, con la función agnes también puede obtener el coeficiente de aglomeración, que mide la cantidad de estructura de agrupamiento encontrada (los valores más cercanos a 1 sugieren una estructura de agrupación fuerte).
# Compute with agnes (make sure you have the package cluster)
hc2 <- agnes(data, method = "complete")
# Agglomerative coefficient
hc2$ac## [1] 0.9317012## [1] 0.9317012
#Let’s compare the methods discussed
# vector of methods to compare
m <- c( "average", "single", "complete", "ward")
names(m) <- c( "average", "single", "complete", "ward")
# function to compute coefficient
ac <- function(x) {
agnes(data, method = x)$ac
}
map_dbl(m, ac) ## average single complete ward
## 0.9241325 0.9215283 0.9317012 0.9493598## from ‘purrr’ package
## average single complete ward
## 0.9241325 0.9215283 0.9317012 0.9493598
#Ward’s method gets us the highest agglomerative coefficient. Let us look at its dendogram.
hc3 <- agnes(data, method = "ward")
pltree(hc3, cex = 0.6, hang = -1, main = "Dendrogram of agnes")
Agrupamiento divisional jerárquico
La función ‘diana’ en el paquete de clúster nos ayuda a realizar agrupamientos jerárquicos divisivos. ‘diana’ funciona de manera similar a ‘agnes’. Sin embargo, no hay un argumento de método aquí, y, en lugar del coeficiente de aglomeración, tenemos un coeficiente de división.
# compute divisive hierarchical clustering
hc4 <- diana(data)
# Divise coefficient
hc4$dc## [1] 0.9305939## [1] 0.9305939
# plot dendrogram
pltree(hc4, cex = 0.6, hang = -1, main = "Dendrogram of diana")
Un dendograma es un árbol de clúster donde cada grupo está vinculado a dos o más grupos sucesores. Estos grupos están anidados y organizados como un árbol. Podrías administrar dendogramas y hacer mucho más con ellos usando el paquete “dendextend”. Mira la viñeta del paquete aquí:
https://cran.r-project.org/web/packages/dendextend/vignettes/Quick_Introduction.html
¡Estupendo! Entonces, ahora entendemos cómo realizar agrupamientos y proponer dendogramas. Pasemos al último paso de asignar clusters a los puntos de datos.
Esto se puede hacer con la función R cutree . Corta un árbol (o dendograma), como resultado de hclust (o diana / agnes), en varios grupos, ya sea especificando el número deseado de grupos (k) o la altura de corte (h). Se debe especificar al menos uno de k o h, k anula h si se dan ambos.
Siguiendo nuestra demostración, asigne clusters para el árbol obtenido por la función diana (en la sección Agrupamiento jerárquico divisional).
clust <- cutree(hc4, k = 5)También podemos usar la función fviz_cluster del paquete factoextra para visualizar el resultado en un diagrama de dispersión.
library(factoextra)## Loading required package: ggplot2## Welcome! Related Books: `Practical Guide To Cluster Analysis in R` at https://goo.gl/13EFCZfviz_cluster(list(data = data, cluster = clust)) ## from ‘factoextra’ package
También puede visualizar los clústeres dentro del dendograma colocando bordes como se muestra a continuación
pltree(hc4, hang=-1, cex = 0.6)
rect.hclust(hc4, k = 9, border = 2:10)
dendextend
Puede hacer muchas otras manipulaciones en dendrogramas con el paquete dendextend , como - cambiar el color de las etiquetas, cambiar el tamaño del texto de las etiquetas, cambiar el tipo de línea de ramas, sus colores, etc. También puede cambiar el texto de la etiqueta así como también ordenarlo. Puede ver las muchas opciones en la viñeta en línea del paquete.
Otra función importante que ofrece el paquete dendextend es el tanglegrama. Se usa para comparar dos dendrogramas (con el mismo conjunto de etiquetas), uno frente al otro y con sus etiquetas conectadas por líneas.
Como ejemplo, comparemos los métodos de vinculación único y completo para la función de Agnes.
library(“dendextend”)
hc_single <- agnes(data, method = “single”) hc_complete <- agnes(data, method = “complete”)
converting to dendogram objects as dendextend works with dendogram objects
hc_single <- as.dendrogram(hc_single) hc_complete <- as.dendrogram(hc_complete)
tanglegram(hc_single,hc_complete)
Esto es útil al comparar dos métodos. Como se ve en la figura, uno puede relacionarse con la metodología utilizada para construir los conglomerados al observar esta comparación. Puede encontrar más funcionalidades del paquete dendextend aquí .
Notas finales
Espero que comprendas mejor los algoritmos de agrupamiento que con los que comenzaste. Discutimos sobre las técnicas de agrupamiento divisional y de aglomeración y cuatro métodos de vinculación, a saber, el método individual, completo, promedio y de Ward. A continuación, implementamos las técnicas discutidas en R usando un conjunto de datos numéricos. Tenga en cuenta que no teníamos ninguna variable categórica en el conjunto de datos que utilizamos. Debe tratar las variables categóricas para incorporarlas a un algoritmo de agrupamiento. Por último, discutimos un par de diagramas para visualizar los grupos / grupos formados. Tenga en cuenta que se ha asumido que el valor de ‘k’ (número de clústeres) es conocido. Sin embargo, este no es siempre el caso. Hay una serie de heurísticas y reglas generales para elegir el número de clústeres. Una heurística dada funcionará mejor en algunos conjuntos de datos que otros. Lo mejor es aprovechar el conocimiento del dominio para ayudar a establecer la cantidad de clústeres, si es posible. De lo contrario, pruebe una variedad de heurísticas, y quizás algunos valores diferentes de k.