UNIT-IV

CLASSIFICATION

Dr. Suresh Chimkode

What is Classification? Discuss with examples
Classification
In each of these is aexamples,
form of data analysis
the data thattask
analysis extracts models describing
is classification, where a
important data isclasses.
model classifier Suchtomodels,
constructed called
predict class as categorical)
(i.e., classifiers, labels.
will predict
Such
categorical
as, class labels.
 “safe” or “risky” for the loanProblem Definition
application data;
 “yes”
Let’s or “no”
consider fewforexamples
the marketing data;
to understand the classification concept
1. we
“treatment A,” “treatment
can build B,” or “treatment
a classification model C”toforcategorize
the medical bank
data loan
 These categories can be represented by discrete values, where the
applications as either safe or risky
[i.e.,ordering
A bankamong
loans values
officerhas no meaning.
needs analysis of his/her data to learn which
 For example, the values 1, 2, and 3 may be used to represent treatments
loan applicants are “safe” and which are “risky” for the bank.]
A, B, and C, where there is no ordering implied among this group of
treatment regimes.
Similarly,
2. A marketing manager at AllElectronics needs data analysis to help
guess whether a customer with a given profile will buy a new computer.

3. A medical researcher wants to analyze breast cancer data to predict

which one of three specific treatments (treatment A, B or C) a patient
should receive.
Dr. Suresh Chimkode
 General Approach to Classification
How does classification work?
Data classification is a two-step process.

1. learning step (where a classification model is constructed)

2. classification step (where the model is used to predict class labels for given
data).

The two-step process is shown in below Fig. for the loan application data.

Dr. Suresh Chimkode

1. learning step (where a classification model is constructed)…. ..

 In the first step, a classifier is built describing a predetermined set of data

classes or concepts.
 This is the learning step (or training phase), where a classification algorithm
builds the classifier by analyzing or “learning from” a training set made up
of database tuples and their associated class labels.

Because the class label of each training tuple is provided, this step is also
known as supervised learning. (i.e., the learning of the classifier is
“supervised”, means to which class each training tuple belongs).
 It contrasts with unsupervised learning (or clustering), where the class
label of each training tuple is not known, and the number or set of classes
to be learned may not be known in advance.
 For example, if we did not have the loan decision data available for the
training set, we could use clustering to try to determine “groups of like
tuples,” which may correspond to risk groups within the loan application
data.
Dr. Suresh Chimkode
1. learning step (where a classification model is constructed)…. ..

 This first step of the classification process can also be viewed as the
learning of a mapping or function, y = f (X), that can predict the associated
class label y of a given tuple X.

 In this context, we wish to learn a mapping or function that separates the

data classes. Such mapping is represented in the form of classification
rules, decision trees, or mathematical formulae.

 In our example, the mapping is represented as classification rules that

identify loan applications as being either safe or risky.

Dr. Suresh Chimkode

2. classification step (where the model is used to predict class labels for given
data).
 In the second step as shown in below fig. The model is used for
classification. First, the predictive accuracy of the classifier is estimated.
d th e ir a ss o cia ted class
a d e u p o f te st t uples an a t they
s e t u s e d is m e a nin g is th
Therefore, a test th e t ra in in g tu ples, m
ey a re in d e p e n dent of
labels. Th uc t t h e c la s sifier. t a g e o f t e st set
co n s t r the pe r ce n
were not used to s s ifier on a g iv e n te st se t is
u r ac y o f a c la ifier.
 The acc ss ifi e d b y t h e c la ss
learned
a re c o r r e c tly cla p ar e d w ith th e
tuples that o f e a ch te s t t u p le is com
 The associated cla
ss label
d ic ti o n fo r t h a t tuple.
r e
classifier ’s class p

 If we were to use the training set to measure the classifier’s accuracy, this
estimate would likely be optimistic, because the classifier tends to overfit the
data.
i.e., During learning it may incorporate some particular anomalies of the
training data that are not present in the general data set overall.
Dr. Suresh Chimkode
Discovering and evaluating classification knowledge

Creating classifiers is a multi-step approach:

 Generating a classifier from the given learning data set,
 Evaluation on the test examples,
 Using for new example
Train and test paradigm!

Evaluation criteria (1)

• Predictive (Classification) accuracy: this refers to the ability of the model to
correctly predict the class label of new or previously unseen data:
• accuracy = % of testing set examples correctly classified by the
classifier
• Speed: this refers to the computation costs involved in generating and using
the model
• Robustness: this is the ability of the model to make correct predictions given
noisy data or data with missing values

Dr. Suresh Chimkode

Discovering and evaluating classification knowledge.. .. .

Evaluation criteria (2)

Scalability: this refers to the ability to construct the model efficiently given
large amount of data
Interpretability: this refers to the level of understanding and insight that is
provided by the model
Simplicity:
• decision tree size
• rule compactness
• Domain-dependent quality indicator

Dr. Suresh Chimkode

What is Evaluation of Classifiers and what are Key Metrics of Evaluation .
 Evaluation of a classifier is the process of assessing how well a machine
learning model performs in predicting the target variable.
 Here, the goal is to understand the effectiveness of the model in making
accurate predictions on new, unseen data.
Key Metrics for Evaluation are:
Accuracy: Proportion of correct predictions. (i.e., % of correctness of the
classifier)

Precision: Proportion of true positive predictions out of all positive

predictions. (i.e., % of the positive predictions that are actually correct)

Recall (Sensitivity): Proportion of actual positives correctly predicted.

(i.e., % of the actual positives were correctly identified)

F1 Score: Harmonic mean of precision and recall.

Dr. Suresh Chimkode
Classification Techniques
 Several techniques can be used for classification, each with its pros and
cons.
 Few of them are as follows:
Decision Trees
 Decision trees Splits data into branches based on feature values to make
decisions.
 Pros: Easy to interpret, handles both categorical and numerical data.
 Cons: Can be prone to overfitting.

Naive Bayes
 Naïve Bayes uses Bayes' theorem to calculate the probability of each class.
 Pros: Fast, handles large datasets well, effective for text classification.
 Cons: Assumes independence of features, which may not always hold true.

k-Nearest Neighbour (k-NN)

 k-NN Classifies based on the majority class of k-nearest neighbors.
 Pros: Simple, no training phase, effective for small datasets.
 Cons: Computationally intensive with large datasets, sensitive to irrelevant
features. Dr. Suresh Chimkode
 Decision tree
What is Decision tree?
 A decision tree is a flowchart-like structure used for decision-making and
predictive modeling.
 It breaks down a complex decision into simpler parts by asking a series of
questions that lead to an outcome or classification.
 Each internal node in tree represents a decision based on a feature
(attribute), each branch represents the outcome of that decision, and each
leaf node represents a final outcome (label).

Why to use Decision Trees?

For the following reasons
Simplicity: They are easy to understand and interpret, even for non-experts.
Visualization: They can be visualized graphically, making it easy to present the
decision-making process.
Non-parametric: They don't assume a specific distribution of the data, which
makes them flexible.
Versatile: Can be used for both classification (categorical outcomes) and
regression (continuous outcomes).
Flexible: Handles both numerical and categorical
Dr. data.
Suresh Chimkode
 An example Scenario for Decision tree
Imagine we want to decide whether to play Tennis outside based on weather
conditions.

Outlook Temperature Humidity Windy PlayTennis

-------------- ----------------- ---------------- --------------- ------------
Sunny Hot High False No
Sunny Hot High True No
Overcast Hot High False Yes
Rainy Mild High False Yes
Rainy Cool Normal False Yes
Rainy Cool Normal True No
Overcast Cool Normal True Yes
Sunny Mild High False No

Here, the Features are:

Outlook (Sunny, Overcast, Rainy)
Temperature (Hot, Mild, Cool)
Humidity (High, Normal)
Dr. Suresh Chimkode
 An example Scenario for Decision tree.. …
Building the Decision Tree:
Root Node: Start with the feature that best splits the data (e.g., Outlook).
Branches: Split into child nodes based on the values of Outlook (Sunny,
Overcast, Rainy). sta nc e s b a se d on feature
ca n e ffe c tiv e ly c la ssify in
ion tree
DecisTree:
Example s Outlookion-making.
a p o w e r fu l to ol for de?cis
values, making them
Outlook?
| Sunny -> Humidity? Sunny
Overca
Rainy
st
| | High -> No
| | Normal -> Yes Humidity
Yes Windy ?
| Overcast -> Yes ?

| Rainy -> Windy? Norma True False

High
|Here,
| True -> No Process is as follows:
the Decision
l

|If the
| False -> Yes
outlook is Overcast, play tennis.
No Yes No Yes
If the outlook is Sunny:
If humidity is High, don't play
tennis.
If humidity is Normal, play tennis.
If the outlook is Rainy:
If it's windy, don't play tennis. Dr. Suresh Chimkode
Explain Construction of decision tree using the weather data set
The weather dataset includes features like "Outlook," "Temperature,"
"Humidity," and "Wind" to decide whether to play tennis.
1. Select the Best Attribute
Initial Dataset: Assume we have records like:
Outlook: Sunny, Overcast, Rainy
Temperature: Hot, Mild, Cool
Humidity: High, Normal
Wind: Weak, Strong
PlayTennis: Yes, No
 We start by selecting the attribute that best separates the "PlayTennis"
outcomes.
 Let's use the Information Gain criterion here. "Outlook" typically shows
significant separation.
2. Split the Dataset
First Split: Split based on "Outlook":
Sunny
Overcast
Rainy
Dr. Suresh Chimkode
3. Repeat for Subsets
Second Split: For each subset, choose the best attribute. For example:
Sunny: Split based on "Humidity" (High, Normal)
Overcast: No further split needed as it's always "Yes."
Rainy: Split based on "Wind" (Weak, Strong)

4. Terminate
Stop when further splitting doesn't improve classification or when the
subsets are pure (all "Yes" or "No").
[Outlook]
/ | \
Sunny Overcast Rainy
/ | \
[Humidity] Yes [Wind]
/ \ / \
High Normal Weak Strong
| | | |
No Yes Yes No
Dr. Suresh Chimkode
What is Information Gain criterion in construction of decision tree?
 Information Gain is a metric used to measure how well a feature
(attribute) separates the training examples according to their target
classification.
i.e., In the context of constructing decision trees, it helps in selecting the
best attribute to split the data at each node.

Explain with an example how Information Gain helps (or works) for
selecting the best attribute to split the data at each node in decision
tree construction?

Example: Consider Weather Dataset

Attributes: Outlook, Temperature, Humidity, Wind Target: PlayTennis (Yes/No)

Dr. Suresh Chimkode

Assume the Initial Dataset is as follows

Information Gain Works as:

Step-1. Calculate Initial Entropy: Entropy (H) indicates disorder or uncertainty.
For above shown dataset:
9 "Yes" for PlayTennis
5 "No" for PlayTennis
(i.e., we have 14 instances, 9 of which are "Yes" (Play Tennis) and 5 are "No".)
Dr. Suresh Chimkode
Entropy Calculation
 We have 14 instances, 9 of which are "Yes" (Play Tennis) and 5 are "No".
 Entropy is a measure of the disorder or uncertainty in the dataset. For a
binary classification, entropy H(D) is calculated as:
where, c is Number of classes, p1 and p2 (i.e., pi in short) are the proportions
of instances in two classes of the dataset D.
H(D) = - ∑ (p1 * log2 (p1) + p2 * log2(p2))
H(D) = - (9/14 * log2(9/14) + 5/14 * log2(5/14))
≈ 0.94
Step-2. Information Gain Calculation:
Information Gain measures the reduction in entropy when the dataset is split
on an attribute. It is calculated as:

Where: IG(D, A) = Information Gain for dataset D and attribute A

H(D) = Entropy of the entire dataset
∑ = Summation over each value v of attribute A
∣ Dv ∣ = Number of instances in subset Dv
∣ D ∣ = Total number of instances in dataset D
H(Dv) = Entropy of subset Dv Dr. Suresh Chimkode
Information Gain for "Outlook": If we split based on "Outlook" (Sunny,
Overcast, Rainy): Count class attribute
values for each "Outlook“ attribute value
For Sunny: 2 Yes, 3 No
For Overcast: 4 Yes, 0 No
For Rainy: 3 Yes, 2 No
Calculate Entropy for 'Outlook' Attribute
Sunny:
Subset: 5 instances (2 Yes, 3 No)
Entropy: H(Sunny) = -(2/5 * log2(2/5) + 3/5 * log2(3/5)) ≈ 0.97

Overcast:
Subset: 4 instances (4 Yes, 0 No)
Entropy: H(Overcast) = 0 (since all are Yes)

Rainy:
Subset: 5 instances (3 Yes, 2 No)
Entropy: H(Rainy) = -(3/5 * log2(3/5) + 2/5 * log2(2/5)) ≈ 0.97
Dr. Suresh Chimkode
Step 3: Calculate Weighted Average Entropy H(D, Outlook)
Where,
H(D, A) = Weighted Entropy after splitting on attribute A
∣Dv∣ = Number of instances in subset Dv
∣D∣ = Total number of instances in the original dataset D
H(Dv) = Entropy of subset Dv
Values(A) = All possible values of attribute A

Weighted Entropy (Outlook) = (5/14 * 0.97) + (4/14 * 0) + (5/14 * 0.97)

≈ 0.69
Step 4: Calculate Information Gain for 'Outlook’ i.e., IG(D, Outlook)
IG(D, Outlook) = H(D) - Weighted Entropy (Outlook)
≈ 0.94 - 0.69
≈ 0.25
 The higher the Information Gain, the more effective the attribute is at reducing
uncertainty and splitting the dataset.
 Here, 'Outlook' has an Information Gain of 0.25, making it a good candidate for
the initial split.
 This process is repeated for other attributes, and the one with the highest
Information Gain is used for splitting at each node.
Dr. Suresh Chimkode
What is the significance of minus sign in Entropy Calculation formula?

The minus sign in the entropy calculation formula signifies the negation of
probabilities, ensuring a positive result.
Because,

 Probabilities and Logarithms: In the formula, log2(pi) yields a negative

value for probabilities between 0 and 1.

 Negative Probabilities: The sum of these values without the minus sign
would result in negative entropy, which doesn't make sense, as entropy is
supposed to be a measure of uncertainty and should be non-negative.

Hence, The minus sign ensures that entropy values are always positive or
zero, giving a proper measure of uncertainty.

Dr. Suresh Chimkode

 Methods for expressing attribute test conditions in Decision Trees
Discuss the methods for expressing attribute test conditions in Decision Trees
 In decision tree algorithms, attribute test conditions can be expressed in
several ways depending on the type of data and the complexity of the
decision boundary we want to define.
 Some common methods are:
1. Binary Splits
2. Multi-way Splits
3. Range-based Splits
4. Nominal and Ordinal Attributes
5. Complex Conditions
1. Binary Splits: Divide the dataset into two subsets based on a binary
condition.
Example: A decision tree node might test whether the "Temperature" is "Hot".
Visual Representation:
[Temperature = Hot]
/ \
Yes (True) No (False)

Dr. Suresh Chimkode

 Methods for expressing attribute test conditions Decision Trees..
2. Multi-way Splits: Split the dataset into multiple subsets based on
categorical values.
Example: For the attribute "Outlook" with values {Sunny, Overcast, Rainy}.
Visual Representation:
[Outlook]
/ | \
Sunny Overcast Rainy

3. Range-based Splits: Split numeric attributes into ranges.

Example: For the attribute "Age", the decision tree might have ranges like
"< 18", "18-40", and "> 40".
[Age]
/ | \
< 18 18-40 > 40

Dr. Suresh Chimkode

 Methods for expressing attribute test conditions Decision Trees..
4. Nominal and Ordinal Attributes:
Nominal: No inherent order among categories.
Example: Attribute "Color" with values {Red, Green, Blue}.
[Color]
/ | \
Red Green Blue
Ordinal: Inherent order among categories.
Example: Attribute "Education Level" with values {High School, Bachelor’s,
Master’s}.
[ Education Level ]
/ | \ .. …
High School Bachelor’s Master’s

Dr. Suresh Chimkode

 Methods for expressing attribute test conditions Decision Trees..
5. Complex Conditions: Combine multiple attributes to form a test condition.
Example: Combining "Age" and "Income" attributes to form a condition.
[Age < 30 AND Income > 50k]
/ \
Yes (True) No (False)

These methods help decision trees to handle a variety of data types and
complexities, enabling them to create accurate and interpretable models.

Dr. Suresh Chimkode

Explain with example following measures for selecting best split in decision
trees.
1. Gain ratio
2. Gini Index

Gain ratio

 Gain Ratio is a metric used in decision tree algorithms, to select the

attribute that best splits the data by overcoming the bias towards
attributes with many values that is inherent in Information Gain.
 Gain Ratio normalizes Information Gain to account for the number
and size of branches, preventing bias towards attributes with many
unique values.
 It ensures the selected attribute provides meaningful and balanced
splits.

Dr. Suresh Chimkode

 Gain ratio.. …

Gain Ratio Works as:

1. Calculate Information Gain (IG)

Where H(D) is the entropy of the dataset D, and Dv is th

e subset of D for attribute A with value v.
2. Calculate Split Information (SI):
Split Information quantifies how uniformly or randomly
the data is split among the branches. It’s calculated as:

Where: D is the dataset, A is the attribute,

Dv is the subset of D where
attribute A has value v.
3. Calculate Gain Ratio (GR)

Dr. Suresh Chimkode

 Gain ratio.. …
Example: Weather Dataset
Let's consider a simplified weather dataset for predicting whether to
play tennis.
Calculate Information Gain for "Outlook":
1. Entropy of the entire dataset H(D):
9 ‘Yes’ and 5 ‘No’ instances among 14 instances

2. Entropy for each subset:

Sunny:

Overcast:
Rainy: Sunny 2 Yes + 3 No = 5
Overcast 4 Yes = 4
Rainy 3 Yes + 2 No = 5
3. Weighted Entropy for "Outlook":

Dr. Suresh Chimkode

 Gain ratio.. …
Calculate Information Gain for "Outlook“… ..
4. Information Gain for "Outlook":
IG(D,Outlook) = H(D) - H(D, Outlook)

Calculate Split Information for "Outlook":

Calculate Gain Ratio for "Outlook":

A Gain Ratio of 0.16 for the "Outlook" attribute indicates that when
considering the "Outlook" attribute to split the dataset, it provides a
moderate balance between its ability to split the data (measured by
Information Gain) and the number of unique values (measured by Split
Information).
Information Gain alone shows how well "Outlook" separates the classes (play or not play
tennis).
Gain Ratio adjusts this by considering how many ways the dataset is split when using "Outlook".
Dr. Suresh Chimkode
 Gini Index
 The Gini Index is a measure of impurity or purity used in decision
tree algorithms to select the best attribute for splitting the data.
 It quantifies the likelihood of an incorrect classification of a
randomly chosen element from the dataset if it were labeled
according to the distribution of labels in the subset.
 A lower Gini Index indicates a purer node, meaning a better split.
Formula:

Where, Gini(D) is the Gini Index for dataset D. Pi is the proportion

of instances of class i in the dataset. n is the number of classes.
Significance of Gini index:
Impurity Measurement: The Gini Index helps in measuring the impurity
of a node, guiding the algorithm in creating purer splits.
Decision Making: It helps in selecting the attribute that will best
separate the data into classes, improving the classification
performance of the decision tree. Dr. Suresh Chimkode
 Gini Index
Consider a simplified weather dataset to illustrate how the Gini Index
works. The goal is to decide whether to play tennis based on the
weather conditions.
Steps to Calculate the Gini Index for each subset
based on the "Outlook" attribute.

1. Sunny:

Dr. Suresh Chimkode

 Gini Index
Steps to Calculate the Gini Index for each subset
based on the "Outlook" attribute.

2. Overcast:

Dr. Suresh Chimkode

 Gini Index
Steps to Calculate the Gini Index for each subset
based on the "Outlook" attribute.

3. Rainy:

Dr. Suresh Chimkode

 Gini Index
Steps to Calculate the Gini Index for each subset
based on the "Outlook" attribute.

4. Weighted Gini Index for "Outlook":

 The Gini Index helps in selecting the "Outlook" attribute as it results

in a relatively low weighted Gini Index, indicating it is a good split
that creates purer nodes.
 This metric guides the decision tree in making effective splits,
leading to improved classification performance.
Dr. Suresh Chimkode
 Algorithms for Decision tree Induction
Explain with example, algorithms for Decision tree Induction

 Decision tree induction is a process of generating a decision tree from

a dataset.
 It involves several algorithms that build the tree by recursively
splitting the dataset into subsets based on the most significant
attribute.

Few key algorithms are:

1. ID3 (Iterative Dichotomiser 3)

ID3 uses Information Gain to select the attribute that will best separate
the data into classes. It works by choosing the attribute with the highest
Information Gain as the root node, then recursively builds the tree.
Example: Weather dataset to predict "PlayTennis" (yes/no).
Steps.. ..
Dr. Suresh Chimkode
 Algorithms for Decision tree Induction
ID3 Steps:
 Calculate the entropy of the entire dataset.
 Calculate the Information Gain for each attribute.
 Select the attribute with the highest Information Gain (e.g.,
"Outlook").
 Split the dataset based on the selected attribute.
 Repeat the process for each subset.

2. C4.5
C4.5, an extension of ID3, uses Gain Ratio instead of Information Gain to
select the best attribute, addressing the bias towards attributes with
many values.
Example: Continuing with the weather dataset.
Steps..
Dr. Suresh Chimkode
 Algorithms for Decision tree Induction
C4.5 Steps:
 Calculate the Information Gain for each attribute.
 Calculate the Split Information for each attribute.
 Calculate the Gain Ratio for each attribute.
 Select the attribute with the highest Gain Ratio.
 Split the dataset based on the selected attribute.
 Repeat the process for each subset.

3. CART (Classification and Regression Trees)

CART uses the Gini Index to measure the impurity of a split. It
constructs binary trees, meaning each node has exactly two children.
Example: Again, using the weather dataset.
Steps:
 Calculate the Gini Index for each attribute.
 Select the attribute with the lowest Gini Index.
 Split the dataset based on the selected attribute.
 Repeat the process for each subset.
Dr. Suresh Chimkode
 Algorithms for Decision tree Induction
Detailed Example: ID3 on Weather Dataset
1. Calculate Entropy of Entire Dataset:

2. Calculate Information Gain for "Outlook":

Sunny:

Overcast:

Rainy:
3. Weighted Entropy for "Outlook":

4. Information Gain for "Outlook":

 Using these calculations, the "Outlook" attribute provides the best
split. The tree starts with "Outlook" and proceeds to recursively split
the dataset based on the next best attributes.
Dr. Suresh Chimkode
 Naive Bayes Classifier
Discuss about Naive Bayes Classifier.
Definition:

Naive Bayes is a probabilistic classification algorithm based on Bayes'

Theorem, with the "naive" assumption that features are independent
given the class label.

Bayes' Theorem:

Bayes' Theorem forms the foundation of the Naive Bayes classifier. It is

expressed as,
Where,
o P(C∣X) is the posterior probability of class C given the feature vector
X.
o P(X∣C) is the likelihood of feature vector X given class C.
o P(C) is the prior probability of class C.
o P(X) is the evidence, which is a normalizing constant.
Dr. Suresh Chimkode
 Naive Bayes Classifier
Discuss about Naive Bayes Classifier.. …
Naive Assumption
• The "naive" part assumes that each feature is conditionally independent of
the others given the class label.
• This simplifies the computation as
Types of Naive Bayes Classifiers
Gaussian Naive Bayes: Assumes that features follow a Gaussian (normal)
distribution.
Multinomial Naive Bayes: Used for discrete features like word counts in text
classification.
Bernoulli Naive Bayes: Used for binary/boolean features.
Training and Prediction
 Training: Calculate the prior probabilities for each class. Then
Calculate the likelihood of each feature given each class.
 Prediction: For a given feature vector, compute the posterior
probability for each class. Then Predict the class with the highest
posterior probability.
Dr. Suresh Chimkode
 Naive Bayes Classifier
Discuss about Naive Bayes Classifier.. …

Example: Spam Detection

Imagine we are building a spam email classifier. Features could be the
presence of certain words in the email (e.g., "free", "win", "money").

Steps:

 Calculate the probabilities of each word given "spam" and "not spam".
(i.e., Training)

 For a new email, calculate the posterior probability of "spam" and

"not spam" using the presence of the words in the email then
Classify the email based on the higher posterior probability. (i.e.,
Prediction).

Dr. Suresh Chimkode

 QUESTION
How can the Naive Bayes classifier be applied to detect email spam?
Explain the process using a dataset of emails with features such as the
presence of specific words (e.g., "Free", "Win", "Money", "Dear",
"Meeting"), and include the steps for training the classifier, calculating
prior probabilities, likelihoods, and predicting whether a new email is
spam or not spam.

Problem Statement
Classify emails as either "Spam" or "Not Spam" based on the presence
of certain words.

Training Data
Suppose we have the following dataset with features representing the
presence of specific words:

Dr. Suresh Chimkode

Training the Naive Bayes Classifier
Step 1: Calculate Prior Probabilities

Step 2: Calculate Likelihoods: Calculate the likelihood of each word

given "Spam" and "Not Spam".

Dr. Suresh Chimkode

Prediction: New Email
Suppose we receive a new email (E7) with the following features:

Step 3:
Calculate Posterior Probabilities

For Spam:

P(Spam|E7) = (3/3) * (2/3) * (2/3) * (1/3) * (0/3) * 0.5

P(Spam|E7) = 0

For Not Spam:

Smoothing to Prevent Zero Probability Issue

To avoid zero probability, we can use Laplace Smoothing. Let’s add 1 to each
count: Recalculate likelihoods with smoothing for Spam & Not Spam
Dr. Suresh Chimkode
Let’s add 1 to each count & Recalculate likelihoods with smoothing for Spam:
P(Free|Spam) = 3+1
3+2 Let’s add 1 to each count & Recalculate likelihoods with
= 4/5 smoothing for Not Spam

Recalculate Posterior Probabilities with

Smoothing For Spam:
P(Spam|E7) = (4/5) * (3/5) * (3/5) * (2/5) * (1/5) * 0.5 = 0.01152
For Not Spam:

Since P(Spam∣E7)>P(Not_Spam∣E7) i.e, 0.01152 > 0.00096, we classify the

new email (E7) as Spam. Dr. Suresh Chimkode
K-Nearest Neighbor classifier
Discuss about K-Nearest Neighbor classifier algorithm and its characteristics.
 It is a non-parametric, instance-based learning algorithm, which means it
makes decisions based on the instances closest to the new data point. KNN
algorithm is a used in machine learning.

K-Nearest Neighbors Works as:

1. Training Phase: There is no explicit training phase with KNN. Instead, the
training data is stored, and the algorithm uses this data for classification.

 For a new data point, the algorithm finds the 𝑘 nearest neighbors among
2. Classification Phase:

the training data. The value of 𝑘 is a user-defined constant.

 The distance between the new data point and the training data points is
calculated using a distance metric such as Euclidean distance, Manhattan

 The algorithm counts the class labels of the 𝑘 nearest neighbors.

distance, or others.

its 𝑘 nearest neighbors (majority voting).

 The new data point is assigned the class label that is most frequent among

Dr. Suresh Chimkode

K-Nearest Neighbor classifier…
Characteristics of K-Nearest Neighbors:
1. Simplicity:
KNN is easy to understand and implement. It doesn't involve complex training
processes or parameter tuning.
2. Instance-Based Learning:
KNN is a lazy learning algorithm, meaning it doesn't learn an explicit model.
Instead, it makes decisions based on the stored instances.
3. Distance Metrics:
The performance of KNN heavily depends on the choice of distance metric.
Commonly used metrics include Euclidean, Manhattan, and Minkowski

4. Parameter 𝑘:
distances.

The value of 𝑘 is crucial for the algorithm's performance. A small 𝑘 can lead to
overfitting, while a large 𝑘 can lead to underfitting. Selecting an appropriate 𝑘
is often done through cross-validation.
5. Computational Complexity:
KNN can be computationally expensive, especially with large datasets, since it
requires calculating distances to all training data points. Efficient data
structures like KD-trees and Ball-trees can helpDr.
speed up the
Suresh process.
Chimkode
K-Nearest Neighbor classifier…
Characteristics of K-Nearest Neighbors:
6. Non-Parametric:
KNN does not make any assumptions about the underlying data distribution,
making it a non-parametric algorithm.
7. Versatility:

the prediction is usually the mean of the values of 𝑘 nearest neighbors.

KNN can be used for both classification and regression tasks. For regression,

Example:
Suppose we have a dataset with two features (height and weight) and two
classes (athlete and non-athlete). To classify a new instance, we:

2. Select the 𝑘 nearest neighbors.

1. Calculate the distance between the new instance and all training instances.

3. Determine the most common class among these neighbors.

4. Assign this class to the new instance.

Dr. Suresh Chimkode

K-Nearest Neighbor classifier…
Illustration of previous example, consider a dataset with two features (height
and weight) and two classes (athlete and non-athlete).

Height (cm) Weight (kg) Class

170 65 Athlete
160 70 Non-Athlete
180 80 Athlete
150 55 Non-Athlete
175 75 Athlete

1. Determine the Value of 𝑘

Step-by-Step Process

Let's choose 𝑘 = 3
2. New Data Point
We want to classify a new data point: Height = 165 cm, Weight = 68 kg.
3. Calculate the Distance
We'll use the Euclidean distance to calculate the distance between the new
data point and each point in the dataset.
Dr. Suresh Chimkode
The Euclidean distance formula for two points (𝑥1, 𝑦1) and (𝑥2, 𝑦2) is:
Illustration of K-Nearest Neighbor classifier…

Calculate the distances:

1. To (170, 65)

2. To (160, 70)

3. To (180, 80)

4. To (150, 55)

5. To (175, 75)

4. Find the 𝑘 Nearest Neighbors

 select the 𝑘= 3 nearest neighbors

 Sort the distances and

Dr. Suresh Chimkode

Illustration of K-Nearest Neighbor classifier…

5. Majority Voting
Among the 3 nearest neighbors:
 2 are Athletes
 1 is a Non-Athlete
The majority class is Athlete.

6. Classify the New Data Point

The new data point (Height = 165 cm, Weight = 68 kg) is classified as Athlete.

These steps K-Nearest Neighbors algorithm uses to classify a new data point

the 𝑘 nearest neighbors.

based on its distance to the training data points and majority voting among
Dr. Suresh Chimkode
 OU
KY
AN

ws
TH

Fo ’s?
llo
Dr. Suresh Chimkode