我正在寻找一种聚类算法，通过使用它们的成对距离来聚类对象，而无需计算所有成对距离。
通常成对聚类是这样完成的：（见这里）
然而，这里来了：
计算对象的所有成对组合的全距离矩阵在计算上非常昂贵。所以我的想法是，是否有一些聚类算法只对成对距离的子集进行查找，所以没有必要计算完整的矩阵？
我知道光谱聚类也适用于稀疏矩阵，但由于理论上可以计算所有成对距离，哪些应该被忽略？
很想听听你的想法，谢谢！
好吧，有人可能会争辩说 DBSCAN 基于所有成对距离，但它使用数据索引来避免使用几何边界计算所有这些距离。
如果您浏览文献，还有其他示例。
例如，经典的 CLARA 方法是 PAM 的一种近似方法，可避免计算所有成对距离。
还有更多这样的技术。
四叉树可用于此目的。
该算法将二维空间划分为簇。在这个例子中；我们可以从与“E”和“F”的比较中排除点“C”
http://wiki.gis.com/wiki/index.php/Quadtree
DBSCAN 在某些情况下也很有用：https ://en.wikipedia.org/wiki/DBSCAN
您可以使用 Locality Sensitive Hashing 技术Wiki 文章
有了这个，您可以估计两个文档之间的 Jaccard 相似度 (MinHash) 或余弦相似度 (SimHash)，然后对文档集合应用聚类。
MinHash 有一个很好的 Python 代码示例。我从文章中得到的是下面的引用
在示例代码中，我们收集了 10,000 篇文章，平均每篇文章包含 250 个带状疱疹。在我的 PC 上直接计算所有对的 Jaccard 相似度需要 20 分钟，而生成和比较 MinHash 签名只需大约 2 分 45 秒。