Measuring Document Similarity

Question

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)?

Answer 1

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.

Answer 2

You might want to try this online service for cosine document similarity http://www.scurtu.it/documentSimilarity.html

import urllib,urllib2
import json
API_URL="http://www.scurtu.it/apis/documentSimilarity"
inputDict={}
inputDict['doc1']='Document with some text'
inputDict['doc2']='Other document with some text'
params = urllib.urlencode(inputDict)    
f = urllib2.urlopen(API_URL, params)
response= f.read()
responseObject=json.loads(response)  
print responseObject