How do Decision Trees work in machine learning?
A Decision Tree is a supervised machine-learning model that makes predictions by repeatedly splitting data into smaller subsets according to feature thresholds. It solves classification and regression problems with an interpretable, if sometimes high-variance, structure of rules. Its main trade-off is explainability versus overfitting: shallow trees are easy to understand, while unrestricted trees can memorize training data.
Read full answerHide full answer
Applies toscikit-learn 1.5+ (Python 3.12)
How It Works
A decision tree is built using CART, a greedy recursive algorithm:
-
A node examines candidate feature thresholds.
-
It selects the split that produces the greatest reduction in impurity.
-
The data are divided, and the process repeats for each child node.
-
A node becomes a leaf when stopping criteria are met.
-
Leaves store a class prediction or an estimated target value.
For classification, CART uses impurity at a node and information gain to choose a split:
-
Gini impurity:
Gini = 1 - sum(p_k^2) -
Entropy:
Entropy = -sum(p_k * log2(p_k)) -
Information gain:
Information Gain = Impurity(parent) - sum((n_child / n_parent) * Impurity(child))
Here, p_k is the proportion of samples in class k at a node, and log2 is the base-2 logarithm. In the information-gain formula, n_parent is the number of samples at the parent node, n_child is the number at one child node, and the sum runs over the children. Each child’s impurity is weighted by its proportion of the parent’s samples. Information gain measures how much a split reduces impurity.
For regression, CART usually measures the reduction in variance, equivalent to reduction in squared error:
Variance = (1 / n) * sum((y - y_mean)^2)
In this formula, n is the number of samples, y is an observed target, and y_mean is the target mean at the node.
The splits are axis-aligned, meaning each internal node tests one feature against one threshold. This naturally captures nonlinear relationships and feature interactions without requiring feature scaling.
Stopping and Pruning
Scikit-learn provides several ways to control tree size:
-
max_depth: Limits the maximum number of edges from the root to a leaf. -
min_samples_split: Requires enough samples before a node can be split. -
min_samples_leaf: Requires each resulting leaf to contain a minimum number of samples. -
max_leaf_nodes: Limits the total number of leaves. -
ccp_alpha: Applies cost-complexity pruning by penalizing complicated trees.
cost_complexity_pruning_path can identify useful ccp_alpha values for a fitted tree. Good pruning preserves predictive structure while removing branches that merely fit noise.
Prediction and Feature Importance
A prediction follows the feature thresholds from the root to a leaf. Classification leaves predict a class; regression leaves usually predict the mean target of their training samples.
feature_importances_ measures the total reduction in impurity contributed by each feature. It is useful for interpretation, but can be biased toward high-cardinality features. permutation_importance provides an alternative that evaluates features by measuring the effect of shuffling them on validation performance.
Strengths and Limitations
| Aspect | Strengths | Limitations |
|---|---|---|
| Interpretability | Rules and leaf predictions are easy to explain and visualize | Deep trees can become difficult to read |
| Features | Handles nonlinear relationships and interactions | Uses axis-aligned rectangular regions |
| Preprocessing | Does not require feature scaling | Missing-value behavior depends on the splitter and configuration |
| Categories | Can work with encoded categorical features | Categories generally require encoding in many workflows |
| Stability | Deterministic when random_state and data order are fixed |
Small data changes can produce a different tree |
| Generalization | Pruning and constraints can control complexity | Unrestricted trees have high variance and may overfit |
| Ensembles | Forms the basis of random forests and gradient boosting | A single tree may be weaker than an ensemble |
Scikit-learn trees have supported native missing-value handling since version 1.3 for supported splitters, but missing-value policies and results should still be validated.
Code Example
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score, confusion_matrix
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text
X, y = load_iris(return_X_y=True)
# Split before fitting the tree to avoid evaluating on training data.
X_train, X_test, y_train, y_test = train_test_split(
X,
y,
test_size=0.25,
random_state=42,
stratify=y,
)
tree = DecisionTreeClassifier(random_state=42)
tree.fit(X_train, y_train)
y_pred = tree.predict(X_test)
print("Test accuracy:", accuracy_score(y_test, y_pred))
print("Confusion matrix:\n", confusion_matrix(y_test, y_pred))
print("\nLearned rules:")
print(export_text(tree, feature_names=load_iris().feature_names))
print("\nImpurity-based feature importance:")
for feature, importance in zip(load_iris().feature_names, tree.feature_importances_):
print(f"{feature}: {importance:.3f}")
Prediction after training takes approximately O(depth) time per sample, while tree storage is proportional to the number of nodes. Exact training cost depends on the implementation, feature count, candidate thresholds, and tree size.
Common Pitfalls
-
Overfitting: An unrestricted tree can memorize training data. Compare
max_depth,min_samples_leaf, and cost-complexity pruning using cross-validation. -
Data leakage: Fit the tree only on training data. Any encoding, imputation, feature selection, or resampling must also occur within the training process.
-
Wrong metric: Accuracy can be misleading with imbalanced classes; also examine precision, recall, F1, ROC-AUC, and PR-AUC.
-
Misreading importance:
feature_importances_is impurity-based and may favor features with many possible split values. Prefer permutation importance when appropriate. -
Excessive validation reuse: Do not repeatedly tune against the same test set; use
StratifiedKFoldcross-validation and reserve the test set for final evaluation. -
Ignoring ensembles: A single tree is high variance. Random forests reduce variance through bagging and feature randomization, while gradient boosting builds trees sequentially to reduce errors.