# Supervised Learning-Instance Based Classifiers Part-2
course: Module 2 — Machine Learning Algorithms
module: Module-2-Machine-Learning-Algorithms
type: pdf
source_url: https://personal-learn.armco.dev/files/Module-2-Machine-Learning-Algorithms/General/Supervised_Learning-Instance_Based_Classifiers_Part-2.pdf
pages: 30
---
[page 1]
IIT Roorkee – Futurense
PG Certification
GenAI and Agentic AI for Engineers
Supervised Learning
Dr Durga Toshniwal
Professor
Department of Computer Science & Engg.
Indian Institute of Technology Roorkee
durga.toshniwal@cs.iitr.ac.in, durgatoshniwal@gmail.com
www.durgatoshniwal.in
[page 2]
Today’s Agenda
• Instance Based Classifiers
• Rote Learner
• kNN Classifier
• Naïve Bayes’ Classifier
• K-Fold Cross Validation
[page 3]
Classifiers
• Decision tree classifier involves a model
construction & then its application
• They are eager learners as they are
designed to learn the model mapping the
attributes to class labels as soon as the
training data set is made available
[page 4]
Classifiers
• An opposite strategy would be to delay the
process of learning the training data until it
is required to classify the test examples
• Such classifiers are called lazy classifiers
[page 5]
Instance-Based Classifiers
Atr1 ……... AtrN Class
A
B
B
C
A
C
B
Set of Stored Cases
Atr1 ……... AtrN
Unseen Case
• Store the training records
• Use training records to
predict the class label of
unseen cases
[page 6]
Instance Based Classifiers
• Examples:
– Rote-learner
• Performs classification only if attributes of
record match one of the training examples
exactly
• Drawback – some records may not be
classified as they don’t match exactly to any
training record
• Leads to…
[page 7]
Instance Based Classifiers
So we go for approximate match…
So all training records that are not exactly similar
but relatively similar to the attributes of the test
example are identified
Hence ...
– Nearest Neighbor
• Uses k “closest” points (nearest neighbors)
for performing classification
[page 8]
Nearest Neighbor Classifiers
• Basic idea:
– If it looks like a duck, is part of a flock of duck,
then it’s probably a duck
Training
Records
Test
Record
Compute
Distance
Choose k of the
“nearest” records
[page 9]
Instance Based Classifiers
• K Nearest Neighbor (kNN)
• Represents each record as a data point in
a d-dimensional space where d is the
number of attributes
• A distance measure is used to compute
closeness of a test record to the data points
in training set
• K closest points are identified & their class
labels are used to find class label for the
test record
[page 10]
K Nearest-Neighbor (KNN)
Classifiers
Requires three
things
– The set of stored
records
– Distance Metric to
compute distance
between records
– The value of k, the
number of nearest
neighbors to
retrieve
Unknown record
[page 11]
K Nearest-Neighbor (KNN) Classifiers
To classify an unknown
record:
– Compute distance to
other training records
– Identify k nearest
neighbors
– Use class labels of k
nearest neighbors to
determine the class
label of unknown
record e.g., by taking
majority vote
Unknown record
[page 12]
K Nearest Neighbor (KNN)
Classification
• Compute distance between two points:
– Euclidean distance
• Determine the class from nearest neighbor
list
– take the majority vote of class labels among the
k-nearest neighbors
−=
i ii qpqpd
2
)(),(
[page 13]
K Nearest Neighbors
X X X
(a) 1-nearest neighbor (b) 2-nearest neighbor (c) 3-nearest neighbor
K-nearest neighbors of a record x are k data points
closest to x
[page 14]
Nearest Neighbor Classification
• Choosing the value of k:
– If k is too small, sensitive to noise points
– If k is too large, neighborhood may include points from
other classes
X
[page 15]
K Nearest Neighbor (KNN)
Classification
• k-NN classifiers are lazy learners
• Do not maintain an abstraction or model from
training data
• Thus Make their predictions on the basis of local
information & not global models that fit the entire
data
• So are quite susceptible to noise
[page 16]
Eager Learners Versus Lazy
Learners
Eager Learners are better ?
Lazy Learners are better ?
[page 17]
Bayesian Classifiers
• Sometimes the relationship b/w the attribute set
& the class variable is non-deterministic
• The class label of a test record can’t be
predicted with certainty even though its attribute
set is identical to some training examples
[page 18]
Bayesian Classifiers
• Sometimes the relationship b/w the attribute set & the
class variable is non-deterministic
• The class label of a test record can’t be predicted with
certainty even though its attribute set is identical to some
training examples
• Ex – Predicting whether a person is at risk for a
heart disease on the basis of Diet & frequency of
workout
• There may be other factors like heredity,
smoking etc. that might affect a person
[page 19]
Bayesian Classifiers
• We thus need to model probabilistic
relationships b/w the attribute set & the
class variable
• Bayes Theorem is a statistical principle
• Bayes theorem can be used to compute the
probability that the proposed diagnosis is
correct
[page 20]
Bayes Classifier
• Bayes' Theorem relates the conditional and marginal
probabilities of events A and B :
• Intuitively, Bayes' Theorem in this form describes the
way in which one's beliefs about observing ‘C' are
updated by having observed ‘A'.
𝑃(𝐶|𝐴) = 𝑃(𝐴|𝐶)𝑃(𝐶)
𝑃(𝐴)
[page 21]
Bayes Classifier
• P(A) is the prior probability or marginal probability
of A. It is "prior" in the sense that it does not take into
account any information about C
• P(A|C) is the conditional probability of A, given C. It
is also called the posterior probability because it is
derived from or depends upon C
• P(C|A) is the conditional probability of C given A
• P(C) is the prior or marginal probability of C
𝑃(𝐶|𝐴) = 𝑃(𝐴|𝐶)𝑃(𝐶)
𝑃(𝐴)
[page 22]
Example of Bayes Theorem
• Given:
– A doctor knows that meningitis causes stiff neck 50% of the time
– Prior probability of any patient having meningitis is 1/50,000
– Prior probability of any patient having stiff neck is 1/20
• If a patient has stiff neck, what’s the
probability he/she has meningitis?
0002.020/1
50000/15.0
)(
)()|()|( === SP
MPMSPSMP
[page 23]
Bayesian Classifiers
• Approach:
– compute the posterior probability P(C | A1, A2, …, An) for all
values of C using the Bayes theorem
– Choose value of Class C that maximizes
P(C | A1, A2, …, An)
• How to estimate P(A1, A2, …, An | C )?
)(
)()|()|(
21
21
21
n
n
n
AAAP
CPCAAAPAAACP
=
[page 24]
Naïve Bayes Classifier
Conditional Independence
• Assumes that the attributes are
conditionally independent of each other,
given a class label Cj
• Formally:
P(A1, A2, …, An | Cj )
= P(A1| Cj) P(A2| Cj)… P(An| Cj)
= P(Ai| Cj) for i = 1 to n
[page 25]
Naïve Bayes Classifier
• Assume conditional independence among attributes
Ai when class is given:
– P(A1, A2, …, An |C) = P(A1| Cj) P(A2| Cj)… P(An| Cj)
– New point is classified to Cj if P(Cj) P(Ai| Cj) is
maximal.
)(
)()|()|( AP
CPCAPACP =
[page 26]
How to Estimate Probabilities from Data?
• Class: P(C) = Nc/N
– P(No) = 7/10, P(Yes) = 3/10
• For discrete attributes:
P(Ai | Ck) = |Aik|/ Nc
– where |Aik| is number of
instances having attribute Ai
and belongs to class Ck
– Examples:
P( Status = Married | No) = 4/7
P( Refund = Yes | Yes) = 0
Tid Refund Marital
Status
Taxable
Income Cheat
1 Yes Single 125K No
2 No Married 100K No
3 No Single 70K No
4 Yes Married 120K No
5 No Divorced 95K Yes
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 120K Yes
9 No Married 75K No
10 No Single 90K Yes
10
[page 27]
How to Estimate Probabilities from Data?
Given a record :
X = (Refund = No, Marital Status =
Single, Income = 70 K), Class = ?
Tid Refund Marital
Status
Taxable
Income Cheat
1 Yes Single 125K No
2 No Married 100K No
3 No Single 70K No
4 Yes Married 120K No
5 No Divorced 95K Yes
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 120K Yes
9 No Married 75K No
10 No Single 90K Yes
10
[page 28]
Naïve Bayes (Summary)
• Robust to isolated noise points
• Handle missing values by ignoring the instance
during probability estimate calculations
• Robust to irrelevant attributes
• Independence assumption may not hold for all kinds
of datasets
[page 29]
K Cross Fold Validation
• Cross-validation is a technique for evaluating ML models
by training several ML models on subsets of the available input data and
evaluating them on the complementary subset of the data
• In k-fold cross-validation, the input data is split into k subsets of data
(also known as folds).
[page 30]
K Cross Fold Validation
• Average Performance is the model performance