After initially playing around with text processing in my prior post, I added an additional algorithm and cleaned up the logic to make it easier to perform test runs and reuse later. I tweaked the RAKE algorithm implementation and added TextRank into the mix, with full sample code and links to sources available. I’m also using a read-through cache of the unprocessed and processed files so I can see the content and tweak the cleanse logic.
Context: The ultimate goal is to build a script that could process through 6 years of my bookmarked reading and extract out keywords, so I could do some trend analysis on how my reading has changed over time and maybe later build a supervised model with that data to analyze new online posts and produce a “worth my time or not” score.
The first step was to increase my hands-on knowledge of text processing and identify potential algorithms. I used Python as the programming language, 5 sample posts from my own website, and two algorithms: TF-IDF and RAKE. I learned how these algorithms work, that data cleansing is an incredibly important step, and that python package management has trailed significantly behind most of the other languages I use day-to-day.
The code for this post is available here: https://github.com/tarwn/bookmark_analysis/tree/master/exploration/v2
Let me start with the results, then I’ll jump into the algorithms and code.
Keyword Extract Results
These results are a subset of a larger set using TF-IDF, RAKE, and TextRank for the latest 50 posts I’ve written on LessThandot. I chose a larger sample because TF-IDF relies on frequency of words found in other documents as part of the score, so I wanted a large enough pool to help it shine (or not).
Here are results for two recent posts:
RAKE: * greatly simplify future updates * self-hosted web â€“ updating assets * stop manually updating * normal debugging sessions * tiny sample project TF-IDF: * allspecs * specrunner * spec * gulp * file TextRank: * self-hosted website * vanilla bootloader * jasmine specrunner * custom bootloader * similar approach
RAKE optimizes towards long keywords, which provides accurate phrases that aren’t terribly useful as keywords. TF-IDF has pulled out some viable keywords. TextRank seems to most frequently pull out the best candidate set of the 3 by landing somewhere between the twp.
If you read the prior post, you can skip past the first two to TextRank.
TF-IDF stands for Text Frequency Inverse Document Frequency. At a high level, a TF-IDF score finds the words that have the highest ratio of occurring in the current document vs the frequency of occurring in the larger set of documents.
The code for the TF-IDF implementation was based on this post by Steven Loria.
- Candidates are extracted from the text by finding strings of words that do not include phrase delimiters or stop words (a, the, of, etc). This produces the list of candidate keywords/phrases.
- A Co-occurrence graph is built to identify the frequency that words are associated together in those phrases. Here is a good outline of how co-occurence graphs are built: Mining Twitter Data with Python (Part 4: Rugby and Term Co-occurrences)
- A score is calculated for each phrase that is the sum of the individual word’s scores from the co-occurrence graph. An individual word score is calculated as the degree (number of times it appears + number of additional words it appears with) of a word divided by it’s frequency (number of times it appears), which weights towards longer phrases.
- Adjoining keywords are included if they occur more than twice in the document and score high enough. An adjoining keyword is two keyword phrases with a stop word between them.
- The top T keywords are then extracted from the content, where T is 1/3rd of the number of words in the graph
TextRank is described in the paper TextRank: Bringing Order into Texts by Rada Mihalcea and Paul Tarau.
In general, TextRank creates a graph of the words and relationships between them from a document, then identifies the most important vertices of the graph (words) based on importance scores calculated recursively from the entire graph.
- Candidates are extracted from the text via sentence and then word parsing to produce a list of words to be evaluated. The words are annotated with part of speech tags (noun, verb, etc) to better differentiate syntactic use
- Each word is then added to the graph and relationships are added between the word and others in a sliding window around the word
- A ranking algorithm is run on each vertex for several iterations, updating all of the word scores based on the related word scores, until the scores stabilize – the research paper notes this is typically 20-30 iterations
- The words are sorted and the top N are kept (N is typically 1/3rd of the words)
- A post-processing step loops back through the initial candidate list and identifies words that appear next to one another and merges the two entries from the scored results into a single multi-word entry
I used this TextRank implementation as a base, modifying it to return the numeric score with the keywords so I could isolate the top 5 like I have for other algorithms. My solution for multi-word scores was simple addition, for no reason better than it was good enough for what I’m doing.
Making it all work
As I mentioned earlier, the initial cleansing of the data was a critical step. I wrote a small data loader that accepts a cache folder and a cleanse method and surfaces a call to load the text for a given URL.
When called, ContentLoader identifies whether HTML or processed Text content is already available, and if not, downloads and/or processes the HTML, caching the results if work was required, and returning just the text. This allows lots of fast repetition on the algorithm side when I am tweaking those, lets me see the raw html and text results of the cleanse function, and allows me to easily rerun part of thw cleanse by removing the text or HTML files.
The barebones of my logic to download content and run it through the algorithms above is:
Compared to my exploratory scripts in the prior version, now I have something easy to read and usable as the base for other projects. The cleanse method is provided as a function so the underlying contentloader isn’t tied directly to my site’s page layout and the links are gathered independently for the same reason.
TextRank provided the best results for what I’m trying to do, but seemed the slowest by a lot.
Time: At 50 documents the RAKE and TF-IDF implementations took about 2 seconds each, while TextRank took over 6.5 minutes. This is a comparison of three implementations I downloaded from the internet, though, so I’m going to dig deeper or write my own implementation of TextRank to see if I can locate the bottleneck.
Other Alternative: I also evaluated the Text Analytics option for Azure Cognitive Services. It was quick to get running and has a free tier that would be plenty for me (1000 calls/month). Unfortunately the Key Phrases API surfaces only the keywords (1/3rd of the phrases, at a guess) and not the associated scores, so it wouldn’t work for this use (which is unfortunate, parallel cloud execution would be nice to have for this project).