Module 3: Classification
1. Introduction
● Classification is a supervised learning technique used in data mining.
● The goal is to build a model (classifier) that can predict the class label of new, unseen data based
on past data (training set).
● Example: Predicting whether an email is spam or not spam, whether a loan will be approved or
rejected.
2. Basic Concepts
What is Classification?
● Classification is the process of finding a mapping function (or model) that maps input data
(attributes) to predefined classes (output labels).
● Input: Training data with class labels.
● Output: A model that can predict class labels for new data.
How Does Classification Work?
1. Building the Classifier / Model (Training Phase)
○ Historical data (training set) is used.
○ A learning algorithm analyzes the data and finds patterns that distinguish classes.
○ Example: Decision tree, Naïve Bayes, Neural networks.
2. Using the Classifier for Classification (Testing Phase)
○ The model is applied to new (test) data.
○ The predicted class label is assigned based on learned patterns.
○ Performance is measured using metrics such as accuracy, precision, recall, F1-score.
3. Classification Issues
1. Data Cleaning
○ Real-world data often contains noise, missing values, or outliers.
○ Cleaning ensures high-quality input, which improves model accuracy.
2. Relevance Analysis (Feature Selection)
○ Not all attributes contribute equally.
○ Irrelevant or redundant features are removed to improve efficiency.
○ Example: Removing "customer phone number" when predicting loan approval.
3. Data Transformation and Reduction
○ Transformation: Normalize or scale attributes so all are on a similar range.
○ Reduction: Use dimensionality reduction (PCA) or sampling to reduce dataset size
without losing important information.
○ Purpose: Speed up training and avoid overfitting.
4. Comparison of Classification Methods
Method Characteristics Pros Cons
Decision Trees Tree structure with rules Easy to interpret, fast Can overfit if not pruned
Naïve Bayes Based on probability, Simple, works well Assumption of
assumes independence with text independence may not
hold
k-Nearest Instance-based, uses Simple, no training Slow with large datasets
Neighbor (k-NN) distance phase
Support Vector Finds optimal hyperplane Works well with Complex, slow for big
Machines (SVM) high-dimensional data datasets
Neural Networks Multi-layer, non-linear Powerful for complex Hard to interpret, needs
patterns large data
Random Forests Ensemble of decision trees High accuracy, More complex than a
reduces overfitting single tree
Decision Tree
1. Introduction to Decision Tree Induction
● A Decision Tree is a supervised learning method used for classification and prediction.
● It splits data into subsets based on the values of attributes.
● The tree structure consists of:
○ Root Node – represents the entire dataset.
○ Internal Nodes – represent tests on attributes.
○ Branches – outcomes of the test.
○ Leaf Nodes – final class labels.
Advantages:
● Easy to understand and interpret.
● Handles categorical and numerical data.
● Requires little data preparation.
2. Decision Tree Induction Algorithm (Steps)
1. Start with the entire dataset as the root.
2. Select the best attribute to split data (using measures like Information Gain, Gini Index).
3. Create branches for each value of the attribute.
4. Partition data into subsets.
5. Repeat recursively until one of the following:
○ All tuples belong to the same class.
○ No remaining attributes.
○ No more data to split.
6. The final nodes are leaf nodes with class labels.
3. Tree Pruning
● After building a tree, it may overfit (too complex, capturing noise).
● Pruning reduces tree size by removing unimportant branches.
Types:
● Pre-pruning (Early Stopping): Stop growing tree early if further splitting is not useful.
● Post-pruning: Build full tree first, then remove branches that do not improve accuracy.
5. Classification Using Information Gain
● Information Gain (IG) is based on Entropy (measure of impurity).
● Formula:
○ Entropy(S) = − Σ pᵢ log₂(pᵢ)
○ Information Gain = Entropy(parent) − Weighted Avg(Entropy(children))
● The attribute with highest Information Gain is selected for splitting.
ID3 Algorithm (Iterative Dichotomiser 3)
Introduction
● Proposed by Ross Quinlan (1986).
● A decision tree induction algorithm that uses Information Gain (based on Entropy) to select
the attribute that best classifies the data at each step.
● Works well for categorical data.
Steps of ID3 Algorithm
1. Input: Training dataset with attributes and class labels.
2. Check for stopping conditions:
○ If all samples belong to the same class → make a leaf node.
○ If attributes are exhausted → make a leaf with the majority class.
3. Calculate Entropy for the dataset.
4. For each attribute, calculate Information Gain (IG):
5. Select the attribute with maximum IG as the root node.
6. Partition the dataset according to this attribute’s values.
7. Repeat recursively for each subset until stopping conditions are met.
Day Outlook Temperature Humidity Wind Play Tennis
1 Sunny Hot High Weak No
2 Sunny Hot High Strong No
3 Cloudy Hot High Weak Yes
4 Rain Mild High Weak Yes
5 Rain Cool Normal Weak Yes
6 Rain Cool Normal Strong No
7 Cloudy Cool Normal Strong Yes
8 Sunny Mild High Weak No
9 Sunny Cool Normal Weak Yes
10 Rain Mild Normal Weak Yes
11 Sunny Mild Normal Strong Yes
12 Cloudy Mild High Strong Yes
13 Cloudy Hot Normal Weak Yes
14 Rain Mild High Strong No
Naive Bayes Classifiers
Naive Bayes is a machine learning classification algorithm that predicts the
category of a data point using probability. It assumes that all features are
independent of each other. Naive Bayes performs well in many real-world
applications such as spam filtering, document categorization and sentiment
analysis.
Key Features of Naive Bayes Classifiers
The main idea behind the Naive Bayes classifier is to use Bayes' Theorem to
classify data based on the probabilities of different classes given the features
of the data. It is used mostly in high-dimensional text classification
● The Naive Bayes Classifier is a simple probabilistic classifier and it
has very few number of parameters which are used to build the ML
models that can predict at a faster speed than other classification
algorithms.
● It is a probabilistic classifier because it assumes that one feature in
the model is independent of existence of another feature. In other
words, each feature contributes to the predictions with no relation
between each other.
● Naive Bayes Algorithm is used in spam filtration, Sentimental
analysis, classifying articles and many more.
Why it is Called Naive Bayes?
It is named as "Naive" because it assumes the presence of one feature does
not affect other features. The "Bayes" part of the name refers to its basis in
Bayes’ Theorem.
Introduction to Bayes' Theorem
Bayes’ Theorem provides a principled way to reverse conditional
probabilities. It is defined as:
Accuracy and Error Measures
1. Introduction
When we build a classifier, we must check how well it performs.
This is done using:
● Confusion Matrix (basic tool)
● Derived Metrics (Accuracy, Precision, Recall, F-score, etc.)
2. Confusion Matrix
For a binary classification (positive vs. negative):
Predicted Positive Predicted Negative
Actual Positive True Positive (TP) False Negative (FN)
Actual Negative False Positive (FP) True Negative (TN)
● TP (True Positive): Correctly predicted positive cases.
● TN (True Negative): Correctly predicted negative cases.
● FP (False Positive): Incorrectly predicted positive (Type I error).
● FN (False Negative): Incorrectly predicted negative (Type II error).
3. Evaluation Metrics
(a) Accuracy
Overall correctness of the model.
(b) Error Rate
Proportion of wrong predictions.
(c) Sensitivity (Recall / True Positive Rate)
How well the model identifies actual positives.
(d) Specificity (True Negative Rate)
How well the model identifies actual negatives.
(e) Precision (Positive Predictive Value)
Out of all predicted positives, how many are correct.
(f) Recall
(Same as Sensitivity, already above).
(g) F-Score (F1-Score)
Harmonic mean of Precision and Recall.
4. Example
Suppose we test a model on 100 cases:
● TP = 40
● TN = 50
● FP = 5
● FN = 5
Compute:
● Accuracy = (40 + 50) / 100 = 0.90 (90%)
● Error Rate = (5 + 5) / 100 = 0.10 (10%)
● Sensitivity = 40 / (40 + 5) = 0.89
● Specificity = 50 / (50 + 5) = 0.91
● Precision = 40 / (40 + 5) = 0.89
● Recall = 0.89
● F1 = 2 × (0.89 × 0.89) / (0.89 + 0.89) = 0.89
5. Quick Summary
● Confusion Matrix = base tool for evaluation.
● Accuracy = overall correctness.
● Error Rate = misclassification rate.
● Sensitivity/Recall = ability to detect positives.
● Specificity = ability to detect negatives.
● Precision = reliability of positive predictions.
● F-score = balance between Precision & Recall.
Prediction and Regression Models
● Prediction means estimating the value of a dependent (target) variable using one or more
independent (predictor) variables.
● Regression models are used when the target variable is continuous (e.g., predicting
house price, salary, temperature).
General structure of a regression model:
Where:
● Y = dependent (response) variable
● X = independent (predictor) variable(s)
● f(X) = function (linear or non-linear)
● ϵ = error term (difference between predicted and actual values)
Simple Linear Regression (SLR)
● Used when there is one independent variable and one dependent variable.
● Assumes a straight-line relationship between X and Y.
Equation:
Where:
● Y: dependent variable (predicted)
● X: independent variable (input)
● β0: intercept (value of Y when X=0)
● β1: slope (change in Y for one unit change in X)
● ϵ: error term
Example: Predicting marks (Y) based on hours studied (X):
Marks=20+5×(Hours)
(Here, slope = 5 means each extra hour of study increases marks by 5.)
Multiple Linear Regression (MLR)
● Used when there are two or more independent variables.
Equation:
Uses
● Business: predict sales, profit, demand.
● Healthcare: predict patient recovery time.
● Engineering: predict system performance.
● Social Sciences: predict behavior trends.
● Simple Linear Regression → one predictor, straight-line model.
● Multiple Linear Regression → many predictors, linear combination model.
Example
Simple Linear Regression (SLR)
Concept: Predict one variable (Y) using a single predictor (X).
Equation:
Example: Hours studied vs. Exam Score
Suppose we collect data:
Hours Studied (X) Exam Score (Y)
1 40
2 50
3 65
4 70
5 80
If we fit a regression line, we may get:
Y=30+10X
Interpretation:
● Intercept (30): Even if no study (X=0), expected score = 30.
● Slope (10): Each extra hour of study increases score by 10 marks.
Prediction:
If a student studies 6 hours, predicted score =
Y=30+10×6=90
Multiple Linear Regression (MLR)
Concept: Predict one variable (Y) using two or more predictors.
Equation:
Example: Predict Salary based on Experience & Education
Data (hypothetical):
Experience (X1, years) Education Level (X2, scale 1–5) Salary (Y, in ₹0)
1 2 25
3 3 45
5 4 65
7 5 85
Suppose regression model is:
Salary=15+5X1+8X2
Interpretation:
● Intercept (15): Base salary with zero experience & education level = ₹15,000.
● Coefficient of Experience (5): Each extra year of experience increases salary by ₹5,000.
● Coefficient of Education (8): Each extra education level increases salary by ₹8,000.
Prediction:
If a person has 4 years experience (X1=4) and education level 3 (X2=3):
Salary=15+(5×4)+(8×3)=15+20+24=₹59,000
● Simple Linear Regression → one predictor, straight line in 2D.
● Multiple Linear Regression → multiple predictors, regression plane/hyperplane in
higher dimensions.