Classification & Decision Tree Induction

1Classification vs prediction

Both build a model from data to describe data classes or predict future trends.

Key terms

2The two-step classification process

Step 1: learning (training phase). The algorithm analyses a training set of tuples with their class labels and builds a classifier. In the loan example the classifier is a set of classification rules:

IF age = youth THEN loan_decision = risky
IF income = high THEN loan_decision = safe
IF age = middle_aged AND income = low THEN loan_decision = risky

Step 2: classification. First estimate predictive accuracy on a test set.

If the accuracy is acceptable, the classifier labels future ("unknown", "previously unseen") tuples, e.g. approving or rejecting new loan applicants.

3Preparing data & comparing methods

Preprocessing for classification

Criteria to compare classifiers and predictors

4Decision trees & their history

A decision tree is a flowchart-like tree:

• Internal (non-leaf) node = a test on an attribute
• Branch = an outcome of the test
• Leaf (terminal) node = a class label
• The top node is the root

                    age?
          ┌──────────┼──────────────┐
        youth    middle_aged      senior
          │          │               │
      student?      yes        credit_rating?
       ┌──┴──┐                  ┌────┴─────┐
      no    yes               fair     excellent
      │      │                 │          │
      no    yes               yes         no

Concept "buys_computer". The final tree from the worked example.

History

ID3, C4.5 and CART all use a greedy (non-backtracking), top-down recursive divide-and-conquer approach. The training set is recursively partitioned into smaller subsets as the tree grows.

Basic algorithm (Figure 11-4) in plain words

1. Create node N.
2. If all tuples in D are in the same class → N becomes a leaf with that class.
3. If there are no attributes left → leaf labelled with the majority class.
4. Otherwise, use an attribute selection measure to find the best splitting criterion, label N with it, and remove the attribute if it was discrete with multiway splits.
5. For each outcome j, form partition Dⱼ. If Dⱼ is empty → attach a leaf with the majority class of D. Otherwise recurse on Dⱼ.

5Attribute selection measures

An attribute selection measure (or splitting rule) is a heuristic for choosing the split that best separates D into classes. Ideally every partition is pure (one class). The measure ranks the attributes, and the best one is the splitting attribute. For continuous attributes we also need a split point; for binary trees, a splitting subset.

Information gain (ID3)

Based on Claude Shannon's information theory. Choose the attribute with the highest gain: it minimises the information still needed (least impurity) and so the expected number of tests.

• p_i = |C_i,D| / |D| = probability that a tuple belongs to class C_i.
• |Dⱼ|/|D| is the weight of partition j.

Gain ratio (C4.5)

C4.5 normalises gain using split information: the potential information from splitting D into v partitions, regardless of class.

Pick the attribute with the maximum gain ratio.

Gini index (CART)

• Gini considers binary splits only. For a discrete attribute with v values there are 2ᵛ subsets. Excluding the full set and the empty set leaves 2ᵛ − 2 subsets. Each split appears twice ({low} vs {medium, high} is the same split), so there are (2ᵛ − 2)/2 distinct binary splits.
• For continuous attributes, try the midpoint between each pair of adjacent sorted values as the split point: D₁ = A ≤ split, D₂ = A > split.
• Choose the attribute and split with the minimum Gini_A(D), i.e. the maximum reduction in impurity.

6Worked example — buys_computer (14 tuples)

9 yes, 5 no.

Information gain

Step 1: entropy of D

Step 2: split on age

Step 3: the other attributes. Gain(income) = 0.029, Gain(student) = 0.151, Gain(credit_rating) = 0.048.

Step 4: choose the root. age has the highest gain, so it is the root. The middle_aged branch is all "yes", so it becomes a leaf. Recursing on youth (best is student) and senior (best is credit_rating) gives the final tree shown earlier.

Gain ratio for income

Income splits D into low (4), medium (6) and high (4):

Gini index

Worked line for income ∈ {low, medium}: D₁ has 10 tuples (7 yes, 3 no), D₂ has 4 (2 yes, 2 no).

So the root split is age ∈ {youth, senior}, with impurity reduction 0.459 − 0.357 = 0.102.

7Weka: J48, filters and visualisation

The Weka videos this week cover:

8Quick revision sheet