Decision trees and ensembles

A decision tree is a supervised learning model that makes predictions by splitting data into branches based on feature values, forming a tree of decision nodes that ends in leaf nodes giving the output. Each internal node tests a feature, each branch represents an outcome of the test, and each leaf gives a class label (classification) or value (regression). It mimics human if-then reasoning and is easy to interpret.

Internal (decision) nodes represent a test on a single feature, and the branches leaving them correspond to the possible outcomes of that test. Leaf (terminal) nodes represent the final prediction, which is a class label for classification or a numeric value for regression. The path from root to leaf forms the rule used to make a prediction.

Gini impurity measures how mixed the classes are in a node; it is the probability of misclassifying a randomly chosen sample if it were labeled according to the class distribution in that node. It ranges from 0 (pure) up to a maximum of 1 - 1/k for k classes (which equals 0.5 for two equally likely classes). A Gini impurity of 0 means the node is pure: all samples belong to a single class.

# Gini for a node with class probabilities p
gini = 1 - sum(p_i**2 for p_i in p)

Gini impurity equals 1 minus the sum of the squared class probabilities: Gini = 1 - Σ p_i². For example, a node with 50% class A and 50% class B gives 1 - (0.25 + 0.25) = 0.5. Lower values indicate purer nodes.

gini = 1 - sum(p_i**2 for p_i in probs)

Entropy measures the disorder or uncertainty of the class distribution in a node, defined as Entropy = -Σ p_i log2(p_i). It is 0 when the node is pure (one class) and maximal (1 bit for two equal classes) when classes are evenly mixed. Trees use entropy to decide which split best reduces uncertainty.

import math
entropy = -sum(p*math.log2(p) for p in probs if p > 0)

Information gain is the reduction in entropy (or impurity) achieved by splitting a node on a particular feature: it is the parent entropy minus the weighted average entropy of the child nodes. The tree-building algorithm chooses the feature and threshold that maximize information gain at each step. Higher information gain means the split separates the classes more cleanly.

gain = parent_entropy - (w_left*left_entropy + w_right*right_entropy)

A fully grown tree keeps splitting until leaves are pure, creating very deep, specific rules that memorize the training data including its noise. This makes it fit training data almost perfectly but generalize poorly to new data, showing high variance. Limiting depth, requiring minimum samples per leaf, or pruning reduces this overfitting.

Pruning removes parts of a tree (subtrees or branches) that provide little predictive power, replacing them with leaves. It is used to reduce overfitting and improve generalization by simplifying an overly complex tree. Pre-pruning stops growth early (e.g., max depth), while post-pruning grows the full tree then trims it back.

Common controls include max_depth (limits how deep the tree grows), min_samples_split (minimum samples needed to split a node), min_samples_leaf (minimum samples in a leaf), and max_leaf_nodes. Restricting these prevents the tree from creating tiny, overly specific leaves. They act as regularization to balance bias and variance.

from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(max_depth=4, min_samples_leaf=5)

In a regression tree, each leaf predicts a continuous value, typically the mean of the target values of the training samples that fall in that leaf. Splits are chosen to minimize a measure like mean squared error (variance reduction) rather than classification impurity. The result is a piecewise-constant function over the feature space.

from sklearn.tree import DecisionTreeRegressor
reg = DecisionTreeRegressor(max_depth=3)

Ensemble learning combines the predictions of several base models to produce a stronger overall model. By aggregating diverse models, errors from individual models tend to cancel out, reducing variance and/or bias and improving accuracy and robustness. Common ensemble methods include bagging, boosting, and stacking.

Bagging trains many base models on different bootstrap samples (random samples drawn with replacement) of the training data, then averages their outputs (or takes a majority vote). It mainly reduces variance, making unstable, high-variance models like deep decision trees much more reliable. Because the models are trained independently, bagging can be parallelized easily.

A bootstrap sample is a dataset of the same size as the original, created by randomly drawing samples with replacement, so some rows appear multiple times and others are left out. Each base model in bagging is trained on its own bootstrap sample, which introduces the diversity needed for the ensemble. On average about 63% of unique rows appear in each bootstrap sample.

A random forest is an ensemble of decision trees built with bagging plus an extra source of randomness: at each split, only a random subset of features is considered. This feature randomness decorrelates the trees, so their errors are more independent and the averaged result has lower variance than ordinary bagging. Predictions are made by majority vote (classification) or averaging (regression).

from sklearn.ensemble import RandomForestClassifier
rf = RandomForestClassifier(n_estimators=100, max_features='sqrt')

If a few features are very strong predictors, all bagged trees would split on them similarly and become highly correlated, limiting variance reduction. Restricting each split to a random feature subset forces trees to use different features, making them more diverse and decorrelated. Averaging decorrelated trees reduces overall variance more effectively.

For each tree, the samples not included in its bootstrap sample are its out-of-bag samples. The OOB error estimates generalization performance by predicting each training sample using only the trees that did not see it, then comparing to the true labels. This gives a built-in validation estimate without needing a separate test set.

rf = RandomForestClassifier(oob_score=True)
rf.fit(X, y); print(rf.oob_score_)

Boosting builds models sequentially, where each new model focuses on correcting the errors of the previous ones, and the final prediction is a weighted combination. Unlike bagging, which trains independent models in parallel to reduce variance, boosting is sequential and primarily reduces bias (and often variance too). Examples include AdaBoost and gradient boosting.

AdaBoost assigns weights to training samples; after each weak learner, it increases the weights of misclassified samples and decreases those of correctly classified ones. The next weak learner therefore focuses more on the hard, previously misclassified examples. Final predictions combine the weak learners weighted by their accuracy.

Gradient boosting builds an additive model by sequentially adding trees, where each new tree is trained to predict the residual errors (negative gradient of the loss) of the current ensemble. By repeatedly fitting the leftover errors, the model gradually reduces the loss. A learning rate scales each tree's contribution to control the pace and prevent overfitting.

from sklearn.ensemble import GradientBoostingClassifier
gb = GradientBoostingClassifier(learning_rate=0.1, n_estimators=100)

The learning rate (shrinkage) scales the contribution of each new tree to the ensemble, so a smaller value makes each tree add less and slows learning. Lower learning rates usually require more trees but improve generalization and reduce overfitting. It trades off training speed against accuracy and is tuned together with the number of estimators.

Weak learners are simple models that perform only slightly better than random guessing, commonly shallow decision trees called decision stumps (depth-1 trees). Boosting combines many such weak learners sequentially so that together they form a strong, accurate model. Keeping individual learners weak helps control overfitting and lets the ensemble improve gradually.

A decision stump is a decision tree with only one split, i.e., a tree of depth 1 that tests a single feature and produces two leaves. It is a classic weak learner used in boosting algorithms like AdaBoost. On its own it is weak, but many stumps combined can model complex patterns.

A common method sums, for each feature, the total reduction in impurity (e.g., Gini) it produces across all splits in all trees, then normalizes these values. Features that produce large, frequent impurity reductions get higher importance scores. Permutation importance is an alternative that measures the drop in accuracy when a feature's values are shuffled.

rf.fit(X, y)
importances = rf.feature_importances_

A decision tree can be read as a set of clear if-then rules from the root to each leaf, so a human can follow exactly why a prediction was made. The splits are based on understandable feature thresholds, and the tree can be visualized directly. This transparency contrasts with 'black-box' models like deep neural networks.

No, decision trees do not require feature scaling because each split is based on a threshold comparison on a single feature, which is unaffected by the scale or units of the data. Monotonic transformations of a feature do not change the ordering used for splits. This is an advantage over distance- or gradient-based models like KNN or logistic regression.

A decision tree produces axis-aligned, piecewise (rectangular) decision boundaries because each split partitions the space along one feature at a time. This means it can struggle to represent smooth diagonal boundaries efficiently, often approximating them with many staircase-like steps. Ensembles of trees can smooth this out somewhat.

The prediction at a leaf is typically the majority class among the training samples that reached that leaf. The tree can also output class probabilities equal to the fraction of each class in the leaf. New samples are routed through the tree's tests until they land in a leaf, which provides their predicted class.

For classification, a random forest uses majority voting: each tree votes for a class and the most-voted class wins (or probabilities are averaged). For regression, it averages the numeric predictions of all the trees. Aggregating many trees reduces variance and yields more stable predictions than any single tree.

The bias-variance tradeoff describes how model error splits into bias (error from oversimplified assumptions) and variance (error from sensitivity to training data). Bagging (e.g., random forests) mainly reduces variance by averaging diverse models, while boosting mainly reduces bias by sequentially correcting errors. Choosing between them depends on whether a model is underfitting (high bias) or overfitting (high variance).

Because boosting repeatedly focuses on the hardest, often misclassified examples, it can end up fitting noisy or mislabeled points if training continues too long. Bagging averages independent models and does not chase individual errors, so it is more robust to noise. Boosting controls this with a learning rate, limited tree depth, and early stopping.

Tree-building algorithms are greedy: at each node they choose the split that looks best locally (e.g., maximum information gain) without reconsidering earlier choices. This is efficient but does not guarantee a globally optimal tree, since a locally weak split might have led to a better overall structure. Finding the truly optimal tree is computationally infeasible, so greedy heuristics are used.

The class probabilities are p(A) = 0.8 and p(B) = 0.2. Gini = 1 - (0.8² + 0.2²) = 1 - (0.64 + 0.04) = 1 - 0.68 = 0.32. So the node has a Gini impurity of 0.32, indicating it is fairly but not completely pure.

gini = 1 - (0.8**2 + 0.2**2)  # 0.32

Because a tree can split on one feature and then split its children on a different feature, the effect of a feature can depend on the value of another along a path. This captures feature interactions automatically without manually creating interaction terms. It is one reason tree-based models often work well on tabular data with complex relationships.

Stacking trains several different base models on the data and then uses their predictions as inputs to a higher-level 'meta-model' that learns how best to combine them. Unlike bagging or boosting, the base models can be of different types (e.g., a tree, an SVM, and a logistic model). The meta-learner aims to exploit the strengths of each base model for better overall performance.