# Clustering a very large number of very small clusters with most data unrelated

I'm trying to detect duplicates in a data set of about 34k distinct items. When I say "duplicate," I don't mean identical items, just very similar. I have an algorithm that will Cartesian join the items and return a sparse matrix of similar items with a similarity from 0.0 to 1.0. This matrix has about 5k non-zero entries in it, so it's very sparse.

I already know what the similar items are by pairs. What I need is a good way to cluster them together. I expect there to be many clusters with only 2 items in them, and a couple thousand with more than 2 items, with the vast majority of items being unclustered.

Is there a clustering algorithm that fits this scenario well? I've tried several, but they either give poor results, or are designed with few large clusters in mind instead of many small clusters, and so tend to crash.

Is clustering the wrong approach?

I'm using Spark, but the sparse matrix is small enough that I don't mind exporting to something else if necessary.

At this data size, you can still use hierarchical clustering.

You can stop the clustering early when the similarity is too low.

But all of these approaches are pretty inefficient. The proper approach is to not use clustering at all. Instead, use similarity search or, e.g., minhash.

• I'm not seeing how minhash helps me. Isn't the output just estimated similarities between items? – Tim Gautier Jun 12 '17 at 20:55
• You don't run it on all pairs (which is slow), but only look at documents that share at least x>=1 hash buckets. These are likely to be duplicates. Objects with no such maches are unclustered. – Has QUIT--Anony-Mousse Jun 13 '17 at 7:28
• I already have the exact similarity measurement of all pairs. What I need is the best way to group the items together, given the sparse similarity matrix. – Tim Gautier Jun 13 '17 at 13:51
• See the first line of the answer. It is the easiest to use, but I don't think you should be using clustering at all, but something even simpler, like if sim(a,b)>0.9 then delete(b). – Has QUIT--Anony-Mousse Jun 13 '17 at 14:06
• If a is similar to b and b is similar to c, then I'd like to group a,b,c together. If I do something as simple as what I think you're suggesting, I'll likely end up with a,b and b,c, with b duplicated. – Tim Gautier Jun 13 '17 at 15:55

Clustering does not seem like the right approach here. Following on Anony-Mousse, a similarity matrix doesn't seem right either. Locality Sensitive Hashing (ie minhash) would be a good way to group all similar items.

Creating and searching through a similarity matrix is much more inefficient (you are computing the similarity of $\binom{n}{2}$ pairs ), so I would suggest going right to LSH rather than generating the matrix. This will group the similar items as you desire.