0
$\begingroup$

Suppose I have a dataset

A B C D
1 1 1 0
1 1 0 0
1 1 0 1
1 0 1 1

Here A,B,C,D are my independent features and D is my dependent feature. Now if I make a decision tree here.

A -> Yes/No = 2/2 - > Based on value 1-> 2/2 So we go further for B. 
B -> Yes/No = 2/2 -> Based on value 1-> 1/2 So we go further for C
When B=1 & C = 1 then D = 0
When B=1 & C = 0 then D = 0 and as well as D = 1 too. 

So here we have a 50/50 chance, Or we can see we can't go further to get unique value to predict. So how does decision tree solve this problem?

$\endgroup$
1
$\begingroup$

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)
$\endgroup$
4
  • $\begingroup$ Thanks for this broad explanation. So the worst case scenario is only producing output at random. $\endgroup$ Feb 23 at 23:05
  • $\begingroup$ @HasibulIslamPolok Yes, that would be correct. Happy to be of help! $\endgroup$
    – MartinM
    Feb 24 at 8:11
  • $\begingroup$ Can you tell me in what happens in case of a (5 yes/2 no) situation? How does it take decision? Will it take yes for every time as most of the cases are yes? Or is there any probability theorem? $\endgroup$ Feb 24 at 10:17
  • $\begingroup$ @HasibulIslamPolok Precisely, it'll just say say every time, because there are more yes's than no's. $\endgroup$
    – MartinM
    Feb 24 at 10:20
0
$\begingroup$

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 condition statement is best? Well, it does this by measuring the "purity" of the split (conditional statements split the data in two, so we call it a "split"). The purity is simply how well the statement split up the target variable (so, a good split would be [2, 0], which basically translates to "If I did this split, I would get two $D = 0$ instances, and zero $D = 1$ instances.", and a bad split would be [1, 1], saying "With this split I would get one $D = 0$ instance and one $D = 1$ instance"). If the model finds that no further splits can reduce the purity, it stops.
If you want to look into it further, there are a couple of measures for measuring purity (or rather, impurity), the main ones being gini and entropy.

$\endgroup$
5
  • $\begingroup$ I get it. gini, entropy and information gain all works for finding the best route. But what happens when your best route fells in a condition of entropy 1 or I can say entropy is 1 bit. What happens then if it can't split into further unique nodes? $\endgroup$ Feb 21 at 0:55
  • $\begingroup$ @HasibulIslamPolok It stops? If none of the possible further splits have a lower entropy than the current node, it stops, and the current node becomes a leaf node. Is that what you meant? Sorry if my answer unclear about that. $\endgroup$
    – MartinM
    Feb 21 at 9:30
  • $\begingroup$ What exactly do you mean by "can't split into further unique nodes"? $\endgroup$
    – MartinM
    Feb 21 at 19:38
  • $\begingroup$ I meant the above scenario. When your leaf node is having 50/50 case. And using the information gain it's the best decision tree route. Then how will it take the decision then as there's no possibility of making pure subset. $\endgroup$ Feb 21 at 23:30
  • $\begingroup$ @HasibulIslamPolok Well, I have posted a new answer, that covers far more broadly the training of Decision Trees. My hope is that you can understand how it deals with the situation you're describing by looking at how Decision Trees work in general. $\endgroup$
    – MartinM
    Feb 22 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.