Module-5

Learning With Clustering

 Definition
•Clustering can be considered the most important
unsupervised learning technique; so, as every other
problem of this kind, it deals with finding a structure in a
collection of unlabeled data.

•Clustering is “the process of organizing objects into

groups whose members are similar in some way”.

•A cluster is therefore a collection of objects which are

“similar” between them and are “dissimilar” to the objects
belonging to other clusters.
 What is Cluster Analysis?
■ Cluster: a collection of data objects
Similar to one another within the same cluster
Dissimilar to the objects in other clusters
■ Cluster analysis
Grouping a set of data objects into clusters
■ Clustering is unsupervised classification: no
predefined classes
■ Typical applications
As a stand-alone tool to get insight into data
distribution
As a preprocessing step for other algorithms
■ Clustering aims at forming groups of homogeneous data points from a
heterogeneous dataset. It evaluates the similarity based on a metric
like Euclidean distance, Cosine similarity, Manhattan distance,
etc. and then group the points with highest similarity score together.
■ For Example, In the graph given below, we can clearly see that there
are 3 circular clusters forming on the basis of distance.
■ Now it is not necessary that the clusters formed must be circular in
shape. The shape of clusters can be arbitrary. There are many
algorithms that work well with detecting arbitrary shaped clusters.
■ For example, In the below given graph we can see that the clusters
formed are not circular in shape.
 Types of Clustering
Clustering broadly divides into two subgroups:

● Hard Clustering: Each input data point either fully belongs to a

cluster or not. For instance, in the example above, every customer is

assigned to one group out of the ten.

● Soft Clustering: Rather than assigning each input data point to a

distinct cluster, it assigns a probability or likelihood of the data point

being in those clusters. For example, in the given scenario, each

customer receives a probability of being in any of the ten retail store

clusters.
:
Applications of Clustering in different fields
1. Marketing: It can be used to characterize & discover customer segments for marketing
purposes.
2. Biology: It can be used for classification among different species of plants and animals.
3. Libraries: It is used in clustering different books on the basis of topics and information.
4. Insurance: It is used to acknowledge the customers, their policies and identifying the
frauds.
5. City Planning: It is used to make groups of houses and to study their values based on
their geographical locations and other factors present.
6. Earthquake studies: By learning the earthquake-affected areas we can determine the
dangerous zones.
7. Image Processing: Clustering can be used to group similar images together, classify
images based on content, and identify patterns in image data.
8. Genetics: Clustering is used to group genes that have similar expression patterns and
identify gene networks that work together in biological processes.
9. Finance: Clustering is used to identify market segments based on customer behavior,
identify patterns in stock market data, and analyze risk in investment portfolios.
10. Customer Service: Clustering is used to group customer inquiries and complaints into
categories, identify common issues, and develop targeted solutions.
1. Manufacturing: Clustering is used to group similar products together, optimize
production processes, and identify defects in manufacturing processes.
2. Medical diagnosis: Clustering is used to group patients with similar symptoms or
diseases, which helps in making accurate diagnoses and identifying effective
treatments.
3. Fraud detection: Clustering is used to identify suspicious patterns or anomalies in
financial transactions, which can help in detecting fraud or other financial crimes.
4. Traffic analysis: Clustering is used to group similar patterns of traffic data, such as
peak hours, routes, and speeds, which can help in improving transportation planning
and infrastructure.
5. Social network analysis: Clustering is used to identify communities or groups within
social networks, which can help in understanding social behavior, influence, and
trends.
6. Cybersecurity: Clustering is used to group similar patterns of network traffic or system
behavior, which can help in detecting and preventing cyberattacks.
7. Climate analysis: Clustering is used to group similar patterns of climate data, such as
temperature, precipitation, and wind, which can help in understanding climate change
and its impact on the environment.
Spectral Clustering
⚫ Algorithm which perform better than
many traditional clustering algorithm in
many cases.

⚫ It treats each data point as a graph node

and thus transform clustering problem
into graph partitioning problem.

⚫ It consists of 3 steps
1) Building Similarity Graph
a) Epsilon neighborhood graph
⚫ First a Parameter epsilon is fixed
⚫ Two vertices are connected if the distance
of the corresponding data points is less
than epsilon
b) K- nearest Neighbours

KNN algorithm stores the entire training

dataset as a reference. When making
predictions, it calculates the distance
between the input data point and all the
training examples, using a chosen distance
metric such as Euclidean distance.
c) Fully Connected graph
⚫ Here, each point is connected with an
undirected edge weighted by the distance
between two point to every point

⚫ Gaussian similarity metric is used to

calculate the distance
2) Projecting data into lower
dimensional space

⚫ There is a possibility that members of the

same cluster may be far away in the given
dimensional space.
⚫ Thus dimensional space is reduced so that
points are closer in the reduced dimensional
space and can be clustered together by
traditional clustering algorithm
3) Clustering the data

⚫ It involves clustering the reduced data by

using K- means clustering technique.
⚫ First each node is assigned a row of the
normalized of graph-laplacian matrix
⚫ Then the data is clustered using any
traditional technique
K-mean and spectral clustering
⚫ Spectral Clustering: Data points as nodes
of a connected graph and clusters are
found by partitioning this graph. It is based
on its spectral decomposition into
subgraphs.

⚫ K-mean Clustering: It divides the objects

into K-clusters such that some metric
relative to the centroids of the clusters is
minimised.
Evaluation Methods based on ground
truth homogeneity
⚫ Disadvantage of any clustering technique is that
it is difficult to evaluate its performance
⚫ To solve this problem the metric of V-measure
was developed.
⚫ The calculation of V measure requires the
calculation of 2 terms
1) Homogeneity: A perfectly homogenous
clustering is one where each cluster has data
points belonging to the same class label.
Trivial Homogeneity:
It is the case when number of cluster is equal
to the number of data points and each point
is in exactly one cluster.

It takes when homogeneity is highest while

completeness is minimum.
2) Completeness: A perfectly complete
cluster is one where all data points
belonging to the same class are clustered
into the same cluster.
Completeness describe the closeness of
the clustering algorithm to this perfection.

Trivial completeness: It is the case when

all the data points are clustered into one
cluster.
It is the extreme case when homogeneity is
minimum and completeness is maximum.
 Adjusted Rand Index
The Rand Index computes a similarity
measure between two clustering by
considering all pairs of samples and counting
pairs that are assigned in the same or
different clusters in the predicted and true
clustering.
⚫ ARI = (RI - Expected RI) / (max(RI) -
Expected RI)
⚫ Range: The ARI ranges from -1 to 1.
◦ ARI = 1: The two clusterings are identical.
◦ ARI = 0: The clustering is better than random
assignments.
◦ ARI < 0: The clustering is worse than random
assignments.
⚫ ARI is commonly used in unsupervised
learning for evaluating clustering algorithms
like K-means, Agglomerative Clustering, etc.,
by comparing the predicted clusters with
true labels.
Unsupervised Learning: Hierarchical
clustering
Agglomerative Hierarchical Clustering:

⚫ Agglomerative hierarchical clustering is a

method used in cluster analysis to build a
hierarchy of clusters. It is a bottom-up
approach, meaning it starts with individual data
points as separate clusters and then iteratively
merges clusters together until a single,
all-encompassing cluster is formed. This
hierarchical structure is typically represented as
a tree-like diagram known as a dendrogram.
⚫ Here's a step-by-step overview of the
agglomerative hierarchical clustering process:
⚫ Initialization: Start by treating each data point
as a single [Link] have as many clusters as
there are data points.
⚫ Pairwise Distance Calculation: Compute
the distance or dissimilarity between all pairs of
clusters or data points. Common distance
measures include Euclidean distance, Manhattan
distance, or other similarity/dissimilarity
metrics, depending on the data and the
problem.
⚫ Merge Closest Clusters: Identify the two clusters
that are closest to each other (i.e., have the smallest
distance). Merge these two clusters into a single
cluster.
⚫ Update the Distance Matrix: Recalculate the
distances between the newly formed cluster and all
other clusters. This can be done using various linkage
methods, such as single linkage, complete linkage,
average linkage, or Ward's method.
⚫ Repeat: Continue the process by repeatedly merging
the closest clusters and updating the distance matrix
until you have a single cluster containing all the data
points.
⚫ Dendrogram Construction: As the clusters merge,
you can construct a dendrogram, which is a visual
representation of the hierarchy of clusters. The height
at which two clusters merge in the dendrogram
represents the dissimilarity between them.
⚫ Determine the Number of Clusters: At any point
in the process, you can stop and choose the desired
number of clusters by cutting the dendrogram at a
certain height. The choice of the number of clusters
depends on the specific problem you are trying to
solve.

⚫ Agglomerative hierarchical clustering is a versatile

technique used in various fields, such as biology, social
sciences, and data analysis, to discover natural
groupings in data. It's important to choose an
appropriate linkage method and distance metric based
on the characteristics of your data and the goals of
your analysis. Different linkage methods can lead to
different cluster structures.
Graph Based Clustering

⚫ Graph-based clustering is a method for

identifying groups of similar cells or
samples. It makes no prior assumptions
about the clusters in the data.
Graph Clustering Algorithm
⚫ The HCS (Highly Connected Subgraphs) clustering
algorithm (also known as the HCS algorithm, and
other names such as highly connected clusters
/components /Kernels) is an algorithm based on graph
connectivity for cluster analysis.
⚫ It works by representing the similarity data in a
similarity graph, and then finding all the highly
connected subgraphs.
⚫ It does not make any prior assumptions on the
number of clusters.
⚫ The HCS algorithm gives a clustering solution, which
is inherently meaningful in the application domain.
Methods of graph based clustering

1) Transform data into graph representation

2) Clustering as graph Partitioning
3) Objective function for partitioning
 4) Algorithm for graph partitioning
i) We can use heuristic (greedy)approach
ii) By using spectral graph theory
 5) Spectral clustering
i) Start with similarity / adjacency matrix,
W
ii) Define diagonal matrix D
6) Graph Laplacian matrix
L=D-W
 7) Spectral clustering
i) Construct matrix W
ii) Compute L=D-W
iii) Compute K smallest eigenvector of L
a) each eigenvector V1 is an N*1 column vector
b) Create matrix V containing vectors V1,V2….Vk
iv) Cluster the row of V using K-means or other clustering
algorithm into K-clusters.
Clustering with minimum spanning tree

Clustering using a Minimum Spanning

Tree (MST) is a graph-based method that
can be effective in clustering spatial or
network data.
⚫ Steps for Clustering with MST:
⚫ Construct a Graph:
◦ Represent the data points as nodes of a graph.
◦ The edges between nodes represent the
similarity or distance between those points (e.g.,
Euclidean distance, Manhattan distance).
[Link] a Minimum Spanning Tree
(MST):

⚫ The MST is a subgraph that connects all

the nodes with the minimum total edge
weight (the sum of the distances or
similarities) without forming any cycles.
⚫ Popular algorithms for constructing an MST
include Kruskal’s and Prim’s algorithms.
[Link] by Cutting the MST:
⚫ To create clusters, the edges of the MST are
cut. The idea is to remove the most significant
(longest) edges, which likely connect nodes
from different clusters.

⚫ The number of clusters can be controlled by

removing a certain number of edges or by
setting a threshold on the edge weights (e.g.,
remove edges with weights above a certain
value)
MODEL CLUSTERING-
Expectation Maximisation Algorithm
Model Based clustering
Density based clustering(DBSCAN)
⚫ Density-based clustering is a technique for partitioning data
into clusters based on the density of data points in the feature
space. Unlike some other clustering algorithms, density-based
clustering methods can discover clusters of arbitrary shapes
and sizes and are particularly effective in the presence of noise.
One of the most popular density-based clustering algorithms is
DBSCAN (Density-Based Spatial Clustering of Applications
with Noise). Here's an overview of density-based clustering
and DBSCAN:
⚫ DBSCAN Algorithm:
◦ Density Estimation: DBSCAN identifies clusters by estimating the
density of data points in the feature space. It defines two important
parameters:
● Epsilon (ε): A distance threshold that specifies the maximum
distance between two data points for them to be considered
neighbors.
● MinPoints (MinPts): The minimum number of data points required
within the ε-neighborhood of a point for that point to be
considered a core point.
Core Points:

⚫ A data point is classified as a "core point" if there

are at least MinPts data points (including itself)
within its ε-neighborhood. Core points are
typically located in the interior of dense clusters.
⚫ Border Points:

⚫ A data point is classified as a "border point" if it is

within the ε-neighborhood of a core point but
does not have enough neighbors to be
considered a core point itself. Border points are
part of a cluster but are not as densely
connected as core points.
⚫ Noise Points (Outliers):
◦ Data points that are neither core points nor
border points are considered "noise points" or
"outliers." They do not belong to any cluster.
⚫ Cluster Formation:
◦ The DBSCAN algorithm identifies clusters by
connecting core points and their reachable
neighbors. Any data point that is reachable from a
core point (i.e., can be reached by following a chain
of core points) is considered part of the same
cluster.
⚫ Result:
◦ After processing all data points, DBSCAN outputs a
set of clusters and a set of noise points (outliers).
Advantages of Density-Based
Clustering (DBSCAN):
⚫ Robust to noise: DBSCAN can effectively handle
noisy data points as outliers and not assign them
to any cluster.
⚫ Ability to find clusters of arbitrary shapes and
sizes.
⚫ Parameter-free clustering: DBSCAN does not
require specifying the number of clusters in
advance, which is an advantage over methods like
K-means.
⚫ Minimization of subjectivity: The choice of ε and
MinPts values may affect clustering results, but
they can often be set based on domain
knowledge or using heuristic methods.
Challenges and Considerations:

⚫ Choosing appropriate values for ε and

MinPts can be non-trivial and may require
domain knowledge or experimentation.
⚫ DBSCAN may struggle to identify clusters
with varying densities.
⚫ The algorithm can be sensitive to the
order in which data points are processed.