16
$\begingroup$

In a context of decision tree splitting, it is not obvious to see why the Gini impurity $$ i(t)=1-\sum\limits_{j=1}^k p^2(j|t) $$ is a measure of node t impurity. Is there an easy explanation of this?

$\endgroup$
1

2 Answers 2

21
$\begingroup$

Imagine an experiment with $k$ possible output categories. Category $j$ has a probability of occurrence $p(j|t)$ (where $j=1,..k$)

Reproduce the experiment two times and make these observations:

  • the probability of obtaining two identical outputs of category $j$ is $$ p^2(j|t) $$
  • the probability of obtaining two identical outputs, independently of their category, is: $$\sum\limits_{j=1}^k p^2(j|t)$$
  • the probability of obtaining two different outputs is thus: $$1-\sum\limits_{j=1}^k p^2(j|t)$$

That's it: the Gini impurity is simply the probability of obtaining two different outputs, which is an "impurity measure".


Remark: another expression of the Gini index is: $$ \sum\limits_{j=1}^k p_j(1-p_j) $$ This is the same quantity: $$ \sum\limits_{j=1}^k p_j(1-p_j) = \left(\sum\limits_{j=1}^k p_j \right) -\left( \sum\limits_{j=1}^k p^2_j \right) = 1 - \sum\limits_{j=1}^k p^2_j $$

$\endgroup$
7
  • $\begingroup$ Same math but with a more practical interpretation: it is natural to predict the class $j = 1 \ldots k$ of an element in the set by selecting a class $j$ with probability $p(j)$. 1-Gini then simply gives you the (Rand) accuracy. Thus, a Gini impurity of 0 means a 100 % accuracy in predicting the class of the elements, so they are all of the same class. Similarly, a Gini impurity of 0.5 means a 50 % chance of correctly classifying an element of the set with this natural method, etc. $\endgroup$ Aug 6, 2018 at 11:00
  • $\begingroup$ I think the usage of "outputs" above is a little confusing - the "output" actually means the true class or category, and has nothing to do with the output of the decision tree classifier. $\endgroup$
    – flow2k
    Jul 26, 2020 at 9:53
  • $\begingroup$ On another note, I believe "reproduce the experience..." should read "reproduce the experiment...". (I tried to edit, but the edit was rejected - stats.stackexchange.com/review/suggested-edits/268539.) $\endgroup$
    – flow2k
    Jul 27, 2020 at 11:37
  • 1
    $\begingroup$ @flow2k thanks. I tried to improve a little bit the answer. $\endgroup$ Jul 28, 2020 at 6:14
  • 1
    $\begingroup$ Such a simple articulation. Thank you :) $\endgroup$ Jul 16, 2021 at 5:39
0
$\begingroup$

Gini impurity = logical entropy = Gini-Simpson biodiversity index = quadratic entropy with logical distance function (1-Kroneckerdelta), etc. See: Ellerman, David. 2018. “Logical Entropy: Introduction to Classical and Quantum Logical Information Theory.” Entropy 20 (9): Article ID 679. https://doi.org/10.3390/e20090679, and the references contained therein.

$\endgroup$
1
  • $\begingroup$ Economists are apt to call this the Herfindahl-Hirschman index. $\endgroup$
    – Nick Cox
    Feb 5, 2019 at 12:34

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.