Decision Trees and Rule-Based Models

Introduction and context

Decision trees are supervised learning models that represent prediction as a sequence of questions. Each internal node tests a feature, each branch represents an outcome of that test, and each terminal node (leaf) produces a class label, probability, or numerical prediction. Rule-based models express the same logic as human-readable statements such as: “If customer tenure is less than six months and payment failures exceed two, classify the account as high risk.”

These models are especially valuable in business analytics because they combine predictive capability with operational transparency. A bank can explain a credit decision, a retailer can identify the conditions associated with churn, and a hospital can audit a triage rule. However, transparency should not be confused with reliability: an interpretable tree can still be biased, unstable, or poorly calibrated.

Learning objectives

By the end of this chapter, the reader should be able to:

1. Explain recursive partitioning and the structure of classification and regression trees.
2. Calculate and interpret entropy, Gini impurity, variance reduction, and split gain.
3. Construct a small tree and translate it into decision rules.
4. Apply stopping, pruning, validation, and stability procedures.
5. Evaluate the managerial value and limitations of transparent models.
6. Compare tree-based rules with other predictive modelling approaches.

1. Structure of a decision tree

A tree partitions the predictor space into regions. Let the training data be D = {(x_i, y_i)}_i=1ⁿ, where x_i is the vector of predictors for observation i, y_i is its outcome, and n is the number of observations. A split divides a parent region into child regions. Recursion continues until a stopping rule is met.

A classification leaf predicts the majority class or an estimated class probability. If a leaf contains n_t observations and n_tk belong to class k, its estimated probability is:

This estimate assumes that observations in the leaf are treated as exchangeable for prediction. A regression leaf commonly predicts the mean response:

The units of ŷ_t are the same as the response variable. For a monetary response, for example, the prediction is in monetary units.

A binary tree can be represented as rules. The path from the root to a leaf forms one rule, and the leaf’s prediction is the rule’s conclusion.

Figure: A tree converts sequential feature tests into operational risk rules.

2. Recursive partitioning

Most classical tree algorithms use greedy recursive partitioning. At each node, the algorithm searches candidate features and thresholds, evaluates the resulting child nodes, and chooses the split that produces the greatest improvement according to an impurity or loss criterion. The process is greedy because it optimizes the immediate split rather than searching all possible complete trees. This makes tree construction feasible but does not guarantee a globally optimal tree.

For a numerical feature, a candidate split may be x_j ≤ c, where x_j is feature j and c is a threshold. For a categorical feature, the split may separate one category or a subset of categories from the remainder. The search must be defined carefully when categories are numerous, missing, or ordered.

A weighted child impurity is:

Here, I(L) and I(R) are the impurities of the left and right children, n_L and n_R are their observation counts, and n_t = n_L + n_R is the parent count. Weighting is essential; otherwise a tiny pure child could dominate the criterion.

The impurity reduction is:

A larger positive ΔI indicates a better local split. The same conceptual framework supports classification and regression, but the impurity measure differs.

3. Classification trees

Entropy and information gain

For a node containing K classes, entropy is:

where p_tk is the proportion of class k in node t. The convention 0 log₂ 0 = 0 is used. Entropy is zero when a node is pure and is largest when classes are equally represented. Its unit is bits because the logarithm is base 2.

Information gain is the entropy reduction produced by a split:

Gini impurity

Gini impurity is:

It is the probability that two observations drawn independently from the node would belong to different classes. It ranges from 0 to 1 − 1/K for K classes. Gini impurity and entropy often select similar splits, although they can differ when candidate splits are close.

Worked example: comparing two splits

Suppose a parent node contains 10 customers: six churners and four non-churners. Its Gini impurity is:

G(t) = 1 − (0.6² + 0.4²) = 0.48

Consider Split A. The left child contains five churners and one non-churner; the right child contains one churner and three non-churners.

G(L) = 1 − (5/6)² − (1/6)² ≈ 0.278

G(R) = 1 − (1/4)² − (3/4)² = 0.375

Thus:

G_split,A = (6/10)(0.278) + (4/10)(0.375) ≈ 0.317

and the reduction is approximately 0.48 − 0.317 = 0.163.

Suppose Split B produces two children, each containing three churners and two non-churners. Each child has Gini impurity 1 − 0.6² − 0.4² = 0.48, so the weighted split impurity is 0.48 and the reduction is zero. Split A is therefore preferable under the Gini criterion.

4. Regression trees

For continuous outcomes, a common node loss is the within-node sum of squared errors (SSE):

The leaf prediction ŷ_t is the mean, which minimizes SSE among all constant predictions. A split is selected by minimizing the total child SSE or, equivalently, maximizing SSE reduction:

This criterion assumes squared-error loss is appropriate and gives greater influence to large residuals. If the business objective is absolute error or a conditional quantile, a median-based or quantile-based leaf may be more suitable.

For example, a node with response values 2, 4, 8 has mean 14/3. Its SSE is:

(2−14/3)² + (4−14/3)² + (8−14/3)² = 152/3 ≈ 50.67

A split into {2, 4} and {8} gives child means 3 and 8, with SSE (2−3)²+(4−3)²+0² = 2. The reduction is approximately 48.67. This is a strong improvement, although the example is intentionally small and should not be treated as evidence of generalization.

5. From trees to rule-based models

A tree can be converted into disjoint, mutually exclusive rules. For the figure above:

• If tenure is less than six months and payment failures exceed two, classify as high churn risk.
• If tenure is less than six months and payment failures are two or fewer, classify as medium risk.
• If tenure is at least six months, classify as low churn risk.

Rule systems can also be built directly. A rule has an antecedent (conditions) and a consequent (prediction or action). Useful rule measures include:

• Coverage: the proportion of records satisfying the antecedent.
• Confidence: the proportion of covered records for which the consequent is correct.
• Support: often the proportion of all records satisfying both antecedent and consequent.
• Lift: confidence divided by the overall prevalence of the consequent.

Rules may overlap. In that case, a priority order, voting procedure, or default rule is required. A rule list is sequential: the first rule that matches is applied. A rule set may apply multiple rules and combine their results. This distinction matters operationally because rule precedence can change decisions.

6. Controlling complexity and overfitting

A fully grown tree can fit noise, create tiny leaves, and perform poorly on new data. Complexity control occurs during growth or after growth.

Pre-pruning

Common pre-pruning controls include maximum depth, minimum observations required for a split, minimum observations per leaf, and a minimum impurity reduction. These controls reduce computation and can improve generalization, but overly strict limits can underfit.

Cost-complexity pruning

A standard post-pruning objective is:

Here, T is a tree, R(T) is its empirical risk, |T| is the number of terminal nodes, and α ≥ 0 is the complexity parameter. The risk must be defined consistently with the task, such as misclassification loss or SSE. Larger α penalizes larger trees more strongly. The value of α should be selected using validation or cross-validation, not chosen merely because the resulting tree looks attractive.

Validation and leakage

A holdout set or cross-validation estimates out-of-sample performance. Feature engineering, imputation, threshold selection, and pruning choices must be performed within the training folds when cross-validation is used. Otherwise information from validation observations leaks into model development and makes performance estimates optimistic.

7. Instability and model assessment

Decision trees are high-variance learners. A small change in the sample can change the best root split and consequently alter the entire downstream structure. Instability is increased by correlated predictors, near-tied split candidates, small samples, class imbalance, and measurement noise.

Assessment should match the decision context. For classification, useful metrics include accuracy, precision, recall, specificity, F1 score, balanced accuracy, log loss, and area under the ROC curve. Accuracy is:

where TP, TN, FP, and FN denote true positives, true negatives, false positives, and false negatives. Accuracy can be misleading when classes are imbalanced. A fraud model, for example, may achieve high accuracy by predicting “not fraud” for nearly every transaction.

For regression, common measures include mean absolute error:

and root mean squared error:

MAE is in the response units and is less sensitive to extreme errors than RMSE. Neither metric alone establishes that a model is useful; the cost of errors, operational constraints, and performance across important subgroups must also be examined.

Probability estimates from trees may be poorly calibrated, especially when leaves are small. Calibration assessment compares predicted probabilities with observed frequencies. If a model predicts 0.8 risk for a group, approximately 80% should experience the event for that group to be well calibrated.

8. Interpretability and managerial value

Trees are often called interpretable because their logic can be inspected. Interpretability has several dimensions:

• Simulatability: can a person mentally follow the model?
• Decomposability: can each variable and condition be understood?
• Fidelity: does a simplified explanation accurately represent the deployed model?
• Actionability: can the organization act on the conditions?

A shallow tree with stable, plausible variables is usually more useful than a deep tree with hundreds of narrow branches. Managers should ask whether each split reflects a meaningful mechanism, a policy variable, or merely a proxy for protected status or historical process.

Feature importance based on aggregate impurity reduction can be biased toward continuous variables or categorical variables with many possible split points. Permutation importance can be more informative but is affected by correlated predictors. Local explanations should be supplemented by global structure, subgroup analysis, and error analysis.

9. A detailed applied case: subscription churn

Background

Consider an illustrative telecommunications company with monthly data on 20,000 customers. The business wants to identify customers likely to cancel within the next 30 days so that retention offers can be targeted.

Problem

The company faces three constraints. First, the retention team can contact only 1,500 customers per month. Second, managers require an explanation for each offer. Third, the model must not use post-cancellation information or variables that unfairly encode protected characteristics.

Analysis

Candidate predictors include tenure, monthly fee, service complaints, payment failures, data usage change, contract type, and recent contact history. The outcome is churn within the subsequent 30 days. The temporal definition prevents a common leakage error: using a complaint recorded after the customer has effectively decided to leave.

The data are divided chronologically into training, validation, and test periods. A classification tree is grown with minimum leaf size constraints. Candidate complexity values are compared on validation data using recall at the operational capacity of 1,500 customers, precision, calibration, and subgroup performance.

Suppose the selected tree contains four leaves. One leaf identifies short-tenure customers with repeated payment failures; another identifies long-tenure customers with recent service complaints. The model’s overall accuracy is less important than its ranking and capacity-constrained precision, because the company can act on only a fixed number of cases.

Approach and solution

The company converts the final tree into a monitored rule list. Each rule includes its coverage, estimated churn rate, confidence interval, and recommended action. For example, a rule may trigger a service review rather than an automatic discount when complaints are high. A default rule handles missing or out-of-range values.

Before deployment, the team checks whether performance differs materially by region, language group, age band, or other legally and ethically relevant groups. Protected attributes may be excluded from prediction but retained in a secure audit dataset for fairness monitoring, subject to applicable law and governance policy. Human agents can override a recommendation, but overrides are logged.

Outcome

The tree is easier for retention managers to adopt than a black-box score. However, monitoring shows that a billing-system change alters the distribution of payment failures. The company therefore treats the tree as a governed model: it tracks data drift, rule coverage, calibration, intervention outcomes, and customer complaints. The tree is retrained only after a documented review rather than automatically replacing the existing policy.

Learning points

1. Business capacity determines the appropriate evaluation metric.
2. Temporal design is essential to prevent leakage.
3. Explanations must include uncertainty, coverage, and limitations.
4. Transparent rules do not remove the need for fairness testing.
5. Deployment changes can invalidate previously useful thresholds.

10. Ethics, governance, and regulation

A tree can reproduce historical discrimination even when protected attributes are omitted. Proxy variables such as postcode, language, purchasing pattern, or employment history may encode protected characteristics. A model should therefore be assessed for disparate error rates, unequal access to beneficial decisions, and unjustified exclusion.

Important governance practices include data provenance, documented outcome definitions, version control, reproducible training, access control, human oversight, appeal procedures, and monitoring for drift. In regulated settings, requirements may include adverse-action explanations, record retention, model validation, and restrictions on automated decisions. The exact obligations depend on jurisdiction and sector; legal review is necessary.

Managers should distinguish explanation from justification. “The tree selected this rule” explains the mechanism, but it does not establish that the rule is fair, causally valid, or appropriate for policy.

11. Extensions and contemporary developments

Single trees are often outperformed by ensembles. Bagging averages trees trained on resampled data and reduces variance. Random forests add random feature selection. Gradient-boosted trees build trees sequentially to correct previous errors and frequently achieve excellent predictive performance. These models are less directly interpretable, although partial dependence, permutation importance, local explanations, and surrogate trees can assist analysis.

Modern tree implementations support missing-value directions, categorical encodings, monotonic constraints, class weights, quantile prediction, and cost-sensitive learning. These capabilities should be treated as modelling choices rather than automatic improvements. A monotonic constraint, for example, is appropriate only when domain knowledge supports the claimed direction.

Rule-based models remain useful as policy layers around complex models. A firm may use a high-performing model for ranking but impose explicit rules for legal exclusions, safety limits, or human review. This architecture separates prediction from governance and makes non-negotiable constraints auditable.

Best-practice checklist

• Define the prediction target and prediction time precisely.
• Separate training, validation, and test data using the deployment timeline.
• Select a loss function that reflects business consequences.
• Compare pruning and leaf-size choices using out-of-sample evidence.
• Inspect class balance, missingness, outliers, and subgroup performance.
• Prefer stable, sufficiently large leaves over fragile micro-rules.
• Report coverage, uncertainty, and exceptions for every operational rule.
• Test calibration when probabilities drive decisions.
• Monitor drift, override rates, outcomes, and unintended impacts after deployment.
• Retain human accountability for consequential decisions.

Chapter Summary

Decision trees use recursive partitioning to divide observations into increasingly homogeneous regions. Classification trees commonly use entropy or Gini impurity, whereas regression trees commonly minimize within-node squared error. A leaf predicts a class, probability, mean, median, or other task-appropriate quantity. Paths from root to leaf become interpretable decision rules.

Greedy split selection is computationally practical but can produce unstable trees. Pre-pruning, cost-complexity pruning, validation, and appropriate leaf sizes help control overfitting. Evaluation must reflect class imbalance, error costs, calibration, and operational capacity. Trees offer valuable transparency, but transparent models can still encode bias, rely on leakage, or become invalid under data drift. Effective managerial use therefore combines interpretability with statistical validation, fairness assessment, governance, monitoring, and human responsibility.

Key Terms

Decision tree: A supervised model that represents predictions through hierarchical tests.

Root node: The first node in a tree.

Internal node: A node that applies a feature-based split.

Branch: An outcome of a node’s test.

Leaf: A terminal node that produces a prediction.

Recursive partitioning: Repeatedly dividing a region into child regions.

Impurity: A measure of heterogeneity within a node.

Entropy: A classification impurity measure based on class proportions.

Gini impurity: The probability that two randomly selected node observations have different classes.

Information gain: Reduction in entropy caused by a split.

Regression tree: A tree predicting a numerical outcome.

Rule antecedent: The conditions in an if–then rule.

Rule consequent: The prediction or action produced by a rule.

Coverage: The proportion of records satisfying a rule’s conditions.

Pruning: Removing branches to reduce complexity.

Overfitting: Fitting training-specific noise that harms generalization.

Calibration: Agreement between predicted probabilities and observed frequencies.

Data leakage: Use of information unavailable at prediction time.

Concept drift: Change in the relationship between predictors and outcome over time.

Surrogate model: A simpler model used to approximate another model’s behaviour.

Review Questions

Short Answer Questions

1. What are the roles of internal nodes, branches, and leaves in a decision tree?
2. Why are child-node impurities weighted by child sample size?
3. State the difference between entropy and Gini impurity.
4. What is cost-complexity pruning intended to achieve?
5. Why can a decision tree be interpretable but still unfair?

Long Answer Questions

1. Explain recursive partitioning and compare pre-pruning with post-pruning.
2. Derive the classification-split impurity reduction using Gini impurity and explain each term.
3. Compare classification trees, regression trees, and rule lists in terms of objectives and outputs.
4. Discuss why single trees are unstable and how validation and ensembles address this problem.
5. Explain how a manager should evaluate a churn tree when contact capacity is limited.

Analytical / Application Questions

1. A node contains 12 observations: seven positive and five negative. Calculate its Gini impurity. Then explain what information would be needed to evaluate a proposed split.
2. Design a leakage-resistant modelling plan for predicting loan default when monthly records arrive over time. Specify the data split, target window, evaluation metrics, and governance checks.
3. A deployed tree’s payment-failure variable changes after a billing-system redesign. Analyse the risks and propose a monitoring, validation, and redeployment procedure.

Multiple Choice Questions with Answers

Question 1

Which quantity is the usual prediction of a regression-tree leaf under squared-error loss?

A. The mean response in the leaf

B. The largest response in the leaf

C. The global median response

D. The standard deviation of the response

Correct Answer: A. The mean response in the leaf

Question 2

For a binary node with class proportions 0.6 and 0.4, what is the Gini impurity?

A. 0.16

B. 0.24

C. 0.40

D. 0.48

Correct Answer: D. 0.48

Question 3

Why are child impurities weighted by their node sizes when evaluating a split?

A. To guarantee a deeper tree

B. To prevent a tiny child from dominating the criterion

C. To make all classes equally frequent

D. To eliminate missing values

Correct Answer: B. To prevent a tiny child from dominating the criterion

Question 4

In cost-complexity pruning, what is the role of the parameter α?

A. It increases the number of predictors

B. It converts a regression task into classification

C. It penalizes tree complexity

D. It guarantees fairness

Correct Answer: C. It penalizes tree complexity

Question 5

Which situation is a clear example of data leakage in churn modelling?

A. Using tenure measured at the scoring date

B. Using a complaint recorded after the prediction date

C. Using contract type known at signup

D. Using historical payment failures

Correct Answer: B. Using a complaint recorded after the prediction date

Question 6

What does a rule’s coverage measure?

A. The proportion of records satisfying its antecedent

B. The proportion of errors among uncovered records

C. The number of predictors in the model

D. The model’s calibration slope

Correct Answer: A. The proportion of records satisfying its antecedent

Question 7

Why can a single decision tree be unstable?

A. It cannot represent categorical variables

B. Small data changes can alter the selected splits

C. It always uses linear relationships

D. Pruning makes every tree identical

Correct Answer: B. Small data changes can alter the selected splits

Question 8

Which metric is expressed in the same units as the regression response?

A. Entropy

B. Gini impurity

C. Mean absolute error

D. Accuracy

Correct Answer: C. Mean absolute error

Question 9

If a tree predicts a probability of 0.8 for a well-calibrated group, what should approximately occur over many comparable cases?

A. 20% should experience the event

B. 50% should experience the event

C. 80% should experience the event

D. 100% should experience the event

Correct Answer: C. 80% should experience the event

Question 10

Which governance practice is most appropriate after deploying an operational decision tree?

A. Never changing the tree regardless of data drift

B. Monitoring drift, outcomes, subgroup performance, and overrides

C. Removing all human review

D. Selecting thresholds solely by visual appeal

Correct Answer: B. Monitoring drift, outcomes, subgroup performance, and overrides