UNIT-III

CLASSIFICATION
Syallabus :
Part-I

Basic issues regarding classification and predication –

General Approach to solving a classification problem-Decision Tree Classification,
Attribute Selection Measures, Tree Pruning-

Part-II

Bayesian Classification – Rule Based Classification – Support Vector Machines.

Classification Model Evaluation and Selection –Accuracy and Error measures,
Holdout, Random Sampling, Cross Validation, Bootstrap,
Comparing Classifier performance using ROC Curves.

Classification is a form of data analysis that extracts models describing important data
classes. Such models, called classifiers, predict categorical (discrete, unordered) class
labels. For example, we can build a classification model to categorize bank loan
applications as either safe or risky. Such analysis can help provide us with a better
understanding of the data at large. Many classification methods have been proposed by
researchers in machine learning, pattern recognition, and statistics.

Why Classification?
A bank loans officer needs analysis of her data to learn which loan applicants are
“safe” and which are “risky” for the bank. A marketing manager at AllElectronics needs
data analysis to help guess whether a customer with a given profile will buy a new
computer.
A medical researcher wants to analyze breast cancer data to predict which one of
three specific treatments a patient should receive. In each of these examples, the data
analysis task is classification, where a model or classifier is constructed to predict class
(categorical) labels, such as “safe” or “risky” for the loan application data; “yes” or “no”
for the marketing data; or “treatment A,” “treatment B,” or “treatment C” for the medical
data.
Suppose that the marketing manager wants to predict how much a given customer
will spend during a sale at AllElectronics. This data analysis task is an example of numeric
prediction, where the model constructed predicts a continuous-valued function, or ordered
value, as opposed to a class label. This model is a predictor.
Regression analysis is a statistical methodology that is most often used for numeric
prediction; hence the two terms tend to be used synonymously, although other methods for
 numeric prediction exist. Classification and numeric prediction are the two major types of
prediction problems.

Basic issues regarding classification and prediction in data mining include:

1. Data Preparation:
 Data Cleaning:
Handling noise (errors, outliers) and missing values is crucial. Noise can lead to inaccurate
models, and missing values require imputation or removal strategies.
 Relevance Analysis (Feature Selection):
Identifying and removing irrelevant or redundant attributes (features) is important. Irrelevant
features can increase computational cost and potentially mislead the learning process, while
redundant features offer no additional information.
 Data Transformation:
Techniques like normalization or standardization scale data to a specific range, preventing
attributes with larger scales from dominating the learning process, especially in distance-
based algorithms.
2. Model Evaluation and Comparison:
 Accuracy:
Assessing how well the model predicts class labels (for classification) or continuous values
(for prediction). This involves using metrics like accuracy, precision, recall, F1-score for
classification, and mean squared error, mean absolute error for prediction.
 Speed:
Evaluating the computational cost of building (training) and using (predicting with) the
model.
 Robustness:
Determining the model's ability to handle noisy data or data with missing values effectively.
 Scalability:
Assessing the model's efficiency and performance when dealing with large datasets.
 Interpretability:
Understanding the insights and explanations provided by the model, especially important in
domains where transparency is critical.
3. Model Challenges:
 Overfitting:
 Occurs when a model learns the training data too well, including noise, and performs poorly
on unseen data. Techniques like cross-validation, regularization, and early stopping are used
to mitigate this.
 Underfitting:
Occurs when a model is too simple to capture the underlying patterns in the data, leading to
poor performance on both training and test data.
 Bias-Variance Trade-off:
A fundamental concept where reducing bias (simplifying the model) often increases variance
(sensitivity to training data), and vice-versa. Striking the right balance is essential.
 Class Imbalance:
In classification, when one class significantly outnumbers others, the model may become
biased towards the majority class, leading to poor performance on the minority
class. Techniques like oversampling, under sampling, or using cost-sensitive learning can
address this.

General Approach to solving a Classification problem :

Data classification is a two-step process, consisting of a learning step (where a
classification model is constructed) and a classification step (where the model is used to
predict class labels for given data).

 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.
 Each tuple/sample is assumed to belong to a predefined class, as determined by the
class label attribute
 In the second step, the model is used for classification. First, the predictive accuracy of
the classifier is estimated. 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.
 Accuracy rate is the percentage of test set samples that are correctly classified by the
model
 Fig: Learning Step

Fig: Classification Step

Decision Tree Induction:

Decision tree induction is the learning of decision trees from class-labeled training
tuples. A decision tree is a flowchart-like tree structure, where each internal node
(non leaf node) denotes a test on an attribute, each branch represents an outcome of
the test, and each leaf node (or terminal node) holds a class label.
The topmost node in a tree is the root node. Internal nodes are denoted by rectangles,
and leaf nodes are denoted by ovals.
“How are decision trees used for classification?” :
Given a tuple, X, for which the associated class label is unknown, the attribute values of
the tuple are tested against the decision tree. A path is traced from the root to a leaf
 node, which holds the class prediction for that tuple. Decision trees can easily be
converted to classification rules.
“Why are decision tree classifiers so popular?” :
The construction of decision tree classifiers does not require any domain knowledge or
parameter setting, and therefore is appropriate for exploratory knowledge discovery.
Decision trees can handle multidimensional data. Their representation of acquired
knowledge in tree form is intuitive and generally easy to assimilate by humans. The
learning and classification steps of decision tree induction are simple and fast.
Decision tree induction algorithms have been used for classification in many
application areas such as medicine, manufacturing and production, financial analysis,
astronomy, and molecular biology. Decision trees are the basis of several commercial
rule induction systems.
During tree construction, attribute selection measures are used to select the attribute that best
partition the tuples into distinct classes. When decision trees are built, many of the branches
may reflect noise or outliers in the training data. Tree pruning attempts to identify and remove
such branches, with the goal of improving classification accuracy on unseen data.

o During the late 1970s and early 1980s, J. Ross Quinlan, a researcher in machine
learning, developed a decision tree algorithm known as ID3 (Iterative
Dichotomizer).
o This work expanded on earlier work on concept learning systems, described by E.
B. Hunt, J. Marin, and P. T. Stone.
o Quinlan later presented C4.5 (a successor of ID3), which became a benchmark to
which newer supervised learning algorithms are often compared.
o In 1984, a group of statisticians (L. Breiman, J. Friedman, R. Olshen, and C.
Stone)
Published the book Classification and Regression Trees (CART), which described
the Generation of binary decision trees.

Decision Tree Algorithm:

Algorithm: Generate decision tree.
Generate a decision tree from the training tuples of data partition, D.

Input:
 Data partition, D, which is a set of training tuples and their associated class labels;
 attribute list, the set of candidate attributes;
 Attribute selection method, a procedure to determine the splitting
criterion that “best” partitions the data tuples into individual classes.
This criterion consists of a splitting attribute and, possibly, either a split-
point or splitting subset.
Outp ut: A decision tree.

Method:
1) create a node N;
2) if tuples in D are all of the same class, C, then
3) return N as a leaf node labeled with the class C;
4) if attribute list is empty then
5) return N as a leaf node labeled with the majority class in D; // majority voting
6) apply Attribute selection method(D, attribute list) to find the
“best” splitting criterion;
7) label node N with splitting criterion;
8) if splitting attribute is discrete-valued and
multiway splits allowed then // not restricted to binary trees
9) attribute list attribute list - splitting attribute; // remove splitting attribute
10) for each outcome j of splitting criterion
// partition the tuples and grow subtrees for each partition
11) let Dj be the set of data tuples in D satisfying outcome j; // a partition
12) if Dj is empty then
13) attach a leaf labeled with the majority class in D to node N;
14) else attach the node returned by Generate decision tree(Dj , attribute list) to node
N;
endfor
15) return N;

Attribute Selection Measures

 An attribute selection measure is a heuristic for selecting the splitting
criterion that “best” separates a given data partition, D, of class-labeled
training tuples into individual classes.
 If we were to split D into smaller partitions according to the outcomes of the
splitting criterion, ideally each partition would be pure (i.e., all the tuples
that fall into a given partition would belong to the same class).
 Conceptually, the “best” splitting criterion is the one that most closely
results in such a scenario. Attribute selection measures are also known as
splitting rules because they determine how the tuples at a given node are to
be split.
 The attribute selection measure provides a ranking for each attribute
describing the given training tuples. The attribute having the best score for
the measure is chosen as the splitting attribute for the given tuples.
 If the splitting attribute is continuous-valued or if we are restricted to binary
trees, then, respectively, either a split point or a splitting subset must also be
 determined as part of the splitting criterion.
 The tree node created for partition D is labeled with the splitting criterion,
branches are grown for each outcome of the criterion, and the tuples are
partitioned accordingly.
 There are three popular attribute selection measures—information gain, gain
ratio, and Gini index.

Information Gain
ID3 uses information gain as its attribute selection measure. Let node N
represent or hold the tuples of partition D. The attribute with the highest
information gain is chosen as the splitting attribute for node N. This attribute
minimizes the information needed to classify the tuples in the resulting
partitions and reflects the least randomness or “impurity” in these partitions.
Such an approach minimizes the expected number of tests needed to classify a
given tuple and guarantees that a simple (but not necessarily the simplest) tree is
found.

The expected information needed to classify a tuple in D is given by

Where piis the nonzero probability that an arbitrary tuple in D belongs to class
Ciand is estimated by |Ci,D|/|D|. A log function to the base 2 is used, because
the information is encoded in bits. Info(D) is also known as the entropy of D.

Information needed after using A to split D into V partitions.

Information gain is defined as the difference between the original information

requirement (i.e., based on just the proportion of classes) and the new
requirement (i.e., obtained after partitioning on A). That is,

The attribute A with the highest information gain, Gain(A), is chosen as

the splitting attribute at nodeN. This is equivalent to saying that we want to
partition on the attribute A that would do the “best classification,” so that the
amount of information still required to finish classifying the tuples is minimal.
Gain Ratio
 C4.5, a successor of ID3, uses an extension to information gain known as
gain ratio, which attempts to overcome this bias. It applies a kind of

normalization to information gain using a “split information” value defined

analogously with Info(D) as
This value represents the potential information generated by splitting the
trainingdata set, D, into v partitions, corresponding to the v outcomes of a test
on attribute A. Note that, for each outcome, it considers the number of tuples
having that outcome with respect to the total number of tuples in D. It differs
from information gain, which measures the information with respect to
classification that is acquired based on the same partitioning. The gain ratio is
defined as

Gini Index
The Gini index is used in CART. Using the notation previously

described, the Gini indexmeasures the impurity of D, a data partition or set of

training tuples, as
Where piis the nonzero probability that an arbitrary tuple in D belongs to
class Ci and is estimated by |Ci,D|/|D| over m classes.
Note: The Gini index considers a binary split for each attribute.
When considering a binary split, we compute a weighted sum of the
impurity of each resulting partition. For example, if a binary split on A partitions
D into D1 and D2, the Gini index of D given that partitioning is

 For each attribute, each of the possible binary splits is considered. For a
discrete-valued attribute, the subset that gives the minimum Gini index for
that attribute is selected as its splitting subset.
 For continuous-valued attributes, each possible split-point must be
considered. The strategy is similar to that described earlier for information
gain, where the midpoint between each pair of (sorted) adjacent values is
 taken as a possible split-point.
 The reduction in impurity that would be incurred by a binary split on a
discrete- or continuous-valued attribute A is

Tree Pruning:
 When a decision tree is built, many of the branches will reflect anomalies
in the training data due to noise or outliers.
 Tree pruning methods address this problem of overfitting the data.
Such methods typically use statistical measures to remove the least-
reliable branches.
 Pruned trees tend to be smaller and less complex and, thus, easier to comprehend.
 They are usually faster and better at correctly classifying independent test
data (i.e., of previously unseen tuples) than unpruned trees.
“How does tree pruning work?” There are two common approaches to tree pruning:
prepruning and postpruning.

 In the prepruning approach, a tree is “pruned” by halting its construction

early. Upon halting, the node becomes a leaf. The leaf may hold the most
frequent class among the subset tuples or the probability distribution of those
tuples.
 If partitioning the tuples at a node would result in a split that falls below a
prespecified threshold, then further partitioning of the given subset is halted.
There are difficulties, however, in choosing an appropriate threshold.
 In the postpruning, which removes subtrees from a “fully grown” tree. A
subtree at a given node is pruned by removing its branches and replacing it
with a leaf. The leaf is labeled with the most frequent class among the
 subtree being replaced.
 The cost complexity pruning algorithm used in CART is an example of the
postpruning approach
Fig: Unpruned and Pruned Trees

 This approach considers the cost complexity of a tree to be a function of

the number of leaves in the tree and the error rate of the tree (where the
error rate is the percentage of tuples misclassified by the tree). It starts
from the bottom of the tree.
 For each internal node, N, it computes the cost complexity of the subtree
at N, and the cost complexity of the subtree at N if it were to be pruned
(i.e., replaced by a leaf node).
 The two values are compared. If pruning the subtree at node N would
result in a smaller cost complexity, then the subtree is pruned. Otherwise,
it is kept.
 A pruning set of class-labeled tuples is used to estimate cost complexity.
 This set is independent of the training set used to build the unpruned tree
and of any test set used for accuracy estimation.
 The algorithm generates a set of progressively pruned trees. In general,
the smallest decision tree that minimizes the cost complexity is preferred.
 C4.5 uses a method called pessimistic pruning, which is similar to the
cost complexity method in that it also uses error rate estimates to make
decisions regarding subtree pruning.
 Scalability of Decision Tree Induction:
“What if D, the disk-resident training set of class-labeled tuples, does not
fit in memory? In other words, how scalable is decision tree induction?” The
efficiency of existing decision tree algorithms, such as ID3, C4.5, and CART,
has been well established for relatively small data sets. Efficiency becomes an
issue of concern when these algorithms are applied to the mining of very large
real-world databases. The pioneering decision tree algorithms that we have
discussed so far have the restriction that the training tuples should reside in
memory.

In data mining applications, very large training sets of millions of tuples

are common. Most often, the training data will not fit in memory! Therefore,
decision tree construction becomes inefficient due to swapping of the training
tuples in and out of main and cache memories. More scalable approaches,
capable of handling training data that are too large to fit in memory, are
required. Earlier strategies to “save space” included discretizing continuous-
valued attributes and sampling data at each node. These techniques, however,
still assume that the training set can fit in memory.

Several scalable decision tree induction methods have been introduced in

recent studies. Rain Forest, for example, adapts to the amount of main memory
available and applies to any decision tree induction algorithm. The method
maintains an AVC-set (where “AVC” stands for “Attribute-Value, Classlabel”)
for each attribute, at each tree node, describing the training tuples at the node.
The AVC-set of an attribute A at node N gives the class label counts for each
value of A for the tuples at N. The set of all AVC-sets at a node N is the AVC-
group of N. The size of an AVC-set for attribute A at node N depends only on
the number of distinct values of A and the number of classes in the set of tuples
at N. Typically, this size should fit in memory, even for real-world data. Rain
Forest also has techniques, however, for handling the case where the AVC-
group does not fit in memory. Therefore, the method has high scalability for
decision tree induction in very large data sets.
 Fig: AVC Sets for dataset

Rule based classification

Rule-based classification is a data mining technique used to categorize data into predefined
classes or segments based on a set of "if-then" rules. These rules are derived from the
characteristics and features of the data, and the classification of new data points depends on
whether they satisfy the conditions of these rules.
Key Components:
 IF-THEN Rules: The core of rule-based classification. Each rule consists of:
o Antecedent (IF condition): Specifies the conditions or features that must be met for the rule to
apply. Multiple conditions can be combined using logical operators like "AND."
o Consequent (THEN conclusion): Specifies the class label or action to be taken if the
antecedent conditions are satisfied.

Characteristics:
 Transparency and Interpretability:
The explicit nature of the "if-then" rules makes the classification process easy to understand
and explain, unlike some "black box" machine learning models.
 Coverage: The proportion of records in the dataset that satisfy the antecedent of a given rule.
 Accuracy: The proportion of records that satisfy both the antecedent and consequent of a rule
(i.e., are correctly classified by the rule).

 Mutually Exclusive and Exhaustive (or not):

Rule sets can be designed to be mutually exclusive (no two rules classify the same record to
different classes) and/or exhaustive (every record is covered by at least one rule), though this
is not always a requirement.
 Rule Ordering:
In cases where multiple rules might apply to a single data point, rules can be ordered based on
priority or quality to determine the final classification.
Applications:

Rule-based classification finds application in various domains, including:

 Customer segmentation:
Classifying customers into different segments based on demographic or behavioral data.
 Medical diagnosis:
Aiding in diagnosing conditions based on patient symptoms and medical history.
 Fraud detection:
Identifying potentially fraudulent transactions based on predefined patterns.
 Credit risk assessment:
Determining eligibility for credit or loans based on financial and demographic information.

Example
A rule-based classifier uses a set of
IF-THEN rules to categorize data, making the decision-making logic transparent and easy to
interpret.
Example: Credit eligibility assessment
A company can use a rule-based classifier to determine if a customer is eligible for credit based
on their age, income, and other financial data.
The data
Imagine a dataset with the following attributes for different customers:
 age (numerical)

 income (numerical)

 credit_score (numerical)
 has_existing_loan (boolean)
A credit analyst might define a set of ordered rules to classify a customer into one of three
classes: Approve , Review , or Reject . The rules are ordered by priority, so the first rule that
is satisfied determines the classification.

1. Rule 1: IF credit_score < 600 THEN class = Reject

2. Rule 2: IF has_existing_loan = true AND income < $40,000 THEN class = Review

3. Rule 3: IF age < 25 AND income > $50,000 THEN class = Review

4. Rule 4: IF income > $60,000 AND credit_score >= 600 THEN class = Approve

5. Default Rule: THEN class = Review

Classification process
Let's see how new customer applications would be classified using these rules:
Customer A
 age : 35

 income : $70,000

 credit_score : 720

 has_existing_loan : false

Classification:
 Rule 1 is not met ( credit_score is not less than 600).

 Rule 2 is not met ( has_existing_loan is false).

 Rule 3 is not met ( age is not less than 25).

 Rule 4 is met ( income is > $60,000 and credit_score is >= 600).

 Result: Approve .

Customer B
 age : 22

 income : $65,000
 credit_score : 680

 has_existing_loan : false

Classification:
 Rule 1 is not met.

 Rule 2 is not met.

 Rule 3 is met ( age is < 25 and income is > $50,000).

 Result: Review . (The process stops after the first rule is triggered).

Customer C
 age : 48

 income : $35,000

 credit_score : 580

 has_existing_loan : false

Classification:
 Rule 1 is met ( credit_score is < 600).

 Result: Reject .

Customer D
 age : 40

 income : $50,000

 credit_score : 650

 has_existing_loan : true

Classification:
 Rule 1 is not met.

 Rule 2 is met ( has_existing_loan is true and income is < $40,000).

 Result: Review .

Customer E
 age : 30

 income : $50,000

 credit_score : 650

 has_existing_loan : false

Classification:
 Rule 1 is not met.

 Rule 2 is not met.

 Rule 3 is not met.

 Rule 4 is not met.

 No other rules are met, so the Default Rule is used.

 Result: Review .

Key takeaways from the example

 Interpretability: The logic for every classification is clear because it follows explicit, human-
readable rules.

 Maintenance: Rules can be easily added, deleted, or modified by a subject-matter expert

without retraining a machine learning model.

 Handling conflicts: The use of an ordered rule set (a decision list) resolves conflicts by
prioritizing certain rules over others.

 Handling exceptions: A default class ensures that every data record is assigned a category,
even if no specific rules apply.

Rule-based classification utilizes a set of "IF-THEN" rules to categorize data into distinct
classes. These rules are derived from patterns and relationships within the data.
Example: Animal classification
 Consider a rule-based system designed to classify animals based on their biological
characteristics:
 Rule 1: IF (Give Birth = No) AND (Can Fly = Yes) THEN Classify as "Bird"
 Rule 2: IF (Give Birth = No) AND (Live in Water = Yes) THEN Classify as "Fish"
 Rule 3: IF (Give Birth = Yes) AND (Blood Type = Warm) THEN Classify as "Mammal"
 Rule 4: IF (Give Birth = No) AND (Can Fly = No) THEN Classify as "Reptile"
 Rule 5: IF (Live in Water = Sometimes) THEN Classify as "Amphibian"
Application:
 Lemur:
A lemur satisfies Rule 3 (Give Birth = Yes, Blood Type = Warm), so it is classified as a
"Mammal"

 Turtle:
A turtle satisfies both Rule 4 (Give Birth = No, Can Fly = No) and Rule 5 (Live in Water =
Sometimes). In a system where rules are prioritized or a conflict resolution strategy is in
place, one classification would be chosen.
 Dogfish Shark:
A dogfish shark may not satisfy any of these specific rules, indicating that the rule set might
not be exhaustive or that additional rules are needed to cover all possible cases.
This example demonstrates how explicit, interpretable rules can be used to classify data based
on specific attribute values.
Rule-Based Classifier - Machine Learning
Animal classification example
A classic example is a rule-based system for classifying animals based on their characteristics.
Input data attributes:
 Blood Type : Warm or cold-blooded

 Give Birth : Yes or no

 Can Fly : Yes or no

 Live in Water : Yes, no, or sometimes

Rules:
 Rule R1: IF ( Give Birth = yes) AND ( Blood Type = warm) THEN Class = mammal

 Rule R2: IF ( Give Birth = no) AND ( Can Fly = yes) THEN Class = bird
 Rule R3: IF ( Give Birth = no) AND ( Live in Water = yes) THEN Class = fish

 Rule R4: IF ( Give Birth = no) AND ( Can Fly = no) THEN Class = reptile

 Rule R5: IF ( Live in Water = sometimes) THEN Class = amphibian

Classification process:
o classify a new animal, the classifier checks the rules in order until it finds a match.
 To classify a lemur:

o The animal gives birth ( Give Birth = yes) and is warm-blooded ( Blood Type = warm).

o Result: Rule R1 is triggered, and the lemur is classified as a mammal.

 To classify a turtle:

o The turtle does not give birth, cannot fly, and sometimes lives in water.

o Rules R4 and R5 are both triggered.

o To resolve this conflict, the rules must be ordered by priority. If Rule R5 (amphibian) has
higher priority than Rule R4 (reptile), the turtle is classified as an amphibian. If R4 has higher
priority, it is a reptile. This shows that handling conflicting rules is a key aspect of building
rule-based classifiers.

Example :Spam filtering

A rule-based system is commonly used for filtering unwanted emails by detecting specific
keywords or sender characteristics.
Rules:
 Rule R1: IF ( Subject contains "free money") THEN Class = spam

 Rule R2: IF ( Sender is "scammer@[Link]") THEN Class = spam

 Rule R3: IF ( Body contains "urgent action needed") THEN Class = spam

 Rule R4: IF (Rule R1 OR Rule R2 OR Rule R3) THEN Class = spam ELSE Class = not
spam

Classification process:
 New email: An email arrives with the subject "Get free money now!"
 Classifier check: The system checks the Subject field and finds the phrase "free money."

 Result: Rule R1 is triggered, and the email is sent to the spam folder.

┌────────────────────────────┐
│ Default on previous loan? │
└────────────┬───────────────┘
│
┌────────────▼────────────┐
│ Yes │
│ ➤ Risk = High │
└─────────────────────────┘
│
▼
┌────────────────────────────┐
│ Credit Score < 600? │
└────────────┬───────────────┘
│
┌────────────▼────────────┐
│ Yes │
│ ➤ Risk = High │
└─────────────────────────┘
│
▼
┌────────────────────────────┐
│ Debt-to-Income > 40%? │
└────────────┬───────────────┘
│
┌────────────▼────────────┐
│ Yes │
│ ➤ Risk = High │
└─────────────────────────┘
│
▼
┌────────────────────────────┐
│ Credit Score > 750 AND │
│ Employment > 2 years? │
└────────────┬───────────────┘
│
┌────────────▼────────────┐
│ Yes │
│ ➤ Risk = Low │
└─────────────────────────┘
│
 ▼
┌─────────────────────────┐
│ No │
│ ➤ Risk = Medium │
└─────────────────────────┘

Support Vector Machine (SVM)

Support Vector Machines (SVMs) are supervised learning models used for classification and
regression, especially effective in high-dimensional data. They work by finding an optimal
hyperplane that maximizes the margin between different classes of data points. This hyperplane
serves as a decision boundary. The data points closest to the hyperplane are called support
vectors, and they determine the position of the boundary. SVMs use kernel functions to handle
 non-linear data by mapping it to a higher-dimensional space, where it can be separated by a
linear hyperplane.

How SVMs Work

1. 1. Data Representation:
 Each data point is represented as a vector in an n-dimensional space, where the dimensions
are the features of the data.
2. 2. Hyperplane:
The goal is to find a hyperplane (a line in 2D, a plane in 3D, etc.) that best separates the data
points into distinct classes.
3. 3. Maximum Margin:
SVMs aim to find the hyperplane that has the largest distance to the nearest data points of any
class. This maximum distance is called the margin.
4. 4. Support Vectors:
The data points that fall on the boundary of this margin are the support vectors. They are
critical for defining the hyperplane.
5. 5. Kernel Trick:
For non-linear data that cannot be separated by a linear hyperplane, SVMs use the kernel
trick. This involves applying a nonlinear mapping to transform the data into a higher-
dimensional feature space where a linear separation is possible.

Key Components
 Hyperplane: The decision boundary that separates the data into classes.
 Margin: The distance between the hyperplane and the nearest data points of any class.
Hard Margin: A maximum-margin hyperplane that perfectly separates the data without
misclassifications.
Soft Margin: Allows some misclassifications by introducing slack variables, balancing margin
maximization and misclassification penalties when data is not perfectly separable
 Support Vectors: The data points closest to the hyperplane that define the margin.
 Kernel Functions: Functions (e.g., Linear, Gaussian Radial Basis Function) used to transform
data to a higher dimension to allow for nonlinear separation.
 Hinge Loss: A loss function penalizing misclassified points or margin violations and is combined
with regularization in SVM.
 Dual Problem: Involves solving for Lagrange multipliers associated with support vectors,
facilitating the kernel trick and efficient computation.
Applications
 Image Recognition: Used in features like facial recognition by services like Facebook and
Google Photos.
 Speech Recognition: Used in voice assistants such as Apple's Siri and Google Assistant.
 Pattern Recognition: Widely applied for identifying patterns in various types of data.
 Functional Estimation: Can be used in regression problems to predict continuous values.
 Support Vector Machine (SVM) Algorithm




Support Vector Machine (SVM) is a supervised machine learning algorithm used for
classification and regression tasks. It tries to find the best boundary known as hyperplane that
separates different classes in the data. It is useful when you want to do binary classification like
spam vs. not spam or cat vs. dog.
The main goal of SVM is to maximize the margin between the two classes. The larger the
margin the better the model performs on new and unseen data.

Multiple hyperplanes separate the data from two classes

The best hyperplane also known as the "hard margin" is the one that maximizes the distance
between the hyperplane and the nearest data points from both classes. This ensures a clear
separation between the classes. So from the above figure, we choose L2 as hard margin. Let's
consider a scenario like shown below:

Multiple hyperplanes separate the data from two classes

Here, we have one blue ball in the boundary of the red ball.

Selecting hyperplane for data with outlier

Hyperplane which is the most optimized one

How does SVM classify the data?

The blue ball in the boundary of red ones is an outlier of blue balls. The SVM algorithm has the
characteristics to ignore the outlier and finds the best hyperplane that maximizes the margin.
SVM is robust to outliers.
Hyperplane which is the most optimized one
A soft margin allows for some misclassifications or violations of the margin to improve
generalization. The SVM optimizes the following equation to balance margin maximization
and penalty minimization:
Objective Function=(1margin)+λ∑penalty Objective Function=(margin1)
+λ∑penalty
The penalty used for violations is often hinge loss which has the following behavior:
 If a data point is correctly classified and within the margin there is no penalty (loss = 0).
 If a point is incorrectly classified or violates the margin the hinge loss increases
proportionally to the distance of the violation.
Till now we were talking about linearly separable data that separates group of blue balls and
red balls by a straight line/linear line.
What if data is not linearly separable?
When data is not linearly separable i.e it can't be divided by a straight line, SVM uses a
technique called kernels to map the data into a higher-dimensional space where it becomes
separable. This transformation helps SVM find a decision boundary even for non-linear data.
Original 1D dataset for classification
A kernel is a function that maps data points into a higher-dimensional space without explicitly
computing the coordinates in that space. This allows SVM to work efficiently with non-linear
data by implicitly performing the mapping. For example consider data points that are not
linearly separable. By applying a kernel function SVM transforms the data points into a higher-
dimensional space where they become linearly separable.

Mapping 1D data to 2D to become able to separate the two classes

 Linear Kernel: For linear reparability.
 Polynomial Kernel: Maps data into a polynomial space.
 Radial Basis Function (RBF) Kernel: Transforms data into a space based on distances between
data points.
Mapping 1D data to 2D to become able to separate the two classes
In this case the new variable y is created as a function of distance from the origin.
Mathematical Computation of SVM
Consider a binary classification problem with two classes, labeled as +1 and -1. We have a
training dataset consisting of input feature vectors X and their corresponding class labels Y.
The equation for the linear hyperplane can be written as:
wTx+b=0wTx+b=0
Where:
 ww is the normal vector to the hyperplane (the direction perpendicular to it).
 bb is the offset or bias term representing the distance of the hyperplane from the origin
along the normal vector ww.
Distance from a Data Point to the Hyperplane
The distance between a data point xixiand the decision boundary can be calculated as:
di=wTxi+b∣∣w∣∣di=∣∣w∣∣wTxi+b
where ||w|| represents the Euclidean norm of the weight vector w.

Linear SVM Classifier

Distance from a Data Point to the Hyperplane:

y^={1: wTx+b≥00: wTx+b <0y^={10: wTx+b≥0: wTx+b <0

Where y^y^ is the predicted label of a data point.

Optimization Problem for SVM

For a linearly separable dataset the goal is to find the hyperplane that maximizes the margin
between the two classes while ensuring that all data points are correctly classified. This leads to
the following optimization problem:

minimizew,b12∥w∥2w,bminimize21∥w∥2
Subject to the constraint:
yi(wTxi+b)≥1fori=1,2,3,⋯,myi(wTxi+b)≥1fori=1,2,3,⋯,m
Where:
 yiyi is the class label (+1 or -1) for each training instance.
 xixi is the feature vector for the ii-th training instance.
 mm is the total number of training instances.
The condition yi(wTxi+b)≥1yi(wTxi+b)≥1 ensures that each data point is correctly
classified and lies outside the margin.

Soft Margin in Linear SVM Classifier

In the presence of outliers or non-separable data the SVM allows some misclassification by
introducing slack variables ζiζi. The optimization problem is modified as:
minimize
w,b12∥w∥2+C∑i=1mζiw,bminimize 21∥w∥2+C∑i=1mζi
Subject to the constraints:

yi(wTxi+b)≥1−ζiandζi≥0for i=1,2,…,myi(wTxi+b)≥1−ζiandζi≥0for
i=1,2,…,m
Where:
 CC is a regularization parameter that controls the trade-off between margin maximization
and penalty for misclassifications.
 ζiζi are slack variables that represent the degree of violation of the margin by each data
point.

Dual Problem for SVM

The dual problem involves maximizing the Lagrange multipliers associated with the support
vectors. This transformation allows solving the SVM optimization using kernel functions for
non-linear classification.
The dual objective function is given by:

maximize α12∑i=1m∑j=1mαiαjtitjK(xi,xj)−∑i=1mαiαmaximize 21∑i=1m

∑j=1mαiαjtitjK(xi,xj)−∑i=1mαi
Where:
 αiαi are the Lagrange multipliers associated with the ithith training sample.
 titi is the class label for the ithith-th training sample.
 K(xi,xj)K(xi,xj) is the kernel function that computes the similarity between data points xixi
and xjxj. The kernel allows SVM to handle non-linear classification problems by mapping
data into a higher-dimensional space.
The dual formulation optimizes the Lagrange multipliers αiαi and the support vectors are those
training samples where αi>0αi>0.

SVM Decision Boundary

Once the dual problem is solved, the decision boundary is given by:
w=∑i=1mαitiK(xi,x)+bw=∑i=1mαitiK(xi,x)+b
Where ww is the weight vector, xx is the test data point and bb is the bias term. Finally the bias
term bb is determined by the support vectors, which satisfy:
ti(wTxi−b)=1⇒b=wTxi−titi(wTxi−b)=1⇒b=wTxi−ti
Where xixi is any support vector.
This completes the mathematical framework of the Support Vector Machine algorithm which
allows for both linear and non-linear classification using the dual problem and kernel trick.
Types of Support Vector Machine
Based on the nature of the decision boundary, Support Vector Machines (SVM) can be divided
into two main parts:
 Linear SVM: Linear SVMs use a linear decision boundary to separate the data points of
different classes. When the data can be precisely linearly separated, linear SVMs are very
suitable. This means that a single straight line (in 2D) or a hyperplane (in higher
dimensions) can entirely divide the data points into their respective classes. A hyperplane
that maximizes the margin between the classes is the decision boundary.
 Non-Linear SVM: Non-Linear SVM can be used to classify data when it cannot be separated
into two classes by a straight line (in the case of 2D). By using kernel functions, nonlinear
SVMs can handle nonlinearly separable data. The original input data is transformed by these
kernel functions into a higher-dimensional feature space where the data points can be
linearly separated. A linear SVM is used to locate a nonlinear decision boundary in this
modified space.

Advantages of Support Vector Machine (SVM)

1. High-Dimensional Performance: SVM excels in high-dimensional spaces, making it suitable for
image classification and gene expression analysis.
2. Nonlinear Capability: Utilizing kernel functions like RBF and polynomial SVM effectively
handles nonlinear relationships.
3. Outlier Resilience: The soft margin feature allows SVM to ignore outliers, enhancing
robustness in spam detection and anomaly detection.
4. Binary and Multiclass Support: SVM is effective for both binary classification and multiclass
classification suitable for applications in text classification.
5. Memory Efficiency: It focuses on support vectors making it memory efficient compared to
other algorithms.

Disadvantages of Support Vector Machine (SVM)

1. Slow Training: SVM can be slow for large datasets, affecting performance in SVM in data
mining tasks.
2. Parameter Tuning Difficulty: Selecting the right kernel and adjusting parameters like C requires
careful tuning, impacting SVM algorithms.
3. Noise Sensitivity: SVM struggles with noisy datasets and overlapping classes, limiting
effectiveness in real-world scenarios.
4. Limited Interpretability: The complexity of the hyperplane in higher dimensions makes SVM
less interpretable than other models.
5. Feature Scaling Sensitivity: Proper feature scaling is essential, otherwise SVM models may
perform poorly.

A classic example illustrating Support Vector Machine (SVM) classification is the Iris dataset,
specifically classifying two species, such as Iris Setosa and Iris Versicolor, based on their sepal
length and sepal width.
 Example Scenario:
 Data Preparation:
Load the Iris dataset and filter for Iris Setosa and Iris Versicolor. Extract the 'Sepal Length'
and 'Sepal Width' as features. Each data point represents an individual flower, with its
features plotted on a 2D plane. The species of the flower is the target variable, indicating
which class it belongs to.
 Visualization:
Plot the data points, coloring them differently based on their species. Observe that Iris Setosa
and Iris Versicolor are generally linearly separable, meaning a straight line can be drawn to
divide them.
 SVM Application:
 An SVM algorithm is applied to this data. The goal of the SVM is to find the optimal
hyperplane (a straight line in this 2D example) that best separates the two classes.
 Unlike simply finding any separating line, SVM aims to find the line that maximizes the
margin between the two classes. The margin is the distance between the hyperplane and the
closest data points from each class, known as support vectors.
 The SVM identifies these support vectors and constructs the hyperplane such that it is
equidistant from the closest points of both classes, thereby maximizing the margin.
 Classification:
Once the optimal hyperplane is determined, new, unseen Iris flowers can be classified. By
measuring their sepal length and sepal width and plotting them on the same plane, their
position relative to the hyperplane dictates whether they are classified as Iris Setosa or Iris
Versicolor.
Why this example demonstrates SVM effectively:
 Linear Separability:
The Iris dataset, particularly these two species, often exhibits clear linear separability, making
it easy to visualize the hyperplane and the concept of a margin.
 Support Vectors:
The concept of support vectors, the crucial data points that define the margin and the
hyperplane, becomes evident in this example.
 Margin Maximization:
The visual representation clearly illustrates how SVM aims to find the widest possible
"street" between the two classes, leading to a more robust classification boundary.

A common example of a Support Vector Machine (SVM) classification is identifying spam

emails. The algorithm learns to separate emails into two categories: "spam" and "not spam" by
finding the optimal boundary that maximizes the margin between the two classes.