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?


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

Then reproduce the experience 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". In the other direction, if we have a $j^\star$ such that $p(j^\star|t)=1$ (and thus the other p(j|t)=0) we have a Gini impurity $i(t)=0$ and we will always get two identical outputs of category $j^\star$, which is a "pure" situation!.

  • $\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$ – Eric O Lebigot Aug 6 '18 at 11:00

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.

  • $\begingroup$ Economists are apt to call this the Herfindahl-Hirschman index. $\endgroup$ – Nick Cox Feb 5 '19 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.