Splitting on One Question

A single yes or no question divides the data into two groups, and a measure of how mixed a group is turns the choice of question into arithmetic.

One question, two groups

Here is a table of loan applications with an outcome attached. Twelve rows,

three inputs, and a column saying whether the loan was repaid.

Ask one question: was the applicant's income above thirty thousand? Every row

answers yes or no, so the twelve rows become two groups. That is the entire

operation this course is built from, repeated.

FIG 1Twelve applications, split three different ways

	rows on the yes side	repaid among them	rows on the no side	repaid among them
income above 30	7	6	5	1
age above 40	6	4	6	3
has other debts	4	1	8	6
lives in a city	8	5	4	2

Four candidate questions on the same twelve rows. The first produces a yes group that is six repaid out of seven and a no group that is one out of five, which is a clean division. The second produces four out of six against three out of six, which is barely a division at all. The method needs a number that says the first is better.

Notice what a question does not require. It compares one column against a

threshold, so the columns never have to be on comparable scales, never have to

be rescaled, and can be measured in entirely different units. That is the

first practical advantage of this family over everything in the previous

course, and it is a consequence of the question being about one column at a

time.

Measuring how mixed a group is

A group of rows is pure if every one of them has the same outcome, and mixed

if they are split. The measure has to be zero for pure and largest for an even

split, and it has to work for any proportion in between.

FIG 2The two standard measures of mixedness

: the fraction of the group with the first outcome
: the first measure, which is the chance that two rows drawn at random disagree
: the second measure, which is the number of bits needed to say which outcome a row has

Both are zero when p is zero or one and largest at a half, where the first gives 0.5 and the second gives 1. They are different numbers and they rank questions almost identically, so arguments about which to use are usually arguments about nothing.

The first measure has a reading worth keeping. Pick two rows from the group at

random; the measure is the chance that they have different outcomes. A pure

group gives zero because any two rows agree. An even split gives a half.

FIG 3Both measures, across the whole range

the disagreement measurethe bits measure

The same shape at different heights: zero at both ends, a single peak in the middle, symmetric. The bits measure rises more steeply near the ends, so it rewards a question that produces a nearly pure group slightly more, which is the only practical difference between them.

What a question is worth

A question is worth the amount of mixedness it removes. Compute the mixedness

of the whole group, then the mixedness of each side, then subtract.

The subtlety is in the weighting. The two sides are not the same size, and the

mixedness after the question must be the average of the two sides weighted by

how many rows each holds. Without that weighting the method would love a

question that peels off a single pure row and leaves eleven mixed ones, since

one side would be perfectly clean.

FIG 4The value of a question

: the mixedness of the group before the question
: how many rows went each way
: the total, which is the two of them added

This is never negative, which is a useful fact: no question can make the weighted mixedness worse. So a question is always at least harmless, and the search is for the one that helps most rather than for one that does not hurt.

FIG 5The four candidate questions, scored

step	question	mixedness after, weighted	value	verdict
1	before any question	0.486
2	income above 30	0.276	0.210	the best of the four
3	lives in a city	0.479	0.007	almost worthless
4	has other debts	0.375	0.111	moderate
5	age above 40	0.472	0.014	weak

5 steps

The ordering matches what the first figure suggested by eye, which is the point of checking it on a case small enough to see. Income is chosen, and the tree in the next lesson will begin with it.

Finding the best question

Choosing means searching, and the search is finite.

For a column of numbers, every threshold between the same pair of neighbouring

values produces the same split, so there are only as many distinct questions

as there are gaps between distinct values. Sort the column, try the midpoint

of each gap, keep the best. For a column of categories, the question is

whether the value is in some subset, and for a small number of categories all

the subsets can be tried.

FIG 6The whole search, on one column at a time

python

def mixedness(rows):
    if not rows: return 0.0
    p = sum(r[-1] for r in rows) / len(rows)
    return 1 - p * p - (1 - p) * (1 - p)
def best_question(rows, n_inputs):
    base, n, best = mixedness(rows), len(rows), (0.0, None, None)
    for col in range(n_inputs):
        values = sorted({r[col] for r in rows})
        for a, b in zip(values, values[1:]):
            cut = (a + b) / 2
            yes = [r for r in rows if r[col] > cut]
            no  = [r for r in rows if r[col] <= cut]
            after = (len(yes) * mixedness(yes) + len(no) * mixedness(no)) / n
            if base - after > best[0]:
                best = (base - after, col, cut)
    return best  # value, which column, which threshold
print("sort each column, try each gap, keep the best: that is the whole of it")

Two loops and a subtraction. The cost is the number of columns multiplied by the number of rows, times a sort, and that is the cost of one split in every tree in this course. Everything later is this function called many times.

The thing to take from this lesson is how little machinery is involved. There

are no knobs to turn, no step size, no landscape, no derivatives. A question

is chosen by trying all of them and keeping the best, which is a completely

different way of fitting a model, and it is why this family behaves so

differently from the one in the previous course.

The next lesson does the obvious thing: apply this to each group that comes

out, and keep going.

Recap

A question divides the rows into two groups, and a good question is one whose groups are each more uniform than the original was.
Mixedness is measured by a number that is zero when a group is all one kind and largest when it is evenly split.
The value of a question is the mixedness before it minus the weighted mixedness after it, which makes choosing a question a search over a finite list.

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

NextGrowing a Whole Tree →