Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 39 ยท Classification

Decision Trees in Data Mining

Understand how decision tree induction works: entropy, information gain, Gini impurity, gain ratio, stopping rules, pruning and reading the rules a tree learns, with runnable code.

A decision tree classifies a record by asking a sequence of simple questions. Each internal node tests one attribute ("is income above 50k?"), each branch is an answer, and each leaf holds a class. Trees are popular in data mining because you can read them: every path from root to leaf is an if-then rule you can explain to a manager.

The learning algorithm is greedy and recursive: pick the attribute that best separates the classes, split the records, and repeat on each part until the parts are pure or a stopping rule fires. The whole craft is in the phrase "best separates", which needs a measure of impurity.

Measuring impurity

A group of records is pure if they all share one class. Two common impurity measures:

  • Entropy: H = - sum(p_i * log2(p_i)) over the class proportions p_i. A 50/50 split has entropy 1 bit; a pure group has 0.
  • Gini impurity: G = 1 - sum(p_i^2). A 50/50 split has 0.5; a pure group has 0.

The information gain of a split is the parent's entropy minus the weighted average entropy of the children. The attribute with the highest gain wins the node (the ID3 algorithm). C4.5 divides the gain by the split's own entropy (gain ratio) so attributes with many distinct values are not unfairly favored. CART uses Gini and always makes binary splits.

Python Entropy and information gain by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The "overcast" group is pure (entropy 0), so splitting on outlook removes a good part of the uncertainty.

Building a tree from scratch

Here is the full recursive algorithm in about twenty lines, using Gini and numeric thresholds. It shows exactly what libraries do for you.

Python A tiny tree builder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The tree is stored as nested tuples (feature, threshold, left, right); a plain number is a leaf. One split on income separates this toy data perfectly.

Stopping and pruning

Left alone, a tree keeps splitting until every leaf is pure, which memorizes noise (see overfitting). There are two defenses:

  • Pre-pruning (early stopping): limit max_depth, require a minimum number of records per leaf (min_samples_leaf) or a minimum gain.
  • Post-pruning: grow the full tree, then cut back branches that do not help on validation data. scikit-learn implements cost-complexity pruning through ccp_alpha: a larger alpha removes more branches.
Python Pruning with ccp_alpha

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A moderate alpha shrinks the tree a lot while the test accuracy stays about the same or improves; too much alpha underfits.

Reading the rules

Python Print a tree as rules

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each indented path is a rule, such as "if petal width <= 0.80 then class 0 (setosa)". The feature_importances_ values tell you which attributes did most of the splitting work.

Strengths and weaknesses

Strength Weakness
Easy to explain, rules are readable Unstable: small data changes can give a different tree
No feature scaling needed Greedy: the best split now may not give the best tree
Handles numbers and categories Tends to overfit without pruning
Fast to train and predict Axis-aligned splits approximate diagonal boundaries badly

The instability problem is exactly what ensembles fix by averaging many trees. For a deeper tour of tree options see scikit-learn decision trees.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the entropy of a node where all records belong to one class?

    A pure node has no uncertainty, so entropy (and Gini impurity) is 0.
  2. 2. Which attribute does ID3 choose for a split?

    ID3 picks the attribute whose split reduces entropy the most. C4.5 refines this with the gain ratio.
  3. 3. Why does C4.5 use gain ratio instead of plain information gain?

    An ID-like column splits the data into tiny pure groups and gets a huge gain although it is useless for new data.
  4. 4. Which is an example of post-pruning?

    Post-pruning grows the full tree first, then removes branches that do not improve validation performance.

Summary

  • A decision tree is a set of nested if-then tests learned greedily by choosing the split with the best impurity reduction.
  • Entropy and Gini measure impurity; information gain, gain ratio and Gini decrease score splits (ID3, C4.5, CART).
  • Control overfitting with depth and leaf-size limits or with cost-complexity pruning.
  • Trees are readable and need no scaling, but they are unstable, which ensembles address.

Next: Nearest Neighbors and Naive Bayes