Como você compara a “similaridade” entre dois dendrogramas (em R)?

Question

Eu tenho dois dendrogramas que desejo comparar uns aos outros, a fim de descobrir como "similar" eles são. Mas eu não sei de qualquer método para fazer isso (e muito menos um código para implementá-lo, digamos, em R).

Alguma pista?

Atualizar (2014/09/13):

Uma vez que esta pergunta, eu escrevi um pacote de R chamado dendextend , para a visualização, manipulação e comparação de dendrograma. Este pacote está no CRAN e vem com um detalhou vinheta . Ele inclui funções tais como cor_cophenetic, cor_bakers_gamma e Bk / Bk_plot. Bem como uma função tanglegram para comparar visualmente duas árvores.

Answer 1

Comparando dendrogramas não é exatamente o mesmo que comparar agrupamentos hierárquicos, porque o primeiro inclui os comprimentos dos ramos, bem como os splits, mas eu também acho que é um bom começo. Eu sugiro que você leia E. B. Fowlkes & C. L. Mallows (1983). "Um método para comparar dois hierárquica agrupamentos". Journal of the American Statistical Association 78 (383): 553-584 (link) .

A sua abordagem baseia-se cortar as árvores em cada nível k , obtendo uma medida Bk que compara os agrupamentos em k clusters e em seguida, examinar o Bk vs k parcelas. A medida Bk baseia-se olhando para pares de objetos e ver se eles se enquadram no mesmo cluster ou não.

Estou certo de que alguém pode escrever código com base neste método, mas primeiro precisa saber como os dendrogramas são representados em R.

Answer 2

Como você sabe, Dendrograms surgem de agrupamento hierárquico - então o que você está pedindo realmente é como posso comparar os resultados de duas corridas de agrupamento hierárquico. Não existem métricas padrão que eu conheço, mas eu estaria olhando para o número de clusters encontrados e comparando filiação semelhança entre como clusters. Aqui é uma boa visão geral de agrupamento hierárquico que o meu colega escreveu no agrupamento scotch whisky é.

Answer 3

dar uma olhada em desta página :

Eu também pergunta semelhante perguntou aqui

Parece que podemos usar correlação cophenetic para medir a similaridade entre dois dendrogramas. Mas não parece haver nenhuma função para este fim em R momento.

Editar na 2014,9,18: A função cophenetic em pacote stats é capaz de calcular a matriz de dissimilaridade cofenética. e a correlação pode ser calculada utilizando a função cor. como @Tal apontou a função as.dendrogram voltou a árvore com ordem diferente, o que irá causar resultados errados se calcular a correlação com base nos resultados dendrograma. Como mostrado no exemplo da função função cor_cophenetic no pacote 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!

Answer 4

Se você tiver acesso à matriz de distância subjacente que gerou cada dendrograma (você provavelmente se você gerou os dendorograms em R), você não pode apenas utilizar a correlação entre os valores correspondentes das duas matrizes? Eu sei que este não aborda a letra do que você pediu, mas é uma boa solução para o espírito do que você pediu.

Answer 5

Dê uma olhada desta página que tem muita informação sobre software que lida com árvores, incluindo dendrogramas. Notei várias ferramentas que lidam com comparação árvore, embora eu não tenha pessoalmente utilizado qualquer um deles ainda. Há uma série de referências citadas também.

Answer 6

Há um rico corpo de literatura para métricas de distância árvore na comunidade filogenética que parece ter sido negligenciado a partir da perspectiva de ciência da computação. Consulte dist.topo do pacote ape por duas métricas de distância árvore e várias citações (Penny e Hardy 1985 Kuhner e Felsenstein, 1994) o que, considerando a semelhança das partições de árvores, e também o Robinson-Foulds métrica que tem uma implementação R na phangorn pacote.

Um problema é que essas métricas não têm uma escala fixa, de modo que eles só são úteis nos casos de 1) Comparação árvore ou 2) comparação com alguns de base gerado, talvez através de permutação testa semelhante ao que Tal fez com Gamma de Baker em seu pacote dendextend fantástica .

Se você tem hclust ou dendrograma objetos gerados a partir R agrupamento hierárquico, utilizando as.phylo do pacote ape irá converter seus dendrogramas para árvores filogenéticas para uso nessas funções.