Try first

Three groups of ten fruits.

A: 10 apples, 0 oranges
B:  5 apples, 5 oranges
C:  9 apples, 1 orange

Rank them from most mixed to least mixed. Then try to write a formula that produces those rankings as numbers. This is harder than it looks and the attempt is worth the time.

What the formula has to do

B is worst, C is nearly pure, A is perfect. So we want a number that is 0 for A, large for B, and small for C.

Two formulas are in common use, and both do the job.

function gini(data) {
  const counts = {};
  for (const r of data) counts[r.y] = (counts[r.y] || 0) + 1;
  let s = 0;
  for (const k in counts) {
    const p = counts[k] / data.length;
    s += p * p;
  }
  return 1 - s;
}

function entropy(data) {
  const counts = {};
  for (const r of data) counts[r.y] = (counts[r.y] || 0) + 1;
  let s = 0;
  for (const k in counts) {
    const p = counts[k] / data.length;
    if (p > 0) s -= p * Math.log2(p);
  }
  return s;
}

Check them on your three groups. Gini gives 0, 0.5 and 0.18. Entropy gives 0, 1.0 and 0.47. Same ranking, different scales.

What entropy means

Entropy is the average number of yes/no questions needed to identify one item’s label, if you ask optimally.

Group B is a fifty-fifty mix, so one question settles it: exactly 1 bit. Group A needs no questions, because you already know the answer: 0 bits. Group C is mostly apples, so usually you need almost nothing and occasionally more, averaging 0.47 bits.

That reading is worth holding on to. Entropy measures how much you do not know, in bits. It is the same quantity that sets the limit on how far a file can be compressed, and it came from communication theory rather than from statistics.

Gini has a similar reading: the chance of being wrong if you guess a label at random using the group’s own proportions. It is cheaper to compute because there is no logarithm, and in practice the two almost always choose the same splits.

Information gain

Now the point. A split is good if it reduces uncertainty, and you can measure that directly.

function informationGain(data, feature, threshold) {
  const left  = data.filter(r => r.x[feature] <= threshold);
  const right = data.filter(r => r.x[feature] >  threshold);
  if (!left.length || !right.length) return 0;
  const after = (left.length * entropy(left) + right.length * entropy(right)) / data.length;
  return entropy(data) - after;
}

Uncertainty before, minus average uncertainty after. That difference is information gain: how many bits this question bought you.

Try it on the fruit data.

const fruitRows = fruit.map(r => ({ x: r.x, y: r.y }));
log("start entropy", entropy(fruitRows).toFixed(3));
log("split on weight     0.5", informationGain(fruitRows, 0, 190).toFixed(3));
log("split on diameter   7.2", informationGain(fruitRows, 1, 7.2).toFixed(3));
log("split on orangeness 0.5", informationGain(fruitRows, 2, 0.5).toFixed(3));

The orangeness split gains a full bit, which is everything there was to gain, because it separates the classes completely. The other two gain very little.

Look at what that produced. The tree just discovered, by measurement, the thing lesson 3036 asked you to notice by eye: orangeness is the useful column and the other two are not. No labels on the features, no domain knowledge, just counting.

Where it misleads

Information gain favors features with many distinct values, and it does so for a bad reason.

Take a customer ID column. Every value is unique, so splitting on it produces groups of one, every group is perfectly pure, and the gain is maximal. The tree will happily choose it and will have learned nothing that transfers to a new customer.

The standard fix is gain ratio, which divides the gain by how much the split fragments the data, penalizing splits that produce many tiny groups. Being aware of the problem matters more than the fix: any measure that rewards purity will reward memorization if you let it.

What to watch

Both measures are greedy. bestSplit picks whichever single question looks best right now, with no consideration of what will be available two levels down. Sometimes a mediocre first split enables two excellent second splits, and this method will never find that.

Finding the genuinely best tree is computationally infeasible, so every practical tree algorithm is greedy. It is a known and accepted compromise.

Exercises

  1. Compute gini and entropy for a 10-way even split. Which grows faster with the number of classes?
  2. Plot entropy against p for two classes, from 0 to 1. Where is the maximum, and why there?
  3. Add an ID column to the fruit data and confirm the tree splits on it. Then implement gain ratio and confirm it does not.
  4. Build a dataset where the greedy choice is provably worse than the best two level tree.
PreviousNext