Decision Trees Demystified: A Practitioner‘s Guide

Decision trees are a classical machine learning algorithm that remain widely used today due to their simplicity, interpretability, and strong performance on a variety of tasks. In this guide, we‘ll take a deep dive into decision trees from the perspective of a AI/ML practitioner – covering their inner workings, variants, implementation, tuning, and applications. Whether you‘re a beginner or expert, you‘ll gain insights to help you wield decision trees effectively in your own work.

A Brief History of Decision Trees

The origins of decision trees can be traced back to the 1960s, with the development of AID (Automatic Interaction Detection) by Morgan and Sonquist. This was one of the first algorithms for building regression trees.

The next major milestone was Quinlan‘s ID3 (Iterative Dichotomiser 3) in 1979, which built decision trees for classification using information gain. Quinlan followed up with the improved C4.5 algorithm in 1993.

Another seminal work was the development of CART (Classification and Regression Trees) by Breiman, Friedman, Stone, and Olshen in 1984. CART was novel in that it could be used for both classification and regression.

Since then, there have been many extensions like Quinlan‘s M5 for regression, Amit and Geman‘s randomized trees, Dietterich‘s ensemble methods, and Quinlan‘s MinEntropy method for building decision trees.

In the 2000s, Breiman introduced random forests, which combine many decorrelated decision trees to improve accuracy and reduce overfitting. Friedman developed gradient boosted decision trees, which successively build trees to minimize errors of previous trees.

Today, optimized tree implementations like XGBoost are widely used to achieve state-of-the-art results on tabular data and decision trees remain a go-to in the ML practitioner‘s toolkit.

How Decision Trees Work

At their core, decision trees work by recursively partitioning data into subsets based on feature splits that maximize some measure of separation between classes (for classification) or minimize variation of the target within subsets (for regression).

The basic steps are:

1. Calculate the impurity of the target variable for the entire dataset
2. For each feature, calculate the impurity if we split on that feature
3. Choose the feature that provides the most reduction in impurity if split upon
4. Recurse on the subsets from step 3 until a stopping criterion is met

Common impurity measures for classification are entropy and Gini impurity. For regression, mean squared error (MSE) or mean absolute error (MAE) are used.

Mathematically, the "gain" from splitting on a feature is the difference between the impurity of the parent node and the weighted average of impurities of the child nodes:

Gain(T,X) = Impurity(T) - |T_L|/|T|*Impurity(T_L) - |T_R|/|T|*Impurity(T_R)

Where T is the current node, X is the feature to split on, and T_L and T_R are the left and right child nodes from splitting on X.

Stopping criteria can be a maximum depth, a minimum number of samples to split a node, or a threshold on the gain.

Comparison of Decision Tree Algorithms

While all decision trees share this general approach, there are a variety of specific algorithms that differ in the impurity measures used, types of features supported, and details of the tree construction process.

Here is a comparison of some of the most common algorithms:

Algorithm	Developed	Used For	Impurity Measure	Supports Categorical Features	Notes
ID3	1979	Classification	Information Gain	Yes	Tends to prefer features with more levels
C4.5	1993	Classification	Gain Ratio	Yes	Improvement on ID3 by normalizing gain by split info
C5.0	1997	Classification	Information Gain	Yes	Faster and more memory efficient than C4.5
CART	1984	Both	Gini (classification), MSE (regression)	No	Builds binary trees, easy to interpret
CHAID	1980	Classification	Chi Square	Yes	Popular in marketing, builds non-binary trees
M5	1992	Regression	Standard Deviation	No	Computationally efficient
MARS	1991	Regression	Generalized Cross-Validation (GCV)	No	More of a spline method than decision tree

In terms of computational complexity, most decision tree algorithms are generally pretty efficient. ID3, C4.5, and CART have a time complexity of O(n*m*log(m)) for n training examples and m features. Space complexity is O(m) since the size of the tree scales with the number of features.

Some more advanced algorithms like MARS can be more computationally intensive due to the search for optimal spline placements. And of course, ensembles of trees like random forests and boosted trees require building multiple trees so are slower to train than single trees.

Implementing Decision Trees

Most major programming languages have libraries that implement various decision tree algorithms. Here are a few of the most popular:

Python:

• scikit-learn: Implements CART, along with ensembles like random forests and gradient boosting
• XGBoost: Optimized gradient boosting library
• LightGBM: Fast gradient boosting implementation that uses histogram-based algorithms

Example of training a decision tree classifier in Python with scikit-learn:

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

X, y = load_iris(return_X_y=True)
clf = DecisionTreeClassifier(criterion=‘gini‘, max_depth=3)
clf.fit(X, y)

R:

• rpart: Recursive partitioning for CART trees
• party: Implements conditional inference trees
• C50: Implements Quinlan‘s C5.0 algorithm

Example in R with rpart:

library(rpart)
fit <- rpart(Survived ~ ., data = titanic_train, method = "class")

Java:

• Weka: Java library that implements ID3, C4.5, M5, and more
• Apache Spark MLlib: Distributed implementation of decision trees and ensembles

Tuning Decision Trees

While decision trees often work quite well with default hyperparameters, tuning them can improve performance and avoid overfitting or underfitting. Key hyperparameters to consider tuning include:

• max_depth: The maximum depth to grow the tree to. Larger values risk overfitting. Typical values range from 3-10.
• min_samples_split: The minimum number of examples required to split a node. Increase this to prevent overfitting. Common values are 2-20.
• min_samples_leaf: The minimum number of examples that must be in a leaf. Larger values prevent the tree from learning relations specific to small subsets. Typical values are 1-20.
• max_features: Number of features to consider when looking for best split. For classification, sqrt(n_features) is a good starting point. For regression, log2(n_features) tends to work well.

To tune hyperparameters, common approaches include grid search and random search. With grid search, you define a range of values for each hyperparameter and the algorithm tries every combination. Random search tries random combinations and can be more computationally efficient.

Another effective tuning method is k-fold cross-validation. The training data is split into k folds and the tree is trained k times, using a different fold as the validation set each time. Performance is then averaged across the k trials.

Early stopping is another useful technique, where tree growth is stopped early based on the performance on a validation set to prevent overfitting.

Case Studies and Benchmarks

To demonstrate the effectiveness of decision trees, let‘s look at some case studies and benchmarks.

Predicting Heart Disease

In one study, researchers used decision trees to predict presence of heart disease based on clinical and demographic features like age, sex, chest pain type, blood pressure, cholesterol levels, etc. On a dataset of 270 patients, a C4.5 decision tree achieved an accuracy of 78.9%, outperforming logistic regression and naive Bayes.

Detecting Credit Card Fraud

Another study applied CART decision trees to the task of identifying fraudulent credit card transactions. On a dataset of 284,807 transactions, of which 492 were fraudulent, a single decision tree achieved a precision of 87% and recall of 69% on the fraudulent class. An ensemble of trees was able to improve precision to 89% and recall to 95%.

Benchmarks on Standard Datasets

To compare decision trees to other common algorithms, here are results on some standard machine learning datasets:

Dataset	Decision Tree (CART)	Random Forest	SVM	kNN
Iris	94.7%	94.7%	96.0%	95.3%
MNIST	87.5%	96.8%	98.4%	97.1%
Titanic	81.4%	81.8%	83.2%	75.9%
Boston Housing	5.11 MSE	3.13 MSE	7.69 MSE	10.06 MSE

Results are averages over 10 trials using scikit-learn with default hyperparameters. While not always the top performing model, decision trees are consistently competitive across a range of datasets. And their fast training time and interpretability make them an attractive choice in many scenarios.

Limitations and Ongoing Research

Despite their strengths, decision trees do have some important limitations:

• Prone to overfitting, especially when allowed to grow very deep
• High variance – small changes in training data can lead to quite different trees
• Cannot learn simple relationships like XOR
• Struggles with imbalanced classes since impurity measures don‘t account for class frequencies
• Biased towards features with large number of levels
• Can‘t handle missing values natively

There is ongoing research to try to address these limitations:

• Cost-complexity pruning and other methods to prevent overfitting
• Random forests and other ensembles to reduce variance
• Hellinger distance decision trees (HDDTs) for imbalanced data
• Methods for regularizing or discretizing features with many levels
• Techniques for incorporating missing value handling into split criteria
• Incremental optimization of trees based on newly observed data
• Application of deep learning techniques like representation learning and gradient-based optimization to tree construction

Another exciting area is making decision trees differentiable so that they can be used as layers in neural networks and trained end-to-end. This could allow embedding expert knowledge into neural networks and using trees to explain the decisions of black box models.

The Future of Decision Trees

As machine learning continues its rapid growth and application to new domains, decision trees are well positioned to remain a critical part of the practitioner‘s toolkit.

Some key advantages of decision trees – their interpretability, quick training, and easy handling of various data types – make them ideal for fast prototyping and building models that are transparent and accountable. In fields with strict regulations like healthcare and finance, these traits are especially valuable.

With the rise of Internet of Things, there will be an explosion of streaming sensor data where the efficient inference of decision trees will be valuable for edge computing on low-powered devices. Especially with the development of more efficient tree-based methods like Hoeffding trees.

The automated machine learning (AutoML) movement also presents an opportunity for decision trees, since their fast training times make them ideal for the rapid iteration and evaluation of many model configurations. Several AutoML systems already include trees and ensembles prominently in their search spaces.

Longer term, the intertwinement of decision trees with deep learning is an exciting frontier. Whether through differentiable trees, using trees to explain neural nets, or constraining neural nets to have tree-like properties, there is a lot of potential for these two powerful approaches to enhance each other.

Whatever the future holds, it‘s a safe bet that decision trees will continue to branch out to new applications and will keep bearing fruit for savvy data scientists who cultivate them.