liveBook · Manning

Decision tree

As explained in Timeless Algorithms, The Foundational Ideas

A decision tree is a hierarchical predictive model that recursively partitions data using feature-based rules.

A decision tree predicts an outcome by asking a sequence of feature-based questions. Each internal node tests a feature, each branch records an answer, and each leaf supplies a prediction. Trees can classify observations into categories, such as loan approval or denial, or predict a continuous value, such as a house price. section 5.3.1

Construction starts with all training observations at the root. A splitting rule divides them into mutually exclusive groups; the procedure repeats within each group until leaves are reached. A new observation follows the rules from root to leaf. A classification leaf predicts its most common training class, while a regression leaf predicts the average training outcome. section 9.1

For classification, one way to choose a split is to measure the reduction in entropy, or uncertainty about class labels. If H(parent) is the entropy before splitting and H(child) is the entropy of a resulting group, information gain is H(parent) − Σ wᵢH(childᵢ), where wᵢ is the fraction of observations in child i. A larger gain means the split leaves less weighted uncertainty. Regression trees instead seek splits that reduce variation in the numerical outcome. section 5.3.1 section 9.1

Split selection is greedy: it chooses the greatest immediate improvement at each node, without looking ahead or revisiting earlier choices. Nearly equal candidate splits can exchange places after a small change in the training sample. A different early split changes the data reaching later nodes and can produce a substantially different tree. section 9.1.1

Trees accommodate numerical and categorical features and can capture nonlinear relationships and interactions without specifying them in advance. Greater depth increases expressive power, but small leaves can reflect noise rather than patterns that generalize. Pruning can reduce overfitting; combining diverse trees through bagging or random forests can reduce variance. section 9.1.2 section 9.9

A predictive tree differs from a decision-analysis tree. The former learns rules from data to estimate outcomes; the latter represents specified actions, uncertainties, probabilities, and utilities to compare choices. section 7.1.2

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Explains split selection, leaf predictions, greedy instability, depth and overfitting, and ensemble remedies.
Examples
Illustrates classification with loan approval and regression with house-price prediction.
What you can do after
Evaluate/understand how splits produce predictions and why a well-fitting tree may generalize poorly.
How it connects
Connects trees to entropy, information gain, pruning, bagging, random forests, and decision analysis.

Also explained in

Compare how 18 books explain decision tree →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.