Decision Trees

1. Introduction

A Decision Tree makes predictions the same way a person might play a game of "20 Questions" — asking a series of yes/no questions about the data until it arrives at a confident answer. It's one of the most intuitive and visually interpretable ML algorithms, and it forms the foundation for the much more powerful Random Forest algorithm covered next.

2. What is a Decision Tree?

Simple definition: A Decision Tree is a supervised learning algorithm that makes predictions by asking a series of yes/no (or threshold-based) questions about the input features, branching through a tree-like structure until it reaches a final prediction.

Technical explanation: A Decision Tree recursively splits the training data into increasingly pure subsets based on feature values, choosing splits that maximize "information gain" (or minimize impurity, commonly measured via Gini Impurity or Entropy), continuing until a stopping condition (like maximum depth) is reached, at which point each leaf node represents a final prediction.

3. Why is it Important?

• It's highly interpretable — you can literally trace the exact path of decisions that led to any prediction.
• It naturally handles both numeric and categorical features without requiring extensive preprocessing.
• It forms the building block for Random Forest (Topic 6), one of the most powerful and widely used ML algorithms in practice.

4. Prerequisites

Comfort with Supervised Learning concepts (Module 2, Topic 5) and Basic Probability (Module 1, Topic 9, for understanding impurity measures).

5. Core Concepts

1. Nodes, branches, and leaves
2. Splitting criteria: Gini Impurity and Entropy
3. Information Gain
4. Tree depth and stopping conditions
5. Overfitting risk in Decision Trees

6. Detailed Explanation

a) Nodes, Branches, and Leaves

A Decision Tree consists of a root node (the starting question), internal nodes (further questions), branches (the possible answers, leading to the next node), and leaf nodes (final predictions, with no further splits).

b) Splitting Criteria: Gini Impurity and Entropy

At each node, the algorithm must decide which feature and threshold to split on. It does this by evaluating how "pure" the resulting groups would be — Gini Impurity and Entropy are the two most common measures of impurity, both quantifying how mixed the classes are within a group (0 = perfectly pure, higher values = more mixed).

c) Information Gain

Information Gain measures how much a particular split reduces impurity — the algorithm chooses the split (feature + threshold) that provides the greatest information gain at each step.

d) Tree Depth and Stopping Conditions

Without limits, a Decision Tree could keep splitting until every single training example has its own leaf — a sign of severe overfitting. Setting a max_depth (or other stopping conditions like minimum samples per leaf) prevents the tree from growing excessively complex.

e) Overfitting Risk

Decision Trees are notoriously prone to overfitting — memorizing the training data too closely, including its noise, rather than learning generalizable patterns (explored in depth in Module 7).

7. How It Works

1. Starting with the full training dataset at the root node, evaluate all possible splits (feature + threshold combinations).
2. Choose the split that produces the greatest reduction in impurity (highest information gain).
3. Divide the data into two (or more) branches based on that split.
4. Repeat this process recursively for each resulting branch, until a stopping condition is met (max depth, minimum samples, or perfectly pure nodes).
5. Each final leaf node represents a class prediction (for classification) or a numeric value (for regression).

8. Real-World Example

A bank deciding whether to approve a loan might use a Decision Tree that first asks "Is the applicant's credit score above 700?" If yes, it might then ask "Is their income above $50,000?" and so on, eventually reaching a final approve/reject decision — this mirrors exactly how a human loan officer might reason through a checklist of criteria.

9. Mathematical Explanation

Gini Impurity Formula:

Gini = 1 − Σ(pᵢ)²

Where:

• pᵢ = the proportion of samples belonging to class i within that node
• The sum is taken across all classes present in the node

Numerical Example:

Suppose a node contains 10 samples: 6 belong to Class A, 4 belong to Class B.

• p(A) = 6/10 = 0.6, p(B) = 4/10 = 0.4
• Gini = 1 − (0.6² + 0.4²) = 1 − (0.36 + 0.16) = 1 − 0.52 = 0.48

Interpreting the Result: A Gini value of 0 would mean the node is perfectly pure (only one class present); a Gini of 0.48 indicates a fairly mixed node. The algorithm looks for splits that reduce this value as much as possible in the resulting child nodes.

10. Python Example

python
from sklearn.tree import DecisionTreeClassifier, plot_tree
import matplotlib.pyplot as plt

# Features: [hours_studied, attendance_percent]
X = [[1, 60], [2, 65], [3, 70], [8, 95], [9, 98], [7, 90]]
y = [0, 0, 0, 1, 1, 1]   # 0 = Fail, 1 = Pass

model = DecisionTreeClassifier(max_depth=2, random_state=42)
model.fit(X, y)

prediction = model.predict([[6, 85]])
print("Prediction (0=Fail, 1=Pass):", prediction[0])

# Visualizing the tree structure
plt.figure(figsize=(10, 6))
plot_tree(model, feature_names=["hours_studied", "attendance_percent"],
          class_names=["Fail", "Pass"], filled=True)
plt.show()

Expected Output (approximate):

text
Prediction (0=Fail, 1=Pass): 1

(A tree diagram also displays, showing the exact splitting rules the model learned.)

11. Code Explanation

• DecisionTreeClassifier(max_depth=2, ...) limits the tree to a maximum of 2 levels of splits, helping prevent overfitting on this small example dataset.
• model.fit(X, y) builds the tree by recursively finding the best splits based on Gini Impurity (the default criterion).
• model.predict([[6, 85]]) traces this new student's data through the learned tree's decision rules to arrive at a final prediction.
• plot_tree(...) visually displays the actual decision rules the tree learned — for example, showing exactly which feature and threshold was used at each split, making the model's logic fully transparent and interpretable.

12. Advantages

• Highly interpretable — the exact decision-making logic can be visualized and understood.
• Handles both numeric and categorical data without requiring scaling or extensive preprocessing.
• Naturally captures non-linear relationships and interactions between features.

13. Limitations

• Prone to overfitting, especially with deep trees that closely memorize training data.
• Can be unstable — small changes in training data can lead to a very different tree structure.
• Individual trees often have somewhat lower predictive accuracy than ensemble methods like Random Forest (Topic 6).

14. Common Mistakes

• Not limiting tree depth (max_depth), leading to severe overfitting on training data.
• Assuming a single Decision Tree will always outperform more robust ensemble methods.
• Ignoring how sensitive Decision Trees can be to small changes in the training data.

15. Best Practices

• Set a reasonable max_depth or other stopping conditions to control overfitting.
• Visualize the tree (plot_tree) to sanity-check that the learned rules make logical sense.
• Consider Random Forest (Topic 6) when a single Decision Tree's instability or overfitting becomes a concern.

16. Real-World Applications

• Loan approval and credit risk assessment.
• Medical diagnosis decision support systems.
• Customer segmentation based on clear, interpretable business rules.

17. Interview-Oriented Points

• Be ready to explain how a Decision Tree chooses where to split (Gini Impurity or Entropy, and Information Gain).
• Understand why Decision Trees are prone to overfitting, and how max_depth helps control this.
• Be able to explain the tree-based prediction process in simple, step-by-step terms.

18. Exam-Oriented Points

• Decision Trees split data recursively based on feature thresholds, aiming to reduce impurity (Gini or Entropy) at each step.
• max_depth and similar parameters help prevent overfitting by limiting tree complexity.
• Predictions are made by following the learned decision path down to a leaf node.

19. Comparison Table — Gini Impurity vs Entropy

20. Quick Revision

• Decision Trees make predictions through a series of feature-based yes/no questions, structured as a tree.
• Splits are chosen to reduce impurity (Gini Impurity or Entropy) as much as possible at each step.
• max_depth and similar parameters help control overfitting, a common risk with Decision Trees.
• Decision Trees are highly interpretable but can be less accurate and less stable than ensemble methods like Random Forest.