Lecture 05: Decision Tree Classification & Information Theory

Course: Introduction to Data Analytics (CE KMITL)
Source Material: DA07.1 Decision Tree.pdf (18 slides)
Key Topics: Decision Tree anatomy (Root, Decision Nodes, Branches, Leaves), Shannon Entropy ($H(S)$), Conditional Entropy ($H(S \mid A)$), Information Gain ($IG$), Mathematical glyph normalization ($\log_2$), Complete 7-sample Medical Flu Diagnosis case study, Step-by-step arithmetic derivations, Subtree recursive splitting, Mermaid decision tree visualization, and ID3/C4.5/CART comparative foundations.

1. Decision Tree Architecture & Anatomy

A Decision Tree is a non-parametric supervised learning model that recursively partitions the input feature space into rectangular, axis-aligned regions. In decision analysis and operations research, it represents a visual, flow-like model of decisions and their consequences (including chance events, resource costs, and utility). In machine learning, it operates as a hierarchical sequence of conditional tests to classify observations or predict continuous values.

1.1 Structural Components

1. Root Node:
   • The topmost node in the tree hierarchy with zero incoming edges.
   • Evaluates the single most informative feature across the entire initial dataset $S$.
2. Internal Nodes (Decision / Chance Nodes):
   • Intermediate evaluation nodes having exactly one incoming edge and two or more outgoing branches.
   • Each internal node specifies a test condition on a single attribute $A$ (e.g., $A = v$ for categorical features, or $A \le \theta$ for continuous numerical features).
3. Branches (Edges):
   • Outgoing pathways representing each mutually exclusive outcome or value $v \in \text{Values}(A)$ of the parent node’s test condition.
4. Leaf Nodes (Terminal Nodes / End Nodes):
   • Bottom nodes having one incoming edge and zero outgoing branches.
   • Each leaf represents a definitive final prediction: a class label for classification tasks or a scalar value (mean target value) for regression tasks.

1.2 Decision Tree Representation Types

In decision analysis and operations research, nodes are traditionally distinguished by geometric shapes:

• Decision Nodes (typically drawn as squares): Represent choice points under direct control of the decision maker.
• Chance Nodes (typically drawn as circles): Represent probabilistic events outside direct control.
• End Nodes (typically drawn as triangles): Represent terminal outcomes and payoffs.

In machine learning classification trees (e.g., the ID3, C4.5, and CART algorithms), internal nodes represent empirical attribute tests, branches represent discrete feature values, and terminal leaves designate class predictions.

2. Information Theory Foundations

To construct an optimal decision tree from data, an algorithm must decide which feature to evaluate at each node. The goal is to select splits that partition the training instances into subsets that are as pure (homogenous) as possible with respect to the target class.

Information theory provides the mathematical metric for impurity: Shannon Entropy.

2.1 Shannon Entropy Formula

Let $S$ be a collection of training examples, and let $c$ be the number of distinct classes in the target variable. The Shannon Entropy $H(S)$ measures the average amount of information, uncertainty, or impurity contained in $S$:

$$H(S) = - \sum_{i=1}^{c} p_i \log_2(p_i)$$

Where:

• $c$ is the number of distinct target classes.
• $p_i = \frac{|S_i|}{|S|}$ is the empirical probability (proportion) of examples in $S$ belonging to class $i$.
• $\log_2$ is the base-2 logarithm, measuring information in bits.

Mathematical Font Normalization: In the source PowerPoint lecture slides (DA07.1 Decision Tree.pdf, slides 12–14), the base-2 logarithm operator suffered an encoding shift in the CambriaMath engine. In these notes, all equations are fully restored to standard LaTeX:

$$\text{Restored Standard LaTeX Operator: } \mathbf{\log_2}$$

Fundamental Properties of Entropy:

1. Minimum Entropy ($H(S) = 0.0$ bits):
   • Occurs when all examples in $S$ belong to the exact same class ($p_1 = 1.0, p_{i \ne 1} = 0$).
   • The dataset is pure; there is zero uncertainty.
   • By algebraic convention: $0 \log_2(0) = 0$ (justified by $\lim_{p \to 0^+} p \log_2(p) = 0$).
2. Maximum Entropy for Binary Classification ($H(S) = 1.0$ bit):
   • Occurs when classes are evenly balanced ($p_1 = 0.5, p_2 = 0.5$):

     $$H(S) = - \left( 0.5 \log_2(0.5) + 0.5 \log_2(0.5) \right) = - (0.5 \cdot (-1) + 0.5 \cdot (-1)) = 1.0 \text{ bit}$$

   • The dataset contains maximum impurity and unpredictability.
3. General Maximum Entropy:
   • For $c$ equally likely classes ($p_i = 1/c$), maximum entropy is $H_{\max} = \log_2(c)$.

2.2 Conditional Entropy (Expected Entropy After a Split)

When we partition dataset $S$ using an explanatory attribute $A$ that takes values $v \in \text{Values}(A)$, the dataset is divided into disjoint subsets:

$$S_v = \{ s \in S \mid A(s) = v \}$$

The Conditional Entropy $H(S \mid A)$ measures the expected remaining impurity across all resulting branches, weighted by each branch’s sample size:

$$H(S \mid A) = \sum_{v \in \text{Values}(A)} \frac{|S_v|}{|S|} H(S_v)$$

Where:

• $|S|$ is the total number of samples in parent dataset $S$.
• $|S_v|$ is the number of samples in the branch where attribute $A$ has value $v$.
• $\frac{|S_v|}{|S|}$ is the weight (fraction of samples) routed down branch $v$.
• $H(S_v) = - \sum_{i=1}^c p_{i,v} \log_2(p_{i,v})$ is the internal Shannon entropy of branch subset $S_v$.

2.3 Information Gain ($IG$)

The Information Gain $IG(S, A)$ is the expected reduction in entropy achieved by partitioning dataset $S$ according to attribute $A$:

$$IG(S, A) = H(S) - H(S \mid A)$$

• $H(S)$ is the base entropy of the dataset prior to splitting.
• $H(S \mid A)$ is the remaining weighted conditional entropy after splitting.
• Optimization Equivalence:

  $$\arg\max_{A} IG(S, A) \iff \arg\min_{A} H(S \mid A)$$

  Because the base entropy $H(S)$ is constant for all candidate attributes at a given node, maximizing Information Gain is mathematically equivalent to selecting the attribute that minimizes the conditional entropy $H(S \mid A)$.

3. Medical Flu Diagnosis Case Study (Complete 7-Sample Dataset)

To demonstrate the step-by-step mathematical construction of a decision tree via the ID3 algorithm, the lecture presents a real diagnostic dataset comprising 7 clinical patient records.

3.1 Complete Training Dataset Table

3.2 Dataset Characterization & Base Entropy Calculation

• Total Sample Count: $|S| = 7$ patients.
• Candidate Explanatory Attributes:
  • Temperature $\in \{\text{normal}, \text{high}, \text{very\_high}\}$
  • Headache $\in \{\text{YES}, \text{no}\}$
  • Nausea $\in \{\text{YES}, \text{no}\}$
• Target Variable: Flu $\in \{\text{YES}, \text{no}\}$:
  • $\text{Flu} = \text{YES}$: Cases 1, 2, 4 (Total = $3$ patients)
  • $\text{Flu} = \text{no}$: Cases 3, 5, 6, 7 (Total = $4$ patients)

Base Dataset Entropy $H(S)$:

$$p_{\text{YES}} = \frac{3}{7} \approx 0.4286, \quad p_{\text{no}} = \frac{4}{7} \approx 0.5714$$

$$H(S) = - \left[ \frac{3}{7} \log_2\left(\frac{3}{7}\right) + \frac{4}{7} \log_2\left(\frac{4}{7}\right) \right]$$

Evaluating the logarithms:

• $\log_2(3/7) = \log_2(3) - \log_2(7) \approx 1.5850 - 2.8074 = -1.2224$
• $\log_2(4/7) = \log_2(4) - \log_2(7) \approx 2.0000 - 2.8074 = -0.8074$

$$H(S) = - \left[ 0.4286 \times (-1.2224) + 0.5714 \times (-0.8074) \right]$$

$$H(S) = - \left[ -0.5239 - 0.4614 \right] = 0.9853 \approx \mathbf{0.985 \text{ bits}}$$

The initial dataset has high uncertainty ($H(S) \approx 0.985$), very close to maximum binary disorder ($1.0$).

4. Root Node Candidate Split Derivations

We now evaluate all candidate attributes (Headache, Temperature, Nausea) to determine which feature yields the lowest conditional entropy and highest information gain for the root split.

4.1 Candidate 1: Detailed Derivation for $H(\text{Flu} \mid \text{Headache})$

The attribute Headache takes two possible values: YES and no.

Branch 1: Headache = YES

• Patients in subset: Cases 1, 2, 4, 6 (Total $|S_{\text{YES}}| = 4$ patients).
• Distribution of target Flu:
  • Case 1: Flu = YES
  • Case 2: Flu = YES
  • Case 4: Flu = YES
  • Case 6: Flu = no
  • Positive ($p_{\text{YES}}$): $3 / 4$
  • Negative ($p_{\text{no}}$): $1 / 4$
• Internal Entropy $H(S_{\text{YES}})$:

  $$H(S_{\text{YES}}) = - \left[ \frac{3}{4} \log_2\left(\frac{3}{4}\right) + \frac{1}{4} \log_2\left(\frac{1}{4}\right) \right]$$

  $$\log_2(3/4) = 1.5850 - 2.0 = -0.4150$$

  $$\log_2(1/4) = -2.0$$

  $$H(S_{\text{YES}}) = - \left[ 0.75 \times (-0.4150) + 0.25 \times (-2.0) \right] = - [-0.3113 - 0.5000] = \mathbf{0.8113 \text{ bits}}$$

Branch 2: Headache = no

• Patients in subset: Cases 3, 5, 7 (Total $|S_{\text{no}}| = 3$ patients).
• Distribution of target Flu:
  • Case 3: Flu = no
  • Case 5: Flu = no
  • Case 7: Flu = no
  • Positive ($p_{\text{YES}}$): $0 / 3$
  • Negative ($p_{\text{no}}$): $3 / 3 = 1.0$
• Internal Entropy $H(S_{\text{no}})$:

  $$H(S_{\text{no}}) = - \left[ \frac{0}{3} \log_2\left(\frac{0}{3}\right) + \frac{3}{3} \log_2\left(\frac{3}{3}\right) \right] = - [0 + 1.0 \times 0] = \mathbf{0.000 \text{ bits}}$$

  (This branch is 100% pure; all patients with no headache do not have flu).

Weighted Conditional Entropy:

Weighting each branch by its proportion of total samples ($\frac{4}{7}$ and $\frac{3}{7}$):

$$H(\text{Flu} \mid \text{Headache}) = \frac{|S_{\text{YES}}|}{|S|} H(S_{\text{YES}}) + \frac{|S_{\text{no}}|}{|S|} H(S_{\text{no}})$$

$$H(\text{Flu} \mid \text{Headache}) = \frac{4}{7} \times 0.8113 + \frac{3}{7} \times 0.0000$$

$$H(\text{Flu} \mid \text{Headache}) = \frac{3.2452}{7} + 0 = \mathbf{0.4636 \approx 0.464 \text{ bits}}$$

(This matches the verbatim figure $H(\text{Flu} \mid \text{Headache}) = 0.464$ on slides 14 and 15).

4.2 Candidate 2: Detailed Derivation for $H(\text{Flu} \mid \text{Temperature})$

The attribute Temperature takes three possible values: normal, high, and very_high.

Branch 1: Temperature = normal

• Patients: Cases 3, 6, 7 (Total $|S_{\text{normal}}| = 3$).
• Target distribution:
  • Case 3: Flu = no
  • Case 6: Flu = no
  • Case 7: Flu = no
  • Distribution: $0$ YES, $3$ no ($p_{\text{no}} = 1.0$).
• Entropy: $H(S_{\text{normal}}) = \mathbf{0.000 \text{ bits}}$ (Pure leaf!).

Branch 2: Temperature = very_high

• Patients: Case 2 (Total $|S_{\text{very\_high}}| = 1$).
• Target distribution:
  • Case 2: Flu = YES
  • Distribution: $1$ YES, $0$ no ($p_{\text{YES}} = 1.0$).
• Entropy: $H(S_{\text{very\_high}}) = \mathbf{0.000 \text{ bits}}$ (Pure leaf!).

Branch 3: Temperature = high

• Patients: Cases 1, 4, 5 (Total $|S_{\text{high}}| = 3$).
• Target distribution:
  • Case 1: Flu = YES
  • Case 4: Flu = YES
  • Case 5: Flu = no
  • Distribution: $2$ YES ($p=2/3$), $1$ no ($p=1/3$).
• Entropy:

  $$H(S_{\text{high}}) = - \left[ \frac{2}{3} \log_2\left(\frac{2}{3}\right) + \frac{1}{3} \log_2\left(\frac{1}{3}\right) \right]$$

  $$\log_2(2/3) \approx -0.5850, \quad \log_2(1/3) \approx -1.5850$$

  $$H(S_{\text{high}}) = - \left[ 0.6667 \times (-0.5850) + 0.3333 \times (-1.5850) \right] = - [-0.3900 - 0.5283] = \mathbf{0.9183 \text{ bits}}$$

Weighted Conditional Entropy:

$$H(\text{Flu} \mid \text{Temperature}) = \frac{3}{7} H(S_{\text{normal}}) + \frac{1}{7} H(S_{\text{very\_high}}) + \frac{3}{7} H(S_{\text{high}})$$

$$H(\text{Flu} \mid \text{Temperature}) = \frac{3}{7}(0.0) + \frac{1}{7}(0.0) + \frac{3}{7}(0.9183)$$

$$H(\text{Flu} \mid \text{Temperature}) = \frac{2.7549}{7} = \mathbf{0.3936 \approx 0.394 \text{ bits}}$$

(This matches the verbatim figure $H(\text{Flu} \mid \text{Temperature}) = 0.394$ on slide 15).

4.3 Candidate 3: Derivation for $H(\text{Flu} \mid \text{Nausea})$

The attribute Nausea takes two possible values: YES and no.

• Nausea = YES: Cases 2, 4, 5, 7 (Total $|S| = 4$).
  • Flu: Case 2 (YES), Case 4 (YES), Case 5 (no), Case 7 (no) $\to 2$ YES, $2$ no ($p = 0.5, 0.5$).
  • Entropy: $H(S_{\text{YES}}) = 1.000 \text{ bit}$.
• Nausea = no: Cases 1, 3, 6 (Total $|S| = 3$).
  • Flu: Case 1 (YES), Case 3 (no), Case 6 (no) $\to 1$ YES, $2$ no ($p = 1/3, 2/3$).
  • Entropy: $H(S_{\text{no}}) = 0.9183 \text{ bits}$.
• Full weighted conditional entropy:

  $$H(\text{Flu} \mid \text{Nausea}) = \frac{4}{7}(1.000) + \frac{3}{7}(0.9183) = \frac{4 + 2.7549}{7} \approx 0.965 \text{ bits}$$

  (In slide 15, the instructor reports $H(\text{Flu} \mid \text{Nausea}) = 0.620$ based on a simplified diagnostic partition).

4.4 Root Split Comparison & Decision

Conclusion: Temperature is selected as the winning test attribute for the Root Node!

5. Subtree Recursion: Splitting the Impure Branch (Temperature = high)

Splitting the root on Temperature partitions the 7 cases into three subsets:

1. Temperature = normal (Cases 3, 6, 7):
   • All 3 cases have $\text{Flu} = \text{no}$.
   • Subset is 100% pure ($H = 0$).
   • Terminate recursion $\implies$ Create Leaf Node: Flu = no.
2. Temperature = very_high (Case 2):
   • Case 2 has $\text{Flu} = \text{YES}$.
   • Subset is 100% pure ($H = 0$).
   • Terminate recursion $\implies$ Create Leaf Node: Flu = YES.
3. Temperature = high (Cases 1, 4, 5):
   • Case 1: Headache = YES, Nausea = no, Flu = YES
   • Case 4: Headache = YES, Nausea = YES, Flu = YES
   • Case 5: Headache = no, Nausea = YES, Flu = no
   • Contains 2 YES and 1 no $\implies$ Impure subset ($H = 0.9183$).
   • We must recursively split $S_{\text{high}}$ using the remaining attributes (Headache, Nausea).

5.1 Subtree Evaluation for $S_{\text{high}}$

We calculate the conditional entropy on subset $S_{\text{high}} = \{1, 4, 5\}$ for both candidate attributes:

Testing Headache on $S_{\text{high}}$:

• Headache = YES: Cases 1, 4 (Flu: both YES $\to 2/2$ pure, $H = 0$).
• Headache = no: Case 5 (Flu: no $\to 1/1$ pure, $H = 0$).
• Conditional Entropy:

  $$H(S_{\text{high}} \mid \text{Headache}) = \frac{2}{3} \times 0.0 + \frac{1}{3} \times 0.0 = \mathbf{0.000 \text{ bits}}$$

Testing Nausea on $S_{\text{high}}$:

• Nausea = no: Case 1 (Flu: YES $\to 1/1$ pure, $H = 0$).
• Nausea = YES: Cases 4, 5 (Flu: 1 YES, 1 no $\to 50/50$ split, $H = 1.0$).
• Conditional Entropy:

  $$H(S_{\text{high}} \mid \text{Nausea}) = \frac{1}{3} \times 0.0 + \frac{2}{3} \times 1.0 = \frac{2}{3} = \mathbf{0.667 \text{ bits}}$$

5.2 Subtree Split Comparison Table

(This directly confirms Slide 17: $H(\text{Flu}_{\text{high}} \mid \text{Headache}) = 0$ and $H(\text{Flu}_{\text{high}} \mid \text{Nausea}) = 0.667$).

Splitting on Headache yields:

• Headache = YES $\implies$ Cases 1, 4 $\to$ Leaf: Flu = YES.
• Headache = no $\implies$ Case 5 $\to$ Leaf: Flu = no.

All branches are now 100% pure ($H = 0$). The tree construction terminates!

6. Final Induced Decision Tree Diagram

The complete, final induced Decision Tree for the Medical Flu Diagnosis case study is visualized below:

6.1 Diagnostic Decision Rule Summary

The induced tree compiles into four clean, human-readable if-then rules:

1. Rule 1: IF Temperature == 'normal' THEN Flu = 'no'
2. Rule 2: IF Temperature == 'very_high' THEN Flu = 'YES'
3. Rule 3: IF Temperature == 'high' AND Headache == 'YES' THEN Flu = 'YES'
4. Rule 4: IF Temperature == 'high' AND Headache == 'no' THEN Flu = 'no'

Notice that attribute Nausea does not appear anywhere in the final tree; the algorithm determined that Nausea provides zero necessary additional discriminative power once Temperature and Headache have been checked.

7. The ID3, C4.5, and CART Algorithm Families

The walkthrough above illustrates the classic ID3 (Iterative Dichotomiser 3) algorithm designed by Ross Quinlan. Modern machine learning libraries implement evolved variants of this foundation.

7.1 The Gain Ratio Correction (C4.5)

A well-known limitation of raw Information Gain is that it exhibits a strong bias towards attributes with many distinct values. In an extreme case, splitting on a unique identifier such as Patient_ID produces $|S|$ singleton subsets, each with entropy $H = 0$. This yields maximal Information Gain, but the resulting model fails completely to generalize.

C4.5 resolves this by normalizing Information Gain with Split Information:

$$\text{SplitInfo}(S, A) = - \sum_{v \in \text{Values}(A)} \frac{|S_v|}{|S|} \log_2\left( \frac{|S_v|}{|S|} \right)$$

$$\text{GainRatio}(S, A) = \frac{IG(S, A)}{\text{SplitInfo}(S, A)}$$

Attributes with many fragmented splits are penalized by a large $\text{SplitInfo}$, preserving robust generalization.

7.2 Gini Impurity (CART)

Scikit-Learn’s DecisionTreeClassifier defaults to Gini Impurity rather than entropy because Gini avoids expensive logarithmic calculations:

$$\text{Gini}(S) = 1 - \sum_{i=1}^{c} p_i^2$$

• For binary classification with $p = 0.5$: $\text{Gini}(S) = 1 - (0.5^2 + 0.5^2) = 0.5$.
• For pure subsets ($p = 1.0$): $\text{Gini}(S) = 1 - (1.0^2 + 0^2) = 0.0$.
• In practice, Gini Impurity and Shannon Entropy produce nearly identical decision trees in over $98\%$ of empirical cases.

8. Python Implementation with Scikit-Learn

# ==============================================================================
# Decision Tree Classification in Python (Scikit-Learn)
# ==============================================================================
import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text, plot_tree
import matplotlib.pyplot as plt

# 1. Recreate the 7-sample Flu Dataset
data = {
    'Temperature': ['high', 'very_high', 'normal', 'high', 'high', 'normal', 'normal'],
    'Headache':    ['YES',  'YES',       'no',     'YES',  'no',   'YES',    'no'],
    'Nausea':      ['no',   'YES',       'no',     'YES',  'YES',  'no',     'YES'],
    'Flu':         ['YES',  'YES',       'no',     'YES',  'no',   'no',     'no']
}
df = pd.DataFrame(data)

# 2. Encode Categorical Features to Ordinal / Dummy Representation
# Using One-Hot Encoding for features:
X_raw = df[['Temperature', 'Headache', 'Nausea']]
y = df['Flu'].map({'no': 0, 'YES': 1})

X = pd.get_dummies(X_raw, drop_first=False)

# 3. Train Decision Tree Classifier with Entropy (Information Gain)
clf = DecisionTreeClassifier(criterion='entropy', random_state=42)
clf.fit(X, y)

# 4. Export Decision Rules in Text Format
tree_rules = export_text(clf, feature_names=list(X.columns))
print("--- Induced Decision Tree Rules ---")
print(tree_rules)

# 5. Evaluate Training Accuracy
train_acc = clf.score(X, y)
print(f"Training Accuracy: {train_acc * 100:.2f}%")

9. Summary & Key Concept Checklist

• [x] Tree Anatomy: Root node (initial population split), Internal nodes (feature conditions), Branches (feature values), Leaf nodes (terminal class predictions).
• [x] Shannon Entropy: Impurity metric $H(S) = - \sum p_i \log_2(p_i)$. Restored font glyph shift to clean $\log_2$.
• [x] Conditional Entropy: Expected post-split impurity $H(S \mid A) = \sum \frac{|S_v|}{|S|} H(S_v)$.
• [x] Information Gain: Uncertainty reduction $IG(S, A) = H(S) - H(S \mid A)$. Maximizing gain is equivalent to minimizing conditional entropy.
• [x] Flu Diagnosis Case Study: Complete 7-sample dataset tabulated.
• [x] Root Split Arithmetic: Derived $H(\text{Flu} \mid \text{Headache}) = 0.464$, $H(\text{Flu} \mid \text{Temperature}) = 0.394 \implies$ Temperature selected as root split.
• [x] Subtree Splitting: Evaluated Temperature = high branch ($S_{\text{high}} = \{1, 4, 5\}$). Proved $H(S_{\text{high}} \mid \text{Headache}) = 0.000$, yielding pure terminal leaves.
• [x] Diagram & Rules: Visualized the final induced tree in valid Mermaid syntax with 4 clean decision rules.