Vector Spaces for Document Similarity

Introduction

How can a search engine determine whether two documents are similar? In our post on search engine operation we looked at how search engines can retrieve information on documents given a query string. Vector methods are also used to decide whether documents are related.

Example

Let’s make this a concrete example. Say we have three toy documents which have been parsed into their keywords so that all the unimportant word have been removed. For example, commonly occurring words such as: as, of, the, … and so on are removed. We might be left with:

document 1 = {news, information, campaign, raise, awareness}
document 2 = {news, today’s, world, information, news}
document 3 = {world, news}

We define the term space as all the unique words that occur in all the documents:

term-space = {news,information,campaign, raise, awareness, today’s, world}

Now we can convert the documents into a vector whose dimension is the same as the number of terms in the term-space. We can compare the documents with the term space and where the word occurs in the document we give it a value of 1 for that component in the term space vector.

The magnitude of the three document in document term space is:

|d_i|² = t_i1² + t_i2² + t_i3² + … + t_in²

for each of the documents this becomes:

|d₁| = √5

|d₂| = 2

|d₃| = √2

Thinking in a geometric way, these document now represent vectors pointing in 7-dimensional term space. Their similarity, is given by the how closely they they point in the same direction. If they had the same components they would be the same. We determine the similarity between two vectors by calculating the cosine of the angle between them.

Remembering back to your school-days, that the dot product of two vectors is x₁ . x₂ = |x₁||x₂| cos θ.

Therefore, cos θ =(x₁.x₂)/(|x₁||x₂|)

and x₁.x₂ = x₁₁x_{21 +} x₁₂ x₂₂ + x₁₃ x₂₃ + … + x_1nx_2n

Plugging in the numbers,

The method works with a search query q also. Assume, that the search term was “today’s news”, in this case we can write a table in the search term space.

This shows that document 3 has the greatest relevance. As a test we can change the query to be “world news” and this produces a 100%  match with document 3 as would be expected.

Weighting

If a document contains more occurrences of a word in the search query, then it is fair to say at this basic level that the document has more relevance, we can use different weights to increase the importance of the document with the most occurrences of the word. There are many different ways in which you could weight the results but one obvious example would be to sum the number of times a word appears in the document.

Using the same example documents, in document 2 the word news occurs twice so this is given additional weight.

Formally we write the new equation as cos θ =(Σ_k=1w_ik . w_jk)/(|x_i||x_j|)

After the similarity between documents has been determined, the results can be displayed.An Excel spreadsheet calculator is available to explain the vector similarity calculations.

This may be either by assuming a cut off value, documents that have a value which is above the threshold value are shown and the those that are not are discarded. Alternatively, the documents can be ranked in terms of their similarity with the most similar to the least similar.

The idea of converting documents into vectors is very useful one and it allows us to define to perform another useful task. By normalising the documents, they will have the same magnitude and the results will lye on the surface of a sphere in n-dimensional term space. Taking a small area of the surface it will appear to be flat and so we see that documents that are very similar will appear close together as shown in figure. 1.

Figure 1.