Decision Tree

The Story: Ramesh the Loan Officer

What Is a Decision Tree?

A Decision Tree is a supervised learning algorithm that models decisions as a flowchart-like tree structure. It learns a hierarchy of if-else questions from training data.

Anatomy of a Decision Tree

Real Worked Example: The "Play Tennis" Dataset

This is the canonical dataset used to teach ID3 — the original decision tree algorithm by Ross Quinlan (1986). The task: given weather conditions, should we play tennis today? We have 14 days of historical data with four weather features and the outcome.

The dataset has 9 Yes and 5 No — written as S = [9+, 5-]. ID3 must figure out which of the four features creates the most useful first split by calculating Information Gain for each.

Entropy and Information Gain — Choosing the Root Split

Attribute: Outlook — Gain = 0.246 bits (WINNER)

Outlook creates 3 groups: Sunny (D1,D2,D8,D9,D11), Overcast (D3,D7,D12,D13), Rain (D4,D5,D6,D10,D14).

Recursion: Sunny Branch uses Humidity

The Sunny subset (D1, D2, D8, D9, D11) has [2+, 3-], H = 0.971 bits. Recursing on the 3 remaining attributes:

Recursion: Rain Branch uses Wind

The Rain subset (D4, D5, D6, D10, D14) has [3+, 2-], H = 0.971 bits.

The Final Decision Tree: Play Tennis

Entropy and Gini Ranges for Multiple Classes

A key insight from the Play Tennis example: entropy maximum depends on the number of classes. This matters when comparing problems.

Gini Impurity vs Entropy — Full Comparison

How the CART Algorithm Builds the Tree

Overfitting and Pruning

Left unconstrained, a tree grows until every leaf is pure — memorising every training sample including noise. The Play Tennis tree happened to generalise perfectly because the dataset is clean. Real datasets have noise, and deep trees overfit badly.

Key Hyperparameters

Python — Replicating the Play Tennis Example

import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.preprocessing import OrdinalEncoder

# The Play Tennis dataset — exactly as in the lecture
data = pd.DataFrame({
    'Outlook' : ['Sunny','Sunny','Overcast','Rain','Rain','Rain',
                 'Overcast','Sunny','Sunny','Rain','Sunny','Overcast',
                 'Overcast','Rain'],
    'Temp'    : ['Hot','Hot','Hot','Mild','Cool','Cool','Cool',
                 'Mild','Cool','Mild','Mild','Mild','Hot','Mild'],
    'Humidity': ['High','High','High','High','Normal','Normal','Normal',
                 'High','Normal','Normal','Normal','High','Normal','High'],
    'Wind'    : ['Weak','Strong','Weak','Weak','Weak','Strong','Strong',
                 'Weak','Weak','Weak','Strong','Strong','Weak','Strong'],
    'PlayTennis': ['No','No','Yes','Yes','Yes','No','Yes','No','Yes',
                   'Yes','Yes','Yes','Yes','No']
})

X_raw = data[['Outlook','Temp','Humidity','Wind']]
y     = (data['PlayTennis'] == 'Yes').astype(int)

enc = OrdinalEncoder()
X   = enc.fit_transform(X_raw)

# Use entropy to replicate ID3 behaviour
dt = DecisionTreeClassifier(criterion='entropy', random_state=42)
dt.fit(X, y)

# Print the learned rules
rules = export_text(dt, feature_names=['Outlook','Temp','Humidity','Wind'])
print(rules)

# Feature importances — matches our hand-calculated IG table
for feat, imp in zip(['Outlook','Temp','Humidity','Wind'], dt.feature_importances_):
    print(f"  {feat:<12} importance: {imp:.4f}")

Classification Tree — Bank Loan Approval

import numpy as np
import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.metrics import accuracy_score, classification_report

np.random.seed(42)
n = 500

data = pd.DataFrame({
    'credit_score'    : np.random.randint(500, 850, n),
    'annual_income'   : np.random.randint(20, 150, n),
    'debt_ratio'      : np.random.uniform(0.1, 0.8, n),
    'employment_years': np.random.randint(0, 20, n),
    'num_accounts'    : np.random.randint(1, 10, n),
})

approved = (
    (data['credit_score']     >= 700) &
    (data['annual_income']    >= 50)  &
    (data['debt_ratio']       <= 0.4)
) | (
    (data['credit_score']     >= 650) &
    (data['employment_years'] >= 5)   &
    (data['debt_ratio']       <= 0.35)
)
data['approved'] = approved.astype(int)
noise_idx = np.random.choice(n, size=50, replace=False)
data.loc[noise_idx, 'approved'] = 1 - data.loc[noise_idx, 'approved']

X = data.drop('approved', axis=1)
y = data['approved']

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=42, stratify=y
)

# Compare depths — shows bias-variance tradeoff
for depth in [2, 5, None]:
    dt = DecisionTreeClassifier(criterion='gini', max_depth=depth, random_state=42)
    dt.fit(X_train, y_train)
    train_acc = accuracy_score(y_train, dt.predict(X_train))
    test_acc  = accuracy_score(y_test,  dt.predict(X_test))
    print(f"depth={str(depth):>4}  train={train_acc:.3f}  test={test_acc:.3f}  gap={train_acc-test_acc:+.3f}")

# GridSearchCV to find optimal hyperparameters
param_grid = {
    'max_depth'        : [2, 3, 4, 5, 6],
    'min_samples_split': [5, 10, 20],
    'min_samples_leaf' : [2, 5, 10],
    'criterion'        : ['gini', 'entropy'],
}
grid = GridSearchCV(DecisionTreeClassifier(random_state=42),
                    param_grid, cv=5, scoring='accuracy', n_jobs=-1)
grid.fit(X_train, y_train)
print(f"
Best params : {grid.best_params_}")
print(f"Best CV acc : {grid.best_score_:.4f}")
print(f"Test acc    : {accuracy_score(y_test, grid.predict(X_test)):.4f}")

Feature Importances and Prediction

best_dt = grid.best_estimator_

# Feature importances
importances = pd.Series(best_dt.feature_importances_, index=X.columns).sort_values(ascending=False)
print("Feature Importances (MDI):")
print(importances.round(4))

# Predict a new applicant
new_applicant = pd.DataFrame([{
    'credit_score': 720, 'annual_income': 65, 'debt_ratio': 0.30,
    'employment_years': 8, 'num_accounts': 3
}])
pred  = best_dt.predict(new_applicant)[0]
proba = best_dt.predict_proba(new_applicant)[0]
print(f"New applicant: {'Approved' if pred==1 else 'Rejected'}")
print(f"Confidence   : Rejected={proba[0]:.2f}  Approved={proba[1]:.2f}")

Advantages and Disadvantages

Golden Rules