Comment comparez-vous la « similitude » entre deux dendrogrammes (en R)?

StackOverflow https://stackoverflow.com/questions/2218395

Question

J'ai deux dendrogrammes que je veux comparer les uns aux autres afin de trouver comment « similaires » ils sont. Mais je ne connais pas de méthode pour le faire (et encore moins un code pour la mettre en œuvre, par exemple, en R).

Des pistes?

UPDATE (13/09/2014):

Depuis posant cette question, j'ai écrit un paquet R appelé dendextend , pour la visualisation, la manipulation et comparaison de dendrogramme. Ce paquet est et CRAN est livré avec un vignette détaillée . Il comprend des fonctions telles que cor_cophenetic, cor_bakers_gamma et Bk / Bk_plot. De plus en fonction de tanglegram pour comparer visuellement deux arbres.

Était-ce utile?

La solution

La comparaison dendrogrammes est pas tout à fait la même chose que la comparaison clusterings hiérarchiques, parce que le premier comprend les longueurs des branches, ainsi que le grand écart, mais je pense aussi que c'est un bon point de départ. Je vous suggère de lire E. B. Fowlkes & C. L. Mallows (1983). « Une méthode de comparaison de deux Clusterings hiérarchiques ». Journal de l'American Statistical Association 78 (383): 553-584 (lien) .

Leur approche est basée sur la coupe des arbres à chaque niveau k , obtenir une mesure Bk qui compare les groupements dans k clusters, et examiner ensuite la Bk vs k parcelles. La mesure Bk est basée sur la recherche à des paires d'objets et de voir si elles tombent dans le même groupe ou non.

Je suis sûr que l'on peut écrire un code basé sur cette méthode, mais d'abord nous aurions besoin de savoir comment les dendrogrammes sont représentés dans R.

Autres conseils

Comme vous le savez, Dendrogrammes proviennent de regroupement hiérarchique - donc ce que vous demandez vraiment est comment puis-je comparer les résultats de deux séries de classification hiérarchique. Il n'y a pas des mesures standard que je connais, mais je regarderais le nombre de grappes trouvés et en comparant la similarité des membres entre les groupes tels que. est un bon aperçu de la classification hiérarchique que mon collègue a écrit sur son regroupement whisky écossais.

un coup d'oeil à cette page :

J'ai aussi question similaire posée

Il semble que nous pouvons utiliser la corrélation cophénétique pour mesurer la similitude entre les deux dendrogrammes. Mais il ne semble pas fonction à cet effet dans R actuellement.

EDIT à 2014,9,18:  La fonction cophenetic dans le set de stats est capable de calculer la matrice de dissimilarité cophénétique. et la corrélation peut être calculée en utilisant la fonction de cor. comme @Tal a souligné la fonction as.dendrogram retourne l'arbre avec un ordre différent, ce qui provoquera des résultats erronés si l'on calcule la corrélation sur la base des résultats de dendrogramme. Comme montré dans l'exemple de fonction de la fonction cor_cophenetic dans le set de dendextend: 

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!

Si vous avez accès à la matrice de la distance sous-jacente qui a généré chaque dendrogramme (vous probablement si vous avez généré le dendorograms dans R), ne pourriez-vous utiliser simplement une corrélation entre les valeurs correspondantes des deux matrices? Je sais que cela ne répond pas à la lettre de ce que vous avez demandé, mais il est une bonne solution à l'esprit de ce que vous avez demandé.

Jetez un oeil à cette page qui a beaucoup d'informations sur les logiciels qui traite arbres, y compris dendrogrammes. J'ai remarqué plusieurs outils qui traitent de la comparaison des arbres, bien que je ne l'ai pas personnellement utilisé encore aucun d'entre eux. Il y a un certain nombre de références citées là aussi.

Il y a un riche corpus de littérature pour les mesures de distance des arbres dans la communauté phylogénétique qui semble avoir été négligé du point de vue de la science informatique. Voir dist.topo du paquet ape pour deux métriques de distance de l'arbre et plusieurs citations (Penny et Hardy 1985, Kühner et Felsenstein 1994), qui compte tenu de la similitude des partitions d'arbres, et aussi le métrique Robinson-Foulds qui a une implémentation R dans la section phangorn package .

Un problème est que ces mesures ne sont pas une échelle fixe, de sorte qu'ils ne sont utiles que dans les cas de 1) de comparaison d'arbres ou 2) par rapport à certains de référence généré, peut-être via

Non affilié à StackOverflow
scroll top