๐ณ Decision Tree Philosophy
๐ฏ Hierarchical, Interpretable Learning
Decision Trees are non-parametric supervised learning algorithms that partition the feature space into regions using a series of if-then-else rules. They are highly interpretable and form the foundation of ensemble methods like Random Forest and Gradient Boosting.
Why Trees?
White-box model โ the entire decision path can be visualized and understood. Trees naturally handle mixed data types, are robust to outliers, and require minimal preprocessing. However, they are prone to overfitting without proper pruning.
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
iris = load_iris()
dt = DecisionTreeClassifier(max_depth=3, random_state=42)
dt.fit(iris.data, iris.target)
plt.figure(figsize=(12,8))
plot_tree(dt, feature_names=iris.feature_names, class_names=iris.target_names, filled=True)
plt.title("Decision Tree Visualization")
plt.show()โ๏ธ Splitting Criteria
๐ฏ Choosing the Best Split
Classification: Gini Impurity, Entropy (Information Gain). Regression: MSE (Variance Reduction), MAE.
Split Selection Process
At each node, the algorithm evaluates all possible splits for all features and selects the one that maximizes purity (classification) or minimizes variance (regression).
from sklearn.tree import DecisionTreeClassifier
# Gini (default)
dt_gini = DecisionTreeClassifier(criterion='gini')
# Entropy
dt_entropy = DecisionTreeClassifier(criterion='entropy')
# For regression
from sklearn.tree import DecisionTreeRegressor
dt_mse = DecisionTreeRegressor(criterion='squared_error')๐ Gini Impurity Deep Dive
๐ฏ Measure of Node Impurity
Gini = 1 - ฮฃ p_iยฒ. Ranges from 0 (pure) to 0.5 (max impurity for binary).
Computational Efficiency
Gini is computationally cheaper than entropy (no logarithms) and often yields similar results. It measures how often a randomly chosen element would be incorrectly classified.
import numpy as np
def gini(p):
return 1 - np.sum(p**2)
# Pure node
print(f"Gini [1,0]: {gini([1,0]):.3f}")
# Impure node
print(f"Gini [0.5,0.5]: {gini([0.5,0.5]):.3f}")๐ Entropy & Information Gain
๐ฏ Entropy = -ฮฃ p_i logโ(p_i)
Information Gain = Entropy(parent) - ฮฃ (weighted) Entropy(child).
Information Theory Perspective
Entropy measures uncertainty. Information Gain is the reduction in uncertainty after a split โ higher is better.
from scipy.stats import entropy
def entropy_p(p):
return -np.sum(p * np.log2(p + 1e-9))
print(f"Entropy [0.5,0.5]: {entropy_p([0.5,0.5]):.3f}")
# Information Gain
parent_entropy = entropy_p([0.5,0.5])
child1_entropy = entropy_p([0.9,0.1])
child2_entropy = entropy_p([0.1,0.9])
info_gain = parent_entropy - 0.5*child1_entropy - 0.5*child2_entropy
print(f"Info Gain: {info_gain:.3f}")๐ MSE & Variance Reduction
๐ฏ Regression Trees
Split minimizes MSE = ฮฃ (yแตข - ศณ)ยฒ. Choose split that maximizes variance reduction.
Continuous Target
Each leaf predicts the mean of training instances in that region. MSE splits ensure homogeneous leaves.
from sklearn.tree import DecisionTreeRegressor
X_reg = np.random.rand(100, 1) * 10
y_reg = np.sin(X_reg).ravel() + np.random.normal(0, 0.1, 100)
dt_reg = DecisionTreeRegressor(max_depth=4)
dt_reg.fit(X_reg, y_reg)
print(f"Rยฒ: {dt_reg.score(X_reg, y_reg):.3f}")โ๏ธ Pruning & Overfitting Control
๐ฏ Reduce Complexity
Cost-complexity pruning (ccp_alpha), pre-pruning (max_depth, min_samples_split).
Pruning Strategies
Pre-pruning stops growth early. Post-pruning grows full tree then removes branches with little predictive power.
# Cost-complexity pruning
path = dt.cost_complexity_pruning_path(X, y)
ccp_alphas = path.ccp_alphas
pruned_trees = []
for alpha in ccp_alphas:
dt_pruned = DecisionTreeClassifier(ccp_alpha=alpha)
dt_pruned.fit(X, y)
pruned_trees.append(dt_pruned)โ๏ธ Hyperparameters
๐ฏ Key Tuning Parameters
max_depth, min_samples_split, min_samples_leaf, max_features, ccp_alpha.
Tuning for Generalization
Shallow trees (small max_depth) reduce overfitting. min_samples_split prevents splits on small subsets.
dt_tuned = DecisionTreeClassifier(
max_depth=5,
min_samples_split=10,
min_samples_leaf=5,
max_features='sqrt',
ccp_alpha=0.01
)
dt_tuned.fit(X, y)๐ท๏ธ Classification Trees
๐ฏ Majority Class in Leaves
Each leaf predicts the most frequent class among training points.
Decision Boundaries
Axis-aligned splits create rectangular decision regions.
from sklearn.datasets import make_classification
X_clf, y_clf = make_classification(n_samples=200, n_features=2, n_redundant=0, random_state=42)
dt_clf = DecisionTreeClassifier(max_depth=4)
dt_clf.fit(X_clf, y_clf)
print(f"Accuracy: {dt_clf.score(X_clf, y_clf):.3f}")๐ Regression Trees
๐ฏ Average Target in Leaves
Each leaf predicts the mean (or median) of target values.
Piecewise Constant
The model approximates the function with step functions โ interpretable but not smooth.
from sklearn.tree import DecisionTreeRegressor
dt_reg2 = DecisionTreeRegressor(max_depth=3)
dt_reg2.fit(X_reg, y_reg)
# Predictions are constant within each leaf๐ Feature Importance
๐ฏ Gini / MSE Reduction
Importance = total reduction in impurity from splits on that feature.
Interpreting Importance
High importance features are those that provide the most discriminative power.
importances = dt.feature_importances_
for name, imp in zip(iris.feature_names, importances):
print(f"{name}: {imp:.3f}")๐งฉ Handling Missing Values
๐ฏ Surrogate Splits
Decision trees handle missing values via surrogate splits.
Surrogate Mechanism
If the primary split feature is missing, use the next best alternative split.
# sklearn supports missing values in recent versions
# DecisionTreeClassifier(splitter='best') can handle NaN๐ท๏ธ Categorical Features
๐ฏ Native Support in sklearn
DecisionTreeClassifier supports categorical features via the 'categorical_features' parameter in HistGradientBoosting, but standard tree requires encoding.
Encoding Strategies
One-hot encoding or ordinal encoding. Trees can handle high cardinality with ordinal encoding.
from sklearn.preprocessing import OneHotEncoder
# Example: encode categorical features before treeโ๏ธ sklearn API & Pipelines
๐ฏ DecisionTreeClassifier, DecisionTreeRegressor
Unified API, GridSearchCV, Pipelines.
Production Setup
Combine preprocessing and tree in a Pipeline with hyperparameter tuning.
from sklearn.pipeline import Pipeline
pipe = Pipeline([('scaler', StandardScaler()), ('dt', DecisionTreeClassifier())])
params = {'dt__max_depth': [3,5,7,10]}
grid = GridSearchCV(pipe, params, cv=5)
grid.fit(X, y)
print(f"Best params: {grid.best_params_}")๐ Ensemble Foundations (Random Forest)
๐ฏ Building Blocks for Ensembles
Decision trees are the base learners for Random Forest, Gradient Boosting, and XGBoost.
Why Ensemble?
Combining multiple trees reduces variance (bagging) or bias (boosting). Trees are perfect candidates because they are high-variance, low-bias learners.
from sklearn.ensemble import RandomForestClassifier
rf = RandomForestClassifier(n_estimators=100, max_depth=5)
rf.fit(X, y)
print(f"RF Accuracy: {rf.score(X, y):.3f}")