Decision Tree & Ensemble Learning
Decision Tree
An iterative, top-down construction method that represents a hierarchy of decisions — each internal node tests one feature, and recursion continues until leaf nodes hold class predictions.
All data, no split. The root node holds the entire training set. Its Gini impurity is high — the classes are thoroughly mixed.
Gini Impurity
where is the proportion of class at node . A node with only one class has Gini = 0 (pure). Equal class proportions maximise impurity.
CART selects the feature and threshold that minimise the weighted average impurity of the two resulting child nodes.
▶Python (sklearn)
from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(
criterion='gini', # or 'entropy'
max_depth=3,
min_samples_split=4,
)
clf.fit(X_train, y_train)
print(clf.score(X_test, y_test))Bagging
Bootstrap Aggregating trains k classifiers on independent random subsamples and reduces variance by averaging their predictions.
A single tree is unstable — high variance. Fit the same algorithm on different subsamples and you'll get wildly different boundaries.
Each is trained on a bootstrap sample — N draws with replacement from the training set. Roughly 63% of the original points appear in each bag; the remaining 37% form the out-of-bag (OOB) set, a free internal validation estimate.
Bagging excels when the base learner has high variance (e.g., deep trees). It does not reduce bias — a consistently wrong learner stays wrong.
▶sklearn — BaggingClassifier
from sklearn.ensemble import BaggingClassifier
from sklearn.tree import DecisionTreeClassifier
model = BaggingClassifier(
estimator=DecisionTreeClassifier(max_depth=4),
n_estimators=10,
random_state=42
)
model.fit(X_train, y_train)AdaBoost
Adaptive Boosting trains weak learners sequentially, re-weighting misclassified examples at each round so subsequent learners focus on hard cases.
Start with equal sample weights. Every point matters equally. The first decision stump picks the best single split, ignoring weights.
Each round trains a stump on the current weight distribution. Its vote weight is , where is the weighted error. Weights are then updated: misclassified samples are multiplied by , correct ones by .
AdaBoost reduces both bias and variance. It is sensitive to noisy labels — outliers repeatedly gain weight and can dominate later rounds.
▶sklearn — AdaBoostClassifier
from sklearn.ensemble import AdaBoostClassifier
model = AdaBoostClassifier(
n_estimators=50,
learning_rate=1.0,
random_state=42
)
model.fit(X_train, y_train)Gradient Boosting
Generalises boosting to any differentiable loss function by fitting each new tree to the negative gradient of the loss — the direction of steepest descent.
Start with a constant prediction (log-odds). f₀ is set to the log-odds of the positive class — the best constant prediction under log-loss.
At each stage , the residuals are computed and a new weak learner is fit to them. The learning rate shrinks each step, trading convergence speed for better generalisation.
For log-loss (binary classification), the residual simplifies to where is the sigmoid. XGBoost and LightGBM are optimised implementations of this framework.
▶sklearn — GradientBoostingClassifier
from sklearn.ensemble import GradientBoostingClassifier
model = GradientBoostingClassifier(
n_estimators=100,
learning_rate=0.1,
max_depth=3,
random_state=42
)
model.fit(X_train, y_train)Random Forest
Extends bagging with random feature subsampling at each split, de-correlating trees so their errors cancel more effectively.
Bagging reduces variance. Multiple trees each see a bootstrap sample. But trees on correlated features tend to look similar, limiting the benefit.
At every split, only features are considered — typically for classification. This forces diversity: even if one feature is strongly predictive, different trees may use different features, so their errors are less correlated.
The OOB error — computed on the ~37% of points excluded from each tree's bootstrap sample — is an unbiased estimate of generalisation error without any dedicated validation set.
3D view:Decision tree boundary as a stepped surface. Each column's height and color reflects its predicted class (blue = 1, orange = 0). The steps reveal the axis-aligned, piecewise structure of tree decisions. Drag to orbit.
▶sklearn — RandomForestClassifier
from sklearn.ensemble import RandomForestClassifier
model = RandomForestClassifier(
n_estimators=100,
max_features='sqrt', # m ≈ √p
random_state=42
)
model.fit(X_train, y_train)
print('OOB score:', model.oob_score_)Stacking
Stacked generalisation trains a meta-learner on the outputs of diverse base classifiers, learning which models to trust in which regions of the input space.
Train diverse base learners on the same data. Trees of different depths learn different aspects of the boundary — deliberately using diverse models.
Base learners are trained on the full (or split) training data. Their predictions form a new feature vector that is fed to the meta-learner . To avoid leakage, base predictions for the meta-training set are ideally produced via cross-validation (out-of-fold predictions).
Stacking works best when base learners are diverse — using different algorithms, hyperparameters, or feature subsets. The meta-learner need not be complex; logistic regression is often sufficient.
▶sklearn — StackingClassifier
from sklearn.ensemble import StackingClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.linear_model import LogisticRegression
estimators = [
('dt_deep', DecisionTreeClassifier(max_depth=4)),
('dt_shallow', DecisionTreeClassifier(max_depth=2)),
]
model = StackingClassifier(
estimators=estimators,
final_estimator=LogisticRegression()
)
model.fit(X_train, y_train)