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

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!.

• 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. – 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.

• Economists are apt to call this the Herfindahl-Hirschman index. – Nick Cox Feb 5 at 12:34