分布式层次聚类

是否有任何算法可以帮助进行分层聚类？谷歌的map-reduce只有一个k-clustering的例子.在分层聚类的情况下,我不确定如何在节点之间划分工作.我找到的其他资源是:http://issues.apache.org/jira/browse/MAHOUT-19 但是,使用哪种算法并不明显.

首先,您必须决定是自下而上还是自上而下构建层次结构.

自下而上称为分层凝聚聚类.这是一个简单,记录良好的算法: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-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.