Data Mining: Assignment on Classification (Solution)

University of Transportation and Communication, Ho Chi Minh City

August 21, 2025

Submission guideline
You may work in groups of 3-4 people. Turn in a single pdf document including part 1 and part
2, and your python notebook.

Part I
Manual Problems
1. This problem focuses on building decision trees from pre-aggregated data.

Dataset A

A summary of records for two classes (C1, C2) based on three binary attributes (A, B, C).
Note: The counts in the table (C1=12, C2=18, Total=30) are used for all calculations.

A B C C1 C2
T T T 0 1
T T F 0 4
T F T 0 1
T F F 0 1
F T T 0 2
F T F 2 5
F F T 5 1
F F F 5 3

Dataset B

Ten records with two binary attributes (A, B) and a class label (+, -). The summary
table is: Total records: C1(+)=4, C2(-)=6. Total=10.

A B C1 (+) C2 (-)
T T 3 1
T F 1 2
F T 0 0
F F 0 3

0.1 Part 1.1: Decision Tree Construction

a. Gini Gain Criterion:

1
 Dataset A - Gini Gain (Fully Grown)

Level 1: As calculated previously, the best split is on B (Gain = 0.1157).

Level 2 (Node B=T): Best split is on A (Gain = 0.023).
• Path B=T, A=T: Node is (C1=0, C2=5). This is a pure leaf node (Class C2).
• Path B=T, A=F: Node is (C1=2, C2=7). This node is impure. We must split
on the remaining attribute, C.
Level 2 (Node B=F): Best split is on A (Gain = 0.11175).
• Path B=F, A=T: Node is (C1=0, C2=2). This is a pure leaf node (Class C2).
• Path B=F, A=F: Node is (C1=10, C2=4). This node is impure. We must split
on C.
Level 3 Splits:
• Splitting Node (B=T, A=F) on C:
– Path B=T, A=F, C=T: Node is (C1=0, C2=2). Pure leaf node (Class C2).
– Path B=T, A=F, C=F: Node is (C1=2, C2=5). Impure leaf node (predicts
C2).
• Splitting Node (B=F, A=F) on C:
– Path B=F, A=F, C=T: Node is (C1=5, C2=1). Impure leaf node (predicts
C1).
– Path B=F, A=F, C=F: Node is (C1=5, C2=3). Impure leaf node (predicts
C1).

Dataset B - Gini Gain

Level 1: Best Split is B (Gain = 0.1633). Level 2 (Node B=F): Split on A. The
tree is now complete as all attributes have been used. The leaves (B=T), (B=F,
A=T), and (B=F, A=F) are final. The leaves (3,1) and (1,2) are impure because the
dataset contains conflicting examples for those attribute combinations.
b. Information Gain Criterion:

Dataset A - Information Gain (Fully Grown)

Level 1: As calculated previously, the best split is on A (Gain = 0.206).

• Path A=T: Node is (C1=0, C2=7). This is a pure leaf node (Class C2).
Level 2 (Node A=F): Best split is on B (Gain = 0.174).
• Path A=F, B=T: Node is (C1=2, C2=7). Impure. Must split on C.
• Path A=F, B=F: Node is (C1=10, C2=4). Impure. Must split on C.
Level 3 Splits:
• Splitting Node (A=F, B=T) on C:
– Path A=F, B=T, C=T: Node is (C1=0, C2=2). Pure leaf node (Class C2).
– Path A=F, B=T, C=F: Node is (C1=2, C2=5). Impure leaf node (predicts
C2).
• Splitting Node (A=F, B=F) on C:
– Path A=F, B=F, C=T: Node is (C1=5, C2=1). Impure leaf node (predicts
C1).
– Path A=F, B=F, C=F: Node is (C1=5, C2=3). Impure leaf node (predicts
C1).

2
 Dataset B - Information Gain

Level 1: Best Split is A (Gain = 0.2814). Level 2 (Node A=T): Split on B. The
tree is now complete as all attributes have been used. The leaves remain impure due
to conflicting examples in the data.

0.2 Part 1.2: Analysis and Comparison

• For Dataset A, Gini Gain and Information Gain produced different tree struc-
tures. Gini chose attribute B as the root, while Information Gain chose A.
• For Dataset B, they also produced different tree structures. Gini chose B as
the root, while Information Gain chose A.
• Similarities: Both are impurity measures aiming to create purer child nodes. They
evaluate splits by measuring the reduction in impurity.
• Differences: Information Gain uses entropy (log function), which penalizes impurity
more heavily, while Gini is a simpler quadratic calculation. As shown here, this
mathematical difference can lead them to prefer different splits, especially when gain
values are close, resulting in different final trees.

2. This problem explores the greedy approach and classification error rate.

Dataset C

Note: The counts in the table (C1=100, C2=100, Total=200) are used for all calculations.

Questions
(a) Compute a two-level decision tree using the greedy approach.
Splitting Attribute at Level 1: First, we compute the error rate for splitting on
each attribute at the root node.
• Attribute X:
– X=0: (C1=60, C2=60). Error = 60.
– X=1: (C1=40, C2=40). Error = 40.
– Total Error = (60 + 40)/200 = 0.5.
• Attribute Y:
– Y=0: (C1=40, C2=60). Error = 40.
– Y=1: (C1=60, C2=40). Error = 40.
– Total Error = (40 + 40)/200 = 0.4.
• Attribute Z:
– Z=0: (C1=30, C2=70). Error = 30.
– Z=1: (C1=70, C2=30). Error = 30.
– Total Error = (30 + 30)/200 = 0.3.
Since attribute Z gives the lowest error rate (0.3), it is chosen as the splitting attribute
at level 1.
Splitting Attribute at Level 2: After splitting on Z, we consider the child nodes.
• For the Z=0 child node: The error rate for splitting on X is (15+15)/100 = 0.3.
The error rate for splitting on Y is also (15 + 15)/100 = 0.3. We can choose
either X or Y.

3
 B?

T F

A? A?

T F T F

C2 C2
(0,5) C? (0,2) C?

T F T F

C2 C2 C1 C1
(0,2) (2,5) (5,1) (5,3)
Dataset A - Gini (Fully Grown)

A?

T F

C2
(0,7) B?

T F

C? C?

T F T F

C2 C2 C1 C1
(0,2) (2,5) (5,1) (5,3)
Dataset A - Info Gain (Fully Grown)

Figure 1: Fully Grown Decision Trees for Dataset A

• For the Z=1 child node: The error rate for splitting on X is (15+15)/100 = 0.3.
The error rate for splitting on Y is also (15 + 15)/100 = 0.3. We can choose
either X or Y.
The resulting two-level tree splits on Z at the root, and then on either X or Y at the
second level.
Overall Error Rate: The total number of misclassified examples is 15 + 15 + 15 +
15 = 60. The overall error rate is 60/200 = 0.3.
(b) Build a tree with X as the first split.
Splitting Attribute at Level 2 (after splitting on X):
• For the X=0 child node:
– Splitting on Y: Error = (5 + 5)/120 = 10/120.

4
 B?
(4,6)

T F

+ A?
(3,1) (1,5)

T F
- -
(1,2) (0,3)

Dataset B - Gini
A?
(4,6)

T F

B? -
(4,3) (0,3)

T F
+ -
(3,1) (1,2)

Dataset B - Info Gain

Figure 2: Decision Trees for Dataset B (Cannot be split further)

– Splitting on Z: Error = (15 + 15)/120 = 30/120.

– Attribute Y provides a better split.
• For the X=1 child node:
– Splitting on Y: Error = (5 + 5)/80 = 10/80.
– Splitting on Z: Error = (15 + 15)/80 = 30/80.
– Attribute Y provides a better split.
The tree splits on X at the root, and then on Y at the second level for both branches.
Overall Error Rate: The total number of misclassified examples is 10 + 10 = 20.
The overall error rate is 20/200 = 0.1.
(c) Compare the error rates. The error rate for the greedy approach in part (a) is 0.3,
which is significantly larger than the 0.1 error rate from the tree in part (b). This
result demonstrates that a greedy heuristic, which makes the locally optimal choice
at each step, does not always produce a globally optimal solution. The initial split

5
 on Z in part (a) seemed best at level 1, but it led to a worse overall tree than the
one constructed by starting with the suboptimal attribute X.

3. This problem explores the Naive Bayes classifier and the effect of probability estimation
methods.

Dataset D

From the data, we have 10 records.

• Class +: 5 records
• Class -: 5 records

Therefore, the prior probabilities are P (+) = 5/10 = 0.5 and P (−) = 5/10 = 0.5.

Questions
(a) Estimate the conditional probabilities.
We calculate the conditional probabilities for each attribute value given the class.
• For Class = + (5 records):
– P (A = 0|+) = 2/5 = 0.4
– P (A = 1|+) = 3/5 = 0.6
– P (B = 0|+) = 4/5 = 0.8
– P (B = 1|+) = 1/5 = 0.2
– P (C = 0|+) = 1/5 = 0.2
– P (C = 1|+) = 4/5 = 0.8
• For Class = - (5 records):
– P (A = 0|−) = 1/5 = 0.2
– P (A = 1|−) = 4/5 = 0.8
– P (B = 0|−) = 2/5 = 0.4
– P (B = 1|−) = 3/5 = 0.6
– P (C = 0|−) = 0/5 = 0
– P (C = 1|−) = 5/5 = 1.0
(b) Use the estimate of conditional probabilities given in the previous question to predict
the class label for a test sample (A = 0, B = 1, C = 0) using the naive Bayes approach.
We need to compare P (+ | A = 0, B = 1, C = 0) with P (− | A = 0, B = 1, C = 0).
• P (+ | sample) ∝ P (A = 0|+) × P (B = 1|+) × P (C = 0|+) × P (+)
= 0.4 × 0.2 × 0.2 × 0.5 = 0.008
• P (− | sample) ∝ P (A = 0|−) × P (B = 1|−) × P (C = 0|−) × P (−)
= 0.2 × 0.6 × 0 × 0.5 = 0
Since 0.008 > 0, the class label should be ’+’.
(c) Estimate the conditional probabilities using the m-estimate approach, with p = 1/2
and m = 4.
The formula is P (xi |cj ) = nn+m
c +mp
, where n is the number of records in class cj , nc is
the count of xi in class cj , p is the prior probability (1/2 for binary attributes), and
m is the equivalent sample size. Here, n = 5 for both classes.
• For Class = +:

6
 – P (A = 0|+) = (2 + 4 × 0.5)/(5 + 4) = 4/9
– P (B = 1|+) = (1 + 4 × 0.5)/(5 + 4) = 3/9
– P (C = 0|+) = (1 + 4 × 0.5)/(5 + 4) = 3/9
• For Class = -:
– P (A = 0|−) = (1 + 4 × 0.5)/(5 + 4) = 3/9
– P (B = 1|−) = (3 + 4 × 0.5)/(5 + 4) = 5/9
– P (C = 0|−) = (0 + 4 × 0.5)/(5 + 4) = 2/9
(d) Repeat part (b) using the conditional probabilities given in part (c).
• P (+ | sample) ∝ P (A = 0|+) × P (B = 1|+) × P (C = 0|+) × P (+)
= (4/9) × (3/9) × (3/9) × 0.5 = 36/729 × 0.5 ≈ 0.0247
• P (− | sample) ∝ P (A = 0|−) × P (B = 1|−) × P (C = 0|−) × P (−)
= (3/9) × (5/9) × (2/9) × 0.5 = 30/729 × 0.5 ≈ 0.0206
Since 0.0247 > 0.0206, the class label should be ’+’.
(e) Compare the two methods for estimating probabilities. Which method is better and
why?
The m-estimate approach is better. The standard probability estimate in part
(a) suffers from the zero-probability problem. When a conditional probability
is zero (like P (C = 0|−)), the entire posterior probability for that class becomes
zero, regardless of the other evidence. This is a very brittle and overly confident
conclusion. The m-estimate approach avoids this by adding pseudo-counts, ensuring
that no probability estimate is ever exactly zero, which makes the model more robust.

4. Given the data sets shown in the figure, explain how the classifiers would perform. (Re-
ferring to the six synthetic datasets in the provided PDF).

5. Given the data sets shown in the figure, explain how the classifiers would perform. (Re-
ferring to the six synthetic datasets in the provided PDF).

(a) For this dataset, both the Decision Tree and Naive Bayes classifiers will perform
well. This is because the ”distinguishing attributes” have strong predictive power,
which will be identified by the decision tree’s entropy gain and by the high conditional
probabilities in the Naive Bayes model. In contrast, k-NN will not perform as well
because its distance calculations will be negatively impacted by the large number of
irrelevant ”noise attributes”.
(b) Naive Bayes will not work at all for this dataset. Its core assumption of attribute
independence is violated here, as the class label clearly depends on the interaction
between attributes. Other classifiers, such as Decision Trees or k-NN, will perform
better because they do not make this assumption.
(c) Naive Bayes is expected to perform very well on this dataset. The data is struc-
tured such that each distinguishing attribute has a higher conditional probability for
one class over the other. Naive Bayes excels in this scenario by multiplying these in-
dividual probabilities to make a final classification. A Decision Tree, however, will
not perform as well. Due to the relatively large number of distinguishing attributes,
it will likely create an overly complex tree and suffer from an overfitting problem.
k-NN should perform reasonably well.
(d) For this dataset, k-NN will perform well due to its ability to capture local patterns.
A Decision Tree will also work, but it will likely result in a fairly large and complex
tree. The initial splits of the tree may seem random, as it might struggle to find
a good initial attribute that cleanly separates the checkerboard-like data. Naive

7
 Bayes will not perform as well because the clear attribute dependency violates its
core assumption.
(e) k-NN is well-suited for this dataset and will perform well. A standard Decision
Tree can also work, but it will create a large tree by approximating the non-linear
boundary with many horizontal and vertical splits. If the decision tree could use
an ”oblique” (diagonal) split, it would be much more compact and highly accurate.
Naive Bayes will not perform well due to the attribute dependency that defines the
shape of the data clusters.
(f ) k-NN works best for this dataset, as its distance-based approach can easily handle
the concentric circular boundaries. Naive Bayes will not work well because its linear
decision boundary cannot separate the circles, a clear case of attribute dependency.
A Decision Tree would have to create a very large and complex tree to approximate
the circular boundaries.