Machine Learning (BCS02)

MODULE 3
SIMILARITY BASED LEARNING
• Similarity-based learning or Instance based learning is a type of machine learning where the
system makes decisions or predictions by comparing new data to previously seen examples
(instances). Instead of learning a complex formula or pattern, it simply looks at how "close" or
"similar" a new item is to known items and uses that information to make a decision.
• Let’s say you're training a model to recognize fruits (apples, bananas, and oranges). Here’s how
similarity-based learning would go:
o Store examples: The system remembers the shape, colour, and size of different fruits it has
seen.
o Get a new fruit: You give it a new fruit to identify.
o Compare: It measures how similar this fruit is to the examples it has stored.
o Decide: Based on which stored fruits are most similar, it decides what the new fruit probably
is.
• Algorithms based on similarity-based learning:
1. K- Nearest Neighbour
2. Variants of Nearest Neighbour Learning
3. Locally Weighted Regression
4. Learning Vector Quantization (LVQ)
5. Self-Organizing Map (SOM)
6. Radial Basis Function (RBF) Networks

1. Nearest Neighbour Learning

• Also called as k- Nearest Neighbour (k-NN)
• Predicts the label of a new data point by finding its closest neighbour in the k- samples of training
data.
• It works on basis of Measuring distance (like Euclidean Distance) between the new point and all
training points → pick the closest → use its label.
• It is memory based as it uses the training data only when the prediction is to be made.
• Pros: Simple, no training phase.
• Cons: Can be sensitive to noise or outliers.
• Consider the following example:

Circles represent class 0

Squares represent class 1
The black X is the new point to classify Dashed lines show
the 3 nearest neighbours

The model would classify the new point based on the majority
class of those 3 neighbours (k=3).

Department of CSE,CEC 1
 Machine Learning (BCS02)

• Euclidian Distance- is used to measure how close each training point is to the test point and the
closest neighbours are selected based on this metric.

Algorithm:

Inputs: Training dataset T, distance metric d, Test instance t, the number of nearest neighbours k
Output: Predicted class or category
Prediction: For test instance t,
1. For each instance i in T, compute the distance between the test instance t and every other instance i
in the training dataset using a distance metric (Euclidean distance).
[Continuous attributes – Euclidean distance between two points in the plane with
coordinates (x₁, y₁) and (x₂, y₂) is given as
dist((x₁, y₁), (x₂, y₂)) = √((𝐱₂ − 𝐱₁)² + (𝐲₂ − 𝐲₁)²) ]

[Categorical attributes (Binary) – Hamming Distance: If the value of the two is same, the
distance d will be equal to 0, otherwise d = 1.]

2. Sort the distances in ascending order and select the first k nearest training data instances to the test
instance.
3. Predict the class of the test instance by majority voting (if target attribute is discrete valued) or mean
(if target attribute is continuous valued) of the k selected nearest instances.
Problem 1. Consider the student performance training dataset of 8 data instances shown in Table
below which describes the performance of individual students in a course and their CGPA obtained
in the previous semesters. The independent attributes are CGPA, Assessment and Project. The target
variable is ‘Result’ which is a discrete valued variable that takes two values ‘Pass’ or ‘Fail’. Based
on the performance of a student, classify whether a student with CGPA 6.1, Assessment 40 and project
submission score 5 will pass or fail in that course. Apply KNN

[Link]. CGPA Assessment Project Submitted Result

1 9.2 85 8 Pass

2 8.0 80 7 Pass

3 8.5 81 8 Pass

4 6.0 45 5 Fail

5 6.5 50 4 Fail

6 8.2 72 7 Pass

7 5.8 38 5 Fail

8 8.9 91 9 Pass

Department of CSE,CEC 2
 Machine Learning (BCS02)

Solution:
Step 1: Calculate Euclidean Distance from the Test Instance Using the formula:
For 3 attributes (CGPA, Assessment, Project):
Distance = √[(𝐂𝐆𝐏𝐀ₜ − 𝐂𝐆𝐏𝐀ᵢ)² + (𝐀𝐬𝐬𝐞𝐬𝐬𝐦𝐞𝐧𝐭ₜ − 𝐀𝐬𝐬𝐞𝐬𝐬𝐦𝐞𝐧𝐭ᵢ)² + (𝐏𝐫𝐨𝐣𝐞𝐜𝐭ₜ − 𝐏𝐫𝐨𝐣𝐞𝐜𝐭ᵢ)²]

Project
[Link]. CGPA Assessment Result Euclidean Distance
Submitted

1 9.2 85 8 Pass √((9.2 − 6.1)² + (85 − 40)² + (8 − 5)²) = 45.2063

2 8.0 80 7 Pass √((8 − 6.1)² + (80 − 40)² + (7 − 5)²) = 40.09501

3 8.5 81 8 Pass √((8.5 − 6.1)² + (81 − 40)² + (8 − 5)²) = 41.17961

4 6.0 45 5 Fail √((6 − 6.1)² + (45 − 40)² + (5 − 5)²) = 5.001

5 6.5 50 4 Fail √((6.5 − 6.1)² + (50 − 40)² + (4 − 5)²) = 10.05783

6 8.2 72 7 Pass √((8.2 − 6.1)² + (72 − 40)² + (7 − 5)²) = 32.13114

7 5.8 38 5 Fail √((5.8 − 6.1)² + (38 − 40)² + (5 − 5)²) = 2.022375

8 8.9 91 9 Pass √((8.9 − 6.1)² + (91 − 40)² + (9 − 5)²) = 51.23319

Sort the distances in ascending order and select the first k nearest training data instances to the test instance.

Instance Euclidean Distance

7 2.022375

4 5.001

5 10.05783

6 32.13114

2 40.09501

3 41.17961

1 45.2063

8 51.23319

Department of CSE,CEC 3
 Machine Learning (BCS02)

Step 2: Select 3 Nearest Neighbors (smallest distances)

Instance Euclidean Distance Class

7 2.022375 Fail

4 5.001 Fail

5 10.05783 Fail

Step 3: Prediction by Majority Voting

All 3 nearest neighbours have the class "Fail", so: Predicted Result for (6.1, 40, 5) = Fail

2. Weighted k-Nearest Neighbour (Weighted k-NN) Algorithm

• Weighted k-NN is an enhanced version of the standard k-NN algorithm.
It addresses a limitation of regular k-NN: all k neighbours are treated equally, regardless of how close
they are to the test point.
• Closer neighbours to the test instance are more influential in prediction.
• Weights are assigned inversely proportional to the distance.
• This helps the algorithm give more importance to nearby data points, improving accuracy.

Algorithm
Inputs: Training dataset T, Distance metric d(i, t), Weighting function w(d), Test instance t, the number
of nearest neighbours k

Output: Predicted class or category

Prediction: For test instance t,

1. For each instance i in Training dataset T, compute the distance between the test instance t and every
other instance i using a distance metric (Euclidean distance).

[Continuous attributes – Euclidean distance between two points in the plane with
coordinates (x₁, y₁) and (x₂, y₂) is given as
dist((x₁, y₁), (x₂, y₂)) = √((𝐱₂ − 𝐱₁)² + (𝐲₂ − 𝐲₁)²) ]

[Categorical attributes (Binary) – Hamming Distance: If the values of two instances are the
same, the distance d will be equal to 0. Otherwise, d = 1.]

2. Sort the distances in the ascending order and select the first k nearest training data instances to the
test instance.
3. Predict the class of the test instance by weighted voting technique (Weighting function w(d)) for the
k selected nearest instances:

Department of CSE,CEC 4
 Machine Learning (BCS02)

o Compute the inverse of each distance of the k selected nearest instances.

o Find the sum of the inverses.
o Compute the weight by dividing each inverse distance by the sum. (Each weight is a vote for
its associated class.)
o Add the weights of the same class.
o Predict the class by choosing the class with the maximum vote.

Problem Consider the student performance training dataset of 8 data instances shown in Table below which
describes the performance of individual students in a course and their CGPA obtained in the previous
semesters. The independent attributes are CGPA, Assessment and Project. The target variable is ‘Result’
which is a discrete valued variable that takes two values ‘Pass’ or ‘Fail’. Based on the performance of a
student, classify whether a student with CGPA 6.1, Assessment 40 and project submission score 5 will pass
or fail in that course. Apply weighted KNN
[Link]. CGPA Assessment Project Submitted Result
1 9.2 85 8 Pass
2 8.0 80 7 Pass
3 8.5 81 8 Pass
4 6.0 45 5 Fail
5 6.5 50 4 Fail
6 8.2 72 7 Pass
7 5.8 38 5 Fail
8 8.9 91 9 Pass

Step 1: Calculate Euclidean Distance from the Test Instance Using the formula:
For 3 attributes (CGPA, Assessment, Project):
Distance = √[(𝐂𝐆𝐏𝐀ₜ − 𝐂𝐆𝐏𝐀ᵢ)² + (𝐀𝐬𝐬𝐞𝐬𝐬𝐦𝐞𝐧𝐭ₜ − 𝐀𝐬𝐬𝐞𝐬𝐬𝐦𝐞𝐧𝐭ᵢ)² + (𝐏𝐫𝐨𝐣𝐞𝐜𝐭ₜ − 𝐏𝐫𝐨𝐣𝐞𝐜𝐭ᵢ)²]

Project
[Link]. CGPA Assessment Result Euclidean Distance
Submitted
1 9.2 85 8 Pass √((9.2 − 6.1)² + (85 − 40)² + (8 − 5)²) = 45.2063
2 8.0 80 7 Pass √((8 − 6.1)² + (80 − 40)² + (7 − 5)²) = 40.09501
3 8.5 81 8 Pass √((8.5 − 6.1)² + (81 − 40)² + (8 − 5)²) = 41.17961
4 6.0 45 5 Fail √((6 − 6.1)² + (45 − 40)² + (5 − 5)²) = 5.001
5 6.5 50 4 Fail √((6.5 − 6.1)² + (50 − 40)² + (4 − 5)²) = 10.05783
6 8.2 72 7 Pass √((8.2 − 6.1)² + (72 − 40)² + (7 − 5)²) = 32.13114
7 5.8 38 5 Fail √((5.8 − 6.1)² + (38 − 40)² + (5 − 5)²) = 2.022375
8 8.9 91 9 Pass √((8.9 − 6.1)² + (91 − 40)² + (9 − 5)²) = 51.23319

Department of CSE,CEC 5
 Machine Learning (BCS02)

Sort the distances in ascending order and select the first k nearest training data instances to the test instance.
Instance Euclidean Distance
7 2.022375
4 5.001
5 10.05783
6 32.13114
2 40.09501
3 41.17961
1 45.2063
8 51.23319
Step 2: Select 3 Nearest Neighbors (smallest distances)
Instance Euclidean Distance Class
7 2.022375 Fail
4 5.001 Fail
5 10.05783 Fail

Step 3: Predict the class of the test instance by weighted voting technique from the 3 selected nearest
instances.

Table: Inverse Distance (1/ Euclidean Distance)

Instance Euclidean Distance Inverse Distance Class
7 2.02 0.495 Fail
4 5.00 0.200 Fail
5 10.05 0.0995 Fail

• Find the sum of Inverse:

Sum=0.495+0.200+0.0995=0.7945

• Compute the weight by dividing each inverse distance by the sum as shown in Table.
Instance Euclidean Distance Inverse Distance Weight =( Inverse / Sum ) Class
7 2.02 0.495 0.6229 Fail
4 5.00 0.200 0.2517 Fail
5 10.05 0.0995 0.1252 Fail
• Add the weights of the same classes:
Fail = 0.6229 + 0.2517 + 0.1252 = 1.000
Pass = 0
• Predict the class by choosing the class with the maximum vote.
The class is predicted as "Fail".

Department of CSE,CEC 6
 Machine Learning (BCS02)

Problem 2

A COVID care centre decided to develop a case-based reasoning system to predict whether a person will test
positive or negative based on the symptoms. The table below shows the number of possible symptoms and
the results of the previous cases. The training dataset contains the following instances as shown in the Table
4.13 below.

Table 4.13: Sample Set of Instances

Loss of
Dry Sore Shortness Chest
[Link]. Fever Tiredness Diarrhea Headache Taste or Result
Cough Throat of Breath Pain
Smell
1 Yes Yes Yes Yes Yes Yes Yes Yes Yes Positive
2 Yes No Yes No No Yes No No No Negative
3 No No No No No No No No No Negative
4 Yes Yes No No No No No No Yes Negative
5 Yes Yes Yes No No No No Yes Yes Positive
6 Yes Yes Yes No No Yes No No No Positive
7 Yes Yes Yes No No No No No No Positive
8 Yes Yes Yes No No No No No No Positive
9 Yes Yes Yes No No No No No No Positive
10 No No No No No No No No No Negative

• Determine k = number of nearest neighbors to get a better prediction result.

• Increase 'K' value and check the prediction. Is it good or bad to have a smaller or larger 'K' value?

• Apply proper similarity measure [Asymmetric binary features] and predict the test result of the instance
[Fever = Yes, Dry Cough = Yes, Tiredness = Yes, Sore Throat = Yes, Diarrhea = No, Headache = No,
Loss of Taste or Smell = No, Shortness of Breath = No, Chest Pain = No].

Solution

What is Asymmetric Binary Hamming Distance?

When we are dealing with binary features (Yes/No converted to 1/0), and presence (Yes) is more important
than absence (No), we use:

Asymmetric Binary Distance:

We only count mismatches where the test instance has 1 (Yes) and the training instance has 0 (No).
This is because a symptom present in the test case but absent in the training case is important.
The other way (training has Yes, test has No) is ignored.

Department of CSE,CEC 7
 Machine Learning (BCS02)

Test Instance (converted to binary)

Symptom Value
Fever 1
Dry Cough 1
Tiredness 1
Sore Throat 1
Diarrhea 0
Headache 0
Loss of Taste/Smell 0
Shortness of Breath 0
Chest Pain 0

Test Vector:
[1, 1, 1, 1, 0, 0, 0, 0, 0]

Step-by-step Hamming Distance Calculation

For each training row, we:
• Compare it with the test vector.
• Count where test = 1 and train = 0.

Row-by-row Distance Calculation

Row 1: [1, 1, 1, 1, 1, 1, 1, 1, 1]
Compare with test:
[1, 1, 1, 1, 0, 0, 0, 0, 0]
Only check where test has 1 → first 4 values.
Symptom Test Train Penalty?
Fever 1 1 No
Dry Cough 1 1 No
Tiredness 1 1 No
Sore Throat 1 1 No
Distance = 0
Result: Positive

Row 2: [1, 0, 1, 0, 0, 1, 0, 0, 0]
Symptom Test Train Penalty?
Fever 1 1 No
Dry Cough 1 0 Yes
Tiredness 1 1 No
Sore Throat 1 0 Yes
Distance = 2
Result: Negative
Row 3: [0, 0, 0, 0, 0, 0, 0, 0, 0]

Department of CSE,CEC 8
 Machine Learning (BCS02)

Symptom Test Train Penalty?

Fever 1 0 Yes
Dry Cough 1 0 Yes
Tiredness 1 0 Yes
Sore Throat 1 0 Yes
Distance = 4

Result: Negative
Row 4: [1, 1, 0, 0, 0, 0, 0, 0, 1]
Symptom Test Train Penalty?
Fever 1 1 No
Dry Cough 1 1 No
Tiredness 1 0 Yes
Sore Throat 1 0 Yes
Distance = 2
Result: Negative

Row 5: [1, 1, 1, 0, 0, 0, 0, 1, 1]
Symptom Test Train Penalty?
Fever 1 1 No
Dry Cough 1 1 No
Tiredness 1 1 No
Sore Throat 1 0 Yes
Distance = 1
Result: Positive

Row 6: [1, 1, 1, 0, 0, 1, 0, 0, 0]
Symptom Test Train Penalty?
Fever 1 1 No
Dry Cough 1 1 No
Tiredness 1 1 No
Sore Throat 1 0 Yes

Penalty only for Sore Throat → Distance = 1

Result: Positive

Department of CSE,CEC 9
 Machine Learning (BCS02)

Row 7, 8, 9: All have [1, 1, 1, 0, 0, 0, 0, 0, 0]

Symptom Test Train Penalty?
Fever 1 1 No
Dry Cough 1 1 No
Tiredness 1 1 No
Sore Throat 1 0 Yes

Only Sore Throat = mismatch → Distance = 1

Result: Positive

Row 10: [0, 0, 0, 0, 0, 0, 0, 0, 0]

Symptom Test Train Penalty?
Fever 1 0 Yes
Dry Cough 1 0 Yes
Tiredness 1 0 Yes
Sore Throat 1 0 Yes

All 1’s in test mismatch → Fever, Dry Cough, Tiredness, Sore Throat → 4 mismatches
Distance = 4
Result: Negative

Final Table:
Row Distance Result
1 0 Positive
2 2 Negative
3 4 Negative
4 2 Negative
5 1 Positive
6 1 Positive
7 1 Positive
8 1 Positive
9 1 Positive
10 4 Negative

1. Determine k = number of nearest neighbors to get a better prediction result.

Prediction using k = 3:
Top 3 Nearest Neighbors:
Row Distance Result
1 0 Positive
5 1 Positive
6 1 Positive

Department of CSE,CEC 10
 Machine Learning (BCS02)

Prediction = Positive

2. Increase 'K' value and check the prediction. Is it good or bad to have a smaller or larger 'K' value
Prediction using k = 5:
Top 5 Neighbors:
Row Distance Result
1 0 Positive
5 1 Positive
6 1 Positive
7 1 Positive
8 1 Positive
Prediction = Positive
The predicted result for the given test instance is: POSITIVE using both k = 3 and k = 5 with
asymmetric binary Hamming distance.

Department of CSE,CEC 11
 Machine Learning (BCS02)

3. Nearest Centroid Classifier

In Nearest Centroid Classifier, the distance between the centroid (average) of each class and the test
instance is calculated. The test instance is assigned to the class with the minimum distance.

Algorithm

Input: Training dataset with class labels

Output: Class label for the test instance
Step 1: Calculate the mean (centroid) of the attributes for each class
Step 2: Compute the distance between the test instance and centroid of each class
Step 3: Assign the class with the minimum distance to the test instance

Problem:
Consider the sample data shown in Table with two features x and y. The target classes are ‘A’ or ‘B’.
Predict the class using Nearest Centroid Classifier.

Table : Sample Data

X Y Class
3 1 A
5 2 A
4 3 A
7 6 B
6 7 B
8 5 B
Solution:

Step 1: Compute the mean/centroid of each class. In this example there are two classes called ‘A’
and ‘B’.
Centroid of class “A” = (3 + 5 + 4, 1 + 1 + 2)/3 = (12, 6)/3 = (4, 2)
Centroid of class “B” = (7 + 6 + 8, 6 + 7 + 5)/3 = (21, 18)/3 = (7, 6)
Now given a test instance (6, 5), we can predict the class.
Step 2: Calculate the Euclidean distance between test instance (6, 5) and each of the centroid.

Euc_Dist[(6,5),(4,2)] = √(𝟔 − 𝟒)𝟐 + (𝟓 − 𝟐)𝟐 = √13 = 3.6

Euc_Dist[(6,5),(7,6)] = √(𝟔 − 𝟕)𝟐 + (𝟓 − 𝟔)𝟐 = √2 =1.414

The test instance has smaller distance to class B. Hence, the class of this test instance is
predicted as ‘B’.

Department of CSE,CEC 12
 Machine Learning (BCS02)

4. Locally Weighted Regression (LWR)

• Locally Weighted Regression (LWR) is a non-parametric supervised learning algorithm.
• It makes predictions based on nearby data points, instead of using the whole dataset.
• It is also called as memory based method as it requires the training data to predict.
• Regular regression draws one big straight line through all the data. But real-life data often curves-
so one line doesn’t fit well.
• LWR draws many little lines in different places, depending on the test point. These lines combine
to form a smooth curve, giving more accurate predictions.
• When you want to make a prediction, LWR looks for the K closest data points (neighbours). It gives
more importance (weight) to points that are closer. It fits a tiny linear model just for that region and
uses that local model to make the prediction

• In simple linear regression, the goal is to find a straight line that best fits all the data points.
The prediction function is given as:
𝒉𝜷 (𝒙) = 𝜷𝟎 + 𝜷𝟏 (x)
ℎ𝛽 (𝑥) is predicted function/ hypothesis function
𝛽1 𝑖𝑠 𝑡ℎ𝑒 𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑜𝑓 𝑥
𝛽0 is the intercept
• (The intercept is where the line crosses or touches the Y-axis. It is the value of y when x = 0.)

• To find the best line, we minimize a cost function:

𝟏
J(β) = 𝟐 ∑𝒎
𝒊=𝟏(𝒉𝜷 (𝒙𝒊 ) − 𝒚𝒊 )
𝟐

m is no. of instances in the training set.

This minimises the error between predicted value ℎ𝛽 (𝑥) and true value y.

• In LWR, the cost function is changed/ modified so that closer points have more influence, and farther
points have less influence when making predictions. This is done using weights, and that's what
Equation below represents.
𝟏
J(β) = 𝟐 ∑𝒎
𝒊=𝟏 𝒘𝒊 (𝒉𝜷 (𝒙𝒊 ) − 𝒚𝒊 )
𝟐

𝑤𝑖 is the weight associated with each 𝑥𝑖

−(𝒙𝒊 −𝒙)𝟐
Gaussian kernel, 𝒘𝒊 = 𝒆 𝟐𝝉𝟐

τ is bandwidth parameter

Department of CSE,CEC 13
 Machine Learning (BCS02)

Meaning of each term:

Problem:

Consider a simple example with four instances shown in Table below and apply locally weighted
regression.

Table: Sample Table

S. No. Salary (in lakhs) Expenditure (in thousands)

1 5 25
2 1 5
3 2 7
4 1 8

Solution:

Using linear regression model assuming we have computed the parameters: β₀ = 4.72, β₁ = 0.62
Given a test instance with x = 2, the predicted y is:
𝒚𝒍 = 𝜷𝟎 + 𝜷𝟏 (x)

𝒚𝒍 = 4.72 +( 0.62 X 2) = 5.96

Let k=3 be closest neighbours/ instances

Department of CSE,CEC 14
 Machine Learning (BCS02)

Table: Euclidean Distance Calculation

S. No. x = Salary (in lakhs) y = Expenditure (in thousands) Euclidean Distance

1 5 25 √(5 − 2)2 = 3
2 1 5 √(1 − 2)2 = 1
3 2 7 √(2 − 2)2 = 0
4 1 8 √(1 − 2)2 = 1

Instances 2, 3 and 4 are closer with smaller distances.

The mean value = (5 + 7 + 8)/3 = 20/3 = 6.67.

compute the weights for the closest instances, using the Gaussian kernel,

−(𝒙𝒊 −𝒙)𝟐
𝒘𝒊 = 𝒆 𝟐𝝉𝟐

Hence the weights of the closest instances is computed as follows,

−(𝒙𝟐 −𝒙)𝟐 −(𝟏−𝟐)𝟐 −𝟏𝟐

Weight of Instance 2 is: 𝒘𝟐 = 𝒆 𝟐𝝉𝟐 = 𝒆 𝟐(𝟎.𝟒)𝟐 =𝒆 𝟐 = 0.043

−(𝒙𝟑 −𝒙)𝟐 −(𝟐−𝟐)𝟐

Weight of Instance 3 is: 𝒘𝟑 = 𝒆 𝟐𝝉𝟐 =𝒆 𝟐(𝟎.𝟒)𝟐 = 𝒆𝟎 = 𝟏 (higher weight because 𝑤3 is closer)

−(𝒙𝟒𝟑 −𝒙)𝟐 −(𝟏−𝟐)𝟐 −𝟏𝟐

Weight of Instance 4 is: 𝒘𝟒 = 𝒆 𝟐𝝉𝟐 =𝒆 𝟐(𝟎.𝟒)𝟐 =𝒆 𝟐 = 𝟎. 𝟎𝟒𝟑

The predicted output for the three closest instances is given as follows:

The predicted output of Instance 2 is: 𝒚𝟐 = 𝒉𝜷 (𝒙𝟐 ) = ( 𝜷𝟎 + 𝜷𝟏 (𝒙𝟐 ) )= 4.72 +( 0.62 X 1) = 5.34

The predicted output of Instance 3 is: 𝒚𝟑 = 𝒉𝜷 (𝒙𝟑 ) = (𝜷𝟎 + 𝜷𝟏 (𝒙𝟑 ) )= 4.72 +( 0.62 X 2) = 5.96

The predicted output of Instance 4 is: 𝒚𝟒 = 𝒉𝜷 (𝒙𝟒 ) = (𝜷𝟎 + 𝜷𝟏 (𝒙𝟒 )) = 4.72 +( 0.62 X 1) = 5.34

𝟏
The error value/ adjusted cost function is calculated as: J(β) = 𝟐 ∑𝒎
𝒊=𝟏 𝒘𝒊 (𝒉𝜷 (𝒙𝒊 ) − 𝒚𝒊 )
𝟐

𝟏
= 𝟐[0.043(𝟓. 𝟑𝟒 − 𝟓)𝟐 + 1(𝟓. 𝟗𝟔 − 𝟕)𝟐 + 0.043(𝟓. 𝟑𝟒 − 𝟖)𝟐

= 0.6953

Department of CSE,CEC 15
 Machine Learning (BCS02)

How to choose τ :

1. Manual testing: Try values like 0.1, 0.3, 0.5, 0.8, 1.0, 2.0, ... and see performance.
2. Cross-validation: Split your data, and test different τ\tauτ values to see which gives best
prediction accuracy.
3. Plot weights vs distance: Visually check how fast weights decay.
4. Grid search + error metric (e.g., RMSE): Automate the selection using a performance metric.

Example values to try:

Department of CSE,CEC 16
 Machine Learning (BCS02)

Regression Analysis
INTRODUCTION TO REGRESSION

Regression analysis is the premier method of supervised learning. This is one of the most popular and oldest
supervised learning techniques. Given a training dataset D containing N training points (xi,yi), where
i=1,...,N, regression analysis is used to model the relationship between one or more independent variables x
and a dependent variable y. The relationship between the dependent and the independent variables can be
represented as a function as follows:

y=f(x) …………………..(5.1)

The feature variable x is also known as an explanatory variable, exploratory variable, a predictor variable,
an independent variable, a covariate, or a domain point. y is a dependent variable. Dependent variables are
also called as labels, target variables, or response variables.

Regression analysis determines the change in response variables when one explanatory variable is varied
while keeping all other parameters constant. This is used to determine the relationship each of the exploratory
variables exhibits. Thus, regression analysis is used for prediction and forecasting.

Regression is used to predict continuous variables or quantitative variables such as price and revenue.
Thus, the primary concern of regression analysis is to find answers to questions such as:

1. What is the relationship between the dependent and independent variables?

2. What is the strength of the relationship?
3. What is the nature of the relationship such as linear or non-linear?
4. What is the contribution of each attribute?
5. What is the relevance of the attribute?

There are many applications of regression analysis. Some of the applications of regression include predicting:

1. Sales of a product or services

2. Value of bonds in portfolio management
3. Premium on insurance companies
4. Yield of crops in agriculture
5. Prices of real estate

Types of Regression

Department of CSE,CEC 17
 Machine Learning (BCS02)

1. Linear Regression
It is a type of regression where a line is fitted upon given data for finding the linear relationship
between one independent variable and one dependent variable to describe relationships.

2. Multiple Regression
It is a type of regression where a line is fitted for finding the linear relationship between two or more
independent variables and one dependent variable to describe relationships among variables.

3. Polynomial Regression
It is a type of non-linear regression method of describing relationships among variables where Nᵗʰ
degree polynomial is used to model the relationship between one independent variable and one
dependent variable. Polynomial multiple regression is used to model two or more independent
variables and one dependent variable.

4. Logistic Regression
It is used for predicting categorical variables that involve one or more independent variables and one
dependent variable. This is also known as a binary classifier.

5. Lasso and Ridge Regression Methods

These are special variants of regression methods where regularization methods are used to limit the
number and size of coefficients of the independent variables.

INTRODUCTION TO LINEAR REGRESSION

In the simplest form, the linear regression model can be created by fitting a line among the scattered data
points. The line is of the form given in Eq. (5.2).

y = a₀ + a₁x + e (5.2)

Here, a0 is the intercept which represents the bias and a1 represents the slope of the line. These are called
regression coefficients. e is the error in prediction.

The assumptions of linear regression are listed as follows:

1. The observations (y) are random and are mutually independent.

2. The difference between the predicted and true values is called an error. The error is also mutually
independent with the same distributions such as normal distribution with zero mean and constant
variables.
3. The distribution of the error term is independent of the joint distribution of explanatory variables.
4. The unknown parameters of the regression models are constants.

The idea of linear regression is based on Ordinary Least Square (OLS) approach. This method is also known
as ordinary least squares method. In this method, the data points are modelled using a straight line. Any
arbitrarily drawn line is not an optimal line. In Figure 5.4, three data points and their errors (e1,e2,e3)are
shown. The vertical distance between each point and the line (predicted by the approximate line equation
y=a0+a1x) is called an error. These individual errors are added to compute the total error of the predicted
line. This is called sum of residuals. The squares of the individual errors can also be computed and added
to give a sum of squared error. The line with the lowest sum of squared error is called line of best fit.

Department of CSE,CEC 18
 Machine Learning (BCS02)

Figure 5.4: Data Points and their Errors

In another words, OLS is an optimization technique where the difference between the data points and the
line is optimized.

Mathematically, based on Eq. (5.2), the line equations for points (x1,x2,...,xn)) are:

y₁ = a₀ + a₁x₁ + e₁

y₂ = a₀ + a₁x₂ + e₂

yₙ = a₀ + a₁xₙ + eₙ (5.3)

In general, the error is given as:

eᵢ = yᵢ - (a₀ + a₁xᵢ) (5.4)

Here, the terms (e1,e2,...,en) are error associated with the data points and denote the difference between the
true value of the observation and the point on the line. This is also called as residuals. The residuals can be
positive, negative or zero.

A regression line is the line of best fit for which the sum of the squares of residuals is minimum. The
minimization can be done as minimization of individual errors by finding the parameters a0 and a1such that:

Or as the minimization of sum of absolute values of the individual errors:

Or as the minimization of the sum of the squares of the individual errors:

Department of CSE,CEC 19
 Machine Learning (BCS02)

Sum of the squares of the individual errors, often preferred as individual errors (positive and negative errors),
do not get cancelled out and are always positive, and sum of squares results in a large increase even for a
small change in the error. Therefore, this is preferred for linear regression.

Therefore, linear regression is modelled as a minimization function as follows:

Here, J(a1,a0) is the criterion function of parameters a0 and a1. This needs to be minimized. This is done
by differentiating and substituting to zero. This yields the coefficient values of a0 and a1. The values of
estimates of a0 and a1 are given as follows:

And the value of a0 is given as follows:

Example 5.1

Let us consider an example where the five weeks' sales data (in Thousands) is given as shown below in
Table 5.1. Apply linear regression technique to predict the 7ᵗʰ and 12ᵗʰ month sales.

Table 5.1: Sample Data

𝑥ᵢ (Week) 𝑦ᵢ (Sales in Thousands)

1 1.2
2 1.8
3 2.6
4 3.2
5 3.8

Solution:

Here, there are 5 items, i.e., 𝑖 = 1, 2, 3, 4, 5. The computation table is shown below (Table 5.2). Here, there
are five samples, so 𝑖 ranges from 1 to 5.

Department of CSE,CEC 20
 Machine Learning (BCS02)

Table 5.2: Computation Table

𝑥ᵢ 𝑦ᵢ (𝑥ᵢ)² 𝑥ᵢ × 𝑦ᵢ
1 1.2 1 1.2
2 1.8 4 3.6
3 2.6 9 7.8
4 3.2 16 12.8
5 3.8 25 19.0
Sum=15 Sum=12.6 Sum=55 Sum=44.4
Average of xi Average of yi. Average of xᵢ²: Average of xi×yi
xˉ=15/5=3 yˉ=12.6/5=2.52 xi2ˉ=55/5=11 xy‾=44.4/5=8.88

Computation of Slope and Intercept using Eq. (5.9) (5.10):

Let us model the relationship using Regression Equation:

y=a0+a1x
y = 0.54 + 0.66x

Predicted Sales:
• 7ᵗʰ week (x = 7):
y = 0.54 + 0.66 × 7 = 5.16

• 12ᵗʰ week (x = 12):

y = 0.54 + 0.66 × 12 = 8.46

Construction of linear regression model.

Regression Equation (fitted line):

y = 0.54 + 0.66x
Now let’s compute predicted values y for each x:

x Actual y Predicted ȳ = 0.54 + 0.66x

1 1.2 0.66(1)+0.54=1.200.66(1) + 0.54 = 1.20
2 1.8 0.66(2)+0.54=1.860.66(2) + 0.54 = 1.86
3 2.6 0.66(3)+0.54=2.520.66(3) + 0.54 = 2.52
4 3.2 0.66(4)+0.54=3.180.66(4) + 0.54 = 3.18
5 3.8 0.66(5)+0.54=3.840.66(5) + 0.54 = 3.84

Department of CSE,CEC 21
 Machine Learning (BCS02)

The plot includes both actual and predicted values:

• Actual values (xi,yi) : These are shown as individual data points (like dots or squares) on the
graph.
• Predicted values (xi, ȳ) : These are calculated using the regression equation ȳ = 0.54 + 0.66x, and
the line connecting these points is the regression line.

The above graph shows a fitted line. The line almost passes through or very close to the actual points —
because the data is highly linear, and the regression model captures that relationship accurately.

Linear Regression in Matrix Form

In linear regression, matrix notation is a compact and efficient way to represent the regression equation
involving multiple data points. Instead of writing out separate equations for each observation, we can express
the entire system of equations in a single matrix form.
This is particularly useful for computation and implementation using programming or statistical software.
The simple linear regression model

y₁ = a₀ + a₁x₁ + e₁

y₂ = a₀ + a₁x₂ + e₂

yₙ = a₀ + a₁xₙ + eₙ (5.3)

can be written in matrix form as:

This can be written as:

Y=Xa+e

Department of CSE,CEC 22
 Machine Learning (BCS02)

where:
• X is an n×2 matrix,
• Y is an n×1 vector,
• a is a 2×1 column vector, and
• e is an n×1 column vector.

Example

Find the linear regression of the data of week and product sales (in Thousands) using the matrix form of
linear regression.

(Table 5.3)

x₁ (Week) y₁ (Product Sales in Thousands)

1 1
2 3
3 4
4 8

Step 1: Represent data in matrix form

Step 2: Apply the Regression Equation

The matrix formula for linear regression is:

Department of CSE,CEC 23
 Machine Learning (BCS02)

Step-by-Step Computation
1. Compute XTX :

2. Compute (XTX)-1: (Finding inverse of a Matrix)

Note : steps to find inverse of a matrix

3. Compute (XTX)-1 XT :

4. Multiply with Y:

• So, the intercept is –1.5 and the slope is 2.2. (The first value in the result vector (-1.5) is the
intercept — denoted as [Link] second value (2.2) is the slope — denoted as a1.)

Department of CSE,CEC 24
 Machine Learning (BCS02)

MULTIPLE LINEAR REGRESSION

Multiple Linear Regression is an extension of simple linear regression. It models the relationship between
one dependent variable and two or more independent (predictor) variables. The basic assumptions of
Multiple Linear Regressions are
1. Independent variables are not highly correlated (i.e., no multicollinearity).
2. The residuals (errors) are normally distributed.
Example with Two Predictors:

When there are two independent variables x1 and x2, the regression model is:

𝑦 = 𝑓(𝑥_1, 𝑥_2) = 𝑎_0 + 𝑎_1 𝑥_1 + 𝑎_2 𝑥_2 {5.21}

• y: dependent variable (output)

• x1,x2: independent variables (inputs/predictors)
• a0: intercept
• a1,a2: regression coefficients

General Form with n Predictors:

𝒚 = 𝒇(𝒙₁, 𝒙₂, . . . , 𝒙ₙ) = 𝒂₀ + 𝒂₁𝒙₁ + 𝒂₂𝒙₂ + . . . + 𝒂ₙ𝒙ₙ + 𝜺 (𝟓. 𝟐𝟐)

• x1,x2,…,xn : independent variables

• y: dependent variable
• a0,a1,…,an: coefficients showing the effect of each x on y.
• ε : error term, representing the unexplained variation in y

Example

Apply multiple regression for the values given in Table 5.7, where weekly sales y are provided along with
sales of products x1 and x2. Use the matrix approach to find the regression equation.

x1 x2 Y
Product one sales Product one sales Output weekly sales(in thousands)
1 4 1
2 5 6
3 8 8
4 2 12
Step 1: General Formula
The matrix formula for multiple regression is:

𝐴 = (𝑋ᵗ𝑋)⁻¹ 𝑋ᵗ𝑌

Where:

• X is the matrix of independent variables (with a column of ones for the intercept),
• Y is the column vector of dependent variables,
• A is the column vector of regression coefficients:

Department of CSE,CEC 25
 Machine Learning (BCS02)

Step 2: Construct Matrices

Note : The first column of 1s allows the equation to include an intercept a0. Without it, the model would
force the regression line to pass through the origin (0,0) — which is usually not what we want.

Step 3.1: Compute A= XTX

Step 3.2: Compute A= XTY

Step 3.3: Compute inverse of XTX (Use calculator)

Step 3.4: Multiply to Find A

Final Regression Equation

𝒚 = −𝟏. 𝟔𝟗𝟗𝟓 + 𝟑. 𝟒𝟖𝟑𝟔𝒙_𝟏 − 𝟎. 𝟎𝟓𝟒𝟔𝒙_𝟐

Department of CSE,CEC 26
 Machine Learning (BCS02)

POLYNOMIAL REGRESSION
In many practical situations, the relationship between the independent and dependent variables is not linear.
If a linear regression model is applied to such data, it may result in large prediction errors. To handle this
issue, there are two commonly used approaches to deal with non-linear regression problems:
1. Transforming the non-linear data into linear form, allowing the use of linear regression.
2. Using polynomial regression, which can directly model non-linear relationships.
1. Transformations
The transformation method is based on converting a non-linear relationship into a linear one. Once the data
has been transformed into a linear form, standard linear regression techniques can be applied.
Let us consider an exponential function where y is expressed as y = aeᵇˣ. To convert this into a linear form,
we take the natural logarithm of both sides:
ln y = bx + ln a (5.24)
The resulting equation is now linear in terms of ln y and x. This transformed data can now be analyzed using
linear regression.
Another common non-linear function is the power function y = axᵇ. To linearize this relationship, we apply
the base-10 logarithm to both sides of the equation:
log₁₀y = b log₁₀x + log₁₀a (5.25)
Again, this transformation produces a linear relationship between log₁₀y and log₁₀x, allowing for the use of
linear regression techniques.
After the linear regression is applied to the transformed data and the coefficients are estimated, the original
non-linear model can be retrieved by applying the inverse of the transformation.
2. Polynomial Regression
Polynomial regression is a method that models the relationship between variables as an n-th degree
polynomial. This approach does not require any transformation and is well suited to handle curvilinear
relationships directly.
For example, quadratic regression (second-degree polynomial) models the data using a function of the form:
y = a₀ + a₁x + a₂x²
Cubic regression (third-degree polynomial) uses a function of the form:
y = a₀ + a₁x + a₂x² + a₃x³
In general, polynomial regression of degree up to 4 is used, as higher-degree polynomials may result in
overfitting, which reduces the model's ability to generalize to new data.
Let us now consider fitting a second-degree polynomial to a given set of data points (x₁, y₁), (x₂, y₂), ..., (xₙ,
yₙ). The polynomial model is given by:

Department of CSE,CEC 27
 Machine Learning (BCS02)

y = a₀ + a₁x + a₂x² (5.26)

To find the best-fit polynomial, we minimize the sum of squared errors (E) between the observed values yᵢ
and the predicted values from the polynomial model. The error function is defined as:

To determine the optimal coefficients a₀, a₁, and a₂ that minimize the error E, we take the partial derivatives
of E with respect to each coefficient and set them equal to zero:
∂E/∂a₀ = 0, ∂E/∂a₁ = 0, ∂E/∂a₂ = 0
This process leads to a system of linear equations known as the normal equations. These equations are:

These equations can be expressed in matrix form for convenience. The matrix form of the system is:

This matrix equation is of the form Xa = B, where X is the matrix of input features, a is the vector of
unknown coefficients, and B is the vector of known outcomes. To solve for the coefficient vector a, we use
the inverse of matrix X as follows:
a = X⁻¹B (5.29)

Example Consider the data provided in Table and fit it using the second-order polynomial.

x y
1 1
2 4
3 9
4 15

Department of CSE,CEC 28
 Machine Learning (BCS02)

Solution:

To apply polynomial regression of order 2, computations are carried out as shown in Table .

Computation Table

xᵢ yᵢ xᵢ·yᵢ xᵢ² xᵢ²·yᵢ xᵢ³ xᵢ⁴

1 1 1 1 1 1 1
2 4 8 4 16 8 16
3 9 27 9 81 27 81
4 15 60 16 240 64 256
Σ 29 96 30 338 100 354

From the table:

• N=4, ∑xi=10, ∑yi=29 , ∑xiyi=96, ∑xi2=30, ∑xi3=100, ∑xi4=354, ∑xi2yi=338\

Step 1: Set Up the Matrix Equation

Step 2: Solve

This gives the coefficients: a₀ = -0.75, a₁ = 0.95, a₂ = 0.75

Final Regression Equation: y = -0.75 + 0.95x + 0.75x²

LOGISTIC REGRESSION
Linear regression is used to predict numerical responses, but it is not suitable for categorical variables. When
dealing with categorical variables, the problem is known as a classification problem. Logistic regression is
suitable for binary classification (i.e., two possible outcomes).

Department of CSE,CEC 29
 Machine Learning (BCS02)

• Examples of binary classification:

1. Spam detection: Is the mail spam or not spam? (Yes or No)
2. Student admission: Should a student be admitted based on exam marks? (Admit or Not Admit)
3. Pass/Fail prediction: Predicting pass or fail based on marks.

Logistic regression works by predicting the probability of a categorical variable. It uses one or more features
x to predict the response y. If linear regression is used to predict probability:
p(x) = a₀ + a₁x
But the value of p(x) must lie between 0 and 1, unlike linear regression which gives a range from -∞ to +∞.

Sigmoid Function:
To map values between 0 and 1, the sigmoid function is used:

Where x is the independent variable, and e is Euler's number.

Odds and Log-Odds:

Odds are defined as the ratio of the probability of an event to the probability of the event not happening:

Taking the log of odds gives the logit function:

Solving for p(x):

Prediction Rule (Threshold Function):

Based on the predicted probability p(x), the final binary output y is given by:

y = { 1 if p(x) ≥ 0.5,
0 otherwise } (5.36)
Where:
x: predictor variable
e: Euler number
a₀, a₁: regression coefficients (learned during training)

Department of CSE,CEC 30
 Machine Learning (BCS02)

Example
Let us assume a binary logistic regression problem with two classes: pass and fail. The student dataset
includes entrance exam marks. Based on past data, the model is trained to predict selection.
Given: Regression coefficients are a₀ = 1 and a₁ = 8. If a student has marks x = 60, compute the probability
of selection and determine the class.
Step 1: Compute z using regression coefficients:
z = a₀ + a₁x
= 1 + 8 × 60 = 481

Step 2: Use sigmoid function from Eq. (5.30):

Since the threshold is 0.5 and 0.44 < 0.5, the student is not selected.

Parameter Estimation using MLE

To find the relationship between dependent and independent variables, logistic regression uses Maximum
Likelihood Estimation (MLE). MLE finds the best parameters (a₀, a₁, ...) by maximizing the probability of
the observed data.
If π is the probability of success and (1 - π) is the probability of failure, the likelihood function is:

To estimate the parameters, we take the log of the likelihood function and use methods like Newton’s method
to maximize it.

Multinomial Logistic Regression

Logistic regression is mainly used for binary classification. For more than two classes, we use multinomial
logistic regression. If there are 3 classes (say class 1, class 2, and class 3), we form 3 binary classification
problems:
1. Class 1 vs Not Class 1
2. Class 2 vs Not Class 2
3. Class 3 vs Not Class 3
The model selects the class with the highest predicted probability.
Advantages and Disadvantages
Advantages:
- Simple and efficient for binary classification
- Easy to interpret results
Disadvantages:
- Cannot handle many attributes or nonlinear relationships
- Struggles with multicollinearity among variables

Department of CSE,CEC 31
 Machine Learning (BCS02)

DECISION TREE LEARNING

INTRODUCTION TO DECISION TREE LEARNING MODEL

The decision tree learning model is a popular supervised predictive learning model used for classification
tasks. It classifies data instances with high accuracy and consistency. It performs inductive inference,
meaning it draws general conclusions from observed examples. The model is widely used for complex
classification problems. A decision tree summarizes information from the training dataset in a tree
structure. Once this model is built, it can easily classify test data.

Decision trees can handle both categorical and continuous-valued target variables. Given a training dataset
X, it computes a hypothesis function f(X) in the form of a decision tree. Inputs to the model are objects or
data instances with features, which can be either discrete or continuous. The model outputs a tree that predicts
the class of the test data. In statistics, these features are called independent variables, while the target class
is called the response variable.

The model generates a complete hypothesis space using the training dataset. This allows searching through
different hypotheses by traversing the tree. Smaller trees represent specific hypotheses during this process.
This search bias is known as preference bias.

Structure of a Decision Tree

A decision tree has a structure that includes a root node, internal nodes (also called decision nodes),
branches, and leaf nodes (also called terminal nodes). The root node is the topmost node. Internal nodes
are test points based on input attributes, and the branches represent the outcomes of these tests. Each decision
node leads to branches that represent sub-sections of the tree. Each branch ends at a leaf node that gives the
final classification output.

Leaf nodes contain class labels which are the final outcomes of the decision paths. Every path from the root
to a leaf represents a logical rule formed by a combination of test conditions. The full tree forms a set of
classification rules in logical form.

Decision trees can also be extended into decision networks or influence diagrams, which have a directed
graph structure. These are based on Bayesian belief networks and represent node states, actions, outcomes,
and utilities. Symbols used in decision trees include circles for root nodes, diamonds for decision nodes,
and rectangles for leaf nodes.

Department of CSE,CEC 32
 Machine Learning (BCS02)

A decision tree consists of two major procedures:

Building the Tree

The goal of this step is to create a decision tree using the training data. The tree is built from the top (root
node) and grows downwards. At each level, the best attribute is chosen to split the data. This process repeats
until we reach the last level or a leaf node that can’t be split anymore. The tree is finished when all paths
lead to leaf nodes that show the final class or result. The result of this step is a decision tree that shows all
possible outcomes.
Knowledge Inference or Classification
The goal here is to find out which class a test example belongs to using the built decision tree. To do this,
we start from the root and check the conditions at each node. Based on the test result, we move to the next
branch. This continues until we reach a leaf node, which gives us the final class label for that test example.

Advantages of Decision Trees

1. Easy to model and interpret
2. Simple to understand
3. The input and output attributes can be discrete or continuous predictor variables
4. Can model a high degree of nonlinearity in the relationship between the target variables and the
predictor variables
5. Quick to train

Disadvantages of Decision Trees

Some of the issues that generally arise with a decision tree learning are that:
1. It is difficult to determine how deeply a decision tree can be grown or when to stop growing it.
2. If training data has errors or missing attribute values, then the decision tree constructed may
become unstable or biased.
3. If the training data has continuous valued attributes, handling it is computationally complex and has
to be discretized.
4. A complex decision tree may also be over-fitting with the training data.
5. Decision tree learning is not well suited for classifying multiple output classes.
6. Learning an optimal decision tree is also known to be NP-complete.

Example1
How to draw a decision tree to predict a student’s academic performance based on the given information
such as class attendance, class assignments, home-work assignments, tests, participation in
competitions or other events, group activities such as projects and presentations, etc.

Step 1: Identify Target Feature and Attributes

• Target (Response) variable:

o Exam Result → Pass or Fail

• Input (Independent) attributes:

Taken from Table, these are:

Department of CSE,CEC 33
 Machine Learning (BCS02)

Attribute Possible Values

Class attendance Good, Average, Poor
Class assignments Good, Moderate, Poor
Home-work assignments Yes, No
Assessment Good, Moderate, Poor
Participation in competitions/other events Yes, No
Group activities (projects/presentations) Yes, No

Step 2: Use Attributes as Decision Nodes

We form decision nodes using if-else conditions that check the value of each attribute. Each node splits the
dataset based on attribute values.
For example:
• If Class attendance = Good, we might proceed one way.
• If Class attendance = Poor, we might go down a different path in the tree.
This is done recursively for the remaining attributes until we reach a leaf node, which will be either Pass or
Fail.

Step 3: Build the Tree Structure (Conceptual Layout)

Here’s a simplified conceptual breakdown:
Class Attendance?
├── Good
│ └── Class Assignments?
│ ├── Good → Homework Assignments?
│ │ ├── Yes → Assessment? → ... (until Pass/Fail)
│ │ └── No → ... (continue decision path)
│ └── Moderate → ... (continue)
├── Average → ...
└── Poor → May directly lead to Fail (depending on other values)
Every decision node checks an attribute. Each branch corresponds to a value of that attribute. The tree keeps
branching until it reaches a decision (leaf) node — either Pass or Fail.

Step 4: Interpret Leaf Nodes

The leaf nodes represent the final outcome — Pass or Fail — based on the path taken through the tree.
Each path represents a set of conditions that, when satisfied, lead to a final decision.
For instance:
• If a student has:
o Good class attendance
o Good assignments
o Yes, to homework
o Good assessment
o Participated in events
o Yes, to group activities
→ then the student might be classified as Pass.
Whereas a student with:
• Poor attendance
• Poor assignments
• No homework
→ might be classified as Fail.

Department of CSE,CEC 34
 Machine Learning (BCS02)

The decision tree is constructed by following a series of if-else conditions based on all or some of the
attributes. The tree allows for non-binary splits (e.g., Good/Average/Poor), meaning it's not always a
binary tree.
A decision tree is not always a binary tree. It is a tree which can have more than two branches.

Example 2:

Predict a student’s academic performance of whether they will pass or fail based on the given information
such as ‘Assessment’ and ‘Assignment’. The independent variables are Assessment and Assignment, and
the target variable is Exam Result with values Pass and Fail.

Attributes Values
Assessment ≥50, <50
Assignment Yes, No
Exam Result Pass, Fail

Step 1: Identify Attributes and Target Variable

• Attributes (Features):
o Assessment (≥50, <50)
o Assignment (Yes, No)
• Target Variable:
o Exam Result (Pass, Fail)
Step 2: Choose the Root Node
• The decision tree starts with Assessment as the root node.
o If Assessment ≥ 50, then the result is Pass.
o If Assessment < 50, then we move to another decision node: Assignment.

Step 3: Add Second-Level Decision Node (if needed)

• At the second level, if Assessment < 50, we now check Assignment:
o If Assignment = Yes, then the result is Pass.
o If Assignment = No, then the result is Fail.
Final Decision Tree Rules:
1. If Assessment ≥ 50 → Pass
2. If Assessment < 50 and Assignment = Yes → Pass
3. If Assessment < 50 and Assignment = No → Fail

Department of CSE,CEC 35
 Machine Learning (BCS02)

Fundamentals of Entropy
• When building a decision tree, the goal is to choose the attribute that best separates the data based
on the target class (label).
• The best attribute for splitting is the one that provides the most information about the classification
outcome.
• This splitting continues until the stopping condition is met. At each step, we want the data subsets
to be as pure as possible.

What is Entropy?
• Entropy is a measure of randomness or uncertainty in data.
• It helps decide which feature gives the best split.
• A lower entropy means higher purity (i.e., data is more similar), and a higher entropy means more
uncertainty.

Examples to Understand Entropy

• If all data belongs to the same class (say all are ‘Pass’), entropy = 0 → complete certainty.
• If the data is equally split (e.g., 50% Pass and 50% Fail), entropy = 1 → maximum uncertainty.
• For instance, if out of 10 students, 6 passed and 4 failed, entropy is calculated as:

This gives a value between 0 and 1. A value closer to 0 is preferred because it means a clearer classification.

General Formula
• Let P be the probability distribution of outcomes (classes).
• If there are n possible classes, then:

• The entropy of this distribution is given by:

• If we consider a case with 6 Pass and 4 Fail students (i.e., P1=0.6 = 0.6, P2=0.4):

Mathematical Expression of Entropy

Entropy can also be written as:

Department of CSE,CEC 36
 Machine Learning (BCS02)

• Here, Pr[X = x] is the probability of an outcome x, and this form shows that lower probabilities
give higher entropy.
Note:

Algorithm : General Algorithm for Decision Trees

1. Find the best attribute from the training dataset using an attribute selection measure and place it at
the root of the tree.
2. Split the training dataset into subsets based on the outcomes of the test attribute, and each subset
in a branch contains the data instances or tuples with the same value for the selected test attribute.
3. Repeat Step 1 and Step 2 on each subset until we end up in leaf nodes in all the branches of the
tree.
4. This splitting process is recursive until the stopping criterion is reached.

Stopping Criteria
The following are some of the common stopping conditions:
1. The data instances are homogeneous, which means all belong to the same class Ci, and hence its
entropy is 0.
2. A node with some defined minimum number of data instances becomes a leaf.
(The number of data instances in a node is between 0.25% and 1.00% of the full training dataset).
3. The maximum tree depth is reached, so further splitting is not done and the node becomes a leaf
node.

DECISION TREE INDUCTION ALGORITHMS

There are many decision tree algorithms, such as ID3, C4.5, CART, CHAID, QUEST, GUIDE, CRUISE,
and CTREE, that are used for classification in a real-time environment. The most commonly used decision
tree algorithms are ID3 (Iterative Dichotomizer 3), developed by J.R. Quinlan in 1986, and C4.5, an
advancement of ID3 presented by the same author in 1993. CART, which stands for Classification and
Regression Trees, is another algorithm developed by Breiman et al. in 1984.
The accuracy of the tree constructed depends upon the selection of the best split attribute. Different
algorithms are used for building decision trees that use different measures to decide on the splitting criterion.
Algorithms such as ID3, C4.5, and CART are popular algorithms used in the construction of decision trees.
The algorithm ID3 uses ‘Information Gain’ as the splitting criterion, whereas the algorithm C4.5 uses
‘Gain Ratio’ as the splitting criterion. The CART algorithm is popularly used for classifying both
categorical and continuous-valued target variables. CART uses the GINI Index to construct a decision tree.
Decision trees constructed using ID3 and C4.5 are also called univariate decision trees, which consider
only one feature/attribute to split at each decision node. On the other hand, decision trees constructed using
the CART algorithm are multivariate decision trees, which consider a conjunction of univariate splits.

Department of CSE,CEC 37
 Machine Learning (BCS02)

ID3 Tree Construction

• ID3 is a supervised learning algorithm which uses a training dataset with labels and constructs a
decision tree. ID3 is an example of univariate decision trees as it considers only one feature at
each decision node. This leads to axis-aligned splits.
• The tree is then used to classify future test instances. It constructs the tree using a greedy approach
in a top-down fashion by identifying the best attribute at each level of the tree.
• ID3 works well if the attributes or features are considered as discrete/categorical values. If some
attributes are continuous, then they must be partitioned to be discretized or converted into nominal
attributes or features.
• The algorithm builds the tree using a purity measure called ‘Information Gain’ with the given
training data instances and then uses the constructed tree to classify the test data. It is applied to
training sets with only nominal attributes and with no missing values for classification.
• ID3 works well for large datasets. If the dataset is small, overfitting may occur. Moreover, it is not
accurate if the dataset has missing attribute values.
• No pruning is done during or after construction of the tree, and ID3 is prone to outliers. C4.5 and
CART can handle both categorical and continuous attributes. Both C4.5 and CART can also
handle missing values, but C4.5 is prone to outliers, whereas CART can handle outliers as well.

Definitions
• Let T be the training dataset.
• Let A be the set of attributes:
A={A1,A2,A3,…,An}
• Let m be the number of classes in the training dataset.
• Let Pi be the probability that a data instance or tuple 'd' belongs to class Ci.
It is calculated as:

Entropy and Information Gain

The expected information or entropy needed to classify a data instance 'd' in T is denoted as Entropy
Info(T):

The entropy of an attribute A is denoted as Entropy_Info(T, A) and calculated as:

Department of CSE,CEC 38
 Machine Learning (BCS02)

Where:
• Attribute A has v distinct values {a1,a2,...,aj}
• ∣Ai∣: Number of instances for distinct value i in attribute A
• Entropy_Info(Ai): Entropy for the i-th subset of instances

Information Gain
• Information_Gain(A) measures how much information is gained by branching on attribute A.
• It reflects the reduction in impurity after the split.

It is computed as:

As entropy increases, information gain decreases.

They are inversely proportional.

Algorithm : Procedure to Construct a Decision Tree using ID3

1. Compute Entropy_Info Eq. (6.8) for the whole training dataset based on the target attribute.
2. Compute Entropy_Info Eq. (6.9) and Information_Gain Eq. (6.10) for each of the attributes in
the training dataset.
3. Choose the attribute for which entropy is minimum and therefore the gain is maximum as the best
split attribute.
4. The best split attribute is placed as the root node.
5. The root node is branched into subtrees with each subtree as an outcome of the test condition of the
root node attribute. Accordingly, the training dataset is also split into subsets.
6. Recursively apply the same operation for the subset of the training set with the remaining attributes
until a leaf node is derived or no more training instances are available in the subset.

Note: We stop branching a node if entropy is 0.

The best split attribute at every iteration is the attribute with the highest information gain.

Example
Assess a student’s performance during his course of study and predict whether a student will get a job offer
or not in his final year of the course. The training dataset T consists of 10 data instances with attributes such
as ‘CGPA’, ‘Interactiveness’, ‘Practical Knowledge’ and ‘Communication Skills’ as shown in Table .
The target class attribute is the ‘Job Offer’.
Table 6.3: Training Dataset T
[Link]. CGPA Interactiveness Practical Knowledge Communication Skills Job Offer
1 ≥9 Yes Very good Good Yes
2 ≥8 No Good Moderate Yes
3 ≥9 No Average Poor No
4 <8 No Average Good No
5 ≥8 Yes Good Moderate Yes
6 ≥9 Yes Good Moderate Yes
7 <8 Yes Good Poor No
8 ≥9 No Very good Good Yes
9 ≥8 Yes Good Good Yes
10 ≥8 Yes Average Good Yes

Department of CSE,CEC 39
 Machine Learning (BCS02)

Solution :

Department of CSE,CEC 40
 Machine Learning (BCS02)

Department of CSE,CEC 41
 Machine Learning (BCS02)

Department of CSE,CEC 42
 Machine Learning (BCS02)

Department of CSE,CEC 43
 Machine Learning (BCS02)

C4.5 Construction
C4.5 is an improvement over ID3. C4.5 works with continuous and discrete attributes and missing values,
and it also supports post-pruning. C5.0 is the successor of C4.5 and is more efficient and used for building
smaller decision trees. C4.5 works with missing values by marking as ‘?’, but these missing attribute values
are not considered in the calculations.
The algorithm C4.5 is based on Occam’s Razor which says that given two correct solutions, the simpler
solution has to be chosen. Moreover, the algorithm requires a larger training set for better accuracy. It uses
Gain Ratio as a measure during the construction of decision trees. ID3 is more biased towards attributes with
larger values. For example, if there is an attribute called ‘Register No’ for students it would be unique for
every student and will have distinct value for every data instance resulting in more values for the attribute.
Hence, every instance belongs to a category and would have higher Information Gain than other attributes.
To overcome this bias issue, C4.5 uses a purity measure Gain ratio to identify the best split attribute. In C4.5
algorithm, the Information Gain measure used in ID3 algorithm is normalized by computing another factor
called Split_Info. This normalized information gain of an attribute called as Gain_Ratio is computed by the
ratio of the calculated Split_Info and Information Gain of each attribute. Then, the attribute with the highest
normalized information gain, that is, highest gain ratio is used as the splitting criteria.
As an example, we will choose the same training dataset shown in Table 6.3 to construct a decision tree using
the C4.5 algorithm.
Given a Training dataset T,
The Split_Info of an attribute A is computed as given in Eq. (6.11):

where, the attribute A has got ‘d’ distinct values a1,a2,...,ad and ∣Ai∣ is the number of instances for distinct
value ‘i’ in attribute A.
The Gain_Ratio of an attribute A is computed as given in Eq. (6.12):

Algorithm : Procedure to Construct a Decision Tree using C4.5

1. Compute Entropy_Info Eq. (6.8) for the whole training dataset based on the target attribute.
2. Compute Entropy_Info Eq. (6.9), Info_Gain Eq. (6.10), Split_Info Eq. (6.11) and Gain_Ratio Eq.
(6.12) for each of the attribute in the training dataset.
3. Choose the attribute for which Gain_Ratio is maximum as the best split attribute.
4. The best split attribute is placed as the root node.

Department of CSE,CEC 44
 Machine Learning (BCS02)

5. The root node is branched into subtrees with each subtree as an outcome of the test condition of the
root node attribute. Accordingly, the training dataset is also split into subsets.
6. Recursively apply the same operation for the subset of the training set with the remaining attributes
until a leaf node is derived or no more training instances are available in the subset.

Department of CSE,CEC 45
 Machine Learning (BCS02)

Department of CSE,CEC 46
 Machine Learning (BCS02)

Department of CSE,CEC 47
 Machine Learning (BCS02)

Department of CSE,CEC 48
 Machine Learning (BCS02)

Dealing with Continuous Attributes in C4.5

The C4.5 algorithm is further improved by considering attributes which are continuous, and a continuous
attribute is discretized by finding a split point or threshold. When an attribute ‘A’ has numerical values
which are continuous, a threshold or best split point ‘s’ is found such that the set of values is categorized
into two sets such as A<sA < s and A≥sA >=s. The best split point is the attribute value which has
maximum information gain for that attribute.
Now, let us consider the set of continuous values for the attribute CGPA in the sample dataset as shown in
Table 6.12.

Department of CSE,CEC 49
 Machine Learning (BCS02)

Department of CSE,CEC 50
 Machine Learning (BCS02)

Classification and Regression Trees Construction

The Classification and Regression Trees (CART) algorithm is a multivariate decision tree learning method
used for classifying both categorical and continuous-valued target variables. CART algorithm is an example
of multivariate decision trees that gives oblique splits. It solves both classification and regression problems.
If the target feature is categorical, it constructs a classification tree and if the target feature is continuous, it
constructs a regression tree. CART uses GINI Index to construct a decision tree. GINI Index is defined as
the number of data instances for a class or it is the proportion of instances. It constructs the tree as a binary
tree by recursively splitting a node into two nodes.
Therefore, even if an attribute has more than two possible values, GINI Index is calculated for all subsets of
the attributes and the subset which has maximum value is selected as the best split subset. For example, if an
attribute A has three distinct values say {a₁, a₂, a₃}, the possible subsets are:
{ }, {a₁}, {a₂}, {a₃}, {a₁, a₂}, {a₁, a₃}, {a₂, a₃}, and {a₁, a₂, a₃}
So, if an attribute has 3 distinct values, the number of possible subsets is 2³ = 8. Excluding the empty set {
} and the full set {a₁, a₂, a₃}, we have 6 subsets. With 6 subsets, we can form three possible combinations
such as:
• {a₁} with {a₂, a₃}
• {a₂} with {a₁, a₃}
• {a₃} with {a₁, a₂}
Hence, in this CART algorithm, we need to compute the best splitting attribute and the best split subset i in
the chosen attribute.
Higher the GINI value, higher is the homogeneity of the data instances.

Department of CSE,CEC 51
 Machine Learning (BCS02)

Gini_Index(T) is computed as given in Eq. (6.13):

Where:
• Pi be the probability that a data instance or a tuple ‘d’ belongs to class Ci. It is computed as:
• Pi=No. of data instances belonging to class i /Total no. of data instances in the training dataset TP_i
GINI Index assumes a binary split on each attribute, therefore, every attribute is considered as a binary
attribute which splits the data instances into two subsets S1 and S2
Gini_Index(T, A) is computed as given in Eq. (6.14):

The splitting subset with minimum Gini_Index is chosen as the best splitting subset for an attribute. The
best splitting attribute is chosen by the minimum Gini_Index which is otherwise maximum ΔGini because
it reduces the impurity.
ΔGini is computed as given in Eq. (6.15):

Algorithm 6.4: Procedure to Construct a Decision Tree using CART

1. Compute Gini_Index Eq. (6.13) for the whole training dataset based on the target attribute.
2. Compute Gini_Index for each of the attribute Eq. (6.14) and for the subsets of each attribute in the
training dataset.
3. Choose the best splitting subset which has minimum Gini_Index for an attribute.
4. Compute ΔGini Eq. (6.15) for the best splitting subset of that attribute.
5. Choose the best splitting attribute that has maximum ΔGini.
6. The best split attribute with the best split subset is placed as the root node.
7. The root node is branched into two subtrees with each subtree an outcome of the test condition of
the root node attribute. Accordingly, the training dataset is also split into two subsets.
8. Recursively apply the same operation for the subset of the training set with the remaining attributes
until a leaf node is derived or no more training instances are available in the subset.

Department of CSE,CEC 52
 Machine Learning (BCS02)

Department of CSE,CEC 53
 Machine Learning (BCS02)

Department of CSE,CEC 54
 Machine Learning (BCS02)

Department of CSE,CEC 55
 Machine Learning (BCS02)

Department of CSE,CEC 56
 Machine Learning (BCS02)

Department of CSE,CEC 57
 Machine Learning (BCS02)

Department of CSE,CEC 58
 Machine Learning (BCS02)

Department of CSE,CEC 59
 Machine Learning (BCS02)

Department of CSE,CEC 60
 Machine Learning (BCS02)

Regression Trees
Regression trees are a variant of decision trees where the target feature is a continuous valued variable.
These trees can be constructed using an algorithm called reduction in variance which uses standard
deviation to choose the best splitting attribute.
Algorithm 6.5: Procedure for Constructing Regression Trees
1. Compute standard deviation for each attribute with respect to target attribute.
2. Compute standard deviation for the number of data instances of each distinct value of an attribute.
3. Compute weighted standard deviation for each attribute.
4. Compute standard deviation reduction by subtracting weighted standard deviation for each attribute
from standard deviation of each attribute.
5. Choose the attribute with a higher standard deviation reduction as the best split attribute.
6. The best split attribute is placed as the root node.
7. The root node is branched into subtrees with each subtree as an outcome of the test condition of the
root node attribute. Accordingly, the training dataset is also split into different subsets.
8. Recursively apply the same operation for the subset of the training set with the remaining attributes
until a leaf node is derived or no more training instances are available in the subset.

Department of CSE,CEC 61
 Machine Learning (BCS02)

Department of CSE,CEC 62
 Machine Learning (BCS02)

Department of CSE,CEC 63
 Machine Learning (BCS02)

Department of CSE,CEC 64
 Machine Learning (BCS02)

Department of CSE,CEC 65
 Machine Learning (BCS02)

Department of CSE,CEC 66