Hello!
In this video, we'll be covering decision trees
The first algorithm we will cover is the decision tree algorithm.
What exactly is a decision tree?
How do they help us classify?
How can I grow my own decision tree?
These may be some questions you have in mind from hearing the term, decision tree.
Hopefully you'll soon be able to answer these questions and a lot more by going through
this lesson!
Decision Trees are built by splitting the training set into distinct nodes, where one
node contains all of or most of, one category of the data.
These categories can be called subsets.
With the dataset divided, inputted out-of-sample data will be classified more easily when it
falls into a node that is strictly one subset of the data.
If so, there is a higher probability that the data point is the same classification
as the node it fell under.
So if we look at the diagram here, we can see that it's a weather classifier.
So, to make this more interesting, let's say that we want to go out for a run but the decision
to go out will be influenced by the weather forecast.
We start with the outlook, which can be sunny, overcast, or raining.
Our preference is to run on an overcast day, so if the forecast says it's going to be overcast,
then we'll definitely go for the run.
On the other hand, if it's sunny or raining, we'll need more details to help us determine
if we want to go out running.
The additional forecast variables can be things such as humidity, wind and rain.
For example, if the forecast is calling for high humidity then we're not going on our
run, but if it's normal, then we are!
Similarly with the wind on a rainy day.
If it's strong wind, then we're definitely not going, but if there's only going to be
a slight breeze, then we are.
Let's take a more in-depth look at entropy and information gain.
Here, we have our dataset at the root node consisting of 4 colors: red, blue, green,
and yellow.
There are 4 dots for each color, totaling 16 dots.
We?ll be using histograms to look at the chance that an out-of-sample data point would be
a certain color.
So we start off having an equal chance of 25% for all colors.
Let's say we make a binary split on the node . Note that in these examples, the attribute
used in the split will be ignored for simplification.
From this split, all of the red dots go to the left side, and the rest of the dots go
to the right side.
Now, let?s take a look at what the histogram looks like for this split!
A split that looks like this is ideal.
This would produce the most information gain, and greatly decrease the entropy.
Let's say we just stopped here, and we wanted to put an out-of-sample point into our tree.
We'll want to decide what color this point is.
Let's say that this point fulfills the condition to be on the left-hand side.
We can most likely say that this point should be red.
Next, let's quickly review some terminology that can apply to decision trees.
If some of these definitions don't make sense right now, don't worry, as we'll be going
through some examples that will clarify this.
First, we have a node.
In a node, we have a dataset that gets tested for a certain attribute.
The goal of the node is to split the dataset on an attribute.
Next is a leaf node, which is the terminal node in the tree that predicts the outcome.
There is also a root node, which appears at the top of tree and contains the entire dataset
for that tree.
Next, have the term, entropy.
Entropy is the amount of information disorder, or the amount of randomness in the data.
If we are talking about a decision tree, we can say, for example, that the entropy in
the node depends on how much random data is in that node.
Next, we have information gain.
This is the information collected that can increase the level of certainty in a particular
prediction.
We can think of information gain and entropy as opposites.
As entropy, or the amount of randomness, decreases, the information gain, or amount of certainty,
increases, and vice-versa.
There are also mathematical formulas that you can use to calculate the entropy and information
gain in each node to ensure you?ve made the best split.
However, examining those formulas is outside of
the scope of
this lesson.
Back to the tree.
The split we saw here is the best case scenario.
Most likely, we would see split that would look like this.
We can see that the split isn't perfect, but the right split has the highest chance of
being blue, but it's not 100% like the first split with red.
Let's also look at the histogram for this split.
And now, let's throw in another out-of-sample point.
Let's say that the point has the attributes to move to the right side twice.
What do you think this point will end up being?
Well, it has a high possibility of being blue . Remember, though, that the point could also
be green, since there was an equivalent number of green in the split.
It could even be yellow, but the chance of that would be a lot lower, since there would
be a higher chance of the point going to the left
Nonetheless, having more splits to increase the information gain would present a more
clear conclusion to what the point should be.
In the second split, there is less information gain then the first split.
We can see that there is a lot more entropy in the datasets here then here, since there
is more randomness in the data sets.
Alright, so we just looked at an example of information gain that demonstrated good gain,
as well as a more realistic example of it that still presented a decent amount of gain.
This time, we'll look at a quick example that demonstrates bad information gain.
We'll still be using the same dataset as before, which consists of 4 data points of 4 colors,
as well as the histogram.
Take a couple of seconds to look at the split now.
How do you think this split differs from the previous example?
We can see that a split like this provides zero information gain, insofar as there's
still the same probability of a point being red, blue, green, or yellow after the split
than before the split.
As such, Let's look at the histogram for this split.
As you can see, there is no information gain, therefore the entropy in the splits remains
the same.
Thus, a split like this is pointless.
Thanks for watching!