分布式层次聚类

Question

有没有什么算法可以帮助层次化聚类？谷歌的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-means和主方向分裂分区：http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf。最后，您只需要将每个父节点拆分成相对平衡的子节点。

自上而下的方法更容易分发。在您的第一个节点拆分之后，创建的每个节点都可以发送到分布式进程，以便再次拆分，依此类推……每个分布式进程只需要知道它正在拆分的数据集的子集。只有父进程知道完整的数据集。

此外，每个拆分都可以并行执行。K-means的两个示例：

• 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回顾了几种用于分层聚类的分布式算法：

C.F.Olson“用于分层聚类的并行算法。”并行计算，21:1313-203,1995，doi:10.1016/0167-8191(95)00017-I。

Parunak等人。描述一个算法，灵感来自于蚂蚁如何对它们的巢进行排序：

H.Van Dyke Parunak，Richard Rohwer，Theodore C.Belding和Sven Brueckner：“动态去中心化任何时间的层次聚类。”在进程中。第四届工程自组织系统国际研讨会，2006，doi:10.1007/978-3-540-69868-5

Answer 3

看看这篇可读性很强的文章，如果有一点过时的话review by Olson (1995)。从那时起，大多数论文都需要付费才能访问。:-)

如果你使用R，我推荐使用另一个R模块snow来实现并行的pvclust。