我有大约 50K 数据集,其值可能介于 0 到 10 之间。我想应用 HAC 对这些数据进行聚类。但是要应用 HAC,我需要准备一个 N*N 相似度矩阵。
对于 N = 50 K ,即使我使用short,这个矩阵也会太大而无法保存在内存中。
有什么方法可以批量进行 HAC 或任何其他方法可以帮助我应用具有 50K 数据点的 HAC。我打算在java中实现它。
我也担心需要花费的总时间,任何关于此的指示都会非常有帮助。
我有大约 50K 数据集,其值可能介于 0 到 10 之间。我想应用 HAC 对这些数据进行聚类。但是要应用 HAC,我需要准备一个 N*N 相似度矩阵。
对于 N = 50 K ,即使我使用short,这个矩阵也会太大而无法保存在内存中。
有什么方法可以批量进行 HAC 或任何其他方法可以帮助我应用具有 50K 数据点的 HAC。我打算在java中实现它。
我也担心需要花费的总时间,任何关于此的指示都会非常有帮助。
如果您想应用自上而下的聚类方法,您可以轻松分发它,相关文章: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.
有各种不同的 HAC 方法,但它们通常都以 O(n^2) 复杂度为下界。因此,虽然 50k 仍然是一个可行的数据点数量,但您无法将其扩展得太远。
我不知道您使用的是什么代码,但您不必显式存储 N^2 大小的相似度矩阵,可以根据需要动态计算相似度值。Scikit learn 会在不显式形成矩阵的情况下做到这一点。