Decision Trees: ID3, C4.5 and CART Explained

Read both the tree and its evidence

You will compare the main split criteria historically associated with ID3, C4.5 and CART, then train a small pruned tree and inspect every rule.

• Calculate the intuition behind entropy, information gain and Gini impurity.
• Explain why gain ratio discourages splits with many values.
• Distinguish multiway ID3-style splits from binary CART splits.
• Use depth, leaf-size and cost-complexity pruning to control variance.

A split tries to create purer children

Entropy is zero when every record in a node has the same class and higher when classes are mixed. Information gain subtracts the weighted child entropy from the parent entropy. ID3 chooses the attribute with the highest gain, which can favour an identifier with many unique values.

C4.5 extends the idea with continuous thresholds, missing-value handling and gain ratio. Gain ratio divides by a split-information term, reducing the advantage of fragmenting data into many small branches. CART builds binary trees and commonly uses Gini impurity for classification and squared-error reduction for regression.

A fully grown tree can memorize training quirks. Pre-pruning limits depth, requires more samples in a split or enforces a minimum leaf size. Post-pruning removes weak branches after growth. Scikit-learn exposes CART-style cost-complexity pruning through ccp_alpha.

Feature importance based on impurity reduction can favour continuous or high-cardinality features. Use held-out permutation importance and error inspection as additional evidence. Correlated features can share or substitute importance, so neither method provides a causal explanation.

Readable rules help domain review. Print sample counts and class distribution for each leaf. A rule affecting three records is not equivalent to a rule supported by three thousand.

Train a small, bounded CART tree

The example uses a shallow tree so every rule can be printed. It is a teaching dataset, not an accuracy benchmark.

Install the lesson dependencies

python -m pip install numpy scikit-learn

Inspect thresholds and leaves

import numpy as np
from sklearn.tree import DecisionTreeClassifier, export_text

feature_names = ["visits", "open_tickets"]
X = np.array([
    [1, 3], [2, 2], [3, 2], [4, 1],
    [6, 1], [7, 0], [8, 1], [9, 0],
])
y = np.array([0, 0, 0, 0, 1, 1, 1, 1])

tree = DecisionTreeClassifier(
    criterion="gini",
    max_depth=2,
    min_samples_leaf=2,
    random_state=42,
)
tree.fit(X, y)

print(export_text(tree, feature_names=feature_names))
print("training predictions:", tree.predict(X).tolist())
print("leaf samples:", tree.tree_.n_node_samples[tree.tree_.children_left == -1].tolist())

Expected rule shape

|--- visits <= 5.00
|   |--- class: 0
|--- visits >  5.00
|   |--- class: 1

training predictions: [0, 0, 0, 0, 1, 1, 1, 1]
leaf samples: [4, 4]

A perfect training separation is expected because the sample was constructed that way. Evaluate on unseen data before assigning significance to the rule.

Tree behaviour that needs investigation

Small changes in data can produce a different first split. Treat a tree as fitted evidence, not a timeless policy.

• An ID-like feature near the root suggests high-cardinality overfitting or leakage.
• Leaves with very few samples create unstable probabilities.
• An unbounded tree with near-perfect training performance and weak validation is overfitting.
• Missing values require a declared imputation or estimator-specific policy before prediction.

Compare pruning choices

Train trees across depths 1 through 10 and several ccp_alpha values using cross-validation.

• Plot training and validation scores against tree size.
• Print the selected tree with leaf counts and class distributions.
• Inspect false-positive and false-negative leaves.
• Compare impurity and permutation importance on the held-out set.

Evidence to retain

• Cross-validated pruning table.
• Readable selected tree.
• A note on one unstable or misleading rule.

Official references and further reading

• scikit-learn decision trees (Official CART implementation and pruning guidance)
• scikit-learn permutation importance (Official held-out importance method and caveats)

Review note for Decision Trees: ID3, C4.5 and CART Explained: recheck the linked documentation after a dependency changes the relevant API, metric or modelling assumption, then record the tested version beside your result.