Classification
Dr. Vimal K. Shrivastava
Assistant Professor (II)
School of Electronics Engineering
KIIT Deemed to be University,
Bhubaneswar
Classification
In classification, the data is categorized under different labels
(classes).
Here, we want to know which class the input belongs to.
Output is categorical (discrete value).
Examples:
Spam mail filtering: Classifies the mails in regular or
spam.
Digit recognition service: Classifies the digit image into
0 to 9.
2
Dr. Vimal Shrivastava
Classification Techniques
• There are many classification techniques:
• Logistic Regression
• K-Nearest Neighbors
• Decision Tree
• SupportVector Machine
• Artificial Neural Network
3
Dr. Vimal Shrivastava
Logistic Regression
Logistic Regression is an extension of Linear regression where the
dependent variable is categorical and not continuous.
It predicts the output of a categorical variable, which is discrete in
nature.
Hence, it is a classification algorithm and a supervised machine
learning technique.
It can be either Yes or No, 0 or 1, true or False, etc. i.e. binary
outcome.
However, instead of giving the exact value as 0 and 1, it gives the
output as the probability which lies between 0 and 1.
4
Dr. Vimal K. Shrivastava
The logistic regression model transforms the continuous
output of linear regression into categorical output using a
sigmoid function.
It maps any real-valued set of independent variables input
into a value between 0 and 1.
Let the independent input features be:
The dependent variable is Y having only binary value i.e. 0 or
1.
5
Now, apply the linear function to the input variables X:
Now we use the sigmoid function where the input will be z
and we find the probability between 0 and 1. i.e. predicted y.
1
𝜎 𝑧 =
1 + 𝑒− 𝑤.𝑋+𝑏
6
As shown in the figure sigmoid function converts the
continuous variable data into the probability i.e. between 0
and 1.
where the probability of being a class can be measured as:
7
• Consider the following example where the data points belong to
one of the two categories:
• A threshold (usually 0.5) is then used to categorize the data into
one of the two categories.
8
Training of Logistic Regression Model
It is known as log-loss or binary cross-entropy loss function.
To find the coefficients (weights) that minimize the loss
function we will use Gradient Descent.
𝜕(𝐿𝑜𝑠𝑠)
𝑊𝑗 =𝑊𝑗 −L
𝜕𝑊𝑗
9 [Link]
K–Nearest Neighbor (KNN)
It is one of the simplest and widely used classification
algorithm.
It is based on Supervised Learning technique.
It relies on the idea that similar data points tend to have
similar class labels.
KNN predicts the class label of a new data point by
considering its K closest neighbors in the training dataset.
10
Dr. Vimal Shrivastava
KNN Algorithm
Step 1: Divide the dataset into training and test set.
Step 2: Choose the value of K i.e. the nearest data points. K should be
integer.
Step 3: For each data point in the test set do the following:
3.1: Calculate the distance between test data and each training data
using Euclidean distance.
3.2: Now, based on the distance value, sort them in ascending order.
3.3: Next, it will choose the top K training data from the sorted
array.
3.4: Now, it will assign a class to the test data based on most frequent
class of these rows.
11
Dr. Vimal Shrivastava
Distance Metrics
• Usually, we use the Euclidean approach, which is the most widely used
12
distance measure
KNN Example
Suppose we have a dataset which can be plotted as follows:
13
Dr. Vimal Shrivastava
KNN Example
Now, we need to classify new data point with black dot into blue
or red class. We are assuming K = 3 i.e. it would find three nearest
data points.
We can see in the above diagram that the three nearest neighbors
of the data point with black dot. Among those three, two of them
lies in Red class hence the black dot will also be assigned in red
14
class.
Determining the Optimal K
• As you can verify from the figure, if we proceed with K=3,
then we predict that test input belongs to class B, and if we
continue with K=7, then we predict that test input belongs to
class A.
• That’s how you can imagine that the K value has a powerful
effect on KNN performance.
15
Choosing the right K value is important for getting accurate
results with the [Link] cases could arise:-
1. The K value is too less, and it leads to underfitting if the K value
is too less, i.e., if we select K=1 or K=2, we would be only
looking at a very small number of neighbors and hence won't be
utilizing the full scope of the data.
2. The K value is too large, which may lead to overfitting. If the K
value is too large, we might consider a lot of outliers, which
would lead to inaccurate results.
One way to find the optimal K value is the square root of
N, where N is the total number of samples.
Another way is: Elbow method.
16
Elbow Method
Initialize a random K value and start computing.
Draw a plot between error rate and K denoting values in a
defined range.
Then choose the K value as having a minimum error rate.
From the plot, you can see that the smallest error we got is
0.59 at K=37.
17
Pros and Cons of KNN
Pros Cons
1. Easy to understand. 1. Memory Intensive /
2. No assumptions about Computationally
data. expensive.
3. Can be applied to both 2. Sensitive to scale of data.
classification and 3. Not work well on highly
regression. imbalanced dataset.
4. Works easily on multi- 4. Struggle when high
class problems. number of independent
variables.
18
Problem 01:
19
Dr. Vimal Shrivastava
Solution
20
Dr. Vimal Shrivastava
21
Dr. Vimal Shrivastava
22
Classification Model Evaluation
Confusion Matrix
A confusion matrix is a tabular way of visualizing the performance of
the model.
A Confusion matrix is an N x N matrix used for evaluating the
performance of a classification model, where N is the number of
target classes.
The matrix compares the actual target values with those predicted by
the machine learning model.
This gives us a holistic view of how well our classification model is
performing and what kinds of errors it is making.
For a binary classification (two class problem), we would have a 2 x 2
matrix as shown below with 4 values:
23
Dr. Vimal Shrivastava
Confusion Matrix for Binary Classification:
True Positive (TP): It refers to the number of predictions where
the classifier correctly predicts the positive class as positive.
True Negative (TN): It refers to the number of predictions where
the classifier correctly predicts the negative class as negative.
False Positive (FP): It refers to the number of predictions where
the classifier incorrectly predicts the negative class as positive. It is
also known as Type-I error.
False Negative (FN): It refers to the number of predictions where
the classifier incorrectly predicts the positive class as negative. It is
24 also known as Type-II error.
Problem 1:
• Find TP, TN, FP and FN.
• Solution:
• True Positive (TP) = 560; meaning 560 positive class data points were
correctly classified by the model.
• True Negative (TN) = 330; meaning 330 negative class data points were
correctly classified by the model.
• False Positive (FP) = 60; meaning 60 negative class data points were
incorrectly classified as belonging to the positive class by the model.
• False Negative (FN) = 50; meaning 50 positive class data points were
incorrectly classified as belonging to the negative class by the model.
25
Dr. Vimal Shrivastava
Performance Measures from the
Confusion Matrix
Accuracy: It gives the overall accuracy of the model, meaning
the fraction of the total samples that were correctly classified by
the classifier.
Accuracy = (TP+TN)/(TP+TN+FP+FN)
Misclassification Rate: It tells that what fraction of predictions
were incorrect. It is also known as Classification Error.
Misclassification Rate = (FP+FN)/(TP+TN+FP+FN) or
Misclassification Rate = (1-Accuracy)
26
Dr. Vimal Shrivastava
Why Do We Need a Confusion Matrix?
Why Do We Need Other Parameters?
Let’s say there are two values for our target variable: Sick and
Not Sick.
Our dataset is an example of an imbalanced dataset. There
are 947 data points for the negative class (Not Sick) and 53
data points for the positive class (Sick).
• Let’s say the total outcome values
are:
TP = 30, TN = 930,
FP = 30, FN = 10
• So, the accuracy of our model turns
out to be:
• 96%! Not bad!
But it gives the wrong idea about the result for an imbalanced
dataset.
The model is saying, “I can predict accurately 96% of the time”.
However, it is unable to predict correctly the 10 sick cases
(FN=10).
This is where we come across the confusion matrix and other
performance parameters like Precision, Recall and F1-Score.
28
Dr. Vimal Shrivastava
Precision: It tells that what fraction of predictions as a positive class were
actually positive.
Precision is a useful metric in cases where False Positive is a higher concern
than False Negatives.
Precision is important in music or video recommendation systems, e-commerce
websites, etc. Wrong results could lead to customer churn and be harmful to
the business.
Precision = TP/(TP+FP)
Recall: It tells that what fraction of all positive samples were correctly
predicted as positive by the classifier. It is also known as True Positive Rate
(TPR) or Sensitivity.
Recall is a useful metric in cases where False Negative is a higher concern than
False Positive.
Recall is important in medical cases where it doesn’t matter whether we raise a
false alarm, but the actual positive cases should not go undetected!
Recall =TP/(TP+FN)
29
• 50% percent of the correctly predicted cases
turned out to be positive cases.
• Whereas 75% of the positives were
successfully predicted by our model.
But there will be cases where there is no clear distinction between
whether Precision is more important or Recall. What should we do in
those cases? We combine them!
In practice, when we try to increase the precision of our model, the
recall goes down, and vice-versa.
The F1-score captures both the trends in a single value.
Specificity: It tells that what fraction of all negative samples are
correctly predicted as negative by the classifier. It is also known as True
Negative Rate (TNR).
31
Specificity =TN/(TN+FP)
Confusion Matrix for Multi-Class
Classification
For simplicity, let’s consider our multi-class classification problem to be
a 3-class classification problem.
Say, we have a dataset that has three class labels, namely Apple, Orange
and Mango.
We have to find TP,TN, FP and FN for each individual class.
For example, if we take class Apple, then let’s see what are the values of
32 the metrics from the confusion matrix.
Dr. Vimal Shrivastava
TP = 7
TN = (2+3+2+1) = 8
FP = (8+9) = 17
FN = (1+3) = 4
Now, we can calculate the performance measures for class Apple.
Precision = 7/(7+17) = 0.29
Recall = 7/(7+4) = 0.64
33
Dr. Vimal Shrivastava
Similarly, we can calculate the measures for the other classes.
34
Dr. Vimal Shrivastava
Problem 2:
• Find TP, TN, FP and FN and other performance parameters.
• Solution:
• TP=100; TN=50; FP=10; FN=5
• Accuracy: Overall, how often is the classifier correct?
(TP+TN)/total = (100+50)/165 = 0.91
• Misclassification Rate: Overall, how often is it wrong?
(FP+FN)/total = (10+5)/165 = 0.09
• Equivalent to 1 minus Accuracy also known as "Error Rate"
35
Dr. Vimal Shrivastava
True Positive Rate: When it's actually yes, how often
does it predict yes?
TP/actual yes = 100/105 = 0.95
also known as "Sensitivity" or "Recall“
True Negative Rate: When it's actually no, how often
does it predict no?
TN/actual no = 50/60 = 0.83
also known as "Specificity“
False Positive Rate: When it's actually no, how often
does it predict yes?
FP/actual no = 10/60 = 0.17
equivalent to 1 minus True Negative Rate
Precision:When it predicts yes, how often is it correct?
TP/predicted yes = 100/110 = 0.91
36
Dr. Vimal Shrivastava
Problem 3:
Define the following terms associated with confusion matrix.
i. Accuracy
ii. Misclassification
iii. Precision
iv. Sensitivity
v. Specificity
Thus, compute these metrics for the confusion matrix given
below.
37
Dr. Vimal Shrivastava
Receiver Operating Characteristics
(ROC) Curve
It is one of the most important evaluation metrics for checking
any classification model’s performance.
An ROC curve is a graph showing the performance of a
classification model at all classification thresholds.
By looking at this graph, we can understand how good the model
is and choose the threshold that gives us the right balance between
correct and incorrect predictions.
The ROC curve is plotted with True Positive Rate (TPR) against
the False Positive Rate (FPR) where TPR is on the y-axis and FPR
38
is on the x-axis.
Dr. Vimal Shrivastava
• Have a look at the table below:
• The metrics change with the changing threshold values.
39
[Link]
40
795b1399481c#:~:text=To%20plot%20the%20ROC%20curve,That's%20it!
Area Under The ROC Curve (AUC)
AUC represents the degree or measure of separability.
Higher the AUC, the better the model is at predicting 0 classes as
0 and 1 classes as 1.
Ex: The Higher the AUC, the better the model is at distinguishing
between patients with the disease and no disease.
An excellent model has AUC near to the 1 which means it has a
good measure of separability.
A poor model has an AUC near 0 which means it has the worst
measure of separability.
41
Dr. Vimal Shrivastava
42 Dr. Vimal Shrivastava
43 Dr. Vimal Shrivastava
Naïve Bayes Classifier
A Naive Bayes classifier is a probabilistic machine learning
model that’s used for classification task.
It is based on Bayes’Theorem.
The assumption made here is that the features are
independent. That is presence of one particular feature does
not affect the other. Hence it is called naive.
Naive Bayes model is easy to build and particularly useful for
very large data sets.
Dr. Vimal Shrivastava
Bayes' Theorem
In probability theory , Bayes’ theorem explains the probability of
most probable event, based on prior given conditions that might
be related to the event.
For example, if any disease is related to age, then, using Bayes’
theorem, a person’s age can be used to more accurately assess the
probability that they have similar disease, compared to the
judgement of the probability of disease made without knowledge
of the person’s age.
Bayes' theorem is used to compute the conditional probability of
an event using prior knowledge.
45
Dr. Vimal Shrivastava
Bayes Theorem Derivation
• Proof:
• From the definition of conditional probability:
• P(A|B) = P(A ⋂ B)/ P(B), where P(B) ≠ 0
• P(B|A) = P(B ⋂ A)/ P(A), where P(A) ≠ 0
• Here, the joint probability P(A ⋂ B) of both events A and B being
true such that,
• P(B ⋂ A) = P(A ⋂ B)
• P(A ⋂ B) = P(A | B) P(B) = P(B | A) P(A)
46
47
• Bayes’ theorem is stated mathematically as the following equation:
• where,
• A and B are events and P(B)≠0.
• P(A|B) is conditional probability: the likelihood of event A
occurring given that B is true.
• P(B|A) is also a conditional probability :the likelihood of event B
occurring given that A is true.
• P(A) and P(B) are probabilities of observing A and B
independently, this is known as marginal probability.
48 Dr. Vimal Shrivastava
Example:
Step 1: (A) Find Individual probabilities:
Suppose, we have 2 boxes A and B, then we have to calculate the
probability of selecting the boxes.
It is simple, since we have to select one box out two so:
P(A) = 1/2 and P(B) = 1/2
What if individual probabilities are given:
P(A) = 60%, P(B) = 30% and P(C) = 10%
P(A) = 0.6, P(B) = 0.3 and P(C) = 0.1
49
Dr. Vimal Shrivastava
Step 2 : (B) Find conditional probability:
It is represented as P(x|A) here x is selecting element from
set of A.
Suppose, we have a box contains 5 red and 3 white balls.
Calculate the probability of selecting red ball from the box.
P(R|A) = (red ball)/(total number of balls) = 5/8
50
Dr. Vimal Shrivastava
Naive Bayes Classifier
Example:
Consider the weather [Link] dataset is represented as below.
51
Dr. Vimal Shrivastava
We have to classify whether the day is suitable for playing golf, given the
features of the day.
According to this example, Bayes theorem can be rewritten as:
The variable y is the class variable (play golf), which represents if it is
suitable to play golf or not given the conditions.
Variable X represents the features which is given as:
Here x1, x2,….xn represent the features, i.e. they can be mapped to
outlook, temperature, humidity and windy.
52
Dr. Vimal Shrivastava
By substituting for X and expanding using the chain rule we get:
Now, you can obtain the values for each by looking at the dataset
and substitute them into the equation.
For all entries in the dataset, the denominator does not change, it
remain static. Therefore, the denominator can be removed and a
proportionality can be introduced.
53
Dr. Vimal Shrivastava
In this example, the class variable (y) has only two outcomes, yes
or no.
There could be cases where the classification could be
multivariate. Therefore, we need to find the class y with maximum
probability.
Using the above function, we can obtain the class, given the
features.
54
Dr. Vimal Shrivastava
• Let us apply the above formula manually on weather dataset. For this,
we need to do some precomputations on our dataset.
55
We need to find P(xi|yj) for each xi in X and yj in y. All these
calculations have been demonstrated in the tables below:
56
Dr. Vimal Shrivastava
Let us test it on a new set of features (let us call it today):
today = (Sunny, Hot, Normal, False)
57
Dr. Vimal Shrivastava
58 Dr. Vimal Shrivastava
Pros and Cons of Naive Bayes
Pros:
It is easy and fast to predict class of test dataset.
When assumption of independence holds, a Naive Bayes classifier
performs better compare to other models like logistic regression and we
need less training data.
It perform well in case of categorical input variables compared to
numerical variable(s). For numerical variable, normal distribution is
assumed (bell curve, which is a strong assumption).
Cons:
If categorical variable has a category (in test data set), which was not
observed in training data set, then model will assign a 0 (zero)
probability and will be unable to make a prediction. This is often known
as “Zero Frequency”.
Another limitation of Naive Bayes is the assumption of independent
predictors. In real life, it is almost impossible that we get a set of
predictors which are completely
Dr. Vimal independent.
Shrivastava
Decision Tree (DT)
Example 2
63
• In the below diagram the tree will first ask what is the
weather? Is it sunny, cloudy, or rainy?
• If not cloudy then it will go to the next feature which is
humidity and wind.
• It will again check if there is a strong wind or weak, if it’s
rainy and weak wind then the person may go and play.
64
Dr. Vimal Shrivastava
Example 3
A decision tree is a flowchart-like a tree structure where an internal
node represents feature (or attribute), the branch represents a
decision rule, and each leaf node represents the outcome.
Decision trees are nothing but a bunch of if-else statements in
layman terms. It checks if the condition is true and if it is then it
goes to the next node attached to that decision.
Root Nodes – It is the node present at the beginning of a decision
tree from this node the population starts dividing according to
various features.
Decision Nodes – the nodes we get after splitting the root nodes
are called Decision Node
Leaf Nodes – the nodes where further splitting is not possible are
called leaf nodes or terminal nodes
Sub-tree – just like a small portion of a graph is called sub-graph
67
similarly a sub-section of this decision tree is called sub-tree.
68
ID3 (Iterative Dichotomiser 3) Algorithm
Entropy
Entropy is nothing but the uncertainty in our dataset or measure
of disorder.
More knowledge less Entropy or More uncertainty higher the
Entropy.
How to calculate Entropy?
Ex: For two class problem:
Here p+ is the probability of positive class
p– is the probability of negative class
S is the subset of the training example
69
Dr. Vimal Shrivastava
Example: 01
70
Example: 02
71
Dr. Vimal Shrivastava
Entropy for 3 Class Problem
72
Dr. Vimal Shrivastava
Observations
73
Dr. Vimal Shrivastava
Entropy vs. Probability
74
Information Gain
Information gain measures the reduction of uncertainty given
some feature i.e., the information gain is based on the decrease in
entropy after a dataset is split on an feature.
It is also a deciding factor for which feature/attribute should be
selected as a decision node or root node.
75
Example: 01
76
77
78
79
80
Example: 02
Suppose the entire population has a total of 30 instances. The dataset is
to predict whether the person will go to the gym or not. Let’s say 16
people go to the gym and 14 people don’t.
Now we have two features to predict whether he/she will go to the gym
or not.
Feature 1 is “Energy” which takes two values “high” and “low”.
Feature 2 is “Motivation” which takes 3 values “No motivation”, “Neutral”
and “Highly motivated”.
Let’s see how our decision tree will be made using these 2 features.
We’ll use information gain to decide which feature should be the root
node and which feature should be placed after the split.
81
Dr. Vimal Shrivastava
Let’s calculate the entropy:
To see the weighted average of entropy of each node we will do as follows:
82
Dr. Vimal Shrivastava
Now we have the value of E(Parent) and E(Parent|Energy),
information gain will be:
Our parent entropy was near 0.99 and after looking at this
value of information gain, we can say that the entropy of the
dataset will decrease by 0.37 if we make “Energy” as our root
node.
Similarly, we will do this with the other feature “Motivation”
and calculate its information gain.
83
Dr. Vimal Shrivastava
Let’s calculate the entropy here:
84
Dr. Vimal Shrivastava
To see the weighted average of entropy of each node we will do as
follows:
Now we have the value of E(Parent) and E(Parent|Motivation),
information gain will be:
We now see that the “Energy” feature gives more reduction which is
0.37 than the “Motivation” feature. Hence we will select the feature
which has the highest information gain and then split the node based on
that feature.
85
Dr. Vimal Shrivastava
Example: 03
• This dataset has 10 instances and four numbers of attributes. Here, first
three attributes are predictor and the last attribute is the target attribute.
86
Dr. Vimal Shrivastava
Solution:
E(Profit) = 1
E(Age=old) = 0 Age Down Up
E(Age=mid) = 1 Old 3 0
E(Age=new)= 0 Mid 2 2
E(Age) = 0.4 New 0 3
IG = 1 - 0.4
= 0.6
Similarly,
E(Competition=yes) = 0.81
E(Competition=no) = 0.91
E(Competition)= 0.88
IG(Competition)= 0.12
87
Dr. Vimal Shrivastava
E(Type=software) = 1
E(Type=hardware) = 1
E(Type) = 1
IG(Type) = 0
So, Gain of (age, competition, type)
Information Gain of age = 0.6
Information Gain of competition = 0.12
Information Gain of type = 0
As Age has a max gain as compared to others so age becomes a
root node.
88
Dr. Vimal Shrivastava
So age has three attributes which are Old, mid and new.
For old age target attribute, all goes down. So make a leaf
node for old which is down.
89
Dr. Vimal Shrivastava
For new age target attribute all go up. So make a leaf node for new
age.
Now what is for mid? Because mid age has 2 cases.
So who becomes the child node of mid.
We take that attribute for which information gain is higher among
Competition and Type.
Information Gain of competition = 0.12
Information Gain of type = 0
90
Dr. Vimal Shrivastava
So, Information Gain of
Competition is Greater than
Type, so Competition
becomes the child node of
mid.
Now, make a leaf node for
competition. If the
competition is yes then the
profit will down and if
competition no then profits
up.
91 Dr. Vimal Shrivastava
Gini Impurity (Gini Index)
Gini impurity is a measure used to quantify a dataset’s impurity
level or disorder.
It is one of the methods used in decision tree algorithms to
decide the optimal split from a root node, and subsequent splits.
It ranges from 0 to 0.5, where 0 indicates a perfectly pure node
(all instances belong to the same class), and 0.5 signifies
maximum impurity (an equal distribution of classes).
Gini Impurity is calculated using the formula:
Ex: For 2-class dataset:
92
Example
93
Entropy v/s Gini Impurity
94
Gini Impurity Entropy
Formula for the Gini index is Formula for entropy is:
GI = 1 – ∑(Pi)^2 , Entropy = -∑(Pi)log(Pi),
where Pi is probability of class i. where pi is probability of class i.
It is the probability of Entropy measures the amount
misclassifying a randomly of uncertainty or randomness in
chosen element in a set. a set.
For binary classification, the For binary classification, the
range of the Gini index is [0, range of the Entropy is [0, 1],
0.5], where 0 indicates perfect where 0 indicates perfect purity
purity and 0.5 indicates and 1 indicates maximum
maximum impurity. impurity.
Gini index is a linear measure. Entropy is a logarithmic
measure.
The computational complexity
The computational complexity
of Entropy is more.
of the Gini index is less.
It is more robust than Gini
95 It is less robust than entropy.
index.
Overfitting and Underfitting in Decision Tree
96
97
98
99
Pruning
Pruning is a technique associated with decision trees.
Pruning reduces the size of decision trees by removing parts of the
tree.
Effective pruning can reduce the overfitting.
There are two types of pruning:
Pre-pruning and
Post-pruning.
100
Dr. Vimal Shrivastava
Pre-pruning
The pre-pruning technique is tuning the hyper-parameters
prior to the training pipeline.
It is also known as ‘early stopping’ which stops the growth of
the decision tree - preventing it from reaching its full depth.
During each stage of the splitting of the tree, the cross-
validation error will be monitored.
Cross-validation is the process of building a tree with most of
the data and then using the remaining part of the data to test
the accuracy of the decision tree.
101
Dr. Vimal Shrivastava
If the value of the error does not decrease anymore - then we
stop the growth of the decision tree.
The hyper-parameters that can be tuned for early stopping
and preventing overfitting are: max_depth.
However, one should be cautious as early stopping can also
lead to underfitting.
102
Dr. Vimal Shrivastava
Post-pruning
Post-pruning does the opposite of pre-pruning and allows the
DecisionTree model to grow to its full depth.
Once the model grows to its full depth, tree branches are
removed to prevent the model from overfitting.
This is done by segregating the actual training set into two
sets: training data set, D and validation data set,V.
Prepare the decision tree using the segregated training data
set, D. Then continue trimming the tree accordingly to
optimize the accuracy of the validation data set,V.
103
Handling Numerical Values in DT
Example:
104
Solution
105
106
107
• Repeat this process for each value of User Rating.
108
Step 3 Step 4
109
110
111
Support Vector Machine (SVM)
A Support Vector Machine (SVM) is a supervised machine learning
algorithm that can be employed for both classification and
regression purposes.
However, it is mostly used in classification problems.
The goal of the SVM algorithm is to create the best decision
boundary that can segregate n-dimensional space into classes so
that we can easily put the test data point in the correct category.
This best decision boundary is called a hyperplane.
112
Dr. Vimal Shrivastava
Hyperplane
A hyperplane is a generalization of a plane.
in one dimension, a hyperplane is called a point.
in two dimensions, it is a line.
in three dimensions, it is a plane.
in more dimensions, we can call it an hyperplane.
113
How does SVM work?
The basic principle behind the working of SVM is to create a
hyperplane that separates the dataset into classes.
Suppose that for a given dataset, we have to classify red squares
from blue circles. Our goal is to create a line that classifies the data
into two classes, creating a distinction between red squares and
blue circles.
114
While one can hypothesize a clear line that separates the two
classes, there can be many lines that can do this job.
Therefore, there is not a single line that you can agree on which
can perform this task.
Let us visualize some of the lines that can differentiate between
the two classes as follows –
115
According to SVM, we have to find the points that lie closest to
both the classes. These points are known as support vectors and
hence, the algorithm is termed as SupportVector Machine
The distance between the support vectors and the dividing line
(decision boundary) is known as margin.
The aim of an SVM algorithm is to maximize this margin.
When the margin reaches its maximum, the hyperplane becomes
the optimal one.
116
Dr. Vimal Shrivastava
• The SVM model tries to maximize the distance between the two
classes by creating a well-defined decision boundary.
• In the above case, hyperplane divided the data. While our data was in
2 dimensions, the hyperplane was of 1 dimension.
• For higher dimensions, say, an n-dimensional Space, we have an
n-1 dimensional hyperplane.
117
Dr. Vimal Shrivastava
What happens when there is no
clear hyperplane?
• This type of dataset is called non-linearly separable dataset.
• In order to classify non-linearly separable dataset like the one above,
we need to map the dataset into a higher dimension space using
kernel functions.
118
Dr. Vimal Shrivastava
Kernel Functions
• The kernel function maps the input data into a higher-dimensional
space where the data becomes linearly separable.
119
Another example of non-linearly separable dataset:
Example 2:
• For mathematical background of SVM:
120 • [Link]
Dr. Vimal Shrivastava
• Example 3:
• To separate the data points as shown below (left), we need to add one
more dimension. For linear data, we have used two dimensions x and y,
so for non-linear data, we will add a third dimension z. It can be
calculated as: 2 2
𝑍 = 𝑥 +𝑦
• By adding the third dimension, the sample space will become as below
image (right):
121
So now, SVM will divide the datasets into classes in the
following way.
Since we are in 3-d Space, hence it is looking like a plane
parallel to the x-axis.
122
SVM can be of two types:
Linear SVM: Linear SVM is used for linearly separable data,
which means if a dataset can be classified into two classes by using
a single straight line, then such data is termed as linearly separable
data, and classifier is used called as Linear SVM classifier.
Non-linear SVM: Non-Linear SVM is used for non-linearly
separated data, which means if a dataset cannot be classified by
using a straight line, then such data is termed as non-linear data
and classifier used is called as Non-linear SVM classifier.
123
Dr. Vimal Shrivastava
Advantages:
Ability to perform well with small datasets.
Ability to handle high-dimensional data.
They also have the ability to model non-linear decision
boundaries, which can be very useful in many applications.
Disadvantages:
SVMs can be sensitive to the choice of kernel.
It can be computationally expensive when the dataset is large.
124
Dr. Vimal Shrivastava
Math behind SVM
Equation of hyperplane: Hard Margin SVM:
Margin: Soft Margin SVM:
[Link]
125 guide-for-beginners/
Hard Margin SVM Vs Soft Margin SVM
126
Numerical on SVM
Graphical representation of the given data
Support vectors:
Illustration of support vectors (marked in yellow):