Building a Decision Tree — Height/Gender Data

Step 1: Discretize Height into the given ranges

Class distribution: Short = 4, Medium = 8, Tall = 3 (15 tuples).

Step 2: Root entropy

$$H(D) = -\frac{4}{15}\log_2\frac{4}{15} -\frac{8}{15}\log_2\frac{8}{15} -\frac{3}{15}\log_2\frac{3}{15} \approx 1.46$$

Step 3: Choose the best attribute by Information Gain

Splitting on Height ranges (each row of the discretization table):

Weighted entropy $= \frac{2}{15}(1) = 0.13$; therefore

$$\text{Gain(Height)} = 1.46 - 0.13 = 1.33$$

Splitting on Gender:

• Female (9): Short 3, Medium 6 → $H(F) = 0.92$, contributes $\frac{9}{15}\cdot0.92 = 0.55$
• Male (6): Short 1, Medium 2, Tall 3 → $H(M) = 1.46$, contributes $\frac{6}{15}\cdot1.46 = 0.58$

$$\text{Gain(Gender)} = 1.46 - (0.55+0.58) = 0.33$$

Since Gain(Height) = 1.33 > Gain(Gender) = 0.33, split on Height at the root.

Step 4: Resulting Decision Tree

                      Height range?
        ┌──────────────┬────────────┬───────────┬────────--┬──────────┬──────────┐
      (0,1.6]      (1.6,1.7]   (1.7,1.8]  (1.8,1.9]   (1.9,2.0]    (2.0,5.0]
         │             │            │          │           │             │
      Short         Short       Medium     Medium        │           Tall
                                                         │
                                             Height ≥ 2.0 ?
                                            /             \
                                      Tall            Medium
                                     (2.0)            (1.95)

Explanation

• Every range except (1.9,2.0] is already pure (all classes identical), so it becomes a leaf directly.
• The range (1.9,2.0] contains two male students: height 2.0 → Tall, height 1.95 → Medium — Gender cannot separate them (both M), so the only distinguishing feature left is a finer height threshold (≥ 2.0 → Tall, else Medium).
• The final tree separates students into the three classes Short / Medium / Tall using their height, giving perfect classification on this training set.