What Are Decision Trees?

Decision trees are hierarchical, tree-structured models used for classification and regression that partition a feature space through a sequence of binary or multi-way tests, each associated with a node in the tree. Each internal node tests the value of a single input feature, each branch represents an outcome of that test, and each leaf node assigns a class label or predicts a numeric value. A decision tree is interpretable by design: a human can trace any prediction from the root to the leaf and read off exactly which feature values drove the outcome.

The approach draws from statistics, pattern recognition, and information theory. Quinlan's ID3 algorithm, published in 1986, formalized entropy-based attribute selection for classification trees. Leo Breiman and colleagues extended the framework with the CART (Classification and Regression Trees) algorithm in 1984, introducing Gini impurity as an alternative splitting criterion and establishing recursive binary splitting as the dominant tree construction paradigm. CART also introduced cost-complexity pruning to control overfitting, addressing the tendency of deep trees to fit training noise.

Tree Construction and Splitting Criteria

Building a decision tree involves selecting, at each node, the feature and threshold that best separate the training examples according to a purity criterion. For classification, the two most common criteria are information gain (used in ID3 and C4.5), which measures the reduction in Shannon entropy after a split, and Gini impurity (used in CART), which measures the probability of misclassifying a randomly chosen sample if it were labeled according to the node's class distribution. For regression trees, the criterion is typically the reduction in mean squared error. The scikit-learn decision tree documentation describes both criteria and their implementation in a widely-used open-source library, noting that Gini impurity is generally faster to compute and produces similar results to information gain in practice.

Pruning addresses the overfitting that results from growing a tree until every training example is correctly classified. Reduced-error pruning removes subtrees whose removal does not increase validation-set error. Cost-complexity pruning, introduced with CART, parameterizes tree complexity by a regularization term and selects the optimal size by cross-validation. A decision tree's depth, leaf count, and minimum samples per leaf are all regularization knobs that trade variance for bias.

Random Forests and Ensemble Methods

Individual decision trees have high variance: small changes in training data produce substantially different trees. Random forests, introduced by Breiman in 2001, reduce variance by training many trees in parallel on bootstrap samples of the training data, with each split limited to a random subset of features. The forest aggregates predictions by majority vote for classification or averaging for regression. This bagging with feature randomization breaks correlations between individual trees, improving ensemble accuracy substantially relative to any single tree. The CART and random forest methods surveyed in the machine learning in R reference contrasts single-tree behavior with ensemble performance on benchmark datasets. Gradient boosting, an alternative ensemble strategy, builds trees sequentially with each new tree fitting residuals from the ensemble so far, yielding models such as XGBoost and LightGBM that consistently achieve high accuracy on structured tabular data.

The Springer volume on decision tree algorithms describes extensions including semi-supervised decision trees that incorporate unlabeled data, and oblique trees that test linear combinations of features rather than single attributes, broadening the class of decision boundaries representable within the tree structure.

Applications

Decision trees have applications in a wide range of fields, including:

• Medical diagnosis and clinical decision support
• Financial credit scoring and fraud detection
• Customer churn prediction and marketing analytics
• Fault diagnosis in industrial machinery and control systems
• Feature selection and exploratory data analysis in machine learning pipelines