Agrupamiento jerárquico

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)

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.

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.

Datos sin procesar

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

Representación tradicional

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).

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

• Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). «14.3.12 Hierarchical clustering» (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.

• 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 4.0 Internacional.