1 Definition and Basic Concepts

A decision tree is a supervised machine learning algorithm that models decisions and their possible consequences in a tree-like structure. It is used for both classification (predicting categorical labels) and regression (predicting continuous values). The algorithm partitions the feature space into regions, each associated with a simple model (e.g., a constant value or a class label). Decision trees are popular for their interpretability and serve as building blocks for advanced ensemble methods.

1.1 Tree Structure

The structure of a decision tree consists of nodes connected by branches, forming a hierarchical, directed graph from the root to the leaves. Each node represents a test on a feature, and branches correspond to possible outcomes of that test.

1.1.1 Root Node

The root node is the topmost node of the tree. It contains the entire training dataset and represents the first decision or split. All subsequent splits originate from this node.

1.1.2 Internal Nodes

Internal nodes are nodes between the root and the leaves. Each internal node applies a test on a single feature, splitting the data reaching it into two or more subsets based on the outcome of the test.

1.1.3 Branches

Branches connect nodes and represent the outcomes of the test at a parent node. For categorical features, each branch typically corresponds to a distinct category; for numerical features, branches represent intervals (e.g., “≤ threshold” and “> threshold”).

1.1.4 Leaf Nodes

Leaf nodes, also called terminal nodes, are the final nodes in the tree. They do not perform any test and instead store the predicted output: a class label for classification trees or a numeric value for regression trees.

1.2 Decision vs. Regression Trees

Decision trees can perform two types of predictive tasks, distinguished by the nature of the target variable.

1.2.1 Classification Trees

A classification tree predicts a discrete class label. Each leaf node is assigned the majority class of the training instances that reach it. The splitting criteria aim to increase purity of the child nodes with respect to the class distribution.

1.2.2 Regression Trees

A regression tree predicts a continuous value. Each leaf node stores the average (or median) of the target values of the instances in that leaf. Splitting is guided by minimizing the variance or the sum of squared errors within the resulting subsets.

1.3 Splitting Criteria

Splitting criteria quantify the quality of a candidate split. They measure the reduction in impurity (for classification) or the reduction in variance (for regression) achieved by partitioning the data.

1.3.1 Information Gain and Entropy

Entropy measures the disorder in a set of class labels. For a dataset with classes, entropy is defined as \( H = -\sum_{i} p_i \log_2(p_i) \), where \(p_i\) is the proportion of instances of class \(i\). Information gain is the difference between the entropy of the parent node and the weighted average entropy of the child nodes. The split that maximizes information gain is selected.

1.3.2 Gini Impurity

Gini impurity is another measure for classification. It is calculated as \( G = 1 - \sum_{i} p_i^2 \). A pure node (all instances belong to one class) has Gini = 0. The Gini gain (reduction in impurity) is used similarly to information gain; splits with higher gain are preferred.

1.3.3 Variance Reduction

For regression trees, the splitting criterion is typically variance reduction. The variance of the target values in a node is computed. The split that minimizes the weighted sum of variances of the child nodes (or maximizes the reduction in variance relative to the parent) is chosen.

2 Algorithm and Construction

Constructing a decision tree involves recursively partitioning the data based on feature tests, using a greedy strategy to select splits that optimize a chosen criterion.

2.1 Greedy Top-Down Induction

The standard algorithm builds the tree from the root downward, making locally optimal decisions at each node without considering future splits.

2.1.1 Selecting the Best Split

At each node, all possible splits across all features are evaluated. For each candidate, the impurity or variance reduction is computed. The split that yields the highest gain (or lowest impurity) is selected.

2.1.2 Stopping Conditions

Recursive partitioning stops when one or more conditions are met: all instances in a node belong to the same class (or have identical target values for regression), the node contains fewer than a minimum number of samples, the maximum tree depth is reached, or no split yields a significant reduction in impurity.

2.1.3 Recursive Partitioning

After selecting the best split, the algorithm partitions the data according to the branches and recursively applies the same process to each child node. This continues until a stopping condition is triggered for each node.

2.2 Handling Different Data Types

Decision trees can naturally handle various feature types, though the splitting logic differs.

2.2.1 Categorical Features

For categorical features, splits may be based on a single value (e.g., “color = red” vs. “color ≠ red”) or on subsets of categories (e.g., “color in {red, blue}” vs. other). Many implementations use binary splits for simplicity.

2.2.2 Numerical Features

For numerical features, a threshold value is searched. The data is partitioned into two groups: those with feature value ≤ threshold and those with value > threshold. The threshold that gives the best split is chosen by scanning sorted values.

2.3 Handling Missing Values

Missing feature values must be dealt with during both training and prediction.

2.3.1 Surrogate Splits

Surrogate splits provide an alternative test when the primary test’s feature is missing. During training, a secondary split (using a different feature) that best approximates the original partition is learned. At prediction time, the surrogate is used if the primary feature is unavailable.

2.3.2 Mean/Mode Imputation

A simpler approach is to replace missing values with the mean (for numerical features) or mode (for categorical features) of the feature in the training set. Some algorithms also perform imputation separately for each node during tree construction.

2.4 Pruning Methods

Pruning reduces overfitting by removing branches that have little predictive power.

2.4.1 Pre-Pruning (Early Stopping)

Pre-pruning halts tree growth before it becomes overly complex. Common constraints include setting a maximum depth, a minimum number of samples required to split a node, or a minimum impurity decrease. This prevents the model from learning noise.

2.4.2 Post-Pruning (Cost Complexity Pruning)

Post-pruning first builds a full tree and then removes subtrees that do not improve generalization on validation data. It is more computationally expensive but often yields better results.

2.4.2.1 Minimal Cost-Complexity Pruning

This method introduces a complexity parameter α that penalizes the number of leaves. The algorithm generates a sequence of nested subtrees by iteratively removing the branch that minimizes the increase in cost (e.g., misclassification error) per unit decrease in complexity. The optimal α is chosen via cross-validation.

2.4.2.2 Reduced Error Pruning

Reduced error pruning uses a validation set. Starting from the leaves, each node is replaced by the most frequent class (or mean value) if doing so does not increase validation error. The process repeats until no further simplification improves performance.

3 Advantages and Limitations

3.1 Strengths

3.1.1 Interpretability

Decision trees are highly interpretable, as the learned model can be visualized as a flowchart. The path from root to leaf provides an explicit decision rule that humans can easily understand and verify.

3.1.2 Non-parametric Nature

The algorithm makes no assumptions about the underlying data distribution (e.g., normality, linearity). It can capture complex interactions and non-linear relationships without requiring feature transformation.

3.1.3 Feature Importance

Decision trees inherently rank features by their contribution to reducing impurity. The total reduction in impurity attributable to each feature aggregated over all splits provides a measure of importance, useful for feature selection.

3.2 Weaknesses

3.2.1 Overfitting

Unpruned decision trees can grow very deep and memorize noise in the training data, leading to poor generalization. Pruning and hyperparameter tuning are essential to mitigate this.

3.2.2 Instability (High Variance)

A small change in the training data (e.g., adding or removing a few points) can cause a completely different tree structure. This high variance makes single decision trees less robust compared to ensemble methods.

3.2.3 Bias towards Dominant Features

Splitting criteria tend to favor features with many distinct values (e.g., high-cardinality categorical features). This can result in biased trees that over-rely on such features, potentially reducing interpretability and performance.

4 Extensions and Variants

4.1 Ensemble Methods

Ensemble methods combine multiple decision trees to improve accuracy and stability.

4.1.1 Random Forest

Random forest builds a collection of decision trees on bootstrapped samples of the data and random subsets of features. Predictions are aggregated by voting (classification) or averaging (regression). This reduces variance and mitigates overfitting.

4.1.2 Gradient Boosted Trees

Gradient boosting builds trees sequentially, each correcting the errors of the previous ones. It optimizes a differentiable loss function, producing a strong predictive model, but it can overfit if not carefully regularized.

4.1.3 AdaBoost with Decision Stumps

AdaBoost (Adaptive Boosting) uses shallow decision trees (often stumps, i.e., single-split trees) as weak learners. Each stump is weighted according to its performance, and the final prediction is a weighted vote.

4.2 Multivariate Decision Trees

Standard decision trees use univariate splits (testing a single feature). Multivariate decision trees allow splits that are linear combinations of several features, enabling oblique decision boundaries. This can capture correlations between features but reduces interpretability.

4.3 Oblique Decision Trees

Oblique decision trees are a special case of multivariate trees where the split at each node is a linear function (e.g., \(a_1 x_1 + a_2 x_2 + ... + a_n x_n \leq c\)). They are more powerful than axis-aligned splits for some datasets but are computationally more expensive.

4.4 Decision Trees for Imbalanced Data

Imbalanced datasets (where one class is rare) can cause standard decision trees to bias toward the majority class. Variants adjust splitting criteria to account for class weights, use sampling techniques (e.g., SMOTE) before tree construction, or employ cost-sensitive pruning that penalizes misclassification of the minority class more heavily.

5 Applications

5.1 Healthcare Diagnostics

Decision trees are widely used in medical decision support systems. For example, a tree can classify whether a patient has a disease based on symptoms, lab results, and demographics, providing transparent rules that clinicians can validate.

5.2 Credit Risk Assessment

Banks and financial institutions use decision trees to evaluate loan applications. The model’s interpretability allows them to explain why a customer was approved or denied, meeting regulatory requirements.

5.3 Customer Segmentation

Marketing analysts apply decision trees to segment customers into groups based on purchasing behavior, demographics, and preferences. The resulting rules help design targeted campaigns.

5.4 Anomaly Detection

In cybersecurity or fraud detection, decision trees can identify unusual patterns by learning the normal behavior of a system. Outliers that fall into low-density leaf nodes can be flagged as anomalies.

5.5 Game AI Decision Making

In video games, decision trees are a classic method for modeling non-player character (NPC) behavior. The tree decides actions (e.g., attack, flee, patrol) based on game state variables such as health, distance to enemy, or ammunition.

6 Implementation and Tools

6.1.1 Scikit-learn (Python)

Scikit-learn provides the DecisionTreeClassifier and DecisionTreeRegressor classes with support for Gini, entropy, and variance-based splitting, as well as pruning via ccp_alpha. It integrates well with the Python ecosystem for data preprocessing and evaluation.

6.1.2 rpart (R)

The rpart package in R implements recursive partitioning and cost-complexity pruning. It includes functions for plotting trees and cross-validating hyperparameters. It is a standard tool for decision tree analysis in R.

6.1.3 Weka (Java)

Weka is a collection of machine learning algorithms, including J48 (an implementation of C4.5) and REPTree. It offers a graphical user interface and command-line interface, making it accessible for educational and research purposes.

6.2 Practical Considerations

6.2.1 Hyperparameter Tuning

Key hyperparameters affecting performance include maximum tree depth, minimum samples per leaf, minimum impurity decrease, and the complexity parameter α (for cost-complexity pruning). Grid search or random search combined with cross-validation helps find optimal values.

6.2.2 Cross-Validation

Cross-validation (e.g., k-fold) estimates the generalization error of the tree. It is used to select hyperparameters and to assess whether pruning has reduced overfitting. Stratified cross-validation is recommended for classification tasks with imbalanced classes.

6.2.3 Visualization

Decision trees can be visualized using libraries such as graphviz (Python) or rpart.plot (R). Visualizations show the tree structure, split conditions, and leaf values, aiding interpretation and communication of the model’s logic.