Agrupamiento jerárquico

En minería de datos, el agrupamiento jerárquico es un método de análisis de grupos puntuales, el cual busca construir una jerarquía de grupos. Estrategias para agrupamiento jerárquico generalmente caen en dos tipos:

• Aglomerativas: Este es un acercamiento ascendente: cada observación comienza en su propio grupo, y los pares de grupos son mezclados mientras uno sube en la jerarquía.
• Divisivas: Este es un acercamiento descendente: todas las observaciones comienzan en un grupo, y se realizan divisiones mientras uno baja en la jerarquía.

En general, las mezclas y divisiones son determinadas con un Algoritmo voraz. Los resultados del agrupamiento jerárquico son usualmente presentados en un dendrograma.

En el caso general, la complejidad del agrupamiento aglomerativo es ${\displaystyle {\mathcal {O}}(n^{3})}$, lo cual los hace demasiado lentos para grandes conjuntos de datos. El agrupamiento divisivo con búsqueda exhaustiva es ${\displaystyle {\mathcal {O}}(2^{n})}$ lo cual es aún peor. Sin embargo, para algunos casos especiales, óptimos y eficientes métodos aglomerativos (de complejidad ${\displaystyle {\mathcal {O}}(n^{2})}$) son conocidos: SLINK^[1]​ para agrupamiento de enlace-simple y CLINK^[2]​ para agrupamiento de enlace completo.

Disimilitud de grupo

En orden de decidir qué grupos deberían ser combinados (para aglomerativo), o cuando un grupo debería ser dividido (para divisivo), una medida de disimilitud entre conjuntos de observaciones es requerida. En la mayoría de los métodos de agrupamiento jerárquico, esto es logrado mediante uso de una métrica apropiada (una medida de distancia entre pares de observaciones), y un criterio de enlace el cual especifica la disimilitud de conjuntos como una función de las distancias dos a dos entre observaciones en los conjuntos.

Métrica

La elección de una métrica apropiada influenciará la forma de los grupos, ya que algunos pueden estar cerca unos de otros de acuerdo a una distancia y más lejos de acuerdo a otra. Por ejemplo, en un espacio 2-dimensional, la distancia entre el punto (1,0) y el origen (0,0) es siempre 1 de acuerdo a las normas usuales, pero la distancia entre el punto (1,1) y el origen (0,0) puede ser 2, ${\displaystyle \scriptstyle {\sqrt {2}}}$  o 1 bajo la distancia Manhattan, la distancia euclidiana o la distancia máxima respectivamente.

Algunas métricas comúnmente usadas para agrupamiento jerárquico son:^[3]​

Names	Formula
Distancia euclidiana	${\displaystyle \|a-b\|_{2}={\sqrt {\sum _{i}(a_{i}-b_{i})^{2}}}}$
Distancia euclidiana al cuadrado	${\displaystyle \|a-b\|_{2}^{2}=\sum _{i}(a_{i}-b_{i})^{2}}$
Distancia Manhattan	${\displaystyle \|a-b\|_{1}=\sum _{i}|a_{i}-b_{i}|}$
distancia máxima	${\displaystyle \|a-b\|_{\infty }=\max _{i}|a_{i}-b_{i}|}$
Distancia de Mahalanobis	${\displaystyle {\sqrt {(a-b)^{\top }S^{-1}(a-b)}}}$  donde S es la matriz de covarianza
Similitud coseno	${\displaystyle {\frac {a\cdot b}{\|a\|\|b\|}}}$

Para texto u otro dato no numérico, métricas como la Distancia de Hamming o la Distancia de Levenshtein son frecuentemente usadas.

Criterio de enlace

El criterio de enlace determina la distancia entre conjuntos de observaciones como una función de las distancias entre observaciones dos a dos. Algunos criterios de enlace entre dos conjuntos de observaciones A y B frecuentemente usados son:^[4]​^[5]​

Nombres	Fórmula
Agrupamiento de máximo o completo enlace	${\displaystyle \max \,\{\,d(a,b):a\in A,\,b\in B\,\}.}$
Agrupamiento de mínimo o simple enlace	${\displaystyle \min \,\{\,d(a,b):a\in A,\,b\in B\,\}.}$
Agrupamiento de enlace media o promedio, o UPGMA	${\displaystyle {\frac {1}{|A||B|}}\sum _{a\in A}\sum _{b\in B}d(a,b).}$
Agrupamiento de mínima energía	${\displaystyle {\frac {2}{nm}}\sum _{i,j=1}^{n,m}\|a_{i}-b_{j}\|_{2}-{\frac {1}{n^{2}}}\sum _{i,j=1}^{n}\|a_{i}-a_{j}\|_{2}-{\frac {1}{m^{2}}}\sum _{i,j=1}^{m}\|b_{i}-b_{j}\|_{2}}$

Donde d es la métrica escogida. Otros criterios de enlace incluye:

• La suma de todas las varianzas intragrupo.
• El decrecimiento en la varianza para los grupos que están siendo mezclados (criterio de Ward).
• La probabilidad de que grupos candidatos se produzcan desde la misma función de distribución.(V-enlace)

Discusión

El agrupamiento jerárquico tiene la ventaja distintiva de que cualquier medida de distancia puede ser usada. De hecho, las observaciones de por si no son requeridas: todo lo que se usa es una matriz de distancia.

Ejemplo para agrupamiento aglomerativo

Por ejemplo, suponga que estos datos van a ser agrupados, y que la distancia euclidiana será la métrica de distancia.

Cortar el árbol a una altura determinada dará un grupo particionante de una precisión seleccionada. En este ejemplo, cortar después de la segunda fila dará como resultado los grupos {a} {b c} {d e} {f}. Cortar después de la tercera fila dará como resultado los grupos {a} {b c} {d e f}, el cual es un agrupamiento ‘tosco’, con un número menor de grupos mayores.

 

El dendrograma del agrupamiento jerárquico sería como este:

 

Este método construye la jerarquía desde los elementos individuales mediante progresivamente ir mezclando grupos. En nuestro ejemplo, tenemos seis elementos {a} {b} {c} {d} {e} y {f}. El primer paso es determinar cuales elementos mezclar en un grupo. Usualmente, queremos tomar los dos elementos más cercanos, de acuerdo a una distancia escogida.

Opcionalmente, uno solo puede construir una matriz de distancias a este nivel, donde el número en la i-ésima fila j-ésima columna es la distancia entre los i-ésimo y j-ésimo elementos. Entonces, a medida que el agrupamiento progresa, filas y columnas son mezcladas como también son mezclados los grupos y las distancias actualizadas. Esta es una forma común de implementar este tipo de agrupamiento y tiene el beneficio de almacenar las distancias entre grupos. Un algoritmo de agrupamiento aglomerativo simple es descrito en la página agrupamiento de enlace simple; puede ser fácilmente adaptado a diferentes tipos de enlace (ver abajo).

Suponga que hemos mezclado los dos elementos más cercanos b y c, ahora tenemos los siguientes grupos {a}, {b, c}, {d}, {e} y {f}, y queremos mezclarlos más adelante. Para hacerlo, necesitamos tomar la distancia entre {a} y {b c}, y por tanto definir la distancia entre dos grupos.

Usualmente la distancia entre dos grupos ${\displaystyle {\mathcal {A}}}$  and ${\displaystyle {\mathcal {B}}}$  es una de los siguientes:

• • La distancia máxima entre elementos de cada grupo (también llamada agrupamiento de enlace completo):

${\displaystyle \max\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$ 

• • La distancia mínima entre elementos de cada grupo (también llamada agrupamiento de enlace simple):

${\displaystyle \min\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$ 

• • La distancia media entre elementos de cada grupo (también llamada agrupamiento de enlace promedio, usado e.g. en UPGMA):

${\displaystyle {1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y).}$ 

• La suma de todas las varianzas intra-grupo..
• El aumento en la varianza de los grupos que están siendo mezclados (método de Ward).
• La probabilidad de que grupos candidatos sean producidos desde la misma función de distribución (enlace-V).

Cada aglomeración ocurre a una mayor distancia entre grupos que la aglomeración anterior, y no puede decidir parar de agrupar ya sea cuando los grupos están muy lejos para ser mezclados (criterio de distancia) o cuando hay un suficientemente pequeño número de grupos (criterio de número).

Software

Libre

• R tiene varias funciones de agrupamiento jerárquico.^[6]​
• Orange, una suite software gratis de minería de datos, módulo orngClustering para hacer scripts en Python, o análisis de grupo a través de visual programming.^[7]​
• hcluster es software Python, basado en NumPy, el cual soporta agrupamiento jerárquico y plotting.
• Cluster 3.0 provee una agradable GUI para acceder a diferentes rutinas de agrupamiento y está disponible para Windows, Mac OS X, Linux, Unix. ^[8]​
• ELKI incluye múltiples algoritmos de agrupamiento jerárquico.
• figue Un paquete JavaScript que implementa algunas funciones de agrupamiento aglomerativo (enlace simple, enlace completo, enlace promedio) y funciones para visualizar resultados de agrupamientos (e.g. dendrogramas)
• MultiDendrograms Una aplicación open source en Java para agrupamiento jerárquico aglomerativo de grupos variables, con GUI.^[9]​
• CrimeStat implementa dos rutinas de agrupamiento jerárquico, una de vecino más cercano (Nnh) y una de riesgo-ajustado (Rnnh).
• Complete C# DEMO implementado como proyecto de Visual Studio que incluye procesado real de archivos de texto, construcción de matrices documento-término con filtrado de stopwords y stemming. El mismo sitio ofrece comparación con otros algoritmos.
• HAC C# es una implementación de un algoritmo de agrupamiento aglomerativo que usa enlace-simple.

Comercial

• Software for analyzing multivariate data with instant response using Hierarchical clustering
• SAS

Véase también

• Análisis de grupos
• Dendrograma
• Taxonomía numérica

Referencias

1. R. Sibson (1973). «SLINK: an optimally efficient algorithm for the single-link cluster method». The Computer Journal (British Computer Society) 16 (1): 30-34. 
2. D. Defays (1977). «An efficient algorithm for a complete link method». The Computer Journal (British Computer Society) 20 (4): 364-366. 
3. «The DISTANCE Procedure: Proximity Measures». SAS/STAT 9.2 Users Guide. SAS Institute. Consultado el 26 de abril de 2009. 
4. «The CLUSTER Procedure: Clustering Methods». SAS/STAT 9.2 Users Guide. SAS Institute. Consultado el 26 de abril de 2009. 
5. Székely, G. J. and Rizzo, M. L. (2005) Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method, Journal of Classification 22, 151-183.
6. Gruen, Friedrich Leisch and Bettina (3 de mayo de 2017). CRAN Task View: Cluster Analysis & Finite Mixture Models. Consultado el 6 de julio de 2017. 
7. http://www.ailab.si/orange/screenshots.psp (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
8. «Open source Clustering software». bonsai.hgc.jp. Consultado el 6 de julio de 2017. 
9. «Sergio Gómez - DEIM - URV». deim.urv.cat. Consultado el 6 de julio de 2017. 

Bibliografía

• Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). (PDF). The Elements of Statistical Learning (2nd edición). Nueva York: Springer. pp. 520-528. ISBN 0-387-84857-6. Archivado desde el original el 10 de noviembre de 2009. Consultado el 20 de octubre de 2009. 
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). «Section 16.4. Hierarchical Clustering by Phylogenetic Trees». Numerical Recipes: The Art of Scientific Computing (3rd edición). New York: Cambridge University Press. ISBN 978-0-521-88068-8. 

Enlaces externos

• Esta obra contiene una traducción derivada de «Hierarchical clustering» de Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.

•   Datos: Q1277447
•   Multimedia: Hierarchical clustering