A simple & clear explanation of the Gini impurity?

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$$)

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$$

• 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. Aug 6, 2018 at 11:00
• 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. Jul 26, 2020 at 9:53
• 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.) Jul 27, 2020 at 11:37
• @flow2k thanks. I tried to improve a little bit the answer. Jul 28, 2020 at 6:14
• Such a simple articulation. Thank you :) Jul 16, 2021 at 5:39

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.

• Economists are apt to call this the Herfindahl-Hirschman index. Feb 5, 2019 at 12:34