Growing a Whole Tree

Last timeSplitting on One Question

Applying the same question search to each group that comes out of the last one builds a tree, and a prediction is made by following a case down to a leaf.

Do it again

The first lesson produced two groups. Each of those groups is a table of rows

with outcomes attached, which is exactly the thing the first lesson knows how

to split.

So split it. And split what comes out of that. Keep going until a group is

pure, or until some rule says stop, and what has been built is a tree.

FIG 1The whole tree growing procedure

python

def grow(rows, n_inputs, depth=0, max_depth=3, min_rows=2):
    labels = [r[-1] for r in rows]
    if depth >= max_depth or len(rows) < min_rows or len(set(labels)) == 1:
        return {"leaf": sum(labels) / len(labels), "n": len(rows)}
    value, col, cut = best_question(rows, n_inputs)
    if value <= 0:
        return {"leaf": sum(labels) / len(labels), "n": len(rows)}
    yes = [r for r in rows if r[col] > cut]
    no  = [r for r in rows if r[col] <= cut]
    return {"col": col, "cut": cut, "n": len(rows),
            "yes": grow(yes, n_inputs, depth + 1, max_depth, min_rows),
            "no":  grow(no,  n_inputs, depth + 1, max_depth, min_rows)}
print("one call to the search from the previous lesson, then the same function twice")

Eleven lines, of which the last three are the recursion. Nothing has been added since the previous lesson: the search is the same function, and growing a tree is calling it on each group it produces. The three conditions at the top are the stopping rules, which the next lesson is about.

A prediction is made by starting at the top with a new case, answering each

question as it comes, and reporting whatever is at the leaf that is reached.

Three or four comparisons and the answer is out, however large the tree and

however much data it was grown on.

FIG 2One application travelling down the tree

step	where it is	question asked	answer	rows remaining
1	the top	income above 30	yes	7 of 12
2	second level	has other debts	no	5 of 7
3	third level	age above 40	yes	3 of 5
4	a leaf	none		3, all repaid

4 steps

Three questions and the case has landed. The leaf holds three training rows, all of which repaid, so the prediction is that this one will too. The number of rows in the leaf is worth carrying around, because a leaf holding three rows is much weaker evidence than one holding three hundred.

A path is a rule

Follow one route from the top to a leaf and read the questions in order: income

above thirty thousand, no other debts, age above forty. That is a rule, and the

leaf is what the rule concludes.

A tree is therefore a set of rules. Every case satisfies exactly one of them,

because the questions at each level send it one way or the other, so the rules

cover everything and never overlap. That is a genuinely different kind of

object from the models in the previous course, where every input contributed

to every prediction.

The lesson stops here

4 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

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

Growing a Whole Tree

Do it again

A path is a rule

4 more paragraphs to go

This is the reading half

Read alongside