MerQuR+Statistics Glossary

Statistics Glossary → Decision Tree (CART)

Decision Tree (CART)analysis

A classification and regression method that splits the data in two again and again with 'yes/no' questions, ending in subgroups that each give a single prediction, and presents the result as easily read decision rules.

Concept

To predict an outcome, a decision tree asks questions such as 'is age above 35?' or 'is income below 20,000?' and divides the data into two subgroups with each answer. The splits are chosen so that each subgroup is as homogeneous (pure) as possible with respect to the outcome. The resulting model is a set of rules that can be drawn on paper and explained to a non-specialist, which is why it is widely used in clinical, administrative and agricultural decisions where interpretability matters.

At each step all variables and all possible cut points are tried, and the split that most reduces the node's impurity is chosen. In classification impurity is usually measured by the Gini index: G = 1 − Σ p_k² (p_k is the proportion of class k in the node); a node containing a single class has G = 0. In a regression tree the criterion is the sum of squares, and each leaf predicts the mean of its observations. If splitting were never stopped, the tree would grow until every observation had its own leaf; therefore a large tree is grown first and then pruned back with a complexity penalty chosen by cross-validation.

Trees need no distributional assumptions, pick up interactions on their own and can handle missing values through surrogate splits. They are, however, unstable: a small change in the data can greatly alter the structure of the tree, and step-shaped predictions reflect continuous relationships only coarsely. In small samples the rules depend heavily on chance; the generalisation of the pruned tree should be checked with cross-validation and a test set.

When to use it

  • When, besides prediction, clear decision rules that can be applied directly in practice are needed (triage, credit approval, species identification keys).
  • If predictive accuracy matters more than interpretability, random forest or gradient boosting, which combine many trees, are preferred.
  • If the size of effects must be reported with coefficients and confidence intervals, logistic or linear regression is used.

An everyday example

A bank branch wants to predict whether loan applicants will have repayment problems. The decision tree first asks 'does more than half of monthly income go on debt repayments?'; if the answer is 'yes', the second question is 'has the applicant been in the current job for less than 2 years?'. If most applicants answering 'yes' to both questions ran into problems, the tree labels this branch 'high risk'. In the end the branch staff have a list of rules three or four steps long that they can apply without a computer.

Parameters in MerQur

Task (Classification / Regression)

Concept: If the outcome is a category, a classification tree is built and each leaf gives the most likely class (and the class proportions); if the outcome is numeric, a regression tree is built and each leaf predicts the mean of its observations.

Everyday example: If the bank asks 'will there be a problem or not?', it builds a classification tree. If it asks 'how many days late will this customer pay?', it builds a regression tree and each leaf gives the average number of days late.

What it does: A classification tree (rpart method = "class") or a regression tree ("anova").

Effect on the result: The splitting criterion (Gini/entropy or sum of squares), the node prediction and the reported metrics.

On the validation data: car.test.frame Mileage ~ Weight full data: 4 leaves, cptable CP 0.595349, 0.134528, 0.012828, 0.01, rel error 1, 0.40465, 0.27012, 0.25729, root error 22.576.

Splitting criterion (Gini / Entropy)

Concept: Measures how 'mixed' a node is. The Gini index is the probability that two observations drawn at random from the node belong to different classes; entropy measures the class uncertainty in the node in information-theoretic terms. In practice the two usually choose similar splits.

Everyday example: A group in which half the applicants ran into problems is as mixed as it gets; a group where all or none did is completely pure. With each question, the tree tries to bring the groups closer to this pure state.

What it does: The node impurity measure in classification.

Effect on the result: The selected splits and the improvement values.

On the validation data: kyphosis (test 0.2) Gini and entropy built the same tree (4 leaves, accuracy 0.7647); kyphosis full data, entropy and equal priors: 4 leaves, importance Start 15.84, Age 9.57, Number 2.13.

→ Node impurity (Gini, entropy)

Complexity parameter (cp)

Concept: The complexity parameter is a 'price' paid for each leaf added to the tree: a split that does not reduce the error by more than this price is not kept. A large cp gives small, simple trees; a small cp large, detailed ones.

Everyday example: With a large cp the bank adds only questions that make a real difference and ends up with a two- or three-question list. With a very small cp, dozens of small questions are added just to sort a few applications correctly.

What it does: Splits that do not reduce the relative risk by at least cp are pruned.

Effect on the result: A large cp gives a smaller tree, a small cp a larger tree; the number of leaves, test performance and variable importance change.

On the validation data: kyphosis full data cp 0.01: 5 leaves, accuracy 0.8395; cp 0.05: 2 leaves, 0.8272. In the training set cp 0.2: root only (accuracy 0.7647 = majority proportion). Even at cp = 0, splits that do not reduce the misclassification risk are pruned (maxdepth 3, cp 0: 2 leaves).

→ Tree pruning and the complexity parameter (cp)

Pruning (Given cp / Minimum CV error / 1-SE rule)

Concept: Pruning cuts unnecessary branches off a large tree. The size at which to stop can be chosen from the cross-validation error: 'minimum CV error' picks the tree with the lowest error, while the '1-SE rule' picks the smallest tree whose error is within one standard error of the lowest.

Everyday example: If the five-question tree has an error of 0.40 and the two-question tree 0.42, and this difference lies within the measurement uncertainty, the 1-SE rule picks the two-question tree. For branch staff a shorter rule list with almost the same success is more useful.

What it does: Pruning at the given cp; the cp of the row with the smallest xerror ("min"); the smallest tree with xerror <= smallest xerror + xstd ("1se"). Requires xval >= 2.

Effect on the result: The size of the final tree is selected from the cptable; the "min" and "1se" rules can lead to smaller trees.

On the validation data: kyphosis full data cp 0 and min or 1se: selected cp 0.1765, root only (xerror did not fall below 1 in any row). Pima full data cp 0 and 1se: cp 0.01471, 5 leaves, training accuracy 0.835.

→ Tree pruning and the complexity parameter (cp)

Minimum node size to split (minsplit) and Minimum leaf size (minbucket)

Concept: Sets the minimum number of observations a node must contain to be considered for splitting (minsplit) and the minimum number left in each leaf (minbucket). These limits prevent unreliable rules based on a handful of observations.

Everyday example: If each leaf must contain at least 10 applications, the tree cannot produce rules based on a couple of applicants, such as 'two people of this occupation, this age, living in this district'.

What it does: The minimum number of observations in a node required to try a split; the minimum number of observations in a leaf (0 = automatic round(minsplit/3)).

Effect on the result: Large values restrict splitting and shrink the tree; small values give large trees prone to overfitting.

On the validation data: kyphosis full data minsplit 2 (cp 0): 17 leaves, training accuracy 1.0, CV 0.8029; minsplit 50: 2 leaves. minbucket 1 (minsplit 20, cp 0): 5 leaves but different splits (Age importance from 3.10 to 4.86); minbucket 10: 2 leaves.

→ Minimum leaf / node size

Maximum depth

Concept: The largest number of successive questions that can be asked between the root and the farthest leaf. Limiting depth simplifies the tree and reduces its variability, but also lowers its ability to capture complex relationships.

Everyday example: With depth limited to 2, at most two questions are asked about an application: for example, debt burden and time in the job. This gives a rule that can be applied quickly at the counter but may miss finer distinctions.

What it does: Maximum number of levels from the root to the farthest leaf.

Effect on the result: A shallow tree gives fewer rules and lower variance; the number of leaves and the performance change.

On the validation data: kyphosis full data maxdepth 1: 2 leaves (Start < 8.5); maxdepth 3 and cp 0: 2 leaves.

→ Maximum tree depth

CV folds (xval)

Concept: For the pruning decision, the cross-validation error (xerror) and its standard error (xstd) are computed for every possible size of the tree. This internal CV does not change the tree itself; it only provides information for deciding at what size to prune.

Everyday example: The training applications are split into 10 parts; each time a tree is built on 9 parts and tried on the remaining one. The average errors of one-, two- and three-question trees in these tests are compared, and the pruning point is chosen accordingly.

What it does: V-fold CV for the xerror/xstd columns of the cptable; groups are assigned randomly with the seed; 0 = off.

Effect on the result: Does not change the tree (when prune = cp); it affects only xerror/xstd and the min/1se selection.

On the validation data: kyphosis full data, last-row xerror: xval 5: 1.1765; 10: 1.0; 20: 0.8235; at xval 0 there is no xerror. xerror and xstd depend on the CV groups formed with the seed.

→ k-fold cross-validation

Categorical X (Subset splits / Dummy (k-1 indicators) / Ordinal codes)

Concept: Determines how a categorical variable is split in the tree: its levels can be divided into two subsets, each level can be turned into a separate yes/no indicator (dummy), or the levels can be treated as ordered numbers. The choice changes which splits are available as candidates.

Everyday example: If the occupation variable has the levels 'civil servant, shopkeeper, labourer, retired', a subset split can separate '{civil servant, retired} from {shopkeeper, labourer}'. With dummy indicators the tree asks about one occupation at a time, such as 'shopkeeper or not?'.

What it does: How categorical predictors enter the tree: splits on subsets of levels, k-1 dummy indicators or an ordinal numeric code.

Effect on the result: The candidate splits change; the tree structure, number of leaves and performance may change.

On the validation data: car.test.frame Type ~ ...: Country with 8 levels: subset splits 8 leaves, accuracy 0.8167; dummy and ordinal codes 7 leaves, 0.7833. Mileage regression: subset R² 0.854, dummy and ordinal 0.8545.

→ Dummy (indicator) variable coding

Test proportion, CV folds and repeats, Random seed

Concept: The tree is built on the training set only and tested on a test set it has never seen; cross-validation gives an additional measure of generalisation within the training set. Because trees are very sensitive to the data, the split proportion and seed can change even the tree's structure.

Everyday example: The bank builds the tree on 400 of 500 past applications and tests the rules on the remaining 100. If choosing a different 400 with another seed changes even the first question, that shows how unstable the rules are.

What it does: Stratified training/test split proportion (0 = all data); k-fold CV within the training set and its repeats; split and CV seed.

Effect on the result: The tree is grown on the training set only; the proportion and seed change the tree and the test and CV scores.

On the validation data: kyphosis test proportion 0: training accuracy 0.8395 (5 leaves); 0.2: test 0.7647 (4 leaves); 0.5: root only in the training set of 41 observations. With test 0.2 the 5-fold CV on the 64 training rows is 0.6551. Seed 1: a different split, 2 leaves, test accuracy 0.7059 (seed 42: 0.7647). car.test.frame Mileage ~ Weight 5-fold CV R² 0.606 (full-data R² 0.743).

→ Train-test split (holdout)

Imbalanced classes: balanced weights

Concept: With imbalanced classes the tree easily reaches high accuracy by predicting the majority class. Equal prior probabilities give each class an equal say in the impurity calculation, so the splits are directed at telling the minority class apart.

Everyday example: If only 10% of applications run into problems, the tree can reach 90% accuracy by saying 'everyone repays', yet catch none of the problem cases. With balanced weights, questions that separate the problem applications come to the fore.

What it does: Equal prior probabilities (prior = 1/K); weights minority-class errors more heavily.

Effect on the result: Splits shift in favour of the minority class; sensitivity and F1 may increase and accuracy may change.

On the validation data: kyphosis full data: 3 leaves, accuracy 0.8272, F1 0.6667, root split Start < 12.5.

→ Class imbalance and balanced weights

Permutation importance, Save predictions, Probability threshold, Additional metrics, Partial dependence, Chart

Concept: Permutation importance shows how much performance drops when a variable is shuffled, and partial dependence how the prediction changes as a variable changes. The probability threshold sets at which leaf proportion a case is called 'positive'; the additional metrics and charts summarise the tree's performance and structure.

Everyday example: If 35% of the applications in a leaf ran into problems, the default 50% threshold labels this leaf 'low risk'. If the bank is very risk-averse, it lowers the threshold to 30% and sends the applications in this leaf for further review as well.

What it does: Permutation importance on the test set; saving prediction and probability columns; probability threshold in binary classification; additional metrics (Kappa, MCC, NIR, McNemar); partial dependence; plot.

Effect on the result: The tree does not change; the threshold changes only the class predictions, the others produce additional output.

On the validation data: kyphosis permutation importance: Start 0.0176 (SD 0.0459), Number 0.0, Age -0.0059. Threshold 0.3: test accuracy from 0.7647 to 0.8235, F1 from 0.3333 to 0.6667. Additional metrics: Kappa 0.2093 (ASE 0.2668), MCC 0.2279, NIR p 0.630, McNemar p 0.617. The chart type (cp, importance) changes only the drawing.

→ Permutation importance

Example on real data

Data: kyphosis, R rpart package (n = 81)

Variables: target Kyphosis (postoperative kyphosis absent/present), features Age (months), Number (vertebrae involved) and Start (first vertebra)

  • Question: How accurately does a decision tree built on age (Age), number of vertebrae operated on (Number) and first vertebra (Start) classify postoperative kyphosis (Kyphosis)?
  • Tree: Gini criterion, cp = 0.01, a tree with 3 splits and 4 leaves (depth 3): if Start >= 12.5 then absent (36 of 37 children); if Start < 12.5, Age >= 34.5 and Number >= 4.5 then present (8 of 11 children). Training n = 64, test n = 17.
  • Result: On the test set accuracy = .76, precision = .50, recall = .25, F1 = .33, ROC-AUC = .76; only 1 of 4 children with kyphosis is detected.
  • Variable importance: Start 53.7%, Number 25.5%, Age 20.7% (primary and surrogate splits).
  • Generalization: 5-fold CV accuracy M = .66 (SD = .12); in the internal CV the smallest xerror belongs to the root (1.00) and the unpruned tree has xerror 1.23, so the generalization gain of the tree is uncertain.
  • Limitation: The sample is very small (n = 81, 17 kyphosis cases); sensitivity for the minority class is low, and balanced weights or threshold tuning are needed.
  • APA: CART (Gini, cp = 0.01; 4 leaves) on the test set (n = 17) gave accuracy = .76, ROC-AUC = .76; 5-fold CV accuracy M = .66 (SD = .12).

Related concepts

Tree pruning and the complexity parameter (cp)Node impurity (Gini, entropy)Minimum leaf / node sizeMaximum tree depthTrain-test split (holdout)Permutation importanceVariable importance (gain, cover, frequency)Class imbalance and balanced weights

The numbers in the examples are MerQur's output on independent, publicly available validation data; see the MerQur Technical Note for details.