CHAPTER 6

Text Similarity and

Clustering

Previous chapters have covered several techniques of analyzing text and extracting interesting
insights. We have looked at supervised machine learning (ML) techniques that are used to
classify or categorize text documents into several pre-assumed categories. Unsupervised
techniques like topic models and document summarization have also been also covered,
which involved trying to extract and retrieve key themes and information from large text
documents and corpora. In this chapter, we will be looking at several other techniques and
use-cases that leverage unsupervised learning and information retrieval concepts.
If you refresh your memory of Chapter 4, text categorization is indeed an interesting
problem that has several applications, most notably in the classification of news articles
and email. But one constraint in text classification is that we need some training data with
manually labeled categories because we use supervised learning algorithms to build our
classification model. The efforts of building this dataset are definitely not easy, because
to build a good model, you need a sizeable amount of training data. For this, we need to
spend time and manual effort in labeling data, building a model, and then finally using it to
classify new documents. Can we instead make the machine do it? Yes, as a matter of fact, we
can. This chapter specifically addresses looking at the content of text documents, analyzing
their similarity using various measures, and clustering similar documents together.
Text data is unstructured and highly noisy. We get the benefits of well-labeled
training data and supervised learning when performing text classification. But document
clustering is an unsupervised learning process, where we are trying to segment and
categorize documents into separate categories by making the machine learn about the
various text documents, their features, similarities, and the differences among them.
This makes document clustering more challenging, albeit interesting. Consider having
a corpus of documents that talk about various different concepts and ideas. Humans are
wired in such a way that we use our learning from the past and apply it to distinguish
documents from each other. For example, the sentence The fox is smarter than the
dog is more similar to The fox is faster than the dog than it is to Python is an excellent
programming language. We can easily spot and intuitively figure out specific keyphrases
like Python, fox, dog, programming, and so on, which help us determine which sentences
or documents are more similar. But can we do that programmatically? In this chapter,
we will focus on several concepts related to text similarity, distance metrics, and
unsupervised ML algorithms to answer the following questions:

© Dipanjan Sarkar 2016 265

D. Sarkar, Text Analytics with Python, DOI 10.1007/978-1-4842-2388-8_6
Chapter 6 ■ Text Similarity and Clustering

• How do we measure similarity between documents?

• How can we use distance measures to find the most relevant
documents?
• When is a distance measure called a metric?
• How do we cluster or group similar documents?
• Can we visualize document clusters?
Although we will be focused on trying to answer these questions, we will cover
essential concepts and information needed to understand various techniques for
solving these problems. We will also use some practical examples to illustrate concepts
related to text similarity, distance metrics, and document clustering. Also, many of these
techniques can be combined with some of the techniques we learned previously and
vice versa. For example, concepts of text similarity using distance metrics are also used
to build document clusters. You can also use features from topic models for measuring
text similarity. Besides this, clustering is often a starting point to get a feel for the possible
groups or categories that your data might consist of, or to even visualize these clusters
or groups of similar text documents. This can then be plugged in to other systems
like supervised classification systems, or you can even combine them both and build
weighted classifiers. The possibilities are indeed endless!
In this chapter, we will first cover some important concepts related to distance
measures, metrics, and unsupervised learning and brush up on text normalization and
feature extraction. Once the basics are covered, our objective will be to understand and
analyze term similarity, document similarity, and finally document clustering.

Important Concepts
Our main objectives in this chapter are to understand text similarity and clustering.
Before moving on to the actual techniques and algorithms, this section will discuss some
important concepts related to information retrieval, document similarity measures, and
machine learning. Even though some of these concepts might be familiar to you from the
previous chapters, all of them will be useful to us as we gradually journey through this
chapter. Without further ado, let’s get started.

Information Retrieval (IR)

Information retrieval (IR) is the process of retrieving or fetching relevant sources of
information from a corpus or set of entities that hold information based on some
demand. For example, it could be a query or search that users enter in a search engine
and then get relevant search items pertaining to their query. In fact, search engines are
the most popular use-case or application of IR.
The relevancy of documents with information compared to the demand can
be measured in several ways. It can include looking for specific keywords from the
search text or using some similarity measures to see the similarity rank or score of the
documents with respect to the entered query. This makes is quite different from string
matching or matching regular expressions because more than often the words in a search

266
 Chapter 6 ■ Text Similarity and Clustering

string can have different order, context, and semantics in the collection of documents
(entities), and these words can even have multiple different resolutions or possibilities
based on synonyms, antonyms, and negation modifiers.

Feature Engineering
Feature engineering or feature extraction is something which you know quite well by
now. Methods like Bag of Words, TF-IDF, and word vectorization models are typically
used to represent or model documents in the form of numeric vectors so that applying
mathematical or machine learning techniques become much easier. You can use various
document representations using these feature-extraction techniques or even map each
letter or a word to a corresponding unique numeric identifier.

Similarity Measures
Similarity measures are used frequently in text similarity analysis and clustering. Any
similarity or distance measure usually measures the degree of closeness between two
entities, which can be any text format like documents, sentences, or even terms. This
measure of similarity can be useful in identifying similar entities and distinguishing
clearly different entities from each other. Similarity measures are very effective, and
sometimes choosing the right measure can make a lot of difference in the performance
of your final analytics system. Various scoring or ranking algorithms have also been
invented based on these distance measures. Two main factors determine the degree of
similarity between entities:
• Inherent properties or features of the entities
• Measure formula and properties
There are several distance measures that measure similarity, and we will be covering
several of them in future sections. However, an important thing to remember is that all
distance measures of similarity are not distance metrics of similarity. The excellent paper
by A. Huang, “Similarity Measures for Text Document Clustering,” talks about this in
detail. Consider a distance measure d and two entities (say they are documents in our
context) x and y. The distance between x and y, which is used to determine the degree of
similarity between them, can be represented as d(x, y), but the measure d can be called as
a distance metric of similarity if and only if it satisfies the following four conditions:
1. The distance measured between any two entities, say x and y,
must be always non-negative, that is, d ( x , y ) ³ 0 .
2. The distance between two entities should always be zero if
and only if they are both identical, that is, d ( x , y ) ³ 0 iff x = y .
3. This distance measure should always be symmetric, which
means that the distance from x to y is always the same as the
distance from y to x. Mathematically this is represented as
d (x, y ) = d ( y, x ) .

267
Chapter 6 ■ Text Similarity and Clustering

4. This distance measure should satisfy the triangle inequality

property, which can be mathematically represented
d (x, z) £ d (x, y ) + d ( y, z) .
This tells us important criteria and gives us a good framework we can use to check
whether a distance measure can be used as a distance metric for measuring similarity. I
don’t have room here to go into more detail, but you may be interested in knowing that
the very popular KL-divergence measure, also known as Kullback-Leibler divergence, is
a distance measure that violates the third property, where this measure is asymmetric,
hence it kind of does not make sense to use it as a measure of similarity for text
documents—but otherwise, this is extremely useful in differentiating between various
distributions and patterns.

Unsupervised Machine Learning Algorithms

Unsupervised machine learning algorithms are the family of ML algorithms that try to
discover latent hidden structures and patterns in data from their various attributes and
features. Besides this, several unsupervised learning algorithms are also used to reduce
the feature space, which is often of a higher dimension to one with a lower dimension.
The data on which these algorithms operate is essentially unlabeled data that does not
have any pre-determined category or class. We apply these algorithms with the intent
of finding patterns and distinguishing features that might help us in grouping various
data points into groups or clusters. These algorithms are popularly known as clustering
algorithms. Even the topic models covered in Chapter 5 belong to the unsupervised
learning family of algorithms.
This concludes our discussion on the important concepts and background
information necessary for this chapter. We will now move on to a brief coverage of text
normalization and feature extraction, where we introduce a few things which are specific
to this chapter.

Text Normalization
We will need to normalize our text documents and corpora as usual before we perform
any further analyses or NLP. For this we will reuse our normalization module from
Chapter 5 but with a few more additions specifically aimed toward this chapter. The
complete normalization module is available in the code files for this chapter in the file
[Link], but I will still be highlighting the new additions in our normalization
module in this section for your benefit.
To start, we have updated our stopwords list with several new words that have been
carefully selected after analyzing many corpora. The following code snippet illustrates:

stopword_list = [Link]('english')
stopword_list = stopword_list + ['mr', 'mrs', 'come', 'go', 'get', 'tell',
'listen', 'one', 'two', 'three', 'four', 'five',
'six', 'seven', 'eight',
'nine', 'zero', 'join', 'find', 'make', 'say', 'ask',
'tell', 'see', 'try', 'back', 'also']

268
 Chapter 6 ■ Text Similarity and Clustering

You can see the new additions are words that are mostly generic verbs or nouns without
a lot of significance. This will be useful to us in feature extraction during text clustering. We
also add a new function in our normalization pipeline, which is to only extract text tokens
from a body of text for which we use regular expressions, as depicted in the following function:

import re

def keep_text_characters(text):
    filtered_tokens = []
    tokens = tokenize_text(text)
    for token in tokens:
        if [Link]('[a-zA-Z]', token):
            filtered_tokens.append(token)
    filtered_text = ' '.join(filtered_tokens)
    return filtered_text

We add this in our final normalization function along with the other functions that
we have reused from previous chapters, including expanding contractions, unescaping
HTML, tokenization, removing stopwords, special characters, and lemmatization. The
updated normalization function is shown in the following snippet:

def normalize_corpus(corpus, lemmatize=True,

                     only_text_chars=False,
                     tokenize=False):

    normalized_corpus = []    
    for text in corpus:
        text = html_parser.unescape(text)
        text = expand_contractions(text, CONTRACTION_MAP)
        if lemmatize:
            text = lemmatize_text(text)
        else:
            text = [Link]()
        text = remove_special_characters(text)
        text = remove_stopwords(text)
        if only_text_chars:
            text = keep_text_characters(text)

        if tokenize:
            text = tokenize_text(text)
            normalized_corpus.append(text)
        else:
            normalized_corpus.append(text)

    return normalized_corpus

Thus, as you can see, the preceding function is very similar to the one from Chapter 5
with only the addition of keeping text characters using the keep_text_characters()
function, which can be executed by setting the only_text_chars parameter to True.

269
Chapter 6 ■ Text Similarity and Clustering

Feature Extraction
We will also be using a feature-extraction function similar to the one used in Chapter 5.
The code will be very similar to our previous feature extractor, except we will be adding
some new parameters in this chapter. The function can be found in the [Link] file and
is also shown in the following snippet:

from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizer

def build_feature_matrix(documents, feature_type='frequency',

                         ngram_range=(1, 1), min_df=0.0, max_df=1.0):

    feature_type = feature_type.lower().strip()  

    if feature_type == 'binary':

        vectorizer = CountVectorizer(binary=True, min_df=min_df,
                                     max_df=max_df, ngram_range=ngram_range)
    elif feature_type == 'frequency':
        vectorizer = CountVectorizer(binary=False, min_df=min_df,
                                     max_df=max_df, ngram_range=ngram_range)
    elif feature_type == 'tfidf':
        vectorizer = TfidfVectorizer(min_df=min_df, max_df=max_df,
                                     ngram_range=ngram_range)
    else:
        raise Exception("Wrong feature type entered. Possible values:
'binary', 'frequency',  
                         'tfidf'")

    feature_matrix = vectorizer.fit_transform(documents).astype(float)

    return vectorizer, feature_matrix

You can see from the function definition that we have capabilities for Bag of Words
frequency, occurrences, and also TF-IDF–based features. The new additions in this
function include the addition of the min_df, max_df and ngram_range parameters and
also accepting them as optional arguments. The ngram_range is useful when we want
to add bigrams, trigrams, and so on as additional features. The min_df parameter can
be expressed by a threshold value within a range of [0.0, 1.0] and it will ignore terms
as features that will have a document frequency strictly lower than the input threshold
value. The max_df parameter can also be expressed by a threshold value within a range
of [0.0, 1.0] and it will ignore terms as features that will have a document frequency
strictly higher than the input threshold value. The intuition behind this would be that
these words, if they occur in almost all the documents, tend to have little value that would
help us in distinguishing among various types of documents. We will now deep dive into
the various techniques for text similarity.

270
 Chapter 6 ■ Text Similarity and Clustering

Text Similarity
The main objective of text similarity is to analyze and measure how two entities of text are
close or far apart from each other. These entities of text can be simple tokens or terms,
like words, or whole documents, which may include sentences or paragraphs of text.
There are various ways of analyzing text similarity, and we can classify the intent of text
similarity broadly into the following two areas:
• Lexical similarity: This involves observing the contents of the
text documents with regard to syntax, structure, and content and
measuring their similarity based on these parameters.
• Semantic similarity: This involves trying to find out the semantics,
meaning, and context of the documents and then trying to see
how close they are to each other. Dependency grammars and
entity recognition are handy tools that can help in this.
Note that the most popular area is lexical similarity, because the techniques
are more straightforward, easy to implement, and you can also cover several parts of
semantic similarity using simple models like the Bag of Words. Usually distance metrics
will be used to measure similarity scores between text entities, and we will be mainly
covering the following two broad areas of text similarity:
• Term similarity: Here we will measure similarity between
individual tokens or words.
• Document similarity: Here we will be measuring similarity
between entire text documents.
The idea is to implement and use several distance metrics and see how we can
measure and analyze similarity among entities that are just simple words, and then
how things change when we measure similarity among documents that are groups of
individual words.

Analyzing Term Similarity

We will start with analyzing term similarity—or similarity between individual word
tokens, to be more precise. Even though this is not used a lot in practical applications,
it can be used as an excellent starting point for understanding text similarity. Of course,
several applications and use-cases like autocompleters, spell check, and correctors use
some of these techniques to correct misspelled terms. Here we will be taking a couple of
words and measuring the similarity between then using different word representations as
well as distance metrics. The word representations we will be using are as follows:
• Character vectorization
• Bag of Characters vectorization

271
Chapter 6 ■ Text Similarity and Clustering

For character vectorization, it is an extremely simple process of just mapping each

character of the term to a corresponding unique number. We can do that using the
function depicted in the following snippet:

import numpy as np

def vectorize_terms(terms):
    terms = [[Link]() for term in terms]
    terms = [[Link](list(term)) for term in terms]
    terms = [[Link]([ord(char) for char in term])
                for term in terms]
    return terms

The function takes input a list of words or terms and returns the corresponding
character vectors for the words. Bag of Characters vectorization is very similar to the Bag
of Words model except here we compute the frequency of each character in the word.
Sequence or word orders are not taken into account. The following function helps in
computing this:

from [Link] import itemfreq

def boc_term_vectors(word_list):
    word_list = [[Link]() for word in word_list]
    unique_chars = [Link](
                        [Link]([list(word)
                        for word in word_list]))
    word_list_term_counts = [{char: count for char, count in
itemfreq(list(word))}
                             for word in word_list]

    boc_vectors = [[Link]([int(word_term_counts.get(char, 0))

                            for char in unique_chars])
                   for word_term_counts in word_list_term_counts]
    return list(unique_chars), boc_vectors

In that function, we take in a list of words or terms and then extract the unique
characters from all the words. This becomes our feature list, just like we do in Bag of
Words, where instead of characters, unique words are our features. Once we have this list
of unique_chars, we get the count for each of the characters in each word and build our
Bag of Characters vectors.
We can now see our previous functions in action in the following snippet. We will be
using a total of four example terms and computing the similarity among them later on:

root = 'Believe'
term1 = 'beleive'
term2 = 'bargain'
term3 = 'Elephant'    

272
 Chapter 6 ■ Text Similarity and Clustering

terms = [root, term1, term2, term3]

# Character vectorization
vec_root, vec_term1, vec_term2, vec_term3 = vectorize_terms(terms)
# show vector representations
In [103]: print '''
     ...: root: {}
     ...: term1: {}
     ...: term2: {}
     ...: term3: {}
     ...: '''.format(vec_root, vec_term1, vec_term2, vec_term3)
root: [ 98 101 108 105 101 118 101]
term1: [ 98 101 108 101 105 118 101]
term2: [ 98  97 114 103  97 105 110]
term3: [101 108 101 112 104  97 110 116]

# Bag of characters vectorization

features, (boc_root, boc_term1, boc_term2, boc_term3) = boc_term_
vectors(terms)
# show features and vector representations
In [105]: print 'Features:', features
     ...: print '''
     ...: root: {}
     ...: term1: {}
     ...: term2: {}
     ...: term3: {}
     ...: '''.format(boc_root, boc_term1, boc_term2, boc_term3)
Features: ['a', 'b', 'e', 'g', 'h', 'i', 'l', 'n', 'p', 'r', 't', 'v']

root: [0 1 3 0 0 1 1 0 0 0 0 1]
term1: [0 1 3 0 0 1 1 0 0 0 0 1]
term2: [2 1 0 1 0 1 0 1 0 1 0 0]
term3: [1 0 2 0 1 0 1 1 1 0 1 0]

Thus you can see how we can easily transform text terms into numeric vector
representations. We will now be using several distance metrics to compute similarity
between the root word and the other three words mentioned in the preceding snippet.
There are a lot of distance metrics out there that you can use to compute and measure
similarities. We will be covering the following five metrics in this section:
• Hamming distance
• Manhattan distance
• Euclidean distance
• Levenshtein edit distance
• Cosine distance and similarity

273
Chapter 6 ■ Text Similarity and Clustering

We will be looking at the concepts for each distance metric and using the power of
numpy arrays to implement the necessary computations and mathematical formulae.
Once we do that, we will put them in action by measuring the similarity of our example
terms. First, though, we will set up some necessary variables storing the root term,
the other terms with which its similarity will be measures, and their various vector
representations using the following snippet:

root_term = root
root_vector = vec_root
root_boc_vector = boc_root

terms = [term1, term2, term3]

vector_terms = [vec_term1, vec_term2, vec_term3]
boc_vector_terms = [boc_term1, boc_term2, boc_term3]

We are now ready to start computing similarity metrics and will be using the
preceding terms and their vector representations to measure similarities.

Hamming Distance
The Hamming distance is a very popular distance metric used frequently in information
theory and communication systems. It is distance measured between two strings under
the assumption that they are of equal length. Formally, it is defined as the number of
positions that have different characters or symbols between two strings of equal length.
Considering two terms u and v of length n, we can mathematically denote Hamming
distance as

n
hd ( u , v ) = å ( ui ¹ vi )
i =1

and you can also normalize it if you want by dividing the number of mismatches by the
total length of the terms to give the normalized hamming distance, which is represented
as

å (u i ¹ vi )
norm _ hd ( u , v ) = i =1
n

whereas you already know n denotes the length of the terms.

The following function computes the Hamming distance between two terms and
also has the capability to compute the normalized distance:

def hamming_distance(u, v, norm=False):

    if [Link] != [Link]:
        raise ValueError('The vectors must have equal lengths.')
    return (u != v).sum() if not norm else (u != v).mean()

274
 Chapter 6 ■ Text Similarity and Clustering

We will now measure the Hamming distance between our root term and the other
terms using the following code snippet:

# compute Hamming distance

In [115]: for term, vector_term in zip(terms, vector_terms):
     ...:     print 'Hamming distance between root: {} and term: {} is {}'.
format(root_term,
     ...:                      term, hamming_distance(root_vector, vector_
term, norm=False))

Hamming distance between root: Believe and term: believe is 2

Hamming distance between root: Believe and term: bargain is 6
Traceback (most recent call last):
  File "<ipython-input-115-3391bd2c4b7e>", line 4, in <module>
    hamming_distance(root_vector, vector_term, norm=False))
ValueError: The vectors must have equal lengths.

# compute normalized Hamming distance

In [117]: for term, vector_term in zip(terms, vector_terms):
     ...:     print 'Normalized Hamming distance between root: {} and term:
{} is
     ...:                                              {}'.format(root_term,
term,
     ...:             round(hamming_distance(root_vector, vector_term,
norm=True), 2))

Normalized Hamming distance between root: Believe and term: believe is 0.29
Normalized Hamming distance between root: Believe and term: bargain is 0.86
Traceback (most recent call last):
  File "<ipython-input-117-7dfc67d08c3f>", line 4, in <module>
    round(hamming_distance(root_vector, vector_term, norm=True), 2))
ValueError: The vectors must have equal lengths

You can see from the preceding output that terms 'Believe' and 'believe'
ignoring their case are most similar to each other with the Hamming distance of 2 or 0.29,
compared to the term 'bargain' giving scores of 6 or 0.86 (here, the smaller the score,
the more similar are the terms). The term 'Elephant' throws an exception because the
length of that term (term3) is 8 compared to length 7 of the root term 'Believe', hence
Hamming distance can’t be computed because the base assumption of strings being of
equal length is violated.

Manhattan Distance
The Manhattan distance metric is similar to the Hamming distance conceptually, where
instead of counting the number of mismatches, we subtract the difference between each
pair of characters at each position of the two strings. Formally, Manhattan distance is
also known as city block distance, L1 norm, taxicab metric and is defined as the distance

275
Chapter 6 ■ Text Similarity and Clustering

between two points in a grid based on strictly horizontal or vertical paths instead of
the diagonal distance conventionally calculated by the Euclidean distance metric.
Mathematically it can be denoted as

n
md ( u , v ) = u - v 1 = å ui - vi
i =1

where u and v are the two terms of length n. The same assumption of the two terms
having equal length from Hamming distance holds good here. We can also compute the
normalized Manhattan distance by dividing the sum of the absolute differences by the
term length. This can be denoted by

u -v å u -v i i
norm _ md ( u , v ) = 1
= i =1
n n

where n is the length of each of the terms u and v. The following function helps us in
implementing Manhattan distance with the capability to also compute the normalized
Manhattan distance:

def manhattan_distance(u, v, norm=False):

    if [Link] != [Link]:
        raise ValueError('The vectors must have equal lengths.')
    return abs(u - v).sum() if not norm else abs(u - v).mean()

We will now compute the Manhattan distance between our root term and the other
terms using the previous function, as shown in the following code snippet:

# compute Manhattan distance

In [120]: for term, vector_term in zip(terms, vector_terms):
     ...:     print 'Manhattan distance between root: {} and term: {} is
{}'.format(root_term,
     ...:                      term, manhattan_distance(root_vector,
vector_term, norm=False))

Manhattan distance between root: Believe and term: believe is 8

Manhattan distance between root: Believe and term: bargain is 38
Traceback (most recent call last):
  File "<ipython-input-120-b228f24ad6a2>", line 4, in <module>
    manhattan_distance(root_vector, vector_term, norm=False))
ValueError: The vectors must have equal lengths.

# compute normalized Manhattan distance

In [122]: for term, vector_term in zip(terms, vector_terms):
     ...:     print 'Normalized Manhattan distance between root: {} and
term: {} is {}'.format(root_term,

276
 Chapter 6 ■ Text Similarity and Clustering

     ...:              term,
     ...:              round(manhattan_distance(root_vector, vector_term,
norm=True),2))
     ...:
     ...:
Normalized Manhattan distance between root: Believe and term: believe is 1.14
Normalized Manhattan distance between root: Believe and term: bargain is 5.43
Traceback (most recent call last):
  File "<ipython-input-122-d13a48d56a22>", line 4, in <module>
    round(manhattan_distance(root_vector, vector_term, norm=True),2))
ValueError: The vectors must have equal lengths.

From those results you can see that as expected, the distance between 'Believe'
and 'believe' ignoring their case is most similar to each other, with a score of 8 or
1.14, as compared to 'bargain', which gives a score of 38 or 5.43 (here the smaller the
score, the more similar the words). The term 'Elephant' yields an error because it has
a different length compared to the base term just as we noticed earlier when computing
Hamming distances.

Euclidean Distance
We briefly mentioned the Euclidean distance when comparing it with the Manhattan
distance in the earlier section. Formally, the Euclidean distance is also known as the
Euclidean norm, L2 norm, or L2 distance and is defined as the shortest straight-line
distance between two points. Mathematically this can be denoted as

n
ed ( u , v ) = u - v 2 = å (u - v )
2
i i
i =1

where the two points u and v are vectorized text terms in our scenario, each having
length n. The following function helps us in computing the Euclidean distance between
two terms:

def euclidean_distance(u, v):

    if [Link] != [Link]:
        raise ValueError('The vectors must have equal lengths.')
    distance = [Link]([Link]([Link](u - v)))
    return distance

We can now compare the Euclidean distance among our terms by using the
preceding function as depicted in the following code snippet:

# compute Euclidean distance

In [132]: for term, vector_term in zip(terms, vector_terms):
     ...:     print 'Euclidean distance between root: {} and term: {} is
{}'.format(root_term,
     ...:                         term, round(euclidean_distance(root_
vector, vector_term),2))
277
Chapter 6 ■ Text Similarity and Clustering

Euclidean distance between root: Believe and term: believe is 5.66

Euclidean distance between root: Believe and term: bargain is 17.94
Traceback (most recent call last):
  File "<ipython-input-132-90a4dbe8ce60>", line 4, in <module>
    round(euclidean_distance(root_vector, vector_term),2))
ValueError: The vectors must have equal lengths.

From the preceding outputs you can see that the terms 'Believe' and 'believe'
are the most similar with a score of 5.66 compared to 'bargain' giving us a score of 17.94,
and 'Elephant' throws a ValueError because the base assumption that strings being
compared should have equal lengths holds good for this distance metric also.
So far, all the distance metrics we have used work on strings or terms of the same
length and fail when they are not of equal length. So how do we deal with this problem?
We will now look at a couple of distance metrics that work even with strings of unequal
length to measure similarity.

Levenshtein Edit Distance

The Levenshtein edit distance, often known as just Levenshtein distance, belongs to the
family of edit distance–based metrics and is used to measure the distance between two
sequence of strings based on their differences—similar to the concept behind Hamming
distance. The Levenshtein edit distance between two terms can be defined as the
minimum number of edits needed in the form of additions, deletions, or substitutions
to change or convert one term to the other. These substitutions are character-based
substitutions, where a single character can be edited in a single operation. Also, as
mentioned before, the length of the two terms need not be equal here. Mathematically,
we can represent the Levenshtein edit distance between two terms as ldu, v(|u|, |v|) such
that u and v are our two terms where |u| and |v| are their lengths. This distance can be
represented by the following formula

ìmax ( i ,j ) if min ( i ,j ) = 0 ü
ï ï
ï ì ldu ,v ( i - 1, j ) + 1 ü ï
ldu ,v ( i ,j ) = í ï ï ý
ïmin í ldu ,v ( i , j - 1 ) + 1 ý otherwise ï
ï ïld ( i - 1, j - 1) + C ï ï
î î u ,v ui ¹ v j þ þ

where i and j are basically indices for the terms u and v. The third equation in the minimum
above has a cost function denoted by Cui ¹ v j such that it has the following conditions

ïì 1 if ui ¹ v j ïü
Cui ¹ v j = í ý
îï0 if ui = v j þï

and this denotes the indicator function, which depicts the cost associated with two
characters being matched for the two terms (the equation represents the match or
mismatch operation). The first equation in the previous minimum stands for the deletion

278
 Chapter 6 ■ Text Similarity and Clustering

operation, and the second equation represents the insertion operation. The function
ldu, v(i, j) thus covers all the three operations of insertion, deletion, and addition as we
mentioned earlier and it denotes the Levenshtein distance as measured between the first
i characters for the term u and the first j characters of the term v. There are also several
interesting boundary conditions with regard to the Levenshtein edit distance:
• The minimum value that the edit distance between two terms can
take is the difference in length of the two terms.
• The maximum value of the edit distance between two terms can
be the length of the term that is larger.
• If the two terms are equal, the edit distance is zero.
• Hamming distance between two terms is an upper bound for
Levenshtein edit distance if and only if the two terms have equal
length.
• This being a distance metric also satisfies the triangle inequality
property, discussed earlier when we talked about distance
metrics.
There are various ways of implementing Levenshtein distance computations for
terms. Here we will start with an example of two of our terms. Considering the root term
'believe' and another term 'beleive' (we ignore case in our computations). The edit
distance would be 2 because we would need the following two operations:
• 'beleive' → 'beliive' (substitution of e to i)
• 'beliive' → 'believe' (substitution of i to e)
To implement this, we build a matrix that will basically compute the Levenshtein
distance between all the characters of both terms by comparing each character of the
first term with the characters of the second term. For computation, we follow a dynamic
programming approach to get the edit distance between the two terms based on the
last computed value. For the given two terms, the Levenshtein edit distance matrix our
algorithm should generate is shown in Figure 6-1.

Figure 6-1. Levenshtein edit distance matrix between terms

279
Chapter 6 ■ Text Similarity and Clustering

You can see in Figure 6-1 that the edit distances are computed for each pair of
characters in the terms, as mentioned earlier, and the final edit distance value highlighted
in the figure gives us the actual edit distance between the two terms. This algorithm is
also known as the Wagner-Fischer algorithm and is available in the paper by R. Wagner
and M. Fischer titled “The String-to-String Correction Problem,” which you can refer to
if you are more interested in the details. The pseudocode for the same is shown in the
snippet below, courtesy of the paper:

function levenshtein_distance(char u[1..m], char v[1..n]):

# for all i and j, d[i,j] will hold the Levenshtein distance between the
first i characters of  
# u and the first j characters of v, note that d has (m+1)*(n+1) values
int d[0..m, 0..n]

# set each element in d to zero

d[0..m, 0..n] := 0

# source prefixes can be transformed into empty string by dropping all

characters
for i from 1 to m:
   d[i, 0] := i

# target prefixes can be reached from empty source prefix by inserting every
character
for j from 1 to n:
    d[0, j] := j

# build the edit distance matrix

for j from 1 to n:
    for i from 1 to m:
        if s[i] = t[j]:
            substitutionCost := 0
        else:
            substitutionCost := 1
            d[i, j] := minimum(d[i-1, j] + 1,                   # deletion
                               d[i, j-1] + 1,                   # insertion
                               d[i-1, j-1] + substitutionCost)  # substitution

# the final value of the matrix is the edit distance between the terms
return d[m, n]

You can see from the preceding function definition pseudocode how we have
captured the necessary formulae we used earlier to define Levenshtein edit distance.
We will now implement this pseudocode in Python. The preceding algorithm uses
O(mn) space because it stores the entire distance matrix, but it is enough to just store the
previous and current row of distances to get to the final result. We will do the same in our
code but we will also store the results in a matrix so that we can visualize it in the end. The
following function implements Levenshtein edit distance as mentioned:

280
 Chapter 6 ■ Text Similarity and Clustering

import copy
import pandas as pd

def levenshtein_edit_distance(u, v):

    # convert to lower case
    u = [Link]()
    v = [Link]()
    # base cases
    if u == v: return 0
    elif len(u) == 0: return len(v)
    elif len(v) == 0: return len(u)
    # initialize edit distance matrix
    edit_matrix = []
    # initialize two distance matrices
    du = [0] * (len(v) + 1)
    dv = [0] * (len(v) + 1)
    # du: the previous row of edit distances
    for i in range(len(du)):
        du[i] = i
    # dv : the current row of edit distances    
    for i in range(len(u)):
        dv[0] = i + 1
        # compute cost as per algorithm
        for j in range(len(v)):
            cost = 0 if u[i] == v[j] else 1
            dv[j + 1] = min(dv[j] + 1, du[j + 1] + 1, du[j] + cost)
        # assign dv to du for next iteration
        for j in range(len(du)):
            du[j] = dv[j]
        # copy dv to the edit matrix
        edit_matrix.append([Link](dv))
    # compute the final edit distance and edit matrix    
    distance = dv[len(v)]
    edit_matrix = [Link](edit_matrix)
    edit_matrix = edit_matrix.T
    edit_matrix = edit_matrix[1:,]
    edit_matrix = [Link](data=edit_matrix,
                               index=list(v),
                               columns=list(u))
    return distance, edit_matrix

That function returns both the final Levenshtein edit distance and the complete edit
matrix between the two terms u and v, which are taken as input. Remember, we need to
pass the terms directly in their raw string format and not their vector representations.
Also, we do not consider case of strings here and convert them to lowercase.
The following snippet computes the Levenshtein edit distance between our example
terms using the preceding function:

281
Chapter 6 ■ Text Similarity and Clustering

In [223]: for term in terms:

     ...:     edit_d, edit_m = levenshtein_edit_distance(root_term, term)
     ...:     print 'Computing distance between root: {} and term: {}'.
format(root_term,
     ...:                                                             term)
     ...:     print 'Levenshtein edit distance is {}'.format(edit_d)
     ...:     print 'The complete edit distance matrix is depicted below'
     ...:     print edit_m
     ...:     print '-'*30    

Computing distance between root: Believe and term: beleive

Levenshtein edit distance is 2
The complete edit distance matrix is depicted below
   b  e  l  i  e  v  e
b  0  1  2  3  4  5  6
e  1  0  1  2  3  4  5
l  2  1  0  1  2  3  4
e  3  2  1  1  1  2  3
i  4  3  2  1  2  2  3
v  5  4  3  2  2  2  3
e  6  5  4  3  2  3  2
------------------------------
Computing distance between root: Believe and term: bargain
Levenshtein edit distance is 6
The complete edit distance matrix is depicted below
   b  e  l  i  e  v  e
b  0  1  2  3  4  5  6
a  1  1  2  3  4  5  6
r  2  2  2  3  4  5  6
g  3  3  3  3  4  5  6
a  4  4  4  4  4  5  6
i  5  5  5  4  5  5  6
n  6  6  6  5  5  6  6
------------------------------
Computing distance between root: Believe and term: Elephant
Levenshtein edit distance is 7
The complete edit distance matrix is depicted below
   b  e  l  i  e  v  e
e  1  1  2  3  4  5  6
l  2  2  1  2  3  4  5
e  3  2  2  2  2  3  4
p  4  3  3  3  3  3  4
h  5  4  4  4  4  4  4
a  6  5  5  5  5  5  5
n  7  6  6  6  6  6  6
t  8  7  7  7  7  7  7
------------------------------

282
 Chapter 6 ■ Text Similarity and Clustering

You can see from the preceding outputs that 'Believe' and 'beleive' are the
closest to each other, with an edit distance of 2 and the distances between 'Believe',
'bargain', and 'Elephant' are 6, indicating a total of 6 edit operations needed. The edit
distance matrices provide a more detailed insight into how the algorithm computes the
distances per iteration.

Cosine Distance and Similarity

The Cosine distance is a metric that can be actually derived from the Cosine similarity and
vice versa. Considering we have two terms such that they are represented in their
vectorized forms, Cosine similarity gives us the measure of the cosine of the angle
between them when they are represented as non-zero positive vectors in an inner
product space. Thus term vectors having similar orientation will have scores closer to 1
( cos0 ) indicating the vectors are very close to each other in the same direction (near to
zero degree angle between them). Term vectors having a similarity score close to 0
( cos90 ) indicate unrelated terms with a near orthogonal angle between then. Term
vectors with a similarity score close to –1 ( cos180 ) indicate terms that are completely
oppositely oriented to each other. Figure 6-2 illustrates this more clearly, where u and v
are our term vectors in the vector space.

Figure 6-2. Cosine similarity representations for term vectors

Thus you can see from the position of the vectors, the plots show more clearly how
the vectors are close or far apart from each other, and the cosine of the angle between
them gives us the Cosine similarity metric. Now we can formally define Cosine similarity
as the dot product of the two term vectors u and v, divided by the product of their L2
norms. Mathematically, we can represent the dot product between two vectors as

u × v = u v cos (q )

where θ is the angle between u and v and u represents the L2 norm for vector u and v
is the L2 norm for vector v. Thus we can derive the Cosine similarity from the above
formula as

283
Chapter 6 ■ Text Similarity and Clustering

u ×v åu v i i
cs ( u , v ) = cos (q ) = = i =1
u v n n

åu åv
i =1
2
i
i =1
2
i

where cs(u, v) is the Cosine similarity score between u and v. Here ui and vi are the
various features or components of the two vectors, and the total number of these features
or components is n. In our case, we will be using the Bag of Characters vectorization to
build these term vectors, and n will be the number of unique characters across the terms
under analysis. An important thing to note here is that the Cosine similarity score usually
ranges from –1 to +1, but if we use the Bag of Characters–based character frequencies for
terms or Bag of Words–based word frequencies for documents, the score will range from 0
to 1 because the frequency vectors can never be negative, and hence the angle between
the two vectors cannot exceed 90 . The Cosine distance is complimentary to the
similarity score can be computed by the formula,

u ×v åu v i i
cd ( u , v ) = 1 - cs ( u , v ) = 1 - cos (q ) = 1 - = 1- i =1
u v n n

åu åv
i =1
2
i
i =1
2
i

where cd(u, v) denotes the Cosine distance between the term vectors u and v. The
following function implements computation of Cosine distance based on the preceding
formulae:

def cosine_distance(u, v):

    distance = 1.0 - ([Link](u, v) /
                        
([Link](sum([Link](u))) * [Link](sum(np.
square(v))))
                     )
    return distance

We will now test the similarity between our example terms using their Bag of
Character representations, which we created earlier, available in the boc_root_vector
and the boc_vector_terms variables, as depicted in the following code snippet:

In [235]: for term, boc_term in zip(terms, boc_vector_terms):

     ...:     print 'Analyzing similarity between root: {} and term: {}'.
format(root_term,
     ...:                                                            term)
     ...:     distance = round(cosine_distance(root_boc_vector, boc_term),2)
     ...:     similarity = 1 - distance                                   
     ...:     print 'Cosine distance  is {}'.format(distance)
     ...:     print 'Cosine similarity  is {}'.format(similarity)
     ...:     print '-'*40

284
 Chapter 6 ■ Text Similarity and Clustering

Analyzing similarity between root: Believe and term: believe

Cosine distance  is -0.0
Cosine similarity  is 1.0
----------------------------------------
Analyzing similarity between root: Believe and term: bargain
Cosine distance  is 0.82
Cosine similarity  is 0.18
----------------------------------------
Analyzing similarity between root: Believe and term: Elephant
Cosine distance  is 0.39
Cosine similarity  is 0.61
----------------------------------------

These vector representations do not take order of characters into account, hence
the similarity between the terms "Believe" and "believe" is 1.0 or a perfect 100 percent
because it contains the same characters with the same frequency. You can see how this
can be used in combination with a semantic dictionary like WordNet to provide correct
spelling suggestions by suggesting semantically and syntactically correct words from
a vocabulary when users type a misspelled word, by measuring the similarity between
the words. You can even try our different features here instead of single character
frequencies, like taking two characters at a time and computing their frequencies to build
the term vectors. This takes into account some of the sequences that characters maintain
in various terms. Try out different possibilities and compare the results! This distance
measure works very well when measuring similarity between large documents or
sentences, and we will see that in the next section when we discuss document similarity.

Analyzing Document Similarity

We analyzed similarity between terms using various similarity and distance metrics in
the previous sections. We also saw how vectorization was useful so that mathematical
computations become much easier, especially when computing distances between
vectors. In this section, we will try to analyze similarities between documents. By now,
you must already know that a document is defined as a body of text which can be
comprised of sentences or paragraphs of text. For analyzing document similarity, we will
be using our utils module to extract features from document using the build_feature_
matrix() function. We will vectorize documents using their TF-IDFs similarly to what
we did previously when we classified text documents or summarized entire documents.
Once we have the vector representations of the various documents, we will compute
similarity between the documents using several distance or similarity metrics. The
metrics we will cover in this section are as follows:
• Cosine similarity
• Hellinger-Bhattacharya distance
• Okapi BM25 ranking

285
Chapter 6 ■ Text Similarity and Clustering

As usual, we will cover the concepts behind each metric, look at its mathematical
representations and definitions, and then implement it using Python. We will also test
our metrics on a toy corpus here with nine documents and a separate corpus with three
documents, which will be our query documents. For each of these three documents, we
will try to find out the most similar documents from the corpus of nine documents, which
will act as our index. Consider this to be a mini-simulation of what happens in a search
engine when you search with a sentence and the most relevant results are returned to you
from its index of web pages. In our case, the queries are in the form of three documents,
and relevant documents for each of these three will be returned from the index of nine
documents based on similarity metrics.
We will start with loading the necessary dependencies and the corpus of documents
on which we will be testing our various metrics, as shown in the following code snippet:

from normalization import normalize_corpus

from utils import build_feature_matrix
import numpy as np

# load the toy corpus index

toy_corpus = ['The sky is blue',
'The sky is blue and beautiful',
'Look at the bright blue sky!',
'Python is a great Programming language',
'Python and Java are popular Programming languages',
'Among Programming languages, both Python and Java are the most used in
Analytics',
'The fox is quicker than the lazy dog',
'The dog is smarter than the fox',
'The dog, fox and cat are good friends']

# load the docs for which we will be measuring similarities

query_docs = ['The fox is definitely smarter than the dog',
            'Java is a static typed programming language unlike Python',
            'I love to relax under the beautiful blue sky!']  

From that snippet you can see that we have various documents in our corpus index
that talk about the sky, programming languages, and animals. We also have three query
documents for which we want to get the most relevant documents from the toy_corpus
index, based on similarity computations. Before we start looking at metrics, we will
normalize the documents and vectorize them by extracting their TF-IDF features, as
shown in the following snippet:

# normalize and extract features from the toy corpus

norm_corpus = normalize_corpus(toy_corpus, lemmatize=True)
tfidf_vectorizer, tfidf_features = build_feature_matrix(norm_corpus,
                                                        
feature_
type='tfidf',
                                                        ngram_range=(1, 1),
                                                        
min_df=0.0, max_
df=1.0)

286
 Chapter 6 ■ Text Similarity and Clustering

# normalize and extract features from the query corpus

norm_query_docs =  normalize_corpus(query_docs, lemmatize=True)            
query_docs_tfidf = tfidf_vectorizer.transform(norm_query_docs)

Now that we have our documents normalized and vectorized with TF-IDF–based
vector representations, we will look at how to compute similarity for each of the metrics
we specified at the beginning of this section.

Cosine Similarity
We have seen the concepts with regards to computing Cosine similarity and also
implemented the same for term similarity. Here, we will reuse the same concepts to
compute the Cosine similarity scores for documents instead of terms. The document
vectors will be the Bag of Words model–based vectors with TF-IDF values instead of
term frequencies. We have also taken only unigrams here, but you can experiment with
bigrams and so on as document features during the vectorization process. For each of
the three query documents, we will compute its similarity with the nine documents in
toy_corpus and return the n most similar documents where n is a user input parameter.
We will define a function that will take in the vectorized corpus and the document
corpus for which we want to compute similarities. We will get the similarity scores using the
dot product operation as before and finally we will sort them in reverse order and get the
top n documents with the highest similarity score. The following function implements this:

def compute_cosine_similarity(doc_features, corpus_features,

                              top_n=3):
    # get document vectors
    doc_features = doc_features.toarray()[0]
    corpus_features = corpus_features.toarray()
    # compute similarities
    similarity = [Link](doc_features,
                        corpus_features.T)
    # get docs with highest similarity scores
    top_docs = [Link]()[::-1][:top_n]
    top_docs_with_score = [(index, round(similarity[index], 3))
                            for index in top_docs]
    return top_docs_with_score

In that function, corpus_features are the vectorized documents belonging to the

toy_corpus index from which we want to retrieve similar documents. These documents
will be retrieved on the basis of their similarity score with doc_features, which basically
represents the vectorized document belonging to each of the query_docs, as shown in the
following snippet:

# get Cosine similarity results for our example documents

In [243]: print 'Document Similarity Analysis using Cosine Similarity'
     ...: print '='*60
     ...: for index, doc in enumerate(query_docs):

287
Chapter 6 ■ Text Similarity and Clustering

     ...:    
     ...:     doc_tfidf = query_docs_tfidf[index]
     ...:     top_similar_docs = compute_cosine_similarity(doc_tfidf,
     ...:                                              tfidf_features,
     ...:                                              top_n=2)
     ...:     print 'Document',index+1 ,':', doc
     ...:     print 'Top', len(top_similar_docs), 'similar docs:'
     ...:     print '-'*40
     ...:     for doc_index, sim_score in top_similar_docs:
     ...:         print 'Doc num: {} Similarity Score: {}\nDoc: {}'.
format(doc_index+1,
     ...:                                               
sim_score, toy_corpus[doc_index])  
     ...:         print '-'*40      
     ...:     print  

Document Similarity Analysis using Cosine Similarity

============================================================
Document 1 : The fox is definitely smarter than the dog
Top 2 similar docs:
----------------------------------------
Doc num: 8 Similarity Score: 1.0
Doc: The dog is smarter than the fox
----------------------------------------
Doc num: 7 Similarity Score: 0.426
Doc: The fox is quicker than the lazy dog
----------------------------------------

Document 2 : Java is a static typed programming language unlike Python

Top 2 similar docs:
----------------------------------------
Doc num: 5 Similarity Score: 0.837
Doc: Python and Java are popular Programming languages
----------------------------------------
Doc num: 6 Similarity Score: 0.661
Doc: Among Programming languages, both Python and Java are the most used in
Analytics
----------------------------------------

Document 3 : I love to relax under the beautiful blue sky!

Top 2 similar docs:
----------------------------------------
Doc num: 2 Similarity Score: 1.0
Doc: The sky is blue and beautiful
----------------------------------------
Doc num: 1 Similarity Score: 0.72
Doc: The sky is blue
----------------------------------------

288
 Chapter 6 ■ Text Similarity and Clustering

The preceding output depicts the top two most relevant documents for each of the
query documents based on Cosine similarity scores, and you can see that the outputs
are quite what were expected. Documents about animals are similar to the document
that mentions the fox and the dog; documents about Python and Java are most similar to
the query document talking about them; and the beautiful blue sky is indeed similar to
documents that talk about the sky being blue and beautiful!
Also note the Cosine similarity scores in the preceding outputs, where 1.0 indicates
perfect similarity, 0.0 indicates no similarity, and any score between them indicates some
level of similarity based on how large that score is. For instance, in the last example,
the main document vectors are ['sky', 'blue', 'beautiful'] and because they all
match with the first document from the toy corpus, we get a 1.0 or 100 percent similarity
score, and only ['sky', 'blue'] match from the second most similar document, and
we get a 0.72 or 72 percent similarity score. And you should remember our discussion
from earlier where I mentioned briefly that Cosine similarity using Bag of Words–based
vectors only looks at token weights and does not consider order or sequence of the terms,
which is quite desirable in large documents because the same content may be depicted
in different ways, and capturing sequences there might lead to loss of information due to
unwanted mismatches.
We recommend using scikit-learn’s cosine_similarity() utility function, which
you can find under the [Link] module. It uses similar logic as our
implementation but is much more optimized and performs well on large corpora of
documents. You can also use gensim’s similarities module or the cossim() function
directly available in the [Link] module.

Hellinger-Bhattacharya Distance
The Hellinger-Bhattacharya distance (HB-distance) is also called the Hellinger distance or the
Bhattacharya distance. The Bhattacharya distance, originally introduced by A. Bhattacharya,
is used to measure the similarity between two discrete or continuous probability
distributions. E. Hellinger introduced the Hellinger integral in 1909, which is used in the
computation of the Hellinger distance. Overall, the Hellinger-Bhattacharya distance is an
f-divergence, which in the theory of probability is defined as a function D f ( P || Q ) , which
can be used to measure the difference between P and Q probability distributions. There are
many instances of f-divergences, including KL-divergence and HB-distance. Remember that
KL-divergence is not a distance metric because it violates the symmetric condition from the
four conditions necessary for a distance measure to be a metric.
HB-distance is computable for both continuous and discrete probability
distributions. In our case, we will be using the TF-IDF–based vectors as our document
distributions. This makes it discrete distributions because we have specific TF-IDF values
for specific feature terms, unlike continuous distributions. We can define the Hellinger-
Bhattacharya distance mathematically as

1
hbd ( u , v ) = u- v
2 2

289
Chapter 6 ■ Text Similarity and Clustering

where hbd(u, v) denotes the Hellinger-Bhattacharya distance between the document

vectors u and v, and it is equal to the Euclidean or L2 norm of the difference of the square
root of the vectors divided by the square root of 2. Considering the document vectors u and
v to be discrete with n number of features, we can further expand the above formula into

å( )
n
1 2
hbd ( u , v ) = ui - vi
2 i =1

such that u = ( u1 , u2 ,¼, un ) and v = (v1 , v2 ,¼, vn ) are the document vectors having
length n indicating n features, which are the TF-IDF weights of the various terms in the
documents. As with the previous computation of Cosine similarity, we will build our
function on the same principles; basically we will accept as input a corpus of document
vectors and a single document vector for which we want to get the n most similar
documents from the corpus based on their HB-distances. The function implements the
preceding concepts in Python in the following snippet:

def compute_hellinger_bhattacharya_distance(doc_features, corpus_features,

                                            top_n=3):
    # get document vectors                                            
    doc_features = doc_features.toarray()[0]
    corpus_features = corpus_features.toarray()
    # compute hb distances
    distance = [Link](
                    [Link](0.5 *
                            [Link](
                                [Link]([Link](doc_features) -
                                          [Link](corpus_features)),
                                axis=1)))
    # get docs with lowest distance scores                            
    top_docs = [Link]()[:top_n]
    top_docs_with_score = [(index, round(distance[index], 3))
                            for index in top_docs]
    return top_docs_with_score

From the preceding implementation, you case see that we sort the documents based
on their scores in ascending order, unlike Cosine similarity, where 1.0 indicates perfect
similarity—since this is a distance metric between distributions, a value of 0 indicates
perfect similarity, and higher values indicate some dissimilarity being present. We can
now apply this function to our example corpora, compute their HB-distances, and see the
results in the following snippet:

# get Hellinger-Bhattacharya distance based similarities for our example

documents
In [246]: print 'Document Similarity Analysis using Hellinger-Bhattacharya
distance'
     ...: print '='*60
     ...: for index, doc in enumerate(query_docs):

290
 Chapter 6 ■ Text Similarity and Clustering

     ...:    
     ...:     doc_tfidf = query_docs_tfidf[index]
     ...:     top_similar_docs = compute_hellinger_bhattacharya_
distance(doc_tfidf,
     ...:                                              tfidf_features,
     ...:                                              top_n=2)
     ...:     print 'Document',index+1 ,':', doc
     ...:     print 'Top', len(top_similar_docs), 'similar docs:'
     ...:     print '-'*40
     ...:     for doc_index, sim_score in top_similar_docs:
     ...:         print 'Doc num: {} Distance Score: {}\nDoc: {}'.
format(doc_index+1,
     ...:                                        sim_score, toy_corpus[doc_
index])  
     ...:         print '-'*40      
     ...:     print        
     ...:
     ...:
Document Similarity Analysis using Hellinger-Bhattacharya distance
============================================================
Document 1 : The fox is definitely smarter than the dog
Top 2 similar docs:
----------------------------------------
Doc num: 8 Distance Score: 0.0
Doc: The dog is smarter than the fox
----------------------------------------
Doc num: 7 Distance Score: 0.96
Doc: The fox is quicker than the lazy dog
----------------------------------------

Document 2 : Java is a static typed programming language unlike Python

Top 2 similar docs:
----------------------------------------
Doc num: 5 Distance Score: 0.53
Doc: Python and Java are popular Programming languages
----------------------------------------
Doc num: 4 Distance Score: 0.766
Doc: Python is a great Programming language
----------------------------------------

Document 3 : I love to relax under the beautiful blue sky!

Top 2 similar docs:
----------------------------------------
Doc num: 2 Distance Score: 0.0
Doc: The sky is blue and beautiful
----------------------------------------
Doc num: 1 Distance Score: 0.602
Doc: The sky is blue
----------------------------------------

291
Chapter 6 ■ Text Similarity and Clustering

You can see from the preceding outputs that documents with lower HB-distance
scores are more similar to the query documents, and the result documents are quite
similar to what we obtained using Cosine similarity. Compare the results and try out
these functions with larger corpora! I recommend using gensim’s hellinger() function,
available in the [Link] module (which uses the same logic as our preceding
function) when building large-scale systems for analyzing similarity.

Okapi BM25 Ranking

There are several techniques that are quite popular in information retrieval and
search engines, including PageRank and Okapi BM25. The acronym BM stands for best
matching. This technique is also known as BM25, but for the sake of completeness I refer
to it as Okapi BM25, because originally although the concepts behind the BM25 function
were merely theoretical, the City University in London built the Okapi Information
Retrieval system in the 1980s–90s, which implemented this technique to retrieve
documents on actual real-world data. This technique can also be called a framework
or model based on probabilistic relevancy and was developed by several people in the
1970s–80s, including computer scientists S. Robertson and K. Jones. There are several
functions that rank documents based on different factors, and BM25 is one of them. Its
newer variant is BM25F; other variants include BM15 and BM25+.
The Okapi BM25 can be formally defined as a document ranking and retrieval function
based on a Bag of Words–based model for retrieving relevant documents based on a user
input query. This query can be itself a document containing a sentence or collection of
sentences, or it can even be a couple of words. The Okapi BM25 is actually not just a single
function but is a framework consisting of a whole collection of scoring functions combined
together. Say we have a query document QD such that QD = ( q1 , q2 ,¼, qn ) containing n
terms or keywords and we have a corpus document CD in the corpus of documents from
which we want to get the most relevant documents to the query document based on
similarity scores, just as we have done earlier. Assuming we have these, we can
mathematically define the BM25 score between these two documents as

n
f ( qi , CD ) × ( k1 + 1)
bm 25 (CD , QD ) = åidf ( qi ) ×
æ CD ö
f ( qi , CD ) + k1 × ç 1 - b + b ×
i =1
÷
è avgdl ø

where the function bm25(CD, QD) computes the BM25 rank or score of the document
CD based on the query document QD. The function idf(qi) gives us the inverse document
frequency (IDF) of the term qi in the corpus that contains CD and from which we want
to retrieve the relevant documents. If you remember, we computed IDFs in Chapter 4
when we implemented the TF-IDF feature extractor. Just to refresh your memory, it can
represented by

C
idf ( t ) = 1 + log
1 + df ( t )

292
 Chapter 6 ■ Text Similarity and Clustering

where idf(t) represents the idf for the term t and C represents the count of the total
number of documents in our corpus and df(t) represents the frequency of the number
of documents in which the term t is present. There are various other methods of
implementing IDF, but we will be using this one, and on a side note the end outcome
from the different implementations is very similar. The function f(qi, CD) gives us the
frequency of the term qi in the corpus document CD. The expression |CD| indicates the
total length of the document CD which is measured by its number of words, and the
term avgdl represents the average document length of the corpus from which we will be
retrieving documents. Besides that, you will also observe there are two free parameters,
k1, which is usually in the range of [1.2, 2.0], and b, which is usually taken as 0.75. We
will be taking the value of k1 to be 1.5 in our implementation.
There are several steps we must go through to successfully implement and compute
BM25 scores for documents:
1. Build a function to get inverse document frequency (IDF)
values for terms in corpus.
2. Build a function for computing BM25 scores for query
document and corpus documents.
3. Get Bag of Words–based features for corpus documents and
query documents.
4. Compute average length of corpus documents and IDFs of the
terms in the corpus documents using function from point 1.
5. Compute BM25 scores, rank relevant documents, and fetch
the n most relevant documents for each query document
using the function in point 2.
We will start with implementing a function to extract and compute inverse document
frequencies of all the terms in a corpus of documents by using its Bag of Words features,
which will contain the term frequencies, and then convert them to IDFs using the formula
mentioned earlier. The following function implements this:

import [Link] as sp

def compute_corpus_term_idfs(corpus_features, norm_corpus):

    dfs = [Link](sp.csc_matrix(corpus_features, copy=True).indptr)

    dfs = 1 + dfs # to smoothen idf later
    total_docs = 1 + len(norm_corpus)
    idfs = 1.0 + [Link](float(total_docs) / dfs)
    return idfs

We will now implement the main function for computing BM25 score for all
the documents in our corpus based on the query document and retrieving the top n
relevant documents from the corpus based on their BM25 score. The following function
implements the BM25 scoring framework:

293
Chapter 6 ■ Text Similarity and Clustering

def compute_bm25_similarity(doc_features, corpus_features,

                            corpus_doc_lengths, avg_doc_length,
                            term_idfs, k1=1.5, b=0.75, top_n=3):
    # get corpus bag of words features
    corpus_features = corpus_features.toarray()
    # convert query document features to binary features
    # this is to keep a note of which terms exist per document
    doc_features = doc_features.toarray()[0]
    doc_features[doc_features >= 1] = 1

    # compute the document idf scores for present terms

    doc_idfs = doc_features * term_idfs
    # compute numerator expression in BM25 equation
    numerator_coeff = corpus_features * (k1 + 1)
    numerator = [Link](doc_idfs, numerator_coeff)
    # compute denominator expression in BM25 equation
    denominator_coeff =  k1 * (1 - b +
                                (b * (corpus_doc_lengths /
                                        avg_doc_length)))
    denominator_coeff = [Link](denominator_coeff)
    denominator = corpus_features + denominator_coeff
    # compute the BM25 score combining the above equations
    bm25_scores = [Link]([Link](numerator,
                                   denominator),
                         axis=1)
    # get top n relevant docs with highest BM25 score                    
    top_docs = bm25_scores.argsort()[::-1][:top_n]
    top_docs_with_score = [(index, round(bm25_scores[index], 3))
                            for index in top_docs]
    return top_docs_with_score

The comments in the function are self-explanatory and explain how the BM25
scoring function is implemented. In simple terms, we first compute the numerator
expression in the BM25 mathematical equation we specified earlier and then compute
the denominator expression. Finally, we divide the numerator by the denominator to get
the BM25 scores for all the corpus documents. Then we sort them in descending order
and return the top n relevant documents with the highest BM25 score. In the following
snippet, we will test our function on our example corpora and see how it performs for
each of the query documents:

# build bag of words based features first

vectorizer, corpus_features = build_feature_matrix(norm_corpus,
                                                   feature_type='frequency')
query_docs_features = [Link](norm_query_docs)

# get average document length of the corpus (avgdl)

doc_lengths = [len([Link]()) for doc in norm_corpus]  
avg_dl = [Link](doc_lengths)

294
 Chapter 6 ■ Text Similarity and Clustering

# Get the corpus term idfs

corpus_term_idfs = compute_corpus_term_idfs(corpus_features,
                                            norm_corpus)

# analyze document similarity using BM25 framework

In [253]: print 'Document Similarity Analysis using BM25'
     ...: print '='*60
     ...: for index, doc in enumerate(query_docs):
     ...:    
     ...:     doc_features = query_docs_features[index]
     ...:     top_similar_docs = compute_bm25_similarity(doc_features,
     ...:                                                corpus_features,
     ...:                                                doc_lengths,
     ...:                                                avg_dl,
     ...:                                                corpus_term_idfs,
     ...:                                                k1=1.5, b=0.75,
     ...:                                                top_n=2)
     ...:     print 'Document',index+1 ,':', doc
     ...:     print 'Top', len(top_similar_docs), 'similar docs:'
     ...:     print '-'*40
     ...:     for doc_index, sim_score in top_similar_docs:
     ...:         print 'Doc num: {} BM25 Score: {}\nDoc: {}'.format(doc_
index+1,
     ...:                                     sim_score, toy_corpus[doc_
index])  
     ...:         print '-'*40      
     ...:     print

Document Similarity Analysis using BM25

============================================================
Document 1 : The fox is definitely smarter than the dog
Top 2 similar docs:
----------------------------------------
Doc num: 8 BM25 Score: 7.334
Doc: The dog is smarter than the fox
----------------------------------------
Doc num: 7 BM25 Score: 3.88
Doc: The fox is quicker than the lazy dog
----------------------------------------

Document 2 : Java is a static typed programming language unlike Python

Top 2 similar docs:
----------------------------------------
Doc num: 5 BM25 Score: 7.248
Doc: Python and Java are popular Programming languages
----------------------------------------
Doc num: 6 BM25 Score: 6.042

295
Chapter 6 ■ Text Similarity and Clustering

Doc: Among Programming languages, both Python and Java are the most used in
Analytics
----------------------------------------

Document 3 : I love to relax under the beautiful blue sky!

Top 2 similar docs:
----------------------------------------
Doc num: 2 BM25 Score: 7.334
Doc: The sky is blue and beautiful
----------------------------------------
Doc num: 1 BM25 Score: 4.984
Doc: The sky is blue
----------------------------------------

You can now see how for each query document, we get expected and relevant
documents that have similar concepts just like the query documents. You can see that
the results are quite similar to the previous methods—because, of course, they are
all similarity and ranking metrics and are expected to return similar results. Notice
the BM25 scores of the relevant documents. The higher the score, the more relevant
is the document. Unfortunately, I was not able to find any production-ready scalable
implementation of the BM25 ranking framework in nltk or scikit-learn. However,
gensim seems to have a bm25 module under the [Link] package and if
you are interested you can give it a try. But the core of the algorithm is based on what we
implemented, and this should work pretty well on its own!
Try loading a bigger corpus of documents and test out these functions on some
sample query strings and documents. In fact, information retrieval frameworks like Solr
and Elasticsearch are built on top of Lucene, which use these types of ranking algorithms
to return relevant documents from an index of stored documents—and you can build
your own search engine using them! Interested readers can check out [Link]/
blog/found-bm-vs-lucene-default-similarity by [Link], the company behind the
popular Elasticsearch product, which tells that the performance of BM25 is much better
than the default similarity ranking implementation of Lucene.

Document Clustering
Document clustering or cluster analysis is an interesting area in NLP and text analytics
that applies unsupervised ML concepts and techniques. The main premise of document
clustering is similar to that of document categorization, where you start with a whole
corpus of documents and are tasked with segregating them into various groups based
on some distinctive properties, attributes, and features of the documents. Document
classification needs pre-labeled training data to build a model and then categorize
documents. Document clustering uses unsupervised ML algorithms to group the
documents into various clusters. The properties of these clusters are such that documents
inside one cluster are more similar and related to each other compared to documents
belonging to other clusters. Figure 6-3, courtesy of scikit-learn, visualizes an example
of clustering data points into three clusters based on its features.

296
 Chapter 6 ■ Text Similarity and Clustering

Figure 6-3. Sample cluster analysis results (courtesy: scikit-learn)

The cluster analysis in Figure 6-3 depicts three clusters among the data points,
which are visualized using different colors. An important thing to remember here is
that clustering is an unsupervised learning technique, and from Figure 6-3 it is pretty
clear that there will always be some overlap among the clusters because there is no such
definition of a perfect cluster. All the techniques are based on math, heuristics, and some
inherent attributes toward generating clusters, and they are never a 100 percent perfect.
Hence, there are several techniques or methods for finding clusters. Some popular
clustering algorithms are briefly described as follows:
• Hierarchical clustering models: These clustering models are also
known as connectivity-based clustering methods and are based on
the concept that similar objects will be closer to related objects
in the vector space than unrelated objects, which will be farther
away from them. Clusters are formed by connecting objects based
on their distance and they can be visualized using a dendrogram.
The output of these models is a complete, exhaustive hierarchy
of clusters. They are mainly subdivided into agglomerative and
divisive clustering models.

297
Chapter 6 ■ Text Similarity and Clustering

• Centroid-based clustering models: These models build clusters in

such a way that each cluster has a central representative member
that represents each cluster and has the features that distinguish
that particular cluster from the rest. There are various algorithms
in this, like k-means, k-medoids, and so on, where we need to set
the number of clusters 'k' in advance, and distance metrics like
squares of distances from each data point to the centroid need
to be minimized. The disadvantage of these models is that you
need to specify the 'k' number of clusters in advance, which
may lead to local minima, and you may not get a true clustered
representation of your data.
• Distribution-based clustering models: These models make use
of concepts from probability distributions when clustering data
points. The idea is that objects having similar distributions can
be clustered into the same group or cluster. Gaussian mixture
models (GMM) use algorithms like the Expectation-Maximization
algorithm for building these clusters. Feature and attribute
correlations and dependencies can also be captured using these
models, but it is prone to overfitting.
• Density-based clustering models: These clustering models
generate clusters from data points that are grouped together at
areas of high density compared to the rest of the data points,
which may occur randomly across the vector space in sparsely
populated areas. These sparse areas are treated as noise and
are used as border points to separate clusters. Two popular
algorithms in this area include DBSCAN and OPTICS.
Several other clustering models have been recently introduced, including algorithms
like BIRCH and CLARANS. Entire books and journals have been written just for clustering
alone—it is a very interesting topic offering a lot of value. Covering each and every
method would be impossible for us in the current scope, so we will cover a total of
three different clustering algorithms, illustrating them with real-world data for better
understanding:
• K-means clustering
• Affinity propagation
• Ward’s agglomerative hierarchical clustering
For each algorithm, we will be covering its theoretical concepts as we have done
previously with other methods. We will also illustrate how each method works by
applying each clustering algorithm on some real-world data pertaining to movies and
their synopses. We will also look at detailed cluster statistics and focus on visualizing the
clusters using tried-and-tested methods, because it is often difficult to visualize results
from clustering, and practitioners often face challenges in this area.

298
 Chapter 6 ■ Text Similarity and Clustering

Clustering Greatest Movies of All Time

We will be clustering a total of 100 different popular movies based on their IMDb synopses
as our raw data. IMDb, also known as the Internet Movie Database ([Link]), is an
online database that hosts extensive detailed information about movies, video games,
and television shows. It also aggregates reviews and synopses for movies and shows and
has several curated lists. The list we are interested in is available at [Link]/list/
ls055592025/, titled Top 100 Greatest Movies of All Time (The Ultimate List). We will be
clustering these movies into groups using the IMDb synopsis and description of each movie.
Before we begin our analysis, I would like to thank Brandon Rose for helping me out
with getting this data, which he personally retrieved and curated, and also for giving me
some excellent pointers on visualizing clusters. He has done some detailed clustering
analysis with this data himself. If you are interested, you can get the raw data and also see
his document clustering analysis in his repository at [Link]
document_cluster, which is also described in further detail in his personal blog, which is
dedicated to analytics, at [Link]
We have downloaded data pertaining to the top 100 movie titles and their synopses
from IMDb from the repository mentioned earlier. We parsed and cleaned it up and also
added the synopses for a few movies that were missing from the original data. We added
these synopses and movie descriptions from Wikipedia. Once parsed, we stored them
in a data frame and saved it as a .csv file called movie_data.csv, which you can find in
the code files for this chapter. We will be loading and using the data from this file in our
clustering analysis, starting with loading and looking at the contents of our movie data
points in the following snippet:

import pandas as pd
import numpy as np

# load movie data

movie_data = pd.read_csv('movie_data.csv')

# view movie data

In [256]: print movie_data.head()

                     Title                                     Synopsis
0             The Godfather  In late summer 1945, guests are gathered...
1  The Shawshank Redemption  In 1947, Andy Dufresne (Tim Robbins),...
2          Schindler's List  The relocation of Polish Jews from...
3               Raging Bull  The film opens in 1964, where an older...
4                Casablanca  In the early years of World War II...

# print sample movie and its synopsis

In [268]: print 'Movie:', movie_titles[0]
     ...: print 'Movie Synopsis:', movie_synopses[0][:1000]
     ...:
Movie: The Godfather

299
Chapter 6 ■ Text Similarity and Clustering

Movie Synopsis: In late summer 1945, guests are gathered for the wedding
reception of Don Vito Corleone's daughter Connie (Talia Shire) and Carlo
Rizzi (Gianni Russo). Vito (Marlon Brando), the head of the Corleone Mafia
family, is known to friends and associates as "Godfather." He and Tom Hagen
(Robert Duvall), the Corleone family lawyer, are hearing requests for favors
because, according to Italian tradition, "no Sicilian can refuse a request
on his daughter's wedding day." One of the men who asks the Don for a favor
is Amerigo Bonasera, a successful mortician and acquaintance of the Don,
whose daughter was brutally beaten by two young men because she refused
their advances; the men received minimal punishment. The Don is disappointed
in Bonasera, who'd avoided most contact with the Don due to Corleone's
nefarious business dealings. The Don's wife is godmother to Bonasera's
shamed daughter, a relationship the Don uses to extract new loyalty from the
undertaker. The Don agrees to have his men punish

You can see that we have our movie titles and their corresponding synopses, which
we load into a data frame and then store them in variables. A sample movie and a part of
its corresponding synopsis are also depicted in the preceding output. The main idea is to
cluster these movies into groups using their synopsis as raw input. We will extract features
from these synopses and use unsupervised learning algorithms on them to cluster them
together. The movie titles are just for representation and will be useful when we would
want to visualize and display clusters and their statistics. The data to be fed to the clustering
algorithms will be features extracted from the movie synopses just to make things clearer.
Before we can jump into each of the clustering methods, we will follow the same process of
normalization and feature extraction that we have followed in all our other processes:

from normalization import normalize_corpus

from utils import build_feature_matrix

# normalize corpus
norm_movie_synopses = normalize_corpus(movie_synopses,
                                       lemmatize=True,
                                       only_text_chars=True)

# extract tf-idf features

vectorizer, feature_matrix = build_feature_matrix(norm_movie_synopses,
                                                  feature_type='tfidf',
                                                  min_df=0.24, max_df=0.85,
                                                  ngram_range=(1, 2))
# view number of features
In [275]: print feature_matrix.shape
(100, 307)

# get feature names

feature_names = vectorizer.get_feature_names()
# print sample features
In [277]: print feature_names[:20]  

300
 Chapter 6 ■ Text Similarity and Clustering

[u'able', u'accept', u'across', u'act', u'agree', u'alive', u'allow',

u'alone', u'along', u'already', u'although', u'always', u'another',
u'anything', u'apartment', u'appear', u'approach', u'arm', u'army',
u'around']

We keep text tokens in our normalized text and extract TF-IDF–based features
for unigrams and bigrams such that each feature occurs in at least in 25 percent of the
documents and at most 85 percent of the documents using the terms min_df and max_df.
We can see that we have a total of 100 rows for the 100 movies and a total of 307 features
for each movie. Some sample features are also printed in the preceding snippet. We will
start our clustering analysis next, now that we have our features and documents ready.

K-means Clustering
The k-means clustering algorithm is a centroid-based clustering model that tries to cluster
data into groups or clusters of equal variance. The criteria or measure that this algorithm
tries to minimize is inertia, also known as within-cluster sum-of-squares. Perhaps the one
main disadvantage of this algorithm is that the number of clusters k need to be specified
in advance, as is the case with all other centroid-based clustering models. This algorithm
is perhaps the most popular clustering algorithm out there and is frequently used due to
its ease of use as well as the fact that it is scalable with large amounts of data.
We can now formally define the k-means clustering algorithm along with its
mathematical notations. Consider that we have a dataset X with N data points or samples
and we want to group them into K clusters where K is a user-specified parameter. The
k-means clustering algorithm will segregate the N data points into K disjoint separate
clusters Ck, and each of these clusters can be described by the means of the cluster
samples. These means become the cluster centroids μk such that these centroids are not
bound by the condition that they have to be actual data points from the N samples in
X. The algorithm chooses these centroids and builds the clusters in such a way that the
inertia or within-cluster sums of squares are minimized. Mathematically, this can be
represented as

K
min å å
2
x n - mi
i =1 xn ÎCi

with regard to clusters Ci and centroids μi such that i Î{1, 2 , ¼, k} . This optimization is
an NP hard problem for all you algorithm enthusiasts out there. Lloyd’s algorithm is a
solution to this problem, which is an iterative procedure consisting of the following steps.
1. Choose initial k centroids μk by taking k random samples from
the dataset X.
2. Update clusters by assigning each data point or sample to its
nearest centroid point. Mathematically, we can represent this
as C k = {x n : x n - mk £ all x n - ml } where Ck denotes the
clusters.

301
Chapter 6 ■ Text Similarity and Clustering

3. Recalculate and update clusters based on the new cluster data

points for each cluster obtained from step 2. Mathematically,
this can be represented as

1
mk =
Ck
åx
xn ÎC k
n

where μk denotes the centroids.

The preceding steps are repeated in an iterative fashion till the outputs of steps 2 and
3 do not change anymore. One caveat of this method is that even though the optimization
is guaranteed to converge, it might lead to a local minimum, hence in reality, this algorithm
is run multiple times with several epochs and iterations, and the results might be averaged
from them if needed. The convergence and occurrence of local minimum are highly
dependent on the initialization of the initial centroids in step 1. One way is to make multiple
iterations with multiple random initializations and take the average. Another way would be
to use the kmeans++ scheme as implemented in scikit-learn, which initializes the initial
centroids to be far apart from each other and has proven to be effective. We will now use
k-means clustering to cluster the movie data from earlier, in the following code snippet:

from [Link] import KMeans

# define the k-means clustering function
def k_means(feature_matrix, num_clusters=5):
    km = KMeans(n_clusters=num_clusters,
                max_iter=10000)
    [Link](feature_matrix)
    clusters = km.labels_
    return km, clusters
# set k = 5, lets say we want 5 clusters from the 100 movies
num_clusters = 5    

# get clusters and assigned the cluster labels to the movies

km_obj, clusters = k_means(feature_matrix=feature_matrix,
                           num_clusters=num_clusters)
movie_data['Cluster'] = clusters

That snippet uses our implemented k-means function to cluster the movies based
on the TF-IDF features from the movie synopses, and we assign the cluster label for each
movie from the outcome of this cluster analysis by storing it in the movie_data dataframe
in the 'Cluster' column. You can see that we have taken k to be 5 in our analysis. We can
now see the total number of movies for each of the 5 clusters using the following snippet:

In [284]: from collections import Counter

     ...: # get the total number of movies per cluster
     ...: c = Counter(clusters)
     ...: print [Link]()
[(0, 29), (1, 5), (2, 21), (3, 15), (4, 30)]

You can see that there are five cluster labels as expected, from 0 to 5, and each of
them has some movies belonging to the cluster whose counts are mentioned as the

302
 Chapter 6 ■ Text Similarity and Clustering

second element of each tuple in the preceding list. But can we do more than just see
cluster counts? Of course we can! We will now define some functions to extract detailed
cluster analysis information, print them, and then visualize the clusters. We will start by
defining a function to extract important information from our cluster analysis:

def get_cluster_data(clustering_obj, movie_data,

                     feature_names, num_clusters,
                     topn_features=10):

    cluster_details = {}  
    # get cluster centroids
    ordered_centroids = clustering_obj.cluster_centers_.argsort()[:, ::-1]
    # get key features for each cluster
    # get movies belonging to each cluster
    for cluster_num in range(num_clusters):
        cluster_details[cluster_num] = {}
        cluster_details[cluster_num]['cluster_num'] = cluster_num
        key_features = [feature_names[index]
                        for index
                        in ordered_centroids[cluster_num, :topn_features]]
        cluster_details[cluster_num]['key_features'] = key_features

        movies = movie_data[movie_data['Cluster'] == cluster_num]['Title'].

[Link]()
        cluster_details[cluster_num]['movies'] = movies

    return cluster_details

The preceding function is pretty self-explanatory. What it does is basically extract the
key features per cluster that were essential in defining the cluster from the centroids. It also
retrieves the movie titles that belong to each cluster and stores everything in a dictionary.
We will now define a function that uses this data structure and prints the results in a
clear format:

def print_cluster_data(cluster_data):
    # print cluster details
    for cluster_num, cluster_details in cluster_data.items():
        print 'Cluster {} details:'.format(cluster_num)
        print '-'*20
        print 'Key features:', cluster_details['key_features']
        print 'Movies in this cluster:'
        print ', '.join(cluster_details['movies'])
        print '='*40

Before we analyze the results of our k-means clustering algorithm, we will also
define a function to visualize the clusters. If you remember, we talked earlier about
challenges associated with visualizing clusters. This happens because we deal with
multidimensional feature spaces and unstructured text data. Numeric feature vectors

303
Chapter 6 ■ Text Similarity and Clustering

themselves may not make any sense to readers if they were visualized directly. So, there
are some techniques like principal component analysis (PCA) or multidimensional scaling
(MDS) to reduce the dimensionality such that we can visualize these clusters in 2- or
3-dimensional plots. We will be using MDS in our implementation for visualizing clusters.
MDS is an approach towards non-linear dimensionality reduction such that the
results can be visualized better in lower dimensional systems. The main idea is having a
distance matrix such that distances between various data points are captured. We will be
using Cosine similarity for this. MDS tries to build a lower-dimensional representation
of our data with higher numbers of features in the vector space such that the distances
between the various data points obtained using Cosine similarity in the higher
dimensional feature space is still similar in this lower-dimensional representation.
The scikit-learn implementation for MDS has two types of algorithms: metric and
non-metric. We will be using the metric approach because we will use the Cosine
similarity–based distance metric to build the input similarity matrix between the various
movies. Mathematically, MDS can be defined as follows: Let S be our similarity matrix
between the various data points (movies) obtained using Cosine similarity on the feature
matrix and X be the coordinates of the n input data points (movies). Disparities are
represented by d̂ij = t ( Sij ) , which is usually some optimal transformation of the similarity
values or could even be the raw similarity values themselves. The objective function for
MDS, called stress, is defined as sumi< j dij ( X ) - dˆij ( X ) . We implement MDS-based
visualization for clusters in the following function:

import [Link] as plt

from [Link] import MDS
from [Link] import cosine_similarity
import random
from matplotlib.font_manager import FontProperties

def plot_clusters(num_clusters, feature_matrix,

                  cluster_data, movie_data,
                  plot_size=(16,8)):
    # generate random color for clusters                  
    def generate_random_color():
        color = '#%06x' % [Link](0, 0xFFFFFF)
        return color
    # define markers for clusters    
    markers = ['o', 'v', '^', '<', '>', '8', 's', 'p', '*', 'h', 'H', 'D', 'd']
    # build cosine distance matrix
    cosine_distance = 1 - cosine_similarity(feature_matrix)
    # dimensionality reduction using MDS
    mds = MDS(n_components=2, dissimilarity="precomputed",
              random_state=1)
    # get coordinates of clusters in new low-dimensional space
    plot_positions = mds.fit_transform(cosine_distance)  
    x_pos, y_pos = plot_positions[:, 0], plot_positions[:, 1]
    # build cluster plotting data

304
 Chapter 6 ■ Text Similarity and Clustering

    cluster_color_map = {}
    cluster_name_map = {}
    for cluster_num, cluster_details in cluster_data.items():
        # assign cluster features to unique label
        cluster_color_map[cluster_num] = generate_random_color()
        cluster_name_map[cluster_num] = ', '.join(cluster_details['key_
features'][:5]).strip()
    # map each unique cluster label with its coordinates and movies
    cluster_plot_frame = [Link]({'x': x_pos,
                                       'y': y_pos,
                                       'label': movie_data['Cluster'].
[Link](),
                                       'title': movie_data['Title'].values.
tolist()
                                        })
    grouped_plot_frame = cluster_plot_frame.groupby('label')
    # set plot figure size and axes
    fig, ax = [Link](figsize=plot_size)
    [Link](0.05)
    # plot each cluster using co-ordinates and movie titles
    for cluster_num, cluster_frame in grouped_plot_frame:
         marker = markers[cluster_num] if cluster_num < len(markers) \
                  else [Link](markers, size=1)[0]
         [Link](cluster_frame['x'], cluster_frame['y'],
                 marker=marker, linestyle='', ms=12,
                 label=cluster_name_map[cluster_num],
                 color=cluster_color_map[cluster_num], mec='none')
         ax.set_aspect('auto')
         ax.tick_params(axis= 'x', which='both', bottom='off', top='off',        
                        labelbottom='off')
         ax.tick_params(axis= 'y', which='both', left='off', top='off',        
                        labelleft='off')
    fontP = FontProperties()
    fontP.set_size('small')    
    [Link](loc='upper center', bbox_to_anchor=(0.5, -0.01),
fancybox=True,
              shadow=True, ncol=5, numpoints=1, prop=fontP)
    #add labels as the film titles
    for index in range(len(cluster_plot_frame)):
        [Link](cluster_plot_frame.ix[index]['x'],
                cluster_plot_frame.ix[index]['y'],
                cluster_plot_frame.ix[index]['title'], size=8)  
    # show the plot          
    [Link]()

The function is quite big, but the self-explanatory comments explain each step
clearly. We build our similarity matrix first using the Cosine similarity between
documents, get the cosine distances, and then transform the high dimensional feature

305
Chapter 6 ■ Text Similarity and Clustering

space into 2 dimensions using MDS. Then we plot the clusters using matplotlib with
a bit of necessary formatting to view the results in a nice way. This function is a generic
function and will work with any clustering algorithm with a dynamic number of clusters.
Each cluster will have its own color, symbol, and label in the terms of top distinguishing
features in the legend. The actual plot will plot each movie with its corresponding cluster
label with its own color and symbol.
We are now ready to analyze the cluster results of our k-means clustering using the
preceding functions. The following code snippet depicts the detailed analysis results for
k-means clustering:

# get clustering analysis data

cluster_data =  get_cluster_data(clustering_obj=km_obj, movie_data=movie_
data,
                                 
feature_names=feature_names, num_
clusters=num_clusters,
                                 topn_features=5)  

# print clustering analysis results

In [294]: print_cluster_data(cluster_data)

Cluster 0 details:
--------------------
Key features: [u'car', u'police', u'house', u'father', u'room']
Movies in this cluster:
Psycho, Sunset Blvd., Vertigo, West Side Story, E.T. the Extra-Terrestrial,
2001: A Space Odyssey, The Silence of the Lambs, Singin' in the Rain, It's
a Wonderful Life, Some Like It Hot, Gandhi, To Kill a Mockingbird, Butch
Cassidy and the Sundance Kid, The Exorcist, The French Connection, It
Happened One Night, Rain Man, Fargo, Close Encounters of the Third Kind,
Nashville, The Graduate, American Graffiti, Pulp Fiction, The Maltese
Falcon, A Clockwork Orange, Rebel Without a Cause, Rear Window, The Third
Man, North by Northwest
========================================
Cluster 1 details:
--------------------
Key features: [u'water', u'attempt', u'cross', u'death', u'officer']
Movies in this cluster:
Chinatown, Apocalypse Now, Jaws, The African Queen, Mutiny on the Bounty
========================================
Cluster 2 details:
--------------------
Key features: [u'family', u'love', u'marry', u'war', u'child']
Movies in this cluster:
The Godfather, Gone with the Wind, The Godfather: Part II, The Sound of
Music, A Streetcar Named Desire, The Philadelphia Story, An American in
Paris, Ben-Hur, Doctor Zhivago, High Noon, The Pianist, Goodfellas, The
King's Speech, A Place in the Sun, Out of Africa, Terms of Endearment,
Giant, The Grapes of Wrath, Wuthering Heights, Double Indemnity, Yankee
Doodle Dandy

306
 Chapter 6 ■ Text Similarity and Clustering

========================================
Cluster 3 details:
--------------------
Key features: [u'apartment', u'new', u'woman', u'york', u'life']
Movies in this cluster:
Citizen Kane, Titanic, 12 Angry Men, Rocky, The Best Years of Our Lives, My
Fair Lady, The Apartment, City Lights, Midnight Cowboy, Mr. Smith Goes to
Washington, Annie Hall, Good Will Hunting, Tootsie, Network, Taxi Driver
========================================
Cluster 4 details:
--------------------
Key features: [u'kill', u'soldier', u'men', u'army', u'war']
Movies in this cluster:
The Shawshank Redemption, Schindler's List, Raging Bull, Casablanca, One
Flew Over the Cuckoo's Nest, The Wizard of Oz, Lawrence of Arabia, On the
Waterfront, Forrest Gump, Star Wars, The Bridge on the River Kwai, Dr.
Strangelove or: How I Learned to Stop Worrying and Love the Bomb, Amadeus,
The Lord of the Rings: The Return of the King, Gladiator, From Here to
Eternity, Saving Private Ryan, Unforgiven, Raiders of the Lost Ark, Patton,
Braveheart, The Good, the Bad and the Ugly, The Treasure of the Sierra
Madre, Platoon, Dances with Wolves, The Deer Hunter, All Quiet on the
Western Front, Shane, The Green Mile, Stagecoach
========================================

# visualize the clusters

In [295]: plot_clusters(num_clusters=num_clusters,
     ...:               feature_matrix=feature_matrix,
     ...:               cluster_data=cluster_data,
     ...:               movie_data=movie_data,
     ...:               plot_size=(16,8))

Figure 6-4. Visualizing the output of K-means clustering on IMDb movie data

307
Chapter 6 ■ Text Similarity and Clustering

The preceding output shows the key features for each cluster and the movies in each
cluster, and you can also see the same in the visualization in Figure 6-4 (there is a lot
in that figure—if the text appears too small, check out the kmeans_clustering.png file,
available along with the code files for this chapter). Each cluster is depicted by the main
themes that define that cluster by its top features, and you can see popular movies like
The Godfather and The Godfather: Part II in the same cluster along with other movies
like Ben-Hur and so on which talk about 'family', 'love', 'war', and so on. Movies
like Star Wars, The Lord of the Rings, The Deer Hunter, Gladiator, Forrest Gump, and so
on are clustered together associated with themes like 'kill', 'soldier', 'army', and
'war'. Definitely interesting results considering the data used for clustering was just a few
paragraphs of synopsis per movie. Look more closely at the results and the visualization.
Can you notice any other interesting patterns?

Affinity Propagation
The k-means algorithm, although very popular, has the drawback that the user has to pre-
define the number of clusters. What if in reality there are more clusters or lesser clusters?
There are some ways of checking the cluster quality and seeing what the value of the
optimum k might be. Interested readers can check out the elbow method and the silhouette
coefficient, which are popular methods of determining the optimum k. Here we will talk
about an algorithm that tries to build clusters based on inherent properties of the data
without any pre-assumptions about the number of clusters. The affinity propagation (AP)
algorithm is based on the concept of “message passing” among the various data points to
be clustered, and no pre-assumption is needed about the number of possible clusters.
AP creates these clusters from the data points by passing messages between pairs
of data points until convergence is achieved. The entire dataset is then represented by a
small number of exemplars that act as representatives for samples. These exemplars are
analogous to the centroids you obtain from k-means or k-medoids. The messages that
are sent between pairs represent how suitable one of the points might be in being the
exemplar or representative of the other data point. This keeps getting updated in every
iteration until convergence is achieved, with the final exemplars being the representatives
of each cluster. Remember, one drawback of this method is that it is computationally
intensive because messages are passed between each pair of data points across the entire
dataset and can take substantial time to converge for large datasets.
We can now define the steps involved in the AP algorithm (courtesy of Wikipedia and
scikit-learn). Consider that we have a dataset X with n data points such that
X = {x1 , x 2 , ¼, x n } , and let sim(x, y) be the similarity function that quantifies the similarity
between two points x and y. In our implementation, we will be using Cosine similarity
again for this. The AP algorithm iteratively proceeds by executing two message-passing
steps as follows:
1. Responsibility updates are sent around, which can be
mathematically represented as

r ( i , k ) ¬ sim ( i , k ) - max {a ( i , k ¢ ) + sim ( i , k ¢ )}

k ¢¹ k

308
 Chapter 6 ■ Text Similarity and Clustering

where the responsibility matrix is R and r(i, k) is a measure which quantifies

how well xk can serve as being the representative or exemplar for xi in
comparison to the other candidates.
2. Availability updates are then sent around which can be
mathematically represented as
æ ö
a ( i , k ) ¬ min ç 0 , r ( k , k ) + å max ( 0 , r ( i¢, k ) ) ÷ for i ≠ k and
ç ÷
è i {i , k}
¢Ï ø
availability for i = k is represented as
a ( k , k ) ¬ å max (0 , r ( i¢, k ) )
i ¢ ¹k

where the availability matrix is A and a(i, k) represents

how appropriate it would be for xi to pick xk as its exemplar,
considering all the other points’ preference to pick xk as an
exemplar.
Those two steps keep occurring per iteration until convergence is achieved. The
following function implements AP such that it takes in a feature matrix and returns the
necessary clusters for each sample based on its features and the other samples:

from [Link] import AffinityPropagation

def affinity_propagation(feature_matrix):
    sim = feature_matrix * feature_matrix.T
    sim = [Link]()
    ap = AffinityPropagation()
    [Link](sim)
    clusters = ap.labels_          
    return ap, clusters

We will now use this function to cluster our movies based on their synopses and
then we will print the number of movies in each cluster and the total number of clusters
formed by this algorithm:

# get clusters using affinity propagation

ap_obj, clusters = affinity_propagation(feature_matrix=feature_matrix)
movie_data['Cluster'] = clusters

# get the total number of movies per cluster

In [299]: c = Counter(clusters)  
     ...: print [Link]()
[(0, 5), (1, 6), (2, 12), (3, 6), (4, 2), (5, 7), (6, 10), (7, 7), (8, 4),
(9, 8), (10, 3), (11, 4), (12, 5), (13, 7), (14, 4), (15, 3), (16, 7)]

# get total clusters

In [300]: total_clusters = len(c)
     ...: print 'Total Clusters:', total_clusters
Total Clusters: 17
309
Chapter 6 ■ Text Similarity and Clustering

From the preceding results, we can see that a total of 17 clusters have been created
by AP on our movie data containing 100 movies. Each cluster has movies ranging from as
low as 2 to as high as 12 movies. We shall now extract detailed cluster information, display
cluster statistics, and visualize the clusters similar to what we did for k-means clustering,
using our utility functions that we implemented in the K-means clustering section:

# get clustering analysis data

cluster_data =  get_cluster_data(clustering_obj=ap_obj, movie_data=movie_
data,
                                 
feature_names=feature_names, num_
clusters=total_clusters,
                                 topn_features=5)

# print clustering analysis results

In [302]: print_cluster_data(cluster_data)
     ...:
Cluster 0 details:
--------------------
Key features: [u'able', u'always', u'cover', u'end', u'charge']
Movies in this cluster:
The Godfather, The Godfather: Part II, Doctor Zhivago, The Pianist,
Goodfellas
========================================
Cluster 1 details:
--------------------
Key features: [u'alive', u'accept', u'around', u'agree', u'attack']
Movies in this cluster:
Casablanca, One Flew Over the Cuckoo's Nest, Titanic, 2001: A Space Odyssey,
The Silence of the Lambs, Good Will Hunting
========================================
Cluster 2 details:
--------------------
Key features: [u'apartment', u'film', u'final', u'fall', u'due']
Movies in this cluster:
The Shawshank Redemption, Vertigo, West Side Story, Rocky, Tootsie,
Nashville, The Graduate, The Maltese Falcon, A Clockwork Orange, Taxi
Driver, Rear Window, The Third Man
========================================
Cluster 3 details:
--------------------
Key features: [u'arrest', u'film', u'evening', u'final', u'fall']
Movies in this cluster:
The Wizard of Oz, Psycho, E.T. the Extra-Terrestrial, My Fair Lady, Ben-Hur,
Close Encounters of the Third Kind
========================================
Cluster 4 details:
--------------------

310
 Chapter 6 ■ Text Similarity and Clustering

Key features: [u'become', u'film', u'city', u'army', u'die']

Movies in this cluster:
12 Angry Men, Mr. Smith Goes to Washington
========================================
Cluster 5 details:
--------------------
Key features: [u'behind', u'city', u'father', u'appear', u'allow']
Movies in this cluster:
Forrest Gump, Amadeus, Gladiator, Braveheart, The Exorcist, A Place in the
Sun, Double Indemnity
========================================
Cluster 6 details:
--------------------
Key features: [u'body', u'allow', u'although', u'city', u'break']
Movies in this cluster:
Schindler's List, Gone with the Wind, Lawrence of Arabia, Star Wars, The
Lord of the Rings: The Return of the King, From Here to Eternity, Raiders of
the Lost Ark, The Best Years of Our Lives, The Deer Hunter, Stagecoach
========================================
Cluster 7 details:
--------------------
Key features: [u'brother', u'bring', u'close', u'although', u'car']
Movies in this cluster:
Gandhi, Unforgiven, To Kill a Mockingbird, The Good, the Bad and the Ugly,
Butch Cassidy and the Sundance Kid, High Noon, Shane
========================================
Cluster 8 details:
--------------------
Key features: [u'child', u'everyone', u'attempt', u'fall', u'face']
Movies in this cluster:
Chinatown, Jaws, The African Queen, Mutiny on the Bounty
========================================
Cluster 9 details:
--------------------
Key features: [u'continue', u'bring', u'daughter', u'break', u'allow']
Movies in this cluster:
The Bridge on the River Kwai, Dr. Strangelove or: How I Learned to Stop
Worrying and Love the Bomb, Apocalypse Now, Saving Private Ryan, Patton,
Platoon, Dances with Wolves, All Quiet on the Western Front
========================================
Cluster 10 details:
--------------------
Key features: [u'despite', u'drop', u'family', u'confront', u'drive']
Movies in this cluster:
The Treasure of the Sierra Madre, City Lights, Midnight Cowboy
========================================
Cluster 11 details:
--------------------

311
Chapter 6 ■ Text Similarity and Clustering

Key features: [u'discover', u'always', u'feel', u'city', u'act']

Movies in this cluster:
Raging Bull, It Happened One Night, Rain Man, Rebel Without a Cause
========================================
Cluster 12 details:
--------------------
Key features: [u'discuss', u'alone', u'drop', u'business', u'consider']
Movies in this cluster:
Singin' in the Rain, An American in Paris, The Apartment, Annie Hall,
Network
========================================
Cluster 13 details:
--------------------
Key features: [u'due', u'final', u'day', u'ever', u'eventually']
Movies in this cluster:
On the Waterfront, It's a Wonderful Life, Some Like It Hot, The French
Connection, Fargo, Pulp Fiction, North by Northwest
========================================
Cluster 14 details:
--------------------
Key features: [u'early', u'able', u'end', u'charge', u'allow']
Movies in this cluster:
A Streetcar Named Desire, The King's Speech, Giant, The Grapes of Wrath
========================================
Cluster 15 details:
--------------------
Key features: [u'enter', u'eventually', u'cut', u'accept', u'even']
Movies in this cluster:
The Philadelphia Story, The Green Mile, American Graffiti
========================================
Cluster 16 details:
--------------------
Key features: [u'far', u'allow', u'apartment', u'anything', u'car']
Movies in this cluster:
Citizen Kane, Sunset Blvd., The Sound of Music, Out of Africa, Terms of
Endearment, Wuthering Heights, Yankee Doodle Dandy
========================================

# visualize the clusters

In [304]: plot_clusters(num_clusters=num_clusters, feature_matrix=feature_
matrix,
     ...:               cluster_data=cluster_data, movie_data=movie_data,
     ...:               plot_size=(16,8))

312
 Chapter 6 ■ Text Similarity and Clustering

Figure 6-5. Visualizing the output of Affinity Propagation clustering on IMDb movie data

The preceding outputs show the contents of the different clusters and their
visualization. If the visual text in Figure 6-5 is too small, you can always refer to the file
affinity_prop_clustering.png, which contains the plot depicted in higher resolution.
You can see from the results that we now have a total of 17 clusters, and there are some
similarities where you will see similar movies that were grouped together in k-means
clustering are in similar clusters here also, and there are also notable differences where
many movies now have their own cluster. Are these clustering results better than the
previous one? Well a lot depends on human perspective, and since I have yet to watch
several of these movies, I leave this decision to you, dear reader! An important point to
note here is that a few keywords from the exemplars or centroids for each cluster may not
always depict the true essence or theme of that cluster, so a good idea here would be to
build topic models on each cluster and see the kind of topics you can extract from each
cluster that would make a better representation of each cluster (another example where
you can see how we can connect various text analytics techniques together).

Ward’s Agglomerative Hierarchical Clustering

The hierarchical clustering family of algorithms is a bit different from the other clustering
models we’ve discussed. Hierarchical clustering tries to build a nested hierarchy of
clusters by either merging or splitting them in succession. There are two main strategies
for Hierarchical clustering:
• Agglomerative: These algorithms follow a bottom-up approach
where initially all data points belong to their own individual
cluster, and then from this bottom layer, we start merging clusters
together, building a hierarchy of clusters as we go up.

313
Chapter 6 ■ Text Similarity and Clustering

• Divisive: These algorithms follow a top-down approach where

initially all the data points belong to a single huge cluster and
then we start recursively dividing them up as we move down
gradually, and this produces a hierarchy of clusters going from the
top-down.
Merges and splits normally happen using a greedy algorithm, and the end result
of the hierarchy of clusters can be visualized as a tree structure, called a dendrogram.
Figure 6-6 shows an example of how a dendrogram is constructed using agglomerative
hierarchical clustering for a sample of documents.

Figure 6-6. Agglomerative hierarchical clustering representation

Figure 6-6 clearly highlights how six separate data points start off as six clusters,
and then we slowly start grouping them in each step following a bottom-up approach.
We will be using an agglomerative hierarchical clustering algorithm in this section. In
agglomerative clustering, for deciding which clusters we should combine when starting
from the individual data point clusters, we need two things:
• A distance metric to measure the similarity or dissimilarity degree
between data points. We will be using the Cosine distance/
similarity in our implementation.
• A linkage criterion that determines the metric to be used for the
merging strategy of clusters. We will be using Ward’s method here.

314
 Chapter 6 ■ Text Similarity and Clustering

The Ward’s linkage criterion minimizes the sum of squared differences within all the
clusters and is a variance minimizing approach. This is also known as Ward’s minimum
variance method and was initially presented by J. Ward. The idea is to minimize the
variances within each cluster using an objective function like the L2 norm distance
between two points. We can start with computing the initial cluster distances between
each pair of points using the formula

( )
dij = d {Ci , C j } = Ci - C j
2

where initially Ci indicates cluster i with one document, and at each iteration, we find the
pairs of clusters that lead to the least increase in variance for that cluster once merged. A
weighted squared Euclidean distance or L2 norm as depicted in the preceding formula
would suffice for this algorithm. We use Cosine similarity to compute the cosine distances
between each pair of movies for our dataset. The following function implements Ward’s
agglomerative hierarchical clustering.:

from [Link] import ward, dendrogram

def ward_hierarchical_clustering(feature_matrix):

    cosine_distance = 1 - cosine_similarity(feature_matrix)
    linkage_matrix = ward(cosine_distance)
    return linkage_matrix

To view the results of the hierarchical clustering, we need to plot a dendrogram using
the preceding linkage matrix, and so we implement the following function to build and
plot a dendrogram from the hierarchical clustering linkage matrix:

def plot_hierarchical_clusters(linkage_matrix, movie_data, figure_

size=(8,12)):
    # set size
    fig, ax = [Link](figsize=figure_size)
    movie_titles = movie_data['Title'].[Link]()
    # plot dendrogram
    ax = dendrogram(linkage_matrix, orientation="left", labels=movie_titles)
    plt.tick_params(axis= 'x',  
                    which='both',  
                    bottom='off',
                    top='off',
                    labelbottom='off')
    plt.tight_layout()
    [Link]('ward_hierachical_clusters.png', dpi=200)

We are now ready to perform hierarchical clustering on our movie data! The
following code snippet shows Ward’s clustering in action:

315
Chapter 6 ■ Text Similarity and Clustering

In [307]:# build ward's linkage matrix    

     ...:linkage_matrix = ward_hierarchical_clustering(feature_matrix)
     ...: # plot the dendrogram
     ...: plot_hierarchical_clusters(linkage_matrix=linkage_matrix,
     ...:                            movie_data=movie_data,
     ...:                            figure_size=(8,10))

Figure 6-7. Ward's clustering dendrogram on our IMDb movie data

316
 Chapter 6 ■ Text Similarity and Clustering

The dendrogram in Figure 6-7 shows the clustering analysis results. The colors
indicate that there are three main clusters, which further get subdivided into more
granular clusters maintaining a hierarchy. (If you have trouble reading the small fonts, look
at the file ward_hierachical_clusters.png available with the code files in this chapter).
You will notice a lot of similarities with the results of the previous clustering algorithms.
The green colored movies like Raiders of the Lost Ark, The Lord of the Rings, Star
Wars, The Godfather, The Godfather: Part II, Pulp Fiction, A Clockwork Orange, and
Platoon are definitely some of the top movies and in fact classics in the action, adventure,
war, and crime-based genres.
The red colored movies include comedy-based movies like City Lights, The
Apartment, and My Fair Lady, and also several movies that belong to the drama genre
including Mutiny on the Bounty, 12 Angry Men, Annie Hall, Midnight Cowboy, Titanic,
and An American in Paris, with several of them having romantic plots too. Several of them
are even musicals, including Yankee Doodle Dandy, An American in Paris, Singin' in the
Rain, and My Fair Lady. It is definitely interesting indeed that with just movie synopses,
our algorithm has clustered movies with similar attributes and genres together!
The blue colored movies give us similar results, in that Braveheart and Gladiator are
action, drama, and war classics. We also have some classics related to drama, romance,
and biographies like The Sound of Music, Wuthering Heights, Terms of Endearment, and
Out of Africa. Toward the top of the dendrogram you will observe movies related to
science fiction and fantasy, like 2001: A Space Odyssey, Close Encounters of the Third Kind,
and E.T. the Extra-Terrestrial, all close to each other.
Can you find more interesting patterns? Which movies do you think do not belong
together in the same clusters? Can we build better clusters? Can we recommend similar
movies to watch based on clustering movies together? These are some interesting
questions to ponder, and I will leave them for you to look at and explore further.

Summary
I would like to really commend your efforts on staying with me till the end of this
chapter. We covered a lot here, including several topics in the challenging but very
interesting unsupervised machine learning domain. You now know how text similarity
can be computed and you learned about various kinds of distance measures and
metrics. We also looked at important concepts related to distance metrics and measures
and properties that make a measure into a metric. We explored concepts related to
unsupervised ML and saw how we can incorporate such techniques in document
clustering. Various ways of measuring term and document similarity were also
covered, and we implemented several of these techniques by successfully converting
mathematical equations into code using the power of Python and several open source
libraries. We touched on document clustering in detail, looking at the various concepts
and types of clustering models. Finally, we took a real-world example of clustering the top
hundred greatest movies of all time using IMDb movie synopses data and used different
clustering models like k-means, affinity propagation, and Ward’s hierarchical clustering
to build, analyze, and visualize clusters. This should be enough for you to get started
with analyzing document similarity and clustering, and you can even start combining
various techniques from the chapters covered so far. (Hint: Topic models with clustering,
building classifiers by combining supervised and unsupervised learning, and augmenting
recommendation systems using document clusters—just to name a few!)

317
CHAPTER 7

Semantic and Sentiment

Analysis

Natural language understanding has gained significant importance in the last decade
with the advent of machine learning (ML) and further advances like deep learning and
artificial intelligence. Computers and other machines can be programmed to learn
things and perform specific operations. The key limitation is their inability to perceive,
understand, and comprehend things like humans do. With the resurgence in popularity
of neural networks and advances made in computer architecture, we now have deep
learning and artificial intelligence evolving rapidly to make some efforts into trying to
engineer machines into learning, perceiving, understanding, and performing actions on
their own. You may have seen or heard several of these efforts, such as self-driving cars,
computers beating experienced players in games like chess and Go, and the proliferation
of chatbots on the Internet.
In Chapters 4–6, we have looked at various computational, language processing, and
ML techniques to classify, cluster, and summarize text. Back in Chapter 3 we developed
certain methods and programs to analyze and understand text syntax and structure.
This chapter will deal with methods that try to answer the question Can we analyze and
understand the meaning and sentiment behind a body of text?
Natural Language Processing (NLP) has a wide variety of applications that try to use
natural language understanding to infer the meaning and context behind text and use it to
solve various problems. We discussed several of these applications briefly in Chapter 1.
To refresh your memory, the following applications require extensive understanding of
text from the semantic perspective:
• Question Answering Systems
• Contextual recognition
• Speech recognition (for some applications)
Text semantics specifically deals with understanding the meaning of text or language.
When combined into sentences, words have lexical relations and contextual relations
between them lead to various types of relationships and hierarchies, and semantics sits
at the heart of all this in trying to analyze and understand these relationships and infer
meaning from them. We will be exploring various types of semantic relationships in natural
language and look at some NLP-based techniques for inferring and extracting meaningful

© Dipanjan Sarkar 2016 319

D. Sarkar, Text Analytics with Python, DOI 10.1007/978-1-4842-2388-8_7
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

semantic information from text. Semantics is purely concerned with context and meaning,
and the structure or format of text holds little significance here. But sometimes even the
syntax or arrangement of words helps us in inferring the context of words and helps us
differentiate things like lead as a metal from lead as in the lead of a movie.
Sentiment analysis is perhaps the most popular application of text analytics, with a
vast number of tutorials, web sites, and applications that focus on analyzing sentiment of
various text resources ranging from corporate surveys to movie reviews. The key aspect of
sentiment analysis is to analyze a body of text for understanding the opinion expressed by
it and other factors like mood and modality. Usually sentiment analysis works best on text
that has a subjective context than on that with only an objective context. This is because
when a body of text has an objective context or perspective to it, the text usually depicts some
normal statements or facts without expressing any emotion, feelings, or mood. Subjective
text contains text that is usually expressed by a human having typical moods, emotions, and
feelings. Sentiment analysis is widely used, especially as a part of social media analysis for
any domain, be it a business, a recent movie, or a product launch, to understand its reception
by the people and what they think of it based on their opinions or, you guessed it, sentiment.
In this chapter, we will be covering several aspects from both semantic and
sentiment analysis for textual data. We will start with exploring WordNet, a lexical
database, and introduce a new concept called synsets. We will also explore various
semantic relationships and representations in natural language and we will cover
techniques such as word sense disambiguation and named entity recognition. In
sentiment analysis, we will be looking at how to use supervised ML techniques to analyze
sentiment and also at several unsupervised lexical techniques with more detailed insights
into natural language sentiment, mood, and modality.

Semantic Analysis
We have seen how terms or words get grouped into phrases that further form clauses
and finally sentences. Chapter 3 showed various structural components in natural
language, including parts of speech (POS), chunking, and grammars. All these concepts
fall under the syntactic and structural analysis of text data. Whereas we do explore
relationships of words, phrases, and clauses, these are purely based on their position,
syntax, and structure. Semantic analysis is more about understanding the actual context
and meaning behind words in text and how they relate to other words to convey some
information as a whole. As mentioned in Chapter 1, the definition of semantics itself is
the study of meaning, and linguistic semantics is a complete branch under linguistics
that deals with the study of meaning in natural language, including exploring various
relationships between words, phrases and symbols. Besides this, there are also various
ways to represent semantics associated with statements and propositions. We will be
broadly covering the following topics under semantic analysis:
• Exploring WordNet and synsets
• Analyzing lexical semantic relations
• Word sense disambiguation
• Named entity recognition
• Analyzing semantic representations
320
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

The main objective of these topics is to give you a clear understanding of the
resources you can leverage for semantic analysis as well as how to use these resources.
We will explore various concepts related to semantic analysis, which was covered
in Chapter 1, with actual examples. You can refresh your memory by revisiting the
“Language Semantics” section in Chapter 1. Without any further delay, let's get started!

Exploring WordNet
WordNet is a huge lexical database for the English Language. The database is a part of
Princeton University, and you can read more about it at [Link]
It was originally created in around 1985, in Princeton University’s Cognitive Science
Laboratory under the direction of Professor G. A. Miller. This lexical database consists
of nouns, adjective, verbs, and adverbs, and related lexical terms are grouped together
based on some common concepts into sets, known as cognitive synonym sets or synsets.
Each synset expresses a unique, distinct concept. At a high level, WordNet can be
compared to a thesaurus or a dictionary that provides words and their synonyms. On a
lower level, it is much more than that, with synsets and their corresponding terms having
detailed relationships and hierarchies based on their semantic meaning and similar
concepts. WordNet is used extensively as a lexical database, in text analytics, NLP, and
artificial intelligence (AI)-based applications.
The WordNet database consists of over 155,000 words, represented in more than
117,000 synsets, and contains over 206,000 word-sense pairs. The database is roughly 12
MB in size and can be accessed through various interfaces and APIs. The official web site
has a web application interface for accessing various details related to words, synsets,
and concepts related to the entered word. You can access it at [Link]
[Link]/perl/webwn or download it from [Link]
wordnet/download/. The download contains various packages, files, and tools related to
WordNet. We will be accessing WordNet programmatically using the interface provided
by the nltk package. We will start by exploring synsets and then various semantic
relationships using synsets.

Understanding Synsets
We will start exploring WordNet by looking at synsets since they are perhaps one of the
most important concepts and structures that tie everything together. In general, based on
concepts from NLP and information retrieval, a synset is a collection or set of data entities
that are considered to be semantically similar. This doesn’t mean that they will be exactly
the same, but they will be centered on similar context and concepts. Specifically in the
context of WordNet, a synset is a set or collection of synonyms that are interchangeable
and revolve around a specific concept. Synsets not only consist of simple words, but
also collocations. Polysemous word forms (words that sound and look the same but
have different but relatable meanings) are assigned to different synsets based on their
meaning. Synsets are connected to other synsets using semantic relations, which we shall
explore in a future section. Typically each synset has the term, a definition explaining
the meaning of the term, and some optional examples and related lemmas (collection
of synonyms) to the term. Some terms may have multiple synsets associated with them,
where each synset has a particular context.

321
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Let’s look at a real example by using nltk’s WordNet interface to explore synsets
associated with the term, 'fruit'. We can do this using the following code snippet:

from [Link] import wordnet as wn

import pandas as pd

term = 'fruit'
synsets = [Link](term)
# display total synsets
In [75]: print 'Total Synsets:', len(synsets)
Total Synsets: 5

We can see that there are a total of five synsets associated with the term 'fruit'.
What can these synsets indicate? We can dig deeper into each synset and its components
using the following code snippet:

In [76]: for synset in synsets:

...: print 'Synset:', synset
...: print 'Part of speech:', [Link]()
...: print 'Definition:', [Link]()
...: print 'Lemmas:', synset.lemma_names()
...: print 'Examples:', [Link]()
...: print
...:
...:
Synset: Synset('fruit.n.01')
Part of speech: [Link]
Definition: the ripened reproductive body of a seed plant
Lemmas: [u'fruit']
Examples: []

Synset: Synset('yield.n.03')
Part of speech: [Link]
Definition: an amount of a product
Lemmas: [u'yield', u'fruit']
Examples: []

Synset: Synset('fruit.n.03')
Part of speech: [Link]
Definition: the consequence of some effort or action
Lemmas: [u'fruit']
Examples: [u'he lived long enough to see the fruit of his policies']

Synset: Synset('fruit.v.01')
Part of speech: [Link]
Definition: cause to bear fruit
Lemmas: [u'fruit']
Examples: []

322
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Synset: Synset('fruit.v.02')
Part of speech: [Link]
Definition: bear fruit
Lemmas: [u'fruit']
Examples: [u'the trees fruited early this year']

The preceding output shows us details pertaining to each synset associated with
the term 'fruit', and the definitions give us the sense of each synset and the lemma
associated with it. The part of speech for each synset is also mentioned, which includes
nouns and verbs. Some examples are also depicted in the preceding output that show
how the term is used in actual sentences. Now that we understand synsets better, let’s
start exploring various semantic relationships as mentioned.

Analyzing Lexical Semantic Relations

Text semantics refers to the study of meaning and context. Synsets give a nice abstraction
over various terms and provide useful information like definition, examples, POS, and
lemmas. But can we explore semantic relationships among entities using synsets? The
answer is definitely yes. We will be talking about many of the concepts related to semantic
relations (covered in detail in the “Lexical Semantic Relations” subsection under the
“Language Semantics” section in Chapter 1. It would be useful for you to review that
section to better understand each of the concepts when we illustrate them with real-world
examples here. We will be using nltk's wordnet resource here, but you can use the same
WordNet resource from the pattern package, which includes an interface similar to nltk.

Entailments
The term entailment usually refers to some event or action that logically involves or is
associated with some other action or event that has taken place or will take place. Ideally
this applies very well to verbs indicating some specific action. The following snippet
shows how to get entailments:

# entailments
In [80]: for action in ['walk', 'eat', 'digest']:
...: action_syn = [Link](action, pos='v')[0]
...: print action_syn, '-- entails -->', action_syn.entailments()
Synset('walk.v.01') -- entails --> [Synset('step.v.01')]
Synset('eat.v.01') -- entails --> [Synset('chew.v.01'),
Synset('swallow.v.01')]
Synset('digest.v.01') -- entails --> [Synset('consume.v.02')]

You can see how related synsets depict the concept of entailment in that output.
Related actions are depicted in entailment, where actions like walking involve or entail
stepping, and eating entails chewing and swallowing.

323
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Homonyms and Homographs

On a high level, homonyms refer to words or terms having the same written form or
pronunciation but different meanings. Homonyms are a superset of homographs, which
are words with same spelling but may have different pronunciation and meaning. The
following code snippet shows how we can get homonyms/homographs:

In [81]: for synset in [Link]('bank'):

...: print [Link](),'-',[Link]()
...:
...:
bank.n.01 - sloping land (especially the slope beside a body of water)
depository_financial_institution.n.01 - a financial institution that accepts
deposits and channels the money into lending activities
bank.n.03 - a long ridge or pile
bank.n.04 - an arrangement of similar objects in a row or in tiers
...
...
deposit.v.02 - put into a bank account
bank.v.07 - cover with ashes so to control the rate of burning
trust.v.01 - have confidence or faith in

The preceding output shows a part of the result obtained for the various homographs
for the term 'bank'. You can see that there are various different meanings associated with
the word 'bank', which is the core intuition behind homographs.

Synonyms and Antonyms

Synonyms are words having similar meaning and context, and antonyms are words having
opposite or contrasting meaning, as you may know already. The following snippet depicts
synonyms and antonyms:

In [82]: term = 'large'

...: synsets = [Link](term)
...: adj_large = synsets[1]
...: adj_large = adj_large.lemmas()[0]
...: adj_large_synonym = adj_large.synset()
...: adj_large_antonym = adj_large.antonyms()[0].synset()
...: # print synonym and antonym
...: print 'Synonym:', adj_large_synonym.name()
...: print 'Definition:', adj_large_synonym.definition()
...: print 'Antonym:', adj_large_antonym.name()
...: print 'Definition:', adj_large_antonym.definition()
Synonym: large.a.01
Definition: above average in size or number or quantity or magnitude or
extent
Antonym: small.a.01

324
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Definition: limited or below average in number or quantity or magnitude or

extent

In [83]: term = 'rich'

...: synsets = [Link](term)[:3]
...: # print synonym and antonym for different synsets
...: for synset in synsets:
...: rich = [Link]()[0]
...: rich_synonym = [Link]()
...: rich_antonym = [Link]()[0].synset()
...: print 'Synonym:', rich_synonym.name()
...: print 'Definition:', rich_synonym.definition()
...: print 'Antonym:', rich_antonym.name()
...: print 'Definition:', rich_antonym.definition()
Synonym: rich_people.n.01
Definition: people who have possessions and wealth (considered as a group)
Antonym: poor_people.n.01
Definition: people without possessions or wealth (considered as a group)

Synonym: rich.a.01
Definition: possessing material wealth
Antonym: poor.a.02
Definition: having little money or few possessions

Synonym: rich.a.02
Definition: having an abundant supply of desirable qualities or substances
(especially natural resources)
Antonym: poor.a.04
Definition: lacking in specific resources, qualities or substances

The preceding outputs show sample synonyms and antonyms for the term 'large'
and the term 'rich'. Additionally, we explore several synsets associated with the term
or concept 'rich', which rightly give us distinct synonyms and their corresponding
antonyms.

Hyponyms and Hypernyms

Synsets represent terms with unique semantics and concepts and are linked or related
to each other based on some similarity and context. Several of these synsets represent
abstract and generic concepts also besides concrete entities. Usually they are interlinked
together in the form of a hierarchical structure representing is-a relationships. Hyponyms
and hypernyms help us explore related concepts by navigating through this hierarchy.
To be more specific, hyponyms refer to entities or concepts that are a subclass of a higher
order concept or entity and have very specific sense or context compared to its superclass.
The following snippet shows the hyponyms for the entity 'tree':

325
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

term = 'tree'
synsets = [Link](term)
tree = synsets[0]
# print the entity and its meaning
In [86]: print 'Name:', [Link]()
...: print 'Definition:', [Link]()
Name: tree.n.01
Definition: a tall perennial woody plant having a main trunk and branches
forming a distinct elevated crown; includes both gymnosperms and angiosperms
# print total hyponyms and some sample hyponyms for 'tree'
In [87]: hyponyms = [Link]()
...: print 'Total Hyponyms:', len(hyponyms)
...: print 'Sample Hyponyms'
...: for hyponym in hyponyms[:10]:
...: print [Link](), '-', [Link]()

Total Hyponyms: 180

Sample Hyponyms
aalii.n.01 - a small Hawaiian tree with hard dark wood
acacia.n.01 - any of various spiny trees or shrubs of the genus Acacia
african_walnut.n.01 - tropical African timber tree with wood that resembles
mahogany
albizzia.n.01 - any of numerous trees of the genus Albizia
alder.n.02 - north temperate shrubs or trees having toothed leaves and
conelike fruit; bark is used in tanning and dyeing and the wood is rot-
resistant
angelim.n.01 - any of several tropical American trees of the genus Andira
angiospermous_tree.n.01 - any tree having seeds and ovules contained in the
ovary
anise_tree.n.01 - any of several evergreen shrubs and small trees of the
genus Illicium
arbor.n.01 - tree (as opposed to shrub)
aroeira_blanca.n.01 - small resinous tree or shrub of Brazil

The preceding output tells us that there are a total of 180 hyponyms for 'tree',
and we see some of the sample hyponyms and their definitions. We can see that each
hyponym is a specific type of tree, as expected. Hyponyms are entities or concepts that act
as the superclass to hyponyms and have a more generic sense or context. The following
snippet shows the immediate superclass hyponym for 'tree':

In [88]: hypernyms = [Link]()

...: print hypernyms
[Synset('woody_plant.n.01')]

You can even navigate up the entire entity/concept hierarchy depicting all the
hyponyms or parent classes for 'tree' using the following code snippet:

# get total hierarchy pathways for 'tree'

In [91]: hypernym_paths = tree.hypernym_paths()

326
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

...: print 'Total Hypernym paths:', len(hypernym_paths)

Total Hypernym paths: 1

# print the entire hypernym hierarchy

In [92]: print 'Hypernym Hierarchy'
...: print ' -> '.join([Link]() for synset in hypernym_paths[0])
Hypernym Hierarchy
entity.n.01 -> physical_entity.n.01 -> object.n.01 -> whole.n.02 -> living_
thing.n.01 -> organism.n.01 -> plant.n.02 -> vascular_plant.n.01 -> woody_
plant.n.01 -> tree.n.01

From the preceding output, you can see that 'entity' is the most generic concept
in which 'tree' is present, and the complete hypernym hierarchy showing the
corresponding hypernym or superclass at each level is shown. As you navigate further
down, you get into more specific concepts/entities, and if you go in the reverse direction
you will get into more generic concepts/entities.

Holonyms and Meronyms

Holonyms are entities that contain a specific entity of our interest. Basically holonym refers
to the relationship between a term or entity that denotes the whole and a term denoting a
specific part of the whole. The following snippet shows the holonyms for 'tree':

In [94]: member_holonyms = tree.member_holonyms()

...: print 'Total Member Holonyms:', len(member_holonyms)
...: print 'Member Holonyms for [tree]:-'
...: for holonym in member_holonyms:
...: print [Link](), '-', [Link]()
Total Member Holonyms: 1
Member Holonyms for [tree]:-
forest.n.01 - the trees and other plants in a large densely wooded area

From the output, we can see that 'forest' is a holonym for 'tree', which is
semantically correct because, of course, a forest is a collection of trees. Meronyms are
semantic relationships that relate a term or entity as a part or constituent of another term
or entity. The following snippet depicts different types of meronyms for 'tree':

# part based meronyms for tree

In [95]: part_meronyms = tree.part_meronyms()
...: print 'Total Part Meronyms:', len(part_meronyms)
...: print 'Part Meronyms for [tree]:-'
...: for meronym in part_meronyms:
...: print [Link](), '-', [Link]()
Total Part Meronyms: 5
Part Meronyms for [tree]:-
burl.n.02 - a large rounded outgrowth on the trunk or branch of a tree
crown.n.07 - the upper branches and leaves of a tree or other plant

327
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

limb.n.02 - any of the main branches arising from the trunk or a bough of a
tree
stump.n.01 - the base part of a tree that remains standing after the tree
has been felled
trunk.n.01 - the main stem of a tree; usually covered with bark; the bole is
usually the part that is commercially useful for lumber

# substance based meronyms for tree

In [96]: substance_meronyms = tree.substance_meronyms()
...: print 'Total Substance Meronyms:', len(substance_meronyms)
...: print 'Substance Meronyms for [tree]:-'
...: for meronym in substance_meronyms:
...: print [Link](), '-', [Link]()
Total Substance Meronyms: 2
Substance Meronyms for [tree]:-
heartwood.n.01 - the older inactive central wood of a tree or woody plant;
usually darker and denser than the surrounding sapwood
sapwood.n.01 - newly formed outer wood lying between the cambium and the
heartwood of a tree or woody plant; usually light colored; active in water
conduction

The preceding output shows various meronyms that include various constituents of
trees like stump and trunk and also various derived substances from trees like heartwood
and sapwood.

Semantic Relationships and Similarity

In the previous sections, we have looked at various concepts related to lexical semantic
relationships. We will now look at ways to connect similar entities based on their
semantic relationships and also measure semantic similarity between them. Semantic
similarity is different from the conventional similarity metrics discussed in Chapter 6. We
will use some sample synsets related to living entities as shown in the following snippet
for our analysis:

tree = [Link]('tree.n.01')
lion = [Link]('lion.n.01')
tiger = [Link]('tiger.n.02')
cat = [Link]('cat.n.01')
dog = [Link]('dog.n.01')
# create entities and extract names and definitions
entities = [tree, lion, tiger, cat, dog]
entity_names = [[Link]().split('.')[0] for entity in entities]
entity_definitions = [[Link]() for entity in entities]

# print entities and their definitions

In [99]: for entity, definition in zip(entity_names, entity_definitions):
...: print entity, '-', definition

328
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

tree - a tall perennial woody plant having a main trunk and branches forming
a distinct elevated crown; includes both gymnosperms and angiosperms
lion - large gregarious predatory feline of Africa and India having a tawny
coat with a shaggy mane in the male
tiger - large feline of forests in most of Asia having a tawny coat with
black stripes; endangered
cat - feline mammal usually having thick soft fur and no ability to roar:
domestic cats; wildcats
dog - a member of the genus Canis (probably descended from the common wolf)
that has been domesticated by man since prehistoric times; occurs in many
breeds

Now that we know our entities a bit better from these definitions explaining them, we
will try to correlate the entities based on common hypernyms. For each pair of entities,
we will try to find the lowest common hypernym in the relationship hierarchy tree.
Correlated entities are expected to have very specific hypernyms, and unrelated entities
should have very abstract or generic hypernyms. The following code snippet illustrates:

common_hypernyms = []
for entity in entities:
# get pairwise lowest common hypernyms
common_hypernyms.append([entity.lowest_common_hypernyms(compared_entity)[0]
.name().split('.')[0]
for compared_entity in entities])
# build pairwise lower common hypernym matrix
common_hypernym_frame = [Link](common_hypernyms,
index=entity_names,
columns=entity_names)
# print the matrix
In [101]: print common_hypernym_frame
...:
tree lion tiger cat dog
tree tree organism organism organism organism
lion organism lion big_cat feline carnivore
tiger organism big_cat tiger feline carnivore
cat organism feline feline cat carnivore
dog organism carnivore carnivore carnivore dog

Ignoring the main diagonal of the matrix, for each pair of entities, we can see their
lowest common hypernym which depicts the nature of relationship between them. Trees are
unrelated to the other animals except that they are all living organisms. Hence we get the
'organism' relationship amongst them. Cats are related to lions and tigers with respect to
being feline creatures, and we can see the same in the preceding output. Tigers and lions are
connected to each other with the 'big cat' relationship. Finally, we can see dogs having the
relationship of 'carnivore' with the other animals since they all typically eat meat.
We can also measure the semantic similarity between these entities using various
semantic concepts. We will use 'path similarity', which returns a value between [0, 1]
based on the shortest path connecting two terms based on their hypernym/hyponym based
taxonomy. The following snippet shows us how to generate this similarity matrix:

329
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

similarities = []
for entity in entities:
# get pairwise similarities
[Link]([round(entity.path_similarity(compared_entity), 2)
for compared_entity in entities])
# build pairwise similarity matrix
similarity_frame = [Link](similarities,
index=entity_names,
columns=entity_names)
# print the matrix
print similarity_frame

tree lion tiger cat dog

tree 1.00 0.07 0.07 0.08 0.13
lion 0.07 1.00 0.33 0.25 0.17
tiger 0.07 0.33 1.00 0.25 0.17
cat 0.08 0.25 0.25 1.00 0.20
dog 0.13 0.17 0.17 0.20 1.00

From the preceding output, as expected, lion and tiger are the most similar with a
value of 0.33, followed by their semantic similarity with cat having a value of 0.25. And
tree has the lowest semantic similarity values when compared with other animals.
This concludes our discussion on analyzing lexical semantic relations. I encourage
you to try exploring more concepts with different examples by leveraging WordNet.

Word Sense Disambiguation

In the previous section, we looked at homographs and homonyms, which are basically words
that look or sound similar but have very different meanings. This meaning is contextual
based on how it has been used and also depends on the word semantics, also called word
sense. Identifying the correct sense or semantics of a word based on its usage is called word
sense disambiguation with the assumption that the word has multiple meanings based on its
context. This is a very popular problem in NLP and is used in various applications, such as
improving the relevance of search engine results, coherence, and so on.
There are various ways to solve this problem, including lexical and dictionary-based
methods and supervised and unsupervised ML methods. Covering everything would be
out of the current scope, so I will be showing word sense disambiguation using the Lesk
algorithm, a classic algorithm invented by M. E. Lesk in 1986. The basic principle behind
this algorithm is to leverage dictionary or vocabulary definitions for a word we want to
disambiguate in a body of text and compare the words in these definitions with a section
of text surrounding our word of interest. We will be using the WordNet definitions for
words instead of a dictionary. The main objective for us would be to return the synset
with the maximum number of overlapping words or terms between the context sentence
and the different definitions from each synset for the word we target for disambiguation.
The following snippet leverages nltk to depict how to use word sense disambiguation for
various examples:

330
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

from [Link] import lesk

from nltk import word_tokenize

# sample text and word to disambiguate

samples = [('The fruits on that plant have ripened', 'n'),
('He finally reaped the fruit of his hard work as he won the
race', 'n')]
word = 'fruit'
# perform word sense disambiguation
In [106]: for sentence, pos_tag in samples:
...: word_syn = lesk(word_tokenize([Link]()), word, pos_tag)
...: print 'Sentence:', sentence
...: print 'Word synset:', word_syn
...: print 'Corresponding definition:', word_syn.definition()
...: print
Sentence: The fruits on that plant have ripened
Word synset: Synset('fruit.n.01')
Corresponding definition: the ripened reproductive body of a seed plant

Sentence: He finally reaped the fruit of his hard work as he won the race
Word synset: Synset('fruit.n.03')
Corresponding definition: the consequence of some effort or action

# sample text and word to disambiguate

samples = [('Lead is a very soft, malleable metal', 'n'),
('John is the actor who plays the lead in that movie', 'n'),
('This road leads to nowhere', 'v')]
word = 'lead'
# perform word sense disambiguation
In [108]: for sentence, pos_tag in samples:
...: word_syn = lesk(word_tokenize([Link]()), word,
pos_tag)
...: print 'Sentence:', sentence
...: print 'Word synset:', word_syn
...: print 'Corresponding definition:', word_syn.definition()
...: print
Sentence: Lead is a very soft, malleable metal
Word synset: Synset('lead.n.02')
Corresponding definition: a soft heavy toxic malleable metallic element;
bluish white when freshly cut but tarnishes readily to dull grey

Sentence: John is the actor who plays the lead in that movie
Word synset: Synset('star.n.04')
Corresponding definition: an actor who plays a principal role

Sentence: This road leads to nowhere

Word synset: Synset('run.v.23')
Corresponding definition: cause something to pass or lead somewhere

331
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

We try to disambiguate two words, 'fruit' and 'lead' in various text documents
in the preceding examples. You can see how we use the Lesk algorithm to get the correct
word sense for the word we are disambiguating based on its usage and context in each
document. This tells you how fruit can mean both an entity that is consumed as well as
some consequence one faces on applying efforts. We also see how lead can mean the soft
metal, causing something/someone to go somewhere, or even an actor who plays the
main role in a play or movie.

Named Entity Recognition

In any text document, there are particular terms that represent entities that are more
informative and have a unique context compared to the rest of the text. These entities are
known as named entities, which more specifically refers to terms that represent real-world
objects like people, places, organizations, and so on, which are usually denoted by proper
names. We can find these typically by looking at the noun phrases in text documents.
Named entity recognition, also known as entity chunking/extraction, is a popular technique
used in information extraction to identify and segment named entities and classify or
categorize them under various predefined classes. Some of these classes that are used
most frequently are shown in Figure 7-1 (courtesy of nltk and The Stanford NLP group).

Figure 7-1. Common named entities with examples

There is some overlap between GPE and LOCATION. The GPE entities are usually more
generic and represent geo-political entities like cities, states, countries, and continents.
LOCATION can also refer to these entities (it varies across different NER systems) along
with very specific locations like a mountain, river, or hill-station. FACILITY on the other
hand refers to popular monuments or artifacts that are usually man-made. The remaining
categories are pretty self-explanatory from their names and the examples depicted in
Figure 7-1.
The Bundesliga is perhaps the most popular top-level professional association
football league in Germany, and FC Bayern Munchen is one of the most popular clubs
in this league with a global presence. We will now take a sample description of this club

332
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

from Wikipedia and try to extract named entities from it. We will reuse our normalization
module (accessible as [Link] in the code files) from the last chapter in
this section to parse the document to remove unnecessary new lines. We will start by
leveraging nltk’s Named Entity Chunker:

# sample document
text = """
Bayern Munich, or FC Bayern, is a German sports club based in Munich,
Bavaria, Germany. It is best known for its professional football team,
which plays in the Bundesliga, the top tier of the German football
league system, and is the most successful club in German football
history, having won a record 26 national titles and 18 national cups.
FC Bayern was founded in 1900 by eleven football players led by Franz John.
Although Bayern won its first national championship in 1932, the club
was not selected for the Bundesliga at its inception in 1963. The club
had its period of greatest success in the middle of the 1970s when,
under the captaincy of Franz Beckenbauer, it won the European Cup three
times in a row (1974-76). Overall, Bayern has reached ten UEFA Champions
League finals, most recently winning their fifth title in 2013 as part
of a continental treble.
"""

import nltk
from normalization import parse_document
import pandas as pd

# tokenize sentences
sentences = parse_document(text)
tokenized_sentences = [nltk.word_tokenize(sentence) for sentence in
sentences]

# tag sentences and use nltk's Named Entity Chunker

tagged_sentences = [nltk.pos_tag(sentence) for sentence in tokenized_
sentences]
ne_chunked_sents = [nltk.ne_chunk(tagged) for tagged in tagged_sentences]

# extract all named entities

named_entities = []
for ne_tagged_sentence in ne_chunked_sents:
for tagged_tree in ne_tagged_sentence:
# extract only chunks having NE labels
if hasattr(tagged_tree, 'label'):
entity_name = ' '.join(c[0] for c in tagged_tree.leaves()) #
get NE name
entity_type = tagged_tree.label() # get NE category
named_entities.append((entity_name, entity_type))
# get unique named entities
named_entities = list(set(named_entities))

333
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

# store named entities in a data frame

entity_frame = [Link](named_entities,
columns=['Entity Name', 'Entity Type'])
# display results
In [116]: print entity_frame
Entity Name Entity Type
0 Bayern PERSON
1 Franz John PERSON
2 Franz Beckenbauer PERSON
3 Munich ORGANIZATION
4 European ORGANIZATION
5 Bundesliga ORGANIZATION
6 German GPE
7 Bavaria GPE
8 Germany GPE
9 FC Bayern ORGANIZATION
10 UEFA ORGANIZATION
11 Munich GPE
12 Bayern GPE
13 Overall GPE

The Named Entity Chunker identifies named entities from the preceding text
document, and we extract these named entities from the tagged annotated sentences
and display them in the data frame as shown. You can clearly see how it has correctly
identified PERSON, ORGANIZATION, and GPE related named entities, although a few of them
are incorrectly identified.
We will now use the Stanford NER tagger on the same text and compare the results.
For this, you need to have Java installed and then download the Stanford NER resources
from [Link] Unzip them
to a location of your choice (I used E:/stanford in my system). Once done, you can use
nltk’s interface to access this, similar to what we did in Chapter 3 for constituency and
dependency parsing. For more details on Stanford NER, visit [Link]
software/[Link], the official web site, which also contains the latest version of
their Named Entity Recognizer (I used an older version):

from [Link] import StanfordNERTagger

import os

# set java path in environment variables

java_path = r'C:\Program Files\Java\jdk1.8.0_102\bin\[Link]'
[Link]['JAVAHOME'] = java_path

# load stanford NER

sn = StanfordNERTagger('E:/stanford/stanford-ner-2014-08-27/classifiers/
[Link]',
path_to_jar='E:/stanford/stanford-ner-2014-08-27/
[Link]')

334
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

# tag sentences
ne_annotated_sentences = [[Link](sent) for sent in tokenized_sentences]

# extract named entities

named_entities = []
for sentence in ne_annotated_sentences:
temp_entity_name = ''
temp_named_entity = None
for term, tag in sentence:
# get terms with NE tags
if tag != 'O':
temp_entity_name = ' '.join([temp_entity_name, term]).strip() #
get NE name
temp_named_entity = (temp_entity_name, tag) # get NE and its
category
else:
if temp_named_entity:
named_entities.append(temp_named_entity)
temp_entity_name = ''
temp_named_entity = None

# get unique named entities

named_entities = list(set(named_entities))
# store named entities in a data frame
entity_frame = [Link](named_entities,
columns=['Entity Name', 'Entity Type'])

# display results
In [118]: print entity_frame
Entity Name Entity Type
0 Franz John PERSON
1 Franz Beckenbauer PERSON
2 Germany LOCATION
3 Bayern ORGANIZATION
4 Bavaria LOCATION
5 Munich LOCATION
6 FC Bayern ORGANIZATION
7 UEFA ORGANIZATION
8 Bayern Munich ORGANIZATION

The preceding output depicts various named entities obtained from our document.
You can compare this with the results obtained from nltk’s NER chunker. The results here
are definitely better—there are no misclassifications and each category is also assigned
correctly. Some really interesting points: It has correctly identified Munich as a LOCATION
and Bayern Munich as an ORGANIZATION. Does this mean the second NER tagger is better?
Not really. It depends on the type of corpus you are analyzing, and you can even build
your own NER tagger using supervised learning by training on pre-tagged corpora similar
to what we did in Chapter 3. In fact, both the taggers just discussed have been trained on
pre-tagged corpora like CoNLL, MUC, and Penn Treebank.

335
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Analyzing Semantic Representations

We usually communicate in the form of messages in spoken form or in written form
with other people or interfaces. Each of these messages is typically a collection of words,
phrases, or sentences, and they have their own semantics and context. So far, we’ve talked
about semantics and relations between various lexical units. But how do we represent the
meaning of semantics conveyed by a message or messages? How do humans understand
what someone is telling them? How do we believe in statements and propositions and
evaluate outcomes and what action to take? It feels easy because the brain helps us with
logic and reasoning—but computationally can we do the same?
The answer is yes we can. Frameworks like propositional logic and first-order logic
help us in representation of semantics. We discussed this in detail in Chapter 1 in the
subsection “Representation of Semantics” under the “Language Semantics” section. I
encourage you to go through that once more to refresh your memory. In the following
sections, we will look at ways to represent propositional and first order logic and prove or
disprove propositions, statements, and predicates using practical examples and code.

Propositional Logic
We have already discussed propositional logic (PL) as the study of propositions,
statements, and sentences. A proposition is usually declarative, having a binary value
of being either true or false. There also exist various logical operators like conjunction,
disjunction, implication, and equivalence, and we also study the effects of applying these
operators on multiple propositions to understand their behavior and outcome.
Let us consider our example from Chapter 1 with regard to two propositions P and Q
such that they can be represented as follows:
P: He is hungry
Q: He will eat a sandwich
We will now try to build the truth tables for various operations on these propositions
using nltk based on the various logical operators discussed in Chapter 1 (refer to the
“Propositional Logic” section for more details) and derive outcomes computationally:

import nltk
import pandas as pd
import os

# assign symbols and propositions

symbol_P = 'P'
symbol_Q = 'Q'
proposition_P = 'He is hungry'
propositon_Q = 'He will eat a sandwich'
# assign various truth values to the propositions
p_statuses = [False, False, True, True]
q_statuses = [False, True, False, True]
# assign the various expressions combining the logical operators
conjunction = '(P & Q)'
disjunction = '(P | Q)'
implication = '(P -> Q)'

336
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

equivalence = '(P <-> Q)'

expressions = [conjunction, disjunction, implication, equivalence]

# evaluate each expression using propositional logic

results = []
for status_p, status_q in zip(p_statuses, q_statuses):
dom = set([])
val = [Link]([(symbol_P, status_p),
(symbol_Q, status_q)])
assignments = [Link](dom)
model = [Link](dom, val)
row = [status_p, status_q]
for expression in expressions:
# evaluate each expression based on proposition truth values
result = [Link](expression, assignments)
[Link](result)
[Link](row)
# build the result table
columns = [symbol_P, symbol_Q, conjunction,
disjunction, implication, equivalence]
result_frame = [Link](results, columns=columns)

# display results
In [125]: print 'P:', proposition_P
...: print 'Q:', propositon_Q
...: print
...: print 'Expression Outcomes:-'
...: print result_frame
P: He is hungry
Q: He will eat a sandwich

Expression Outcomes:-
P Q (P & Q) (P | Q) (P -> Q) (P <-> Q)
0 False False False False True True
1 False True False True True False
2 True False False True False False
3 True True True True True True

The preceding output depicts the various truth values of the two propositions, and
when we combine them with various logical operators, you will find the results matching
with what we manually evaluated in Chapter 1. For example, P & Q indicates He is hungry
and he will eat a sandwich is True only when both of the individual propositions is True.
We use nltk’s Valuation class to create a dictionary of the propositions and their various
outcome states. We use the Model class to evaluate each expression, where the evaluate()
function internally calls the recursive function satisfy(), which helps in evaluating the
outcome of each expression with the propositions based on the assigned truth values.

337
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

First Order Logic

PL has several limitations, like the inability to represent facts or complex relationships
and inferences. PL also has limited expressive power because for each new proposition
we would need a unique symbolic representation, and it becomes very difficult to
generalize facts. This is where first order logic (FOL) works really well with features
like functions, quantifiers, relations, connectives, and symbols. It definitely provides a
richer and more powerful representation for semantic information. The “First Order
Logic” subsection under “Representation of Semantics” in Chapter 1 provides detailed
information about how FOL works.
In this section, we will build several FOL representations similar to what we did
manually in Chapter 1 using mathematical representations. Here we will build them
in our code using similar syntax and leverage nltk and some theorem provers to prove
the outcome of various expressions based on predefined conditions and relationships,
similar to what we did for PL. The key takeaway for you from this section should be
getting to know how to represent FOL representations in Python and how to perform FOL
inference using proofs based on some goal and predefined rules and events. There are
several theorem provers you can use for evaluating expressions and proving theorems.
The nltk package has three main different types of provers: Prover9, TableauProver, and
ResolutionProver. The first one is a free-to-use prover available for download at www.
[Link]/~mccune/prover9/download/. You can extract the contents in a location of
your choice (I used E:/prover9). We will be using both ResolutionProver and Prover9
in our examples. The following snippet helps in setting up the necessary dependencies
for FOL expressions and evaluations:

import nltk
import os
# for reading FOL expressions
read_expr = [Link]
# initialize theorem provers (you can choose any)
[Link]['PROVER9'] = r'E:/prover9/bin'
prover = nltk.Prover9()
# I use the following one for our examples
prover = [Link]()

Now that we have our dependencies ready, let us evaluate a few FOL expressions.
Consider a simple expression that If an entity jumps over another entity, the reverse cannot
happen. Assuming the entities to be x and y, we can represent this is FOL as x y
(jumps_over(x, y) → ¬jumps_over(y, x)) which signifies that for all x and y, if x jumps
over y, it implies that y cannot jump over x. Consider now that we have two entities fox
and dog such that the fox jumps over the dog is an event which has taken place and can
be represented by jumps_over(fox, dog). Our end goal or objective is to evaluate the
outcome of jumps_over(dog, fox) considering the preceding expression and the event
that has occurred. The following snippet shows us how we can do this:

# set the rule expression

rule = read_expr('all x. all y. (jumps_over(x, y) -> -jumps_over(y, x))')
# set the event occured

338
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

event = read_expr('jumps_over(fox, dog)')

# set the outcome we want to evaluate -- the goal
test_outcome = read_expr('jumps_over(dog, fox)')

# get the result

In [132]: [Link](goal=test_outcome,
...: assumptions=[event, rule],
...: verbose=True)
[1] {-jumps_over(dog,fox)} A
[2] {jumps_over(fox,dog)} A
[3] {-jumps_over(z4,z3), -jumps_over(z3,z4)} A
[4] {-jumps_over(dog,fox)} (2, 3)

Out[132]: False

The preceding output depicts the final result for our goal test_outcome is False, that
is, the dog cannot jump over the fox if the fox has already jumped over the dog based on
our rule expression and the events assigned to the assumptions parameter in the prover
already given. The sequence of steps that lead to the result is also shown in the output.
Let us now consider another FOL expression rule x studies(x, exam) → pass(x,
exam), which tells us that for all instances of x, if x studies for the exam, he/she will pass
the exam. Let us represent this rule and consider two students, John and Pierre, such
that John does not study for the exam and Pierre does. Can we then find out the outcome
whether they will pass the exam based on the given expression rule? The following
snippet shows us how:

# set the rule expression

rule = read_expr('all x. (studies(x, exam) -> pass(x, exam))')
# set the events and outcomes we want to determine
event1 = read_expr('-studies(John, exam)')
test_outcome1 = read_expr('pass(John, exam)')
event2 = read_expr('studies(Pierre, exam)')
test_outcome2 = read_expr('pass(Pierre, exam)')

# get results
In [134]: [Link](goal=test_outcome1,
...: assumptions=[event1, rule],
...: verbose=True)
[1] {-pass(John,exam)} A
[2] {-studies(John,exam)} A
[3] {-studies(z6,exam), pass(z6,exam)} A
[4] {-studies(John,exam)} (1, 3)

Out[134]: False

In [135]: [Link](goal=test_outcome2,
...: assumptions=[event2, rule],
...: verbose=True)

339
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

[1] {-pass(Pierre,exam)} A
[2] {studies(Pierre,exam)} A
[3] {-studies(z8,exam), pass(z8,exam)} A
[4] {-studies(Pierre,exam)} (1, 3)
[5] {pass(Pierre,exam)} (2, 3)
[6] {} (1, 5)

Out[135]: True

Thus you can see from the above evaluations that Pierre does pass the exam
because he studied for the exam, unlike John who doesn't pass the exam since he did not
study for it.
Let us consider a more complex example with several entities. They perform several
actions as follows:
• There are two dogs rover (r) and alex (a)
• There is one cat garfield (g)
• There is one fox felix (f)
• Two animals, alex (a) and felix (f) run, denoted by function
runs()
• Two animals rover (r) and garfield (g) sleep, denoted by
function sleeps()
• Two animals, felix (f) and alex (a) can jump over the other two,
denoted by function jumps_over()
Taking all these assumptions, the following snippet builds an FOL-based model
with the previously mentioned domain and assignment values based on the entities
and functions. Once we build this model, we evaluate various FOL-based expressions to
determine their outcome and prove some theorems like we did earlier:

# define symbols (entities\functions) and their values

rules = """
rover => r
felix => f
garfield => g
alex => a
dog => {r, a}
cat => {g}
fox => {f}
runs => {a, f}
sleeps => {r, g}
jumps_over => {(f, g), (a, g), (f, r), (a, r)}
"""
val = [Link](rules)
# view the valuation object of symbols and their assigned values
(dictionary)

340
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

In [143]: print val

{'rover': 'r', 'runs': set([('f',), ('a',)]), 'alex': 'a', 'sleeps':
set([('r',), ('g',)]), 'felix': 'f', 'fox': set([('f',)]), 'dog':
set([('a',), ('r',)]), 'jumps_over': set([('a', 'g'), ('f', 'g'), ('a',
'r'), ('f', 'r')]), 'cat': set([('g',)]), 'garfield': 'g'}

# define domain and build FOL based model

dom = {'r', 'f', 'g', 'a'}
m = [Link](dom, val)

# evaluate various expressions

In [148]: print [Link]('jumps_over(felix, rover) & dog(rover) &
runs(rover)', None)
False

In [149]: print [Link]('jumps_over(felix, rover) & dog(rover) &

-runs(rover)', None)
True

In [150]: print [Link]('jumps_over(alex, garfield) & dog(alex) &

cat(garfield) & sleeps(garfield)', None)
True

# assign rover to x and felix to y in the domain

g = [Link](dom, [('x', 'r'), ('y', 'f')])

# evaluate more expressions based on above assigned symbols

In [152]: print [Link]('runs(y) & jumps_over(y, x) & sleeps(x)', g)
True

In [153]: print [Link]('exists y. (fox(y) & runs(y))', g)

True

The preceding snippet depicts the evaluation of various expressions based on the
valuation of different symbols based on the rules and domain. We create various FOL-
based expressions and see their outcome based on the predefined assumptions. For
example, the first expression gives us False because rover never runs() and the second
and third expressions are True because they satisfy all the conditions like felix and alex
can jump over rover or garfield and rover is a dog that does not run and garfield is
a cat. The second set of expressions is evaluated based on assigning felix and rover to
specific symbols in our domain (dom), and we pass that variable (g) when evaluating the
expressions. We can even satisfy open formulae or expressions using the satisfiers()
function as shown here:

# who are the animals who run?

In [154]: formula = read_expr('runs(x)')
...: print [Link](formula, 'x', g)
set(['a', 'f'])

341
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

# animals who run and are also a fox?

In [155]: formula = read_expr('runs(x) & fox(x)')
...: print [Link](formula, 'x', g)
set(['f'])

The preceding outputs are self-explanatory wherein we evaluate open-ended

questions like which animals run? And also which animals can run and are also foxes?
We get the relevant symbols in our outputs, which you can map back to the actual
animal names (Hint: a: alex, f: felix). I encourage you to experiment with more
propositions and FOL expressions by building your own assumptions, domain, and rules.

Sentiment Analysis
We will now discuss several concepts, techniques, and examples with regard to our second
major topic in this chapter, sentiment analysis. Textual data, even though unstructured,
mainly has two broad types of data points: factual based (objective) and opinion based
(subjective). We briefly talked about these two categories at the beginning of this chapter
when I introduced the concept of sentiment analysis and how it works best on text that has
a subjective context. In general, social media, surveys, and feedback data all are heavily
opinionated and express the beliefs, judgement, emotion, and feelings of human beings.
Sentiment analysis, also popularly known as opinion analysis/mining, is defined as the
process of using techniques like NLP, lexical resources, linguistics, and machine learning
(ML) to extract subjective and opinion related information like emotions, attitude, mood,
modality, and so on and try to use these to compute the polarity expressed by a text
document. By polarity, I mean to find out whether the document expresses a positive,
negative, or a neutral sentiment. More advanced analysis involves trying to find out more
complex emotions like sadness, happiness, anger, and sarcasm.
Typically, sentiment analysis for text data can be computed on several levels,
including on an individual sentence level, paragraph level, or the entire document as a
whole. Often sentiment is computed on the document as a whole or some aggregations
are done after computing the sentiment for individual sentences. Polarity analysis usually
involves trying to assign some scores contributing to the positive and negative emotions
expressed in the document and then finally assigning a label to the document based on
the aggregate score. We will depict two major techniques for sentiment analysis here:
• Supervised machine learning
• Unsupervised lexicon-based
The key idea is to learn the various techniques typically used to tackle sentiment
analysis problems so that you can apply them to solve your own problems. We will
see how to re-use the concepts of supervised machine learning based classification
algorithms from Chapter 4 here to classify documents to their associated sentiment. We
will also use lexicons, which are dictionaries or vocabularies specially constructed to
be used for sentiment analysis, and compute sentiment without using any supervised
techniques. We will be carrying out our experiments on a large real-world dataset
pertaining to movie reviews, which will make this task more interesting. We will compare
the performance of the various algorithms and also try to perform some detailed analytics
besides just analyzing polarity, which includes analyzing the subjectivity, mood, and
modality of the movie reviews. Without further delay, let’s get started!
342
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Sentiment Analysis of IMDb Movie Reviews

We will be using a dataset of movie reviews obtained from the Internet Movie Database
(IMDb) for sentiment analysis. This dataset, containing over 50,000 movie reviews, can be
obtained from [Link] courtesy of Stanford
University and A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, Andrew Ng, and C. Potts,
and this dataset was used in their famous paper, “Learning Word Vectors for Sentiment
Analysis.” We will be using 50,000 movie reviews from this dataset, which contain the
review and a corresponding sentiment polarity label which is either positive or negative.
A positive review is basically a movie review which was rated with more than six stars in
IMDb, and a negative review was rated with less than five stars in IMDb. An important
thing to remember here before we begin our exercise is the fact that many of these reviews,
even though labeled positive or negative, might have some elements of negative or positive
context respectively. Hence, there is a possibility for some overlap in many reviews, which
make this task harder. Sentiment is not a quantitative number that you can compute and
prove mathematically. It expresses complex emotions, feelings, and judgement, and hence
you should never focus on trying to get a cent-percent perfect model but a model that
generalizes well on data and works decently. We will start with setting up some necessary
dependencies and utilities before moving on to the various techniques.

Setting Up Dependencies
There are several utility functions, data, and package dependencies that we need to set
up before we jump into sentiment analysis. We will need our movie review dataset, some
specific packages that we will be using in our implementations, and we will be defining
some utility functions for text normalization, feature extracting, and model evaluation,
similar to what we have used in previous chapters.

Getting and Formatting the Data

We will use the IMDb movie review dataset officially available in raw text files for each
set (training and testing) from [Link] as
mentioned. You can download and unzip the files to a location of your choice and use
the review_data_extractor.py file included along with the code files of this chapter to
extract each review from the unzipped directory, parse them, and neatly format them into
a data frame, which is then stored as a csv file named movie_reviews.csv. Otherwise,
you can directly download the parsed and formatted file from [Link]
dipanjanS/text-analytics-with-python/tree/master/Chapter-7, which contains all
datasets and code used and is the official repository for this book. The data frame consists
of two columns, review and sentiment, for each data point, which indicates the review
for a movie and its corresponding sentiment (positive or negative).

Text Normalization
We will be normalizing and standardizing our text data similar to what we did in Chapter
6 as a part of text pre-processing and normalization. For this we will be re-using our
[Link] module from Chapter 6 with a few additions. This mainly includes

343
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

adding an HTML stripper to remove unnecessary HTML characters from text documents,
as shown here:

from HTMLParser import HTMLParser

class MLStripper(HTMLParser):
def __init__(self):
[Link]()
[Link] = []
def handle_data(self, d):
[Link](d)
def get_data(self):
return ' '.join([Link])

def strip_html(text):
html_stripper = MLStripper()
html_stripper.feed(text)
return html_stripper.get_data()

We also add a new function to normalize special accented characters and convert
them into regular ASCII characters so as to standardize the text across all documents. The
following snippet helps us achieve this:

def normalize_accented_characters(text):
text = [Link]('NFKD',
[Link]('utf-8')
).encode('ascii', 'ignore')
return text

The overall text normalization function is depicted in the following snippet and it
re-uses the expand contractions, lemmatization, HTML unescaping, special characters
removal, and stopwords removal functions from the previous chapter's normalization
module:

def normalize_corpus(corpus, lemmatize=True,

only_text_chars=False,
tokenize=False):

normalized_corpus = []
for index, text in enumerate(corpus):
text = normalize_accented_characters(text)
text = html_parser.unescape(text)
text = strip_html(text)
text = expand_contractions(text, CONTRACTION_MAP)
if lemmatize:
text = lemmatize_text(text)
else:

344
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

text = [Link]()
text = remove_special_characters(text)
text = remove_stopwords(text)
if only_text_chars:
text = keep_text_characters(text)

if tokenize:
text = tokenize_text(text)
normalized_corpus.append(text)
else:
normalized_corpus.append(text)

return normalized_corpus

To re-use this code, you can make use of the [Link] and contractions.
py files provided with the code files of this chapter.

Feature Extraction
We will be reusing the same feature-extraction function we used in Chapter 6, and it is
available as a part of the [Link] module. The function is shown here for the sake of
completeness:

from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizer

def build_feature_matrix(documents, feature_type='frequency',

ngram_range=(1, 1), min_df=0.0, max_df=1.0):

feature_type = feature_type.lower().strip()

if feature_type == 'binary':
vectorizer = CountVectorizer(binary=True, min_df=min_df,
max_df=max_df, ngram_range=ngram_range)
elif feature_type == 'frequency':
vectorizer = CountVectorizer(binary=False, min_df=min_df,
max_df=max_df, ngram_range=ngram_range)
elif feature_type == 'tfidf':
vectorizer = TfidfVectorizer(min_df=min_df, max_df=max_df,
ngram_range=ngram_range)
else:
raise Exception("Wrong feature type entered. Possible values:
'binary', 'frequency', 'tfidf'")

feature_matrix = vectorizer.fit_transform(documents).astype(float)
return vectorizer, feature_matrix

345
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

You can experiment with various features provided by this function, which include
Bag of Words-based frequencies, occurrences, and TF-IDF based features.

Model Performance Evaluation

We will be evaluating our models based on precision, recall, accuracy, and F1-score,
similar to our evaluation methods in Chapter 4 for text classification. Additionally we
will be looking at the confusion matrix and detailed classification reports for each class,
that is, the positive and negative classes to evaluate model performance. You can refer to
the “Evaluating Classification Models” section in Chapter 4 to refresh your memory on
the various model-evaluation metrics. The following function will help us in getting the
model accuracy, precision, recall, and F1-score:

from sklearn import metrics

import numpy as np
import pandas as pd

def display_evaluation_metrics(true_labels, predicted_labels, positive_

class=1):
print 'Accuracy:', [Link](
metrics.accuracy_score(true_labels,
predicted_labels),
2)
print 'Precision:', [Link](
metrics.precision_score(true_labels,
predicted_labels,
pos_label=positive_class,
average='binary'),
2)
print 'Recall:', [Link](
metrics.recall_score(true_labels,
predicted_labels,
pos_label=positive_class,
average='binary'),
2)
print 'F1 Score:', [Link](
metrics.f1_score(true_labels,
predicted_labels,
pos_label=positive_class,
average='binary'),
2)

We will also define a function to help us build the confusion matrix for evaluating
the model predictions against the actual sentiment labels for the reviews. The following
function will help us achieve that:

346
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

def display_confusion_matrix(true_labels, predicted_labels, classes=[1,0]):

cm = metrics.confusion_matrix(y_true=true_labels,
y_pred=predicted_labels,
labels=classes)
cm_frame = [Link](data=cm,
columns=[Link](levels=[['Predicted:'],
classes],
labels=[[0,0],[0,1]]),
index=[Link](levels=[['Actual:'],
classes],
labels=[[0,0],[0,1]]))
print cm_frame

Finally, we will define a function for getting a detailed classification report per
sentiment category (positive and negative) by displaying the precision, recall, F1-score,
and support (number of reviews) for each of the classes:

def display_classification_report(true_labels, predicted_labels,

classes=[1,0]):
report = metrics.classification_report(y_true=true_labels,
y_pred=predicted_labels,
labels=classes)
print report

You will find all the preceding functions in the [Link] module along with the other
code files for this chapter and you can re-use them as needed. Besides this, you need to
make sure you have nltk and pattern installed—which you should already have by this
point of time because we have used them numerous times in our previous chapters.

Preparing Datasets
We will be loading our movie reviews data and preparing two datasets, namely training
and testing, similar to what we did in Chapter 4. We will train our supervised model on
the training data and evaluate model performance on the testing data. For unsupervised
models, we will directly evaluate them on the testing data so as to compare their
performance with the supervised model. Besides that, we will also pick some sample
positive and negative reviews to see how the different models perform on them:

import pandas as pd
import numpy as np
# load movie reviews data
dataset = pd.read_csv(r'E:/aclImdb/movie_reviews.csv')
# print sample data
In [235]: print [Link]()
review sentiment
0 One of the other reviewers has mentioned that ... positive
1 A wonderful little production. <br /><br />The... positive
2 I thought this was a wonderful way to spend ti... positive

347
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

3 Basically there's a family where a little boy ... negative

4 Petter Mattei's "Love in the Time of Money" is... positive

# prepare training and testing datasets

train_data = dataset[:35000]
test_data = dataset[35000:]

train_reviews = [Link](train_data['review'])
train_sentiments = [Link](train_data['sentiment'])
test_reviews = [Link](test_data['review'])
test_sentiments = [Link](test_data['sentiment'])

# prepare sample dataset for experiments

sample_docs = [100, 5817, 7626, 7356, 1008, 7155, 3533, 13010]
sample_data = [(test_reviews[index],
test_sentiments[index])
for index in sample_docs]

We have taken a total of 35,000 reviews out of the 50,000 to be our training dataset
and we will evaluate our models and test them on the remaining 15,000 reviews. This is in
line with a typical 70:30 separation used for training and testing dataset building. We have
also extracted a total of eight reviews from the test dataset and we will be looking closely
at the results for these documents as well as evaluating the model performance on the
complete test dataset in the following sections.

Supervised Machine Learning Technique

As mentioned before, in this section we will be building a model to analyze sentiment
using supervised ML. This model will learn from past reviews and their corresponding
sentiment from the training dataset so that it can predict the sentiment for new reviews
from the test dataset. The basic principle here is to use the same concepts we used for
text classification such that the classes to predict here are positive and negative sentiment
corresponding to the movie reviews.
We will be following the same workflow which we followed in Chapter 4 for text
classification (refer to Figure 4-2 in Chapter 4) in the “Text Classification Blueprint”
section. The following points summarize these steps:

1. Model training
a. Normalize training data
b. Extract features and build feature set and feature
vectorizer
c. Use supervised learning algorithm (SVM) to build a
predictive model

348
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

2. Model testing
a. Normalize testing data
b. Extract features using training feature vectorizer
c. Predict the sentiment for testing reviews using training
model
d. Evaluate model performance
To start, we will be building our training model using the steps in point 1. We will be
using our normalization and feature-extraction modules discussed in previous sections:

from normalization import normalize_corpus

from utils import build_feature_matrix

# normalization
norm_train_reviews = normalize_corpus(train_reviews, lemmatize=True, only_
text_chars=True)
# feature extraction
vectorizer, train_features = build_feature_matrix(documents=norm_train_
reviews,
feature_type='tfidf',
ngram_range=(1, 1),
min_df=0.0, max_df=1.0)

We will now build our model using the support vector machine (SVM) algorithm which
we used for text classification in Chapter 4. Refer to the “Support Vector Machines” subsection
under the “Classification Algorithms” section in Chapter 4 to refresh your memory:

from sklearn.linear_model import SGDClassifier

# build the model
svm = SGDClassifier(loss='hinge', n_iter=200)
[Link](train_features, train_sentiments)

The preceding snippet trainings the classifier and builds the model that is in the
svm variable, which we can now use for predicting sentiment for new movie reviews (not
used for training) from the test dataset. Let us normalize and extract features from the test
dataset first as mentioned in step 2 in our workflow:

# normalize reviews
norm_test_reviews = normalize_corpus(test_reviews, lemmatize=True, only_
text_chars=True)
# extract features
test_features = [Link](norm_test_reviews)

Now that we have our features for the entire test dataset, before we predict the
sentiment and measure model prediction performance for the entire test dataset, let us
look at some of the predictions for the sample documents we extracted earlier:

349
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

# predict sentiment for sample docs from test data

In [253]: for doc_index in sample_docs:
...: print 'Review:-'
...: print test_reviews[doc_index]
...: print 'Actual Labeled Sentiment:', test_sentiments[doc_index]
...: doc_features = test_features[doc_index]
...: predicted_sentiment = [Link](doc_features)[0]
...: print 'Predicted Sentiment:', predicted_sentiment
...: print
...:
...:
Review:-
Worst movie, (with the best reviews given it) I've ever seen. Over the top
dialog, acting, and direction. more slasher flick than [Link] all the
great reviews this movie got I'm appalled that it turned out so silly. shame
on you martin scorsese
Actual Labeled Sentiment: negative
Predicted Sentiment: negative

Review:-
I hope this group of film-makers never re-unites.
Actual Labeled Sentiment: negative
Predicted Sentiment: negative

Review:-
no comment - stupid movie, acting average or worse... screenplay - no sense
at all... SKIP IT!
Actual Labeled Sentiment: negative
Predicted Sentiment: negative

Review:-
Add this little gem to your list of holiday regulars. It is<br /><br
/>sweet, funny, and endearing
Actual Labeled Sentiment: positive
Predicted Sentiment: positive

Review:-
a mesmerizing film that certainly keeps your attention... Ben Daniels is
fascinating (and courageous) to watch.
Actual Labeled Sentiment: positive
Predicted Sentiment: positive

Review:-
This movie is perfect for all the romantics in the world. John Ritter has
never been better and has the best line in the movie! "Sam" hits close to
home, is lovely to look at and so much fun to play along with. Ben Gazzara
was an excellent cast and easy to fall in love with. I'm sure I've met
Arthur in my travels somewhere. All around, an excellent choice to pick up
any evening.!:-)

350
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Actual Labeled Sentiment: positive

Predicted Sentiment: positive

Review:-
I don't care if some people voted this movie to be bad. If you want the
Truth this is a Very Good Movie! It has every thing a movie should have. You
really should Get this one.
Actual Labeled Sentiment: positive
Predicted Sentiment: negative

Review:-
Worst horror film ever but funniest film ever rolled in one you have got
to see this film it is so cheap it is unbeliaveble but you have to see it
really!!!! P.s watch the carrot
Actual Labeled Sentiment: positive
Predicted Sentiment: negative

You can look at each review, its actual labeled sentiment, and our predicted sentiment
in the preceding output and see that we have some negative and positive reviews, and our
model is able to correctly identify the sentiment for most of the sampled reviews except
the last two reviews. If you look closely at the last two reviews, some part of the review has
a negative sentiment ("worst horror film", "voted this movie to be bad") but the
general sentiment or opinion of the person who wrote the review was intended positive.
These are the examples I mentioned earlier about the overlap of positive and negative
emotions, which makes it difficult for the model to predict the actual sentiment!
Let us now predict the sentiment for all our test dataset reviews and evaluate our
model performance:

# predict the sentiment for test dataset movie reviews

predicted_sentiments = [Link](test_features)

# evaluate model prediction performance

from utils import display_evaluation_metrics, display_confusion_matrix,
display_classification_report

# show performance metrics

In [270]: display_evaluation_metrics(true_labels=test_sentiments,
...: predicted_labels=predicted_sentiments,
...: positive_class='positive')
Accuracy: 0.89
Precision: 0.88
Recall: 0.9
F1 Score: 0.89

# show confusion matrix

In [271]: display_confusion_matrix(true_labels=test_sentiments,
...: predicted_labels=predicted_sentiments,
...: classes=['positive', 'negative'])

351
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Predicted:
positive negative
Actual: positive 6770 740
negative 912 6578

# show detailed per-class classification report

In [272]: display_classification_report(true_labels=test_sentiments,
...: predicted_labels=predicted_
sentiments,
...: classes=['positive', 'negative'])
precision recall f1-score support

positive 0.88 0.90 0.89 7510

negative 0.90 0.88 0.89 7490

avg / total 0.89 0.89 0.89 15000

The preceding outputs show the various performance metrics that depict the
performance of our SVM model with regard to predicting sentiment for movie reviews.
We have an average sentiment prediction accuracy of 89 percent, which is really good if
you compare it with standard baselines for text classification using supervised techniques.
The classification report also shows a per-class detailed report, and we see that our F1-
score (harmonic mean of precision and recall) is 89 percent for both positive and negative
sentiment. The support metric shows the number of reviews having positive (7510)
sentiment and negative (7490) sentiment. The confusion matrix shows how many reviews
for which we predicted the correct sentiment (positive: 6770/7510, negative: 6578/7490)
and the number of reviews for which we predicted the wrong sentiment (positive: 740/7510,
negative: 912/7490). Do try out building more models with different features (Chapter
4 talks about different feature-extraction techniques) and different supervised learning
algorithms. Can you get a better model which predicts sentiment more accurately?

Unsupervised Lexicon-based Techniques

So far, we used labeled training data to learn patterns using features from the movie
reviews and their corresponding sentiment. Then we applied this knowledge learned on
new movie reviews (the testing dataset) to predict their sentiment. Often, you may not
have the convenience of a well-labeled training dataset. In those situations, you need
to use unsupervised techniques for predicting the sentiment by using knowledgebases,
ontologies, databases, and lexicons that have detailed information specially curated and
prepared just for sentiment analysis.
As mentioned, a lexicon is a dictionary, vocabulary, or a book of words. In our case,
lexicons are special dictionaries or vocabularies that have been created for analyzing
sentiment. Most of these lexicons have a list of positive and negative polar words with
some score associated with them, and using various techniques like the position of words,
surrounding words, context, parts of speech, phrases, and so on, scores are assigned to
the text documents for which we want to compute the sentiment. After aggregating these
scores, we get the final sentiment. More advanced analyses can also be done, including
detecting the subjectivity, mood, and modality. Various popular lexicons are used for
sentiment analysis, including the following:
352
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

• AFINN lexicon
• Bing Liu’s lexicon
• MPQA subjectivity lexicon
• SentiWordNet
• VADER lexicon
• Pattern lexicon
This is not an exhaustive list of lexicons that can be leveraged for sentiment analysis,
and there are several other lexicons which can be easily obtained from the Internet.
We will briefly discuss each lexicon and will be using the last three lexicons to analyze
the sentiment for our testing dataset in more detail. Although these techniques are
unsupervised, you can also use them to analyze and evaluate the sentiment for the
training dataset too, but for the sake of consistency and to compare model performances
with the supervised model, we will be performing all our analyses on the testing dataset.

AFINN Lexicon
The AFINN lexicon was curated and created by Finn Årup Nielsen, and more details are
mentioned in his paper “A New ANEW: Evaluation of a Word List for Sentiment Analysis
in Microblogs.” The latest version, known as AFINN-111, consists of a total of 2477 words
and phrases with their own scores based on sentiment polarity. The polarity basically
indicates how positive, negative, or neutral the term might be with some numerical
score. You can download it from [Link]/pubdb/views/publication_details.
php?id=6010. It also talks about the lexicon in further details. The author of this lexicon
has also built a Python wrapper over the AFINN lexicon, which you can directly use to
predict the sentiment of text data. The repository is available from GitHub at https://
[Link]/fnielsen/afinn. You can install the afinn library directly and start
analyzing sentiment. This library even has support for emoticons and smileys. Following
is a sample of the AFINN-111 lexicon:

abandon -2
abandoned -2
abandons -2
abducted -2
abduction -2
...
...
youthful 2
yucky -2
yummy 3
zealot -2
zealots -2
zealous 2

353
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

The basic idea is to load the entire list of polar words and phrases in the lexicon
along with their corresponding score (sample shown above) in memory and then find the
same words/phrases and score them accordingly in a text document. Finally, these scores
are aggregated, and the final sentiment and score can be obtained for a text document.
Following is an example snippet based on the official documentation:

from afinn import Afinn

afn = Afinn(emoticons=True)

In [281]: print [Link]('I really hated the plot of this movie')

-3.0
In [282]: print [Link]('I really hated the plot of this movie :(')
-5.0

Thus you can use the score() function directly to evaluate the sentiment of your text
documents, and from the preceding output you can see that they even give proper weightage
to emoticons, which are used extensively in social media like Twitter and Facebook.

Bing Liu’s Lexicon

This lexicon has been developed by Bing Liu over several years and is discussed in
further details in his paper, by Nitin Jindal and Bing Liu, “Identifying Comparative
Sentences in Text Documents.” You can get more details about the lexicon at https://
[Link]/~liub/FBS/[Link]#lexicon, which also includes a
link to download it as an archive (RAR format). This lexicon consists of over 6800 words
divided into two files named [Link], containing around 2000+ words/
phrases, and [Link], which contains around 4800+ words/phrases. The
key idea is to leverage these words to contribute to the positive or negative polarity of
any text document when they are identified in that document. This lexicon also includes
many misspelled words, taking into account that words or terms are often misspelled on
popular social media web sites.

MPQA Subjectivity Lexicon

MPQA stands for Multi-Perspective Question Answering, and it hosts a plethora of
resources maintained by the University of Pittsburgh. It contains resources including
opinion corpora, subjectivity lexicon, sense annotations, argument-based lexicon, and
debate datasets. A lot of these can be leveraged for complex analysis of human emotions
and sentiment. The subjectivity lexicon is maintained by Theresa Wilson, Janyce Wiebe,
and Paul Hoffmann, and is discussed in detail in their paper, “Recognizing Contextual
Polarity in Phrase-Level Sentiment Analysis,” which focuses on contextual polarity. You
can download the subjectivity lexicon from [Link]
lexicon/, which is their official website. It has subjectivity clues present in the dataset
named [Link], which is available once you extract the archive.
Some sample lines from the dataset are depicted as follows:

354
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

type=weaksubj len=1 word1=abandoned pos1=adj stemmed1=n

priorpolarity=negative
type=weaksubj len=1 word1=abandonment pos1=noun stemmed1=n
priorpolarity=negative
type=weaksubj len=1 word1=abandon pos1=verb stemmed1=y
priorpolarity=negative
type=strongsubj len=1 word1=abase pos1=verb stemmed1=y
priorpolarity=negative
...
...
type=strongsubj len=1 word1=zealously pos1=anypos stemmed1=n
priorpolarity=negative
type=strongsubj len=1 word1=zenith pos1=noun stemmed1=n
priorpolarity=positive
type=strongsubj len=1 word1=zest pos1=noun stemmed1=n priorpolarity=positive

To understand this data, you can refer to the readme file provided along with the
dataset. Basically, the clues in this dataset were curated and collected manually with
efforts by the above-mentioned maintainers of this project. The various parameters
mentioned above are explained briefly as follows:

• type: This has values that are either strongsubj indicating the
presence of a strongly subjective context or weaksubj which
indicates the presence of a weak/part subjective context.
• len: This points to the number of words in the term of the clue (all
are single words of length 1 for now).
• word1: The actual term present as a token or a stem of the actual
token.
• pos1: The part of speech for the term (clue) and it can be noun,
verb, adj, adverb, or anypos.
• stemmed1: This indicates if the clue (term) is stemmed (y) or not
stemmed (n). If it is stemmed, it can match all its other variants
having the same pos1 tag.
• priorpolarity: This has values of negative, positive, both, or
neutral, and indicates the polarity of the sentiment associated
with this clue (term).

The idea is to load this lexicon into a database or memory (hint: Python dictionary
works well) and then use it similarly to the previous lexicons to analyze the sentiment
associated with any text document.

355
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

SentiWordNet
We know that WordNet is perhaps one of the most popular corpora for the English
language, used extensively in semantic analysis, and it introduces the concept of synsets.
The SentiWordNet lexicon is a lexical resource used for sentiment analysis and opinion
mining. For each synset present in WordNet, the SentiWordNet lexicon assigns three
sentiment scores to it, including a positive polarity score, a negative polarity score,
and an objectivity score. You can find more details on the official web site http://
[Link], which includes research papers explaining the lexicon in
detail and also a link to download the lexicon. The nltk package in Python provides an
interface directly for accessing the SentiWordNet lexicon, and we will be using this to
analyze the sentiment of our movie reviews. The following snippet shows an example
synset and its sentiment scores using SentiWordNet:

import nltk
from [Link] import sentiwordnet as swn
# get synset for 'good'
good = swn.senti_synsets('good', 'n')[0]
# print synset sentiment scores
In [287]: print 'Positive Polarity Score:', good.pos_score()
...: print 'Negative Polarity Score:', good.neg_score()
...: print 'Objective Score:', good.obj_score()
Positive Polarity Score: 0.5
Negative Polarity Score: 0.0
Objective Score: 0.5

Now that we know how to use the sentiwordnet interface, we define a function
that can take in a body of text (movie review in our case) and analyze its sentiment by
leveraging sentiwordnet:

from normalization import normalize_accented_characters, html_parser, strip_

html

def analyze_sentiment_sentiwordnet_lexicon(review,
verbose=False):
# pre-process text
review = normalize_accented_characters(review)
review = html_parser.unescape(review)
review = strip_html(review)
# tokenize and POS tag text tokens
text_tokens = nltk.word_tokenize(review)
tagged_text = nltk.pos_tag(text_tokens)
pos_score = neg_score = token_count = obj_score = 0
# get wordnet synsets based on POS tags
# get sentiment scores if synsets are found
for word, tag in tagged_text:
ss_set = None

356
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

if 'NN' in tag and swn.senti_synsets(word, 'n'):

ss_set = swn.senti_synsets(word, 'n')[0]
elif 'VB' in tag and swn.senti_synsets(word, 'v'):
ss_set = swn.senti_synsets(word, 'v')[0]
elif 'JJ' in tag and swn.senti_synsets(word, 'a'):
ss_set = swn.senti_synsets(word, 'a')[0]
elif 'RB' in tag and swn.senti_synsets(word, 'r'):
ss_set = swn.senti_synsets(word, 'r')[0]
# if senti-synset is found
if ss_set:
# add scores for all found synsets
pos_score += ss_set.pos_score()
neg_score += ss_set.neg_score()
obj_score += ss_set.obj_score()
token_count += 1

# aggregate final scores

final_score = pos_score - neg_score
norm_final_score = round(float(final_score) / token_count, 2)
final_sentiment = 'positive' if norm_final_score >= 0 else 'negative'
if verbose:
norm_obj_score = round(float(obj_score) / token_count, 2)
norm_pos_score = round(float(pos_score) / token_count, 2)
norm_neg_score = round(float(neg_score) / token_count, 2)
# to display results in a nice table
sentiment_frame = [Link]([[final_sentiment, norm_obj_score,
norm_pos_score, norm_neg_score,
norm_final_score]],
columns=[Link](levels
=[['SENTIMENT STATS:'],
['Predicted Sentiment',
'Objectivity',
'Positive', 'Negative',
'Overall']],
labels=[[0,0,0,0,0],
[0,1,2,3,4]]))
print sentiment_frame

return final_sentiment

The comments in the preceding function are pretty self-explanatory. We take in a

body of text (a movie review), do some initial pre-processing, and then tokenize and POS
tag the tokens. For each pair of (word, tag) we check if any senti-synsets exist for the same
word and its corresponding tag. If there is a match, we take the first senti-synset and store
its sentiment scores in corresponding variables, and finally we aggregate its scores. We
can now see the preceding function in action for our sample reviews (in the sample_data
variable we created earlier from the test data) in the following snippet:

357
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

# detailed sentiment analysis for sample reviews

In [292]: for review, review_sentiment in sample_data:
...: print 'Review:'
...: print review
...: print
...: print 'Labeled Sentiment:', review_sentiment
...: print
...: final_sentiment = analyze_sentiment_sentiwordnet_
lexicon(review,
...:
verbose=True)
...: print '-'*60
...:
...:
Review:
Worst movie, (with the best reviews given it) I've ever seen. Over the top
dialog, acting, and direction. more slasher flick than [Link] all the
great reviews this movie got I'm appalled that it turned out so silly. shame
on you martin scorsese

Labeled Sentiment: negative

SENTIMENT STATS:
Predicted Sentiment Objectivity Positive Negative Overall
0 negative 0.83 0.08 0.09 -0.01
------------------------------------------------------------
Review:
I hope this group of film-makers never re-unites.

Labeled Sentiment: negative

SENTIMENT STATS:
Predicted Sentiment Objectivity Positive Negative Overall
0 negative 0.71 0.04 0.25 -0.21
------------------------------------------------------------
Review:
no comment - stupid movie, acting average or worse... screenplay - no sense
at all... SKIP IT!

Labeled Sentiment: negative

SENTIMENT STATS:
Predicted Sentiment Objectivity Positive Negative Overall
0 negative 0.81 0.04 0.15 -0.11
------------------------------------------------------------
Review:
Add this little gem to your list of holiday regulars. It is<br /><br
/>sweet, funny, and endearing

358
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Objectivity Positive Negative Overall
0 positive 0.76 0.18 0.06 0.13
------------------------------------------------------------
Review:
a mesmerizing film that certainly keeps your attention... Ben Daniels is
fascinating (and courageous) to watch.

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Objectivity Positive Negative Overall
0 positive 0.84 0.14 0.03 0.11
------------------------------------------------------------
Review:
This movie is perfect for all the romantics in the world. John Ritter has
never been better and has the best line in the movie! "Sam" hits close to
home, is lovely to look at and so much fun to play along with. Ben Gazzara
was an excellent cast and easy to fall in love with. I'm sure I've met
Arthur in my travels somewhere. All around, an excellent choice to pick up
any evening.!:-)

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Objectivity Positive Negative Overall
0 positive 0.75 0.2 0.05 0.15
------------------------------------------------------------
Review:
I don't care if some people voted this movie to be bad. If you want the
Truth this is a Very Good Movie! It has every thing a movie should have. You
really should Get this one.

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Objectivity Positive Negative Overall
0 positive 0.73 0.21 0.06 0.15
------------------------------------------------------------
Review:
Worst horror film ever but funniest film ever rolled in one you have got
to see this film it is so cheap it is unbeliaveble but you have to see it
really!!!! P.s watch the carrot

Labeled Sentiment: positive

359
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

SENTIMENT STATS:
Predicted Sentiment Objectivity Positive Negative Overall
0 positive 0.79 0.13 0.08 0.05
------------------------------------------------------------

You can see detailed statistics related to each sentiment score and also the overall
sentiment and compare it with the actual labeled sentiment for each review in the
preceding output. Interestingly, we were able to predict the sentiment correctly for all
our sampled reviews as compared to the supervised learning technique. But how well
does this technique perform for our complete test movie reviews dataset? The following
snippet will give us the answer!

# predict sentiment for test movie reviews dataset

sentiwordnet_predictions = [analyze_sentiment_sentiwordnet_lexicon(review)
for review in test_reviews]

from utils import display_evaluation_metrics, display_confusion_matrix,

display_classification_report

# get model performance statistics

In [295]: print 'Performance metrics:'
...: display_evaluation_metrics(true_labels=test_sentiments,
...: predicted_labels=sentiwordnet_
predictions,
...: positive_class='positive')
...: print '\nConfusion Matrix:'
...: display_confusion_matrix(true_labels=test_sentiments,
...: predicted_labels=sentiwordnet_
predictions,
...: classes=['positive', 'negative'])
...: print '\nClassification report:'
...: display_classification_report(true_labels=test_sentiments,
...: predicted_labels=sentiwordnet_
predictions,
...: classes=['positive', 'negative'])
Performance metrics:
Accuracy: 0.59
Precision: 0.56
Recall: 0.92
F1 Score: 0.7

Confusion Matrix:
Predicted:
positive negative
Actual: positive 6941 569
negative 5510 1980

Classification report:

360
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

precision recall f1-score support

positive 0.56 0.92 0.70 7510

negative 0.78 0.26 0.39 7490

avg / total 0.67 0.59 0.55 15000

Our model has a sentiment prediction accuracy of around 60% and an F1-score of
70% approximately. If you look at the detailed classification report and the confusion
matrix, you will observe that we correctly classify 6941/7510 positive movie reviews as
positive, but we incorrectly classify 5510/7490 negative movie reviews as positive—which
is quite high! A way to redress this would be to change our logic slightly in our function
and relax the threshold for overall sentiment score to decide whether a document will
have an overall positive or negative sentiment from 0 to maybe 0.1 or higher. Experiment
with this threshold and see what kind of results you get.

VADER Lexicon
VADER stands for Valence Aware Dictionary and sEntiment Reasoner. It is a lexicon
with a rule-based sentiment analysis framework that was specially built for analyzing
sentiment from social media resources. This lexicon was developed by C. J. Hutto and
Eric Gilbert, and you will find further details in the paper, “VADER: A Parsimonious Rule-
based Model for Sentiment Analysis of Social Media Text.” You can read more about it
and even download the dataset or install the library from [Link]
vaderSentiment, which contains all the resources pertaining to the VADER lexicon.
The file vader_sentiment_lexicon.txt contains all the necessary sentiment scores
associated with various terms, including words, emoticons, and even slang language-
based tokens (like lol, wtf, nah, and so on). There are over 9000 lexical features from
which it was further curated to 7500 lexical features in this lexicon with proper validated
valence scores. Each feature was rated on a scale from "[-4] Extremely Negative" to
"[4] Extremely Positive", with allowance for "[0] Neutral (or Neither, N/A)".
This curation was done by keeping all lexical features which had a non-zero mean rating
and whose standard deviation was less than 2.5, which was determined by the aggregate
of ten independent raters. A sample of the VADER lexicon is depicted as follows:

)-:< -2.2 0.4 [-2, -2, -2, -2, -2, -2, -3, -3, -2, -2]
)-:{ -2.1 0.9434 [-1, -3, -2, -1, -2, -2, -3, -4, -1, -2]
): -1.8 0.87178 [-1, -3, -1, -2, -1, -3, -1, -3, -1, -2]
...
...
resolved 0.7 0.78102 [1, 2, 0, 1, 1, 0, 2, 0, 0, 0]
resolvent 0.7 0.78102 [1, 0, 1, 2, 0, -1, 1, 1, 1, 1]
resolvents 0.4 0.66332 [2, 0, 0, 1, 0, 0, 1, 0, 0, 0]
...
...
}:-( -2.1 0.7 [-2, -1, -2, -2, -2, -4, -2, -2, -2, -2]
}:-) 0.3 1.61555 [1, 1, -2, 1, -1, -3, 2, 2, 1, 1]

361
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Each line in the preceding lexicon depicts a unique term, which can be a word
or even an emoticon. The first term indicates the word/emoticon, the second column
indicates the mean or average score, the third column indicates the standard deviation,
and the final column indicates a list of scores given by ten independent scorers. The nltk
package has a nice interface for leveraging the VADER lexicon, and the following function
makes use of the same for analyzing sentiment for any text document:

from [Link] import SentimentIntensityAnalyzer

def analyze_sentiment_vader_lexicon(review,
threshold=0.1,
verbose=False):
# pre-process text
review = normalize_accented_characters(review)
review = html_parser.unescape(review)
review = strip_html(review)
# analyze the sentiment for review
analyzer = SentimentIntensityAnalyzer()
scores = analyzer.polarity_scores(review)
# get aggregate scores and final sentiment
agg_score = scores['compound']
final_sentiment = 'positive' if agg_score >= threshold\
else 'negative'
if verbose:
# display detailed sentiment statistics
positive = str(round(scores['pos'], 2)*100)+'%'
final = round(agg_score, 2)
negative = str(round(scores['neg'], 2)*100)+'%'
neutral = str(round(scores['neu'], 2)*100)+'%'
sentiment_frame = [Link]([[final_sentiment, final, positive,
negative, neutral]],
columns=[Link](levels=[['SENTIMENT STATS:'],
['Predicted Sentiment',
'Polarity Score',
'Positive', 'Negative',
'Neutral']],
labels=[[0,0,0,0,0],[0,1,2,3,4]]))
print sentiment_frame

return final_sentiment

That function helps in computing the sentiment and various statistics associated with
it for any text document (movie reviews in our case). The comments explain the main
sections of the function, which include text-preprocessing, getting the necessary sentiment
scores using the VADER lexicon, aggregating them, and computing the final sentiment
(positive/negative) using a specific threshold we talked about earlier. A threshold of 0.1

362
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

seemed to work best on an average, but you can experiment further with it. The following
snippet shows us how to use this function on our sampled test movie reviews:

# get detailed sentiment statistics

In [301]: for review, review_sentiment in sample_data:
...: print 'Review:'
...: print review
...: print
...: print 'Labeled Sentiment:', review_sentiment
...: print
...: final_sentiment = analyze_sentiment_vader_lexicon(review,
...: threshold=0.1,
...: verbose=True)
...: print '-'*60

Review:
Worst movie, (with the best reviews given it) I've ever seen. Over the top
dialog, acting, and direction. more slasher flick than [Link] all the
great reviews this movie got I'm appalled that it turned out so silly. shame
on you martin scorsese

Labeled Sentiment: negative

SENTIMENT STATS:
Predicted Sentiment Polarity Score Positive Negative Neutral
0 negative 0.03 20.0% 18.0% 62.0%
------------------------------------------------------------
Review:
I hope this group of film-makers never re-unites.

Labeled Sentiment: negative

SENTIMENT STATS:
Predicted Sentiment Polarity Score Positive Negative Neutral
0 positive 0.44 33.0% 0.0% 67.0%
------------------------------------------------------------
Review:
no comment - stupid movie, acting average or worse... screenplay - no sense
at all... SKIP IT!

Labeled Sentiment: negative

SENTIMENT STATS:
Predicted Sentiment Polarity Score Positive Negative Neutral
0 negative -0.8 0.0% 40.0% 60.0%
------------------------------------------------------------
Review:
Add this little gem to your list of holiday regulars. It is<br /><br />sweet,
funny, and endearing

363
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Polarity Score Positive Negative Neutral
0 positive 0.82 40.0% 0.0% 60.0%
------------------------------------------------------------
Review:
a mesmerizing film that certainly keeps your attention... Ben Daniels is
fascinating (and courageous) to watch.

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Polarity Score Positive Negative Neutral
0 positive 0.71 31.0% 0.0% 69.0%
------------------------------------------------------------
Review:
This movie is perfect for all the romantics in the world. John Ritter has
never been better and has the best line in the movie! "Sam" hits close to
home, is lovely to look at and so much fun to play along with. Ben Gazzara
was an excellent cast and easy to fall in love with. I'm sure I've met
Arthur in my travels somewhere. All around, an excellent choice to pick up
any evening.!:-)

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Polarity Score Positive Negative Neutral
0 positive 0.99 37.0% 2.0% 61.0%
------------------------------------------------------------
Review:
I don't care if some people voted this movie to be bad. If you want the
Truth this is a Very Good Movie! It has every thing a movie should have. You
really should Get this one.

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Polarity Score Positive Negative Neutral
0 negative -0.16 17.0% 14.0% 69.0%
------------------------------------------------------------
Review:
Worst horror film ever but funniest film ever rolled in one you have got
to see this film it is so cheap it is unbeliaveble but you have to see it
really!!!! P.s watch the carrot

364
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Polarity Score Positive Negative Neutral
0 positive 0.49 11.0% 11.0% 77.0%
------------------------------------------------------------

The preceding statistics are similar to our previous function except the Positive,
Negative, and Neutral columns indicate the percentage or proportion of the document
that is positive, negative, or neutral, and the final score is determined based on the
polarity score and the threshold. The following snippet shows the model sentiment
prediction performance on the entire test movie reviews dataset:

# predict sentiment for test movie reviews dataset

vader_predictions = [analyze_sentiment_vader_lexicon(review, threshold=0.1)
for review in test_reviews]

# get model performance statistics

In [302]: print 'Performance metrics:'
...: display_evaluation_metrics(true_labels=test_sentiments,
...: predicted_labels=vader_predictions,
...: positive_class='positive')
...: print '\nConfusion Matrix:'
...: display_confusion_matrix(true_labels=test_sentiments,
...: predicted_labels=vader_predictions,
...: classes=['positive', 'negative'])
...: print '\nClassification report:'
...: display_classification_report(true_labels=test_sentiments,
...: predicted_labels=vader_predictions,
...: classes=['positive', 'negative'])
Performance metrics:
Accuracy: 0.7
Precision: 0.65
Recall: 0.86
F1 Score: 0.74

Confusion Matrix:
Predicted:
positive negative
Actual: positive 6434 1076
negative 3410 4080

Classification report:
precision recall f1-score support

positive 0.65 0.86 0.74 7510

negative 0.79 0.54 0.65 7490

avg / total 0.72 0.70 0.69 15000

365
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

The preceding metrics depict that our model has a sentiment prediction accuracy of
around 70 percent and an F1-score close to 75 percent, which is definitely better than our
previous model. Also notice that we are able to correctly predict positive sentiment for
6434 out of 7510 positive movie reviews, and negative sentiment correctly for 4080 out of
7490 negative movie reviews.

Pattern Lexicon
The pattern package is a complete package for NLP, text analytics, and information
retrieval. We discussed it in detail in previous chapters and have also used it several
times to solve several problems. This package is developed by CLiPS (Computational
Linguistics & Psycholinguistics), a research center associated with the Linguistics
Department of the Faculty of Arts of the University of Antwerp. It has a sentiment module
associated with it, along with modules for analyzing mood and modality of a body of text.
For sentiment analysis, it analyzes any body of text by decomposing it into sentences
and then tokenizing it and tagging the various tokens with necessary parts of speech.
It then uses its own subjectivity-based sentiment lexicon, which you can access from
its official repository at [Link]
text/en/[Link]. It contains scores like polarity, subjectivity, intensity, and
confidence, along with other tags like the part of speech, WordNet identifier, and so
on. It then leverages this lexicon to compute the overall polarity and subjectivity score
associated with a text document. A threshold of 0.1 is recommended by pattern itself to
compute the final sentiment of a document as positive, and anything below it as negative.
You can also analyze the mood and modality of text documents by leveraging the
mood and modality functions provided by the pattern package. The mood function
helps in determining the mood expressed by a particular text document. This function
returns INDICATIVE, IMPERATIVE, CONDITIONAL, or SUBJUNCTIVE for any text based on its
content. The table in Figure 7-2 talks about each type of mood in further detail, courtesy
of the official documentation provided by CLiPS pattern. The column Use talks about
the typical usage patterns for each type of mood, and the examples provide some actual
examples from the English language.

Figure 7-2. Different types of mood and their examples (figure courtesy of CLiPS pattern)

Modality for any text represents the degree of certainty expressed by the text as
a whole. This value is a number that ranges between 0 and 1. Values > 0.5 indicate
factual texts having a high certainty, and < 0.5 indicate wishes and hopes and have a low

366
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

certainty associated with them. We will define a function now to analyze the sentiment
for text documents using the pattern lexicon:

from [Link] import sentiment, mood, modality

def analyze_sentiment_pattern_lexicon(review, threshold=0.1,

verbose=False):
# pre-process text
review = normalize_accented_characters(review)
review = html_parser.unescape(review)
review = strip_html(review)
# analyze sentiment for the text document
analysis = sentiment(review)
sentiment_score = round(analysis[0], 2)
sentiment_subjectivity = round(analysis[1], 2)
# get final sentiment
final_sentiment = 'positive' if sentiment_score >= threshold\
else 'negative'
if verbose:
# display detailed sentiment statistics
sentiment_frame = [Link]([[final_sentiment, sentiment_score,
sentiment_subjectivity]],
columns=[Link](levels
=[['SENTIMENT STATS:'],
['Predicted Sentiment',
'Polarity Score',
'Subjectivity Score']],
labels=[[0,0,0],
[0,1,2]]))
print sentiment_frame
assessment = [Link]
assessment_frame = [Link](assessment,
columns=[Link](levels=[['DETAILED
ASSESSMENT STATS:'],
['Key Terms', 'Polarity
Score',
'Subjectivity Score',
'Type']],
labels=[[0,0,0,0],
[0,1,2,3]]))
print assessment_frame
print

return final_sentiment

367
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

We will now test the function we defined to analyze the sentiment of our sample
test movie reviews and observe the results. We take a threshold of 0.1 as the cut-off to
decide between positive and negative sentiment for a document based on the aggregated
sentiment polarity score, based on several experiments and recommendations from the
official documentation:

# get detailed sentiment statistics

In [303]: for review, review_sentiment in sample_data:
...: print 'Review:'
...: print review
...: print
...: print 'Labeled Sentiment:', review_sentiment
...: print
...: final_sentiment = analyze_sentiment_pattern_lexicon(review,
...:
threshold=0.1,
...:
verbose=True)
...: print '-'*60

Review:
Worst movie, (with the best reviews given it) I've ever seen. Over the top
dialog, acting, and direction. more slasher flick than [Link] all the
great reviews this movie got I'm appalled that it turned out so silly. shame
on you martin scorsese

Labeled Sentiment: negative

SENTIMENT STATS:
Predicted Sentiment Polarity Score Subjectivity Score
0 negative 0.06 0.62
DETAILED ASSESSMENT STATS:
Key Terms Polarity Score Subjectivity Score Type
0 [worst] -1.0 1.000 None
1 [best] 1.0 0.300 None
2 [top] 0.5 0.500 None
3 [acting] 0.0 0.000 None
4 [more] 0.5 0.500 None
5 [great] 0.8 0.750 None
6 [appalled] -0.8 1.000 None
7 [silly] -0.5 0.875 None

------------------------------------------------------------
Review:
I hope this group of film-makers never re-unites.

368
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Labeled Sentiment: negative

SENTIMENT STATS:
Predicted Sentiment Polarity Score Subjectivity Score
0 negative 0.0 0.0
Empty DataFrame
Columns: [(DETAILED ASSESSMENT STATS:, Key Terms), (DETAILED ASSESSMENT
STATS:, Polarity Score), (DETAILED ASSESSMENT STATS:, Subjectivity Score),
(DETAILED ASSESSMENT STATS:, Type)]
Index: []

------------------------------------------------------------
Review:
no comment - stupid movie, acting average or worse... screenplay - no sense
at all... SKIP IT!

Labeled Sentiment: negative

SENTIMENT STATS:
Predicted Sentiment Polarity Score Subjectivity Score
0 negative -0.36 0.5
DETAILED ASSESSMENT STATS:
Key Terms Polarity Score Subjectivity Score Type
0 [stupid] -0.80 1.0 None
1 [acting] 0.00 0.0 None
2 [average] -0.15 0.4 None
3 [worse, !] -0.50 0.6 None

------------------------------------------------------------
Review:
Add this little gem to your list of holiday regulars. It is<br /><br
/>sweet, funny, and endearing

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Polarity Score Subjectivity Score
0 positive 0.19 0.67
DETAILED ASSESSMENT STATS:
Key Terms Polarity Score Subjectivity Score Type
0 [little] -0.1875 0.5 None
1 [funny] 0.2500 1.0 None
2 [endearing] 0.5000 0.5 None

------------------------------------------------------------
Review:
a mesmerizing film that certainly keeps your attention... Ben Daniels is
fascinating (and courageous) to watch.

369
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Polarity Score Subjectivity Score
0 positive 0.4 0.71
DETAILED ASSESSMENT STATS:
Key Terms Polarity Score Subjectivity Score Type
0 [mesmerizing] 0.300000 0.700000 None
1 [certainly] 0.214286 0.571429 None
2 [fascinating] 0.700000 0.850000 None

------------------------------------------------------------
Review:
This movie is perfect for all the romantics in the world. John Ritter has
never been better and has the best line in the movie! "Sam" hits close to
home, is lovely to look at and so much fun to play along with. Ben Gazzara
was an excellent cast and easy to fall in love with. I'm sure I've met
Arthur in my travels somewhere. All around, an excellent choice to pick up
any evening.!:-)

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Polarity Score Subjectivity Score
0 positive 0.66 0.73
DETAILED ASSESSMENT STATS:
Key Terms Polarity Score Subjectivity Score Type
0 [perfect] 1.000000 1.000000 None
1 [better] 0.500000 0.500000 None
2 [best, !] 1.000000 0.300000 None
3 [lovely] 0.500000 0.750000 None
4 [much, fun] 0.300000 0.200000 None
5 [excellent] 1.000000 1.000000 None
6 [easy] 0.433333 0.833333 None
7 [love] 0.500000 0.600000 None
8 [sure] 0.500000 0.888889 None
9 [excellent, !] 1.000000 1.000000 None
10 [:-)] 0.500000 1.000000 mood

------------------------------------------------------------
Review:
I don't care if some people voted this movie to be bad. If you want the
Truth this is a Very Good Movie! It has every thing a movie should have.
You really should Get this one.

370
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Polarity Score Subjectivity Score
0 positive 0.17 0.55
DETAILED ASSESSMENT STATS:
Key Terms Polarity Score Subjectivity Score Type
0 [bad] -0.7 0.666667 None
1 [very, good, !] 1.0 0.780000 None
2 [really] 0.2 0.200000 None

------------------------------------------------------------
Review:
Worst horror film ever but funniest film ever rolled in one you have got
to see this film it is so cheap it is unbeliaveble but you have to see it
really!!!! P.s watch the carrot

Labeled Sentiment: positive

SENTIMENT STATS:
Predicted Sentiment Polarity Score Subjectivity Score
0 negative -0.04 0.63
DETAILED ASSESSMENT STATS:
Key Terms Polarity Score Subjectivity Score Type
0 [worst] -1.000000 1.0 None
1 [cheap] 0.400000 0.7 None
2 [really, !, !, !, !] 0.488281 0.2 None

------------------------------------------------------------

The preceding analysis shows the sentiment, polarity, and subjectivity scores for
each sampled review. Besides this, we also see key terms and emotions and their polarity
scores, which mainly contributed to the overall sentiment of each review. You can see
that even exclamations and emoticons are also given importance and weightage when
computing sentiment and polarity. The following snippet depicts the mood and modality
for the sampled test movie reviews:

In [304]: for review, review_sentiment in sample_data:

...: print 'Review:'
...: print review
...: print 'Labeled Sentiment:', review_sentiment
...: print 'Mood:', mood(review)
...: mod_score = modality(review)
...: print 'Modality Score:', round(mod_score, 2)
...: print 'Certainty:', 'Strong' if mod_score > 0.5 \
...: else 'Medium' if mod_score > 0.35 \
...: else 'Low'
...: print '-'*60

371
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Review:
Worst movie, (with the best reviews given it) I've ever seen. Over the top
dialog, acting, and direction. more slasher flick than [Link] all the
great reviews this movie got I'm appalled that it turned out so silly. shame
on you martin scorsese
Labeled Sentiment: negative
Mood: indicative
Modality Score: 0.75
Certainty: Strong
------------------------------------------------------------
Review:
I hope this group of film-makers never re-unites.
Labeled Sentiment: negative
Mood: subjunctive
Modality Score: -0.25
Certainty: Low
------------------------------------------------------------
Review:
no comment - stupid movie, acting average or worse... screenplay - no sense
at all... SKIP IT!
Labeled Sentiment: negative
Mood: indicative
Modality Score: 0.75
Certainty: Strong
------------------------------------------------------------
Review:
Add this little gem to your list of holiday regulars. It is<br /><br
/>sweet, funny, and endearing
Labeled Sentiment: positive
Mood: imperative
Modality Score: 1.0
Certainty: Strong
------------------------------------------------------------
Review:
a mesmerizing film that certainly keeps your attention... Ben Daniels is
fascinating (and courageous) to watch.
Labeled Sentiment: positive
Mood: indicative
Modality Score: 0.75
Certainty: Strong
------------------------------------------------------------
Review:
This movie is perfect for all the romantics in the world. John Ritter has
never been better and has the best line in the movie! "Sam" hits close to
home, is lovely to look at and so much fun to play along with. Ben Gazzara
was an excellent cast and easy to fall in love with. I'm sure I've met
Arthur in my travels somewhere. All around, an excellent choice to pick up
any evening.!:-)

372
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Labeled Sentiment: positive

Mood: indicative
Modality Score: 0.58
Certainty: Strong
------------------------------------------------------------
Review:
I don't care if some people voted this movie to be bad. If you want the
Truth this is a Very Good Movie! It has every thing a movie should have. You
really should Get this one.
Labeled Sentiment: positive
Mood: conditional
Modality Score: 0.28
Certainty: Low
------------------------------------------------------------
Review:
Worst horror film ever but funniest film ever rolled in one you have got
to see this film it is so cheap it is unbeliaveble but you have to see it
really!!!! P.s watch the carrot
Labeled Sentiment: positive
Mood: indicative
Modality Score: 0.75
Certainty: Strong
------------------------------------------------------------

The preceding output depicts the mood, modality score, and the certainty factor
expressed by each review. It is interesting to see phrases like "Add this little gem…"
are correctly associated with the right mood, which is an imperative, and "I hope
this…" is correctly associated with subjunctive mood. The other reviews have more of an
indicative disposition, which is quite obvious since it expresses the beliefs of the review
who wrote the movie review. Certainty is lower in cases of reviews that use words like
"hope", "if", and higher in case of strongly opinionated reviews.
Finally, we will evaluate the sentiment prediction performance of this model on our
entire test review dataset as we have done before for our other models. The following
snippet achieves the same:

# predict sentiment for test movie reviews dataset

pattern_predictions = [analyze_sentiment_pattern_lexicon(review,
threshold=0.1)
for review in test_reviews]

# get model performance statistics

In [307]: print 'Performance metrics:'
...: display_evaluation_metrics(true_labels=test_sentiments,
...: predicted_labels=pattern_predictions,
...: positive_class='positive')
...: print '\nConfusion Matrix:'
...: display_confusion_matrix(true_labels=test_sentiments,
...: predicted_labels=pattern_predictions,
...: classes=['positive', 'negative'])

373
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

...: print '\nClassification report:'

...: display_classification_report(true_labels=test_sentiments,
...: predicted_labels=pattern_
predictions,
...: classes=['positive', 'negative'])
Performance metrics:
Accuracy: 0.77
Precision: 0.76
Recall: 0.79
F1 Score: 0.77

Confusion Matrix:
Predicted:
positive negative
Actual: positive 5958 1552
negative 1924 5566

Classification report:
precision recall f1-score support

positive 0.76 0.79 0.77 7510

negative 0.78 0.74 0.76 7490

avg / total 0.77 0.77 0.77 15000

This model gives a better and more balanced performance toward predicting the
sentiment of both positive and negative classes. We have an average sentiment prediction
accuracy of 77 percent and an average F1-score of 77 percent for this model. Although
the number of correct positive predictions has dropped from our previous model to
5958/7510 reviews, the number of correct predictions for negative reviews has increased
significantly to 5566/7490 reviews.

Comparing Model Performances

We have built a supervised classification model and three unsupervised lexicon-based
models to predict sentiment for movie reviews. For each model, we looked at its detailed
analysis and statistics for calculating sentiment. We also evaluated each model on
standard metrics like precision, recall, accuracy, and F1-score. In this section, we will
briefly look at how each model’s performance compares against the other models.
Figure 7-3 shows the model performance metrics and a visualization comparing the
metrics across all the models.

374
 CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Figure 7-3. Comparison of sentiment analysis model performances

From the visualization and the table in Figure 7-3, it is clear that the supervised
model using SVM gives us the best results, which are expected because it was trained on
35,000 training movie reviews. Pattern lexicon performs the best among the unsupervised
techniques for our test movie reviews. Does this mean these models will always perform
the best? Absolutely not. It depends on the data you are analyzing. Remember to consider
various models and also to evaluate all the metrics when evaluating any model, and not
just one or two. Some of the models in the chart have really high recall but low precision,
which indicates these models have a tendency to make more wrong predictions or
false positives. You can re-use these benchmarks and evaluate more sentiment analysis
models as you experiment with different features, lexicons, and techniques.

375
CHAPTER 7 ■ SEMANTIC AND SENTIMENT ANALYSIS

Summary
In this final chapter, we have covered a variety of topics focused on semantic and
sentiment analysis of textual data. We revisited several of our concepts from Chapter
1 with regard to language semantics. We looked at the WordNet corpus in detail and
explored the concept of synsets with practical examples. We also analyzed various lexical
semantic relations from Chapter 1 here, using synsets and real-world examples. We
looked at relationships including entailments, homonyms and homographs, synonyms
and antonyms, hyponyms and hypernyms, and holonyms and meronyms. Semantic
relations and similarity computation techniques were also discussed in detail, with
examples that leveraged common hypernyms among various synsets. Some popular
techniques widely used in semantic and information extraction were discussed, including
word sense disambiguation and named entity recognition, with examples. Besides
semantic relations, we also revisited concepts related to semantic representations,
namely propositional logic and first order logic. We leveraged the use of theorem provers
and evaluated actual propositions and logical expressions computationally.
Next, we introduced the concept of sentiment analysis and opinion mining and saw
how it is used in various domains like social media, surveys, and feedback data. We took
a practical example of analyzing sentiment on actual movie reviews from IMDb and built
several models that included supervised machine learning and unsupervised lexicon-
based models. We looked at each technique and its results in detail and compared the
performance across all our models.
This brings us to the end of this book. I hope the various concepts and techniques
discussed here will be helpful to and that you can use the knowledge and techniques
from this book when you tackle challenging problems in the world of text analytics and
natural language processing. You may have seen by now that there is a lot of unexplored
territory out there in the world of analyzing unstructured text data. I wish you the very
best and would like to leave you with the parting thought from Occam’s razor: Sometimes
the simplest solution is the best solution.

376