Return to Answer

Now, let's figure out what should go on the left branch (all instances where $B=0$).
The thing is, there's only one instance where $B=0$, and that means if we were to split the data here, one side would get zero instances, which isn't allowed, so we won't make a split here, but rather a leaf node. We just need to find which target class has the most instances. In our case, that would be $D=1$.

Now, let's figure out what should go on the left branch (all instances where $B=0$).
The thing is, there's only one instance, and that means if we were to split the data here, one side would get zero instances, which isn't allowed, so we won't make a split here, but rather a leaf node. We just need to find which target class has the most instances. In our case, that would be $D=1$.

Now, for the right branch. First thing's first we need to know the impurity here (so we know what we have to beat if we want to make a split), we actually already found it when computing the cost of B (above), and it came out to be $\frac{4}{9}$. Now, we can compute the cost of all possible splits here:
A - $\frac{4}{9}$
B - $\frac{4}{9}$
C - $\frac{1}{3}$
As we can see, the best choice is C, with cost $\frac{1}{3}$, and since it is lower than the impurity here ($\frac{4}{9}$), we will make the next node in our tree C.

We can see that on the right branch, there's only one C = 1 instance, meaning that it must turn into a leaf node. And since this one instance has target class D = 0, that's what our leaf will return.

Now finally, let's look at the second branch from the C node. Since it has more than one instance, we can compute the costs:
A - $\frac{1}{2}$
B - $\frac{1}{2}$
C - $\frac{1}{2}$
As we can see, all of the features have a cost of $\frac{1}{2}$, but $\frac{1}{2}$ is no better than the impurity here (also $\frac{1}{2}$)! That means no split we do can make the nodes purer, and thus, instead of making another split, we will make a leaf node.
Since both target classes have the same number of instances, it doesn't matter which one we choose, and we can do so at random.

Now, for the right branch (all instances where $B=1$). First thing's first we need to know the impurity here (so we know what we have to beat if we want to make a split), we actually already found it when computing the cost of B (above), and it came out to be $\frac{4}{9}$. Now, we can compute the cost of all possible splits here:
A - $\frac{4}{9}$
B - $\frac{4}{9}$
C - $\frac{1}{3}$
As we can see, the best choice is C, with cost $\frac{1}{3}$, and since it is lower than the impurity here ($\frac{4}{9}$), we will make the next node in our tree C.

We can see that on the right branch (all instances where $B=1$ and $C=1$), there's only one C = 1 instance, meaning that it must turn into a leaf node. And since this one instance has target class D = 0, that's what our leaf will return.

Now finally, let's look at the left branch from the C node (all instances where $B=1$ and $C=0$). Since it has more than one instance, we can compute the costs:
A - $\frac{1}{2}$
B - $\frac{1}{2}$
C - $\frac{1}{2}$
As we can see, all of the features have a cost of $\frac{1}{2}$, but $\frac{1}{2}$ is no better than the impurity here (also $\frac{1}{2}$)! That means no split we do can make the nodes purer, and thus, instead of making another split, we will make a leaf node.
Since both target classes have the same number of instances, it doesn't matter which one we choose, and we can do so at random.

We can call this the cost function of a split, the split with the lowest cost is considered the best.
So, when the Decision Tree is searching for the best split, it will consider every feature, splitting it at every value we see that feature take in the data, and assign every combination a cost. Once it has gone through all possible combinations, it'll simply choose the conditional statement with the lowest cost.
However, if the lowest cost found is no better than the cost of the current node, that means there's nothing it can do to make the data here more pure, and so it'll stop trying to do so and just make the next node a leaf node.

Now, for the right branch. Since it has more than one instance, we can compute the cost of all possible splits:
A - $\frac{4}{9}$
B - $\frac{4}{9}$
C - $\frac{1}{3}$
As we can see, the best choice is C, with cost $\frac{1}{3}$, and since it is lower than the cost of the current node (B with cost $\frac{4}{9}$), we will make the next node in our tree C.

Now finally, let's look at the second branch from the C node. Since it has more than one instance, we can compute the costs:
A - $\frac{1}{2}$
B - $\frac{1}{2}$
C - $\frac{1}{2}$
As we can see, all of the features have a cost of $\frac{1}{2}$, and since $\frac{1}{2}$ is bigger than the cost of the current node (C with cost $\frac{1}{3}$), that means no split we do can make the nodes purer, and thus, instead of making another split, we will make a leaf node.
Since both target classes have the same number of instances, it doesn't matter which one we choose, and we can do so at random.

We can call this the cost function of a split, the split with the lowest cost is considered the best.
So, when the Decision Tree is searching for the best split, it will consider every feature, splitting it at every value we see that feature take in the data, and assign every combination a cost. Once it has gone through all possible combinations, it'll simply choose the conditional statement with the lowest cost.
However, if the lowest cost found is no better than the impurity of the current node, that means there's nothing it can do to make the data here more pure, and so it'll stop trying to do so and just make the next node a leaf node.

Now, for the right branch. First thing's first we need to know the impurity here (so we know what we have to beat if we want to make a split), we actually already found it when computing the cost of B (above), and it came out to be $\frac{4}{9}$. Now, we can compute the cost of all possible splits here:
A - $\frac{4}{9}$
B - $\frac{4}{9}$
C - $\frac{1}{3}$
As we can see, the best choice is C, with cost $\frac{1}{3}$, and since it is lower than the impurity here ($\frac{4}{9}$), we will make the next node in our tree C.

Now finally, let's look at the second branch from the C node. Since it has more than one instance, we can compute the costs:
A - $\frac{1}{2}$
B - $\frac{1}{2}$
C - $\frac{1}{2}$
As we can see, all of the features have a cost of $\frac{1}{2}$, but $\frac{1}{2}$ is no better than the impurity here (also $\frac{1}{2}$)! That means no split we do can make the nodes purer, and thus, instead of making another split, we will make a leaf node.
Since both target classes have the same number of instances, it doesn't matter which one we choose, and we can do so at random.