Clustering and its Applications

UNIT-4

INTRODUCTION

• Clustering is an unsupervised Machine Learning-based Algorithm that comprises a group of data points into clusters so that the objects belong to the same group.
• A cluster is a subset of similar objects
• A subset of objects such that the distance between any of the two objects in the cluster is less than the distance between any object in the cluster and any object that is not located inside it.

Ex: It assists marketers to find different groups in their client base and based on the purchasing patterns. They can characterize their customer groups.

​

​

I

Clustering Methods

It can be classified based on the following categories.

1. Hierarchical Method
2. Partitioning Method
3. Grid-Based Method
4. Density-Based Method

Hierarchical Methods

• Hierarchical clustering refers to an unsupervised learning procedure that determines successive clusters based on previously defined clusters.
• It works via grouping data into a tree of clusters.
• Hierarchical clustering stats by treating each data points as an individual cluster.

There are two types of hierarchical clustering

• Agglomerative Hierarchical Clustering
• Divisive Clustering

Agglomerative Hierarchical Clustering

• It uses Bottom up strategy
• Each data point act as an individual cluster and at each step, data objects are grouped in a bottom-up method.
• Initially, each data object is in its cluster. At each iteration, the clusters are combined with different clusters until one cluster is formed.

Agglomerative hierarchical clustering

Agglomerative hierarchical clustering Alogorithm

​

1. Determine the similarity between individuals and all other clusters. (Find proximity matrix).
2. Consider each data point as an individual cluster.
3. Combine similar clusters.
4. Recalculate the proximity matrix for each cluster.
5. Repeat step 3 and step 4 until you get a single cluster.

Agglomerative hierarchical clustering with Example

​

Distance matrix

​

Step-2: Select minimum distance point i.e., 0.11 for (p3,p6)

​

Divisive Hierarchical Clustering (DIANA)

• Divisive hierarchical clustering is exactly the opposite of Agglomerative Hierarchical clustering. –top down approach.
• In Divisive Hierarchical clustering, all the data points are considered an individual cluster, and in every iteration, the data points that are not similar are separated from the cluster.
• The separated data points are treated as an individual cluster. Finally, we are left with N clusters.
• Partitioning the cluster continues untill each cluster reaches the lowest level.

Types of Linkages in Clustering

• The process of Hierarchical Clustering involves either clustering sub-clusters(data points in the first iteration) into larger clusters in a bottom-up manner or dividing a larger cluster into smaller sub-clusters in a top-down manner.
• During both the types of hierarchical clustering, the distance between two sub-clusters needs to be computed.

The different types of linkages are:-

1. Single Linkage

2. Complete Linkage

3. Average Linkage

1. Single Linkage:

For two clusters R and S, the single linkage returns the minimum distance between two points i and j such that i belongs to R and j belongs to S

2. Complete Linkage:

For two clusters R and S, the complete linkage returns the maximum distance between two points i and j such that i belongs to R and j belongs to S.

3. Average Linkage:

For two clusters R and S, first for the distance between any data-point i in R and any data-point j in S and then the arithmetic mean of these distances are calculated. Average Linkage returns this value of the arithmetic mean

where

– Number of data-points in R

– Number of data-points in S