Module 3: Classification
TE – D – DWM
Prof. Smruti Vyavahare
Assistant Professor
Dept. of Computer Engineering,
SIES Graduate School of Technology
1
Prof. Smruti Vyavahare
Contents
• Basic Concepts
• Decision Tree Introduction
• Naïve Bayesian Classifications
• Accuracy and Error Measures
• Evaluating the Accuracy of a Classifier:
1. Holding & Random Sampling
2. Cross Validation
3. Bootstrap
2
Prof. Smruti Vyavahare
Comparing Supervised and Unsupervised Learning
• Supervised Learning (Classification):
• In this approach, each training example is paired with a label that identifies its category or class.
• The model learns from these labeled examples to predict the class of new, unseen data.
• For example, Google's Gmail uses supervised learning to filter spam emails by learning from
millions of labeled messages. Another case is IBM Watson Health, which classifies medical
images to assist doctors in diagnosing diseases like cancer.
• Unsupervised Learning (Clustering):
• Here, the training data lacks any class labels.
• The goal is to analyze the data—such as measurements or observations—to discover natural
groupings or clusters without prior knowledge of categories.
• For instance, Netflix applies unsupervised learning to group viewers by their watching habits to
recommend personalized content. Similarly, in finance, fraud detection systems cluster
transaction data to identify unusual patterns without predefined categories.
3
Prof. Smruti Vyavahare
Prediction Tasks: Classification vs. Numeric Prediction
• Classification
• Assigns data points to distinct categories or classes (discrete or nominal labels).
• Builds a predictive model from a training dataset by learning the relationship between input
features and their corresponding class labels.
• Applies this model to categorize new, unseen data accurately.
• Example: Email spam detection, where messages are classified as "spam" or "not spam."
• Numeric Prediction
• Estimates continuous values by modeling functions that predict unknown or missing numerical
data.
• Example: Forecasting house prices based on features like size, location, and age.
• Common Use Cases:
1. Credit or Loan Approval: Assessing if an applicant qualifies for credit based on financial
history.
2. Medical Diagnosis: Determining if a tumor is cancerous or benign.
3. Fraud Detection: Identifying fraudulent transactions in banking.
4. Web Page Classification: Categorizing web pages into topics such as sports, news, or
entertainment.
4
Prof. Smruti Vyavahare
5
Prof. Smruti Vyavahare
Classification – A Two-Step Process
6
Prof. Smruti Vyavahare
7
Prof. Smruti Vyavahare
8
Prof. Smruti Vyavahare
9
Prof. Smruti Vyavahare
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.
Output: 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;
10
Prof. Smruti Vyavahare
11
Prof. Smruti Vyavahare
12
Prof. Smruti Vyavahare
13
Prof. Smruti Vyavahare
14
Prof. Smruti Vyavahare
15
Prof. Smruti Vyavahare
16
Prof. Smruti Vyavahare
17
Prof. Smruti Vyavahare
18
Prof. Smruti Vyavahare
19
Prof. Smruti Vyavahare
20
Prof. Smruti Vyavahare
21
Prof. Smruti Vyavahare
22
Prof. Smruti Vyavahare
23
Prof. Smruti Vyavahare
24
Prof. Smruti Vyavahare
25
Prof. Smruti Vyavahare
26
Prof. Smruti Vyavahare
27
Prof. Smruti Vyavahare
28
Prof. Smruti Vyavahare
29
Prof. Smruti Vyavahare
30
Prof. Smruti Vyavahare
Tree Pruning
•Large decision trees may capture noise and outliers and causes overfitting.
•Tree Pruning means removing unnecessary branches.
•Benefits are:
1. Smaller and simpler tree
2. Easy to understand
3. Faster execution
4. Better accuracy on unseen data
Approaches to Pruning
1. Pre-pruning (Early Stopping)
• Stop tree growth early if further splitting is not useful.
• It uses measures like:
1. Information Gain
2. Gini Index
3. Statistical Significance
• Problems facing are:
• High threshold causes oversimplified tree (underfitting).
• Low threshold causes little simplification (overfitting).
2. Post-pruning (Cut After Full Growth)
• Grow the tree fully and then remove weak subtrees.
• Subtree is replaced with a leaf(major class).
• More computation required but more reliable.
• Example: Subtree at A3 replaced with a single leaf (class B).
31
Prof. Smruti Vyavahare
Post-Pruning Techniques
1. Cost Complexity Pruning (CART)
• Cost = Error rate + Number of leaves (tree size).
• For each node: Compare cost of keeping subtree vs pruning it.
• If pruning reduces cost then it prune.
• Needs an independent pruning set.
• Chooses the smallest tree with minimum cost complexity.
2. Pessimistic Pruning (C4.5)
• Uses training set error rate (no pruning set).
• Training set error is biased then adds a penalty to adjust.
• Simpler, but less accurate than cost complexity pruning.
32
Prof. Smruti Vyavahare
3. MDL (Minimum Description Length)
• Selects the tree with minimum encoding length (bits).
• Principle is Simplest tree is the best.
• No pruning set required.
•Sometimes pre- and post-pruning are combined.
•Pruned trees are compact but may still suffer from:
•Repetition means same attribute tested multiple times.
•Replication means duplicate subtrees.
•Solutions are:
1. Use multivariate splits (combine attributes).
2. Use rule-based representation instead of trees.
33
Prof. Smruti Vyavahare
Scalability and Decision Tree Induction
34
Prof. Smruti Vyavahare
35
Prof. Smruti Vyavahare
36
Prof. Smruti Vyavahare
37
Prof. Smruti Vyavahare
38
Prof. Smruti Vyavahare
39
Prof. Smruti Vyavahare
40
Prof. Smruti Vyavahare
41
Prof. Smruti Vyavahare
42
Prof. Smruti Vyavahare
Using IF-THEN Rules for Classification
These are logical statements used to classify data. Each rule has two parts:
• IF (antecedent): Conditions based on attribute values
• THEN (consequent): Predicted class label
IF age = youth AND student = yes THEN buys_computer = yes
Two key metrics:
43
Prof. Smruti Vyavahare
44
Prof. Smruti Vyavahare
Rule Induction using the Sequential Covering Method
Rule induction is a method for learning classification rules from data. These rules are in the form:
IF conditions THEN class label
Sequential Covering
Steps in Sequential Covering:
1. Learn one rule that covers many tuples of a class (say, “buys_computer =
yes”).
2. Remove the tuples that are covered by that rule.
3. Repeat the process on the remaining data.
4. Stop when:
1. No more examples left, or
2. The next rule isn’t good enough (based on a quality threshold)
Comparison with Decision Trees:
• Sequential Covering → learns rules one at a time
• Decision Tree Induction → learns all rules at once by building a tree
45
Prof. Smruti Vyavahare
46
Prof. Smruti Vyavahare
Classifier Evaluation metrics: Confusion Matrix
47
Prof. Smruti Vyavahare
48
Prof. Smruti Vyavahare
49
Prof. Smruti Vyavahare
50
Prof. Smruti Vyavahare
Holdout and Cross-Validation Techniques
• Holdout Approach
• The dataset is randomly split into two separate groups.
• A larger portion (for example, two-thirds) is used to train the model.
• The remaining portion (such as one-third) serves to evaluate the model's accuracy.
• Random Sampling is a variant where this holdout process is repeated multiple times.
• By performing holdout repeatedly (k times), the overall accuracy is calculated as the average of
all individual results.
• Cross-Validation (k-Fold, commonly k=10)
• The data is divided randomly into k distinct subsets of roughly equal size.
• In each iteration i, the i-th subset acts as the test set, while the other k-1 subsets form the training
set.
• Leave-One-Out Cross-Validation is a special case where k equals the total number of data
points, ideal for small datasets.
• Stratified Cross-Validation ensures that each fold maintains approximately the same class
distribution as the original dataset, preserving balance across subsets.
51
Prof. Smruti Vyavahare
Assessing Classifier Performance Using Bootstrap
• Bootstrap Overview
• Particularly effective when working with limited datasets
• Involves randomly drawing samples from the training data with replacement, ensuring each data point
has an equal chance of being picked multiple times
• This means a single data tuple can appear repeatedly in the training subset
• Multiple bootstrap techniques exist; one widely used variant is the .632 bootstrap method
• For a dataset containing d tuples, sampling is done d times with replacement, creating a training set of
size d
• Data points not selected during this process form the test set
• Approximately 63.2% of the original data is included in the bootstrap sample, while the remaining
36.8% serves as the test set (since (1 – 1/d)^d approaches e^-1 ≈ 0.368)
• This sampling and evaluation cycle is repeated k times to estimate the model's overall accuracy
52
Prof. Smruti Vyavahare
53
Prof. Smruti Vyavahare
(a) Modification of Decision Tree Algorithm with Count
In the basic decision tree (like ID3, C4.5, CART), the algorithm works with individual tuples.
Here, instead of individual records, we are given generalized tuples with an associated count (frequency).
When computing entropy, information gain, or Gini index, instead of treating each row as one record, weight each row
by its count.
(b) Constructing the Decision Tree
Step 1: Class distribution
Senior = 52
Junior = 113
Total = 165
Root entropy 0.899
Step 2: Information Gain for attributes
Using counts as weights:
Department → IG 0.049
Age → IG 0.425
Salary → IG 0.538
The best split = Salary (highest gain).
Step 3: Splitting by Salary
Salary values with their class distributions: Step 4: Splitting the 46–50K subset
• 26–30K → 46 juniors (pure Junior) 63 tuples (40 senior, 23 junior). If we split further:
• 31–35K → 40 juniors (pure Junior) • By Department:
• 41–45K → 4 juniors (pure Junior) • Sales → 30 seniors (pure Senior)
• 36–40K → 4 seniors (pure Senior) • Systems → 23 juniors (pure Junior)
• 66–70K → 8 seniors (pure Senior) • Marketing → 10 seniors (pure Senior)
• 46–50K → 40 seniors + 23 juniors (mixed → 63 total) This gives pure leaves.
All salary groups are pure leaves except 46–50K.
54
Prof. Smruti Vyavahare
Prof. Smruti Vyavahare
Thank You!
(smrutiv@[Link])
56
Prof. Smruti Vyavahare