TFIDF In Libraries: Part II of III (For programmers)
Monday, April 20th, 2009This is the second of a three-part series called TFIDF In Libraries, where relevancy ranking techniques are explored through a set of simple Perl programs. In Part I relevancy ranking was introduced and explained. In Part III additional word/document weighting techiques will be explored to the end of filtering search results or addressing the perennial task of “finding more documents like this one.” In the end it is the hoped to demonstrate that relevancy ranking is not magic nor mysterious but rather the process of applying statistical techiques to textual objects.
TFIDF, again
As described in Part I, term frequency/inverse document frequency (TFIDF) is a process of counting words in a document as well as throughout a corpus of documents to the end of sorting documents in statistically relevent ways.
Term frequency (TF) is essencially a percentage denoting the number of times a word appears in a document. It is mathematically expressed as C / T, where C is the number of times a word appears in a document and T is the total number of words in the same document.
Inverse document frequency (IDF) takes into acount that many words occur many times in many documents. Stop words and the word “human” in the MEDLINE database are very good examples. IDF is mathematically expressed as D / DF, where D is the total number of documents in a corpus and DF is the number of document in which a particular word is found. As D / DF increases so does the significance of the given word.
Given these two factors, TFIDF is literally the product of TF and IDF:
TFIDF = ( C / T ) * ( D / DF )
This is the basic form that has been used to denote relevance ranking for more than forty years, and please take note that it requires no advanced mathematical knowledge — basic arithmatic.
Like any good recipe or folk song, TFIDF has many variations. Google, for example, adds additional factors into their weighting scheme based on the popularity of documents. Other possibilities could include factors denoting the characteristics of the person using the texts. In order to accomodate for the wide variety of document sizes, the natural log of IDF will be employed throughout the balance of this demonstration. Therefore, for the purposes used here, TFIDF will be defined thus:
TFIDF = ( C / T ) * log( D / DF )
Simple Perl subroutines
In order to put theory into practice, I wrote a number of Perl subroutines implementing various aspects of relevancy ranking techniques. I then wrote a number of scripts exploiting the subroutines, essencially wrapping them in a user interface.
Two of the routines are trivial and will not be explained in any greater detail than below:
- corpus – Returns an array of all the .txt files in the current directory, and is used to denote the library of content to be analyzed.
- slurp_words – Returns a reference to a hash of all the words in a file, specifically for the purposes of implementing a stop word list.
Two more of the routines are used to support indexing and searching the corpus. Again, since neither is the focus of this posting, each will only be outlined:
- index – Given a file name and a list of stop words, this routine returns a reference to a hash containing all of the words in the file (san stop words) as well as the number of times each word occurs. Strictly speaking, this hash is not an index but it serves our given purpose adequately.
- search – Given an “index” and a query, this routine returns the number of times the query was found in the index as well as an array of files listing where the term was found. Search is limited. It only supports single-term queries, and there are no fields for limiting.
The heart of the library of subroutines is used to calculate TFIDF, ranks search results, and classify documents. Of course the TFIDF calculation is absolutely necessary, but ironically, it is the most straight-forward routine in the collection. Given values for C, T, D, and DF it returns decimal between 0 and 1. Trivial:
# calculate tfidf
sub tfidf {
my $n = shift; # C
my $t = shift; # T
my $d = shift; # D
my $h = shift; # DF
my $tfidf = 0;
if ( $d == $h ) { $tfidf = ( $n / $t ) }
else { $tfidf = ( $n / $t ) * log( $d / $h ) }
return $tfidf;
}
Many readers will probably be most interested in the rank routine. Given an index, a list of files, and a query, this code calculates TFIDF for each file and returns the results as a reference to a hash. It does this by repeatedly calculating the values for C, T, D, and DF for each of the files and calling tfidf:
# assign a rank to a given file for a given query
sub rank {
my $index = shift;
my $files = shift;
my $query = shift;
my %ranks = ();
foreach my $file ( @$files ) {
# calculate n
my $words = $$index{ $file };
my $n = $$words{ $query };
# calculate t
my $t = 0;
foreach my $word ( keys %$words ) { $t = $t + $$words{ $word } }
# assign tfidf to file
$ranks{ $file } = &tfidf( $n, $t, keys %$index, scalar @$files );
}
return \%ranks;
}
The classify routine is an added bonus. Given the index, a file, and the corpus of files, this function calculates TFIDF for each word in the file and returns a refernece to a hash containing each word and its TFIDF value. In other words, instead of calculating TFIDF for a given query in a subset of documents, it calculates TFIDF for each word in an entire corpus. This proves useful in regards to automatic classification. Like rank, it repeatedly determines values for C, T, D, and DF and calls tfidf:
# rank each word in a given document compared to a corpus
sub classify {
my $index = shift;
my $file = shift;
my $corpus = shift;
my %tags = ();
foreach my $words ( $$index{ $file } ) {
# calculate t
my $t = 0;
foreach my $word ( keys %$words ) { $t = $t + $$words{ $word } }
foreach my $word ( keys %$words ) {
# get n
my $n = $$words{ $word };
# calculate h
my ( $h, @files ) = &search( $index, $word );
# assign tfidf to word
$tags{ $word } = &tfidf( $n, $t, scalar @$corpus, $h );
}
}
return \%tags;
}
Search.pl
Two simple Perl scripts are presented, below, taking advantage of the routines described, above. The first is search.pl. Given a single term as input this script indexes the .txt files in the current directory, searches them for the term, assigns TFIDF to each of the results, and displays the results in a relevancy ranked order. The essencial aspects of the script are listed here:
# define
use constant STOPWORDS => 'stopwords.inc';
# include
require 'subroutines.pl';
# get the query
my $q = lc( $ARGV[ 0 ] );
# index
my %index = ();
foreach my $file ( &corpus ) { $index{ $file } = &index( $file, &slurp_words( STOPWORDS ) ) }
# search
my ( $hits, @files ) = &search( \%index, $q );
print "Your search found $hits hit(s)\n";
# rank
my $ranks = &rank( \%index, [ @files ], $q );
# sort by rank and display
foreach my $file ( sort { $$ranks{ $b } <=> $$ranks{ $a } } keys %$ranks ) {
print "\t", $$ranks{ $file }, "\t", $file, "\n"
}
# done
print "\n";
exit;
Output from the script looks something like this:
$ ./search.pl knowledge
Your search found 6 hit(s)
0.0193061840120664 plato.txt
0.00558586078987563 kant.txt
0.00299602568022012 aristotle.txt
0.0010031177985631 librarianship.txt
0.00059150597421034 hegel.txt
0.000150303111274403 mississippi.txt
From these results you can see that the document named plato.txt is the most relevent because it has the highest score, in fact, it is almost four times more relevant than the second hit, kant.txt. For extra credit, ask yourself, “At what point do the scores become useless, or when do the scores tell you there is nothing of significance here?”
Classify.pl
As alluded to in Part I of this series, TFIDF can be turned on its head to do automatic classification. Weigh each term in a corpus of documents, and list the most significant words for a given document. Classify.pl does this by denoting a lower bounds for TFIDF scores, indexing an entire corpus, weighing each term, and outputing all the terms whose scores are greater than the lower bounds. If no terms are greater than the lower bounds, then it lists the top N scores as defined by a configuration. The essencial aspects of classify.pl are listed below:
# define
use constant STOPWORDS => 'stopwords.inc';
use constant LOWERBOUNDS => .02;
use constant NUMBEROFTAGS => 5;
# require
require 'subroutines.pl';
# initialize
my @corpus = &corpus;
# index
my %index = ();
foreach my $file (@corpus ) { $index{ $file } = &index( $file, &slurp_words( STOPWORDS ) ) }
# classify each document
foreach my $file ( @corpus ) {
print $file, "\n";
# list tags greater than a given score
my $tags = &classify( \%index, $file, [ @corpus ] );
my $found = 0;
foreach my $tag ( sort { $$tags{ $b } <=> $$tags{ $a } } keys %$tags ) {
if ( $$tags{ $tag } > LOWERBOUNDS ) {
print "\t", $$tags{ $tag }, "\t$tag\n";
$found = 1;
}
else { last }
}
# accomodate tags with low scores
if ( ! $found ) {
my $n = 0;
foreach my $tag ( sort { $$tags{ $b } <=> $$tags{ $a } } keys %$tags ) {
print "\t", $$tags{ $tag }, "\t$tag\n";
$n++;
last if ( $n == NUMBEROFTAGS );
}
}
print "\n";
}
# done
exit;
For example, sample, yet truncated, output from classify.pl looks like this:
aristotle.txt
0.0180678691531642 being
0.0112840859266579 substances
0.0110363803118312 number
0.0106083766432284 matter
0.0098440843778661 sense
mississippi.txt
0.00499714142455761 mississippi
0.00429324597184886 boat
0.00418922035591656 orleans
0.00374087743616293 day
0.00333830388445574 river
Thus, assuming a lower TFIDF bounds of 0.02, the words being, substance, number, matter, and sense are the most significant in the document named aristotle.txt. But since none of the words in mississippi.txt have a score that high the top five words are returned instead. For more extra credit, think of ways classify.pl can be improved by answering, “How can the output be mapped to controlled vocabulary terms or expanded through the use of some other thesarus?”
Summary
The Perl subroutines and scripts described here implement TFIDF to do rudimentary ranking of search results and automatic classification. They are not designed to be production applications, just example tools for the purposes of learning. Turning the ideas implemented in these scripts into production applications have been the fodder for many people’s careers and entire branches of computer science.
You can download the scripts, subroutines, and sample data in order for you to learn more. You are encouraged to remove the .txt files from the distribution and replace them with your own data. I think your search results and automatic classification output will confirm in your mind that TFIDF is well-worth the time and effort of the library community. Given the amounts of full text books and journal articles freely available on the Internet, it behooves the library profession to learn to exploit these concepts because our traditional practices simply: 1) do not scale, or 2) do not meet with our user’s expectations. Furthermore, farming these sorts of solutions out to vendors is irresponsible.
The 
More specifically, I have created a tiny system for copying scanned materials locally, enhancing it with a word cloud, indexing it, and providing access to whole thing. There is how it works:
The