BCS602-MACHINE LEARNING

Module - 3
SIMILARITY-BASED LEARNING

Similarity-based classifiers determine the class of a test instance by measuring its similarity to
existing data points and identifying the nearest neighbours. This approach differs from other
learning methods such as decision trees or neural networks. Similarity-based learning is also
known as instance-based learning or just-in-time learning because it does not construct an
explicit model during training. Instead, it follows a lazy learning strategy, where the training
instances are simply stored and used only when a new instance needs to be classified.
In this method, the system retains all the training data and performs computation only when a
new query instance is presented. One key advantage of this approach is that processing is
required only at the time of classification. This technique is particularly useful in situations
where the complete dataset is not available initially and is collected gradually in an incremental
manner.

Difference between Instance-and Model-based Learning

Table 4.1: Differences between Instance-based Learning and Model-based Learning
Instance-based Learning Model-based Learning
Known as eager learning, where the
Known as lazy learning, where the system
model is constructed during the training
delays processing until a query is received.
stage.
Training data is mainly processed during Training data is processed during the
the testing phase. training phase itself.
A model is built and generalized from the
No explicit model is created before
training data before a test instance is
receiving a test instance.
given.
The class of a test instance is predicted The class of a test instance is predicted
directly using the stored training data. using the learned model.
Generally, faster during the testing
Typically, slower during the testing phase
phase since predictions are made using
because computations occur at query time.
the pre-built model.
Learning occurs through multiple local Learning occurs by forming a global
approximations based on nearby data approximation of the target function
points.

Some examples of Instance-based Learning algorithms are:

1. KNN
2. Variants of KNN
3. Locally weighted regression
4. Learning vector quantization
5. Self-organizing maps
6. RBF networks

1|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

Nearest Neighbour Learning

 A widely used classification technique in pattern recognition.
 The K-Nearest Neighbours (KNN) method stores all training instances and classifies
a new instance based on a similarity measure such as a distance function.
 It is considered one of the most popular algorithms in data mining.
 KNN is a non-parametric, lazy learning algorithm, meaning it does not build a
model in advance and is categorized as an instance-based learning method.
 This algorithm can be applied to both classification and regression tasks.

Here, 2 classes of
objects called C1 and
C2. When given a test
instance T, the category
of this test instance is
determined by looking
at the class of k=3
nearest neighbors.
Thus, the class of this
test instance T is
predicted as C2.

2|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

Algorithm 4.1: k-NN

Weighted k-Nearest Neighbour Algorithm

The Weighted K-Nearest Neighbour (Weighted KNN) algorithm is an extension of the
traditional KNN method. Instead of treating all the nearest neighbours equally, it assigns
different weights to the neighbours based on their distance from the query instance.
In this approach, the k nearest data points are selected, and each neighbour is assigned a
weight using a kernel (weighting) function. The main idea behind Weighted KNN is that
closer neighbours should have a greater influence on the prediction, while farther
neighbours should contribute less. By giving higher weights to nearby points and lower
weights to distant points, the algorithm often produces more accurate classification or
regression results compared to the standard KNN method.

3|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

Nearest Centroid Classifier

The Nearest Centroid Classifier is a classification technique that assumes each class
in the feature space has its own centroid (central point). During training, the dataset
is divided into groups based on their class labels, and the centroid of each class is
calculated.
A centroid represents the mean value of all input features for the instances belonging
to that class. Because it relies on mean values, this method is also referred to as the
Mean Difference Classifier.
For example, if the dataset contains two classes, two centroids are computed. Similarly,
three classes result in three centroids, and so on. When a new instance needs to be
classified, its distance to each centroid is calculated, and the instance is assigned to the
class whose centroid is closest to it.

Locally Weighted Regression (LWR)

Locally Weighted Regression (LWR) is a non-parametric supervised learning algorithm that
performs regression by combining a regression model with the nearest neighbor approach.
Instead of building a single global model, LWR performs local regression around the query
point.
LWR is also known as a memory-based learning method because it stores the training data and
uses it during prediction. However, only the training instances that are close to the point of
interest are considered for building the regression model.
Using the nearest neighbor algorithm, the method first identifies the K instances that are closest
to the test instance. A linear function is then fitted using these K neighboring points to form a
local regression model.
The main idea behind LWR is to approximate the linear functions of the K nearest neighbors
in such a way that the prediction error is minimized. As a result, the overall prediction is not
strictly linear but forms a smooth curve, since different local linear models are fitted for
different query points.
In contrast, ordinary linear regression establishes a single linear relationship between the input
variable 𝑥and the output variable 𝑦. Given a training dataset 𝑇, the hypothesis function
ℎ𝛽 (𝑥)represents the predicted output as a linear function, where 𝛽0 is the intercept and 𝛽1 is the
coefficient of the input variable 𝑥.
It is expressed by the following equation:
ℎ𝛽 (𝑥) = 𝛽0 + 𝛽1 𝑥

where 𝛽0 represents the intercept and 𝛽1 represents the coefficient (slope) of the input variable
𝑥. This equation defines the linear hypothesis function used to predict the output value.

4|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

The cost function is defined to minimize the difference between the predicted value ℎ𝛽 (𝑥)and
the actual value 𝑦. It measures the overall prediction error for all training instances. The cost
function is expressed as:
𝑚
1
𝐽(𝛽) = ∑( ℎ𝛽 (𝑥𝑖 ) − 𝑦𝑖 )2
2
𝑖=1
where 𝑚represents the number of training instances, ℎ𝛽 (𝑥𝑖 )is the predicted value for the
𝑖 𝑡ℎ instance, and 𝑦𝑖 is the corresponding actual value. This function computes the sum of
squared errors, and the objective of the learning algorithm is to minimize this cost.
For Locally Weighted Linear Regression, the cost function is modified by assigning weights
to the training instances, giving higher importance to the points that are closer to the query
instance and lower importance to those farther away. Thus, the weighted cost function is
defined as:

where:
 𝑤𝑖 represents the weight associated with the 𝑖 𝑡ℎ training instance,
 ℎ𝛽 (𝑥𝑖 )is the predicted value,
 𝑦𝑖 is the actual value, and
 𝑚is the number of training instances.
This weighted cost function ensures that nearby data points contribute more to the
prediction, while distant points have less influence on the regression model.
In Locally Weighted Regression, the weight assigned to each training instance is calculated
using a Gaussian kernel function. This function assigns higher weights to instances that are
closer to the test instance, while the weights for instances that are farther away gradually
decrease. Although the weight becomes very small for distant points, it approaches zero but
never becomes exactly zero.
The weight 𝑤𝑖 is computed as follows:
(𝑥 −𝑥)2
𝑤𝑖 = exp⁡( − 𝑖 2 )
2𝜏
where:
 𝑤𝑖 is the weight assigned to the 𝑖 𝑡ℎ training instance,
 𝑥𝑖 represents the feature value of the training instance,
 𝑥is the query or test instance, and
 𝜏(tau) is the bandwidth parameter that controls how quickly the weight decreases
with distance.
This weighting mechanism ensures that nearby points have a stronger influence on the
prediction, allowing the regression model to adapt locally to the data.

5|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

PROBLEMS
Example 4.1
Consider a student performance training dataset consisting of 8 data instances, as presented in
Table 4.2. This dataset represents the performance of students in a course along with their CGPA
obtained in previous semesters.
The independent attributes are:
 CGPA
 Assessment
 Project Submitted
The target variable is Result, which is a discrete attribute with two possible values: Pass or
Fail. The objective is to classify whether a student will pass or fail based on their performance.
Table 4.2: Training Dataset (T)
Project
[Link] CGPA Assessment Result
Submitted
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

Solution
Given:
 Test instance = (6.1, 40, 5)
 Classes = {Pass, Fail}
 k=3
The task is to classify the test instance using the k-Nearest Neighbors (k-NN) algorithm
with Euclidean distance.
Step 1: Compute Euclidean Distance
Calculate the Euclidean distance between the test instance and each training instance.

Instance Result Euclidean Distance

1 Pass 45.2063
2 Pass 40.0950
3 Pass 41.1796
4 Fail 5.0010
5 Fail 10.0578
6 Pass 32.1311
7 Fail 2.0224
8 Pass 51.2332

6|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

Step 2: Identify Nearest Neighbours

Sort the distances in ascending order and select the k = 3 nearest neighbours.
Instance Distance Class
7 2.0224 Fail
4 5.0010 Fail
5 10.0578 Fail

Step 3: Classification
Using majority voting, all three nearest neighbors belong to the Fail class.
Therefore, the predicted class for the test instance is:
Result: FAIL

Example 4.2
Consider the same training dataset given in Table above Apply the Weighted k-Nearest
Neighbors (Weighted k-NN) algorithm to determine the class of the given test instance.
Solution
Given:
 Test instance = (7.6, 60, 8)
 Classes = {Pass, Fail}
 k=3
The classification is performed using Euclidean distance with weighted voting.
Step 1: Compute Euclidean Distance
Calculate the Euclidean distance between the test instance and each training data point.
Instance Result Euclidean Distance
1 Pass 25.05115
2 Pass 20.02898
3 Pass 21.01928
4 Fail 15.38051
5 Fail 10.82636
6 Pass 12.05653
7 Fail 22.27644
8 Pass 31.04336

Step 2: Select k Nearest Neighbors

Sort distances in ascending order and select the k = 3 nearest neighbors.
Instance Distance Class
5 10.82636 Fail
6 12.05653 Pass
4 15.38051 Fail

7|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

Step 3: Apply Weighted Voting

(a) Compute Inverse Distance

Instance Distance Inverse Distance Class

4 15.38051 0.06502 Fail
5 10.82636 0.09237 Fail
6 12.05653 0.08294 Pass

(b) Compute Sum of Inverse Distances

𝑺𝒖𝒎 = 𝟎. 𝟎𝟔𝟓𝟎𝟐 + 𝟎. 𝟎𝟗𝟐𝟑𝟕 + 𝟎. 𝟎𝟖𝟐𝟗𝟒 = 𝟎. 𝟐𝟒𝟎𝟑𝟑
(c) Compute Weights

(𝑰𝒏𝒗𝒆𝒓𝒔𝒆⁡𝑫𝒊𝒔𝒕𝒂𝒏𝒄𝒆)
𝑾𝒆𝒊𝒈𝒉𝒕⁡ =
𝑻𝒐𝒕𝒂𝒍⁡𝑺𝒖𝒎
Instance Weight Class
4 0.270545 Fail
5 0.384347 Fail
6 0.345109 Pass

(d) Aggregate Weights by Class

⁡Fail⁡=⁡0.270545⁡+⁡0.384347⁡=⁡0.654892⁡
Pass⁡=⁡0.345109

Final Prediction
The class with the highest total weight is selected.
Predicted Class = FAIL

Example 4.3
Consider the sample dataset shown in Table 4.9 with two features x and y. The target
classes are ‘A’ and ‘B’.
Predict the class of a given test instance using the Nearest Centroid Classifier.

Table 4.9: Sample Data

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

8|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

Solution

Step 1: Compute Centroid of Each Class

The centroid represents the mean of feature values for each class.
Centroid of Class A
𝟑 + 𝟓 + 𝟒, 𝟏 + 𝟐 + 𝟑 𝟏𝟐, 𝟔
= = (𝟒, 𝟐)
𝟑 𝟑
Centroid of Class B
𝟕 + 𝟔 + 𝟖, 𝟔 + 𝟕 + 𝟓 𝟐𝟏, 𝟏𝟖
= = (𝟕, 𝟔)
𝟑 𝟑
Step 2: Compute Distance from Test Instance
𝑮𝒊𝒗𝒆𝒏⁡𝒕𝒆𝒔𝒕⁡𝒊𝒏𝒔𝒕𝒂𝒏𝒄𝒆⁡ = ⁡ (𝟔, 𝟓)
Calculate Euclidean distance to each centroid.
𝑫𝒊𝒔𝒕𝒂𝒏𝒄𝒆⁡𝒕𝒐⁡𝑪𝒍𝒂𝒔𝒔⁡𝑨⁡𝒄𝒆𝒏𝒕𝒓𝒐𝒊𝒅⁡(𝟒, 𝟐)
√(𝟔 − 𝟒)𝟐 +⁡ (𝟓 − 𝟐)𝟐 = 𝟑. 𝟔
𝑫𝒊𝒔𝒕𝒂𝒏𝒄𝒆⁡𝒕𝒐⁡𝑪𝒍𝒂𝒔𝒔⁡𝑩⁡𝒄𝒆𝒏𝒕𝒓𝒐𝒊𝒅⁡(𝟕, 𝟔)

√(𝟔 − 𝟕)𝟐 + ⁡ (𝟓 − 𝟔)𝟐 = 𝟏. 𝟒𝟏𝟒

Step 3: Classification
Since the test instance is closer to Class B centroid, it is assigned to that class.
Predicted Class = B

9|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

MODULE 3
REGRESSION ANALYSIS
Introduction to Regression
Regression analysis is a fundamental concept that consists of a set of machine learning methods
that predict a continuous outcome variable (y) based on the value of one or multiple predictor
variables (x).
OR
Regression analysis is a statistical method to model the relationship between a dependent
(target) and independent (predictor) variables with one or more independent variables.
Regression is a supervised learning technique which helps in finding the correlation between
variables. It is mainly used for prediction, forecasting, time series modelling, and
determining the causal-effect relationship between variables.
Regression shows a line or curve that passes through all the datapoints on target-predictor graph
in such a way that the vertical distance between the datapoints and the regression line is
minimum. The distance between datapoints and line tells whether a model has captured a strong
relationship or not.
Function of regression analysis is given by:
𝑌 = 𝑓(𝑥)
Here, Y is called dependent variable and x is called independent variable.
Applications of Regression Analysis
 Sales of a goods or services
 Value of bonds in portfolio management
 Premium on insurance companies
 Yield of crop in agriculture
 Prices of real estate

INTRODUCTION TO LINEARITY, CORRELATION AND CAUSATION

A correlation is the statistical summary of the relationship between two sets of variables. It
is a core part of data exploratory analysis, and is a critical aspect of numerous advanced machine
learning techniques. Correlation between two variables can be found using a scatter plot

There are different types of correlation:

Positive Correlation: Two variables are said to be positively correlated when their values move
in the same direction. For example, in the image below, as the value for X increases, so does the
value for Y at a constant rate.
Negative Correlation: Finally, variables X and Y will be negatively correlated when their values
change in opposite directions, so here as the value for X increases, the value for Y decreases at a
constant rate.
Neutral Correlation: No relationship in the change of variables X and Y. In this case, the values
are completely random and do not show any sign of correlation, as shown in the following image:

1|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

Causation
Causation is about relationship between two variables as x causes y. This is called x implies b.
Regression is different from causation. Causation indicates that one event is the result of the
occurrence of the other event; i.e. there is a causal relationship between the two events.
Linearity and Non-Linearity Relationships
A linear relationship describes a situation where the dependent variable (y) changes at a
constant rate with respect to the independent variable (x).
 The relationship can be represented by a straight line on a graph.
 As x increases, y increases or decreases uniformly.
 The equation 𝑦 = 𝑎𝑥 + 𝑏 fits the data points, where:
o a is the slope (rate of change)
o b is the intercept
Non-Linear Relationship
A non-linear relationship exists when the change in y with respect to x is not constant.
 The graph is curved, not a straight line.
 The rate of change varies at different values of x.
 Common examples include:
o Exponential functions
o Power functions
 Linear relationship: - Represented by a straight line (Figure 5.2a)
 Non-linear relationship: - Represented by curved graphs (Figures 5.2b and 5.2c)

x-axis: Represents the independent variable (x data)

y-axis: Represents the dependent variable (y data)
Linear: - Constant rate of change, straight-line pattern
Non-linear: - Variable rate of change, curved pattern

2|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

Types of Regression

Linear Regression:
Single Independent Variable: Linear regression, also known as simple linear regression, is used
when there is a single independent variable (predictor) and one dependent variable (target).
Equation: The linear regression equation takes the form:
𝑌 = 𝛽𝑜 + 𝛽1 𝑋+∈
Where
Y is the dependent variable,
X is the independent variable,
β0 is the intercept,
β1 is the slope (coefficient), and
ε is the error term.
Linear regression is used to establish a linear relationship between two variables and make
predictions based on this relationship. It's suitable for simple scenarios where there's only one
predictor.

3|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

Multiple Regression:
Multiple Independent Variables: Multiple regression, as the name suggests, is used when there
are two or more independent variables (predictors) and one dependent variable (target).
Equation: The multiple regression equation extends the concept to multiple predictors:
𝑌 = 𝛽𝑜 + 𝛽1 𝑋1 + 𝛽2 𝑋2 + ⋯ . . +𝛽𝑛 𝑋𝑛 +∈
where
Y is the dependent variable,
X1, X2, ..., Xn are the independent variables,
β0 is the intercept, β1, β2, ..., βn are the coefficients, and
ε is the error term.
Multiple regression allows to model the relationship between the dependent variable and
multiple predictors simultaneously. It's used when there are multiple factors that may influence
the target variable, and you want to understand their combined effect and make predictions based
on all these factors.

Polynomial Regression:
Polynomial regression is an extension of multiple regression used when the relationship between
the independent and dependent variables is non-linear.
Equation: The polynomial regression equation allows for higher-order terms, such as quadratic
or cubic terms:
𝑌 = 𝛽𝑜 + 𝛽1 𝑋1 + 𝛽2 𝑋2 + ⋯ . . +𝛽𝑛 𝑋𝑛 +∈
This allows the model to fit a curve rather than a straight line.

Logistic Regression:
Logistic regression is used when the dependent variable is binary (0 or 1). It models the
probability of the dependent variable belonging to a particular class.
Equation: Logistic regression uses the logistic function (sigmoid function) to model
probabilities:
1
𝑃 (𝑌 = 1) =
(1 − 𝑒 𝑧 )
where z is a linear combination of the independent variables:
𝑧 = 𝛽𝑜 + 𝛽1 𝑋1 + 𝛽2 𝑋2 + ⋯ . . +𝛽𝑛 𝑋𝑛 +∈
It transforms this probability into a binary outcome.

Limitations of Regression
1. Outliers - Outliers are abnormal data. It can bias the outcome of the regression model, as
outliers push the regression line towards it.
2. Number of cases - The ratio of independent and dependent variables should be at least 20:1.
For every explanatory variable, there should be at least 20 samples. Atleast five samples are
required in extreme cases.
3. Missing data - Missing data in training data can make the model unfit for the sampled data.
4. Multicollinearity - If exploratory variables are highly correlated (0.9 and above), the
regression is vulnerable to bias. Singularity leads to perfect correlation of 1. The remedy is to

4|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

remove exploratory variables that exhibit correlation more than 1. If there is a tie, then the
tolerance 1 − 𝑅2 is used to eliminate variables that have the greatest value.

INTRODUCTION TO LINEAR REGRESSION

Linear regression model can be created by fitting a line among the scattered data points. The
line is of the form:

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.
Ordinary Least Square Approach
The concept of linear regression is based on the Ordinary Least Squares (OLS) method. In this
approach, the given data points are modeled using a straight line, which represents the
relationship between variables. However, not every arbitrarily drawn line provides the best
representation of the data.
For each data point, the vertical distance between the actual point and the predicted value from
the line (given by the equation 𝑦 = 𝑎0 + 𝑎1 𝑥 is called an error (residual). Below figure 5.4
shows individual errors (e₁, e₂, e₃, …) indicate how much the predicted values deviate from the
actual observations.
To evaluate the overall accuracy of the line, these errors are combined to compute the total error,
known as the sum of residuals. Additionally, the squares of these errors are calculated and
summed to obtain the sum of squared errors (SSE).
The best fit line is the one that minimizes this sum of squared errors, making it the most accurate
representation of the data according to the OLS method.
Ordinary Least Squares (OLS) can be understood as an optimization method that aims to
minimize the difference between the actual data points and the fitted line.
Mathematically, for a set of data points (𝑥1 , 𝑥2 , … . 𝑥𝑛 ) the predicted values are expressed as:
𝑦1 = (𝑎0 + 𝑎1 𝑥1 ) + 𝑒1
𝑦2 = (𝑎0 + 𝑎1 𝑥2 ) + 𝑒2
.
.
𝑦𝑛 = (𝑎0 + 𝑎1 𝑥𝑛 ) + 𝑒𝑛
Here, each eie_iei represents the error (residual) associated with the corresponding data point.
In general, the error for each observation is given by:

5|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

𝑒𝑖 = 𝑦𝑖 − (𝑎0 + 𝑎1 𝑥𝑖 )
Thus, OLS forms a system of equations representing all data points, and the objective is to
determine the values of a0a_0a0 and a1a_1a1 that minimize these errors.

6|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

Linear Regression Example

7|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

8|Page
Department of CSE, RNSIT
 BCS602-MACHINE LEARNING

9|Page
Department of CSE, RNSIT