Distributed agrupamento hierárquico

Question

Existem algoritmos que podem ajudar com agrupamento hierárquico? do Google Map-Reduce tem apenas um exemplo de k-clustering. Em caso de agrupamento hierárquico, eu não sei como é possível dividir o trabalho entre os nós. Outro recurso que eu encontrei é: http://issues.apache.org/jira/browse/ MAHOUT-19 Mas não é aparente, que os algoritmos são utilizados.

Answer 1

Em primeiro lugar, você tem que decidir se você estiver indo para construir o seu baixo para cima hierarquia ou de cima para baixo.

Bottom-up é chamado de agrupamento hierárquico aglomerativo. Aqui está uma simples, o algoritmo bem documentado: http: //nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html .

A distribuição de um algoritmo de baixo para cima é complicado, porque cada processo distribuído precisa de todo o conjunto de dados para fazer escolhas sobre os clusters apropriados. Ele também precisa de uma lista de clusters no seu nível actual para que ele não adicionar um ponto de dados para mais de um cluster no mesmo nível.

construção hierarquia Top-down é chamado agrupamento divisório . K-means é uma opção para decidir como dividir seus da hierarquia nós. Este documento analisa K-means e direção principal Partitioning divisório (PDDP) para dividir nó: http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf . No final, você só precisa dividir cada nó pai para nós filhos relativamente bem equilibrados.

A abordagem top-down é mais fácil de distribuir. Após a sua primeira divisão nó, cada nó criado pode ser enviado para um processo distribuído a ser dividida novamente e assim por diante ... Cada processo distribuído só precisa estar ciente do subconjunto do conjunto de dados que é a divisão. Apenas o processo pai está ciente do conjunto de dados completo.

Além disso, cada divisão poderia ser realizada em paralelo. Dois exemplos de k-médias:

• http://citeseerx.ist. psu.edu/viewdoc/download?doi=10.1.1.101.1882&rep=rep1&type=pdf
• http://www.ece.northwestern.edu/~wkliao/ kmeans / index.html .

Answer 2

Clark Olson Comentários de vários algoritmos distribuídos por agrupamento hierárquico:

C. F. Olson. "Paralelo Algoritmos para Hierárquica Clustering." Paralela Calculando , 21: 1313-1325, 1995 doi: 10,1016 / 0167-8191 (95) 00017-I .

Parunak et al. descrever um algoritmo inspirado em como as formigas classificar seus ninhos:

H. Van Dyke Parunak, Richard Rohwer, Theodore C. Belding, e Sven Brueckner: "descentralizada Dinâmico Qualquer-Time hierárquica Clustering ". Em Proc. 4º Workshop Internacional sobre Engenharia de auto-organização dos sistemas (ESOA) , de 2006, doi: 10,1007 / 978- 3-540-69868-5

Answer 3

Confira esta muito legível revisão se um pouco datado por Olson (1995) . A maioria dos trabalhos desde então exigem uma taxa de acesso. : -)

Se você usar R, recomendo tentar pvclust que atinge paralelismo usando neve, outro módulo R.

Answer 4

Você pode ver também encontrar e avaliar a estrutura da comunidade em redes por Newman e Girvan, onde eles propõem um aproach para avaliar as comunidades em redes (e um conjunto de algoritmos baseados nesta abordagem) e meça da divisão de rede em qualidade comunidades (modularidade gráfico).

Answer 5

Você pode olhar em algum do trabalho que está sendo feito com mapas de auto-organização (método de rede neural de Kohonen) ... os rapazes no Universidade de Tecnologia de Viena ter feito algum trabalho de cálculo distribuído de sua crescente algoritmo mapa hierárquico.

Este é um pouco sobre a borda da sua pergunta clustering, para que ele não pode ajudar, mas eu não consigo pensar em nada mais perto;)