是否有对距离的聚类算法，而不计算所有成对距离？

Question

我正在寻找一种聚类算法，通过使用对象的成对距离来对对象进行聚类，而不需要计算所有成对距离。

通常，成对的聚类如下所示：(请参阅这里)

1. 计算对象的所有成对组合之间的全距离矩阵
2. 假设距离为非欧氏距离，则可以在距离矩阵上使用谱聚类或亲和力传播，并检索聚类结果。

然而，

来了：

计算所有对组合对象的全距离矩阵在计算上是非常昂贵的。所以我的想法是，是否有一些聚类算法只对成对距离的子集进行查找，所以不需要计算整个矩阵？

我知道谱聚类也适用于稀疏矩阵，但是由于理论上可以计算所有成对距离，所以哪一种距离应该被忽略？

很想听听你的想法，谢谢！

Answer 1

嗯，人们可能会说DBSCAN是基于所有成对距离的，但是它使用数据索引来避免使用几何边界来计算它们。

如果你浏览文学，还有其他的例子。

例如，经典的CLARA方法是PAM的近似值，它避免计算所有成对距离。

还有更多这样的技术。

Answer 2

您可以使用局部性敏感散列技术Wiki文章。

这样，您可以估计两个文档之间的Jaccard相似性(MinHash)或余弦相似性(SimHash)，然后在文档集合上应用聚类。

MinHash代码有一个很好的例子。我从这篇文章中得到的是下面的引文

在示例代码中，我们收集了10,000篇文章，平均每篇包含250条。直接为所有对计算Jaccard相似点在我的PC上需要20分钟，而生成和比较MinHash签名只需大约2分45秒。

MinHash代码的解释