您有 n=20000000 个数据点和 d=20 个属性。

方法一

层次凝聚聚类具有时间复杂度O(n^3) 和需要O(n^2)内存。因此对于大数据集（更不用说大数据）是不可行的

您可以做的是首先使用一些近线性时间聚类算法将您的数据聚类到 2000 个集群。例如，该算法可以是 K-Means。有关其时间复杂度，请参阅此 stackoverflow 答案。这实际上是您讨论“降低准确性和组”的替代方案。然后将层次聚类应用于找到的 2000 个聚类。

方法2 使用专为大数据设计的算法。例如，Birch 算法

请参阅 Steve Mosher 解决此问题的博客文章：“Nick Stokes Distance code, now with Big Memory”。

您在这里要求更多的想法，而不是具体的解决方案，对吧？

好吧，也许可以试试RWekakmeans 的实现，SimpleKMeans()？它具有超参数，允许您在运行 KMeans 之前使用Canopy 算法隐式预处理数据。Canopy（与 Python 无关）可以以批处理或增量模式运行。

Weka 还内置了 Canopy Clusterer 的独立实现，您可以通过 Explorer GUI 使用它。但是，对于 RWeka，您必须使用RWeka::make_Weka_clusterer()调用实现 Canopy 的适当 Java 类的机制。因此，在 R 中，您不必将其包装在 SimpleKMeans() 中，然后使用RWeka::make_Weka_clusterer().

Canopy“旨在加速大型数据集上的集群操作”。据我了解 Wikipedia 文章，Canopy 还删除了数据集中的一些冗余，但以不同的方式，而不是按照您的建议构建权重。另请参阅stats.SE 的这个答案。

如果您所有的属性都具有低基数（= 很少有唯一值），我会说只是采样（您的选项＃1）。