Algorithm-VSM
view release on metacpan or search on metacpan
lib/Algorithm/VSM.pm view on Meta::CPAN
@clean_words = map {$_ =~ /$_regex/g} @brokenup;
@clean_words = $self->{_case_sensitive} ?
grep $_, map {$_ =~ /([[:lower:]0-9]{$min,})/i;$1?$1:''} @clean_words :
grep $_, map {$_ =~ /([[:lower:]0-9]{$min,})/i;$1?"\L$1":''} @clean_words;
} else {
my @brokenup = split /\"|\'|\.|\(|\)|\[|\]|\\|\/|\s+/, "@$query";
@clean_words = grep $_, map { /([a-z0-9_]{$min,})/i;$1 } @brokenup;
}
$query = \@clean_words;
print "\nYour query words are: @$query\n" if $self->{_debug};
if ($self->{_idf_filter_option}) {
die "\nYou need to first generate normalized document vectors before you can call retrieve_with_vsm()"
unless scalar(keys %{$self->{_vocab_hist}})
&& scalar(keys %{$self->{_normalized_doc_vecs}});
} else {
die "\nYou need to first generate document vectors before you can call retrieve_with_vsm()"
unless scalar(keys %{$self->{_vocab_hist}})
&& scalar(keys %{$self->{_corpus_doc_vectors}});
}
foreach ( keys %{$self->{_vocab_hist}} ) {
$self->{_query_vector}->{$_} = 0;
}
foreach (@$query) {
if ($self->{_case_sensitive}) {
$self->{_query_vector}->{$_}++ if exists $self->{_vocab_hist}->{$_};
} else {
$self->{_query_vector}->{"\L$_"}++ if exists $self->{_vocab_hist}->{"\L$_"};
}
}
my @query_word_counts = values %{$self->{_query_vector}};
my $query_word_count_total = sum(\@query_word_counts);
die "\nYour query does not contain corpus words. Nothing retrieved.\n"
unless $query_word_count_total;
my %retrievals;
if ($self->{_idf_filter_option}) {
print "\n\nUsing idf filter option for retrieval:\n\n"
if $self->{_debug};
foreach (sort {$self->_doc_vec_comparator}
keys %{$self->{_normalized_doc_vecs}}) {
$retrievals{$_} = $self->_similarity_to_query($_) if $self->_similarity_to_query($_) > 0;
}
} else {
print "\n\nNOT using idf filter option for retrieval:\n\n"
if $self->{_debug};
foreach (sort {$self->_doc_vec_comparator}
keys %{$self->{_corpus_doc_vectors}}) {
$retrievals{$_} = $self->_similarity_to_query($_) if $self->_similarity_to_query($_) > 0;
}
}
if ($self->{_debug}) {
print "\n\nShowing the VSM retrievals and the similarity scores:\n\n";
foreach (sort {$retrievals{$b} <=> $retrievals{$a}} keys %retrievals) {
print "$_ => $retrievals{$_}\n";
}
}
return \%retrievals;
}
######################### Upload a Previously Constructed Model #########################
sub upload_vsm_model_from_disk {
my $self = shift;
die "\nCannot find the database files for the VSM model"
unless -s "$self->{_corpus_vocab_db}.pag"
&& -s $self->{_doc_vectors_db};
$self->{_corpus_doc_vectors} = retrieve($self->{_doc_vectors_db});
tie %{$self->{_vocab_hist_on_disk}}, 'SDBM_File',
$self->{_corpus_vocab_db}, O_RDONLY, 0640
or die "Can't open DBM file: $!";
if ($self->{_debug}) {
foreach ( sort keys %{$self->{_vocab_hist_on_disk}} ) {
printf( "%s\t%d\n", $_, $self->{_vocab_hist_on_disk}->{$_} );
}
}
foreach (keys %{$self->{_vocab_hist_on_disk}}) {
$self->{_vocab_hist}->{$_} = $self->{_vocab_hist_on_disk}->{$_};
}
$self->{_corpus_vocab_done} = 1;
$self->{_vocab_size} = scalar( keys %{$self->{_vocab_hist}} );
print "\n\nVocabulary size: $self->{_vocab_size}\n\n"
if $self->{_debug};
$self->{_corpus_doc_vectors} = retrieve($self->{_doc_vectors_db});
untie %{$self->{_vocab_hist_on_disk}};
}
sub upload_normalized_vsm_model_from_disk {
my $self = shift;
die "\nCannot find the database files for the VSM model"
unless -s "$self->{_corpus_vocab_db}.pag"
&& -s $self->{_normalized_doc_vecs_db};
$self->{_normalized_doc_vecs} = retrieve($self->{_normalized_doc_vecs_db});
tie %{$self->{_vocab_hist_on_disk}}, 'SDBM_File',
$self->{_corpus_vocab_db}, O_RDONLY, 0640
or die "Can't open DBM file: $!";
if ($self->{_debug}) {
foreach ( sort keys %{$self->{_vocab_hist_on_disk}} ) {
printf( "%s\t%d\n", $_, $self->{_vocab_hist_on_disk}->{$_} );
}
}
foreach (keys %{$self->{_vocab_hist_on_disk}}) {
$self->{_vocab_hist}->{$_} = $self->{_vocab_hist_on_disk}->{$_};
}
$self->{_corpus_vocab_done} = 1;
$self->{_vocab_size} = scalar( keys %{$self->{_vocab_hist}} );
print "\n\nVocabulary size: $self->{_vocab_size}\n\n"
if $self->{_debug};
untie %{$self->{_vocab_hist_on_disk}};
}
############################## Display Retrieval Results ################################
sub display_retrievals {
my $self = shift;
my $retrievals = shift;
print "\n\nShowing the retrievals and the similarity scores:\n\n";
my $iter = 0;
foreach (sort {$retrievals->{$b} <=> $retrievals->{$a}} keys %$retrievals){
print "$_ => $retrievals->{$_}\n";
$iter++;
last if $iter > $self->{_max_number_retrievals};
}
print "\n\n";
}
############################### Directory Scanner ################################
sub _scan_directory {
my $self = shift;
my $dir = rel2abs( shift );
my $current_dir = cwd;
chdir $dir or die "Unable to change directory to $dir: $!";
foreach ( glob "*" ) {
if ( -d and !(-l) ) {
$self->_scan_directory( $_ );
chdir $dir
or die "Unable to change directory to $dir: $!";
} elsif (-r _ and
-T _ and
-M _ > 0.00001 and # modification age is at least 1 sec
!( -l $_ ) and
$self->ok_to_filetype($_) ) {
$self->_scan_file_for_rels($_) if $self->{_scan_dir_for_rels};
$self->_scan_file($_) unless $self->{_corpus_vocab_done};
$self->_construct_doc_vector($_) if $self->{_corpus_vocab_done};
}
}
lib/Algorithm/VSM.pm view on Meta::CPAN
###################### Relevance Judgments for Testing Purposes #######################
## IMPORTANT: This estimation of document relevancies to queries is NOT for
## serious work. A document is considered to be relevant to a
## query if it contains several of the query words. As to the
## minimum number of query words that must exist in a document
## in order for the latter to be considered relevant is
## determined by the relevancy_threshold parameter in the VSM
## constructor. (See the relevancy and precision-recall related
## scripts in the 'examples' directory.) The reason for why the
## function shown below is not for serious work is because
## ultimately it is the humans who are the best judges of the
## relevancies of documents to queries. The humans bring to
## bear semantic considerations on the relevancy determination
## problem that are beyond the scope of this module.
sub estimate_doc_relevancies {
my $self = shift;
die "You did not set the 'query_file' parameter in the constructor"
unless $self->{_query_file};
open( IN, $self->{_query_file} )
or die "unable to open the query file $self->{_query_file}: $!";
croak "\n\nYou need to specify a name for the relevancy file in \n" .
" in which the relevancy judgments will be dumped."
unless $self->{_relevancy_file};
while (<IN>) {
next if /^#/;
next if /^[ ]*\r?\n?$/;
$_ =~ s/\r?\n?$//;
die "Format of query file is not correct" unless /^[ ]*q[0-9]+:/;
/^[ ]*(q[0-9]+):[ ]*(.*)/;
my $query_label = $1;
my $query = $2;
next unless $query;
$self->{_queries_for_relevancy}->{$query_label} = $query;
}
if ($self->{_debug}) {
foreach (sort keys %{$self->{_queries_for_relevancy}}) {
print "$_ => $self->{_queries_for_relevancy}->{$_}\n";
}
}
$self->{_scan_dir_for_rels} = 1;
$self->_scan_directory($self->{_corpus_directory});
$self->{_scan_dir_for_rels} = 0;
chdir $self->{_working_directory};
open(OUT, ">$self->{_relevancy_file}")
or die "unable to open the relevancy file $self->{_relevancy_file}: $!";
my @relevancy_list_for_query;
foreach (sort
{get_integer_suffix($a) <=> get_integer_suffix($b)}
keys %{$self->{_relevancy_estimates}}) {
@relevancy_list_for_query =
keys %{$self->{_relevancy_estimates}->{$_}};
print OUT "$_ => @relevancy_list_for_query\n\n";
print "Number of relevant docs for query $_: " .
scalar(@relevancy_list_for_query) . "\n";
}
}
# If there are available human-supplied relevancy judgments in a disk
# file, use this script to upload that information. One of the scripts
# in the 'examples' directory carries out the precision-recall analysis
# by using this approach. IMPORTANT: The human-supplied relevancy
# judgments must be in a format that is shown in the sample file
# relevancy.txt in the 'examples' directory.
sub upload_document_relevancies_from_file {
my $self = shift;
chdir $self->{_working_directory};
open( IN, $self->{_relevancy_file} )
or die "unable to open the relevancy file $self->{_relevancy_file}: $!";
while (<IN>) {
next if /^#/;
next if /^[ ]*\r?\n?$/;
$_ =~ s/\r?\n?$//;
die "Format of query file is not correct" unless /^[ ]*q[0-9]+[ ]*=>/;
/^[ ]*(q[0-9]+)[ ]*=>[ ]*(.*)/;
my $query_label = $1;
my $relevancy_docs_string = $2;
next unless $relevancy_docs_string;
my @relevancy_docs = grep $_, split / /, $relevancy_docs_string;
my %relevancies = map {$_ => 1} @relevancy_docs;
$self->{_relevancy_estimates}->{$query_label} = \%relevancies;
}
if ($self->{_debug}) {
for (sort keys %{$self->{_relevancy_estimates}}) {
my @rels = keys %{$self->{_relevancy_estimates}->{$_}};
print "$_ => @rels\n";
}
}
}
sub display_doc_relevancies {
my $self = shift;
die "You must first estimate or provide the doc relevancies"
unless scalar(keys %{$self->{_relevancy_estimates}});
print "\nDisplaying relevancy judgments:\n\n";
foreach my $query (sort keys %{$self->{_relevancy_estimates}}) {
print "Query $query\n";
foreach my $file (sort {
$self->{_relevancy_estimates}->{$query}->{$b}
<=>
$self->{_relevancy_estimates}->{$query}->{$a}
}
keys %{$self->{_relevancy_estimates}->{$query}}){
print " $file => $self->{_relevancy_estimates}->{$query}->{$file}\n";
}
}
}
sub _scan_file_for_rels {
my $self = shift;
my $file = shift;
open IN, $file;
my @all_text = <IN>;
@all_text = grep $_, map {s/[\r]?\n$//; $_;} @all_text;
my $all_text = join ' ', @all_text;
foreach my $query (sort keys %{$self->{_queries_for_relevancy}}) {
my $count = 0;
my @query_words = grep $_,
split /\s+/, $self->{_queries_for_relevancy}->{$query};
print "Query words for $query: @query_words\n" if $self->{_debug};
foreach my $word (@query_words) {
my @matches = $all_text =~ /$word/gi;
print "Number of occurrences for word '$word' in file $file: " .
scalar(@matches) . "\n" if $self->{_debug};
$count += @matches if @matches;
lib/Algorithm/VSM.pm view on Meta::CPAN
words in order to be considered relevant to a query.
# FOR MEASURING PRECISION VERSUS RECALL FOR LSA:
my $lsa = Algorithm::VSM->new(
break_camelcased_and_underscored => 1,
case_sensitive => 0,
corpus_directory => $corpus_dir,
file_types => ['.txt', '.java'],
lsa_svd_threshold => 0.01,
min_word_length => 4,
query_file => $query_file,
relevancy_file => $relevancy_file,
relevancy_threshold => 5,
stop_words_file => $stop_words_file,
want_stemming => 1,
);
$lsa->get_corpus_vocabulary_and_word_counts();
$lsa->generate_document_vectors();
$lsa->construct_lsa_model();
$lsa->estimate_doc_relevancies();
$lsa->display_doc_relevancies();
$lsa->precision_and_recall_calculator('lsa');
$lsa->display_precision_vs_recall_for_queries();
$lsa->display_average_precision_for_queries_and_map();
We have already explained the purpose of the constructor parameter 'query_file'
and about the constraints on the format of queries in the file named through
this parameter. As mentioned earlier, the module estimates the relevancies of
the documents to the queries and dumps the relevancies in a file named by the
'relevancy_file' constructor parameter. The constructor parameter
'relevancy_threshold' is used in deciding which of the documents are considered
to be relevant to a query. A document must contain at least the
'relevancy_threshold' occurrences of query words in order to be considered
relevant to a query. We have previously explained the role of the constructor
parameter 'lsa_svd_threshold'.
# FOR MEASURING PRECISION VERSUS RECALL FOR VSM USING FILE-BASED RELEVANCE JUDGMENTS:
my $corpus_dir = "corpus";
my $stop_words_file = "stop_words.txt";
my $query_file = "test_queries.txt";
my $relevancy_file = "relevancy.txt";
my $vsm = Algorithm::VSM->new(
break_camelcased_and_underscored => 1,
case_sensitive => 0,
corpus_directory => $corpus_dir,
file_types => ['.txt', '.java'],
min_word_length => 4,
query_file => $query_file,
relevancy_file => $relevancy_file,
stop_words_file => $stop_words_file,
want_stemming => 1,
);
$vsm->get_corpus_vocabulary_and_word_counts();
$vsm->generate_document_vectors();
$vsm->upload_document_relevancies_from_file();
$vsm->display_doc_relevancies();
$vsm->precision_and_recall_calculator('vsm');
$vsm->display_precision_vs_recall_for_queries();
$vsm->display_average_precision_for_queries_and_map();
Now the filename supplied through the constructor parameter 'relevancy_file' must
contain relevance judgments for the queries that are named in the file supplied
through the parameter 'query_file'. The format of these two files must be
according to what is shown in the sample files 'test_queries.txt' and
'relevancy.txt' in the 'examples' directory.
# FOR MEASURING PRECISION VERSUS RECALL FOR LSA USING FILE-BASED RELEVANCE JUDGMENTS:
my $corpus_dir = "corpus";
my $stop_words_file = "stop_words.txt";
my $query_file = "test_queries.txt";
my $relevancy_file = "relevancy.txt";
my $lsa = Algorithm::VSM->new(
break_camelcased_and_underscored => 1,
case_sensitive => 0,
corpus_directory => $corpus_dir,
file_types => ['.txt', '.java'],
lsa_svd_threshold => 0.01,
min_word_length => 4,
query_file => $query_file,
relevancy_file => $relevancy_file,
stop_words_file => $stop_words_file,
want_stemming => 1,
);
$lsa->get_corpus_vocabulary_and_word_counts();
$lsa->generate_document_vectors();
$lsa->upload_document_relevancies_from_file();
$lsa->display_doc_relevancies();
$lsa->precision_and_recall_calculator('vsm');
$lsa->display_precision_vs_recall_for_queries();
$lsa->display_average_precision_for_queries_and_map();
As mentioned for the previous code block, the filename supplied through the
constructor parameter 'relevancy_file' must contain relevance judgments for the
queries that are named in the file supplied through the parameter 'query_file'.
The format of this file must be according to what is shown in the sample file
'relevancy.txt' in the 'examples' directory. We have already explained the roles
played by the constructor parameters such as 'lsa_svd_threshold'.
# FOR MEASURING THE SIMILARITY MATRIX FOR A SET OF DOCUMENTS:
my $corpus_dir = "corpus";
my $stop_words_file = "stop_words.txt";
my $vsm = Algorithm::VSM->new(
break_camelcased_and_underscored => 1,
case_sensitive => 0,
corpus_directory => $corpus_dir,
file_types => ['.txt', '.java'],
min_word_length => 4,
stop_words_file => $stop_words_file,
want_stemming => 1,
);
$vsm->get_corpus_vocabulary_and_word_counts();
$vsm->generate_document_vectors();
# code for calculating pairwise similarities as shown in the
# script calculate_similarity_matrix_for_all_docs.pl in the
# examples directory. This script makes calls to
#
# $vsm->pairwise_similarity_for_docs($docs[$i], $docs[$j]);
#
# for every pair of documents.
=head1 CHANGES
Version 1.70: All of the changes made in this version affect only that part of the
module that is used for calculating precision-vs.-recall curve for the estimation of
MAP (Mean Average Precision). The new formulas that go into estimating MAP are
presented in the author's tutorial on significance testing. Additionally, when
estimating the average retrieval precision for a query, this version explicitly
disregards all documents that have zero similarity with the query.
Version 1.62 removes the Perl version restriction on the module. This version also
fixes two bugs, one in the file scanner code and the other in the
precision-and-recall calculator. The file scanner bug was related to the new
constructor parameter C<case_sensitive> that was introduced in Version 1.61. And the
precision-and-recall calculator bug was triggered if a query consisted solely of
non-vocabulary words.
Version 1.61 improves the implementation of the directory scanner to make it more
platform independent. Additionally, you are now required to specify in the
constructor call the file types to be considered for computing the database model.
If, say, you have a large software library and you want only Java and text files to
be scanned for creating the VSM (or the LSA) model, you must supply that information
to the module by setting the constructor parameter C<file_types> to the anonymous
list C<['.java', '.txt']>. An additional constructor parameter introduced in this
lib/Algorithm/VSM.pm view on Meta::CPAN
data for a set of queries. You can get hold of this data by calling
$vsm->get_query_sorted_average_precision_for_queries();
The script C<significance_testing.pl> in the 'examples' directory shows how you can
use this method for significance testing.
=item B<pairwise_similarity_for_docs():>
=item B<pairwise_similarity_for_normalized_docs():>
If you would like to compare in your own script any two documents in the corpus, you
can call
my $similarity = $vsm->pairwise_similarity_for_docs("filename_1", "filename_2");
or
my $similarity = $vsm->pairwise_similarity_for_normalized_docs("filename_1", "filename_2");
Both these calls return a number that is the dot product of the two document vectors
normalized by the product of their magnitudes. The first call uses the regular
document vectors and the second the normalized document vectors.
=item B<precision_and_recall_calculator():>
After you have created or obtained the relevancy judgments for your test queries, you
can make the following call to calculate C<Precision@rank> and C<Recall@rank>:
$vsm->precision_and_recall_calculator('vsm');
or
$vsm->precision_and_recall_calculator('lsa');
depending on whether you are testing VSM-based retrieval or LSA-based retrieval.
=item B<retrieve_with_lsa():>
After you have built an LSA model through the call to C<construct_lsa_model()>, you
can retrieve the document names most similar to the query by:
my $retrievals = $vsm->retrieve_with_lsa( \@query );
Subsequently, you can display the retrievals by calling the
C<display_retrievals($retrieval)> method described previously.
=item B<retrieve_with_vsm():>
After you have constructed a VSM model, you call this method for document retrieval
for a given query C<@query>. The call syntax is:
my $retrievals = $vsm->retrieve_with_vsm( \@query );
The argument, C<@query>, is simply a list of words that you wish to use for
retrieval. The method returns a hash whose keys are the document names and whose
values the similarity distance between the document and the query. As is commonly
the case with VSM, this module uses the cosine similarity distance when comparing a
document vector with the query vector.
=item B<upload_document_relevancies_from_file():>
When human-supplied relevancies are available, you can upload them into the program
by calling
$vsm->upload_document_relevancies_from_file();
These relevance judgments will be read from a file that is named with the
C<relevancy_file> constructor parameter.
=item B<upload_normalized_vsm_model_from_disk():>
When you invoke the methods C<get_corpus_vocabulary_and_word_counts()> and
C<generate_document_vectors()>, that automatically deposits the VSM model in the
database files named with the constructor parameters C<corpus_vocab_db>,
C<doc_vectors_db> and C<normalized_doc_vecs_db>. Subsequently, you can carry out
retrieval by directly using this disk-based VSM model for speedier performance. In
order to do so, you must upload the disk-based model by
$vsm->upload_normalized_vsm_model_from_disk();
Subsequently you call
my $retrievals = $vsm->retrieve_with_vsm( \@query );
$vsm->display_retrievals( $retrievals );
for retrieval and for displaying the results.
=item B<write_corpus_vocab_to_file():>
This is the method to call for large text corpora if you would like to examine the
vocabulary created. The call syntax is
$vsm->write_corpus_vocab_to_file($filename);
where C<$filename> is the name of the file that you want the vocabulary to be written
out to. This call will also show the frequency of each vocabulary word in your
corpus.
=back
=head1 REQUIRED
This module requires the following modules:
SDBM_File
Storable
PDL
File::Basename
File::Spec::Functions
The first two of these are needed for creating disk-based database records for the
VSM and LSA models. The third is needed for calculating the SVD of the
term-frequency matrix. (PDL stands for Perl Data Language.) The last two are needed
by the directory scanner to make pathnames platform independent.
=head1 EXAMPLES
See the 'examples' directory in the distribution for the scripts listed below:
=over
=item B<For Basic VSM-Based Retrieval:>
For basic VSM-based model construction and retrieval, run the script:
retrieve_with_VSM.pl
Starting with version 1.60, this script does not store away the VSM model in
disk-based hash tables. If you want your model to be stored on the disk, you must
run the script C<retrieve_with_VSM_and_also_create_disk_based_model.pl> for that.
=item B<For a Continuously Running VSM-Based Search Engine for Repeated Retrievals:>
If you want to run an infinite loop for repeated retrievals from a VSM model, run the
script
( run in 0.428 second using v1.01-cache-2.11-cpan-b16cb0d3907 )