\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

ML02.1 · Decision trees

A free, illustrated module of 4 lessons and one interactive in ML02 Supervised Learning: Trees, Ensembles and Kernels: A tree is a list of questions; Impurity: Gini and entropy; Growing a tree greedily; Pruning and the instability of a single tree.

ML02.1 L2 · Intermediate 4 lessons · about 115 min Live · in review

Part of ML02 Supervised Learning: Trees, Ensembles and Kernels in the Machine Learning track.

A decision tree answers by asking one yes-or-no question about one feature at a time, and in doing so it cuts the feature space into rectangles. These four lessons read a tree as questions and as rectangles, measure how mixed a node is with Gini impurity and entropy, grow a tree greedily with the CART algorithm for classes and for numbers, and then cut it back with cost-complexity pruning, ending with the instability that makes a single tree fragile and that the ensembles of the next modules cure.

What you need first. Training, validation and test sets and k-nearest neighbours (ML01.2, ML01.3), the mean as the best constant prediction (ML01.4), overfitting, bias and variance (ML01.8), and cross-validation (ML01.9). Logarithms to base 2 (M01.4) for entropy. NumPy for the code.

Lessons

1. A tree is a list of questions ML02.1.1 25 min

   A decision tree asks one yes-or-no question about one feature at a time until it reaches an answer. Read a tree both as a diagram and as rectangles of the feature plane, walk a new point to its leaf, and see why a leaf predicts the majority class or the mean.

2. Impurity: Gini and entropy ML02.1.2 30 min

   To choose a tree’s questions, a computer needs a number for how mixed a node is. Meet the misclassification rate, the Gini impurity and entropy, score a split by the drop in size-weighted impurity, and find the best first question for the twelve points by hand.

3. Growing a tree greedily ML02.1.3 30 min

   The CART algorithm grows a tree by finding the best single split, then doing the same again in each child. Build it from scratch in NumPy for classes and for numbers, count what the search costs, see where greed fails, and match scikit-learn split for split.

4. Pruning and the instability of a single tree ML02.1.4 30 min

   A fully grown tree fits its training data perfectly and overfits. Prune it with minimal cost-complexity, derive the weakest-link sequence by hand, choose the price per leaf by cross-validation, and measure how much a single tree changes when the data are resampled.

The interactive

ML02.1-X1 · Tree grower. The twelve points and up to twenty more that you add or drag. Press step to make the best next split under Gini or entropy and watch the plane cut into rectangles beside the growing tree diagram, with each node’s counts and impurity, then lower the depth slider to prune it back. It lives in Growing a tree greedily.