java - MapReduce 中的层次聚类实现代表性链接社区的树状图

Question

我想使用层次聚类与链接之间的相似性来构建树状图，其中每个叶子都是原始网络的链接，分支代表链接在 MapReduce 中使用层次聚类的社区。任何引用方法算法将不胜感激。

Answer 1

分层集群永远无法与 MapReduce 很好地配合。

首先，MapReduce设计是为了一次处理一条记录，而距离计算确实一次至少需要两条记录。出于这个原因，将基于距离的算法引入 MapReduce 通常是一个坏主意；这就是为什么 MapReduce 现在已经成为过时的新闻了。没有人再关注 MapReduce，它除了预处理和过滤之外的任何功能都太有限了。

而且，这也没有多大帮助。层次聚类的扩展性本质上很差，因为它在通常的实现中需要 O(n^2) 内存和 O(n^3) 运行时间。因此，通过分布式实现获得的任何 yield 都只能让您处理稍微大一点的数据集:如果您添加 8 倍的计算机，则只能处理 2 倍大的数据集。这对于可扩展性来说显然是不能令人满意的。另外，您还需要更多的磁盘空间。您真的希望有 O(n^2) 可用磁盘空间吗？

最后但并非最不重要的一点是，如果您确实拥有大数据，无论如何您都无法查看树状图。

如果您有大数据，请使用不同的算法。或采样。

如果您的数据不是那么大，只需使用单主机实现，如 ELKI ，相当快。最有可能的是，它会优于基于集群的实现，因为它可以避免使用 mapreduce 获得的所有额外磁盘 IO。