3
$\begingroup$

In a decision tree, Gini Impurity[1] is a metric to estimate how much a node contains different classes. It measures the probability of the tree to be wrong by sampling a class randomly using a distribution from this node:

$$ I_g(p) = 1 - \sum_{i=1}^J p_i^2 $$

If we have 80% of class C1 and 20% of class C2, labelling randomly will then yields 1 - 0.8 x 0.8 - 0.2 x 0.2 = 0.32 Gini impurity value.

However, assigning randomly a class using the distribution seems like a bad strategy compared with simply assigning the most represented class in this node (in above example, you would just label C1 all the time and get only 20% of error instead of 32%).

In that case, I would be tempted to simply use this as a metric, since it is also the probability of mislabeling :

$$ I_m(p) = 1 - \max_i [ p_i] $$

Is there a deeper reason to use Gini and/or a good reason not to use this approach instead ? (In other words, Gini seems to over-estimate the mislabellings that will happen, isn't it ?)

[1] https://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity


EDIT: Motivation

Suppose you have two classes $C_1$ and $C_2$, with probabilities $p_1$ and $p_2$ ($1 \ge p_1 \ge 0.5 \ge p_2 \ge 0$, $p_1 + p_2 = 1$).

You want to compare strategy "always label $C_1$" with strategy "label $C_1$ with $p_1$ probability, and $C_2$ with $p_2$ probability", thus the probability of success are respectively $p_1$ and $p_1^2 + p_2^2$.

We can rewrite this second one to:

$$ p_1^2 + p_2^2 = p_1^2 + 2p_1p_2 - 2p_1p_2 + p_2^2 = (p_1 + p_2)^2 - 2p_1p_2 = 1 - 2p_1p_2 $$

Thus, if we substract it to $p_1$:

$$ p_1 - 1 + 2p_1p_2 = 2p_1p_2 - p_2 = p_2 ( 2p_1 - 1) $$

Since $p_1 \ge 0.5$, then $p_2 ( 2p_1 - 1) \ge 0$, and thus:

$$ p_1 \ge p_1^2 + p_2^2 $$

So choosing the class with highest priority is always a better choice.


EDIT: Choosing an attribute

Suppose now we have $n_1$ items in $C_1$ and $n_2$ items in $C_2$. We have to choose which attribute $a \in A$ is the best to split the node. If we use superscript $n^v$ for number of items that have a value $v$ for a given attribute (and $n^v_1$ items of $C_1$ that have value $v$), I propose we use the score:

$$ \sum_v \frac{n^v}{n_1 + n_2} \frac{max(n^v_1, n^v_2)}{n^v_1 + n^v_2} $$

As a criterion instead of Gini.

Note, since $n^v = n^v_1 + n^v_2$ and $n_1 + n_2$ doesn't depend on the choosen attribute, this can be rewritten:

$$ \sum_v max(n^v_1, n^v_2) $$

And simply interpreted as the number of items in the dataset that will be properly classified.

$\endgroup$
1
$\begingroup$

Misclassification error will not help in splitting the Tree.
Reason-We consider the weighted dip of error from parent Node to the child node and misclassification error will always result in 0(Other than pure splits).

Let's consider an example
Data = 1, 1, 0, 1, 0, 1, 0, 1, 0, 1
Parent Classification error= 4/10 = 0.4
Parent Gini Impurity = 1-(0.4x0.4+0.6x0.6) = 0.48

Case - I
Split - 1, 1, 0, 1 Vs 1, 0, 1, 0, 1, 0
Classification error= 0.4x0.25 + 0.6x0.5 = 0.4, split not possible
Gini Impurity = 0.45

Case - II
Split - 1, 1, 1, 0, 0 Vs 0, 1, 0, 1, 0
Classification error = 0.5x0.4 + 0.5x0.4 = 0.4, split not possible
Gini Impurity = 0.48

Case - III
Split - 1, 1, 0, 0, 1, 1 Vs 1, 0, 1, 0
Classification error = 0.6x(2/6) + 0.4x0.5 = 0.4, split not possible
Gini Impurity = 0.477

Pure splits
Split - 1, 1, 1, 1, 1, 1 Vs 0, 0, 0, 0
Classification error = 0, split possible but no further splits
Gini Impurity = 0

Reference-
Sebastian Raschka Blog

$\endgroup$
4
  • $\begingroup$ The scenario is independent of the attribute as splits happen on Y. So, the result will be the same and we will not get any Attribute/Split to grow the Tree. $\endgroup$
    – 10xAI
    Feb 19 at 14:18
  • $\begingroup$ Ok, maybe you can edit and add Gini scores to be able to compare. If I understand properly, if Gini were to choose among I-II-III it would choose case I, while my criterion would not prefer any case. But what point do we have to say that case I is better? $\endgroup$
    – Gregwar
    Feb 19 at 14:23
  • $\begingroup$ Yes, I have added that too. $\endgroup$
    – 10xAI
    Feb 19 at 16:41
  • $\begingroup$ Thank you And again, even if I see that Gini is indeed better in Case I, I don't see a clear mathematical reason in choosing Case I over II or III here (or to split at all). If your data are well representing your future inputs you will still have 40% of mislabelling anyway. Using Gini appears to mean you will use a less good method to label your tree inputs just because you can see more difference in score in such example? $\endgroup$
    – Gregwar
    Feb 20 at 10:44
0
$\begingroup$

Since I only had a gut feeling about this, I decided to implement it in code. For this, I followed the method described at https://victorzhou.com/blog/gini-impurity/. Generally, calculating the GI provides you with a metric for which you don't have to know the underlying distribution which I think is the reason why your example works.

Generally, my conclusion is "Yes, there are situations in which a majority count is more useful, but usually, the GI usually produces a better separation".

Here is what I've done, following the link mentioned above:

  1. I have generated 4 x 2000 data points with random x/y coordinates.
  2. Based on whether the result of np.sqrt((data.p_x*data.p_y)) was bigger or smaller than a cutoff, I have assigned either blue or red as colors.
  3. Then, for each set of 2000 points, I have drawn 100 vertical lines representing potential splits a decision tree node could evaluate.
  4. Then, for each of these splits, I followed the procedure described in https://victorzhou.com/blog/gini-impurity/#example-1-the-whole-dataset. So I basically evaluated the Gini Impurity for both sides of the split, then calculated a weighted sum of these per split and calculated the "Gini Gain" by subtracting that from the naive probability of being right.
  5. In the lower-center plot, I have plotted the gain for each of these splits against the ratio of correct points this split would be able to classify. Also, for each set I have added a horizontal line indicating the number of correctly classified points if I just were to go for majority voting.

I simplified the real world by only using vertical splits, shown in light grey. Also, I'm approaching a 2D problem basically in 1D. The horizontal lines correspond be the accuracy of the majority vote principle you proposed. enter image description here

I uploaded the code here: https://github.com/dazim/stackoverflow_answers/blob/main/gini-impurity-in-decision-tree-reasons-to-use-it.ipynb

Edit 2021-02-19:

Based on the discussion in the comments I replaced the GI with the approach that Gregwar proposed. enter image description here Based on the two approaches, I evaluated the performance of a node making the decision based on the best cut. Plotted is score_gregwar - score_GI enter image description here Sadly, I've got to work on other stuff. But maybe someone else want's to pick up on that. Based on what I see in this simulation, the differences don't seem that big. However, using more "real" data and not just drawing vertical splits might change this. Sorry!

$\endgroup$
8
  • $\begingroup$ Hello, I am not sure to understand what you are doing exactly in the bottom middle graph. Both Gini and p_naive are simply scalars so why it appears that p_naive is a scalar and Gini a scatter plot ? $\endgroup$
    – Gregwar
    Feb 19 at 8:16
  • $\begingroup$ Your data are red and blue classes. And you try to compute Gini for each possible cut, that would be a decision tree node right? In that case, you would have for each cut two Gini impurities (one for the new "left" node and one for the new "right" node), but also two p_naive values, isn't it ? $\endgroup$
    – Gregwar
    Feb 19 at 8:21
  • $\begingroup$ Hey Gregwar, I have added a more detailed description of what I've done. p_naive reflects reflects a classification in which the node just always decides for the most frequent class in the data it was trained on. Wasn't this what you proposed? $\endgroup$
    – ttreis
    Feb 19 at 9:01
  • $\begingroup$ When you implement a decision tree algorithm there are two questions you might ask: "what attribute should I use for a given node?" and "what node should I split?" (if suppose you want to limit the size of your tree) Classical approach is to use information gain or Gini However I wonder why we can't simply use (1-p_max). This still depends on the attribute or the node you choose. On your top-left plot, if you cut at x=75 with my criterion, the "left" node will label all red and the "right" node will label all blue. If you cut on x=1, both "left" and "right" will be 100% red. $\endgroup$
    – Gregwar
    Feb 19 at 9:44
  • $\begingroup$ I think you are confusing the node of a tree with the resulting split? In your example, the decision to split at x=75 would be the node, separating the data into two subsets. Or at leas the "decision node" that would implement the rule. $\endgroup$
    – ttreis
    Feb 19 at 9:48

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.