3
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I'm not seeing how minhash helps me. Isn't the output just estimated similarities between items? $\endgroup$
    – Tim Gautier
    Commented Jun 12, 2017 at 20:55
  • $\begingroup$ 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. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Jun 13, 2017 at 7:28
  • $\begingroup$ 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. $\endgroup$
    – Tim Gautier
    Commented Jun 13, 2017 at 13:51
  • $\begingroup$ 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). $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Jun 13, 2017 at 14:06
  • $\begingroup$ 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. $\endgroup$
    – Tim Gautier
    Commented Jun 13, 2017 at 15:55
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.