Decision Trees | AI Pathshala

Definition

How would you guess an animal in five yes-or-no questions?

A decision tree predicts by asking a sequence of feature-threshold questions, from the root to a leaf. CART builds it greedily: at each node it chooses the split that most reduces impurity, measured by Gini impurity or entropy (information gain) for classification, or variance for regression. Trees grow until a stopping rule, and pruning removes branches that don't improve validation performance.

In simple words

At each step, ask the question that splits the group into the purest halves: 'Is the tumour radius above 16?' might send nearly all malignant cases one way. Gini measures mixedness: 0 means everyone in the group has the same label. A tree that keeps splitting until every leaf is pure has memorised the training data.

Why it matters

Trees handle mixed feature types, need no scaling, capture interactions and can be read as rules. They are also the building blocks of random forests and gradient boosting, the strongest methods for tabular data.

How it works

For every feature and every candidate threshold, compute the weighted impurity of the two children.
Choose the split with the largest impurity decrease.
Recurse on each child until max_depth, min_samples_leaf or purity stops it.
Prune: limit depth or use cost-complexity pruning (ccp_alpha) chosen by validation.

The maths

Gini impurity

G = 1 - k = 1 \sum K p_{k}^{2}

Entropy and information gain

H = - k \sum p_{k} lo g_{2} p_{k}, I G = H (parent) - child \sum \frac{n _{child}}{n} H (child)

$p_{k}$: Share of class k in the node

A node holds 6 positives and 4 negatives. Gini = 1 − (0.6² + 0.4²) = 0.48. A split sends 5 positives and 1 negative left, and 1 positive and 3 negatives right.

Left:  1 − ((5/6)² + (1/6)²) = 0.278   (6 samples)
Right: 1 − ((1/4)² + (3/4)²) = 0.375   (4 samples)
Weighted = 0.6 × 0.278 + 0.4 × 0.375 = 0.317
Decrease = 0.48 − 0.317 = 0.163

In code

The Gini split above computed by hand, then a scikit-learn tree whose depth controls overfitting, with its top rules printed.

decision_tree.py

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

def gini(counts):
    p = np.array(counts) / sum(counts)
    return 1 - np.sum(p ** 2)

parent = gini([6, 4])
weighted = 0.6 * gini([5, 1]) + 0.4 * gini([1, 3])
print(f"Parent Gini {parent:.3f}, children {weighted:.3f}, decrease {parent - weighted:.3f}")

data = load_breast_cancer()
X_tr, X_te, y_tr, y_te = train_test_split(data.data, data.target, test_size=0.3, random_state=0)
print("depth  train acc  test acc  leaves")
for depth in [1, 2, 4, 8, None]:
    tree = DecisionTreeClassifier(max_depth=depth, random_state=0).fit(X_tr, y_tr)
    print(f"{str(depth):>5}  {tree.score(X_tr, y_tr):9.3f}  {tree.score(X_te, y_te):8.3f}  {tree.get_n_leaves():>6}")

small = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X_tr, y_tr)
print(export_text(small, feature_names=list(data.feature_names)))

Output

Parent Gini 0.480, children 0.317, decrease 0.163
depth  train acc  test acc  leaves
    1      0.930     0.895       2
    2      0.960     0.947       4
    4      0.977     0.947      10
    8      1.000     0.912      19
 None      1.000     0.912      19
|--- worst concave points <= 0.14
|   |--- worst area <= 952.90
|   |   |--- class: 1
|   |--- worst area >  952.90
|   |   |--- class: 0
|--- worst concave points >  0.14
|   |--- area error <= 13.93
|   |   |--- class: 1
|   |--- area error >  13.93
|   |   |--- class: 0

Try it yourself

Compute Gini

Match each node's class counts to its Gini impurity.

10 positives, 0 negatives
5 positives, 5 negatives
8 positives, 2 negatives
Three classes, equal shares

Common mistakes

Growing trees with no depth limit and trusting their training accuracy.
Reading the first split as the only important feature. Correlated features can swap places.
Expecting smooth predictions. Trees make step functions.

Check yourself

1. Gini impurity of a pure node is…

2. How does CART choose a split?

3. Which reduces overfitting in a tree?

Summary

Trees split greedily to reduce Gini or entropy.
They need no scaling and read as rules.
Control depth or prune to avoid memorising the data.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: scikit-learn: Decision trees · James et al., An Introduction to Statistical Learning