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
2
ed ( u , v ) = u - v 2 = å (u - v )
i =1
i i

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 ) =
2
å(
i =1
ui - vi )

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
2
min å å 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

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

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