Qual algoritmo o ward.D no hclust () implementa se não for o critério de Ward?

16

A utilizada pela opção "ward.D" (equivalente à única opção Ward "ward" nas versões R <= 3.0.3) não implementa o critério de agrupamento de Ward (1963), enquanto a opção "ward.D2" implementa esse critério ( Murtagh e Legendre 2014).

( http://stat.ethz.ch/R-manual/R-patched/library/stats/html/hclust.html )

Aparentemente, ward.D não implementa corretamente o critério de Ward. No entanto, parece fazer um bom trabalho em relação aos agrupamentos que produz. O que method = "ward.D" implementa se não for o critério de Ward?

Referências

Murtagh, F., & Legendre, P. (2014). Método de aglomerado hierárquico de Ward: quais algoritmos implementam o critério de Ward ?. Journal of Classification , 31 (3), 274-295.

Raffael
fonte
O artigo de Murthagh e Legendre diz algo sobre isso?
Cbeleites suporta Monica
Eu não tenho acesso a esse papel
Raffael
A primeira coisa que uma pesquisa aparece para mim é o pdf do manuscrito em u montreal !?
Cbeleites suporta Monica
então o que o jornal diz? Não consigo encontrar
Raffael
É isso que peço que você nos diga.
Cbeleites suporta Monica

Respostas:

11

O manuscrito relevante está aqui .

A diferença entre ala D e ala D2 é a diferença entre os dois critérios de agrupamento que, no manuscrito, são denominados Ward1 e Ward2.

Basicamente, tudo se resume ao fato de que o algoritmo Ward é implementado diretamente corretamente apenas em Ward2 (ala.D2), mas a ala1 (ala.D) também pode ser usada, se as distâncias euclidianas (de dist()) forem quadradas antes de inseri-las no hclust()usando a enfermaria.D como método.

Por exemplo, o SPSS também implementa Ward1, mas avisa os usuários que as distâncias devem ser quadradas para obter o critério Ward. Nesse sentido, a implementação da ala D não é obsoleta e, no entanto, pode ser uma boa ideia mantê-la para compatibilidade com versões anteriores.      

JTT
fonte
2
Do artigo que você vincula, não segue Ward algorithm is directly correctly implemented in just Ward2, mas sim que: (1) para obter resultados corretos com ambas as implementações, use distâncias euclidianas quadradas com Ward1 e distâncias euclidianas não-quartas com Ward2; (2) para tornar seus dendrogramas de saída comparáveis ​​(idênticos), aplique a raiz quadrada nos níveis de fusão após Ward1 ou os níveis de fusão quadrada após Ward2, antes de construir o dendrograma.
ttnphns
Você está certo, é claro. Obrigado pelo esclarecimento. O que eu quis dizer com "diretamente implementado corretamente" é que não são necessárias outras etapas, como obter uma raiz quadrada das alturas, para chegar ao resultado correto com o método ward.D2.
JTT
1
A pequena nuance aqui é que, com o método de Ward, é não definiu o que é "correta" ou verdadeiro apresentação níveis de fusão - se eles devem ser plotados "nonsquared" ou "quadrado". A causa da indecisão é que os níveis de fusão em Ward não são distâncias , são dispersões incrementais .
ttnphns
9

A única diferença entre ward.D& ward.D2é o parâmetro de entrada.

hclust(dist(x)^2,method="ward.D") ~ hclust(dist(x)^2,method="ward")

que são equivalentes a: hclust(dist(x),method="ward.D2")

Você pode encontrar o trabalho de pesquisa: Método de Clustering Hierárquico de Ward: Critério de Cluster e Algoritmo Aglomerativo

Os valores do critério Ward2 estão " em uma escala de distâncias ", enquanto os valores do critério Ward1 estão " em uma escala de distâncias ao quadrado ".

Nilesh
fonte
Prefiro essa resposta, pois a outra implica que Ward.D está errado, não está. Apenas diferente.
22417 Chris
6

Me deparei com o trabalho de pesquisa que corresponde à função objetivo que está sendo otimizada por "Ward1 (ward.D)": Clustering hierárquico por meio de distâncias conjuntas entre distâncias: ampliando o método de variância mínima de Ward . Acontece que a implementação de "Ward1 (ward.D)" por R é equivalente a minimizar a distância de energia entre os grupos de cluster.

e

A={a1,,an1}B={b1,,bn2}Rdee(A,B)AB

e(A,B)=n1n2n1+n2(2n1n2i=1n1j=1n2aibj(1)1n12i=1n1j=1n1aiaj1n22i=1n2j=1n2bibj).
user3235207
fonte
Are you sure that that is the correct interpretation of the contents of that paper? It seems to me that e(2) corresponds to ward.D2, but I don't think it is stated anywhere that e(1) corresponds to ward.D1. In fact, on page 161–162, it is stated that for 0<α<2, e(α) does not correspond to any power of Euclidean distance, assuming cluster size is greater than 1 . Interesting paper none the less.
Jonas Dahlbæk