Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let the first document involve the words $\{x_1,x_2,\ldots,x_n\}$ and the second one be composed of $\{y_1,y_2,\ldots,y_m\}$ where $n$ is not necessarily equal to $m$. I have a similarity measure that works for elements of the sets; $s(x_i,y_j)$ for all $i$ and $j$. This similarity may not be symmetric, that is, $s(x_i,y_j)\neq s(y_j,x_i)$.

But I'm not familiar about the similarity of two sets of instances. I thought that the average of the best similarities is reasonable:

$$s\left(\{x_1,x_2,\ldots,x_n\},\{y_1,y_2,\ldots,y_m\}\right) = \frac{1}{n}\sum_{i=1}^n \max_{j=1}^m s(x_i,y_j)$$

What are the main methods used to compute $s\left(\{x_1,x_2,\ldots,x_n\},\{y_1,y_2,\ldots,y_m\}\right)$ in such a case? Particularly the similairty of two text documents?

share|improve this question
It's quite common for documents to have almost toally disjoint sets of words. To deal with the extreme sparsity, you have to do some kind of dimensionality reduction or latent variable estimation. See: Latent Dirichlet Allocation and Latent Semantic Analysis – Stumpy Joe Pete Dec 18 '12 at 20:44
Hi Helen, I think you should first take a look at Vector Space Model. This is the simplest way to compare two text documents but not necessarily the best way. However, it will give you a platform to start from and help you understand the need for the methods mentioned by @StumpyJoePete (+1). – TenaliRaman Dec 19 '12 at 5:23
up vote 8 down vote accepted

There are various methods to define document similarity, but let me introduce the most easiest approach to start with, based on semantic vector space:

  1. First build your term-document matrix
  2. Then "Normalize" the entries in the matrix with tf-idf
  3. From there, you can use your document-vectors columns of the matrix to calculate the similarity with the cosine similarity for instance

I think it's the most basic approach that gives decent results.

If you have a lot of documents and terms, your matrix can be very big but also very sparse. That's where dimension reduction technics are usually introduced. You can for instance use SVD to define underlying correlated dimensions in your space, and use only the few strongly correlated ones as a new basis for your document vectors. It works pretty well but is demanding in computing resources for very large spaces.

Alternatively, you can use random projection to reduce your space, but it's bit longer to explain.

You must know that there are also libraries that can do this for you. If you want to use random projection for instance, the semantic vector package was built around this idea : , but if I remember well they also have SVD encoded (edit: I checked and they have the Latent Semantic Analysis module implemented -LSA is based on SVD-).

You can look for all the terms used in their corresponding wikipedia entries, I wasn't allowed to put more than 2 links for spam reasons apparently !!!

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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