Showing posts with label cosine-similarity. Show all posts
Showing posts with label cosine-similarity. Show all posts

Wednesday, September 18, 2013

Calculating Centroid and Cosine Similarity with Sparse Vectors


I was building a simple topic tagger recently, which involved calculating the centroid for a group of documents in a cluster, and then calculating the cosine similarity of a new document against each cluster centroid in order to find the most similar clusters. The features for each document are concepts, a byproduct of our concept annotation pipeline that matches terms and phrases against our knowledge graph and writes out the concept map as a sparse set of (id, score) pairs. What I found interesting was that it is not necessary to know the size of the matrix (or build it up front) for either calculation.

In this post, I describe the data structurs that I used to build up (somewhat custom) Sparse Matrix and Vector classes using a Map. Using these two classes, I was able to parse the concept map as it exists in my Lucene indexes, compute the centroid of a group of vectors, and compute the cosine similarity between a pair of vectors. I also show the code to train and test my automatic tagger. Finally I show the results of my tagger, which seem pretty good, even if I say so myself.

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Source: src/main/scala/com/mycompany/weka/autotagger/MapMatrix.scala
package com.mycompany.weka.autotagger

import scala.Array.fallbackCanBuildFrom
import scala.actors.threadpool.AtomicInteger

class MapMatrix {

  var initVector = new MapVector(Map())
  var size = 0
  
  def addVector(vector: MapVector): Unit = {
    initVector = initVector.add(vector)
    size = size + 1
  }
  
  def centroid(): MapVector = {
    initVector.divide(size)
  }
}

object MapVector {
  
  def fromString(s: String): MapVector = {
    fromString(s, false)
  }
  
  def fromString(s: String, normalize: Boolean): MapVector = {
    val pairs = s.split(" ")
    val m: Map[String,Double] = pairs.map(pair => {
      val cols = pair.split("\\$")
      (cols(0), cols(1).toDouble)
    }).
    toMap
    val v = new MapVector(m) 
    if (normalize) v.divide(v.l2norm()) 
    else v
  }
  
  def toFormattedString(vector: MapVector): String = 
    vector.iterator.toList.
      map(pair => "%s$%-8.5f".format(pair._1, pair._2).trim()).
      mkString(" ")
}

class MapVector(val map: Map[String,Double]) {
  
  def iterator() = map.iterator
  
  def elementValue(key: String): Double = map.getOrElse(key, 0.0D)

  def divide(scalar: Double): MapVector =
    new MapVector(Map() ++
      iterator.toList.map(pair => (pair._1, pair._2 / scalar)))  
  
  def add(vector: MapVector): MapVector = {
    val keys = iterator.toList.map(pair => pair._1).
      union(vector.iterator.toList.map(pair => pair._1)).
      toSet
    new MapVector(Map() ++ keys.map(key => 
      (key, elementValue(key) + vector.elementValue(key))))
  }
  
  def dotProduct(vector: MapVector): Double = {
    val keys = iterator.toList.map(pair => pair._1).
      union(vector.iterator.toList.map(pair => pair._1)).
      toSet
    keys.map(key => elementValue(key) * vector.elementValue(key)).
      foldLeft(0.0D)(_ + _)
  }
  
  def l2norm(): Double = scala.math.sqrt(
    iterator.toList.
    map(pair => math.pow(pair._2, 2.0D)).
    foldLeft(0.0D)(_ + _))
  
  def cosim(vector: MapVector): Double =
    dotProduct(vector) / (l2norm() * vector.l2norm())  
  
  def realSize(): Int = map.size
  
  override def toString(): String = this.iterator.toList.toString
}

The epiphany for me was realizing that cosine similarity depends on the dot product and the norm, both of which are implemented in the MapVector class. In case of the dot product between two vectors (x • y), if x(i) does not exist, we can simply replace x(i) with zero. Similarly, for a L2 norm (square root of sum of squares) of a vector x, if x(i) does not exist, x(i)2 does not contribute anything to the sum either.

Similarly, for calculating centroids in the MapMatrix class, one simply unions the elements, resulting in a denser and denser centroid vector as more component vectors are added. Finally we divide all the elements by the number of components. Once again, no need to know what the size of the vector is, empty elements don't get to play.

The MapVector object above is a convenience class and is tied to the rest of the application. It defines parsing logic to convert from the sparse (id, score) string representation in the Lucene index to a MapVector object, and vice versa.

During training, these two classes are invoked to parse two files, one containing the concept map (the X file) and one containing the topic labels (the y file) for a group of documents. The concept vectors are partitioned by topic label and centroids built for each topic label, and the resulting "model" containing the labels and centroids are written out to disk.

The input and output files for the training phase are shown below (first two lines only, to given you an idea of the format).

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
sujit@cyclone:data$ head -2 hlcms_X.txt 
8879364$4.57 2791408$5.91 8208163$4.04 8110463$6.30 9109159$2.85 ...
8116692$0.13 9294268$59.22

sujit@cyclone:data$ head -2 hlcms_y.txt 
Heart Health
Pregnancy

sujit@cyclone:data$ head -2 model.txt 
Eyes       2795857$0.00822 8112578$0.00144 8887764$0.00019 ...
Arthritis  8903634$0.00607 8887764$0.00011 8879906$0.00005 ...

Here is the code that calls my MapVector and MapMatrix classes.

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// Source: src/main/scala/com/mycompany/weka/autotagger/AutoTagger.scala
package com.mycompany.weka.autotagger

import java.io.{File, FileWriter, PrintWriter}

import scala.io.Source

object AutoTagger extends App {

  val Xfile = new File("data/hlcms_X.txt")
  val Yfile = new File("data/hlcms_y.txt")
  val ModelFile = new File("data/model.txt")
  val TestFile = new File("data/hlcms_test.txt")
  val ReportFile = new File("data/hlcms_report.txt")
  
  val RecoPercentCutoff = 5
  val RecoNumber = 3
  
//  train(Xfile, Yfile, ModelFile)
  test(ModelFile, TestFile, ReportFile)
  
  def train(xfile: File, yfile: File, modelFile: File): Unit = {
    
    val matrices = scala.collection.mutable.Map[String,MapMatrix]()
  
    val yvalues = Source.fromFile(yfile).getLines.toList
    var ln = 0
    Source.fromFile(xfile).getLines.
      foreach(line => {
        val yvalue = yvalues(ln)
        val matrix = matrices.getOrElse(yvalue, new MapMatrix())
        matrix.addVector(MapVector.fromString(line, true))
        matrices(yvalue) = matrix
        ln = ln + 1    
    })
  
    val model = new PrintWriter(new FileWriter(modelFile), true)
    val x = matrices.keySet.
      map(key => (key, matrices(key).centroid())).
      foreach(pair => model.println("%s\t%s".
      format(pair._1, MapVector.toFormattedString(pair._2))))
    model.flush()
    model.close()
  }  
    
  def test(modelFile: File, testFile: File, reportFile: File): Unit = {
    
    val centroids = Source.fromFile(modelFile).getLines.
      map(line => {
        val cols = line.split("\t")
        (cols(0), MapVector.fromString(cols(1), true))
      }).
      toMap
    val writer = new PrintWriter(new FileWriter(reportFile), true)
    var numTests = 0.0D
    var numCorrect = 0.0D
    Source.fromFile(testFile).getLines.
      foreach(line => {
        val cols = line.split("\t")
        val catscores = centroids.keySet.map(key => {
            val vector = MapVector.fromString(cols(2), true)
            (key, vector.cosim(centroids(key)))
          }).
          toList.
          sortWith((a, b) => a._2 > b._2)
        val scoresum = catscores.map(kv => kv._2).
          foldLeft(0.0D)(_ + _)
        val confidences = catscores.map(kv => 
          (kv._1, kv._2 * 100 / scoresum)).
          filter(kv => kv._2 > RecoPercentCutoff).
          slice(0, RecoNumber)
        writer.println(cols(0)) // title
        writer.println("\t" + confidences.map(kv => 
          new String("%s (%-5.2f%%)".format(kv._1, kv._2))).
          mkString("; "))
        numTests = numTests + 1
        val recommended = confidences.map(_._1).toSet
        if (recommended.contains(cols(1))) 
          numCorrect = numCorrect + 1
    })
    writer.flush()
    writer.close()
    Console.println("Accuracy(%) = " + (numCorrect / numTests) * 100)
  }
}

In the testing phase, we pull out the title, topic tag and concept map for a set of 1,000 new documents. For each document, we build the MapVector, and compute its cosine similarity with each centroid. The highest values are then normalized to percentages and the top 3 topics with over 5% contribution to the total are suggested as possible tags for the new document. Evaluating the actual topic gainst the top recommended topic gave an accuracy rate of 44%. Relaxing the criterion to allow any of the recommended topics to match against the actual topic gave us an accuracy of 65%.

Below we show the input format for our test data, and the first few lines of the output report. As you can see the results look pretty believable.

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
sujit@cyclone:data$ head -2 hlcms_test.txt 
Tales of Two Thrombophilias  Medications  8109393$6.97 5343558$4.35 ...
Extended treatment for addicted smokers  Tobacco Cessation  8954225$3.38 ...

sujit@cyclone:data$ head -20 hlcms_report.txt 
Tales of Two Thrombophilias
  Pregnancy (9.85 %); Medications (5.98 %); General Health (5.42 %)
Extended treatment for some addicted smokers
  Tobacco Cessation (50.56%); Lung Cancer (28.08%); Prevention (16.13%)
Getting Around with COPD
  Asthma (24.70%); Bronchitis (21.13%); Medications (15.31%)
This Week in Crohns: September 28, 2012
  Environmental Health (18.77%); Medications (16.24%); Eyes (10.53%)
Is it better if your heart stops in a mall?
  Heart Health (50.34%); Dental / Oral Health (37.10%)
Valentine's Day and Support
  Cancer (9.10 %); Headache (8.56 %)
Beware of Hype in Training Methods
  Environmental Health (55.08%); Sexual / Reproductive Health (20.78%); \
  Men's Health (6.57 %)
This Week in Crohns: October 5, 2012
  Environmental Health (18.00%); Medications (15.69%); Eyes (10.13%)
The Silent Killer is Making Some Noise
  Women's Health (26.42%); Cancer (13.44%); Weight Management (12.57%)
Spicy Stuffed Tomatoes
  Nutrition News (49.59%); Complementary & Alternative Medicine (21.41%); \
  Heart Health (10.55%)

Thats all I have for today, hope you enjoyed reading about this as much as I enjoyed building it. The code for the classes can be found on my GitHub project page.

Update 2013-09-19: Out of curiosity, since I had already built a converter to convert from my Lucene index format to Weka's ARFF input format, I decided to check how a Naive Bayes classifier would do on my problem. The criteria for accuracy used is the stricter one, ie, the label must match the predicted class. Naive Bayes scored 25.1% against my custom solution, which scored 44%.

Posted by Sujit Pal at 8:51 PM 1 comments

Labels: , , , ,

Share/Save: Digg Technorati Delicious StumbleUpon Reddit BlinkList Furl Mixx Facebook Google Bookmark Yahoo

Friday, May 03, 2013

Inter-Document Similarity with Scikit-Learn and NLTK


Someone recently asked me about using Python to calculate document similarity across text documents. The application had to do with cheating detection, ie, compare student transcripts and flag documents with (abnormally) high similarity for further investigation. For security reasons, I could not get access to actual student transcripts. But the basic idea was to convince ourselves that this approach is valid, and come up with a code template for doing this.

I have been playing quite a bit with NLTK lately, but for this work, I decided to use the Python ML Toolkit Scikit-Learn, which has pretty powerful text processing facilities. I did end up using NLTK for its cosine similarity function, but that was about it.

I decided to use the coffee-sugar-cocoa mini-corpus of 53 documents to test out the code - I first found this in Dr Manu Konchady's TextMine project, and I have used it off and on. For convenience I have made it available at the github location for the sub-project.

Heres the code. It first parses this data into a temporary one line per file version, then vectorizes each line and creates a term document matrix for the corpus.

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
from __future__ import division

from operator import itemgetter

from nltk.cluster.util import cosine_distance
import numpy as np
import random
import re
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.feature_extraction.text import TfidfTransformer
from sklearn.pipeline import Pipeline

def preprocess(fnin, fnout):
  fin = open(fnin, 'rb')
  fout = open(fnout, 'wb')
  buf = []
  id = ""
  category = ""
  for line in fin:
    line = line.strip()
    if line.find("-- Document Separator --") > -1:
      if len(buf) > 0:
        # write out body,
        body = re.sub("\s+", " ", " ".join(buf))
        fout.write("%s\t%s\t%s\n" % (id, category, body))
      # process next header and init buf
      id, category, rest = map(lambda x: x.strip(), line.split(": "))
      buf = []
    else:
      # process body
      buf.append(line)
  fin.close()
  fout.close()

def train(fnin):
  docs = []
  cats = []
  fin = open(fnin, 'rb')
  for line in fin:
    id, category, body = line.strip().split("\t")
    docs.append(body)
    cats.append(category)
  fin.close()
  pipeline = Pipeline([
    ("vect", CountVectorizer(min_df=0, stop_words="english")),
    ("tfidf", TfidfTransformer(use_idf=False))])
  tdMatrix = pipeline.fit_transform(docs, cats)
  return tdMatrix, cats

def test(tdMatrix, cats):
  testIds = random.sample(range(0, len(cats)), int(0.1 * len(cats)))
  testIdSet = set(testIds)
  refIds = filter(lambda x: x not in testIdSet, range(0, len(cats)))
  sims = np.zeros((len(testIds), len(refIds)))
  for i in range(0, len(testIds)):
    for j in range(0, len(refIds)):
      doc1 = np.asarray(tdMatrix[testIds[i], :].todense()).reshape(-1)
      doc2 = np.asarray(tdMatrix[refIds[j], :].todense()).reshape(-1)
      sims[i, j] = cosine_distance(doc1, doc2)
  for i in range(0, sims.shape[0]):
    xsim = list(enumerate(sims[i, :]))
    sortedSims = sorted(xsim, key=itemgetter(1), reverse=True)[0:5]
    sourceCat = cats[testIds[i]]
    numMatchedCats = 0
    numTestedCats = 0
    for j, score in sortedSims:
      targetCat = cats[j]
      if sourceCat == targetCat:
        numMatchedCats += 1
      numTestedCats += 1
    print("Test Doc: %d, Source Category: %s, Target Matched: %d/%d times" %
      (i, sourceCat, numMatchedCats, numTestedCats))
      
def main():
  preprocess("sugar-coffee-cocoa-docs.txt", "sccpp.txt")
  tdMatrix, cats = train("sccpp.txt")
  test(tdMatrix, cats)
  
if __name__ == "__main__":
  main()

The code then pulls out five random documents and tries to find the five most similar documents to it, and counts how many are in the same category as itself. As you can see, the results don't look too bad.

1
2
3
4
5
6
sujit@cyclone:docsim$ python docsim.py 
Test Doc: 0, Source Category: coffee, Target Matched: 3/5 times
Test Doc: 1, Source Category: cocoa, Target Matched: 2/5 times
Test Doc: 2, Source Category: sugar, Target Matched: 3/5 times
Test Doc: 3, Source Category: cocoa, Target Matched: 1/5 times
Test Doc: 4, Source Category: sugar, Target Matched: 2/5 times

Few things I tried was to turn IDF on (its currently off), and to use Eucledian distance instead of Cosine distance. The first actually made the results slightly worse over a set of runs, and the second did not seem to have any effect.

One thing to note is that this approach is unlikely to scale. Computing document-to-document similarity across the entire corpus (as you would need to do for a group of students) is an O(n2) operation. I have recently been reading up about Locally Sensitive Hashing that can mitigate this problem by being able to detect document clumps. Another approach may be to cluster the documents first and only consider inter-document similarities for those within each cluster.

And I guess thats it for today. The approach I took with Scikit-Learn is heavily inspired by the code in the text processing tutorial linked to above. For a slightly more math and code heavy treatment of text processing with Scikit-Learn check out Christian Perone's awesome blog posts here and here.

Update (2013-05-08) - I've been reading the Building Search Applications: Lucene, LingPipe and GATE by Dr Manu Konchady (henceforth referred to as the LLG book in this blog), and I came upon the SCAM (Standard Copy Analysis Mechanism) Algorithm for Plagiarism Detection, and it seemed better suited for my cheating domain than Cosine Similarity. Here is some Python code that implements the SCAM measure between two documents. This code and the update to the original code to use this can be found in my GitHub page for this subproject.

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from __future__ import division
import numpy as np
import scipy.sparse as ss

def _s_pos_or_zero(x):
  return x if x > 0 else 0

def _s_zero_mask(x, y):
  return 0 if y == 0 else x

def _s_safe_divide(x, y):
  return 0 if x == 0 or y == 0 else x / y

_v_pos_or_zero = np.vectorize(_s_pos_or_zero)
_v_zero_mask = np.vectorize(_s_zero_mask)
_v_safe_divide = np.vectorize(_s_safe_divide)

def _assymetric_subset_measure(doc1, doc2):
  epsilon = np.ones(doc1.shape) * 2
  filtered = _v_pos_or_zero(epsilon - (_v_safe_divide(doc1, doc2) +
    _v_safe_divide(doc2, doc1)))
  zdoc1 = _v_zero_mask(doc1, filtered)
  zdoc2 = _v_zero_mask(doc2, filtered)
  return np.sum(np.dot(zdoc1, zdoc2)) / np.sum(np.dot(doc1, doc2))

def scam_distance(doc1, doc2):
  asm12 = _assymetric_subset_measure(doc1, doc2)
  asm21 = _assymetric_subset_measure(doc2, doc1)
  return max(asm12, asm21)

I decided to check this out by calculating the SCAM distance (should really be called SCAM similarity, since higher values indicate closeness) between my previous post, this post without the update and this post with the update. My expectation is that the score for the first pair should be lower than that for the second pair, and indeed it is so, giving 0.655172413793 and 0.954821894005 respectively.

Posted by Sujit Pal at 6:50 PM 17 comments

Labels: , , , , ,

Share/Save: Digg Technorati Delicious StumbleUpon Reddit BlinkList Furl Mixx Facebook Google Bookmark Yahoo

Saturday, September 27, 2008

IR Math with Java : Similarity Measures

Last week, I wrote about building term document matrices based on Dr. Manu Konchady's Text Mining Application Programming book. This week, I continue working on computing some similarity metrics from the same set of data. Most of the material is covered in Chapter 8 of the book.

As before, our document collection consists of 7 document titles as shown below:

1
2
3
4
5
6
7
D1      Human machine interface for computer applications
D2      A survey of user opinion of computer system response time
D3      The EPS user interface management system
D4      System and human system engineering testing of EPS
D5      The generation of random, binary and ordered trees
D6      The intersection graph of paths in trees
D7      Graph minors: A survey

The document collection is first converted to a raw term frequency matrix. This is further normalized using either TF/IDF or LSI. The matrix thus normalized is the input to our similarity computations.

A document is represented by a column of data in our (normalized) term document matrix. To compute the similarity between two documents, we perform computations between two columns of the matrix. Conceptually, each document as a point in an n-dimensional term space, where each term corresponds to a dimension. So in our example, we have 23 terms, therefore our term space is a 23-dimensional space. In case this is hard to visualize (it was for me), it helps to think of documents with 2 terms (and hence a two dimensional term space), and extrapolate from there.

Jaccard Similarity

Jaccard Similarity is a simple and very intuitive measure of document to document similarity. It is defined as follows:

  similarity(A,B) = n(A ∩ B) / n(A ∪ B)

Using the Inclusion-Exclusion Principle, this reduces to:

  similarity(A,B) = n(A ∩ B) / n(A) + n(B) - n(A ∩ B)
  where:
    n(A ∩ B) = Σ min(Ai, Bi)
    n(A) = Σ Ai
    n(B) = Σ Bi
  for i = [0..n-1], where n = number of terms in our term-document matrix.

AbstractSimilarity.java

The AbstractSimilarity class shown below contains the code to compare all document pairs from our collection. This has a complexity of O(n2), which we can reduce to about half if we code in the knowledge that similarity(A,B) == similarity(B,A) and similarity(A,A) == 1.0, but which is still too high for large number of documents. I haven't added these knowledge here, though, since this is just toy data and the performance is tolerable.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Source: src/main/java/com/mycompany/myapp/similarity/AbstractSimilarity.java
package com.mycompany.myapp.similarity;

import org.apache.commons.collections15.Transformer;

import Jama.Matrix;

public abstract class AbstractSimilarity 
    implements Transformer<Matrix, Matrix> {

  public Matrix transform(Matrix termDocumentMatrix) {
    int numDocs = termDocumentMatrix.getColumnDimension();
    Matrix similarityMatrix = new Matrix(numDocs, numDocs);
    for (int i = 0; i < numDocs; i++) {
      Matrix sourceDocMatrix = termDocumentMatrix.getMatrix(
        0, termDocumentMatrix.getRowDimension() - 1, i, i); 
      for (int j = 0; j < numDocs; j++) {
        Matrix targetDocMatrix = termDocumentMatrix.getMatrix(
          0, termDocumentMatrix.getRowDimension() - 1, j, j);
        similarityMatrix.set(i, j, 
          computeSimilarity(sourceDocMatrix, targetDocMatrix));
      }
    }
    return similarityMatrix;
  }

  protected abstract double computeSimilarity(
      Matrix sourceDoc, Matrix targetDoc);
}

JaccardSimilarity.java

For the JaccardSimilarity class, we define the abstract method computeSimilarity() as shown below (based on our formula above). I have cheated here slightly - in Jama, norm1() is defined as the maximum column sum, but since our document matrices are column-matrices (ie 1 column), norm1() returns the same value as the sum of all elements in the document matrix. It does make the code less readable, in the sense that the reader/maintainer would have to go through an extra mental hoop, but it makes the code concise.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
// Source: src/main/java/com/mycompany/myapp/similarity/JaccardSimilarity.java
package com.mycompany.myapp.similarity;

import Jama.Matrix;

public class JaccardSimilarity extends AbstractSimilarity {

  @Override
  protected double computeSimilarity(Matrix source, Matrix target) {
    double intersection = 0.0D;
    for (int i = 0; i < source.getRowDimension();i++) {
      intersection += Math.min(source.get(i, 0), target.get(i, 0));
    }
    if (intersection > 0.0D) {
      double union = source.norm1() + target.norm1() - intersection;
      return intersection / union;
    } else {
      return 0.0D;
    }
  }
}

The result of our Jaccard similarity computation is shown below. The JUnit test to return this is SimilarityTest.java which is shown later in this post. The two matrices are derived from our raw term document matrix normalized using TF/IDF and LSI respectively. As you can see, the similarity matrix created off the LSI normalized vector shows more inter-document similarity than the one created off the TF/IDF normalized vector.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
=== Jaccard Similarity (TF/IDF) ===
            D1      D2      D3      D4      D5      D6      D7
    D1  1.0000  0.0000  0.0000  0.0818  0.0000  0.0000  0.0000
    D2  0.0000  1.0000  0.0000  0.0000  0.0000  0.0000  0.0710
    D3  0.0000  0.0000  1.0000  0.2254  0.0000  0.0000  0.0000
    D4  0.0818  0.0000  0.2254  1.0000  0.0000  0.0000  0.0000
    D5  0.0000  0.0000  0.0000  0.0000  1.0000  0.0000  0.0000
    D6  0.0000  0.0000  0.0000  0.0000  0.0000  1.0000  0.1781
    D7  0.0000  0.0710  0.0000  0.0000  0.0000  0.1781  1.0000

=== Jaccard Similarity (LSI) ===
            D1      D2      D3      D4      D5      D6      D7
    D1  1.0000  0.0000  1.0000  1.0000  0.0000  0.0000  0.0000
    D2  0.0000  1.0000  0.0000  0.0000  1.0000  1.0000  1.0000
    D3  1.0000  0.0000  1.0000  1.0000  0.0000  0.0000  0.0000
    D4  1.0000  0.0000  1.0000  1.0000  0.0000  0.0000  0.0000
    D5  0.0000  1.0000  0.0000  0.0000  1.0000  1.0000  1.0000
    D6  0.0000  1.0000  0.0000  0.0000  1.0000  1.0000  1.0000
    D7  0.0000  1.0000  0.0000  0.0000  1.0000  1.0000  1.0000

Cosine Similarity

Cosine Similarity is the more popular but also a slightly more complex measure of similarity. It is defined as:

  similarity(A,B) = cos θ = (A ⋅ B) / (|A| * |B|)
  where:
    A ⋅ B = Σ Ai * Bi
    |A| = sqrt(Σ Ai2)
    |B| = sqrt(Σ Bi2)
  for i = [0..n-1], where n = number of terms in our term-document matrix.

Here, θ is the angle between the gradients of the documents A and B in the n-dimensional term space. A and B are very similar as θ approaches 0° (cos(0) = 1), and very dissimilar as θ approaches 90° (cos(90) = 0).

Dr. E. Garcia has a very informative tutorial on Cosine Similarity that explains the formula above in much more detail (and with more humor).

CosineSimilarity.java

The code below computes the cosine similarity based on the formula above. Here, normF() is the Frobenius norm, the square root of the sum of all elements, and norm1() is the maximum column sum, which works for me because we are computing it off a one-dimensional matrix.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// Source: src/main/java/src/com/mycompany/myapp/similarity/CosineSimilarity.jav
a
package com.healthline.jrocker.similarity;

import Jama.Matrix;

public class CosineSimilarity extends AbstractSimilarity {

  @Override
  protected double computeSimilarity(Matrix sourceDoc, Matrix targetDoc) {
    double dotProduct = sourceDoc.arrayTimes(targetDoc).norm1();
    double eucledianDist = sourceDoc.normF() * targetDoc.normF();
    return dotProduct / eucledianDist;
  }
}

The results of this computation for a term document vector normalized with TF/IDF and LSI respectively are shown below. As before, the inter-document similarity is higher for the LSI normalized vector.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
=== Cosine Similarity (TF/IDF) ===
            D1      D2      D3      D4      D5      D6      D7
    D1  1.0000  0.0000  0.0000  0.1316  0.0000  0.0000  0.0000
    D2  0.0000  1.0000  0.0000  0.0000  0.0000  0.0000  0.1680
    D3  0.0000  0.0000  1.0000  0.4198  0.0000  0.0000  0.0000
    D4  0.1316  0.0000  0.4198  1.0000  0.0000  0.0000  0.0000
    D5  0.0000  0.0000  0.0000  0.0000  1.0000  0.0000  0.0000
    D6  0.0000  0.0000  0.0000  0.0000  0.0000  1.0000  0.3154
    D7  0.0000  0.1680  0.0000  0.0000  0.0000  0.3154  1.0000

=== Cosine Similarity (LSI) ===
            D1      D2      D3      D4      D5      D6      D7
    D1  1.0000  0.0000  1.0000  1.0000  0.0000  0.0000  0.0000
    D2  0.0000  1.0000  0.0000  0.0000  1.0000  1.0000  1.0000
    D3  1.0000  0.0000  1.0000  1.0000  0.0000  0.0000  0.0000
    D4  1.0000  0.0000  1.0000  1.0000  0.0000  0.0000  0.0000
    D5  0.0000  1.0000  0.0000  0.0000  1.0000  1.0000  1.0000
    D6  0.0000  1.0000  0.0000  0.0000  1.0000  1.0000  1.0000
    D7  0.0000  1.0000  0.0000  0.0000  1.0000  1.0000  1.0000

Searching - Similarity against a Query Vector

Using the similarity vectors above, it is now possible to build a Searcher. The objective is to find the most similar documents that match our query. For this, we will need to build a query vector consisting of the terms in the query, and then compute the similarity of the documents against the query vector. The computation is similar to what we have already done above if we treat the query vector as a specialized instance of a document vector. We use Cosine Similarity for our computations here.

Searcher.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// Source: src/main/java/com/mycompany/myapp/similarity/Searcher.java
package com.healthline.jrocker.similarity;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import Jama.Matrix;

public class Searcher {

  public class SearchResult {
    public String title;
    public double score;
    public SearchResult(String title, double score) {
      this.title = title;
      this.score = score;
    }
  };
  
  private Matrix termDocumentMatrix;
  private List<String> documents;
  private List<String> terms;
  private AbstractSimilarity similarity;
  
  public void setTermDocumentMatrix(Matrix termDocumentMatrix) {
    this.termDocumentMatrix = termDocumentMatrix;
  }
  
  public void setDocuments(String[] documents) {
    this.documents = Arrays.asList(documents);
  }
  
  public void setTerms(String[] terms) {
    this.terms = Arrays.asList(terms);
  }
  
  public void setSimilarity(AbstractSimilarity similarity) {
    this.similarity = similarity;
  }
  
  public List<SearchResult> search(String query) {
    // build up query matrix
    Matrix queryMatrix = getQueryMatrix(query);
    final Map<String,Double> similarityMap = 
      new HashMap<String,Double>();
    for (int i = 0; i < termDocumentMatrix.getColumnDimension(); i++) {
      double sim = similarity.computeSimilarity(queryMatrix, 
        termDocumentMatrix.getMatrix(
          0, termDocumentMatrix.getRowDimension() - 1, i, i));
      if (sim > 0.0D) {
        similarityMap.put(documents.get(i), sim);
      }
    }
    return sortByScore(similarityMap);
  }
  
  private Matrix getQueryMatrix(String query) {
    Matrix queryMatrix = new Matrix(terms.size(), 1, 0.0D);
    String[] queryTerms = query.split("\\s+");
    for (String queryTerm : queryTerms) {
      int termIdx = 0;
      for (String term : terms) {
        if (queryTerm.equalsIgnoreCase(term)) {
          queryMatrix.set(termIdx, 0, 1.0D);
        }
        termIdx++;
      }
    }
    queryMatrix = queryMatrix.times(1 / queryMatrix.norm1());
    return queryMatrix;
  }
  
  private List<SearchResult> sortByScore(
      final Map<String,Double> similarityMap) {
    List<SearchResult> results = new ArrayList<SearchResult>();
    List<String> docNames = new ArrayList<String>();
    docNames.addAll(similarityMap.keySet());
    Collections.sort(docNames, new Comparator<String>() {
      public int compare(String s1, String s2) {
        return similarityMap.get(s2).compareTo(similarityMap.get(s1));
      }
    });
    for (String docName : docNames) {
      double score = similarityMap.get(docName);
      if (score < 0.00001D) {
        continue;
      }
      results.add(new SearchResult(docName, score));
    }
    return results;
  }
}

The results of searching with the query "human computer interface" against a similarity matrix built off a TF/IDF and an LSI normalization are shown below. Notice that we get a few more results from a LSI normalized vector. I have manually copied the titles over to make the result more readable. I suppose I could make the code do it, and I probably would have, if the code was going to be used by anybody other than myself.

1
2
3
4
5
6
7
8
Results for query: [human computer interface] using TF/IDF
D1 (score =   0.8431) Human machine interface for computer applications
D4 (score =   0.1881) System and human system engineering testing of EPS

Results for query: [human computer interface] using LSI
D4 (score =   0.2467) System and human system engineering testing of EPS
D3 (score =   0.2467) The EPS user interface management system
D1 (score =   0.2467) Human machine interface for computer applications

Calling the code - the JUnit test

For completeness, as well as to show you how the components above should be called, I show here the JUnit test that was used to run these components and derive results for this post.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// Source: src/test/java/com/mycompany/myapp/similarity/SimilarityTest.java
package com.mycompany.myapp.similarity;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

import org.apache.commons.lang.StringUtils;
import org.junit.Before;
import org.junit.Test;
import org.springframework.jdbc.datasource.DriverManagerDataSource;

import Jama.Matrix;

import com.mycompany.myapp.indexers.IdfIndexer;
import com.mycompany.myapp.indexers.LsiIndexer;
import com.mycompany.myapp.indexers.VectorGenerator;
import com.mycompany.myapp.similarity.Searcher.SearchResult;

public class SimilarityTest {

  private VectorGenerator vectorGenerator;
  
  @Before
  public void setUp() throws Exception {
    vectorGenerator = new VectorGenerator();
    vectorGenerator.setDataSource(new DriverManagerDataSource(
      "com.mysql.jdbc.Driver", "jdbc:mysql://localhost:3306/tmdb", 
      "tmdb", "irstuff"));
    Map<String,Reader> documents = 
      new LinkedHashMap<String,Reader>();
    BufferedReader reader = new BufferedReader(
      new FileReader("src/test/resources/data/indexing_sample_data.txt"));
    String line = null;
    while ((line = reader.readLine()) != null) {
      String[] docTitleParts = StringUtils.split(line, ";");
      documents.put(docTitleParts[0], new StringReader(docTitleParts[1]));
    }
    vectorGenerator.generateVector(documents);
  }

  @Test
  public void testJaccardSimilarityWithTfIdfVector() throws Exception {
    IdfIndexer indexer = new IdfIndexer();
    Matrix termDocMatrix = indexer.transform(vectorGenerator.getMatrix());
    JaccardSimilarity jaccardSimilarity = new JaccardSimilarity();
    Matrix similarity = jaccardSimilarity.transform(termDocMatrix);
    prettyPrintMatrix("Jaccard Similarity (TF/IDF)", similarity, 
      vectorGenerator.getDocumentNames(), new PrintWriter(System.out, true));
  }
  
  @Test
  public void testJaccardSimilarityWithLsiVector() throws Exception {
    LsiIndexer indexer = new LsiIndexer();
    Matrix termDocMatrix = indexer.transform(vectorGenerator.getMatrix());
    JaccardSimilarity jaccardSimilarity = new JaccardSimilarity();
    Matrix similarity = jaccardSimilarity.transform(termDocMatrix);
    prettyPrintMatrix("Jaccard Similarity (LSI)", similarity, 
      vectorGenerator.getDocumentNames(), new PrintWriter(System.out, true));
  }

  @Test
  public void testCosineSimilarityWithTfIdfVector() throws Exception {
    IdfIndexer indexer = new IdfIndexer();
    Matrix termDocMatrix = indexer.transform(vectorGenerator.getMatrix());
    CosineSimilarity cosineSimilarity = new CosineSimilarity();
    Matrix similarity = cosineSimilarity.transform(termDocMatrix);
    prettyPrintMatrix("Cosine Similarity (TF/IDF)", similarity, 
      vectorGenerator.getDocumentNames(), new PrintWriter(System.out, true));
  }
  
  @Test
  public void testCosineSimilarityWithLsiVector() throws Exception {
    LsiIndexer indexer = new LsiIndexer();
    Matrix termDocMatrix = indexer.transform(vectorGenerator.getMatrix());
    CosineSimilarity cosineSimilarity = new CosineSimilarity();
    Matrix similarity = cosineSimilarity.transform(termDocMatrix);
    prettyPrintMatrix("Cosine Similarity (LSI)", similarity, 
      vectorGenerator.getDocumentNames(), new PrintWriter(System.out, true));
  }
  
  @Test
  public void testSearchWithTfIdfVector() throws Exception {
    // generate the term document matrix via the appropriate indexer
    IdfIndexer indexer = new IdfIndexer();
    Matrix termDocMatrix = indexer.transform(vectorGenerator.getMatrix());
    // set up the query
    Searcher searcher = new Searcher();
    searcher.setDocuments(vectorGenerator.getDocumentNames());
    searcher.setTerms(vectorGenerator.getWords());
    searcher.setSimilarity(new CosineSimilarity());
    searcher.setTermDocumentMatrix(termDocMatrix);
    // run the query
    List<SearchResult> results = 
      searcher.search("human computer interface");
    prettyPrintResults("human computer interface", results);
  }

  @Test
  public void testSearchWithLsiVector() throws Exception {
    // generate the term document matrix via the appropriate indexer
    LsiIndexer indexer = new LsiIndexer();
    Matrix termDocMatrix = indexer.transform(vectorGenerator.getMatrix());
    // set up the query
    Searcher searcher = new Searcher();
    searcher.setDocuments(vectorGenerator.getDocumentNames());
    searcher.setTerms(vectorGenerator.getWords());
    searcher.setSimilarity(new CosineSimilarity());
    searcher.setTermDocumentMatrix(termDocMatrix);
    // run the query
    List<SearchResult> results = 
      searcher.search("human computer interface");
    prettyPrintResults("human computer interface", results);
  }

  private void prettyPrintMatrix(String legend, Matrix matrix, 
      String[] documentNames, PrintWriter writer) {
    writer.printf("=== %s ===%n", legend);
    writer.printf("%6s", " ");
    for (int i = 0; i < documentNames.length; i++) {
      writer.printf("%8s", documentNames[i]);
    }
    writer.println();
    for (int i = 0; i < documentNames.length; i++) {
      writer.printf("%6s", documentNames[i]);
      for (int j = 0; j < documentNames.length; j++) {
        writer.printf("%8.4f", matrix.get(i, j));
      }
      writer.println();
    }
    writer.flush();
  }
  
  private void prettyPrintResults(String query, 
      List<SearchResult> results) {
    System.out.printf("Results for query: [%s]%n", query);
    for (SearchResult result : results) {
      System.out.printf("%s (score = %8.4f)%n", result.title, result.score);
    }
  }
}

Conclusion

I hope this post was helpful. I had looked at Term Vectors in Lucene in the past, but the idea of an n-dimensional term space never quite sank in until I started working through the stuff I describe above. I know that the data I am using is toy data, and that the computations described in the blog are computationally too complex and impractical in real life, but I believe that knowing this stuff helps in building models that would be useful and practical.

Update 2009-04-26: In recent posts, I have been building on code written and described in previous posts, so there were (and rightly so) quite a few requests for the code. So I've created a project on Sourceforge to host the code. You will find the complete source code built so far in the project's SVN repository.

Posted by Sujit Pal at 9:56 AM 84 comments

Labels: , , , , , ,

Share/Save: Digg Technorati Delicious StumbleUpon Reddit BlinkList Furl Mixx Facebook Google Bookmark Yahoo

Subscribe to: Posts (Atom)