decision tree

A decision tree is a machine learning model that predicts a label or a value by asking a series of yes-or-no questions about a data point’s features, such as a house’s floor area or its number of bedrooms. Each answer picks a branch, and the path ends at a leaf that carries the prediction. In its most common form the model is a binary tree fitted straight from data rather than written by hand.

Training grows the tree greedily from the root. At each node the algorithm scans feature-and-threshold pairs and keeps the split that most reduces an impurity measure, a score of how mixed the labels are, across the two groups. Classification scores splits by Gini impurity or by entropy (information gain), while regression minimizes squared error within each group. Splitting stops once a node is pure, too small to split, or at a depth limit.

Finding the optimal tree is NP-complete, with no known efficient solution, so practical algorithms settle for that local heuristic. The main families are Ross Quinlan’s ID3 and its successor C4.5, which allow multiway splits, and CART, published by Breiman, Friedman, Olshen, and Stone in 1984, which splits in two and handles regression. Scikit-learn’s DecisionTreeClassifier implements an optimized CART and defaults to the Gini criterion.

Left unconstrained, a tree keeps splitting until it has memorized its training set, a failure known as overfitting. Depth caps, minimum leaf sizes, and cost-complexity pruning after the fact all trade fit for generalization. Trees are also unstable, in that a small change in the data can reshape the whole structure. And because every leaf predicts a constant, a tree cannot extrapolate beyond the target range it saw during training.

The explorer below caps the depth of a greedy fit on one small training set, and pushing the cap past a depth of three sends training accuracy up while held-out accuracy, measured on data the tree never trained on, falls.

Interpretability is the compensating strength, since the fitted rules can be read straight off the tree. The same structure is also the building block of ensembles such as random forests and gradient-boosted trees, which still lead on tabular, spreadsheet-style data where a neural network often trails.

Related Resources

Tutorial

Split Your Dataset With scikit-learn's train_test_split()

In this tutorial, you'll learn why splitting your dataset in supervised machine learning is important and how to do it with train_test_split() from scikit-learn.

intermediate data-science machine-learning numpy

For additional information on related topics, take a look at the following resources:

• Logistic Regression in Python (Tutorial)
• Linear Regression in Python (Tutorial)
• K-Means Clustering in Python: A Practical Guide (Tutorial)
• Splitting Datasets With scikit-learn and train_test_split() (Course)
• The pandas DataFrame: Make Working With Data Delightful (Tutorial)
• Setting Up Python for Machine Learning on Windows (Tutorial)
• Split Your Dataset With scikit-learn's train_test_split() (Quiz)
• Starting With Linear Regression in Python (Course)
• Linear Regression in Python (Quiz)
• K-Means Clustering in Python: A Practical Guide (Quiz)
• The pandas DataFrame: Working With Data Efficiently (Course)
• The pandas DataFrame: Make Working With Data Delightful (Quiz)
• Setting Up Python for Machine Learning on Windows (Quiz)