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?
-
$\begingroup$ This answer on a related question may help you better understand the intuition: stats.stackexchange.com/a/339514/27974 $\endgroup$ – Scott Apr 10 '18 at 18:22
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".
-
$\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
-
$\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 '20 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 '20 at 11:37
-
$\begingroup$ @flow2k thank you for your comments, I will try to edit my post next days as I do not have a computer right now (holidays). As English is not my mother tongue there are certainly not well-worded sentences. $\endgroup$ – Picaud Vincent Jul 27 '20 at 12:11
-
1$\begingroup$ @flow2k thanks. I tried to improve a little bit the answer. $\endgroup$ – Picaud Vincent Jul 28 '20 at 6:14
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