Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Understanding CART: The Splits Behind Every Decision Tree

A decision tree looks deceptively simple: a question at the top, a rule for each branch, and a leaf that hands back a class or a number. CART — Classification and Regression Trees — is the algorithm behind most of the trees you meet in practice, including scikit-learn's DecisionTreeClassifier and DecisionTreeRegressor. Published by Leo Breiman, Jerome Friedman, Charles Olshen and Robert Sibbetan in 1984, it grew out of statistical learning research and became a workhorse for credit scoring, customer churn analysis, quality control and exploratory data analysis.

The mechanics are worth understanding, because a tree that looks reasonable on paper can quietly overfit, split on a meaningless variable, or produce rules nobody can defend to a compliance team. This walkthrough covers how CART selects splits, what the impurity maths is doing, why the algorithm insists on binary divisions, how pruning keeps trees honest, and how the whole workflow fits into Australian datasets, businesses and legal expectations. If you are comfortable with basic Python and want pseudocode, complexity notes and implementation guidance, the same community that publishes these tutorials keeps a growing library of material on the hello ML site for when a single algorithm is not enough.

Where CART Sits Among Tree-Based Learners

CART builds a tree greedily and recursively. The algorithm starts at the root with every training row, then scans each candidate feature and threshold to find the division that reduces impurity the most. It commits to that split, sends the rows down the two resulting branches, and repeats the process until a stopping rule fires or the data runs out. Because it never reconsiders an earlier decision, each node is locally optimal rather than the whole tree being globally optimal across every possible structure.

That single design choice explains both the appeal and the limitations. Greedy trees train quickly, handle mixed feature types after encoding, and produce rules you can print and read aloud to a risk committee. They are also high variance: change a few rows and the structure can shift dramatically, which is why random forests wrap dozens of CART trees inside bootstrap samples to cancel that instability out.

Several related learners share the same tree-shaped intuition but differ in how they search for splits, so it helps to set CART beside its closest relatives.

Algorithm Split criterion Split shape Regularisation Typical use
CART Gini index (classification), variance (regression) Always binary Cost-complexity pruning Interpretable standalone models
ID3 Information gain Multi-way, native categoricals None by default Small categorical datasets
C4.5 Gain ratio Multi-way Error-based pruning Mixed data with missing values
Random forest CART variants Binary, hundreds of trees Depth limits, feature sampling Accuracy over interpretability
Gradient boosting Shallow CART variants Binary, one tree at a time Learning rate, shrinkage, penalties Structured-data prediction contests

Gini Impurity and the Arithmetic of a Split

Impurity measures how mixed a set of rows is with respect to the target. For a node holding samples from classes with proportions $p_1, p_2, \dots, p_K$, the Gini index is

$$G(t) = 1 - \sum_{i=1}^{K} p_i^2$$

A pure node, where every row belongs to one class, scores zero. A node holding 50/50 classes scores 0.5, the worst case. CART evaluates a candidate split by comparing the parent's impurity against the impurity of the two children, weighted by how many samples each child receives:

$$\Delta G = G(t) - \frac{n_L}{n}G(L) - \frac{n_R}{n}G(R)$$

The threshold with the largest $\Delta G$ wins.

A concrete example from a retail bank dataset: suppose 1,000 customers sit at the root and 420 of them default. A split on "holds a credit card with us" separates 250 rows with 180 defaults from 750 rows with 240 defaults. The parent Gini is $1 - 0.42^2 - 0.58^2 = 0.4876$. The left child has Gini $1 - 0.72^2 - 0.28^2 = 0.4032$, the right child $1 - 0.32^2 - 0.68^2 = 0.4352$, and the weighted result is $0.25(0.4032) + 0.75(0.4352) = 0.4272$. The improvement is 0.0604, which beats every other threshold scanned on that feature.

The scanning itself is efficient. Rather than trying every possible threshold, CART sorts each feature once and walks the sorted values, updating class counts incrementally. Sklearn's default criterion="gini" uses exactly this; swapping to "entropy" enables the information-gain alternative, which is more sensitive to balanced splits and tends to grow slightly different trees on the same data.

Binary Splits, Thresholds and Multi-Class Labels

CART never creates more than two branches at a node, even when the target has a dozen classes. Multi-class problems are handled by tracking a probability vector over all classes at each leaf, and the impurity calculation still evaluates binary feature thresholds. This keeps the search space small and makes every rule readable as "if condition, then ... otherwise ...".

Continuous features are handled with threshold splits of the form $x_j \le t$, and CART evaluates every midpoint between adjacent sorted values. Categorical features need care. Scikit-learn expects numeric input, so a column like "preferred contact method" is usually one-hot encoded, producing one binary comparison per dummy variable. Ordinal encoding also works, but it imposes an order the tree may exploit in ways that look arbitrary to the business reading the output — for instance, a rule that treats a post code band as "less than 9800" carries no real meaning.

Australian data makes this visible constantly. A churn model for a mobile plan might split on "monthly bill" at a threshold that only makes sense once you remember the $5-a-month difference between a prepaid data top-up and a post-paid plan. A delivery model for Woolworths or Coles might key on "distance to store" in a way that quietly encodes whether a customer lives in inner Melbourne or a fringe growth area like Tarneit. When you encode, check that the thresholds you produce match how a colleague would describe the customer.

Growing the Tree and Cutting It Back

A tree that keeps splitting will eventually memorise its training data. Left unconstrained, CART grows until every leaf is pure, which means the model reproduces the sample it was given rather than the pattern in the population. The standard counters are stopping conditions: max_depth limits how deep the tree may go, min_samples_split blocks a node with too few rows, min_samples_leaf requires each leaf to hold a minimum number of samples, and min_impurity_decrease refuses splits that gain almost nothing.

The second line of defence is pruning after growth. Cost-complexity pruning adds a penalty $\alpha$ per leaf, minimising $R_\alpha(T) = R(T) + \alpha |T|$ where $R(T)$ measures misclassification or squared error. Raising $\alpha$ collapses the least valuable branches; scikit-learn exposes this as ccp_alpha and through cost_complexity_pruning_path, which reports the effective alpha at every pruning step.

Validation design matters as much as the pruning parameter. For weekly footfall at a Coles or Woolies, a random split leaks the future into the past, so use time-based folds and train on earlier weeks to predict later ones. For a classification target like "churned within 90 days", the label window also has to sit entirely after the prediction date. A five-fold cross-validated depth, chosen on Australian data and then applied to the same population, tends to hold up well with a bank like CBA or an insurer underwriting a home policy.

A Python Workflow You Can Reuse

The scikit-learn API wraps the recursion in a single estimator, but the sequence underneath stays the same: fit, inspect the structure, prune, then evaluate on untouched data.

from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.model_selection import train_test_split, cross_val_score

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, stratify=y, random_state=42
)

tree = DecisionTreeClassifier(
    criterion="gini", max_depth=5, min_samples_leaf=20, random_state=0
)
tree.fit(X_train, y_train)

print(export_text(tree, feature_names=list(X.columns)))
print(cross_val_score(tree, X_train, y_train, cv=5).mean())

path = tree.cost_complexity_pruning_path(X_train, y_train)
pruned = DecisionTreeClassifier(random_state=0, ccp_alpha=0.01)
pruned.fit(X_train, y_train)

Read the printed tree before trusting the accuracy score. A branch splitting on a customer reference number or a random identifier is a warning sign. Keep in mind that feature_importances_ reflects impurity reduction, so continuous variables with many distinct values accumulate importance more easily than equally informative categories; permutation importance on the validation set is the fairer comparison. When the model is ready to be used, exposing it through a small endpoint or a dashboard means moving into application work, and the web development guides cover how to serve predictions without turning your analysis script into an unmaintainable piece of infrastructure.

CART in Australian Businesses and Regulation

Tree models appear in ordinary Australian commercial settings more often than most people realise. Banks including Commonwealth Bank, ANZ, NAB and Westpac use interpretable branches to support credit and marketing decisions, where a reason code matters when a customer disputes an outcome through the credit reporting process run by AFCA. Telstra and Optus run churn models over prepaid and post-paid subscribers. Retailers such as Woolworths Group, Coles and Aldi model basket size and store-level demand. Insurers and public hospitals use similar trees to triage claims and triage lists.

Regulation shapes how far a tree can go without explanation. The Privacy Act 1988 (Cth) and the Australian Privacy Principles require transparency about how personal information is handled, and the Notifiable Data Breaches regime applies once significant harm is likely. The Office of the Australian Information Commissioner has published guidance on automated decision-making, expecting people to be told when a model drives a decision about them. Melbourne hospitals operate under the Victorian Health Records Act 2001 rather than relying only on federal law, and clinical triage models that influence care decisions attract scrutiny from the TGA as medical device software. The Australian Consumer Law also constrains how outcomes are represented to consumers, particularly around deceptive marketing claims and terms applied to small business contracts.

Those pressures make CART's readability a practical asset rather than a nicety. A shallow tree with three or four rules can be shown to a customer, a regulator or an internal audit committee; a 400-node ensemble cannot. Model risk reviews in Australian financial institutions typically expect validation evidence, stability analysis across quarters and a record of the data lineage behind every input feature.

Recommendations for Building CART Models That Hold Up

CART rewards discipline: clear splits, honest stopping rules, careful pruning and documentation that survives an audit. Master the impurity maths and the recursion, and a single tree becomes a dependable first model or a readable component inside a much larger ensemble.