Decision Tree Classifier

A Decision Tree is a supervised machine learning algorithm that builds a flowchart-like tree structure to make predictions by recursively partitioning data based on the most informative feature at each step.

I. Components

II. Algorithm Steps

The algorithm is greedy and recursive: it makes the locally best split at every node without backtracking.

Step 1 – Start at the root with the full dataset.

Step 2 – For every feature, evaluate every possible split threshold and compute the impurity reduction (Information Gain):

Step 3 – Choose the feature + threshold that gives the highest Information Gain.

Step 4 – Split the data and create two child nodes (CART) or multiple children (ID3 / C4.5).

Step 5 – Recurse on each child node until a stopping criterion is met:

• Node is pure (all same class)
• max_depth reached
• min_samples_split / min_samples_leaf not satisfied
• min_impurity_decrease threshold not met

Step 6 – Assign the majority class of remaining samples to each leaf.

III. Common Algorithms Used

Overview

★ CART — Classification and Regression Trees

Speciality:

• Strictly binary splits;
• Handles both classification (Gini/Entropy) and regression (MSE/MAE). In sklearn library they are handled by DecisionTreeClassifier and DecisionTreeRegressor respectively.

Advantages and Disadvantages

★ ID3 — (Iterative Dichotomiser 3)

Speciality:

Pioneer algorithm. Picks the feature with the highest Information Gain (entropy-based). Produces multi-way splits — one branch per unique category value.

Advantages and Disadvantages

🚨 Caution: Never use raw IDs, zip codes, or timestamps as features with ID3 — they will always be selected first and create useless, overfitting branches.

★ C4.5

Speciality:

Successor to ID3. It is more sophisticated than ID3, handles "noisy" data better, and is much more efficient. Replaces Information Gain with Gain Ratio to penalise high-cardinality features. Handles continuous attributes via threshold splitting. Grow as large as possible and then "prune" back.

Gain Ratio

Instead of just looking at Information Gain, C4.5 calculates Split Information, which measures how "broad" the split is:

By putting "Split Information" in the denominator, C4.5 effectively "taxes" features that have too many unique outcomes.

The Key Upgrades (Why it beat ID3)

A. Handling Continuous Attributes (Numbers)

ID3 could only handle categories (e.g., "Weather: Sunny, Rainy"). C4.5 can handle numbers (e.g., "Temperature: 72.5°F").

How? It sorts the numbers and creates a threshold (e.g., $Temp>70$ vs. $Temp\le 70$) based on which split provides the best information gain.

B. Handling Missing Values

In real datasets, some rows are always missing data. ID3 would crash or ignore them. C4.5 uses a probabilistic approach, assigning a weight to those records based on the distribution of the known values.

C. Pruning (The "Anti-Overfitting" Tool)

Decision trees often grow too deep, "memorizing" noise in the training data. C4.5 uses Post-Pruning: it builds the full tree and then looks at branches that don't actually help with prediction accuracy and "snips" them off.

D. Gain Ratio (Solving the "Bias" Problem)

ID3 had a massive flaw: it loved features with many unique values (like a "Date" or "Transaction ID"). These have high "Information Gain" but zero predictive power.

How? C4.5 uses the Gain Ratio, which penalizes features that have too many branches, ensuring the tree picks meaningful variables instead.

Choose when: You need multi-way splits but want to avoid the high-cardinality bias of ID3.

Advantages and Disadvantages

Today (Apr 2026), while we often use even more advanced versions like C5.0 (which is faster and uses less memory) or Random Forests, C4.5 remains the benchmark algorithm for "Explainable AI." Because the tree is pruned and uses Gain Ratio, the resulting logic is usually very clean and easy for a human to read.

Code example

• 6. C4.5 with the "Heart Disease" Dataset:
     

★ CHAID — Chi-square Automatic Interaction Detection

Speciality:

• Unlike ID3 or C4.5, which use Information Theory (Entropy), CHAID uses Formal Statistics (Chi-square tests) to determine how to split your data.

The Math:

CHAID calculates the Pearson Chi-square statistic for every potential split.

• For Categorical Targets: It measures the independence between the feature and the target.
• For Numerical Targets: It uses F-tests (ANOVA) instead of Chi-square to see if the means of the groups are significantly different.

Differentiating Factors

1. CHAID is more conservative: it uses Significance Testing (p-values). If a split isn't statistically significant (usually $p>0.05$), CHAID simply stops growing that branch. This prevents the tree from seeing "patterns" that are actually just random noise.
2. Naturally produces multi-way splits. Very interpretable in business settings.
3. Category Merging: Before splitting, CHAID looks at the categories of a feature. If two categories (like "Gold" and "Platinum" credit card holders) show nearly identical behavior, CHAID will merge them into a single group before making the split. This keeps the tree simple and "clean."

Choose when:

You need statistically validated splits, survey analysis, or marketing segmentation. e.g

• Credit Risk: Banks love CHAID because they can explain exactly why a "p-value" triggered a rejection.
• Direct Marketing: If you want to know which demographic (Age + Income + Location) is most likely to buy an ETF, CHAID creates easy-to-read segments.
• Non-Linear Relationships: CHAID is great at finding interactions between variables (e.g., "Age" only matters if "Income" is above a certain level).

Advantages and Disadvantages

IV. Split Criteria (Metrics)

Set via the criterion= parameter in DecisionTreeClassifier.

i. Gini Impurity — criterion="gini" (default)

• Range: 0 (pure) → 0.5 (binary, perfectly mixed)
• Intuition: Probability of incorrectly labelling a randomly picked sample using the node's class distribution.
• Speed: ⚡ Fastest — no logarithm required.

Use when: General-purpose classification; default choice; speed matters.

ii. Entropy — criterion="entropy"

• Range: 0 (pure) → 1 (binary, perfectly mixed) → ${\log }_{2}C$ (C-class max)
• Intuition: Average information needed to identify the class of a sample — measures disorder.
• Speed: ~10–20% slower than Gini due to log calculation.

Use when: You want information-theoretic splits; studying feature selection; replicating ID3/C4.5 behaviour.

📌 In practice: Gini and Entropy almost always produce near-identical trees and accuracy. Start with Gini; switch to Entropy only if cross-validation shows a meaningful difference.

iii. Log Loss — criterion="log_loss" (sklearn ≥ 1.1)

• Intuition: Penalises confident wrong predictions heavily; directly optimises probability calibration rather than classification boundaries.
• Speed: Slowest of the three.

Use when: You need well-calibrated probabilities for downstream use — risk scoring, medical diagnosis, cost-sensitive decisions where predict_proba output matters more than raw accuracy.

V. Binary vs. Multi-way Splits

i. Binary Split (CART — sklearn default)

Every node asks exactly one yes/no question. Categorical features are tested as feature ∈ {subset} vs feature ∉ {subset}.

• Produces a deeper but narrower tree.
• Lower overfitting risk — small categories get grouped together rather than isolated branches.

Outlook == Overcast?
   ├── Yes → [Pure: Play=Yes]  ✓ Stop
   └── No  → [Mixed: Sunny + Rainy] → split further

ii. Multi-way Split (ID3 / C4.5 / CHAID)

Creates one branch per unique value of the chosen feature simultaneously.

• Produces a wider but shallower tree.
• Higher overfitting risk — high-cardinality features produce many tiny, pure branches that don't generalise.

Outlook?
   ├── Sunny    → [Mixed] → split further
   ├── Overcast → [Pure: Play=Yes] ✓ Stop
   └── Rainy    → [Mixed] → split further

Comparison

VI. Pros and Cons

VII. Overfitting, Bias–Variance Trade-Off & Pruning

The Core Problem

An unconstrained decision tree grows until every leaf is pure — perfectly fitting the training data but failing on unseen data.

Unconstrained tree:  Train acc = 100%,  Test acc = 65%  ← Overfit
max_depth=4 tree:    Train acc = 85%,   Test acc = 83%  ← Generalises ✅
max_depth=2 tree:    Train acc = 72%,   Test acc = 71%  ← Underfit

Bias–Variance Trade-Off

Approach 1 — Pre-Pruning (Hyperparameter Constraints)

Stop the tree from growing too large during training.

max_leaf_nodes — grows the tree best-first (highest IG first) rather than depth-first, then stops when the leaf count is reached. Often produces a better shape than max_depth alone because it always expands the most informative branch next.

max_features — at each split, only a random subset of features is evaluated. Reduces correlation between splits, acts as mild regularisation, and is the key mechanism that makes Random Forest effective.

Approach 2 — Post-Pruning with ccp_alpha

Train a full tree first, then prune back branches whose cost-complexity score falls below threshold $\alpha$.

Cost-Complexity Criterion:

Where $R(T)$ = misclassification rate, $|T|$ = number of leaves.

Always select ccp_alpha via cross-validation using the pruning path — never guess.

Approach 3 — GridSearchCV

Cross-validate over multiple hyperparameters simultaneously to find the optimal combination.

VIII. Special Parameters Deep-Dive

1. ccp_alpha — Cost-Complexity Pruning

path = DecisionTreeClassifier(random_state=42)\
           .cost_complexity_pruning_path(X_train, y_train)
# path.ccp_alphas → array of alpha values from full tree → root-only tree
# path.impurities → corresponding total impurity at each alpha

Train one tree per alpha value, plot accuracy vs alpha, and pick the alpha that maximises cross-validation accuracy.

2. class_weight — Handling Class Imbalance

Adjusts the impurity calculation so minority classes are treated as more important during splitting.

• By setting class_weight, you are telling the math: "Every time you misclassify a minority, it hurts $10\times$ more than misclassifying a majority."
• The tree will then favor splits that isolate the minority class, even if it makes the overall accuracy slightly lower.

# Auto-balance by inverse class frequency
DecisionTreeClassifier(class_weight='balanced')

# Manual weights  (minority class gets 5× the weight)
DecisionTreeClassifier(class_weight={0: 1, 1: 5})

📌 Using class_weight is equivalent to oversampling the minority class but without duplicating rows.
🚫 If your dataset is extremely imbalanced (e.g., 1 in 10,000), class weights can make the Decision Tree very "jittery" and prone to overfitting on those few minority samples.

3. max_features — Feature Subsampling per Split

Use "sqrt" when using a single DT as a weak learner, or to add regularisation without building a full ensemble.

4. max_leaf_nodes — Best-First Growth Cap

• Without max_leaf_nodes → depth-first, may waste splits on unimportant branches
• With max_leaf_nodes → always expands the most informative branch next
• bias-variance balance: Often gives a better bias-variance balance than max_depth alone, especially on imbalanced or multi-class data.

Growth order: at each step the leaf with the highest potential IG is expanded — not simply left-to-right by depth. This gives a more efficient use of the node budget.

IX. Code Examples

1. Train, Evaluate & Visualise:
   
2. Bias–Variance Plot: Sweeping max_depth:
   
3. Post-Pruning: ccp_alpha Path:
   
4. GridSearchCV Hyperparameter Tuning:
   
5. Feature Importance Plot:
   

X. Summary Cheat-Sheet

Key attributes available after fitting:

clf.tree_.max_depth        # actual depth reached
clf.get_depth()            # same via public API
clf.get_n_leaves()         # number of leaf nodes
clf.feature_importances_   # Gini-based importance per feature
clf.classes_               # class labels in order

XI. Questions and Answers

1. How to pick the values for class_weight?

Option A: The "Balanced" Auto-Pilot (Recommended)

Most libraries (like Scikit-Learn) have a built-in setting called class_weight='balanced'.

The Formula:

It automatically calculates weights inversely proportional to class frequencies:

• Example: If you have 100 samples (90 "Safe", 10 "Risk"):

  • Weight for Safe: $100/(2\times 90)=\mathbf{0.55}$

  • Weight for Risk: $100/(2\times 10)=\mathbf{5.0}$

• Result: The model treats each "Risk" instance as being $9\times$ more important than a "Safe" instance.

Option B: Manual "Cost-Based" Weighting

Sometimes "Balanced" isn't enough. In finance, the cost of a False Negative (missing a default) is much higher than a False Positive (denying a good loan).

You can pass a dictionary: class_weight={0: 1, 1: 20}.

• Pick this when you have a specific Business Cost associated with an error. If a missed "Class 1" event costs the firm $20k$ and a false alarm costs $1k$, a $1:20$ ratio is mathematically sound.

How manually setting class_weight changes the Math (Gini/Entropy)?

When you add weights, the "Purity" calculation changes.

Instead of:

It becomes:

XII. External References

• Scikit-Learn — DecisionTreeClassifier
• Scikit-Learn — Cost-Complexity Pruning
• The Simple Math behind 3 Decision-Tree Splitting Criterions
• Decision Tree Implementation from Scratch