Let’s Write a Decision Tree Classifier from Scratch - Machine Learning Recipes #8

Summary

In this educational video, Josh Gordon teaches viewers how to build a decision tree classifier from scratch using Python. He introduces a toy dataset to predict fruit types based on attributes like color and size. The tutorial covers decision tree learning, Gini impurity, and information gain. The code is available in Jupyter notebook and Python file formats. The video encourages swapping the dataset for personal projects, promoting hands-on learning.

Takeaways

• 🌳 The tutorial focuses on building a decision tree classifier from scratch using pure Python.
• 📊 The dataset used is a toy dataset with both numeric and categorical attributes, aiming to predict fruit types based on features like color and size.
• 📝 The data set is intentionally not perfectly separable to demonstrate how the tree handles overlapping examples.
• 🔍 The CART algorithm is introduced for decision tree learning, standing for Classification and Regression Trees.
• 📉 Gini impurity is explained as a metric for quantifying the uncertainty or impurity at a node, with lower values indicating less mixing of labels.
• 🌐 Information gain is discussed as a concept for selecting the best question to ask at each node, aiming to reduce uncertainty.
• 🔑 The process of partitioning data into subsets based on true or false responses to a question is detailed.
• 🛠️ Utility functions are provided to assist with data manipulation, and demos are included to illustrate their usage.
• 🔄 Recursion is used in the 'Build Tree' function to iteratively split the data and build the tree structure.
• 📚 The video concludes with suggestions for further learning and encourages viewers to apply the concepts to their own datasets.

Q & A

What is the main topic of the video?

The main topic of the video is building a decision tree classifier from scratch in pure Python.

What dataset is used in the video to demonstrate the decision tree classifier?

A toy dataset with both numeric and categorical attributes is used, where the goal is to predict the type of fruit based on features like color and size.

What is the purpose of the dataset not being perfectly separable?

The dataset is not perfectly separable to demonstrate how the decision tree handles cases where examples have the same features but different labels.

What utility functions are mentioned in the script to work with the data?

The script mentions utility functions that make it easier to work with the data, with demos provided to show how they work.

What does CART stand for and what is its role in building the decision tree?

CART stands for Classification and Regression Trees, which is an algorithm used to build trees from data by deciding which questions to ask and when.

How does the decision tree algorithm decide which question to ask at each node?

The decision tree algorithm decides which question to ask at each node by calculating the information gain and choosing the question that produces the most gain.

What is Gini impurity and how is it used in the decision tree?

Gini impurity is a metric that quantifies the uncertainty or mixing at a node, and it is used to determine the best question to ask at each point in the decision tree.

How is information gain calculated in the context of the decision tree?

Information gain is calculated by starting with the uncertainty of the initial set, partitioning the data based on a question, calculating the weighted average uncertainty of the child nodes, and subtracting this from the starting uncertainty.

What is the role of recursion in building the decision tree?

Recursion plays a role in building the decision tree by allowing the build tree function to call itself to add nodes for both the true and false branches of the tree.

How does the video conclude and what is the recommendation for the viewers?

The video concludes by encouraging viewers to modify the tree to work with their own datasets as a way to build a simple and interpretable classifier for their projects.

Outlines

00:00

🌳 Introduction to Building a Decision Tree Classifier

Josh Gordon introduces a tutorial on constructing a decision tree classifier from scratch using Python. The episode's agenda includes an introduction to the dataset, a preview of the completed tree, and a step-by-step guide to building the tree. Key concepts such as decision tree learning, Gini impurity, and information gain are discussed. The dataset, designed to predict fruit types based on attributes like color and size, is intentionally not perfectly separable to demonstrate the tree's handling of such cases. The code for the episode is available in both Jupyter notebook and Python file formats. The tutorial encourages viewers to experiment with their own datasets and features.

05:01

📊 Understanding Gini Impurity and Information Gain

The script delves into the metrics used to build an effective decision tree: Gini impurity and information gain. Gini impurity measures the uncertainty at a node, with lower values indicating less mixing of labels. It's illustrated with examples, including a scenario with no uncertainty (impurity of zero) and one with high uncertainty (impurity of 0.8). Information gain quantifies how much a question reduces uncertainty, calculated by comparing the initial uncertainty with the weighted average uncertainty of the partitions created by the question. The process involves iterating over feature values to generate questions, partitioning data, and calculating information gain. The script includes code examples and demos to clarify these concepts and concludes with a walkthrough of the algorithm used to build the tree, emphasizing the recursive nature of the process.

Keywords

💡Decision Tree Classifier

A decision tree classifier is a type of machine learning model that uses a tree-like graph of decisions to predict the value of a target variable based on its input features. In the video, the host demonstrates how to build a decision tree classifier from scratch using Python. The classifier is used to predict the type of fruit based on attributes like color and size, illustrating the practical application of this machine learning technique.

💡Gini Impurity

Gini impurity is a measure used in decision trees to quantify the uncertainty or 'impurity' of a node during the training process. It is calculated as the probability of a randomly chosen element from the node being incorrectly classified. In the script, Gini impurity is used to determine which feature split will yield the 'purest' subset, thus guiding the construction of the decision tree to maximize information gain.

💡Information Gain

Information gain refers to the reduction in uncertainty or impurity that results from partitioning a dataset based on an attribute. It is a key concept in the construction of decision trees, as it helps in selecting the best feature to split the data at each node. In the video, information gain is used to decide which questions to ask at each node in order to create a tree that accurately classifies the input data.

💡CART

CART stands for Classification and Regression Trees, which is an algorithm used to construct binary trees from data. It is a widely used method for building decision trees. In the script, CART is introduced as the algorithm that will be used to build the decision tree classifier, emphasizing its role in handling both classification and regression tasks.

💡Numeric and Categorical Attributes

Numeric and categorical attributes are types of features that describe data. Numeric attributes are quantitative, such as size or weight, while categorical attributes are qualitative, such as color or type. The script mentions that the toy dataset includes both types of attributes, which are used as inputs for the decision tree classifier to predict the type of fruit.

💡Toy Dataset

A toy dataset is a small, simplified dataset used for demonstration or testing purposes. In the video, the host has created a toy dataset with both numeric and categorical attributes to illustrate the process of building a decision tree classifier. This dataset is used to predict the type of fruit, and it is intentionally not perfectly separable to show how the tree handles such cases.

💡Feature

In the context of machine learning, a feature is an individual measurable property or characteristic of a phenomenon being observed. Features are used as inputs for the model. The script discusses features such as color and size, which are used to describe the data and help the decision tree classifier make predictions.

💡Label

In machine learning, a label is the target variable that the model is trying to predict. It represents the correct answer or value associated with a given set of features. In the video, the label is the type of fruit that the decision tree classifier aims to predict based on the input features.

💡Recursion

Recursion is a method in programming where a function calls itself in order to solve a problem. In the context of the video, recursion is used in the 'build tree' function to construct the decision tree. The function calls itself with subsets of the data until it reaches a base case where no further questions can be asked, and a leaf node is added.

💡Leaf Node

A leaf node is a terminal node in a decision tree that does not have any child nodes. It represents a decision or prediction made by the tree. In the script, leaf nodes are created when there are no further questions to ask, and the node makes a prediction based on the majority label in the subset of data it represents.

Highlights

Introduction to building a decision tree classifier from scratch in Python.

Outline of topics covered including dataset introduction, preview of the completed tree, and building process.

Availability of code in two formats: Jupyter notebook and regular Python file.

Description of a toy dataset with numeric and categorical attributes for predicting fruit type.

Encouragement for viewers to modify the dataset and apply the tree to their own problems.

Explanation of dataset format with examples and attributes.

Discussion on the dataset's non-separability to demonstrate tree handling of conflicting examples.

Introduction of utility functions and their demonstration for easier data manipulation.

Overview of the CART algorithm for decision tree learning.

Description of the tree-building process starting with a root node and partitioning data.

Explanation of how to quantify uncertainty at a node using Gini impurity.

Introduction to the concept of information gain for selecting the best questions to ask.

Detailed walk-through of the algorithm's recursive nature in building the tree.

Demonstration of how to handle data partitioning based on questions asked.

Calculation of Gini impurity to measure node uncertainty.

Explanation of information gain and its role in choosing the best question to ask.

Practical implementation of the build tree function using recursion.

Final tree construction with decision nodes and leaf nodes based on information gain.

Additional functions for classifying data and printing the tree for visualization.

Recommendation for next steps, including modifying the tree with personal datasets.

Conclusion and a prompt for viewers to explore more about decision trees through suggested books.

Transcripts

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.