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
- Fix the evaluation design before tuning anything. Use time-based splits for data with a natural order, such as weekly retail footfall or monthly bill data, and stratify only when the target genuinely has no timeline.
- Cap depth and demand minimum leaves. A depth of three to six and a leaf size of 20 to 50 samples is a sensible starting point, then let cross-validation adjust it rather than intuition alone.
- Prune explicitly instead of relying on defaults. Walk the cost-complexity path, choose an alpha where validation error flattens, and record the number of nodes before and after.
- Audit the printed tree line by line. Confirm that every split corresponds to a concept a domain expert recognises, and remove features that leak identifiers or information unavailable at scoring time.
- Treat impurity-based importances as a starting point. Compare them with permutation importance and with the business cost of each error, which for a bank is rarely a symmetrical mistake.
- Document the data lineage and retention story. Record where each field came from, how fresh it is and who can access it, so your model documentation already satisfies much of what Privacy Act and OAIC expectations require.
- Re-run validation on a schedule. Australian customers move between insurers, retailers and telco plans constantly, so a tree validated once in June can quietly degrade by the time a summer campaign starts.
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.