如何对大型相似性矩阵进行层次聚类

我有大约5万个数据集，其值可能在0到10之间。我想对这些数据进行层次聚类（HAC）。但要应用HAC，我需要准备一个N*N的相似性矩阵。

当N等于5万时，这个矩阵将太大而无法在内存中保存，即使我使用short类型的数据也是如此。

有没有办法可以分批进行HAC，或者其他可以帮助我处理5万个数据点的HAC的方法？我计划用Java来实现它。

我还担心这将花费的总时间，关于这一点的任何建议都会非常有帮助。

回答：

如果你想应用自顶向下的聚类方法，你可以很容易地进行分布式处理，相关文章：http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf

长话短说（引用自另一篇文章）：在第一次节点分裂后，每个创建的节点都可以发送到一个分布式进程中再次分裂，依此类推…每个分布式进程只需要知道它正在分裂的数据集子集。只有父进程知道完整的数据集。

自底向上的方法要分布式处理要困难得多，我在这里不会尝试建议任何方法。

但是，你不需要自己用Java编写这些，Mahout或MLLib库已经有了这些功能，并且它们支持Java和Hadoop。

最后，这里有一篇关于比较不同分布式层次聚类方法的优秀且详尽的工作：

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

学技术