分佈式分層聚類

Question

有沒有可以幫助分層聚類的算法？ Google的map-reduce只是一個k聚類的例子。在分層聚類的情況下，我不確定如何在節點之間劃分工作。 我找到的其他資源是：http://issues.apache.org/jira/browse/MAHOUT-19 但不明顯，使用哪種算法。

Answer 1

首先，你必須決定，如果你要建立你的層級結構中自下而上或自上而下的。

自下而上稱爲分層凝聚聚類。這裏有一個簡單的，有據可查的算法：http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html。

分佈自底向上的算法很棘手，因爲每個分佈式進程都需要整個數據集來做出關於適當集羣的選擇。它還需要一個當前級別的集羣列表，因此它不會將數據點添加到同一級別的多個集羣。

自頂向下層次結構被稱爲Divisive clustering。 K-means是決定如何拆分層次節點的一個選項。本文討論節點分裂的K均值和主方向分裂分割（PDDP）：http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf。最後，你只需要將每個父節點分成相對平衡的子節點。

自頂向下的方法更容易分發。在第一個節點拆分之後，每個創建的節點都可以發送到分佈式進程以再次拆分，等等......每個分佈式進程只需要知道要拆分的數據集的子集。只有父進程知道完整的數據集。

此外，每個拆分可以並行執行。對於k-均值兩個例子：

• 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

你可以看看自組織映射（Kohonen的神經網絡方法）正在完成的一些工作...... Vienna University of Technology的傢伙們已經在分佈式計算他們不斷增加的層次映射算法方面做了一些工作。

這是你的集羣問題的邊緣一點點，所以它可能不會幫助，但我想不出任何東西更接近;）

Answer 3

克拉克奧爾森回顧了層次聚類幾種分佈式算法：

CF Olson。 「並行算法 分層聚類」。 並行 計算,21：1313-1325,1995,doi:10.1016/0167-8191(95)00017-I。

Parunak et al。描述啓發算法螞蟻如何築巢排序：

H.範戴克Parunak，理查德葉蜂， 西奧多·C貝爾丁，斯文 布魯克納：「動態分散 任何時間層次聚類」在 過程。第四屆國際研討會工程自組織系統 （企業服務架構），2006年，doi:10.1007/978-3-540-69868-5

Answer 4

看看這個非常可讀，如果有點日期review by Olson (1995)。此後的大部分論文都需要付費才能訪問。 :-)

如果你使用R，我推薦嘗試pvclust，它可以使用另一個R模塊snow來實現並行性。

Answer 5

你也可以看到Newman和Girvan的Finding and evaluating community structure in networks，他們提出了評估網絡社區（以及基於這種方法的一套算法）以及網絡劃分爲社區質量（圖模塊化）的措施。