分布式分层聚类

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，他们提出了评估网络社区（以及基于这种方法的一套算法）以及网络划分为社区质量（图模块化）的措施。