1
$\begingroup$

I have few hundred thousands of text documents. Some of them are pretty similar - they differ just in ex. names or some numbers, all other text is the same. I would like to cluster these documents, so when I list them, the most similar are listed together in groups. That's how I would avoid having numerous (almost) same documents listed one, after another.

I was thinking some kind of clustering would come handy. But the problem is, I don't know how many clusters I need. Also the number would have to be dynamic. And still, most of the documents wouldn't belong to a cluster, because they don't have any similar documents. So I would cluster just similar documents.

Can anyone point me to the direction that would help me solve this problem, or provide some examples of similar problems.

$\endgroup$
  • $\begingroup$ This is usually studied under Bayesian nonparametric models. Here's a tutorial. The problem with clustering is that it is open to interpretation, and very sensitive to representation, so the algorithm may arrive at a solution that disagrees with your intuition. Do you really need to list all the documents, or simply the "distinct" documents that match a query, because the latter can be done with a similarity search? $\endgroup$ – Emre Mar 30 '17 at 20:27
  • $\begingroup$ Thank you for that link. I will check it out. I need to list all the documents, and also a filtered list. Problem with similar documents also occurs with filtered list. $\endgroup$ – MaticDiba Mar 31 '17 at 7:50
  • $\begingroup$ To filter documents, you could calculate cosine similarity between all documents and then set some distance threshold at which you consider a group of documents the same. $\endgroup$ – emilliman5 Apr 25 '17 at 20:03
3
$\begingroup$

It sounds as if you don't need clustering.

But rather you are trying to detect near duplicates.

The difference is that clustering tries to organize everything with a focus on the larger, overall structure. But much of your data probably isn't duplicate. Clustering is difficult and slow. Near duplicates is much easier, and much faster (e.g., with MinHash or similarity search)

| improve this answer | |
$\endgroup$
  • $\begingroup$ You are correct. This could be a better approach. I will try to find more about this. To get better insight if this approach was successful on any example that is simmilar to mine. $\endgroup$ – MaticDiba Apr 3 '17 at 11:04
2
$\begingroup$

As you say, thinking ahead about the number of clusters may be limiting. A simple solution would be to use KNN.
However, KNN can be pretty expensive to run over hundreds of ks of documents. In order to limit your search space, you should first filter out (and do it quickly) documents that there is no chance that would share a cluster with the new document. So, I'm thinking some sort of hash, but a simpler solution can be to take the $l$ leading indexes in your TF-IDF representation or something. So you'll need some dictionary mapping sets of indices (as in the words in the corpus) to some integer value.

So a general scheme can follow these lines:

  • Create TF-IDF representation $d$ to your document.
  • Extract some $l$ words that have highest value in that document, call this set $W$.
  • Extract a set $S$ of all documents that had $W$ (or, say, 90% of $W$) as their leading words.
  • Run KNN for $d$ over set $S$.

Another, simpler but more mathematically based way to do this, is named MinHash and is thoroughly depicted in Jure Leskovec book `Mining Massive Data Sets, chapter 3 section 3.4. The method uses bag-of-words model and Jaccard similarity to calculate random permutation signatures and then apply LSH on the signatures to bucket similar documents together.

Good luck!

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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