Dynamic clustering for text documents

Question

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.

Answer 1

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)

Answer 2

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!