JOSH GORDON: Hey, everyone.
Welcome back.
In this episode, we'll write a decision tree classifier
from scratch in pure Python.
Here's an outline of what we'll cover.
I'll start by introducing the data set we'll work with.
Next, we'll preview the completed tree.
And then, we'll build it.
On the way, we'll cover concepts like decision tree learning,
Gini impurity, and information gain.
And you can find the code for this episode
in the description.
And it's available in two formats,
both as a Jupiter notebook and as a regular Python file.
OK, let's get started.
For this episode, I've written a toy data
set that includes both numeric and categorical attributes.
And here, our goal will be to predict the type of fruit,
like an apple or a grape, based on features
like color and size.
At the end of the episode, I encourage
you to swap out this data set for one of your own
and build a tree for a problem you care about.
Let's look at the format.
I've re-drawn it here for clarity.
Each row is an example.
And the first two columns provide features or attributes
that describe the data.
The last column gives the label, or the class,
we want to predict.
And if you like, you can modify this data set
by adding additional features or more examples,
and our program will work in exactly the same way.
Now, this data set is pretty straightforward,
except for one thing.
I've written it so it's not perfectly separable.
And by that I mean there's no way to tell apart
the second and fifth examples.
They have the same features, but different labels.
And this is so we can see how our tree handles this case.
Towards the end of the notebook, you'll
find testing data in the same format.
Now I've written a few utility functions that make it easier
to work with this data.
And below each function, I've written a small demo
to show how it works.
And I've repeated this pattern for every block of code
in the notebook.
Now to build the tree, we use the decision tree learning
algorithm called CART.
And as it happens, there's a whole family of algorithms
used to build trees from data.
At their core, they give you a procedure
to decide which questions to ask and when.
CART stands for Classification and Regression Trees.
And here's a preview of how it works.
To begin, we'll add a root node for the tree.
And all nodes receive a list of rows as input.
And the root will receive the entire training set.
Now each node will ask a true false question
about one of the features.
And in response to this question,
we split, or partition, the data into two subsets.
These subsets then become the input to two child nodes
we add to the tree.
And the goal of the question is to unmix the labels
as we proceed down.
Or in other words, to produce the purest possible
distribution of the labels at each node.
For example, the input to this node
contains only a single type of label,
so we'd say it's perfectly unmixed.
There's no uncertainty about the type of label.
On the other hand, the labels in this node are still mixed up,
so we'd ask another question to further narrow it down.
And the trick to building an effective tree
is to understand which questions to ask and when.
And to do that, we need to quantify how much a question
helps to unmix the labels.
And we can quantify the amount of uncertainty
at a single node using a metric called Gini impurity.
And we can quantify how much a question
reduces that uncertainty using a concept
called information gain.
We'll use these to select the best
question to ask at each point.
And given that question, we'll recursively build the tree
on each of the new nodes.
We'll continue dividing the data until there
are no further questions to ask, at which point
we'll add a leaf.
To implement this, first we need to understand
what type of questions can we ask about the data.
And second, we need to understand
how to decide which question to ask when.
Now each node takes a list of rows as input.
And to generate a list of questions
we'll iterate over every value for every feature that
appears in those rows.
Each of these becomes a candidate
for a threshold we can use to partition the data.
And there will often be many possibilities.
In code we represent a question by storing
a column number and a column value,
or the threshold we'll use to partition the data.
For example, here's how we'd write a question
to test if the color is green.
And here's an example for a numeric attribute
to test if the diameter is greater than or equal to 3.
In response to a question, we divide, or partition, the data
into two subsets.
The first contains all the rows for which the question is true.
And the second contains everything else.
In code, our partition function takes a question
and a list of rows as input.
For example, here's how we partition the rows based
on whether the color is red.
Here, true rows contains all the red examples.
And false rows contains everything else.
The best question is the one that reduces our uncertainty
the most.
And Gini impurity let's us quantify how much uncertainty
there is at a node.
Information gain will let us quantify how much
a question reduces that.
Let's work on impurity first.
Now this is a metric that ranges between 0 and 1
where lower values indicate less uncertainty, or mixing,
at a node.
It quantifies our chance of being incorrect if we randomly
assign a label from a set to an example in that set.
Here's an example to make that clear.
Imagine we have two bowls and one contains the examples
and the other contains labels.
First, we'll randomly draw an example from the first bowl.
Then we'll randomly draw a label from the second.
And now, we'll classify the example as having that label.
And Gini impurity gives us our chance of being incorrect.
In this example, we have only apples in each bowl.
There's no way to make a mistake.
So we say the impurity is zero.
On the other hand, given a bowl with five different types
of fruit in equal proportion, we'd
say it has an impurity of 0.8.
That's because we have a one out of five chance of being right
if we randomly assign a label to an example.
In code, this method calculates the impurity of a data set.
And I've written a couple examples
below that demonstrate how it works.
You can see the impurity for the first set is zero
because there's no mixing.
And here, you can see the impurity is 0.8.
Now information gain will let us find the question that reduces
our uncertainty the most.
And it's just a number that describes
how much a question helps to unmix the labels at a node.
Here's the idea.
We begin by calculating the uncertainty
of our starting set.
Then, for each question we can ask,
we'll try partitioning the data and calculating
the uncertainty of the child nodes that result.
We'll take a weighted average of their uncertainty
because we care more about a large set with low uncertainty
than a small set with high.
Then, we'll subtract this from our starting uncertainty.
And that's our information gain.
As we go, we'll keep track of the question that
produces the most gain.
And that will be the best one to ask at this node.
Let's see how this looks in code.
Here, we'll iterate over every value for the features.
We'll generate a question for that feature,
then partition the data on it.
Notice we discard any questions that fail to produce a split.
Then, we'll calculate our information gain.
And inside this function, you can
see we take a weighted average and the impurity of each set.
We see how much this reduces the uncertainty
from our starting set.
And we keep track of the best value.
I've written a couple of demos below as well.
OK, with these concepts in hand, we're ready to build the tree.
And to put this all together I think the most useful thing I
can do is walk you through the algorithm
as it builds a tree for our training data.
This uses recursion, so seeing it in action can be helpful.
You can find the code for this inside the Build Tree function.
When we call build tree for the first time,
it receives the entire training set as input.
And as output it will return a reference
to the root node of our tree.
I'll draw a placeholder for the root here in gray.
And here are the rows we're considering at this node.
And to start, that's the entire training set.
Now we find the best question to ask at this node.
And we do that by iterating over each of these values.
We'll split the data and calculate the information
gained for each one.
And as we go, we'll keep track of the question that
produces the most gain.
Now in this case, there's a useful question to ask,
so the gain will be greater than zero.
And we'll split the data using that question.
And now, we'll use recursion by calling build tree again
to add a node for the true branch.
The rows we're considering now are the first half
of the split.
And again, we'll find the best question to ask for this data.
Once more we split and call the build tree function
to add the child node.
Now for this data there are no further questions to ask.
So the information gain will be zero.
And this node becomes a leaf.
It will predict that an example is either
an apple or a lemon with 50% confidence
because that's the ratio of the labels in the data.
Now we'll continue by building the false branch.
And here, this will also become a leaf.
We'll predict apple with 100% confidence.
Now the previous call returns, and this node
becomes a decision node.
In code, that just means it holds a reference
to the question we asked and the two child nodes that result.
And we're nearly done.
Now we return to the root node and build the false branch.
There are no further questions to ask, so this becomes a leaf.
And that predicts grape with 100% confidence.
And finally, the root node also becomes a decision node.
And our call to build tree returns a reference to it.
If you scroll down in the code, you'll
see that I've added functions to classify data and print
the tree.
And these start with a reference to the root node,
so you can see how it works.
OK, hope that was helpful.
And you can check out the code for more details.
There's a lot more I have to say about decision trees,
but there's only so much we can fit into a short time.
Here are a couple of topics that are good to be aware of.
And you can check out the books in the description
to learn more.
As a next step, I'd recommend modifying the tree
to work with your own data set.
And this can be a fun way to build
a simple and interpretable classifier for use
in your projects.
Thanks for watching, everyone.
And I'll see you next time.