In the first part of the lab, we will convert the Project Gutenberg corpus into a term-document matrix. Each row of the matrix will represent a single document in the corpus. Each column will represent a unique word in the corpus. For example, in the version of Hamlet that we have been using (PG1524), the word "castle" appears 30 times. If the matrix is storing the text PG1524 in row i and the matrix is storing the word "castle" in column j, then then matrix[i][j]=30.

(Note: A fair number of texts listed in the metadata file were not actually downloaded. In some cases it is because the text is no longer available on Project Gutenberg. In other cases, the text is only available in a non-text format such as a PDF or audio file, and we’ve only downloaded the .txt files. Later in the lab you will be able to calculate this value more precisely.)

As we work through this lab, we’re going to be reading through a lot of files. You might want to work with the metadata_small.csv subset during development and debugging.

It may take a few minutes to read through the entire Project Gutenberg corpus, and you don’t want to have to re-process the corpus over and over again. To help out, we’re going to take advantage of python’s pickle library. This library allows us to serialize our data. Practically, this means that we can create large data structures (e.g. our term-document matrix) in one program and save them directly to a file. In another program, we can read our data directly from the file with very little effort.

Here is a small example demonstrating how the pickle library works:

Once we create the matrix, if we see the word "castle" in Hamlet, how do we know which cell in the matrix this goes in? In order to figure that out, we need to assign a row number to each text, and we need to assign a column number to each word. And in order to do this assignment, we need a list of all of the texts and another list of all the words in all of these texts.

Write a program called setup.py that does the following:

If we assume that the percentage you got in the previous question is approximately true for all of the texts in Project Gutenberg, it’s pretty easy to see that a very large portion of the matrix we’re creating will be used to store the value 0, which seems like a huge waste of space. So instead of using a list of lists to store our matrix, we will use a sparse matrix. By default, these sparse matrices will assume that any unspecified values are 0, saving us quite a lot of memory.

There are many implementations of sparse matrices, and we will be using two of them. One implementation will be useful when we need to build the matrix, and one implementation will be useful when we need to do computations using it. Both implementations are in the scipy.sparse library.

We will start with the coo_matrix, or "coordinate matrix". The coo_matrix stores coordinates and their associated values. For example, if Hamlet was stored in row 4688 and if the word "castle" was stored in column 1105, and the word "castle" appeared 30 times in Hamlet, the the coo_matrix would store the fact that cell (1105, 4688) had the value 30.

We will use this constructor to create our coo_matrix (adapted from the reference page linked above):

To use the csr_matrix, coo_matrix, and np.int32 (described below), you will need to import the following:

If you saved your matrix in the variable matrix, you can verify you are correct by printing matrix.toarray().

The coo_matrix is optimized for constructing sparse matrices. But it is not a good format to use when you actually want to inspect values or perform arithmetic operations. Instead, once we create the coo_matrix, we will want to convert it to a csr_matrix. Given the coo_matrix you created, you can convert it to a csr_matrix as follows: matrix_csr = matrix.tocsr(). As before, you can verify this worked by printing matrix_csr.toarray().

Write a program called termdoc.py that creates the term-document matrix. Your program should:

Now that we have our term-document matrix saved, we can move on to finding documents that match a user’s search terms. To do this, we are going to use cosine similarity.

Recall that each row of the matrix represents the counts of the words we found in a single document. We will treat this row as a multidimensional vector (J&M section 6.3.1). You have likely seen two- and three-dimensional vectors, but in this matrix, since there are about 70K words in our vocabulary, each vector has approximately 70K dimensions.

Even though our vectors have a ridiculously large number of dimensions, we can still use standard mathematical techniques to determine how similar two vectors are. In particular, we will try to find the angle between the two vectors. If the angle between two vectors is small, then they are more similar; if the angle between two vectors is large, then they are less similar.

The value of each dimension in our vector is a word count. Each of these word counts has a non-negative value: it is either zero if the word did not occur in the document, or it is a positive value equal to the number of times it did occur. Therefore, the angle between any two vectors must be between 0 and 90 degrees.

Rather than find the angle directly, we will find the cosine of the angle between the two vectors because it is easy to calculate! When we use the cosine to determine how close two vectors are, we call this the "cosine similarity". The cosine similarity will be close to 1 when the two vectors are very similar, and close to 0 when the two vectors are very dissimilar. (See: J&M section 6.4))

Write a program called query.py that allows the user to enter a query (space-separated words) and returns to the user a ranked list of the documents that match the query.

This program will take one command-line argument which will help you distinguish between the three main ways you will run this program. For now, the command-line argument will always be "1" since this is part 1. (This will make more sense later, but for now, just make sure your query program reads and verifies that this is part 1.)

To do this, we will ask the user to enter a space separated list of words, e.g. "flower pollen", which we will call the "query". We will convert that query into a multidimensional vector with a 1 in the "flower" dimension, a 1 in the "pollen" dimension, and a 0 in every other dimension.

To create this query vector, we will first create a vector with the same number of columns as the matrix we built and we will fill all of the entries with 0. In order to make our computations efficient, we will use the numpy.zeros function to create an empty query vector.

Then, for every word in the query vector, we will set the corresponding column value to 1. If the user types includes a word in their query that is not in your words dictionary, just ignore it.

Here is an example of how to use the numpy.zeros function and how to set values in the resulting vector:

Now that you have your query vector, you can compare that query vector to all of the vectors in your matrix and then sort them from most similar to least similar:

The list ranked contains tuples where the first element is the row number and the second element is the similarity value. For example, the highest match might be (22345, 0.15) which means that whichever book was in row 22345 has a cosine similarity of 0.15 between it and your query vector.

At this point, complete your query.py so that it:

Not all query terms are equally important, are they? That is, when you searched for "flower", it was important to find documents that contained the word "flower". But when you searched for "the flower", the cosine similarity algorithm treated "the" as equally important to "flower". That means that a document that has the word "the" a lot of times but doesn’t contain the word "flower" at all can still rank very highly. (In fact, it does! Did you find that when you answered the question above?)

To fix this, we will use a technique called tf-idf that will automatically downweight words that occur in a lot of documents. (See J&M section 6.5.)

At a high level, we are going scale all of the term frequencies so that words that occur in many documents (the "document frequency") have less impact than words that occur in fewer documents.

The formulation for calculating the adjusted tf value that we will use is:

Let’s try to adjust the term frequency for the word "castle" in Hamlet. The word "castle" appears 30 times in Hamlet, so tf_w = 30. In the Project Gutenberg collection, surprisingly, there are 21204 English texts that contain the word "castle", so df_w = 30. There are approximately 50K documents in Project Gutenberg, so N = 50000.

We say that the adjusted term frequency is 54.734 instead of 30.

You should be sure you understand how tf-idf works! However, we will not write the code to implement tf-idf; rather, we will use the scipy library to do it for us.

In the first step, we will use the TfidfTransformer to calculate the document frequency values for each word and then recalculate each value in the matrix according to the tf-idf formula.

In the second step, after the user enters a query, we need to apply tf-idf to the query vector we made. However, we don’t need to recalculate the df values from the original matrix, so we just perform the "transform" step:

Add this code to your query.py program. Be sure to only apply tf-idf to your matrix once. You will need to apply tf-idf to each query that the user enters. When computing the cosine_similarity, use the tfidf_query and tfidf_matrix.

One common way to improve perfomance even further is to remove "stop words". These are very common words that (normally) provide very little information when performing these types of queries. You can find a list of common English stopwords here: /usr/local/share/nltk_data/corpora/stopwords/english. Add code to your setup.py and termdoc.py programs so that any word in that stopword list is ignored. Stopwords are not stored in your words.pkl file and you don’t add any words to your matrix if they are in that list. Compare your results for the queries "flower" vs "the flower".

If your code from the previous part works according to the specifications above, you should be able to run your query.py program with two minor modifications:

Now when you enter a query, e.g. "spaghetti", you will get a ranked list of the words where "spaghetti" appeared very frequently with it.

In the first two parts (command-line argument 1 or 2), you asked the user to enter a query which could be composed of any number of words. You then created a query vector from that string and applied tfidf to it. Finally, you compared that query vector to every vector in the matrix and printed the results.

In the final part (command-line argument 3), you will use the same pickle files as you did in part 2. But instead of asking for a query string as you did in the previous parts, you will ask the user for a single word. Do not create a new query vector: instead, your query vector will be the row in the matrix that corresponds to the word the user entered:

Finally, compare that tfidf_query to every vector in the matrix and print the results. When printing the results, do not print the match between the query and its own row in the matrix.

Hopefully you can make just a few small changes to your existing code to make this work!