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

Question

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

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

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

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

Answer 1

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

长话短说（引用其他文章）：在您的第一个节点拆分后，创建的每个节点都可以运送到分布式进程以再次拆分等等......每个分布式进程只需要知道数据集的子集它正在分裂。只有父进程知道完整的数据集。

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

但是，嘿，您不需要自己用 Java 编写它，Mahout 或 MLLib 库已经有了它，并且它们支持 java。和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.

Answer 2

有各种不同的 HAC 方法，但它们通常都以 O(n^2) 复杂度为下界。因此，虽然 50k 仍然是一个可行的数据点数量，但您无法将其扩展得太远。

我不知道您使用的是什么代码，但您不必显式存储 N^2 大小的相似度矩阵，可以根据需要动态计算相似度值。Scikit learn 会在不显式形成矩阵的情况下做到这一点。