Q4(a) - Building a Decision Tree (ID3, Information Gain)

Method. At every node we test the attribute that yields the largest information gain, i.e. the largest reduction of entropy (class impurity):

$$H(S)=-\sum_{i}p_i\log_2 p_i, \qquad Gain(S,A)=H(S)-\sum_{v\in Values(A)}\frac{|S_v|}{|S|}H(S_v)$$

Height binning. A value lying exactly on a boundary is taken into the higher range, so the given ranges are read as $[0,1.6),[1.6,1.7),[1.7,1.8),[1.8,1.9),[1.9,2.0),[2.0,5.0]$. (With the opposite convention every range comes out pure and the tree is even shallower; the choice of the root attribute does not change.)

Step 1 - Count tables (15 records)

Class counts inside each height range:

Class counts by gender:

Step 2 - Entropy of the whole data set

$$H(S)=-\frac{4}{15}\log_2\frac{4}{15}-\frac{8}{15}\log_2\frac{8}{15}-\frac{3}{15}\log_2\frac{3}{15}=0.5085+0.4837+0.4644=\mathbf{1.4566\ \text{bits}}$$

Step 3 - Candidate splits

(a) Height - multi-way split over the given ranges

Only the range $[1.7,1.8)$ is impure (2 Short + 1 Medium):

$$H([1.7,1.8))=-\frac{2}{3}\log_2\frac{2}{3}-\frac{1}{3}\log_2\frac{1}{3}=0.3900+0.5283=0.9183$$

All other non-empty ranges are pure, so their entropy is 0. Therefore

$$Gain(\text{Height})=1.4566-\frac{3}{15}(0.9183)=1.4566-0.1837=\mathbf{1.2729}$$

(b) Gender - two-way split

$$H(F)=-\frac{3}{9}\log_2\frac{3}{9}-\frac{6}{9}\log_2\frac{6}{9}=0.5283+0.3900=0.9183$$

$$H(M)=-\frac{1}{6}\log_2\frac{1}{6}-\frac{2}{6}\log_2\frac{2}{6}-\frac{3}{6}\log_2\frac{3}{6}=0.4308+0.5283+0.5000=1.4591$$

$$Gain(\text{Gender})=1.4566-\left(\frac{9}{15}\times0.9183+\frac{6}{15}\times1.4591\right)=1.4566-1.1346=\mathbf{0.3219}$$

(c) Binary threshold splits on height (cross-check)

Root = Height, because 1.2729 is by far the largest gain (Gender gives only 0.3219).

Step 4 - Grow each branch

• $[0,1.6)$ - no records, ignored.
• $[1.6,1.7)$ - 2 Short, already pure, so leaf = Short.
• $[1.7,1.8)$ - 2 Short + 1 Medium, so split with the remaining attribute Gender:
  • F gives 1 Short (1.70 m) and 1 Medium (1.75 m): a 1-1 tie, entropy 1.0.
  • M gives one record (1.70 m, Short): pure, leaf = Short.
  • Split gain $=0.9183-\big(\frac{2}{3}\times1+\frac{1}{3}\times0\big)=0.2516>0$, so the split is justified.
• $[1.8,1.9)$ - 4 Medium, pure, leaf = Medium.
• $[1.9,2.0)$ - 3 Medium, pure, leaf = Medium.
• $[2.0,5.0]$ - 3 Tall, pure, leaf = Tall.

Final decision tree

                          [ Height ]
    +-----------+-----------+-------------+------------+------------+------------+
 [0,1.6)    [1.6,1.7)   [1.7,1.8)     [1.8,1.9)   [1.9,2.0)   [2.0,5.0]
  empty        Short        Gender         Medium      Medium       Tall
                              |
                 +------------+------------+
                 F                        M
             Short *                    Short
         (1 Short, 1 Medium)

Resulting classification rules

1. Height $\in[2.0,5.0]$ gives Tall
2. Height $\in[1.8,2.0)$ gives Medium
3. Height $\in[1.6,1.7)$ gives Short
4. Height $\in[1.7,1.8)$ and Gender = M gives Short; Gender = F is a 1-1 tie broken by any fixed rule (e.g. Short)

The tree classifies 14 of the 15 training records correctly (93%); the only ambiguity is the female pair inside $[1.7,1.8)$, which no available attribute can separate.