clustering - ¿Cómo compara la "similitud" entre dos dendrogramas(en R)?

algoritmos de agrupamiento clustering

Question

Tengo dos dendrogramas que deseo comparar entre sí para descubrir qué tan "similares" son. Pero no conozco ningún método para hacerlo (y mucho menos un código para implementarlo, por ejemplo, en R).

¿Alguna pista?

ACTUALIZACIÓN (2014-09-13):

Desde que hice esta pregunta, he escrito un paquete en R llamado dendextend , para la visualización, manipulación y comparación de dendrogramas. Este paquete está en dendextend y viene con una viñeta detallada . Incluye funciones como cor_cophenetic , cor_bakers_gamma y Bk / Bk_plot . Además de una función de tanglegram para comparar visualmente dos árboles.

Answer 1

Como saben, los Dendrograms surgen de la agrupación jerárquica, así que lo que realmente están preguntando es cómo puedo comparar los resultados de dos ejecuciones de agrupación jerárquica. No conozco métricas estándar, pero me gustaría ver la cantidad de grupos encontrados y comparar la similitud de miembros entre grupos similares. Here hay una buena descripción general de la agrupación jerárquica que mi colega escribió sobre la agrupación de whisky escocés.

Answer 2

Comparar dendrogramas no es lo mismo que comparar agrupamientos jerárquicos, ya que el primero incluye las longitudes de las ramas y las divisiones, pero también creo que es un buen comienzo. Le sugiero que lea EB Fowlkes & CL Mallows (1983). "Un método para comparar dos agrupaciones jerárquicas". Revista de la Asociación Americana de Estadística 78 (383): 553–584 (link) .

Su enfoque se basa en cortar los árboles en cada nivel k , obtener una medida Bk que compare las agrupaciones en grupos k , y luego examinar los diagramas Bk vs k . La medida Bk se basa en mirar pares de objetos y ver si caen en el mismo grupo o no.

Estoy seguro de que se puede escribir código basado en este método, pero primero necesitamos saber cómo se representan los dendrogramas en R.

Answer 3

Echa un vistazo a esta página :

También tengo una pregunta similar here

Parece que podemos usar la correlación copenética para medir la similitud entre dos dendrogramas. Pero no parece haber ninguna función para este propósito en R actualmente.

EDITAR en 2014,9,18: La función cophenetic en el paquete de stats es capaz de calcular la matriz de disimilitud cophenetic. y la correlación se puede calcular utilizando la función cor . como @Tal señaló que la función as.dendrogram devolvió el árbol con un orden diferente, lo que causará resultados erróneos si calculamos la correlación en función de los resultados del dendrograma. Como se muestra en el ejemplo de la función cor_cophenetic function in dendextend package:

set.seed(23235)
ss <- sample(1:150, 10 )
hc1 <- iris[ss,-5] %>% dist %>% hclust("com")
hc2 <- iris[ss,-5] %>% dist %>% hclust("single")
dend1 <- as.dendrogram(hc1)
dend2 <- as.dendrogram(hc2)
# cutree(dend1)
cophenetic(hc1)
cophenetic(hc2)
# notice how the dist matrix for the dendrograms have different orders:
cophenetic(dend1)
cophenetic(dend2)
cor(cophenetic(hc1), cophenetic(hc2)) # 0.874
cor(cophenetic(dend1), cophenetic(dend2)) # 0.16
# the difference is becasue the order of the distance table in the case of
# stats:::cophenetic.dendrogram will change between dendrograms!

Answer 4

Eche un vistazo a this página que contiene mucha información sobre el software que se ocupa de los árboles, incluidos los dendrogramas. Noté varias herramientas que tienen que ver con la comparación de árboles, aunque personalmente no he usado ninguna de ellas todavía. Hay una serie de referencias citadas allí también.

Answer 5

Existe una gran cantidad de literatura sobre métricas de distancia de árboles en la comunidad filogenética que parece haber sido descuidada desde la perspectiva de la informática. Consulte el dist.topo del paquete de ape para dos métricas de distancia de árboles y varias citas (Penny y Hardy 1985, Kuhner y Felsenstein 1994) que consideran la similitud de las particiones de árboles, y también la métrica de Robinson-Foulds que tiene una implementación de R en el phangorn paquete.

Un problema es que estas métricas no tienen una escala fija, por lo que solo son útiles en los casos de 1) comparación de árbol o 2) comparación con alguna línea de base generada, tal vez a través de pruebas de permutación similares a las que Tal ha hecho con Gamma de Baker Su fantástico paquete de dendextend.

Si tiene objetos hclust o dendrogram generados a partir del agrupamiento jerárquico R , el uso de as.phylo del paquete ape convertirá sus dendrogramas a árboles filogenéticos para utilizarlos en estas funciones.

Answer 6

Si tiene acceso a la matriz de distancia subyacente que generó cada dendrograma (probablemente lo haga si generó los dendorogramas en R), ¿no podría simplemente usar la correlación entre los valores correspondientes de las dos matrices? Sé que esto no aborda la letra de lo que pidió, pero es una buena solución para el espíritu de lo que pidió.