Clustering Algorithms

AGENDA PART 1
• Types of different Clustering Algorithms
• Partitioning or Similarity based Approach – Kmeans Algorithm
• What Is K Means Clustering
• Implementation of K means Clustering
• WCSS And Elbow Method To find No. Of clusters
• Python Implementation of K means Clustering
 Types of Clustering Algorithms
• Partitioning or Similarity based Approach
• Hierarchical Clustering – Divisive and Agglomerative Approach
• Density Based
• Graph Based
• Probabilistic Based Topic Modelling using LDA (Latent Dirichlet
Algorithm)
 Overview – K Means Clustering
• K means is one of the most popular Unsupervised Machine Learning
Algorithms Used for Solving Classification Problems.
•  K Means segregates the unlabeled data into various groups, called
clusters, based on having similar features, common patterns.
 What Is K Means Algorithm?

• K Means Algorithm is an Iterative algorithm that divides a dataset

into k subgroups /clusters based on the similarity and their mean
distance from the centroid of that particular subgroup/ formed.
• K, here is the pre-defined number of clusters to be formed by the
Algorithm. If K=3, It means the number of clusters to be formed from
the dataset is 3
 Algorithm steps Of K Means
• Centroid - A centroid is a data point at the centre of a cluster. In
centroid-based clustering, clusters are represented by a centroid. It is
an iterative algorithm in which the notion of similarity is derived by
how close a data point is to the centroid of the cluster.
• K-Means clustering works as follows:- The K-Means clustering
algorithm uses an iterative procedure to deliver a final result.
• The algorithm requires number of clusters K and the data set as input.
The data set is a collection of features for each data point. The
algorithm starts with initial estimates for the K centroids.
 Algorithm Steps
• The algorithm then iterates between two steps:-

 Data assignment step

• Each centroid defines one of the clusters. In this step, each data point
is assigned to its nearest centroid, which is based on the squared
Euclidean distance. So, if ci is the collection of centroids in set C, then
each data point is assigned to a cluster based on minimum Euclidean
distance.
 Algorithm Steps
• The algorithm then iterates between two steps:-

Centroid update step

• In this step, the centroids are recomputed and updated. This is done
by taking the mean of all data points assigned to that centroid’s
cluster.
• The algorithm then iterates between step 1 and step 2 until a
stopping criteria is met. Stopping criteria means no data points
change the clusters, the sum of the distances is minimized or some
maximum number of iterations is reached. This algorithm is
guaranteed to converge to a result.
 Choosing The Right Number Of Clusters

• The number of clusters that we choose for the algorithm shouldn’t be

random. Each and Every cluster is formed by calculating and
comparing the mean distances of each data points within a cluster
from its centroid.
• We Can Choose the right number of clusters with the help of the
Within-Cluster-Sum-of-Squares (WCSS) method.
• WCSS Stands for the sum of the squares of distances of the data points
in each and every cluster from its centroid.
• The main idea is to minimize the distance between the data points and
the centroid of the clusters. The process is iterated until we reach a
minimum value for the sum of distances.
To find the optimal value of clusters, the elbow method follows the below
steps:

• 1 Execute the K-means clustering on a given dataset for different K values

(ranging from 1-10).
• 2 For each value of K, calculates the WCSS value.
• 3 Plots a graph/curve between WCSS values and the respective number of
clusters K.
• 4 The sharp point of bend or a point( looking like an elbow joint ) of the plot
like an arm, will be considered as the best/optimal value of K
 Agenda – PART 2
• Why Hierarchical Clustering
• What is Hierarchical Clustering?
• Types of Hierarchical Clustering
• Agglomerative Hierarchical Clustering
• Divisive Hierarchical Clustering
• Steps to perform Hierarchical Clustering
• How to Choose the Number of Clusters in Hierarchical Clustering?
• Solving a Wholesale Customer Segmentation Problem using
Hierarchical Clustering
 Challenges of KMeans
• It always tries to make clusters of the same size. Also, we have to
decide the number of clusters at the beginning of the algorithm.
• Ideally, we would not know how many clusters should we have, in the
beginning of the algorithm and hence it a challenge with K-means.
 What is Hierarchical Clustering?
• Let’s say we have the below points and we want to cluster them into
groups:
• We can assign each of these points to a separate cluster:
 What is Hierarchical Clustering?
• Now, based on the similarity of
these clusters, we can combine the
most similar clusters together and
repeat this process until only a
single cluster is left.
• We are essentially building a
hierarchy of clusters. That’s why
this algorithm is called hierarchical
clustering.
 Types of Hierarchical Clustering

• There are mainly two types of hierarchical clustering:

• Agglomerative hierarchical clustering

• Divisive Hierarchical clustering
 Agglomerative Hierarchical Clustering
• We assign each point to an individual cluster in this technique. Suppose
there are 4 data points. We will assign each of these points to a cluster
and hence will have 4 clusters in the beginning
• Then, at each iteration, we merge the closest pair of clusters and repeat
this step until only a single cluster is left
• We are merging (or adding) the clusters at each step, right? Hence, this
type of clustering is also known as additive hierarchical clustering.
 Divisive Hierarchical Clustering
• Divisive hierarchical clustering works in the opposite way. Instead of
starting with n clusters (in case of n observations), we start with a
single cluster and assign all the points to that cluster.
• So, it doesn’t matter if we have 10 or 1000 data points. All these
points will belong to the same cluster at the beginning
• Now, at each iteration, we split the farthest point in the cluster and
repeat this process until each cluster only contains a single point
• We are splitting (or dividing) the clusters at each step, hence the
name divisive hierarchical clustering.
 Steps to Perform Hierarchical Clustering

• We merge the most similar points or clusters in hierarchical clustering

– we know this.
• Now the question is – how do we decide which points are similar and
which are not? It’s one of the most important questions in clustering!
 Steps to Perform Hierarchical Clustering

• Here’s one way to calculate similarity –

• Take the distance between the centroids of these clusters. The points
having the least distance are referred to as similar points and we can
merge them.
• We can refer to this as a distance-based algorithm as well (since we
are calculating the distances between the clusters).
• In hierarchical clustering, we have a concept called a proximity
matrix. This stores the distances between each point.
 Setting up an example

• Suppose a teacher wants to divide her students into different groups.

She has the marks scored by each student in an assignment and
based on these marks, she wants to segment them into groups.
• There’s no fixed target here as to how many groups to have.
• Since the teacher does not know what type of students should be
assigned to which group, it cannot be solved as a supervised learning
problem. So, we will try to apply hierarchical clustering here and
segment the students into different groups.
 Setting up an example

• Let’s take a sample of 5 students:

 Creating a Proximity Matrix
• First, we will create a proximity
matrix which will tell us the
distance between each of these
points. Since we are calculating
the distance of each point from
each of the other points, we will
get a square matrix of shape n X
n (where n is the number of
observations).
• Let’s make the 5 x 5 proximity
matrix for our example:
 Creating a Proximity Matrix

• The diagonal elements of this matrix will always be 0 as the distance

of a point with itself is always 0. We will use the Euclidean distance
formula to calculate the rest of the distances. So, let’s say we want to
calculate the distance between point 1 and 2:
• √(10-7)^2 = √9 = 3

• Similarly, we can calculate all the distances and fill the proximity
matrix.
 Steps to Perform Hierarchical Clustering

• Step 1: First, we assign all the points to an individual cluster:

• Different colors here represent different clusters. You can see that we
have 5 different clusters for the 5 points in our data.
 Steps to Perform Hierarchical Clustering
• Step 2: Next, we will look at the smallest distance in the proximity
matrix and merge the points with the smallest distance. We then
update the proximity matrix
• Here, the smallest distance is 3 and hence we will merge point 1 and 2:
 Steps to Perform Hierarchical Clustering
• Let’s look at the updated clusters and accordingly update the proximity matrix
• Here, we have taken the maximum of the two marks (7, 10) to replace the
marks for this cluster. Instead of the maximum, we can also take the minimum
value or the average values as well. Now, we will again calculate the proximity
matrix for these clusters:
 Steps to Perform Hierarchical Clustering
• Step 3: We will repeat step 2 until only a single cluster is left.
• So, we will first look at the minimum distance in the proximity matrix
and then merge the closest pair of clusters. We will get the merged
clusters as shown below after repeating these steps:
 Finally

• We started with 5 clusters and finally have a single cluster. This is how

agglomerative hierarchical clustering works. But the burning
question still remains – how do we decide the number of clusters? 
How should we Choose the Number of Clusters in Hierarchical Clustering?

• Ready to finally answer this question that’s been hanging around

since we started learning? To get the number of clusters for
hierarchical clustering, we make use of an awesome concept called
a Dendrogram.
• A dendrogram is a tree-like diagram that records the sequences of
merges or splits.
 Dendogram
• Let’s get back to our
teacher-student example.
Whenever we merge two
clusters, a dendrogram will
record the distance
between these clusters
and represent it in graph
form. Let’s see how a
dendrogram looks like:
 Dendogram

• We have the samples of the dataset on the x-axis and the distance on
the y-axis. Whenever two clusters are merged, we will join them in
this dendrogram and the height of the join will be the distance
between these points. Let’s build the dendrogram for our example:
Dendogram
 Dendogram
• Take a moment to process the above
image. We started by merging sample
1 and 2 and the distance between
these two samples was 3 (refer to the
first proximity matrix in the previous
section). Let’s plot this in the
dendrogram
• Here, we can see that we have merged
sample 1 and 2. The vertical line
represents the distance between these
samples.
 Dendogram
• We can clearly visualize the steps of
hierarchical clustering. More the
distance of the vertical lines in the
dendrogram, more the distance
between those clusters.
• Now, we can set a threshold distance
and draw a horizontal line
(Generally, we try to set the
threshold in such a way that it cuts
the tallest vertical line). Let’s set this
threshold as 12 and draw a
horizontal line:
 Dendogram

• The number of clusters will be the number of vertical lines which are
being intersected by the line drawn using the threshold. In the above
example, since the red line intersects 2 vertical lines, we will have 2
clusters. One cluster will have a sample (1,2,4) and the other will have
a sample (3,5).

• This is how we can decide the number of clusters using a dendrogram

in Hierarchical Clustering. 
 REFERENCES
• https://www.kaggle.com/thebrownviking20/k-means-clustering-of-
1-million-headlines/data
• https://www.kaggle.com/thebrownviking20/k-means-clustering-of-
1-million-headlines/notebook
• https://dataaspirant.com/five-most-popular-similarity-measures-
implementation-in-python/