Decision Tree Classification

Decision Tree Classification: Core Concepts and Algorithms

Decision trees are one of the most intuitive and widely used methods for classification in Artificial Intelligence. This course breaks down the fundamental ideas behind decision‑tree induction, the algorithmic strategies used to build them, and the key measures that guide the splitting process. By the end of this module you will understand how a decision tree is structured, why certain attributes are chosen, and how information‑theoretic concepts such as entropy and information gain drive the learning process.

1. What Does Decision‑Tree Induction Build?

At its heart, decision‑tree induction creates a hierarchical tree that maps attribute tests to class predictions. The tree consists of three main components:

• Internal nodes: each node represents a test on a single attribute (e.g., "Age > 30?").
• Branches: each branch corresponds to a possible outcome of the attribute test (e.g., "Yes" or "No").
• Leaf nodes: the terminal nodes assign a class label to instances that reach them.

This structure contrasts with a flat list of rules or a single monolithic decision rule; the tree’s hierarchy enables efficient, interpretable classification.

2. Algorithmic Strategy: Recursive, Top‑Down Construction

The construction of a decision tree follows a classic divide‑and‑conquer approach:

• Start at the root with the full training set.
• Choose the best attribute to split the data (see Section 4).
• Recursively apply the same process to each resulting subset, creating sub‑trees.
• Stop when a stopping criterion is met (e.g., all instances belong to the same class).

This recursive, top‑down method ensures that each split focuses on the most informative attribute for the current subset of data.

3. Stopping Conditions: When All Instances Share the Same Class

A fundamental stopping rule is reached when all instances in the current subset belong to the same class C. At this point the subset is perfectly pure, and the algorithm creates a leaf node labeled with class C. Other common stopping criteria (not covered in the quiz) include reaching a maximum depth, having too few instances, or achieving a minimal impurity threshold.

4. Attribute Selection Measures: Guiding the Split

Choosing the right attribute at each node is crucial. Attribute selection measures quantify how well a split separates the data into homogeneous class distributions. The most popular measures are based on information theory:

• Information Gain: evaluates the reduction in entropy after splitting on an attribute.
• Gain Ratio: normalizes Information Gain by the intrinsic information of the split, mitigating bias toward attributes with many values.
• Other measures (e.g., Gini impurity) are used by alternative algorithms such as CART.

These measures ensure that each split maximizes class purity while keeping the tree compact.

5. Information Theory Foundations: Entropy

Information Gain relies on the concept of entropy from information theory. Entropy measures the amount of uncertainty or impurity in a dataset. For a dataset D containing classes C₁ … Cₖ, the entropy is defined as:

Entropy(D) = − Σ_i=1^k P(C_i) log₂ P(C_i)

where P(C_i) is the proportion of instances in D that belong to class C_i. A lower entropy indicates a more homogeneous (pure) set.

6. Computing Information Gain

The Information Gain of an attribute A quantifies the reduction in entropy achieved by splitting the dataset on A. It is calculated as:

Gain(A) = Entropy(D) − Σ_{v∈Values(A)} (|D_v| / |D|) × Entropy(D_v)

In short notation used in many textbooks, this can be expressed as Gain(A) = Info(D) − Info_A(D). The term Info_A(D) represents the weighted average entropy of the subsets created by the split.

7. From Information Gain to Gain Ratio (C4.5)

The C4.5 algorithm prefers the Gain Ratio over raw Information Gain because pure Information Gain tends to favor attributes with many distinct values (e.g., a unique ID). Gain Ratio addresses this bias by dividing the Information Gain by the intrinsic information of the split:

GainRatio(A) = Gain(A) / IntrinsicInfo(A)

where IntrinsicInfo(A) is the entropy of the distribution of instances among the attribute’s values. This normalization ensures that attributes are selected based on true discriminative power rather than sheer number of branches.

8. Summary of Key Points

• A decision tree is a hierarchical model with internal test nodes, branches for outcomes, and leaf nodes for class labels.
• Tree construction follows a recursive, top‑down divide‑and‑conquer strategy.
• One primary stopping condition is when all instances in a node belong to the same class.
• Attribute selection measures, especially Information Gain, guide the choice of splits.
• Entropy quantifies impurity: Entropy(D) = − Σ P(C_i) log₂ P(C_i).
• Information Gain = Entropy before split − weighted entropy after split.
• C4.5 uses Gain Ratio to reduce bias toward attributes with many values.

9. Frequently Asked Questions (FAQ)

Q: Can a decision tree handle continuous attributes?

Yes. Continuous attributes are typically handled by finding a threshold that best splits the data, effectively turning the attribute into a binary test (e.g., "Age ≤ 35").

Q: What happens if the tree becomes too deep?

Overly deep trees may overfit the training data. Techniques such as pruning, setting a maximum depth, or requiring a minimum number of instances per leaf help control complexity.

Q: How does entropy differ from Gini impurity?

Both measure impurity, but entropy uses logarithms and is rooted in information theory, while Gini impurity is based on the probability of misclassification. In practice, they often lead to similar splits.

10. Further Reading and Resources

• Wikipedia: Decision Tree Learning – Overview and variations.
• Quinlan, J. R. (1993). C4.5: Programs for Machine Learning – Classic text on the Gain Ratio.
• Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective – Chapter on tree‑based models.
• Scikit‑learn documentation: DecisionTreeClassifier – Practical implementation details.