Clustering gerarchico distribuito

Question

Esistono algoritmi che possono aiutare con il clustering gerarchico?La riduzione della mappa di Google ha solo un esempio di k-clustering.In caso di clustering gerarchico, non sono sicuro di come sia possibile dividere il lavoro tra i nodi.Un'altra risorsa che ho trovato è: http://issues.apache.org/jira/browse/MAHOUT-19Ma non è chiaro quali algoritmi vengano utilizzati.

Answer 1

Innanzitutto, devi decidere se costruirai la tua gerarchia dal basso verso l'alto o dall'alto verso il basso.

Il bottom-up è chiamato clustering agglomerativo gerarchico.Ecco un algoritmo semplice e ben documentato: http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html.

Distribuire un algoritmo bottom-up è complicato perché ogni processo distribuito necessita dell'intero set di dati per fare scelte sui cluster appropriati.È inoltre necessario un elenco di cluster al livello corrente in modo da non aggiungere un punto dati a più di un cluster allo stesso livello.

Viene chiamata la costruzione della gerarchia top-down Raggruppamento divisivo. K-significa è un'opzione per decidere come dividere i nodi della gerarchia.Questo documento esamina le medie K e il partizionamento divisivo della direzione principale (PDDP) per la suddivisione dei nodi: http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf.Alla fine, devi solo dividere ciascun nodo genitore in nodi figli relativamente ben bilanciati.

Un approccio top-down è più facile da distribuire.Dopo la prima suddivisione del nodo, ogni nodo creato può essere inviato a un processo distribuito per essere nuovamente suddiviso e così via...Ogni processo distribuito deve solo essere consapevole del sottoinsieme del set di dati che sta suddividendo.Solo il processo padre è a conoscenza dell'intero set di dati.

Inoltre, ogni divisione potrebbe essere eseguita in parallelo.Due esempi di k-significa:

• 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 esamina diversi algoritmi distribuiti per il clustering gerarchico:

C.F.Olson."Algoritmi paralleli per clustering gerarchico." Calcolo parallelo, 21:1313-1325, 1995, doi:10.1016/0167-8191(95)00017-I.

Parunak et al.descrivi un algoritmo ispirato al modo in cui le formiche ordinano i loro nidi:

H.Van Dyke Parunak, Richard Rohwer, Theodore C.Belding e Sven Brueckner:"Dynamic decentralizzato in qualsiasi momento clustering gerarchico." In Proc.4 ° Workshop internazionale sui sistemi di auto-organizzazione ingegneristica (ESOA), 2006, doi:10.1007/978-3-540-69868-5

Answer 3

Dai un'occhiata a questo molto leggibile anche se un po' datato recensione di Olson (1995).Da allora, la maggior parte dei documenti richiede l'accesso a pagamento.:-)

Se usi R, ti consiglio di provare pvclust che raggiunge il parallelismo utilizzando nevicare, un altro modulo R.

Answer 4

Puoi anche vedere Trovare e valutare la struttura della comunità nelle reti di Newman e Girvan, dove propongono un approccio per valutare le comunità in reti (e un insieme di algoritmi basati su questo approccio) e misurare la divisione della rete in qualità di comunità (modulabilità del grafico).

Answer 5

Potresti guardare parte del lavoro svolto con le mappe auto-organizzanti (metodo della rete neurale di Kohonen)...i ragazzi di Università della Tecnologia di Vienna hanno svolto del lavoro sul calcolo distribuito del loro crescente algoritmo di mappa gerarchica.

Questo è un po' al limite della tua domanda sul clustering, quindi potrebbe non essere d'aiuto, ma non riesco a pensare a niente di più vicino ;)