Zipf's law for text

I haven't posted for a while, I've been busy with work related data science topics using R. However, I'm revisiting text mining for a work related topic and I thought I would revisit some of the things I used to do.

One fascinating topic (and the subject of my Master's dissertation) is Zipf's law. It basically says that for a text corpus there is a simple relation between the rank of a word and its frequency of occurrence. The most common word is given rank 1, the second rank 2 and so on. Zipf's law says that if you multiply the rank of a word by the number of times it appears, you will get a constant. In concrete terms, this means if the most common word appears 100 times, the second most common will appear 50 times, and the third most 33 times and so on.

Of course, it's not precise and this is where it's interesting to see how different texts by different authors vary. It's also possible to calculate an expected probability to see how close to the law a real text corpus actually is. To remind myself how to do this, I made a process here that calculates the observed and expected probabilities of a document corpus.

Here's the picture showing log(rank) against log(observed probability).

It's a log-log plot because the formula relating rank to probability is of the form.

rank = K/probability

and taking the log of both sides leads to

log(rank) = log(K) - log(probability)

which is a straight line with a negative slope.

The graph shows the expected probability in red and the observed in blue. There is a reasonably nice straight line for the blue points which shows there is something in the law.

The process works as follows...

The process requires the Text Mining Extension to be installed so ensure you have that if you want to run it. The process points to the RapidMiner Studio license agreements on the local disk, so ensure you change the location for the "Loop Files" operator in order to run it yourself. This operator reads all the documents it finds and then calls "Process Documents" to process them. Very light tokenizing and filtering is done inside this operator and the resulting word list is used to feed into the rest of the process. The word list gives the words and the number of times they appear across the whole corpus. Some processing of this makes an example set containing observed and expected probabilities. Of interest is the "Normalize" operator that makes probabilities and the "Generate Attributes" operator that calculates an expected probability using a macro containing the number of words found.

The plot can be recreated using the advanced plotting capabilities.

From here, more advanced things can be done such as measuring differences between authors and texts although care is needed to make sure the different texts have certain similarities to avoid getting slightly wrong conclusions. It's also possible to try and model a different law to the distribution of words. One such is the Zipf-Mandelbrot modification which adds some additional parameters and which you can read about here (shameless plug).

In summary, I recreated the process in about half an hour. This shows how easy it can be to create powerful data mining processes using RapidMiner Studio without needing to write software.

English stop words

I wondered recently what is the exact word list used by the Filter Stopwords (English) operator.

I consulted the code for version 5.3 and I made the following file. It contains 395 words in total including some interesting ones ones like "wert" - the imperfect subjunctive of "were" found in Shakespearean English and "summat" - Yorkshire dialect for "something". I'm not sure these would always be stop words.

I assume the operator hasn't changed in the latest version but if it has, the list can be used with the Filter Stopwords (Dictionary) operator to make a facsimile of version 5.3. It would also be possible to use the list as the basis for your own stop word filtering operator and publishing the list would make research more reproducible.

Sentiment Analysis: British politicians compared with a Happiness Histogram.

I'm currently making some text mining videos one of which is about sentiment analysis. For fun, I thought I would analyse the sentiment of speeches given at their respective party conferences by three current British politicians, David Cameron, Nick Clegg and Ed Miliband to see what we can learn. Of course, and I stress, this is by no means an exhaustive and thorough analysis; it's just a bit of fun.

I used RapidMiner and the Text Mining and WordNet extensions. Specifically, the WordNet 3.0 and the SentiWordNet 3.0.0 database. I divided each text into tokens (i.e. words) and then split the text into consecutive equal sized parts with 100 words in each. I then used the Extract Sentiment (English) operator to score each of the parts with a sentiment. This ranges between +1 for positive and -1 for negative. I used a dash of R to draw some of the graphs below with the advanced charts of RapidMiner being used for the last one.

Let's compare the three speeches using a histogram of the sentiments - the Happiness Histogram. The colours represent the parties (Ed Miliband: Red, Nick Clegg: Orange, David Cameron: Blue). The graphs show the sentiment distribution for each 100 word part of the document and you can see that the values range between +0.1 and -0.04. With 100 words you would not expect very high scores because the sentiment calculation simply applies a sentiment value to each word and averages for all words. Nonetheless, the variations are slightly more than would be expected from random sampling; I did some brief checking to confirm this.

This next graph compares them directly.

We notice that the speeches are resolutely perky in that they are always more positive than negative on average. The Miliband speech has an outlying region of happiness (ironically to the right) whereas the other two are more middle of the road,

Now let's see how sentiment varies as we move through the speeches.

This graph is a moving average of 10 data points (i.e. 1000 words) for each of the 3 speeches with the colours as before. The minutes axis corresponds to a speaking rate of 125 words a minute which is what I observed the speeches averaged to. This means the first moving average starts at 1000 words or at about 8 minutes in.

It's quite interesting to see how the different politicians vary sentiment. Ed Miliband approaches the end of the speech in a series of steps gradually getting happier with mini-spells of relative gloom. Nick Clegg seems to get more and more positive but perhaps peaks too early and ends on a down. David Cameron starts happy, gets gloomy then quickly recovers but again maybe too early and ends on a down. Perhaps Messrs Clegg and Cameron have to temper what they say with the realism of being in government.

It is also possible to correlate the extremes of the sentiment with the words being used. There is a wealth of detail and interesting things to note but time prevents me from detailing this today and so I will save that for another post.

Windowing and Processing Documents

The text mining extension contains an operator called "Window Document". It takes a document that has been split into tokens (typically words) and creates a collection of new documents from it. Each new document contains a fixed number of tokens corresponding to a "window length" parameter and the movement of the window that moves through the document is dictated by a "step size" parameter. A meta data attribute called "window" is created for each new document; this corresponds to the window within the original document.

So for example, this text

"The cat sat on the mat"

could be split into three windows each of size two if window length is set to two and step size is set to two.

window: 0 - "The cat"
window: 2 - "sat on"
window: 4 - "the mat"

Here's a simple process that illustrates windowing and processing. It's worth noting that the "Process Documents" operator is able to take a collection of documents as input. Note that the process uses version 6.1 of RapidMiner studio so some manual version number editing would be needed to run it in older versions. Note too that you must have the Text Processing extension installed.

The process illustrates a tiny pitfall for the unwary. If one of the tokens is "window" and if the parameter "add meta information" is set to true for the "Process Documents" operator, the resulting example set contains an attribute with the name "window_0". This is because the meta data for the window creates a special attribute in the final example set with name "window" and this would clash with the attribute corresponding to the token. If the parameter "add meta information" is set to false, the attribute corresponding to the token is called "window". In other words, the example set changes in a subtle way depending on the setting of a parameter which can lead to problems.

It's a very small point but I happened to stumble over it recently as I was preparing my contribution to an upcoming text mining book. Here's a teaser because it looks nice :). It is comparing three novels by Jane Austen and how the shape of word frequencies varies for consecutive windows through the books.

The red line is for Mansfield Park, the blue is for Sense and Sensibility and the green is for Pride and Prejudice.

XSLT

I had to transform some XML from one format to another recently for a cool thing that I am doing at the moment - more details soon with luck ;).

The XML in question was contained in a lot of files and I couldn't face editing them so I decided to embrace the power of XSLT and get the transformation done automatically using RapidMiner.

It turned out to be really quite easy and in the interests of giving something back I made a simple version of the process that shows it working.

Here is the process.

This is the input XML (a copy of the XML for a RapidMiner process as it happens)

 

Close examination shows it contains 5 operators.

The XSLT document input to the "Process XSLT" operator is shown below.

This finds all the operators with name attributes within the input XML and for each writes out the name and also finds and writes out the corresponding class attribute all within a new XML document.

The result of this is shown here.

It has correctly found the 5 operators in the original XML document and has written the name and class for each in a new XML document.

Very cool and powerful and it turned out to be quite easy. The hard bit is knowing how to create the XSLT transform.

Operators that deserve to be better known: part VI

Remove Unused Values

This operator removes the possible nominal values that an attribute can have but which are not used in the example set. This can happen if the example set has been sampled or filtered.

As an example, if an attribute is called Fruit and has possible values Apple, Banana, Orange or Pear and some filtering is done to remove all except Apple, the possible values for Fruit can still be the other values but there are no examples in the filtered example set that use these values. This can be seen in the meta data view for the example set.

This is not normally a problem but if you have a giant data set with lots of nominal values the resulting example set can be slow to process even after sampling or filtering. A particular case would be where each attribute value is a line of text. I had a situation like this where I sampled 2 million rows down to 100 in order to get my process working only to find that the seemingly small 100 row example set was taking a long time to load.

This is easily resolved by using the Remove Unused Values operator (and as an aside you could also simply convert the polynominal attribute to be of type text in the case of text processing).

Counting words in lots of documents

In response to a request contained in a comment for this post, I've modified the process to count total words and unique words for multiple files.

It does this by using the Loop Files operator to iterate over all the files in a folder.

The Loop operator outputs a collection and the Append operator joins them into a single example set.

Inside the Loop operator, the Read Document operator reads the current file and converts it into a document.

Words and unique words are counted as before and the final operator adds an attribute based on the file name contained in the macro provided by the outer Loop operator.

An example result looks like this.

Download the process here and set the directory and filter parameters of the Loop Files operator to the location you want.

Finding text needles in document haystacks

I had to find how many times a sentence occurred within a large set of documents recently and rather than use a search tool or write some software I used RapidMiner.

Here are the bare bones XML of the process to do this with pictures to help explain (the numbers are shown by clicking on the operator execution order within the RapidMiner GUI).

 The basic elements are

1. A document is created to contain the text-to-look-for - the text needles.
2. A word list is created from these using the process documents operator. 
3. A document containing text to search through is created - the document haystack.
4. The document is processed and only the provided word list items are included in the resulting document vector. This is set to output term-occurrences so the end result is a count of the number of times the text-to-look-for appeared in the document.

There are some points to note.

The text-to-look for is shown as the parameters to the first create document operator (labelled 1 above) shown here.

The document to look in contains a fragment of text copied from page 391 of the RapidMiner manual (labelled 3 above).

The first process documents operator (labelled 2) itself contains the following operators.

The tokenize operator simply uses anything but alphanumeric and space as a token boundary. This has the effect of creating each of the provided phrases as valid tokens. The replace tokens operator replaces all occurrences of space with underscore to match what the n-gram generation operator will produce later.

The final process documents operator (labelled 4) contains the following operators.

This tokenizes but by virtue of using the word list from the previous operator, only these will be considered in the final output example set once the generate n-gram operator has combined tokens together.

The end result is shown below.

The end result shows how many times the text appears in the document.

One advantage this approach has is that it seems to execute very quickly.

Append converts text attributes to polynominal

I stumbled on a foible of the "Append" operator the other day.

Attributes of type text in the input example sets are converted to type polynominal in the output example set. This has the effect that subsequent document processing will ignore the attributes.

It took a few minutes for me to work out why so I hope this will save any others these minutes. It's easy to fix, simply use the operator "Convert Nominal to Text" on the output example set.

Edit: this has been fixed in the latest release.I didn't think it was dreadfully serious but thanks to the RM developer chaps anyway.

Counting words and sentences in documents

I discovered a neat trick to allow the number of tokens within a document to be calculated and extracted in many different ways in one "Process Documents" operation. 

An example process is here. This calculates details of words and sentences within a small document.

It works by applying the "Tokenize" operator to fresh copies of the document and then using the "Aggregate Token Length" operator to extract various items of meta data relating to the tokens that have been created.

The following graphic shows the detail within the "Process Documents" operator with the execution order shown.

The execution order is important. The first chain of operators labelled from 2 to 5 extracts information relating to sentences. The resulting tokens are then thrown away but the meta data is retained. The second chain from 6 to 9 extracts information relating to words. The meta data is added to the example set returned by the "Process Documents" operator but the example set will be based on the word tokenization at the end of step 9. This means that meta data relating to sentences can be included in word vectors based on words. This can be extended to tokenize in arbitrary ways.

The result for the example looks like this.

This shows there are 9 sentences each of length 137 characters in the example document. In addition there are 184 words of average length 5.527 characters.

Counting words in a document: a better way

A much easier way to count words in a document compared to this previous post is to use the word list that is generated by text processing operators.

This example shows this. It uses the "Wordlist to Data" operator and then does some light gymnastics to calculate the sum and count of words to produce the desired results.

Normalizing Rows

The "Normalize" operator normalizes each numerical column (called an attribute in RapidMiner's terminology) within an example set to the desired range. Sometimes, you might want to normalize all the numerical values within a row (called an example within an example set in RapidMiner's terminology). I had to do this while understanding how term frequencies are calculated during document vector creation.

A nifty trick is to transpose the example set, normalize and then transpose it back again and the process here shows a very simple example.

This also shows the result of a document processing step which results in term frequencies for comparison. I recently found that RapidMiner performs a cosine normalization when producing term frequencies (it divides by the square root of the sum of the squares of the frequencies within a row which is equivalent to a document) and I wanted to see what differences show up when the sum of the frequencies is used instead (answer: not much with the data I was playing with).

Edit: added RapidMiner equivalent terminology for rows and columns

Counting words in a document

Here's an example that counts the total number of words in a document followed by the total number of unique words.

It does this by using the "cut document" operator with the following regular expression.

(\w+)

This splits the document into words and each word is returned as a document based on the result of the capturing group; the brackets define the capturing group; everything inside these is returned as a value. The "Documents To Data" operator converts all the documents, one for each word, into examples in an example set. The text field name is set to "word" and this is used in the later operators.

An "Extract Macro" operator obtains the number of examples. This is the same as the count of all words. An aggregation is performed to count words and another "Extract Macro" operator determines the number of unique words from the resulting example set. These macros are reported as log values using the "Provide Macro As Log Value" operators and the log file is converted to an example set using "Log To Data".

Other regular expressions could be used if you want to ignore numbers and inside the "Cut Document" operator it is possible to have other filtering operators such as stemming.