Try first

Explain to a colleague, in words, how to tell an apple from an orange using the fruit data from lesson 3036. You are not allowed to mention weights, sums, or distances.

Write your explanation down. It will probably start with “if”.

You wrote a decision tree

Most people write something like: if the orangeness is above about 0.5, it is an orange, otherwise it is an apple.

That is a decision tree with one question in it. Add more questions, each one narrowing what is left, and you have the general form.

if orangeness > 0.5
    if weight > 200  ->  large orange
    else             ->  orange
else
    if diameter > 7.5 ->  large apple
    else              ->  apple

Every node asks about one feature against one threshold. Every leaf gives an answer. Prediction is walking down from the top, answering questions, until you reach a leaf.

The whole model is readable. That is not a small thing. Show the tree above to someone with no background and they can follow it and disagree with it, which is not true of any other model in this course.

Representing and using one

function predictTree(node, x) {
  if (node.leaf !== undefined) return node.leaf;
  return x[node.feature] <= node.threshold
    ? predictTree(node.left, x)
    : predictTree(node.right, x);
}

const handTree = {
  feature: 2, threshold: 0.5,
  left:  { leaf: "apple" },
  right: { leaf: "orange" },
};

A node is either a leaf with an answer, or a question with two children. Prediction is four lines of recursion.

Growing one from data

The question is which feature and which threshold to split on. Try all of them and keep the split that separates the classes best.

function bestSplit(data, scoreFn) {
  let best = null;
  const nFeatures = data[0].x.length;
  for (let f = 0; f < nFeatures; f++) {
    const values = [...new Set(data.map(r => r.x[f]))].sort((a, b) => a - b);
    for (let i = 0; i < values.length - 1; i++) {
      const t = (values[i] + values[i + 1]) / 2;
      const left  = data.filter(r => r.x[f] <= t);
      const right = data.filter(r => r.x[f] >  t);
      if (!left.length || !right.length) continue;
      const score = (left.length * scoreFn(left) + right.length * scoreFn(right)) / data.length;
      if (!best || score < best.score) best = { feature: f, threshold: t, score, left, right };
    }
  }
  return best;
}

Candidate thresholds sit halfway between consecutive values that actually appear, since anything between two observed values splits the data identically.

The score of a split is the weighted average of the two sides’ scores, weighted by how many rows went each way. A split that puts two rows on one side and two hundred on the other is mostly judged by the large side, which is correct.

scoreFn measures how mixed a group is. That is the next lesson, and it is the only piece missing.

Building the whole tree

function grow(data, scoreFn, depth = 0, maxDepth = 4, minRows = 2) {
  const labels = data.map(r => r.y);
  const majority = mode(labels);

  if (depth >= maxDepth || data.length < minRows || new Set(labels).size === 1) {
    return { leaf: majority, n: data.length };
  }
  const s = bestSplit(data, scoreFn);
  if (!s) return { leaf: majority, n: data.length };

  return {
    feature: s.feature,
    threshold: s.threshold,
    n: data.length,
    left:  grow(s.left,  scoreFn, depth + 1, maxDepth, minRows),
    right: grow(s.right, scoreFn, depth + 1, maxDepth, minRows),
  };
}

Find the best split, then do the same thing to each side. Stop when the group is pure, too small, or too deep.

The stopping rules are the important part, and they are what stops the tree memorizing. Without them it keeps splitting until every leaf holds one row, which classifies the training set perfectly and is worthless. Same failure as the degree 9 polynomial, same cause.

What the boundary looks like

Draw a trained tree with the decision map code and you get rectangles. Every boundary is horizontal or vertical, because every question compares one feature to one number.

A diagonal boundary has to be approximated as a staircase, which takes many splits to do badly. So a tree handles the ring from lesson 3077 easily, by boxing it in, and handles a simple diagonal line worse than logistic regression does.

Different models fail at different shapes. Neither is generally better.

What to watch

Trees are unstable. Change one row and the top split can change, which changes every split below it, and you get a completely different tree that performs about the same.

That instability is a real weakness on its own, and lesson 3109 turns it into the basis of the best method in this section.

Exercises

1. Write mode, then print a trained tree as indented text.
2. Sweep maxDepth from 1 to 10 and plot training and validation accuracy. Find the U shape.
3. Confirm that scaling features makes no difference at all to a tree. Explain why, from the code.
4. Change the leaf to return the mean of y instead of the mode, and use it for regression on the house data.