Data Mining:
Concepts and Techniques
(3rd ed.)
Chapter 9
Classification: Advanced Methods
Jiawei Han, Micheline Kamber, and Jian Pei
University of Illinois at Urbana-Champaign &
Simon Fraser University
©2011 Han, Kamber & Pei. All rights reserved.
1
Numerical Modelling
1. Decision Tree: Gini Index
Calculation
GivenFeature
a dataset
1
with the following
Feature 2
information:
(X1) (X2) Class
1 1 A
1 2 A
2 1 B
2 2 A
2 1 A
Calculate the Gini index for splitting the
dataset on Feature 1. 2
Solution:
• For Feature 1 = 1, we have 2 instances of class
A, and for Feature 1 = 2, we have 3 instances (2
of class A and 1 of class B).
• Gini for Feature 1:
• For Feature 1 = 1:
• P(A) = 2/2 = 1,
• Gini = 1 - (12) = 0.
• For Feature 1 = 2:
• P(A) = 2/3, P(B) = 1/3,
• Gini = 1 - (2/3) 2 - (1/3) 2 = 0.444.
Weighted Gini = (2/5 * 0) + (3/5 * 0.444) =
0.266.
3
Numerical Modelling
2. Naive Bayes Classification
Given a dataset with two features (X1 and X2) and
binary classes (A and B):
X1 X2 Class
1 2 A
2 3 A
3 3 B
3 4 B
2 4 B
Assume you are classifying a new instance (X1 = 2, X2
= 3). Calculate the posterior probability for Class A
and Class B using Naive Bayes.
4
Solution:
P(A) = 2/5, P(B) = 3/5.
P(X1=2|A) = 1/2, P(X2=3|A) = 1/2.
P(X1=2|B) = 1/3, P(X2=3|B) = 1/3.
•Posterior for A:
P(A|X1=2, X2=3) ∝ P(A) * P(X1=2|A) * P(X2=3|A)
= (2/5) * (1/2) * (1/2) = 0.1.
•Posterior for B:
P(B|X1=2, X2=3) ∝ P(B) * P(X1=2|B) * P(X2=3|B)
= (3/5) * (1/3) * (1/3) = 0.1.
•Both classes have equal posterior probabilities, so
classify as either class (A or B).
5
Numerical Modelling
3. k-NN Classification: Consider the
following dataset:
X1 X2 Class
1 2 A
1 3 A
4 4 B
5 5 B
3 2 A
Classify the point (X1 = 2, X2 = 3) using k-NN
with k = 3. 6
Solution:
Find the 3 nearest neighbors to (2, 3):
• Distance to (1, 2): sqrt((2-1)^2 + (3-2)^2) = sqrt(2) ≈ 1.41.
• Distance to (1, 3): sqrt((2-1)^2 + (3-3)^2) = sqrt(1) = 1.
• Distance to (4, 4): sqrt((2-4)^2 + (3-4)^2) = sqrt(5) ≈ 2.24.
• Distance to (5, 5): sqrt((2-5)^2 + (3-5)^2) = sqrt(18) ≈
4.24.
• Distance to (3, 2): sqrt((2-3)^2 + (3-2)^2) = sqrt(2) ≈ 1.41.
Nearest neighbors: (1, 3), (3, 2), (1, 2).
Class A appears 3 times, and Class B appears 0 times.
Classify the point as Class A.
7
Numerical Modelling
4. Confusion Matrix and Accuracy:
Consider a binary classifier with the following
confusion matrix:
Predicted A Predicted B
Actual A 50 10
Actual B 15 25
Calculate the following:
• Accuracy
• Precision for Class A
• Recall for Class A
8
Solution:
•Accuracy = (True Positive + True
Negative) / Total = (50 + 25) / (50 +
10 + 15 + 25) = 75 / 100 = 0.75.
•Precision for A = True Positive /
(True Positive + False Positive) = 50 /
(50 + 15) = 0.77.
•Recall for A = True Positive / (True
Positive + False Negative) = 50 / (50
+ 10) = 0.83.
9
Numerical Modelling
5. Entropy for a Dataset: Given the
following dataset:
Feature Class Feature
X A X
X A X
Y B Y
Y B Y
Z B Z
Calculate the entropy for the Class
attribute.
10
Solution:
•Total instances = 5.
•P(A) = 2/5, P(B) = 3/5.
•Entropy = -[P(A) * log2(P(A)) +
P(B) * log2 (P(B))]
= -[(2/5) * log2 (2/5) +
(3/5) * log2 (3/5)] ≈ 0.971.
11
Numerical Modelling
6.K-means Clustering: Finding
Centroids: Given the following
dataset:
X1 X2
1 2
1 3
4 5
5 5
Apply K-means with k=2 (initial centroids:
(1, 2) and (4, 5)). Calculate the new
centroids after one iteration.
12
Solution:
Assign each point to the nearest
centroid:
• (1, 2) → Cluster 1.
• (1, 3) → Cluster 1.
• (4, 5) → Cluster 2.
• (5, 5) → Cluster 2.
Calculate the new centroids:
• Centroid 1: Mean of (1, 2) and (1, 3) = (1,
2.5).
• Centroid 2: Mean of (4, 5) and (5, 5) = (4.5,
5).
13
1
Classification: ROC 4
and AUC
Receiver-operating characteristic curve
(ROC)
• The ROC curve is a visual representation of model
performance across all thresholds.
• The long version of the name, receiver operating
characteristic, is a holdover from WWII radar
detection.
1
Classification: ROC 5
and AUC
Receiver-operating characteristic curve
(ROC)
• The ROC curve is drawn by calculating the
true positive rate (TPR) and false positive
rate (FPR) at every possible threshold (in
practice, at selected intervals), then
graphing TPR over FPR.
•
• A perfect model, which at some threshold
has a TPR of 1.0 and an FPR of 0.0, can be
represented by either a point at (0, 1) if all
other thresholds are ignored, or by the
1
Classification: ROC 6
and AUC
Receiver-operating characteristic curve
(ROC)
ROC and AUC of a
hypothetical
perfect model.
1
Classification: ROC 7
and AUC
Area under the curve (AUC)
The area under the ROC curve (AUC)
represents the probability that the
model, if given a randomly chosen
positive and negative example, will rank
the positive higher than the negative.
1
Classification: ROC 8
and AUC
Area under the curve (AUC)
The perfect model above, containing a square with
sides of length 1, has an area under the curve
(AUC) of 1.0.
This means there is a 100% probability that the
model will correctly rank a randomly chosen
positive example higher than a randomly chosen
negative example.
In other words, looking at the spread of data points
below, AUC gives the probability that the model will
place a randomly chosen square to the right of a
1
Classification: ROC 9
and AUC
Area under the curve (AUC)
The AUC is 0.5, representing a 50% probability of
correctly ranking a random positive and negative
example.
In the spam classifier example, a spam classifier
with AUC of 0.5 assigns a random spam email a
higher probability of being spam than a random
legitimate email only half the time.
2
Classification: ROC 0
and AUC
Area under the curve (AUC)
ROC and AUC of
completely
random guesses.
2
Classification: ROC 1
and AUC
AUC and ROC work well for comparing models
when the dataset is roughly balanced between
classes.
When the dataset is imbalanced, precision-
recall curves (PRCs) and the area under those
curves may offer a better comparative
visualization of model performance.
Precision-recall curves are created by plotting
precision on the y-axis and recall on the x-axis
across all thresholds.
2
Classification: ROC 2
and AUC
Numerical Modelling
7. ROC Curve: Consider the following
classifier output, Plot the ROC curve.
True False True False
Threshold Positives Positives Negatives Negatives
0.2 80 30 40 50
0.5 70 20 50 60
0.8 60 10 60 70
23
Solution:
For the threshold of 0.5:
• Sensitivity (True Positive Rate) = TP /
(TP + FN) = 70 / (70 + 60) = 0.54.
• Specificity (True Negative Rate) = TN /
(TN + FP) = 50 / (50 + 20) = 0.71.
Plot points (0.71, 0.54) on the ROC
curve for this threshold.
24
Numerical Modelling
8. Classification Error: A classifier
predicts the following: Calculate the
classification error.
Actual Predicted
A A
A B
B B
A A
B A
25
Solution:
•Classification
error = (False
Positives + False Negatives) / Total
Instances.
•False Positives = 1 (A predicted as
B), False Negatives = 1 (B
predicted as A).
•Error = (1 + 1) / 5 = 0.4.
26
Numerical Modelling
9. Advanced Decision Tree: Information
Gain and Splitting: You are given the
following dataset with one feature (X1) and
the target variable "Class". Calculate the
information
X1
gain if you Class
split the dataset on the
feature1 "X1". A
1 A
2 B
2 A
3 B
3 B
3 A
27
Solution:
[Link] of the entire dataset
(S):
P(A) = 4/7, P(B) = 3/7.
Entropy(S) = -[(4/7) * log 2(4/7) + (3/7)
* log2(3/7)] ≈ 0.985.
[Link] of subsets after split
by X1:
For X1 = 1: (2 instances of A, 0
instances of B)
Entropy(1) = 0.
28
Solution:
For X1 = 2: (1 instance of A, 1 instance of B)
Entropy(2) = -[(1/2) * log 2 (1/2) + (1/2) * log2
(1/2)] = 1.
For X1 = 3: (2 instances of A, 1 instance of B)
Entropy(3) = -[(2/3) * log 2 (2/3) + (1/3) * log2
(1/3)] ≈ 0.918.
3. Information Gain (IG) for splitting
by X1:
Weighted Entropy = (2/7 * 0) + (2/7 * 1) +
(3/7 * 0.918) ≈ 0.651.
IG = Entropy(S) - Weighted Entropy = 0.985 -
0.651 = 0.334. 29
Numerical Modelling
10. Evaluation Metrics: F1 Score
and Imbalanced Data: You have a
binary classification model with the
following confusion matrix:
Predicted A Predicted B
Actual A 30 5
Actual B 2 50
Calculate the F1 score and interpret its
significance in the case of imbalanced
data.
30
Solution:
•Precision for Class A = TP / (TP + FP)
= 30 / (30 + 2) = 0.94.
•Recall for Class A = TP / (TP + FN) =
30 / (30 + 5) = 0.857.
•F1 Score for Class A = 2 * (Precision
* Recall) / (Precision + Recall) = 2 *
(0.94 * 0.857) / (0.94 + 0.857) ≈
0.897.
31
Numerical Modelling (Home Task) 3
2
1. Decision Tree: Information
Gain
Calculate the Information Gain if
you split the dataset on "Feature".
Given the dataset:
Feature Class
1 A
2 A
2 B
3 B
3 A
Numerical Modelling (Home Task) 3
3
2. Decision Tree: Gini Index
Calculate the Gini Index for
splitting on Feature 1. Given a
dataset with the following
distribution:
Feature 1 Feature 2 Class
1 2 A
1 3 A
2 3 B
2 4 B
3 3 A
Numerical Modelling (Home Task) 3
4
3. Naive Bayes: Posterior
Calculation
You are classifying a new instance
with X1=2X1=2 and X2=3X2=3 using a
Naive Bayes classifier. Given the
following data: Calculate the posterior
probability for Class A and Class B.
X1 X2 Class
1 2 A
2 3 A
3 3 B
4 4 B
5 4 B
Numerical Modelling (Home Task) 3
5
4. k-NN Classification
Given the following training dataset:
Classify the point (X1 = 2, X2 = 3)
using k-NN with k = 3.
X1 X2 Class
1 2 A
1 3 A
4 5 B
5 5 B
Numerical Modelling (Home Task) 3
6
5. Support Vector Machine (SVM)
Using a linear SVM, describe
the decision boundary that separates
classes A and B.
Given the dataset:
X1 X2 Class
2 2 A
3 3 A
5 4 B
6 4 B
Numerical Modelling (Home Task) 3
7
6. Random Forest: Feature
Importance
You have trained a Random Forest with
the following feature usage:
Feature X1: 40% of trees
Feature X2: 30% of trees
Feature X3: 30% of trees
Which feature is most important, and
what does this indicate about feature
selection?
Numerical Modelling (Home Task) 3
8
7. Random Forest: Evaluation
Metric
Calculate the Accuracy, Precision,
and Recall for Class A.
Given the confusion matrix for a binary
classification problem:
Predicted A Predicted B
Actual A 50 10
Actual B 15 25
Numerical Modelling (Home Task) 3
9
8. F1 Score and Imbalanced Data
Calculate the F1 Score for Class A.
Given the confusion matrix:
Predicted A Predicted B
Actual A 10 20
Actual B 5 50
Numerical Modelling (Home Task) 4
0
9. Support Vector Machine: Soft
Margin
Given the following points:
Using a soft margin SVM, describe the
trade-off when you decrease the
regularization parameter C.
X1 X2 Class
1 2 A
3 3 A
4 5 B
6 5 B
Numerical Modelling (Home Task) 4
1
10. Evaluation Metrics: ROC and
AUC
Given the following classifier outputs for
different thresholds:
Plot the ROC curve and calculate
the AUC for threshold = 0.5.
True False True False
Threshold Positives Positives Negatives Negatives
0.2 80 30 40 50
0.5 70 20 50 60
Numerical Modelling (Home Task) 4
2
11. Naive Bayes: Likelihood
Calculation
You are classifying a data
point X=[X1=3,X2=4]X=[X1=3,X2=4] u
sing a Naive Bayes classifier.
If the likelihood for Class A
is P(X∣A)=0.2P(X∣A)=0.2 and for Class
B it is P(X∣B)=0.4P(X∣B)=0.4, and prior
probabilities
are P(A)=0.6P(A)=0.6 and P(B)=0.4P(B)
=0.4, calculate the posterior
4
3
Modify the Basic Decision
Tree Algorithm to Take
Into Consideration the
Count of Each Generalized
Data Tuple
Given Data 4
4
Departme Status Age Salary Count
nt
Sales Senior 31: : :35 46K: : :50 30
K
Sales Junior 26: : :30 26K: : :30 40
K
Sales Junior 31: : :35 31K: : :35 40
K
Systems Junior 21: : :25 46K: : :50 20
K
Systems Senior 31: : :35 66K: : :70 5
K
Systems Junior 26: : :30 46K: : :50 3
K
Systems Senior 41: : :45 66K: : :70 3
K
Marketing Senior 36: : :40 46K: : :50 10
Given Data 4
5
In a typical decision tree algorithm, each
instance (data tuple) is treated as a
unique sample, and the splits are made
based on the feature values of each
tuple.
However, in this case, some of the
entries in the table
represent generalized data tuples,
and each tuple has a count that
indicates how many actual data points
fall under that entry.
4
The decision tree algorithm can be modified
6
to account for these counts as follows:
Modifications for Using Counts in
Decision Tree Construction:
[Link] Splits:
• Instead of treating each data tuple as one
instance, we would treat the count as
the weight of the data tuple.
• The splitting criterion (such
as Information Gain or Gini Index) should
then consider these counts, treating each
generalized tuple as if it represents a number
2. Information Gain with Counts: 4
• In calculating Information Gain, we
7
compute the entropy based on the
weighted frequencies of the classes.
Specifically, for each possible split, the
weighted entropy of the child nodes
should be computed using the count as
the weight of the data instances.
3. Formula for Weighted Entropy:
Given a set of data tuples, the
weighted entropy EE for a split on
an attribute is calculated as:
where: 4
8
• Count iis the number of instances
of the class in the i-th subset,
• Total count is the total count of all
tuples.
4. Information Gain:
The Information Gain (IG) for a split
would be:
Step 1: Calculate the Total Entropy 4
9
for the Dataset
First, let’s calculate the total
entropy for the entire dataset.
Since the status attribute is the class
label, we need to compute the entropy
based on the distribution
of junior and senior statuses, weighted
by their counts.
Total Count of the Data:
The sum of all the counts in the table:
Total count=30+40+40+20+5+3+3+10
Class Distribution: 5
0
•Junior: Sum of counts where status =
junior
= 40+40+20+3+6=10940+40+20+3+
6=109
•Senior: Sum of counts where status =
senior
= 30+5+3+10+4+4=5630+5+3+10+4
+4=56
Entropy of the entire dataset:
The entropy is calculated using the
formula:
where P(Ci) is the probability of each 5
1
class Ci(junior and senior).
Let's compute this:
Naïve Bayesian Classification of the 5
2
Status for the Tuple ("systems,"
"26...30," "46–50K")
We will now apply the Naïve
Bayes algorithm to classify a data tuple
with the values department =
"systems", age = "26-30", and salary
= "46-50K".
Step 1: Calculate Prior Probabilities:
We need the prior probabilities for the
two classes (junior and senior).
These were calculated earlier:
Step 2: Calculate Likelihood for Each 5
3
Class:
Next, we calculate the likelihood of
observing the given features for each
class, assuming independence between
features.
Step 2: Calculate Likelihood for Each 5
4
Class:
•For P(department = "systems" |
junior) and P(department =
"systems" | senior):
• Junior systems count = 20, Total
junior count = 109
• P(department = "systems" |
junior) = 20/109
• Senior systems count = 5, Total
senior count = 56
• P(department = "systems" |
senior) = 5/56
Step 2: Calculate Likelihood for Each 5
5
Class:
•For P(age = "26-30" |
junior) and P(age = "26-30" | senior):
• Junior age 26-30 count =
40, Total junior count = 109
• P(age = "26-30" |
junior) = 40/109
• Senior age 26-30 count =
6, Total senior count = 56
• P(age = "26-30" | senior) = 6/56
Step 2: Calculate Likelihood for Each 5
6
Class:
•For P(salary = "46-50K" |
junior) and P(salary = "46-50K" |
senior):
• Junior salary 46-50K count =
40, Total junior count = 109
• P(salary = "46-50K" |
junior) = 40/109
• Senior salary 46-50K count =
10, Total senior count = 56
• P(salary = "46-50K" |
senior) = 10/56
Step 3: Compute Posterior Probabilities: 5
7
We compute the posterior probability for each
class using Bayes’ Theorem:
P(junior∣data) ∝ P(junior)⋅ P(department = "systems“
∣junior )⋅ P(age = "26-30"∣junior)⋅P(salary = "46-
50K"∣junior)
P(senior∣data) ∝ P (senior) ⋅P (department
= "systems“ ∣senior) ⋅P(age = "26-
30"∣senior)⋅P(salary = "46-50K"∣senior)
After calculating these, we can compare the
two posterior probabilities and classify the
instance as junior or senior based on the
Numerical Problem 5
8
The table lists tuples sorted by
decreasing probability, with a class
label (P for positive, N for negative)
and a classifier-provided probability
value for each tuple:
Numerical Problem 5
9
Tuple # Class Probability
1 P 0.95
2 N 0.85
3 P 0.78
4 P 0.66
5 N 0.60
6 P 0.55
7 N 0.53
8 N 0.52
9 N 0.51
10 P 0.40
Numerical Problem 6
The data tuples of table are sorted by 0
decreasing probability value, as returned by
a classifier.
For each tuple, compute the values for the
number of true positives .TP,
false positives .FP,
true negatives .TN, and
false negatives .FN.
Compute the true positive rate .TPR and false
positive rate, FPR.
Plot the ROC curve for the data.
Numerical Problem 6
1. Understanding (TP), (FP), (TN), and 1
(FN):
For each threshold, the predictions will be made by
comparing the classifier’s probability against the
threshold value. We will classify a tuple as:
True Positive (TP): If the class
is P (positive) and the predicted class
is P (true positive).
False Positive (FP): If the class
is N (negative) but the predicted class
is P (false positive).
True Negative (TN): If the class
is N (negative) and the predicted class
Numerical Problem 6
2. True Positive Rate (TPR) and False 2
Positive Rate (FPR):
True Positive Rate (TPR) is the proportion
of positive instances correctly identified:
TPR = TP / (TP+FN)or P
False Positive Rate (FPR) is the proportion
of negative instances incorrectly classified as
positive:
FPR = FP / (FP+TN)or N
Numerical Problem 6
3
Tuple Clas Probabilit
# s y TP FP TPR FPR
1 P 0.95 1 0
2 N 0.85 1 1
3 P 0.78 2 1
4 P 0.66 3 1
5 N 0.60 3 2
6 P 0.55 4 2
7 N 0.53 4 3
8 N 0.52 4 4
9 N 0.51 4 5
10 P 0.40 5 5
6
4