Classification by Decision Tree Induction

A decision tree is a flowchart-like structure: each internal node tests an attribute, each branch is an outcome, each leaf holds a class label. Trees are the most popular classification model because they need no domain knowledge, handle high-dimensional data and are easy to read as IF-THEN rules.

1. The Classic Example (buys_computer, 14 tuples)

#	age	income	student	credit	buys
1	youth	high	no	fair	no
2	youth	high	no	excellent	no
3	middle	high	no	fair	yes
4	senior	medium	no	fair	yes
5	senior	low	yes	fair	yes
6	senior	low	yes	excellent	no
7	middle	low	yes	excellent	yes
8	youth	medium	no	fair	no
9	youth	low	yes	fair	yes
10	senior	medium	yes	fair	yes
11	youth	medium	yes	excellent	yes
12	middle	medium	no	excellent	yes
13	middle	high	yes	fair	yes
14	senior	medium	no	excellent	no

Class counts: yes = 9, no = 5 → $H(D) = -\frac{9}{14}\log_2\frac{9}{14}-\frac{5}{14}\log_2\frac{5}{14} = 0.940$ bits.

Resulting tree (ID3/C4.5 style):

                 age?
        ┌─────────┼──────────┐
      youth    middle      senior
        │         │           │
    student?     yes       credit?
    ┌───┴───┐      (Y)     ┌───┴────┐
   no      yes           fair   excellent
   (no)    (yes)         (yes)     (no)

2. Attribute Selection — Three Measures

(a) Information gain (ID3 / C4.5)

H(D)=-\sum_{i=1}^{m}p_i\log_2 p_i

\text{Gain}(D,A)=H(D)-\underbrace{\sum_{v}\frac{|D_v|}{|D|}H(D_v)}_{\text{conditional entropy}}

Gain for age:

youth (5): 2 yes, 3 no → $H = 0.971$
middle (4): 4 yes, 0 no → $H = 0$
senior (5): 3 yes, 2 no → $H = 0.971$

\text{Gain}(age)=0.940-\left(\tfrac{5}{14}(0.971)+\tfrac{4}{14}(0)+\tfrac{5}{14}(0.971)\right)=0.940-0.694=0.246

Attribute	Gain
age	0.246 ← best, chosen as root
income	0.029
student	0.151
credit_rating	0.048

(b) Gain ratio (C4.5) — corrects the bias of gain towards attributes with many values:

\text{SplitInfo}(D,A)=-\sum_{v}\frac{|D_v|}{|D|}\log_2\frac{|D_v|}{|D|},\qquad \text{GainRatio}=\frac{\text{Gain}(D,A)}{\text{SplitInfo}(D,A)}

For age: SplitInfo $= -\frac{5}{14}\log_2\frac{5}{14}-\frac{4}{14}\log_2\frac{4}{14}-\frac{5}{14}\log_2\frac{5}{14} = 1.577$ → GainRatio $= 0.246/1.577 = 0.156$ .

(c) Gini index (CART) — measure of impurity; a split is good if it reduces the weighted Gini:

\text{Gini}(D)=1-\sum_{i=1}^{m}p_i^{2},\qquad \text{Gini}_A(D)=\sum_v\frac{|D_v|}{|D|}\text{Gini}(D_v)

\text{Gini}(D)=1-\left(\tfrac{9}{14}\right)^2-\left(\tfrac{5}{14}\right)^2=0.459

For two-way splits CART uses the reduction in Gini; age split into youth vs non-youth gives Gini $= \frac{5}{14}(0.48)+\frac{9}{14}(0.444)=0.457$ → reduction 0.002. CART prefers binary splits and tends to produce smaller trees.

3. Basic Algorithm (recursive partition / Hunt's algorithm)

Generate_decision_tree(D, attribute_list):
  create node N
  if all tuples in D belong to the same class C:   return N labelled C
  if attribute_list is empty:                      return N labelled majority class
  select the attribute A in attribute_list with the highest gain / gain ratio /
                                                     lowest Gini
  label N with A
  for each value v of A:  Dv = {tuples in D with A = v}
       if Dv is empty: attach a leaf labelled with the majority class of D
       else: attach Generate_decision_tree(Dv, attribute_list - {A})
  return N

4. Avoiding Overfitting — Two Pruning Strategies

Strategy	When	Method
Pre-pruning (early stopping)	Stop growing before the tree is perfect	Thresholds: minimum gain, minimum number of tuples per node, maximum depth, χ² test of independence
Post-pruning	Grow the full tree then cut back	Subtree replacement (replace a subtree by a leaf = majority class), subtree raising; use a validation set

Cost-complexity pruning (CART): minimise

\text{Cost}(T)=\text{Err}(T)+\alpha\,|T|

where $|T|$ = number of leaves and $\alpha$ is the complexity parameter: larger $\alpha$ → smaller tree.

Pessimistic pruning (C4.5): estimated error of a node = errors + 0.5 per leaf, adjusted by the binomial confidence bound — no validation set needed.

5. Advantages and Limitations

Advantages

Inexpensive to construct and extremely fast at classifying unknown tuples (a path of tests).
Interpretable — trees convert directly into readable IF-THEN rules; paths are easily explained to users.
Handles numeric and categorical attributes; no assumptions about the underlying distribution; robust to noisy/missing values (C4.5 routes missing values using a probability distribution).
Does not need attribute normalisation or a fixed number of attributes; can handle multidimensional, high-dimensional data.

Limitations

Greedy, top-down recursive partition search → local optima; trouble with XOR-like/parity and other non-axis-parallel concepts (needs many duplications of subtrees).
Sensitive to noise/outliers and to the training sample — small changes can cause big tree changes (instability); hence ensembles (bagging, random forests, boosting).
Overfitting unless pruned; unnecessary complexity — very large trees that are hard to read.
Each split favours attributes with many values (fixed by gain ratio/Gini), and the algorithm cannot express simple relationships for some domains (e.g. diagonal boundaries).
Probability estimates from leaves are crude (needs Laplace/smoothing); class imbalance can create biased trees.

6. Scalability — SLIQ / SPRINT

For huge databases, trees need sorting/indexing once, not once per node. RainForest uses an AVC-set (Attribute-Value-Class counts) per node to prune useless splits. Gini + binary splits keep it I/O efficient.

7. Exam Points

Draw the decision tree for the buys_computer data and show information gain computations for each attribute — 10 marks (extremely frequent numerical).
Explain the tree-induction algorithm with pseudo-code — 7 marks.
Compare information gain, gain ratio and Gini index — 5 marks.
Explain pre-pruning vs post-pruning with examples — 5 marks.
State the advantages and limitations of decision tree induction — 5 marks.

Classification by Decision Tree Induction