machine-learning - 如何对大相似度矩阵进行层次聚类

Question

我有大约 50K 数据集，其值可能在 0 到 10 之间。我想应用 HAC 对这些数据进行聚类。但要应用 HAC，我需要准备一个 N*N 相似度矩阵。

对于 N = 50 K 来说，这个矩阵太大而无法保存在内存中，即使我使用短矩阵。

有没有办法批量进行 HAC 或任何其他方法可以帮助我应用具有 50K 数据点的 HAC。我打算用java实现它。

我还担心需要花费的总时间，任何与此相关的指示都会非常有帮助。

Answer 1

如果您想应用自上而下的聚类方法，您可以轻松分发它，相关文章:http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf

长话短说(引自其他文章):在第一次节点 split 后，创建的每个节点都可以发送到分布式进程以再次 split ，依此类推......每个分布式进程只需要知道子集它正在分割的数据集的大小。只有父进程知道完整的数据集。

自下而上的方法更难分发，我不会在这里尝试提出任何建议。

但是，嘿，您不需要自己用 Java 编写这个，Mahout 或 MLLib 库已经有了它，并且它们支持 java。还有hadoop

无论如何，如果您想自己编写，这里是 hadoop 的 Java 示例: http://sujitpal.blogspot.ru/2009/09/hierarchical-agglomerative-clustering.html

最后，关于层次聚类的不同分布式方法的比较的一项出色而重要的工作:

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