Decision trees

Recursive partitioning

A decision tree splits the feature space into rectangles. Each internal node asks whether one feature is above or below a threshold. Each leaf predicts the majority label of the training rows that reached it. The boundary is a staircase of axis-aligned cuts, not a smooth curve.

The tree is built greedily. At each node, try every feature and every candidate threshold. Score the split and keep the best one. Then repeat on the two children. Greedy means the tree never revisits an early choice. A locally good split can block a better one two levels down. That is a limitation, and it is also what makes the algorithm fast.

The greedy choice is not the only way to build a tree. It is the one that keeps the algorithm tractable. Trying every possible tree and picking the best would take exponential time. The greedy tree is a heuristic, a rule of thumb rather than a guarantee. Its quality depends on the data and on the rule used to score splits. Random forests and boosted trees build many such trees because one greedy tree is unstable.

Impurity

A split is good if the children are purer than the parent. Purity here means how much a node leans toward one class. Gini impurity is one minus the sum of squared class proportions. It is zero when a node is pure and highest when the classes are evenly mixed. Entropy is the other common measure. Information gain is the drop in entropy. The two measures usually agree on which split is best.

The score for a candidate is the weighted average of the children’s impurity. The weights are the share of rows that land in each child. A split that isolates one row perfectly but leaves the rest mixed is not necessarily good. The large child still carries most of the uncertainty. The parent’s impurity minus this weighted score is the gain.

A tree with a depth limit

from sklearn.tree import DecisionTreeClassifier

model = DecisionTreeClassifier(
    criterion="gini",
    max_depth=3,
    min_samples_leaf=5,
    random_state=0,
)
model.fit(X_train, y_train)
print(model.score(X_test, y_test))

Overfitting and pruning

An unconstrained tree can keep splitting until every training row is its own leaf. That gives perfect training accuracy and a boundary that follows every noisy point. The tree has low bias and high variance. It fits the sample closely, but a different sample would produce a different set of cuts. Depth, minimum leaf size and minimum impurity decrease are the usual pre-pruning controls.

Post-pruning grows a full tree and then removes branches. A branch goes if it does not pay for itself on validation data. Cost-complexity pruning is the standard version. It penalises the number of leaves and chooses the penalty by cross-validation. Either way, the goal is the same. Stop before the splits describe the sample rather than the pattern.

Cost-complexity pruning has a clear objective. It minimises the training impurity plus a penalty times the number of leaves. The penalty is chosen by cross-validation. The tree is then pruned against held-out data rather than against the training set. That is the same discipline as early stopping, applied to a structure instead of a number of epochs.

Strengths and limits

Trees need no feature scaling. With the right encoding they handle mixed numeric and categorical columns. They can capture interactions that a linear model would need to be told about. A shallow tree can be read aloud as a set of rules. That is valuable when someone has to approve the decision. Training is fast and prediction is a sequence of comparisons.

The axis-aligned boundary is also the weakness. A diagonal relationship needs many staircase steps. A smooth function is approximated crudely. Trees cannot extrapolate. A leaf predicts a training average, so a value beyond the observed range gets the same answer as the edge of the leaf. Ensembles fix much of the variance. The cost is the single tree’s readability.

The split rule also has a subtle bias. Gini and entropy favour features with many distinct values. More thresholds give more chances to find a good cut. So a random forest’s feature importance can be misleading when the columns have different numbers of distinct values. Permutation importance, measured on held-out data, is a better check on whether a feature actually matters.