UNIT 4 UNSUPERVISED LEARNING

Introduction- Overview of Basic Clustering Methods - K- Means - k-Medoids -DBSCAN -

Dimensionality Reduction - Principal Component Analysis – Outlier Analysis - Outlier Detection
-Introduction to Reinforcement Learning and its Applications

Introduction:
Clustering or cluster analysis is a machine learning technique, which groups the unlabelled dataset.
It can be defined as "A way of grouping the data points into different clusters, consisting of similar
data points. The objects with the possible similarities remain in a group that has less or no
similarities with another group.“ Finding some similar patterns in the unlabelled dataset such as
shape, size, color, behavior, etc., and divides them as per the presence and absence of those similar
patterns.

Clustering:
• It is an unsupervised learning method, hence no supervision is provided to the algorithm,
and it deals with the unlabeled dataset.
• After applying this clustering technique, each cluster or group is provided with a cluster-
ID. ML system can use this id to simplify the processing of large and complex datasets.
• The clustering technique is commonly used for statistical data analysis.
• Note: Clustering is somewhere similar to the classification algorithm, but the difference is
the type of dataset that we are using. In classification, we work with the labeled data set,
whereas in clustering, we work with the unlabelled dataset.
• The below diagram explains the working of the clustering algorithm. We can see the
different fruits are divided into several groups with similar properties.

Unsupervised learning: no predefined classes

• A good clustering method will produce high quality clusters
– high intra-class similarity: cohesive within clusters

1
 – low inter-class similarity: distinctive between clusters
• The quality of a clustering method depends on
– the similarity measure used by the method
– its implementation, and
– its ability to discover some or all of the hidden patterns.
– Clustering is a form of learning by observation rather than learning by examples.

Overview of Basic Clustering Methods:

Main objectives of clustering are:
• Intra-cluster distance is minimized.
• Inter-cluster distance is maximized.

Data Matrix and Dissimilarity Matrix:

2
Distances are normally used to measure the similarity or dissimilarity between to data objects.
Some popular distances are based on Minkowski distance(Lp or Lh norm)

Special cases of Minkowski Distance:

3
Types of Clustering Methods:
• The clustering methods are broadly divided into Hard clustering (data point belongs to only
one group) and Soft Clustering (data points can belong to another group also).
• But there are also other various approaches of Clustering exist. Below are the main
clustering methods used in Machine learning:
– Partitioning Clustering
– Density-Based Clustering
– Distribution Model-Based Clustering
– Hierarchical Clustering
– Fuzzy Clustering

Partitioning Clustering:
• It is a type of clustering that divides the data into non-hierarchical groups. It is also known
as the centroid-based method. The most common example of partitioning clustering is the
K-Means Clustering algorithm.
• In this type, the dataset is divided into a set of k groups, where K is used to define the
number of pre-defined groups. The cluster center is created in such a way that the distance
between the data points of one cluster is minimum as compared to another cluster centroid.

Density-Based Clustering:
• The density-based clustering method connects the highly-dense areas into clusters, and the
arbitrarily shaped distributions are formed as long as the dense region can be connected.
• This algorithm does it by identifying different clusters in the dataset and connects the areas
of high densities into clusters. The dense areas in data space are divided from each other
by sparser areas.

4
• These algorithms can face difficulty in clustering the data points if the dataset has varying
densities and high dimensions.

Hierarchical Clustering:
• Hierarchical clustering can be used as an alternative for the partitioned clustering as there
is no requirement of pre-specifying the number of clusters to be created.
• In this technique, the dataset is divided into clusters to create a tree-like structure, which
is also called a dendrogram.

Dendrogram
• Hierarchical clustering algorithm is of two types:
i) Agglomerative Hierarchical clustering algorithm or AGNES (agglomerative
nesting)
• This approach is also known as bottom-up approach.
• Start with each object forming a separate group.
• It keeps on merging the objects or groups that are close to one another.

5
 • It keep on doing so until all of the groups are merged into one or until the
termination condition holds.
ii) Divisive Hierarchical clustering algorithm or DIANA (divisive analysis).
• Divisive approach is a top-down approach.
• Start with one,all-inclusive cluster.
• Smaller clusters are created by splitting the group by using the continuous
iteration.
• Split until each cluster contains a point.
• Cannot undo after the group is split or merged, and that is why this method is
not so flexible.

Distribution Model-Based Clustering:

• In the distribution model-based clustering method, the data is divided based on the
probability of how a dataset belongs to a particular distribution. The grouping is done by
assuming some distributions commonly Gaussian Distribution.
• The example of this type is the Expectation-Maximization Clustering algorithm that uses
Gaussian Mixture Models (GMM).

6
Fuzzy Clustering:
• Fuzzy clustering is a type of soft method in which a data object may belong to more than
one group or cluster.
• Each dataset has a set of membership coefficients, which depend on the degree of
membership to be in a cluster.
• Fuzzy C-means algorithm is the example of this type of clustering; it is sometimes also
known as the Fuzzy k-means algorithm.

Applications of Clustering:
• In Identification of Cancer Cells: The clustering algorithms are widely used for the
identification of cancerous cells. It divides the cancerous and non-cancerous data sets into
different groups.
• In Search Engines: Search engines also work on the clustering technique. The search result
appears based on the closest object to the search query. It does it by grouping similar data
objects in one group that is far from the other dissimilar objects. The accurate result of a
query depends on the quality of the clustering algorithm used.
• Customer Segmentation: It is used in market research to segment the customers based on
their choice and preferences.
• In Biology: It is used in the biology stream to classify different species of plants and
animals using the image recognition technique.
• In Land Use: The clustering technique is used in identifying the area of similar lands use
in the GIS database. This can be very useful to find that for what purpose the particular
land should be used, that means for which purpose it is more suitable.
• The clustering technique can be widely used in various tasks. Some most common uses of
this technique are:
• Market Segmentation
• Statistical data analysis
• Social network analysis
• Image segmentation
• Anomaly detection, etc.
• Apart from these general usages, it is used by the Amazon in its recommendation system
to provide the recommendations as per the past search of products.

7
 • Netflix also uses this technique to recommend the movies and web-series to its users as per
the watch history.

K-means Clustering Method:

• K-Means clustering is an unsupervised iterative clustering technique.
• It partitions the given data set into k predefined distinct clusters.
• It partitions the data set such that-
– Each data point belongs to a cluster with the nearest mean.
– Data points belonging to one cluster have high degree of similarity.
– Data points belonging to different clusters have high degree of dissimilarity.

• If k is given, the K-means algorithm can be executed in the following steps:

– Partition of objects into k non-empty subsets
– Identifying the cluster centroids (mean point) of the current partition.
– Assigning each point to a specific cluster
– Compute the distances from each point and allot points to the cluster where the
distance from the centroid is minimum.
– After re-allotting the points, find the centroid of the new cluster formed.

8
• The most commonly used partitioning-clustering strategy is based on the square error
criterion.
• The general objective is to obtain the partition that, for a fixed number of clusters,
minimizes the total square error.
• Suppose that the given dataset of N samples in an n-dimensional space has been partitioned
into k-clusters {c1 , c2 ,... ck }.
• Each ck has nk samples and each sample has exactly one cluster, so that

n k  N where k  1,2...,k
• The mean vector MK of cluster Ck is defined as the centroid of the cluster

1  nk
M K    X ik
 nk  i 1
where Xik is the ith sample belonging to cluster Ck
• The square error for cluster Ck is the sum of the squared Euclidean distance between each
sample in Ck and its centroid. This error is also called the within-cluster variation.
nk
e   ( X ik  M k ) 2
2
K
i 1

9
 • The square-error for the entire clustering space containing k clusters is the sum of the
within-cluster variations:
k
E   ek2
2
K
K 1

Problem 1:
Consider the data points X1={1,0} X2={0,1} X3={2,1} X4={3,3}
Clusters: C1={X1 ,X3} C2={X2 ,X4}
a. Apply one iteration of K-means partitioning clustering algorithm.
b. What is the change in total square error?
c. Apply second iteration of K-means partitioning clustering algorithm.
Solution:
Step 1: The centroid for the clusters C1 and C2 are:
Formula:

 1  nk
M K    X ik
 nk  i 1

1  2 0  1
M1   ,   1.5,0.5
 2 2 
0  3 1 3
M2   ,   1.5,2
 2 2 
Step 2: Within cluster variation after initial random distribution of samples:
nk
e   ( X ik  M k ) 2
2
K
i 1

e12  [(1  1.5) 2  (0  0.5) 2  (2  1.5) 2  (1  0.5) 2 ]

 [0.25  0.25  0.25  0.25]
1

e22  [(0  1.5) 2  (1  2) 2  (3  1.5) 2  (3  2) 2 ]

 [2.25  1  2.25  1]
 6.5

10
Step 3: Total square error
k
E   ek2
2
K
K 1

E 2  e12  e22  1  6.5  7.5

• Reassign all samples depending on minimum distance from centroid M1 and M2 ,the new
redistribution of samples inside clusters will be:

M 1  1.5,0.5
M 2  1.5,2
Distance between the data points and centroids:
1. X1={1,0}
d ( X 1 , M 1 )  (1  1.5) 2  (0  0.5) 2  0.707
d ( X 1 , M 2 )  (1  1.5) 2  (0  2) 2  2.062
2. X2={0,1}
d ( X 2 , M1 )  (0  1.5) 2  (1  0.5) 2  1.581
d ( X 2 , M 2 )  (0  1.5) 2  (1  2) 2  1.803
3. X3={2,1}
d ( X 3 , M 1 )  (2  1.5) 2  (1  0.5) 2  0.707
d ( X 3 , M 2 )  (2  1.5) 2  (1  2) 2  1.118
4. X4={3,3}
d ( X 4 , M 1 )  (3  1.5) 2  (3  0.5) 2  2.915
d ( X 4 , M 2 )  (3  1.5) 2  (3  2) 2  1.803

Based on minimum distance from each centroid , the new Clusters are: C1={X1 , X2 ,X3}
C2={X4}.
Calculate the new centroid:

1  0  2 0  1  1
M1   ,   1,0.66
 3 3 
M 2  3,3
Within cluster variation after re-assigning data points:

11
 e12  [(1  1) 2  (0  0.66) 2  (0  1) 2  (1  0.66) 2  (2  1) 2  (1  0.66) 2 ]
 [0  0.4356  1  0.1156  1  0.1156]
 2.668

e22  [(3  3) 2  (3  3) 2 ]
0
Total square error

E 2  e12  e22  2.668  0  2.668

• After first iteration, the total square error is significantly reduced from the value 7.5 to
2.668.

Distance between the data points and new centroids:

M 1  1,0.66
M 2  3,3

1. X1={1,0}
d ( X 1 , M 1 )  (1  1) 2  (0  0.66) 2  0.66
d ( X 1 , M 2 )  (1  3) 2  (0  3) 2  4  9  3.46
2. X2={0,1}
d ( X 2 , M 1 )  (0  1) 2  (1  0.66) 2  1  0.1156  1.056
d ( X 2 , M 2 )  (0  3) 2  (1  3) 2  9  4  3.46
3. X3={2,1}
d ( X 3 , M 1 )  (2  1) 2  (1  0.66) 2  1  0.1156  1.056
d ( X 3 , M 2 )  (2  3) 2  (1  3) 2  1  4  2.24
4. X4={3,3}
d ( X 4 , M 1 )  (3  1) 2  (3  0.66) 2  22  (2.34) 2  3.078
d ( X 4 , M 2 )  (3  3) 2  (3  3) 2  0

Based on minimum distance from each centroid , the new Clusters are : C1={X1 , X2 ,X3}
C2={X4}
There is no reassignment and therefore the algorithm halts.

12
Advantages:
– With large number of variables, k-means may be computationally faster that
hierarchical clustering(if k is small).
– K-means may produce tighter clusters that hierarchical clustering especially is the
cluster are globular.
Disadvantages:
– Difficult in comparing the quality of the clusters produced.
– Applicable only when mean is defined.
– Need to specify k, the number of clusters in advance.
– Unable to handle noisy data and outliers.

K-Medoids Clustering:
K-Medoids Algorithm: Step-by-Step Procedure

The K-Medoids algorithm is a clustering method similar to K-Means, but it selects actual data
points (medoids) instead of calculating the mean. It is more robust to noise and outliers.

Step 1: Initialize Medoids

1. Choose K (number of clusters).

2. Randomly select K data points as the initial medoids.

Step 2: Assign Each Point to the Nearest Medoid

For each data point, compute the distance to all medoids and assign it to the closest one.

 Common distance metrics: Manhattan distance (L1 norm) or Euclidean distance (L2
norm).
 The objective is to minimize the total sum of distances within each cluster.

Step 3: Compute Total Cost

Calculate the total cost as the sum of distances between points and their assigned medoid:

where d(Xi,medoid) is the distance between point Xi and its cluster medoid.

13
Step 4: Swap Medoids and Find the Best Set

For each non-medoid point X, perform the following:

1. Swap X with an existing medoid.

2. Reassign points to the new medoids.
3. Compute the new cost.
4. If the new cost is lower, update the medoids; otherwise, keep the previous medoids.

Step 5: Repeat Until Convergence

 Repeat Steps 2–4 until no medoid changes or cost does not decrease significantly.
 The final clusters are the groups of points around the selected medoids.

Key Differences Between K-Means and K-Medoids

Centroid vs. Medoid

 K-Means: Uses the mean of the points in a cluster as the centroid, which may not be an
actual data point.
 K-Medoids: Uses actual data points as medoids, making it more interpretable.
Distance Measures
 K-Means: Typically uses Euclidean distance, which may not be suitable for all data
types.
 K-Medoids: Can use any distance measure, providing more flexibility.
Sensitivity to Outliers
 K-Means: Sensitive to outliers, as they can significantly affect the mean.
 K-Medoids: More robust to outliers, as medoids are actual data points less influenced by
extreme values.
Computational Complexity
 K-Means: Generally faster and more efficient, making it suitable for very large datasets.
 K-Medoids: Slower due to the need to evaluate all possible swaps, better for smaller
datasets or when robustness is crucial.
Convergence
 K-Means: Converges faster but may end up in local minima.
 K-Medoids: More likely to find a global optimum but at a higher computational cost.

Aspect K -Means Clustering K-Medoids Clustering

Representation of K-Means Clustering uses the mean of It uses the most centrally located point
Clusters points (centroid) to represent a cluster. (medoid) to represent a cluster.
Sensitivity to Highly sensitive to outliers. More robust to outliers.
Outliers
Distance Metrics K-Means primarily uses Euclidean Whereas it can use any distance metric.
distance.
Computational K-Means is generally faster and more It is slower due to the need to calculate all
Efficiency efficient pairwise distances within clusters.
Cluster Shape It assumes spherical clusters. It does not make strong assumptions about
Assumption cluster shapes.

14
Problem 1: Consider the following data points:
I X Y
X1 2 6
X2 3 4
X3 3 8
X4 4 7
X5 6 2
X6 6 4
X7 7 3
X8 7 4
X9 8 5
X10 7 6
Step 1:
Select two medoids : M1=(3, 4) and M2=(7, 4) .Calculate the distance using:
Manhattan Dist = |X1-X2| +| У1 - У2 |
Distance from M1 Distance from M2
• Mdist (2,6), (3, 4)] =|2-3|+|6-4| = 3 • Mdist[(2,6), (7, 4)] =|2-7|+|6-4| = 7
• Mdist[(3,4), (3,4)] = |3-3|+|4-4| =0 • Mdist[(3,4), (7,4)] = |3-7|+|4-4| =4
• Mdist[(3,8), (3,4)] = |3-3|+|8-4| =4 • Mdist[(3,8), (7,4)] = |3-7|+|8-4| =8
• Mdist[(4,7), (3,4)] = |4-3|+|7-4| =4 • Mdist[(4,7), (7,4)] = |4-7|+|7-4| =6
• Mdist[(6,2), (3,4)] = |6-3|+|2-4| =5 • Mdist[(6,2), (7,4)] = |6-7|+|2-4| =3
• Mdist[(6,4), (3,4)] = |6-3|+|4-4| =3 • Mdist[(6,4), (7,4)] = |6-7|+|4-4| =1
• Mdist[(7,3), (3,4)] = |7-3|+|3-4| =5 • Mdist[(7,3), (7,4)] = |7-7|+|3-4| =1
• Mdist[(7,4), (3,4)] = |7-3|+|4-4| =4 • Mdist[(7,4), (7,4)] = |7-7|+|4-4| =0
• Mdist[(8,5), (3,4)] = |8-3|+|5-4| =6 • Mdist[(8,5), (7,4)] = |8-7|+|5-4| =2
• Mdist[(7,6), (3,4)] = |7-3|+|6-4| =6 • Mdist[(7,6), (7,4)] = |7-7|+|6-4| =2

Based on minimum distance assign the data points to the respective clusters (C1 or C2)

I X Y M1 M2 Cluster
X1 2 6 3 7 C1
X2 3 4 0 4 C1
X3 3 8 4 8 C1
X4 4 7 4 6 C1
X5 6 2 5 3 C2
X6 6 4 3 1 C2
X7 7 3 5 1 C2
X8 7 4 4 0 C2
X9 8 5 6 2 C2
X10 7 6 6 2 C2

15
Step 2: The Clusters are C1 and C2 with medoids M1 and M2 respectively.:
C1: {(2, 6), (3, 4), (3, 8), (4, 7)}
C2: {(6, 2), (6, 4), (7, 3), (7, 4), (8, 5), (7, 6)}

Step 3: Calculate the Total Cost:

where Ci is the cluster.

Total Cost = {Cost((3,4), (2,6)) + Cost((3,4), (3,8)) + Cost((3,4), (4,7)) + Cost((7.4), (6,2)) +
Cost((7,4), (6,4)) + Cost((7,4), (7,3)) + Cost((7,4), (8,5)) + Cost((7,4), (7,6))}

Total Cost = 3+4+4+2+3+1+1+2 = 20

Step 4: Randomly select one non-medoid point and recalculate the cost.
Old medoids: M1 = (3, 4) and M2 = (7, 4)
Select a new point O = (7, 3) . Now Swap M2 with O .
New Medoids are: M1 = (3, 4) and O = (7, 3)

Distance from M1 Distance from O

• Mdist (2,6), (3, 4)] =|2-3|+|6-4| = 3 • Mdist[(2,6), (7,3)] =|2-7|+|6-3| = 8
• Mdist[(3,4), (3,4)] = |3-3|+|4-4| =0 • Mdist[(3,4), (7,3)] = |3-7|+|4-3| =5
• Mdist[(3,8), (3,4)] = |3-3|+|8-4| =4 • Mdist[(3,8), (7,3)] = |3-7|+|8-3| =9
• Mdist[(4,7), (3,4)] = |4-3|+|7-4| =4 • Mdist[(4,7), (7,3)] = |4-7|+|7-3| =7
• Mdist[(6,2), (3,4)] = |6-3|+|2-4| =5 • Mdist[(6,2), (7,3)] = |6-7|+|2-3| =2
• Mdist[(6,4), (3,4)] = |6-3|+|4-4| =3 • Mdist[(6,4), (7,3)] = |6-7|+|4-3| =2
• Mdist[(7,3), (3,4)] = |7-3|+|3-4| =5 • Mdist[(7,3), (7,3)] = |7-7|+|3-3| =0
• Mdist[(7,4), (3,4)] = |7-3|+|4-4| =4 • Mdist[(7,4), (7,3)] = |7-7|+|4-3| =1
• Mdist[(8,5), (3,4)] = |8-3|+|5-4| =6 • Mdist[(8,5), (7,3)] = |8-7|+|5-3| =3
• Mdist[(7,6), (3,4)] = |7-3|+|6-4| =6 • Mdist[(7,6), (7,3)] = |7-7|+|6-3| =3

Based on minimum distance assign the data points to the respective clusters (C1 or C2)

16
 I X Y M1 O Cluster
X1 2 6 3 8 C1
X2 3 4 0 5 C1
X3 3 8 4 9 C1
X4 4 7 4 7 C1
X5 6 2 5 2 C2
X6 6 4 3 2 C2
X7 7 3 5 0 C2
X8 7 4 4 1 C2
X9 8 5 6 3 C2
X10 7 6 6 3 C2

The New Clusters are C1 and C2 with medoids M1 and O respectively.:

C1: {(2, 6), (3, 4), (3, 8), (4, 7)}
C2: {(6, 2), (6, 4), (7, 3), (7, 4), (8, 5), (7, 6)}
Calculate the Total Cost
Current Total Cost = {Cost((3,4), (2,6)) + Cost((3,4), (3,8)) + Cost((3,4), (4,7)) + Cost((7,3),
(6,2)) + Cost((7,3), (6,4)) + Cost((7,3), (7,4)) + Cost((7,3), (8,5)) + Cost((7,3), (7,6))}
Current Total Cost =3+4+4+2+2+1+3+3=22

Step 5: Cost of Swapping of medoid M2 with O

S = Current Total Cost - Previous Total Cost
S = 22 - 20 = 2 > 0
Hence Swapping M2 with O is not a good Idea.

Final Medoids are M1 = (3, 4) and M2 = (7, 4)

Clusters are:
C1: {(2, 6), (3, 4), (3, 8), (4, 7)}
C2: {(6, 2), (6, 4), (7, 3), (7, 4), (8, 5), (7, 6)}

17
Advantages:

1. It is simple to understand and easy to implement.

2. K-Medoid Algorithm is fast and converges in a fixed number of steps.
3. PAM (Partitioning Around Medoids) is less sensitive to outliers than other partitioning
algorithms.

Disadvantages:

1. The main disadvantage of K-Medoid algorithms is that it is not suitable for clustering non-
spherical (arbitrarily shaped) groups of objects. This is because it relies on minimizing the
distances between the non-medoid objects and the medoid (the cluster center) – briefly, it
uses compactness as clustering criteria instead of connectivity.
2. It may obtain different results for different runs on the same dataset because the first k
medoids are chosen randomly.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

Algorithm

DBSCAN is a density-based clustering algorithm that groups points in high-density areas while
marking outliers as noise. It does not require the number of clusters to be specified in advance.

Step-by-Step Procedure

Step 1: Define Parameters

 ε (epsilon): The maximum radius of a neighborhood around a point.
 MinPts: The minimum number of points required in a neighborhood to form a dense
region (core point).

Step 2: Classify Each Point

Each point in the dataset is classified into one of three categories:

1. Core Point – A point with at least MinPts neighbors within ε radius.

2. Border Point – A point within ε of a core point but with fewer than MinPts neighbors.
3. Noise Point (Outlier) – A point that is neither a core nor a border point.

Step 3: Expand Clusters

1. Select an unvisited core point and create a new cluster.
2. Include all directly reachable points (points within ε).
3. Expand the cluster recursively by adding their ε-neighbors if they are also core points.
4. Repeat until no more points can be added to the cluster.

18
Step 4: Handle Remaining Points
 Border points are assigned to the nearest cluster.
 Noise points remain unclustered (outliers).

Stopping Condition: All points are visited and assigned to a cluster or labeled as noise.

Problem-1: Consider the following 6 points in a 2D space:

P1=(1,1),P2=(2,2),P3=(2,0),P4=(8,8),P5=(8,9),P6=(25,25)

Use DBSCAN with: ε (epsilon) = 2.5 (neighborhood radius) and MinPts = 2 (minimum points
to form a core point)

Solution:

Step 1: Compute Distances Between Points. Calculate the Euclidean distance between each pair:

P1 P2 P3 P4 P5 P6
P1 0 1.41 1.41 9.89 10.63 33.94
P2 1.41 0 2 8.48 9.22 32.54
P3 1.41 2 0 10 10.77 34.36
P4 9.89 8.48 10 0 1 24.04
P5 10.63 9.22 10.77 1 0 23.32
P6 33.94 32.54 34.36 24.04 23.32 0

Step 2: Identify Core, Border, and Noise Points

 Core points have at least MinPts = 2 neighbors within ε = 2.5.

 Border points are within ε of a core point but don’t have enough points to be core
themselves.
 Noise points are neither core nor border.

Checking Each Point:

1. P1 has P2, P3 within ε = 2.5 → Core Point

2. P2 has P1, P3 within ε = 2.5 → Core Point
3. P3 has P1, P2 within ε = 2.5 → Core Point
4. P4 has P5 within ε = 2.5 → Border Point (not enough points to be core)
5. P5 has P4 within ε = 2.5 → Border Point
6. P6 has no neighbors within ε = 2.5 → Noise Point

19
Step 3: Forming Clusters

 Cluster 1: { P1, P2, P3 } (since all are core or connected)

 Cluster 2: { P4, P5 } (border points forming a small group)
 Noise: { P6 }

Final Answer

 Clusters Identified:
o Cluster 1: P1, P2, P3
o Cluster 2: P4, P5
 Noise Point: P6

This illustrates how DBSCAN naturally handles noise (P6) and finds clusters of varying density
without predefining the number of clusters.

Applications:

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is effective at handling

noise and discovering clusters of varying shapes and densities. Some real-world examples where
DBSCAN's noise-handling capability is useful:

1. GPS Trajectory Data (Urban Mobility & Traffic Analysis)

o DBSCAN can identify road segments and areas with frequent traffic while treating
erratic GPS signals (e.g., sudden jumps or errors) as noise.
2. Anomaly Detection in Cybersecurity
o It helps detect outliers in network traffic, such as intrusion attempts or DDoS
attacks, by considering unusual activity as noise.
3. Astronomical Data Analysis
o DBSCAN can cluster celestial objects like stars and galaxies while treating sensor
noise and spurious detections as noise.
4. Seismology (Earthquake Detection)
o Clusters of seismic activity can be identified, with random, non-repeating tremors
considered as noise.
5. Medical Imaging (Tumor Detection in MRI/CT Scans)
o Clustering tissue types while treating minor variations or artifacts from imaging as
noise.
6. Fraud Detection in Banking and Finance
o Identifying clusters of normal transactions and flagging outliers (suspicious
transactions) as potential fraud.
7. E-commerce & Customer Segmentation
o Clustering customers based on behavior, while treating one-time or inconsistent
buyers as noise.

20
Since DBSCAN does not require pre-specifying the number of clusters and can effectively separate
dense regions from noise, it is particularly useful in scenarios with varying densities and outliers.

Dimensionality Reduction:

Dimensionality reduction is the process of reducing the number of features (or dimensions) in a
dataset while retaining as much information as possible. It is used in machine learning, data
visualization, and noise reduction to handle high-dimensional data efficiently.

In otherwords, The number of input features, variables, or columns present in a given dataset is
known as dimensionality, and the process to reduce these features is called dimensionality
reduction.

It is commonly used in the fields that deal with high-dimensional data, such as speech recognition,
signal processing, bioinformatics, etc. It can also be used for data visualization, noise reduction,
cluster analysis, etc.

The Curse of Dimensionality:

Handling the high-dimensional data is very difficult in practice, commonly known as the curse of
dimensionality. If the dimensionality of the input dataset increases, any machine learning
algorithm and model becomes more complex. As the number of features increases, the number of
samples also gets increased proportionally, and the chance of overfitting also increases. If the
machine learning model is trained on high-dimensional data, it becomes overfitted and results in
poor performance. Hence, it is often required to reduce the number of features, which can be done
with dimensionality reduction.

Approaches of Dimension Reduction:

There are two ways to apply the dimension reduction technique:

21
[Link] Selection

Feature selection is the process of selecting the subset of the relevant features and leaving out the
irrelevant features present in a dataset to build a model of high accuracy. In other words, it is a
way of selecting the optimal features from the input dataset.

Three methods are used for the feature selection:

i. Filters Methods

In this method, the dataset is filtered, and a subset that contains only the relevant features is taken.
Some common techniques of filters method are:

 Correlation
 Chi-Square Test
 ANOVA
 Information Gain, etc.

ii. Wrappers Methods

The wrapper method has the same goal as the filter method, but it takes a machine learning model
for its evaluation. In this method, some features are fed to the ML model, and evaluate the
performance. The performance decides whether to add those features or remove to increase the
accuracy of the model. This method is more accurate than the filtering method but complex to
work. Some common techniques of wrapper methods are:

 Forward Selection
 Backward Selection
 Bi-directional Elimination

iii. Embedded Methods:

Embedded methods check the different training iterations of the machine learning model and
evaluate the importance of each feature. Some common techniques of Embedded methods are:

 LASSO
 Elastic Net
 Ridge Regression, etc.

[Link] Extraction:

Feature extraction is the process of transforming the space containing many dimensions into space
with fewer dimensions. This approach is useful when we want to keep the whole information but
use fewer resources while processing the information.

22
Some common feature extraction techniques are:

1. Principal Component Analysis

2. Linear Discriminant Analysis
3. Kernel PCA
4. Quadratic Discriminant Analysis

Common techniques of Dimensionality Reduction:

1. Principal Component Analysis

2. Backward Elimination
3. Forward Selection
4. Score comparison
5. Missing Value Ratio
6. Low Variance Filter
7. High Correlation Filter
8. Random Forest
9. Factor Analysis
10. Auto-Encoder

Advantages of Dimensionality Reduction

 Faster Computation: With fewer features, machine learning algorithms can process data
more quickly. This results in faster model training and testing, which is particularly
useful when working with large datasets.
 Better Visualization: As we saw in the earlier figure, reducing dimensions makes it
easier to visualize data, revealing hidden patterns.
 Prevent Overfitting: With fewer features, models are less likely to memorize the
training data and overfit. This helps the model generalize better to new, unseen data,
improving its ability to make accurate predictions.

Disadvantages of dimensionality Reduction

 Data Loss & Reduced Accuracy – Some important information may be lost during
dimensionality reduction, potentially affecting model performance.
 Interpretability Challenges – The transformed features (e.g., principal components)
may not have clear meanings, making it harder to understand relationships in the original
data.
 Choosing the Right Components – Deciding how many dimensions to keep is difficult,
as keeping too few may lose valuable information, while keeping too many can lead to
overfitting.

23
Principal Component Analysis:

Principal Component Analysis (PCA) is a statistical method used for dimensionality reduction
while preserving as much variance as possible in the dataset. Here’s a breakdown of the key
points to understand PCA:

1. Purpose of PCA:

 Dimensionality Reduction: PCA reduces the number of variables in the dataset, making
it easier to analyze without losing much information.
 Feature Extraction: PCA helps to identify patterns and features that capture the most
variance in the data.

2. How PCA Works:

PCA transforms the data into a new set of orthogonal (uncorrelated) axes called principal
components (PCs).

 Principal Component 1 (PC1): The direction of maximum variance in the data.

 Principal Component 2 (PC2): The next direction of maximum variance, perpendicular
to PC1, and so on.

These new components are linear combinations of the original features. The goal is to keep the
most important components (those with the highest variance) while discarding the less important
ones.

3. Steps in PCA:

1. Standardize the Data: Since PCA is sensitive to the scale of the data, it's important to
standardize the dataset (mean = 0 and standard deviation = 1).
2. Calculate the Covariance Matrix: This matrix expresses the relationship between all
pairs of features.
3. Compute the Eigenvalues and Eigenvectors of the covariance matrix. Eigenvectors
represent the direction of the new feature axes, and eigenvalues tell you the magnitude
(variance) along those axes.
4. Sort Eigenvalues and Eigenvectors: Arrange them in descending order of eigenvalues.
The eigenvector with the largest eigenvalue is the first principal component, and so on.
5. Select Top k Components: Based on the eigenvalues, decide how many principal
components to keep. This is often determined by the explained variance (e.g., selecting
enough components to explain 95% of the variance).
6. Transform the Data: Project the original data onto the selected principal components.

24
25
26
4. Mathematical Concepts Involved:

 Eigenvectors: Directions in which data points vary the most.

 Eigenvalues: Measure of variance along the corresponding eigenvector.
 Covariance Matrix: Captures the correlation between different features.

5. Explained Variance:

PCA provides an explained variance ratio for each principal component. This shows how much of
the total variance in the data is captured by each component. The sum of the explained variance
ratios of all principal components equals 1 (100%).

6. Benefits of PCA:

 Reduction in Computational Complexity: Fewer dimensions (features) result in faster

processing time.
 Visualization: Reduces data to 2 or 3 dimensions for easier visualization.
 Noise Reduction: By eliminating less important dimensions (those with low variance),
PCA can help reduce noise in the data.

7. Challenges and Considerations:

 Interpretability: The new principal components may not be easy to interpret, especially if
they are combinations of several features.
 Linear Assumption: PCA assumes that the data lies on a linear subspace. It might not
perform well with non-linear data.
 Scaling: Features need to be on the same scale to prevent PCA from being biased towards
features with larger values.

8. Applications of PCA:

 Data Preprocessing: PCA is used before applying machine learning algorithms to reduce
dimensionality.
 Image Compression: Reducing the size of images while maintaining key features.

27
  Data Visualization: Reducing complex datasets to 2 or 3 dimensions for easier
interpretation.
 Noise Reduction: By focusing on the components with high variance, PCA can help
remove noise.

9. Example Calculation:

 Suppose you have a dataset with 3 features, and you want to reduce it to 2 dimensions:
1. Standardize the data.
2. Calculate the covariance matrix.
3. Find the eigenvalues and eigenvectors.
4. Choose the top 2 eigenvectors (principal components).
5. Transform the original data into the new principal components.

Outlier Analysis and Outlier Detection:

Outlier analysis is the process of identifying and analyzing data points that deviate significantly
from the rest of the data in a dataset. These data points, known as outliers, do not conform to the
general pattern or trend of the data. Outlier analysis is crucial in many fields, including statistics,
machine learning, data mining, and even business decision-making, as outliers can represent
anomalies, errors, or rare events that can significantly impact the analysis and models.

What Are Outliers?

An outlier is a data point that differs significantly from the other observations in a dataset. Outliers
may be unusually high or low compared to the expected pattern or trend in the data. They could
represent:

1. Errors or noise: Sometimes outliers are caused by data entry errors, measurement errors,
or miscommunication.
2. Rare events: Outliers may indicate rare but significant events that are genuinely different
from the majority of the data. For example, in financial data, an outlier might represent an
extreme price change or fraud detection.
3. New trends: Outliers can sometimes be indicative of new trends or patterns that have yet
to be discovered in the data, such as in market analysis or detecting new diseases.

Importance of Outlier Analysis:

Outliers can have a significant impact on various data analysis tasks, including:

 Statistical Analysis: Outliers can distort summary statistics like the mean, standard
deviation, and correlation. For instance, a single extreme outlier can shift the mean of a
dataset, which can lead to misleading interpretations.

28
  Machine Learning Models: Many machine learning algorithms (such as linear regression,
k-means clustering, and decision trees) are sensitive to outliers. If outliers are not properly
handled, they can lead to poor model performance, overfitting, or incorrect predictions.
 Data Quality: Detecting and handling outliers is essential for ensuring the quality and
reliability of data before further analysis.

Types of Outliers:

Outliers can be broadly classified into two categories:

1. Univariate Outliers: These are outliers based on a single feature or variable. For example,
a person with an unusually high income compared to others in the dataset.
2. Multivariate Outliers: These occur when a data point deviates from the general pattern in
a multivariate (multi-dimensional) dataset. A data point might appear normal for one
variable but be an outlier when considering multiple variables simultaneously.

Techniques for Outlier Detection:

There are several methods to detect outliers in a dataset, ranging from statistical tests to machine
learning algorithms:

 Visual Methods:
o Boxplots and scatterplots can help visualize the distribution of the data and
highlight points that lie outside the normal range.
 Statistical Methods:
o Z-Score: A data point is considered an outlier if its Z-score (the number of standard
deviations away from the mean) exceeds a certain threshold (often 3).
o IQR (Interquartile Range): Outliers can be detected as data points that lie beyond
1.5 times the interquartile range (IQR) above the third quartile or below the first
quartile.
 Model-Based Methods:
o DBSCAN (Density-Based Spatial Clustering of Applications with Noise): This
clustering algorithm can identify outliers as points that do not belong to any dense
region.
o Isolation Forest: A machine learning technique that isolates outliers by randomly
selecting features and recursively splitting the data.

How to Handle Outliers:

Once outliers are detected, there are several strategies for handling them:

1. Remove Outliers: In some cases, outliers might be errors or irrelevant data points, and
removing them can improve the overall analysis. However, caution is needed, as this could
lead to the loss of valuable information, especially if the outliers represent rare but
important events.

29
 2. Transform the Data: Applying transformations such as logarithms or scaling may reduce
the effect of outliers on the dataset.
3. Impute Missing Values: In some cases, missing or erroneous data points identified as
outliers can be replaced with a more appropriate value (like the median or mean).
4. Use Robust Models: Some algorithms (e.g., tree-based models, robust regression) are less
sensitive to outliers and can handle them without significant impact.

Problem-1: Consider the following dataset of sales figures for 10 different stores (in thousands
of dollars):

Sales=[15,18,21,22,25,30,32,35,38,200]

The value 200 seems unusually large compared to the other sales numbers. We will verify this
using the Z-score method to check if this is indeed an outlier.

Solution:

Step 1: Calculate the Mean and Standard Deviation.

Calculating the squared differences from the mean for each score:
(15−40.6)2=650.76
(18−40.6)2=506.76
(21−40.6)2=396.96
(22−40.6)2=345.96
(25−40.6)2=245.76
(30−40.6)2=112.36
(32−40.6)2=73.96

30
 (35−40.6)2=31.36
(38−40.6)2=6.76
(200−40.6)2=25419.36

sum these squared differences:

650.76+506.76+396.96+345.96+245.76+112.36+73.96+31.36+6.76+25419.36=27779. 60

Calculate the standard deviation:

Step 2: Calculate the Z-Score

The Z-score for each value is calculated using the formula:

Where x is each individual score, μ is the mean, and σ is the standard deviation.

31
Step 3: Identify Outliers

From the Z-scores, we see that:

 The Z-scores for the majority of the data points are close to 0, with values between -0.49
and -0.05, which are typical and within the expected range.
 For the value 200, the Z-score is 3.02, which is greater than 3.

Problem-2: Consider the following set of exam scores of 10 students:

Scores=[45,55,67,70,72,85,88,90,100,500]

The score 500 is likely an outlier because it is much higher than the others, but we will verify
this using outlier analysis.

Solution:

Step 1: Calculate the Mean and Standard Deviation.

Mean (Average):

32
Standard Deviation (SD):

Calculating the squared differences from the mean for each score:
(45−151.2)2=11297.44
(55−151.2)2=9231.04
(67−151.2)2=7071.04
(70−151.2)2=6645.44
(72−151.2)2=6252.84
(85−151.2)2=4374.44
(88−151.2)2=3964.84
(90−151.2)2=3745.44
(100−151.2)2=2601.44
(500−151.2)2=122562.24
sum the squared differences:
11297.44+9231.04+7071.04+6645.44+6252.84+4374.44+3964.84+3745.44+2601.44+122562.2
4 =179185.20
calculate the standard deviation:

Step 2: Calculate the Z-Score

The Z-score for each value is calculated using the formula:

Where x is each individual score, μ is the mean, and σ is the standard deviation.

33
Let's calculate the Z-scores for each data point:

Step 3: Identify Outliers

Typically, a Z-score greater than 3 or less than -3 indicates that a point is an outlier. In our case:

 The Z-score for 500 is 2.60, which is above 2, but not quite above the threshold of 3.
However, given that it's far higher than the other values, it may still be considered an
outlier, depending on the context.

Outlier Detection Using IQR (Interquartile Range):

The Interquartile Range (IQR) method is a statistical way to detect outliers. It works by identifying
values that lie far outside the middle range of the dataset.

34
Problem-1: Consider the Dataset

X=[10,12,14,15,18,21,24,100]

Solution:

Step 1: Compute IQR

The IQR is given by:

IQR=Q3−Q1

where:
 Q1 (First Quartile) = 25th percentile of the data
 Q3 (Third Quartile) = 75th percentile of the data

A data point is considered an outlier if it lies outside:

Lower Bound=Q1−1.5×IQR

Upper Bound=Q3+1.5×IQR

Step 2: Compute Q1, Q3, and IQR

1. Sort the Data:

[10,12,14,15,18,21,24,100]

2. Find Q1 (25th percentile):

Median of the lower half (10, 12, 14, 15)

3. Find Q3 (75th percentile):

Median of the upper half (18, 21, 24, 100)

4. Compute IQR:

35
Step 3: Compute Outlier Thresholds

Step 4: Identify Outliers

Any value below -1.25 or above 36.75 is an outlier. Outlier in the given dataset is: 100

Introduction to Reinforcement Learning and its Applications:

Reinforcement Learning is a part of machine learning. Here, agents are self-trained on reward and
punishment mechanisms. It’s about taking the best possible action or path to gain maximum
rewards and minimum punishment through observations in a specific situation. It acts as a signal
to positive and negative behaviors. Essentially an agent (or several) is built that can perceive and
interpret the environment in which is placed, furthermore, it can take actions and interact with it.

How Does Reinforcement Learning Work?

1. Start in a state

The state represents the current situation of the agent in the environment. It can be a simple
representation (e.g., robot’s location on a grid) or a more complex one (e.g., all objects and
their positions in a room). The agent needs to understand the current state to make informed
decisions about its actions.

36
 2. Take an action

Based on its current policy (essentially a strategy for choosing actions), the agent selects
an action to perform in the environment. This action could be anything from moving to a
new location to manipulating an object. The policy can be random initially, but the goal is
to learn and improve it over time.

3. Receive a reward or penalty from the environment

The environment provides feedback to the agent in the form of a reward signal. This reward
can be positive (for achieving a desired outcome) or negative (for making a mistake). In
some cases, there might be no reward (neutral), indicating the action didn’t bring the agent
closer to its goal. This reward signal is crucial for the agent to learn the consequences of
its actions.

4. Observe the new state of the environment

After taking the action, the environment transitions to a new state. This new state reflects
the outcome of the action. The agent observes this new state, which becomes its starting
point for the next decision cycle.

5. Update your policy to maximize future rewards

This is the heart of the learning process. Based on the reward received, the agent updates
its policy to favor actions that lead to higher rewards in the long run. Various algorithms
exist for updating the policy, but they all aim to learn from past experiences and improve
future decision-making.

By exploring the environment and trying different actions, the agent gradually learns the best
course of action for different situations. These learned behaviors are like a set of guidelines, or a
policy, that helps the agent choose its next action. The goal is to maximize its total reward over
time. However, the agent faces a dilemma: should it keep exploring new possibilities to discover
potentially even better rewards, or should it stick with actions that have already proven
successful? This is known as the exploration-exploitation trade-off.

Terminologies used in Reinforcement Learning:

 Agent – Agent or Reinforcement learning agent or Learning agent all are same. It is the
sole decision-maker and learner
 Environment – a physical world where an agent learns and decides the actions to be
performed
 Action Space – a list of action which an agent can perform
 Action -An agent’s single choice (move left, pick up object) in the environment.
 State – the current situation of the agent in the environment

37
  Reward – For each selected action by agent to solve reinforcement learning problem, the
environment gives a reward. It’s usually a scalar value and nothing but feedback from the
environment
 Reward Function: This is a predefined function within the RL framework that determines
how rewards are assigned based on the state of the environment and the agent’s actions.
 Policy – the agent prepares strategy(decision-making) to map situations to actions.
 Value Function – The value of state shows up the reward achieved starting from the state
until the policy is executed
 Model – Every RL agent doesn’t use a model of its environment. The agent’s view maps
state-action pairs probability distributions over the states.

Characteristics of Reinforcement Learning:

 No supervision, only a real value or reward signal

 Decision making is sequential
 Time plays a major role in reinforcement problems
 Feedback isn’t prompt but delayed
 The following data it receives is determined by the agent’s actions

Types of Reinforcement Learning:

1. Positive Reinforcement: Positive reinforcement is defined as when an event, occurs due to

specific behavior, increases the strength and frequency of the behavior. It has a positive impact on
behavior.

Advantages

 Maximizes the performance of an action

 Sustain change for a longer period

Disadvantage

 Excess reinforcement can lead to an overload of states which would minimize the results.

2. Negative Reinforcement: Negative Reinforcement is represented as the strengthening of a

behavior. In other ways, when a negative condition is barred or avoided, it tries to stop this action
in the future.

Advantages
 Maximized behavior
 Provide a decent to minimum standard of performance

Disadvantage
 It just limits itself enough to meet up a minimum behavior

38
Approaches to Implement Reinforcement Learning Algorithms:

Model-Based:

 Attempts to learn a model of the environment dynamics. This model predicts the next state
and reward for a given state-action pair.
 The agent can then use this model to plan and simulate actions in a virtual environment
before taking them in the real world.
 While conceptually appealing, this approach can be computationally expensive for
complex environments and often requires additional assumptions about the environment’s
behavior.

Value-Based:

 Focuses on learning a value function that estimates the expected future reward for an agent
in a given state under a specific policy.
 The agent aims to maximize this value function to achieve long-term reward.
 Popular algorithms in this category include Q-Learning, SARSA, and Deep Q-Networks
(DQN).

Policy-Based:

 Directly learns the policy function, which maps states to actions.

 The goal is to find the optimal policy that leads to the highest expected future rewards.
 Examples of policy-based methods include REINFORCE, Proximal Policy Optimization
(PPO), and Actor-Critic methods.

Applications of reinforcement learning:

 Robotics for Industrial Automation

 Text summarization engines, dialogue agents (text, speech), gameplays
 Autonomous Self Driving Cars
 Machine Learning and Data Processing
 Training system which would issue custom instructions and materials with respect to the
requirements of students
 AI Toolkits, Manufacturing, Automotive, Healthcare, and Bots
 Aircraft Control and Robot Motion Control
 Building artificial intelligence for computer games

39