13
$\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$
18
$\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".

| cite | improve this answer | |
$\endgroup$
  • $\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 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 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 at 12:11
  • 1
    $\begingroup$ @flow2k thanks. I tried to improve a little bit the answer. $\endgroup$ – Picaud Vincent Jul 28 at 6:14
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.

| cite | improve this answer | |
$\endgroup$
  • $\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.