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. 964
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 / \ ? ? 743