🌲 Decision Tree — CART & Gini Impurity
Build and visualise a CART decision tree step-by-step. Watch the algorithm minimise Gini impurity G = 1−Σpᵢ² at each split, see the decision boundary emerge, and compare tree depth vs accuracy trade-off.
Starting…
Generating dataset. The CART algorithm finds axis-aligned splits that minimise Gini impurity at each node. Nodes are revealed one by one.
The Physics
CART split criterion: Gini(S) = 1 − Σᵢ pᵢ². Best split minimises weighted child impurity: ΔGini = Gini(parent) − (|L|/|S|)·Gini(L) − (|R|/|S|)·Gini(R). Tree grows until max_depth or min_samples_leaf. Pruning via cost-complexity α·|leaves|. Feature importance = total Gini reduction attributed to each feature across all splits.
About Decision Tree — CART & Gini Impurity
This simulation models the CART (Classification and Regression Trees) algorithm, which builds a binary tree by recursively splitting a dataset with axis-aligned thresholds chosen to minimise Gini impurity (G = 1 − Σpᵢ²) at each node. You can watch the decision boundary emerge split by split on a scatter plot, while the growing tree diagram shows each node's split rule, Gini value, and sample count — making the greedy recursive partitioning process visually transparent.
Decision trees underpin many real-world systems, from medical diagnosis triage tools and credit-risk scoring to spam filters. The CART algorithm, introduced by Breiman et al. in 1984, later became the building block for ensemble methods such as random forests and gradient-boosted trees that dominate structured-data machine learning today.
Frequently Asked Questions
What is Gini impurity and why does CART minimise it?
Gini impurity G = 1 − Σpᵢ² measures how often a randomly chosen sample from a node would be misclassified if labelled according to the class distribution at that node. A perfectly pure node (all one class) has G = 0, while a 50/50 binary split reaches the maximum of 0.5. CART chooses the split that gives the largest weighted reduction in Gini across the two child nodes because it is computationally cheap (no logarithm) and correlates closely with the theoretically ideal entropy criterion.
How do the simulation controls change the tree?
Max Depth (1–6) caps how many levels the tree can grow: deeper trees carve finer regions and reach higher training accuracy but risk overfitting. Min Samples Leaf (1–20) blocks any split that would leave fewer than that many points in a child, keeping leaves statistically meaningful. Sample Points (40–200) sets the dataset size. Use Pause/Play to step through the node-by-node reveal and watch the decision boundary form; hit Reset to regenerate with the current settings.
Why does the XOR pattern need more depth than the Linear Separation pattern?
Decision trees only make axis-aligned cuts, so the boundary between classes must be approximated by a series of rectangles. The XOR dataset has no single useful horizontal or vertical split near the root — the classes interleave in all four quadrants — so the tree needs at least depth 2 just to begin separating them. Linear Separation, by contrast, can be captured reasonably well with a single diagonal approximated by just one or two axis-aligned splits, leading to a shallower, simpler tree.
What is the mathematical formula behind the best-split search?
For a candidate split dividing parent set S into left child L and right child R, the information gain is ΔGini = Gini(S) − (|L|/|S|) · Gini(L) − (|R|/|S|) · Gini(R). CART evaluates every midpoint between consecutive sorted feature values for each feature and picks the (feature, threshold) pair with the maximum ΔGini. Feature importance is the sum of Gini reductions weighted by node sample counts across all splits on a given feature, normalised so all features sum to 1.
How are decision trees used in real-world applications?
Decision trees appear in medical triage (e.g., scoring sepsis risk from vital signs), credit scoring (loan default probability), fraud detection, and customer churn prediction. A single shallow tree is often used as an interpretable baseline because each decision path can be expressed as a plain-English rule such as "if income > 40,000 and debt ratio < 0.3, approve." Deeper trees and ensembles (random forests, XGBoost) trade this transparency for higher accuracy on complex datasets.
What is the common misconception about decision trees and overfitting?
A frequent misconception is that a deeper tree is always better because it achieves 100% training accuracy. In reality, an unconstrained tree memorises noise in the training data and generalises poorly to new samples — this is overfitting. The fix is regularisation: limiting max depth, requiring a minimum number of samples per leaf, or applying cost-complexity pruning (alpha · |leaves|) to penalise complexity. Cross-validation is used to choose these hyperparameters.
Who invented CART and when was it introduced?
The CART algorithm was introduced in 1984 by Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone in their book "Classification and Regression Trees." Breiman later built on CART to develop bagging (1996) and random forests (2001), while Friedman extended it to gradient boosting (1999–2001). These three methods collectively transformed machine learning on tabular data and remain widely used decades later.
How do decision trees relate to random forests and gradient boosting?
A random forest trains hundreds of CART trees on bootstrap samples of the data, each considering a random subset of features at every split, then averages their predictions. This reduces variance without significantly increasing bias. Gradient boosting instead trains trees sequentially, each one fitting the residual errors of the ensemble so far, which reduces bias. Both methods inherit the interpretability of individual splits but are far more accurate on complex datasets than any single tree.
Can decision trees handle regression as well as classification?
Yes — that is the R in CART. For regression, each leaf predicts the mean of the target values of the samples it contains, and splits are chosen to minimise the sum of squared residuals rather than Gini impurity. The tree diagram and recursive partitioning logic are identical; only the leaf prediction and split criterion change. This simulation focuses on binary classification, but the same algorithm with MSE as the criterion produces regression trees used in housing-price and demand-forecasting models.
What are current research directions for improving decision trees?
Active research areas include differentiable (soft) decision trees that can be trained end-to-end with gradient descent and embedded in neural networks, oblique trees that use linear combinations of features rather than axis-aligned splits to capture diagonal boundaries more efficiently, and causal trees that estimate heterogeneous treatment effects in randomised experiments. Interpretability research also focuses on post-hoc explanation methods (SHAP values) that decompose any tree ensemble's prediction into per-feature contributions.