# Measuring Document Similarity

To cluster (text) documents you need a way of measuring similarity between pairs of documents.

Two alternatives are:

1. Compare documents as term vectors using Cosine Similarity - and TF/IDF as the weightings for terms.

2. Compare each documents probability distribution using f-divergence e.g. Kullback-Leibler divergence

Is there any intuitive reason to prefer one method to the other (assuming average document sizes of 100 terms)?

-

For text documents, the feature vectors can be very high dimensional and sparse under any of the standard representations (bag of words or TF-IDF etc). Measuring distances directly under such a representation may not be reliable since it is a known fact that in very high dimensions, distance between any two points starts to look the same. One way to deal with this is to reduce the data dimensionality by using PCA or LSA (Latent Semantic Analysis; also known as Latent Semantic Indexing) and then measure the distances in the new space. Using something like LSA over PCA is advantageous since it can give a meaningful representation in terms of "semantic concepts", apart from measuring distances in a lower dimensional space.

Comparing documents based on the probability distributions is usually done by first computing the topic distribution of each document (using something like Latent Dirichlet Allocation), and then computing some sort of divergence (e.g., KL divergence) between the topic distributions of pair of documents. In a way, it's actually kind of similar to doing LSA first and then measuring distances in the LSA space using KL-divergence between the vectors (instead of cosine similarity).

KL-divergence is a distance measure for comparing distributions so it may be preferable if the document representation is in terms of some distribution (which is often actually the case -- e.g., documents represented as distribution over topics, as in LDA). Also note that under such a representation, the entries in the feature vector would sum to one (since you are basically treating the document as a distribution over topics or semantic concepts).

Also see a related thread here.

-
Thanks. Does LDA require you to know the topics upfront? In our case we do not know to which topic each Document belongs and we will be using the similarity measure to perform clustering (EM- G-Means, or GAAC) –  Joel Sep 8 '10 at 10:59
@ebony1 Nice reference to LSA, I made a similar answer some time ago at stats.stackexchange.com/questions/369/… –  chl Sep 8 '10 at 11:00
@Joel: No, LDA doesn't assume that you know the topics for each document beforehand. BTW, just to be clear, LDA represents each document as a mixture of topics, not by just a single topic. So each topic will contribute to some fraction in the documents (and the individual fractions will sum to 1). Basically, LDA assumes that each word in the document is generated by some topic. –  ebony1 Sep 8 '10 at 11:37
@ebony - thanks! At risk of a rephrasing the question and repeating myself, does LDA require you to know the number of discreet topics? –  Joel Sep 8 '10 at 12:02
Yes. But there are variants of LDA (HDP-LDA) that do not require specifying the number of topics. See this paper: cse.buffalo.edu/faculty/mbeal/papers/hdp.pdf –  ebony1 Sep 8 '10 at 14:55