Well, sometimes the features simply do not provide enough information to get 100% accuracy (like in your case), even with a model a flexible as the Decision Tree.
The Decision Tree works by trying to split the data using condition statements (e.g. A < 1), but how does it choose which conditional statement is best? Well, we want the splits (conditional statements split the data in two, so we call it a "split") to split the data so that the target variable is separated into it's different classes, that way when we get a new instance and use the tree to classify it, we can say "This instance is 100% this class", because the leaf node only includes instances of this class. In other words, we want the conditional statements to split the data so that the nodes only include instances of one class. This is what impurity measures, how impure a node is (so the less impure the better).
So, now that we can measure the impurity of the data at a node, we can score conditional statements. All we have to do is simply get the weighted sum of impurity on both sides of the split:
$$\frac{m_{left}}{m}I_{left} + \frac{m_{right}}{m}I_{right}$$
where:
- $I_{left/right} = $ The impurity of the data on the left/right side.
- $m_{left/right} = $ The amount of data on the left/right side.
- $m = $ The total amount of data.
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.
Let's manually go through your toy dataset together to see this algorithm in action:
A B C | D
-----------
1 1 1 | 0
1 1 0 | 0
1 1 0 | 1
1 0 1 | 1
The first thing we have to establish is what impurity measure we'll use. A good default is "Gini Impurity", so I'll be using that one:
$$G_i = 1 - \sum_{k=1}^{n}p_{i,k}^2$$
where:
- $G_i = $ The gini impurity at the $i^{th}$ node.
- $p_{i,k} = $ The ratio of target class $k$ instances among all instances in the $i^{th}$ node.
Now, let's begin building the tree:
The first thing we have to do is find every combination of feature and value:
(A,0), (A,1), (B,0), (B,1), (C,0), (C,1),
then, we split the data using every combination and measure it's cost. Since all the features are binary here, splitting at (A,0) and (A,1) is the same thing, so we just need to measure one of the two, making us not need to specify what value we're splitting at.
Let's measure the cost of B:
First, we measure the impurity where B = 0, there's only one instance, so the gini impurity is $$1 - (\frac{0}{1})^2 - (\frac{1}{1})^2 = 1-1 = 0$$So it's completely pure. Then, for B = 1, the impurity is $$1 - (\frac{2}{3})^2 - (\frac{1}{3})^2 = 1 - \frac{5}{9} = \frac{4}{9}$$Finally, to get the cost, we just need to get the weighted sum of $0$ and $\frac{4}{9}$:
$$\frac{1}{4}*0 + \frac{3}{4}*\frac{4}{9} = \frac{1}{3}$$
There we have it! The cost of using B as the first split is $\frac{1}{3}$. As it turns out, this is the lowest cost we can get (A and C have a cost of $0.5$), so that will be our first node in our tree.
Left = 0
Right = 1
B
/ \
? ?
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$.
B
/ \
(D=1) ?
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.
B
/ \
(D=1) \
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.
B
/ \
(D=1)\
C
/ \
? (D=0)
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.
Left = 0
Right = 1
B
/ \
(D=1)\
C
/ \
(D=1) (D=0)
