MODULE #3
Unsupervised Machine Learning
Module #3 : Unsupervised Machine Learning 1
Module #3: Unsupervised Machine Learning
Lecture 16: Unsupervised Machine Learning: K Means Algorithm
Lecture 17: Hierarchical Clustering
Lecture 18: The Self Organizing feature map
Lecture 19: Explanation based Learning
Lecture 20: Markov Decision Process
Lecture 21: Reinforcement Learning and Evaluating Hypotheses
Lecture 22: Learning Task, Q Learning
Lecture 23: Non-Deterministic Rewards and Actions
Session
Topic Sub-Topic CO Number Reference
Number
Co4, Co5,
1. L16, Unsupervised learning Unsupervised Learning: K-means algorithms T1: [Link].14
Co4, Co5,
L17 Unsupervised Learning Hierarchical Clustering [Link].282-290
Module #3 : Unsupervised Machine Learning 2
Module #3 : Unsupervised Machine Learning 3
What is Clustering?
Clustering refers to grouping similar data points
based on their characteristics or features.
Clustering: grouping data based on similarity
patterns used on distance
The goal is to group similar instances into
clusters. Clustering is an excellent tool for data
analysis, customer segmentation, recommender
systems, search engines, image segmentation,
semi-supervised learning, dimensionality
reduction, and more.
Module #3 : Unsupervised Machine Learning 4
What is K-means Clustering?
K means is an Unsupervised learning and is also
called clustering algorithm.
K mean is a clustering algorithm is used to
classify unlabeled data into groups/clusters
based on similarity.
K defines the number of pre-defined clusters that
need to be created in the process. if K=2, there
will be two clusters, and for K=3, there will be
three clusters, and so on.
Module #3 : Unsupervised Machine Learning 5
“It is an iterative algorithm that divides the
unlabeled dataset into k different clusters in such a
way that each dataset belongs to only one group
that has similar properties. ”
It allows us to cluster the data into different groups
and is a convenient way to discover the categories
of groups in the unlabeled dataset on its own
without the need for any training.
Module #3 : Unsupervised Machine Learning 6
It is a centroid-based algorithm, where each cluster is associated with a centroid.
The main aim of this algorithm is to minimize the sum of distances between the data
point and their corresponding clusters.
K-means then tries to determine different k-points called centroids, which are at the
centre (least cumulative distance) from other points of the same class, but further away
from points of another class.
The algorithm takes the unlabeled dataset as input, divides the dataset into k-number
of clusters, and repeats the process until it does not find the best clusters. The value of
k should be predetermined in this algorithm.
Module #3 : Unsupervised Machine Learning 7
Aim of the K-Mean Algorithm:
The k-means clustering algorithm mainly performs two tasks:
•Determines the best value for K center points or centroids by an iterative process.
•Assigns each data point to its closest K-center. Those data points which are near
to the particular K-center, create a cluster.
Module #3 : Unsupervised Machine Learning 8
How K-Mean Algorithm Works:
Step 1: Plot Data
Step 2: Select the number K to decide the number of clusters.
Step 3: Select random K points or centroids. (It can be other from the input
dataset).
Step 4: Assign each data point to their closest centroid, which will form the
predefined K clusters.
Step 5: Repeat the fourth step, which means reassigning each data point to
the new closest centroid of each cluster.
Module #3 : Unsupervised Machine Learning 9
Module #3 : Unsupervised Machine Learning 10
Figure 1 shows the representation of data from two different items.
• The first item has shown in blue colour and the second item has shown in
red colour.
• We choose the value of K randomly as 2.
• There are different methods by which we can choose the right k values.
In Figure 2, Join the two selected points.
• Now to find out the centroid, we will draw a perpendicular line to that line. The points will
move to their centroid.
• Then you will see that some of the red points are now moved to the blue points.
• Now, these points belong to the group of blue color items.
Module #3 : Unsupervised Machine Learning 11
• The same process will continue in Figure 3.
• We will join the two points and draw a perpendicular line to that and find out the
centroid.
• Now the two points will move to its centroid and again some of the red points get
converted to blue points.
• The same process is happening in Figure 4.
• This process will be continued until and unless we get two completely different
clusters of these groups.
Module #3 : Unsupervised Machine Learning 12
Intercluster distance should be high: The distance between observations in
two clusters should be High.
Intracluster Distance should be Very Less: The distance of observation within
the cluster should be very less.
Module #3 : Unsupervised Machine Learning 13
Measuring Distance:
Euclidean Distance Measure:
The most common case is determining the
distance between two points.
If we have point P and point Q, the
Euclidean distance is an ordinary straight
line.
It is the distance between the two points
in Euclidean space.
Module #3 : Unsupervised Machine Learning 14
Manhattan Distance Measure:
The Manhattan distance is the simple sum of the horizontal and
vertical components or the distance between two points measured
along axes at right angles.
The formula is shown below:
Module #3 : Unsupervised Machine Learning 15
Overview of K-Means Clustering
Module #3 : Unsupervised Machine Learning 16
How to evaluate K-Mean Model?
Silhouette Coefficient:
Silhouette Coefficient or silhouette score is a metric used to calculate the
goodness of a clustering technique. Its value ranges from -1 to 1.
1 : Means clusters are well apart from each other and clearly distinguished.
0 : Means clusters are indifferent, or we can say that the distance between
clusters is not significant.
Module #3 : Unsupervised Machine Learning
17
1: Means clusters are assigned in the wrong
way.
Module #3 : Unsupervised Machine Learning
18
How to select the optimal value for k?
Elbow Method:
• The Elbow method is one of the most popular ways to find the optimal number of
clusters.
• WCSS stands for Within Cluster Sum of Squares, which defines the total variations
within a cluster.
Module #3 : Unsupervised Machine Learning
19
How does it work?
Step 1: Start with some k
k=[2,3,4,5,6,…10]
Step 2: If k=2 apply k-mean, it will find WCSS
Step 3: Then step repeat for different k values
Step 4: Plot a graph of k versus WCSS.
Step 5: Choose the k value after which the WCSS
value is constant.
Module #3 : Unsupervised Machine Learning
20
Hierarchical Clustering
• Hierarchical clustering is another unsupervised machine learning
algorithm.
• It is used to group the unlabeled datasets into a cluster and also known as
hierarchical cluster analysis or HCA.
• In this algorithm, we develop the hierarchy of clusters in the form of a tree,
and this tree-shaped structure is known as the dendrogram.
• In hierarchical clustering there is no requirement to predetermine the
number of clusters as we did in the K-Means algorithm.
Module #3 : Unsupervised Machine Learning
21
The hierarchical clustering technique has two approaches:
Agglomerative: Agglomerative is a bottom-up approach, which it starts with
taking all data points as single clusters and merging them until one cluster is
left.
Divisive: Divisive algorithm is the reverse of the agglomerative algorithm as it is
a top-down approach.
Module #3 : Unsupervised Machine Learning
22
How the Agglomerative Hierarchical clustering Work?
Step-1: Create each data point as a single cluster. Let’s say there are N data points, so the
number of clusters will also be N.
Module #3 : Unsupervised Machine Learning
23
Step-2: Take two closest data points or clusters and merge them to form one cluster.
So, there will now be N-1 clusters.
Module #3 : Unsupervised Machine Learning
24
Step-3: Again, take the two closest clusters and merge them together to form one
cluster. There will be N-2 clusters.
Module #3 : Unsupervised Machine Learning
25
Step-4: Repeat Step 3 until only one cluster left. So, we will get the following clusters.
Consider the below images:
Module #3 : Unsupervised Machine Learning
26
Step-4: Repeat Step 3 until only one cluster left. So, we will get the following clusters.
Consider the below images:
Module #3 : Unsupervised Machine Learning
27
Step-5: Once all the clusters are combined into one big cluster, develop the
dendrogram to divide the clusters as per the problem.
Module #3 : Unsupervised Machine Learning
28
Interested to Know More…
Read more:
Hierarchical Clustering:
[Link]
unsupervised-learning-81213f56cfc9
K-Means Clustering:
[Link]
How to solve K-means clustering Numerically
[Link]
3c94d25076e8
Module #3 : Unsupervised Machine Learning
29
Lecture #16: Questions to Ponder
Which method helps determine optimal K?
A) PCA
B) Elbow Method
C) Naive Bayes
D) Gradient Descent
In K-Means, what does “K” represent?
A) Number of features
B) Number of clusters
C) Number of iterations
D) Number of centroids
Module #3 : Unsupervised Machine Learning
30
Hierarchical clustering can be classified into:
A) Supervised and Unsupervised
B) Agglomerative and Divisive
C) Linear and Non-linear
D) Parametric and Non-parametric
In Agglomerative clustering:
A) Start with one cluster
B) Start with each point as a cluster
C) Random clusters are formed
D) Clusters are predefined
Module #3 : Unsupervised Machine Learning
31
MODULE #3
Unsupervised Machine Learning
Module #3 : Unsupervised Machine Learning 1
Module #3: Unsupervised Machine Learning
Lecture 16: Unsupervised Machine Learning: K Means Algorithm
Lecture 17: Hierarchical Clustering
Lecture 18: The Self Organizing feature map
Lecture 19: Explanation based Learning
Lecture 20: Markov Decision Process
Lecture 21: Reinforcement Learning and Evaluating Hypotheses
Lecture 22: Learning Task, Q Learning
Lecture 23: Non-Deterministic Rewards and Actions
Session
Topic Sub-Topic CO Number Reference
Number
Co4, Co5, Online web
1. L18 Feature map The self-organizing feature map
reference W3
Module #3 : Unsupervised Machine Learning 2
Self-organizing maps (SOMs), also known as
Kohonen maps, are a type of artificial neural
What is SOM?
network that are used for clustering, dimensionality
reduction.
SOMs can be used for dimensionality reduction,
visualization, pattern recognition, anomaly detection,
etc.
SOMs map high-dimensional input data onto a lower-
dimensional grid.
⚠️ Self-Organizing Maps are unsupervised, their
neurons (nodes) are not connected and they do not
use backpropagation.
Module #3 : Unsupervised Machine Learning 3
• The goal of a SOM is to map high-dimensional input data onto a lower-dimensional
grid while preserving the topological relationships.
• Neurons that are spatially close on the map are also similar in terms of the input
data they represent — between the input data points.
• The output of a SOM is a 2D grid (of neurons) where each cell (neuron) is like a kid
who knows one piece of the information.
• Kids that are close to each other in the grid know similar things.
Module #3 : Unsupervised Machine Learning 4
The following is a hexagonal SOM. Neurons that are close to each other
have similar colors and represent similar countries.
Module #3 : Unsupervised Machine Learning 5
How does SOM Learn?
A SOM is a grid of neurons. Each neuron has N weights, where N is the number of
dimensions (features) in the data.
The training process can be summarized in seven steps:
Step 1: Assign random weights to the neurons.
Step 2: Select an input data point.
Step 3: Calculate the distance between the data point and each neuron.
Step 4: Identify the neuron with the smallest distance to the data point.
This neuron is referred to as the Best Matching Unit (BMU) or winning neuron. A
small distance means that the neuron is very close to the data point.
Module #3 : Unsupervised Machine Learning 6
Module #3 : Unsupervised Machine Learning 7
Step 5: Drag the winning neuron closer to the data point.
When you drag a neuron, its neighbors (in the radius) are also dragged.
The closer the neuron, the more drastically it is dragged, resulting in a larger
change in its weight vector.
Module #3 : Unsupervised Machine Learning 8
Step 6: Decrease the radius gradually,
so that neurons farther away from the
BMU are less affected by the updates.
A radius that is too small could lead to
overfitting while a bigger one could
underfit the data.
Module #3 : Unsupervised Machine Learning 9
Step 7: In the resulting map, each
winning neuron is assigned to a
particular cluster based on its location
and the distribution of the input data.
Neurons that are close to each other in
the SOM are likely to be assigned to the
same cluster, reflecting similarities in the
underlying data patterns.
Module #3 : Unsupervised Machine Learning 10
SOMs have some limitations, such as:
• Poor performance with categorical data.
• Lack of interpretability.
• Limited ability to handle high-dimensional data.
• Limited generalization ability: not well-suited for unseen data.
• Difficulty with non-linear relationships.
Module #3 : Unsupervised Machine Learning 11
More concretely, we can use SOMs to:
Build recommender system: grouping similar movies, music, product
reviews, etc.
Identify trends and patterns: find similar employees, customers, social media
topics, stock sector performances, etc.
Detect outliers: Detect and prevent fraud, security breaches, and other
abnormal behavior.
Module #3 : Unsupervised Machine Learning 12
Interested to Know More…
Read more:
Self Organizing Map (SOM):
1. [Link]
2. [Link]
3. [Link]
Module #3 : Unsupervised Machine Learning
13
MODULE #3
Unsupervised Machine Learning
Module #3 : Unsupervised Machine Learning 1
Module #3: Unsupervised Machine Learning
Lecture 16: Unsupervised Machine Learning: K Means Algorithm
Lecture 17: Hierarchical Clustering
Lecture 18: The Self Organizing feature map
Lecture 19: Explanation based Learning
Lecture 20: Markov Decision Process
Lecture 21: Reinforcement Learning and Evaluating Hypotheses
Lecture 22: Learning Task, Q Learning
Lecture 23: Non-Deterministic Rewards and Actions
Session
Topic Sub-Topic CO Number Reference
Number
1. L19. Explanation based learning, Co4, Co5, T1: [Link].13
EBL, MDP [Link].268-239
2. L20 Markov Decision Process
Module #3 : Unsupervised Machine Learning 2
Reinforcement Learning (RL) is a powerful paradigm within machine learning,
where an agent learns to make decisions by interacting with an environment to
maximize cumulative rewards.
At the heart of RL lies the Markov Decision Process (MDP), a mathematical
framework used to model decision-making in situations where outcomes are
partially random and partially under the control of a decision maker (agent).
So, Markov Decision Process is defined as a mathematical framework
to model sequential decision making processes in a stochastic
environment.
Module #3 : Unsupervised Machine Learning 3
Markov Property:
Markov Property states that the future state only depends on the present state
because the current state has already information about the past states.
Let’s say, S is all the possible states in an environment and s₁, s₂, s₃, s₄, …, sₙ∈ S. The
current state is sₜ and the next state is sₜ₊₁. P denotes the probability.
So according to Markov Property, we can say that,
Module #3 : Unsupervised Machine Learning 4
Markov Chain (or Markov Process):
It comprises s₁, s₂, s₃, s₄, …, sₙ ∈ S states that follow the Markov property, and there are
some possible transitions between these states.
When an agent is at sᵢ and goes to sⱼ, then there is a transition probability Pᵢⱼ(from sᵢ ->
sⱼ).
Module #3 : Unsupervised Machine Learning 5
Components of Markov Process:
An MDP is defined by four key components:
1. States (S): A finite set of states that represent all possible situations the agent
can encounter.
2. Actions (A): A finite set of actions available to the agent in each state.
3. Transition Model (P): The transition probability P(s’|s,a) defines the probability
of transitioning to state s’ from state s after taking action a.
4. Reward Function (R): The reward function R(s,a,s’) specifies the immediate
reward received after transitioning from state s to state s’ due to action a.
Module #3 : Unsupervised Machine Learning 6
Additionally, MDPs often include a discount factor (γ), which is a value between 0 and 1
that represents the importance of future rewards.
A higher discount factor means the agent values future rewards more significantly
compared to immediate rewards.
Module #3 : Unsupervised Machine Learning 7
Working Mechanism of MDP:
The objective in an MDP is to find an optimal policy π that maximizes the
expected cumulative reward, also known as the return.
The return is calculated as the sum of discounted rewards over time:
Module #3 : Unsupervised Machine Learning 8
Step-by-Step Process:
Step 1: Initialization: The agent begins in an initial state s₀.
Step 2: Action Selection: At each time step t, the agent selects an action aₜ based on its
current policy π. The policy is a strategy that maps states to actions, aiming to maximize
future rewards.
Step 3: State Transition: The environment transitions to a new state sₜ₊₁ according to the
transition probability P(sₜ₊₁|sₜ,aₜ).
Step 4: Reward Assignment: The agent receives a reward rₜ = R(sₜ, aₜ, sₜ₊₁) based on the
action taken and the resulting state transition.
Step 5: Policy Update: The agent updates its policy based on the new state and received
reward, aiming to improve future decisions to maximize cumulative rewards.
Module #3 : Unsupervised Machine Learning 9
To gain a proper mathematical understanding about Markov Decision Process.
Let S = { s1, s2, …, sN } be the finite set of States that represent different situations
and configurations of the environment.
A={a1,a2,…, aN} be the finite set of Actions that the agent can take to influence the
environment. Actions represent the decisions made by the agent.
The probabilities of transitioning from one state to another when a specific action is
taken.
This is often represented by the transition probability functions T(s,a,s′), which gives
the probability of transitioning from states to state s’ when action A is taken.
Module #3 : Unsupervised Machine Learning 10
Rewards are received by the agent after taking a specific action in a particular state.
It is typically represented by the reward function R(s, a, s ′), which assigns a numerical
value to each state-action-state triple.
To define a policy ( π ) which is a strategy or mapping that defines the agent’s
behaviour.
It specifies which action to take in each state.
A policy can be stochastic (a probability distribution over actions) or deterministic (a
single action for each state).
Mathematically, π is a function that maps states to actions: π: S→A.
•
Module #3 : Unsupervised Machine Learning 11
Framework has the following sub-parts:-
[Link] (S): A set of states that the system can be in.
[Link] (A): A set of actions that can be taken in each state.
[Link] Model (T): A probability distribution that specifies the next state given the
current state and action.
[Link] Function (R): A function that assigns a reward or penalty to each state-action
pair.
[Link] Factor (γ): A value between 0 and 1 that determines how much to discount
future rewards.
Module #3 : Unsupervised Machine Learning 12
The main difference between finite and infinite Markov Decision Processes (MDPs) is the
size of the state and action spaces.
Finite MDP:
[Link] state space: The number of states is finite and countable.
2. Finite action space: The number of actions is finite and countable.
3. Episodic or discounted: Finite MDPs can be episodic (fixed-length episodes) or
discounted (infinite horizon with discount factor).
4. Exact solutions: Finite MDPs can be solved exactly using methods like Dynamic
Programming (DP) or Linear Programming (LP).
Examples:
Finite-state machines, Small-scale inventory control problems
Module #3 : Unsupervised Machine Learning 13
Infinite MDP:
1. Infinite state space: The number of states is infinite and possibly uncountable.
2. Infinite action space: The number of actions is infinite and possibly uncountable.
3. Discounted or average-reward: Infinite MDPs are typically discounted (infinite horizon with
discount factor) or average-reward (long-run average reward).
4. Approximate solutions: Infinite MDPs often require approximate solution methods, such as:
— Function approximation (e.g., neural networks)
— Sampling-based methods (e.g., Monte Carlo Tree Search)
Examples:
1. Continuous-state control problems (e.g., robotics, autonomous vehicles)
2. Large-scale inventory control problems
3. Complex queuing systems
Module #3 : Unsupervised Machine Learning 14
Module #3 : Unsupervised Machine Learning 15
Module #3 : Unsupervised Machine Learning 16
Interested to Know More…
Read more:
MDP:
1. [Link]
2. [Link]
explained-in-plain-english-79087514dba1
Module #3 : Unsupervised Machine Learning
17
MODULE #3
Unsupervised Machine Learning
Module #3 : Unsupervised Machine Learning 1
Module #3: Unsupervised Machine Learning
Lecture 16: Unsupervised Machine Learning: K Means Algorithm
Lecture 17: Hierarchical Clustering
Lecture 18: The Self Organizing feature map
Lecture 19: Explanation based Learning
Lecture 20: Markov Decision Process
Lecture 21: Reinforcement Learning and Evaluating Hypotheses
Lecture 22: Learning Task, Q Learning
Lecture 23: Non-Deterministic Rewards and Actions
Session
Topic Sub-Topic CO Number Reference
Number
1. L21, RL, EH Q learning, Co4, Co5, T1: [Link].13
2. L22, [Link].266-281
Non-deterministic
3. L23 rewards and actions
Module #3 : Unsupervised Machine Learning 2
What is an Evaluating hypothesis?
Hypothesis evaluation refers to the comparison of learned models, as opposed to
the comparison of machine learning algorithms.
Machine learning algorithms can be trained on multiple samples of the same
problem or different problems.
Learning systems are usually designed to predict the class of ”future” unlabelled
data points.
Module #3 : Unsupervised Machine Learning 3
The process involves:
[Link] a null hypothesis (H₀): The default assumption that there is no effect or
difference.
[Link] an alternative hypothesis (H₁): The assumption that there is an effect or
difference.
[Link] a significance level (α), commonly set at 0.05.
[Link] an appropriate statistical test.
[Link] a test statistic and p-value.
[Link] a decision: Reject or fail to reject the null hypothesis.
Module #3 : Unsupervised Machine Learning 4
Module #3 : Unsupervised Machine Learning 5
• Your dog is an agent that is exposed to the environment.
• An example of a state could be your dog sitting, and you use a specific word in
for dog to walk.
• Our agent reacts by performing an action transition from one “state” to
another “state.”
• For example, your dog goes from sitting to walking.
• The reaction of an agent is an action, and the policy is a method of selecting
an action given a state in expectation of better outcomes.
• After the transition, they may get a reward or penalty in return.
Module #3 : Unsupervised Machine Learning 6
Stages of Reinforcement Learning
Module #3 : Unsupervised Machine Learning 7
Formulate Hypotheses:
Null Hypothesis (H0): No effect or difference. Think, “The new algorithm performs
the same as the old one.”
Alternative Hypothesis (H1):
There’s an effect or difference. For example, “The new algorithm performs better
than the old one.”
Module #3 : Unsupervised Machine Learning 8
Calculate Test Statistic and P-Value:
Test Statistic: A value derived from your sample data to test the hypotheses.
P-Value: The probability of observing your data if the null hypothesis is true. A small p-
value (≤ α) suggests the null hypothesis is unlikely.
Choose a Significance Level (α):
Typically set at 0.05, this is the probability of rejecting the null hypothesis when it’s
actually true (Type I error).
Module #3 : Unsupervised Machine Learning 9
Calculate Test Statistic and P-Value:
•Test Statistic: A value derived from your sample data to test the hypotheses.
•P-Value: The probability of observing your data if the null hypothesis is true. A
.
small p-value (≤ α) suggests the null hypothesis is unlikely.
Make a Decision:
•If the p-value is ≤ 0.05, reject the null hypothesis in favor of the alternative.
•If the p-value is > 0.05, fail to reject the null hypothesis.
Module #3 : Unsupervised Machine Learning 10
Practical Examples of Hypothesis Testing
Example 1: A/B Testing in Marketing
Scenario: A company wants to determine if changing the color of a call-to-action
button (from blue to red) increases conversions.
•H₀: There is no difference in conversion rates between the blue and red buttons.
•H₁: The red button has a higher conversion rate than the blue button.
•Test Used: Chi-Square Test or Two-Sample t-Test.
•Outcome: If p < 0.05, the company can reject H₀ and conclude that the red
button improves conversions.
Module #3 : Unsupervised Machine Learning 11
import numpy as np
from scipy import stats
# Conversion data: number of conversions out of total users
blue_button = [Link]([200, 1800]) # 200 conversions out of 2000
red_button = [Link]([250, 1750]) # 250 conversions out of 2000
# Perform a Chi-Square test
chi2, p = stats.chi2_contingency([blue_button, red_button])[:2]
print(f'Chi-Square Test: p-value = {p}')
if p < 0.05:
print("Red button significantly improves conversions!")
else:
print("No significant difference in conversions.")
Module #3 : Unsupervised Machine Learning 12
What is Q-Learning?
Q-learning is an off-policy, model-free TD learning algorithm that learns the value of
actions in different states.
It updates the action-value function (Q-function) based on experiences, helping the agent
make informed decisions.
Key Components of Q-Learning
1. Agent: The decision-maker interacting with the environment.
2. Environment: The external world responding to the agent’s actions.
3. State (S): The current situation or status.
Module #3 : Unsupervised Machine Learning 13
4. Action (A): The agent’s decision or move.
5. Reward (R): The immediate feedback or consequence.
6. Q-Function (Q(s, a)): Estimates the expected return for taking action A in
state S.
How Q-Learning Works
1. Initialization: Initialize Q-function with arbitrary values.
2. Experience Collection: Agent takes action A in state S, receives reward
R, and transitions to next state S’.
Module #3 : Unsupervised Machine Learning 14
3. Q-Function Update: Update Q-function using:
Q(s, a) ← Q(s, a) + α [R + γ max(Q(s’, a’)) — Q(s, a)]
where:
- α: learning rate
- γ: discount factor
- max(Q(s’, a’)): maximum Q-value for next state
4. Repeat: Steps 2–3 continue until convergence or stopping criterion.
Module #3 : Unsupervised Machine Learning 15
Module #3 : Unsupervised Machine Learning 16