É bom usar a distância de Manhattan com a ligação entre cluster de Ward no cluster hierárquico?

15

Estou usando o cluster hierárquico para analisar dados de séries temporais. Meu código é implementado usando a função MathematicaDirectAgglomerate[...] , que gera clusters hierárquicos com as seguintes entradas:

  • uma matriz de distância D

  • o nome do método usado para determinar a ligação entre cluster.

Eu calculei a matriz de distância D usando a distância de Manhattan:

d(x,y)=∑i|xi−yi|

onde e n ≈ 150 é o número de pontos de dados em série meus tempo.i=1,⋯,nn≈150

Minha pergunta é: está tudo bem em usar a ligação inter-cluster de Ward com uma matriz de distância de Manhattan? Algumas fontes sugerem que a ligação de Ward deve ser usada apenas com a distância euclidiana.

Observe que DirectAgglomerate[...]calcula a ligação de Ward usando apenas a matriz de distância, não as observações originais. Infelizmente, não tenho certeza de como o Mathematica modifica o algoritmo original de Ward, que (pelo meu entendimento) funcionou minimizando a soma dos quadrados dos erros das observações, calculada com relação à média do cluster. Por exemplo, para um cluster consiste em um vetor de observações univariadas, Ward formulou a soma dos quadrados dos erros como:c

(∑j||cj−mean(c)||2)2

(Outras ferramentas de software, como Matlab e R, também implementam o cluster de Ward usando apenas uma matriz de distância, para que a questão não seja específica do Mathematica.)

clustering distance-functions ward Rachel
fonte
Recentemente, analisei um conjunto bastante grande de dados usando o método Ward. No meu caso específico, a distância de Manatthan deu essencialmente o mesmo agrupamento que a distância euclidiana. Não posso fornecer nenhuma prova matemática a favor de qualquer combinação de métodos, mas, pelo menos no meu caso, o agrupamento não foi afetado pelo método da distância
nico
Todas as funções R não necessariamente esperam por uma matriz de distância. Veja, por exemplo, a ajuda on-line agnesdo pacote de cluster .
chl
Não há problema em usar qualquer distância. Verifique vlado.fmf.uni-lj.si/pub/preprint/ward.pdf O único problema é que, a média da qual estamos falando não é mais a média aritmética, mas a média de Frechet.
Randy Lai
mas podemos usar a distância de manhattan para ligação completa?
Payel Banerjee

Respostas:

8

O algoritmo de agrupamento de Ward é um método hierárquico de agrupamento que minimiza um critério de 'inércia' a cada etapa. Essa inércia quantifica a soma dos resíduos quadráticos entre o sinal reduzido e o sinal inicial: é uma medida da variação do erro em um sensor l2 (euclidiano). Na verdade, você até menciona isso na sua pergunta. É por isso que, acredito, não faz sentido aplicá-lo a uma matriz de distância que não é uma distância euclidiana.

Por outro lado, uma ligação média ou um cluster hierárquico de ligação única seria perfeitamente adequado para outras distâncias.

Gael Varoquaux
fonte
2
Obrigado por seu comentário; Eu acho que você está correto. No entanto, na prática, parece que a ligação de Ward é freqüentemente usada com distâncias não euclidianas. Ainda não tenho certeza de quais podem ser as implicações disso.
Rachel
Provavelmente vem de pessoas que usam Ward simplesmente porque é bem conhecido. Eu diria que Ward não traz ganho em comparação com uma ligação média nessas configurações. No entanto, é mais caro em termos de computação (você precisa calcular os dois primeiros momentos para cada mesclagem ou pré-calculá-los). Assim, do ponto de vista pragmático, eu simplesmente optaria pelo vínculo médio.
Gael Varoquaux 12/04
1
Na verdade, a inércia seriam definidas usando soma de distância ao quadrado (não é necessário para ser euclidiana) ver vlado.fmf.uni-lj.si/pub/preprint/ward.pdf
Randy Lai
5

Não consigo pensar em nenhum motivo pelo qual Ward deva favorecer qualquer métrica. O método de Ward é apenas outra opção para decidir quais clusters serão fundidos a seguir durante a aglomeração. Isso é obtido encontrando os dois grupos cuja fusão minimizará um certo erro ( fonte exemplar da fórmula ).

Portanto, ele se baseia em dois conceitos:

  1. A média de vetores que (para vetores numéricos) é geralmente calculada pela média de todas as dimensões separadamente.
  2. A própria métrica de distância, ou seja, o conceito de similaridade expresso por essa métrica.

Portanto: desde que as propriedades da métrica escolhida (como rotação, translação ou invariância da escala) atendam às suas necessidades (e a métrica se ajuste à maneira como a média do cluster é calculada), não vejo motivo para não usá-la .

Eu suspeito que a maioria das pessoas sugere a métrica euclidiana porque eles

  • deseja aumentar o peso das diferenças entre uma média de cluster e um único vetor de observação (que é feito por quadratura)
  • ou porque saiu como a melhor métrica na validação com base em seus dados
  • ou porque é usado em geral.
Steffen
fonte
Obrigado pela sua resposta. Esclarei minha pergunta um pouco para destacar que o algoritmo 'DirectAgglomerate [...]' utiliza apenas uma matriz de distância. Diante disso, a implementação modificada do vínculo de Ward se basearia no pressuposto de que a Matriz de distância é euclidiana? A implementação do Matlab do vínculo de Ward, por exemplo, observa que ele é adequado apenas para distâncias euclidianas ( mathworks.com/help/toolbox/stats/linkage.html ).
Rachel
1
@ Rachel: aaah, entendo. Qualquer implementação da ala precisa calcular a distância entre os membros do cluster e o centróide. Intuitivamente, é claro que a métrica usada para isso deve ser equivalente à métrica usada para calcular as distâncias entre as observações ... portanto, o matlab requer uma distmatriz euclidiana. Mas agora surge a pergunta por que implementações não solicitam uma função em vez de matriz de distâncias? Quanto dano é causado quando se usa métricas diferentes para ambas as tarefas? Eu admito, eu não sei direito, sei.
amigos estão dizendo sobre steffen
Olá exemplo removido. algum outro site?
MonsterMMORPG
2

ℓ1ℓ1ℓ1

Suresh Venkatasubramanian
fonte