Decision Tree Induction

A decision tree is a supervised learning method used in data mining for both classification and regression. It is a tree-shaped model that reaches a decision by asking a sequence of questions about the data.

Decision tree induction is the process of building that tree automatically from training data — deciding which question to ask first, which to ask next, and when to stop.

Structure of a Decision Tree

A decision tree splits a dataset into progressively smaller groups, producing a structure of decision nodes and leaf nodes:

• Root node — the top node, representing the single best predictor to split on first
• Decision node — a node where data is split into two or more branches based on a condition
• Leaf node — a terminal node holding the final decision or class label, with no further splitting

                [ Outlook ]           ← root node
                /    |    \
          Sunny/  Overcast \Rainy
              /      |      \
      [Humidity]  ( Yes )  [ Windy ]  ← decision nodes / leaf
         /   \              /    \
     High/    \Normal   True/     \False
       /       \          /        \
    ( No )   ( Yes )   ( No )    ( Yes )   ← leaf nodes

Decision trees handle both categorical data (Yes/No) and numerical data (age, income). The attributes used for splitting can be nominal (colour, gender), ordinal (small, medium, large), binary (Yes/No), or numerical (salary, age) — though the final output class is usually categorical.

Each split creates a segment called a node, and as splitting continues the data within each node becomes more homogeneous. This repeated splitting is called recursive partitioning.

Key Concepts

Entropy

Entropy measures the impurity or randomness in a dataset:

• High entropy → the data is mixed and uncertain
• Low entropy → the data is pure, mostly one class

For a dataset with classes appearing in proportions p₁, p₂, … the formula is:

  Entropy = − Σ pᵢ × log₂(pᵢ)

Two reference points make the scale intuitive for a two-class problem:

• A node split evenly 50/50 has entropy 1.0 — maximum uncertainty
• A node where every record is the same class has entropy 0 — no uncertainty at all

The goal of every split is to move from the first situation toward the second.

Information Gain

Information gain measures the reduction in entropy achieved by splitting on a particular attribute:

  Information Gain = Entropy(parent) − Weighted average Entropy(children)

The attribute with the highest information gain is chosen for the next split. The weighting matters: a subset containing 4 of 14 records contributes only 4/14 of its entropy to the total, so a split producing one small pure group and one large messy group scores worse than the pure group alone suggests.

A Worked Calculation

Take a dataset of 14 records: 9 Yes and 5 No.

The starting entropy is:

  Entropy = −(9/14)log₂(9/14) − (5/14)log₂(5/14) = 0.9403

Close to 1, so the data is nearly as mixed as it can be. Now consider splitting on Outlook, which produces three subsets:

The Overcast branch is pure — every record is Yes — so its entropy is zero and it becomes a leaf immediately. The weighted entropy after the split is:

  (5/14 × 0.9710) + (4/14 × 0.0000) + (5/14 × 0.9710) = 0.6935

  Information Gain = 0.9403 − 0.6935 = 0.2467

The same calculation is performed for every other available attribute, and whichever yields the largest gain becomes the split. Then the process repeats inside each branch that isn't already pure.

Gini Index

Information gain is not the only option. The Gini index measures impurity differently:

  Gini = 1 − Σ pᵢ²

For the same 9/5 split, Gini = 0.4592. It usually selects similar splits to entropy but is cheaper to compute, since it avoids logarithms. CART uses Gini by default; ID3 and C4.5 use information gain.

How the Algorithm Works

Decision tree induction takes three inputs:

1. Dataset (D) — the training data, initially containing all records with their class labels.

2. Attribute list — the features available for splitting.

3. Attribute selection method — the measure used to pick the best split, such as information gain or the Gini index.

The procedure is then straightforward:

1. Start with the complete dataset at the root.
2. Calculate the impurity of the current node.
3. Evaluate every available attribute and choose the one with the best score.
4. Split the data on that attribute, creating a branch per value.
5. Repeat recursively within each branch.
6. Stop when a node is pure, no attributes remain, or a stopping rule is met.

Common algorithms include ID3 (information gain, categorical attributes only), C4.5 (its successor, handling numeric attributes and missing values), and CART (Classification and Regression Trees, using Gini and producing binary splits).

A Different Kind of "Decision Tree"

The term is used in a second, unrelated sense that is worth separating out, because tutorials mix the two and the distinction matters.

In decision analysis, a decision tree is a hand-drawn diagram for evaluating one choice under uncertainty, with branches for options and probabilities. Nothing is induced from data — the analyst supplies the numbers.

Consider a factory deciding whether to expand:

Option 1: Expand (cost $3 million)

• Good economy, probability 0.6 → profit $8 million
• Bad economy, probability 0.4 → profit $6 million

  Expected value = (0.6 × 8) + (0.4 × 6) − 3 = 7.2 − 3 = $4.2 million

Option 2: Do not expand (cost $0)

• Good economy → $4 million
• Bad economy → $2 million

  Expected value = (0.6 × 4) + (0.4 × 2) − 0 = $3.2 million

Since $4.2M > $3.2M, the factory should expand.

This is a useful technique, but it is not decision tree induction. Here a person supplies the probabilities and payoffs to evaluate a single decision; in induction, an algorithm derives the tree from thousands of historical records in order to classify new ones. Both are called decision trees; only the second is a data mining method.

Advantages of Decision Trees

• No data scaling or normalization required — splits depend on ordering, not magnitude, so income in rupees and age in years coexist without preprocessing
• Handle both categorical and numerical attributes
• Require relatively little data preprocessing
• Easy to understand, visualize, and explain — a tree can be read as a series of plain if-then rules, which matters wherever a decision must be justified
• Missing values can be handled by several algorithms, though the mechanism is implementation-specific rather than automatic

Disadvantages of Decision Trees

The limitations deserve equal weight, because they motivate much of what follows in this series.

• Overfitting. A tree grown until every leaf is pure will memorize the training data, including its noise, and generalize poorly. This is the single biggest weakness.
• Instability. Small changes in the training data can produce a very different tree, since one changed split near the root cascades through everything below.
• Bias toward attributes with many values. Information gain favours attributes with many distinct values — an ID column would split the data perfectly and be useless. C4.5's gain ratio corrects for this.
• Difficulty with diagonal boundaries. Splits are axis-parallel, so a relationship like "income > 2 × age" has to be approximated in many steps.

Pruning

The standard remedy for overfitting is pruning — cutting back branches that fit noise rather than signal. Pre-pruning stops growth early using rules such as a maximum depth or a minimum number of records per node; post-pruning grows the full tree and then removes branches that fail to improve accuracy on validation data.

Ensemble methods take this further by combining many trees rather than perfecting one, which is the subject of this series' lesson on bagging vs boosting.

Related Concepts

Classification as a technique is covered in the data mining techniques lesson. Random Forest and Gradient Boosting, which build on the weaknesses described above, are covered in the bagging vs boosting lesson. Decision trees also appear as one of the algorithm choices in the KDD process lesson, where their interpretability is contrasted with the higher accuracy of neural networks.