如何对大型相似矩阵进行层次聚类
How to do Hierarchical Clustering for large similarity matrix
我有大约 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
无论如何，如果您想自己编写 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 会在不显式形成矩阵的情况下进行。
我有大约 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
无论如何，如果您想自己编写 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 会在不显式形成矩阵的情况下进行。