有没有什么算法可以帮助层次聚类？
Google的map-reduce仅是k聚类的一个例子。在分层集群的情况下，我不确定如何在节点之间划分工作。
我发现的其他资源是：http://issues.apache.org/jira/browse/MAHOUT-19
但是使用哪种算法尚不清楚。

解决方案

回答

我们可以看一下使用自组织映射(Kohonen的神经网络方法)正在做的一些工作...维也纳工业大学的家伙已经完成了他们不断增长的层次图算法的分布式计算的一些工作。

这只是聚类问题的边缘，因此它可能无济于事，但我想不出更进一步的方法;)

回答

Clark Olson回顾了几种用于层次聚类的分布式算法：

C. F. Olson. "Parallel Algorithms for
  Hierarchical Clustering." Parallel
  Computing, 21:1313-1325, 1995, doi:10.1016/0167-8191(95)00017-I.

Parunak等。描述一种受蚂蚁如何对巢进行排序启发的算法：

H. Van Dyke Parunak, Richard Rohwer,
  Theodore C. Belding,and Sven
  Brueckner: "Dynamic Decentralized
  Any-Time Hierarchical Clustering."  In
  Proc. 4th International Workshop on Engineering Self-Organising Systems
  (ESOA), 2006, doi:10.1007/978-3-540-69868-5

回答

首先，我们必须决定是要自上而下还是自上而下构建层次结构。

自下而上称为层次聚类。这是一个简单的，有据可查的算法：http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html。

分发自下而上的算法很棘手，因为每个分布式过程都需要整个数据集来做出有关适当集群的选择。它还需要一个当前级别的集群列表，因此它不会向同一级别的多个集群添加数据点。

自上而下的层次结构称为分裂聚类。 K均值是决定如何拆分层次结构节点的一种选择。本文研究了用于节点拆分的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。

回答

如果奥尔森(1995)有点过时的评论，请查看此可读性强的文章。此后，大多数论文都需要付费才能获得。 :-)

如果使用R，我建议我们尝试使用pvclust，它使用另一个R模块snow来实现并行性。