Are there algorithms for clustering objects with pairwise distances, without computing all pairwise distances?

Question

I'm looking for a clustering algorithm that clusters objects, by using their pairwise distances, without needing to calculate all pairwise distances.

Normally pairwise clustering is done like this: (see here)

1. Compute full distance matrix between all pairwise combination of objects
2. Assuming that the distances there are non-euclidean, one might use Spectral Clustering or Affinity propagation on the distance matrix and retrieve the clustering results.

Here comes the however:

Computing the full distance matrix for all pairwise combination of objects is computationally very expensive. So my though was, whether there are some clustering algorithms that only do lookups on a subset of the pairwise distances, so it is not necessary to compute the full matrix?

I know Spectral Clustering works also on sparse matrices, but since it is theoretically possible to compute all pairwise distances, which ones should be left out?

Exited to hear your ideas, thanks!

Answer 1

Well, one may argue that DBSCAN is based on all pairwise distances, but it uses data indexing to avoid computing all of them using geometric bounds.

And there are other examples if you browse through literature.

For example, the classic CLARA method is an approximation to PAM that avoids computing all pairwise distances.

And there are many more such techniques.

Answer 2

You can use Locality Sensitive Hashing technique Wiki article

With this, you can estimate either the Jaccard Similarity (MinHash) or Cosine Similarity (SimHash) between two documents and then apply clustering on the documents collection.

There is a great example with Python code for MinHash. What I get from the article is the bellow quote

In the example code, we have a collection of 10,000 articles which contain, on average, 250 shingles each. Computing the Jaccard similarities directly for all pairs takes 20 minutes on my PC, while generating and comparing the MinHash signatures takes only about 2 minutes and 45 seconds.

MinHash explanation with Python code

Answer 3

Quadtree can be used for this purpose.

This algo divides 2 D space into clusters. In this example ; we can exclude point 'C' from comparison with 'E' and 'F'

http://wiki.gis.com/wiki/index.php/Quadtree

DBSCAN is also useful in some scenarios : https://en.wikipedia.org/wiki/DBSCAN