liveBook · Manning

Decision tree

As explained in Grokking Machine Learning, Second Edition

A procedure for constructing a decision tree by recursively selecting feature-based splits subject to stopping conditions and assigning predictions to terminal nodes.

A decision tree makes a prediction by asking a sequence of simple yes-or-no questions. Start at the root, follow the branch matching the answer, and stop at a leaf, where the tree gives its prediction. Decision nodes ask questions; leaves hold final class labels or predicted values. section 9.0 section 9.6

To build a classification tree, begin with all labeled samples at the root. Choose the feature and split that best separates their labels, create two branches, and repeat for each new group. Stop when a stopping condition is reached; then assign the leaf the most common label among its samples. section 9.2 section 9.6

A split needs a way to judge how useful it is:

  • Accuracy favors splits that correctly classify more samples. section 9.18
  • Gini impurity and entropy measure how mixed the labels are; a pure group has a value of 0 for either measure. section 9.18
  • Information gain is the change in entropy before and after a split. section 9.18

Drawing a tree as boundaries

With two features, each question creates a vertical or horizontal boundary. A first split at x0 = 5 separates most triangles from squares; later splits at x1 = 8 and x1 = 2.5 finish the separation. The sequence of boundaries is the decision tree. section 9.10 section 9.11

Regression trees use the same split-and-repeat structure, but their leaves predict fixed numeric values. For each candidate cutoff, predict the average label on each side and choose the split with the smallest mean square error (MSE). section 9.14 section 9.18

In Python, separate features from labels, create a Scikit-Learn DecisionTreeClassifier or DecisionTreeRegressor, and call fit. A classifier uses the Gini index by default; entropy can be selected as its criterion. Tree depth can also be limited for regression. section 9.11 section 9.14

Trees are useful when the path to a prediction matters. Their hierarchy can reveal which features help determine an outcome, supporting applications such as health-care predictions, recommendation systems, and admissions modeling. section 9.12 section 9.15 section 9.16

Figure 9.26 Left: The resulting decision tree obtained in Scikit-Learn. This tree has three decision nodes and four leaves. Right: The plot of the predictions made by this decision tree. Note that the cutoffs are at ages 35, 15, and 65, corresponding to the decision nodes in the tree. The predictions are 7, 6, 1.33, and 4.5, corresponding to the leaves in the tree.

See how age cutoffs form a regression tree and how each leaf becomes a constant prediction. section 9.14

How Grokking Machine Learning, Second Edition covers it

How deep it goes
Works through recursive training, prediction traversal, split metrics, geometric boundaries, and Scikit-Learn implementations.
Examples
Uses jacket choices, app recommendations, geometric labels, university admissions, user engagement, spam, fraud, and COVID-19 symptoms.
What it assumes
Assumes labeled datasets and introduces decision-tree training through simple binary questions and small examples.
What you can do after
Apply it via Scikit-Learn to train classifiers or regressors and make predictions from separated features and labels.
How it connects
Connects classification, regression, accuracy, Gini impurity, entropy, information gain, mean square error, and recommendation systems.

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 Grokking Machine Learning, Second Edition. The section links point to the parts of the book it draws on.