Gini index - formal or heuristic?

Gini index is quite often used in constructing decision trees in data mining for attribute selection and attribute split point. Is Gini coefficient just a heuristic or can we formally explain why it's defined the way it is?

• Are you saying that a heuristic is what we cannot formally explain how we define it? – ttnphns Apr 19 '15 at 6:53
• No, sorry. The formulation of my question isn't very precise. I'm asking whether we can DERIVE the formula somehow, or PROVE it. Every heuristic method can be defined formally and the question is whether gini index is an example of a heuristic approach. – user4205580 Apr 19 '15 at 8:57
• possible duplicate of Decision tree learning – Anony-Mousse Jun 7 '15 at 21:36

I don't have a formal proof for you.

But from a quick look, the Gini is the probability of two randomly chosen items having the same type, isn't it? That sounds like a way to formally derive it from a simple, probabilistic model.

At least for the variant of Gini that I use mostly, which is this one:

$$G:=\sum_i p_i^2$$

where $p_i$ is the probability of class $i$ occurring. For this index, $1$ indicates a pure result, and $0$ would be maximal impurity. Some people use $1-G$ for consistency with other measures, but that obviously does not make a whole lot of a differences - it's just the opposite probability.

• Gini is the probability of two randomly chosen items having the same type - maybe you could explain how you figured it out? I'd say the opposite - gini index equal 0 means that two randomly chosen items certainly belong to the same class. – user4205580 Apr 19 '15 at 11:14
• But I'm still not sure what's the connection between gini index and calculating a probability. – user4205580 Apr 19 '15 at 11:21
• There are different variations of the index. Somewhat like similarity and dissimilarity. There are even some that range from 0 to 10000... Which equation are you using exactly (you may want to update your question with this)? – Anony-Mousse Apr 19 '15 at 11:28
• Yes, I meant 1−G variant, it makes sense now. – user4205580 Apr 19 '15 at 12:14
• Actually, I'm not sure if the following interpretation of $1-G$ is correct: 'Gini impurity can be computed by summing the probability of each item being chosen times the probability of a mistake in categorizing that item.' I don't quite understand why it's true, because I can't see why $p_i$ is the probability of choosing an item. Rather, it's just the probability of choosing an item in class $i$. – user4205580 May 6 '15 at 13:55

Gini index defined for a discrete probability distribution is a measure for inherent 'randomness' in the distribution. For a two class problem, with probabilities $p, 1-p$, it is given by $2p(1-p)$. All the outcomes belong to the same class, if $p$ equals 0 or 1 in which case the randomness in the distribution is 0. This is captured by Gini, which evaluates to zero in these cases. One can also intuitively see that for $p=1/2$ we have maximum 'randomness' and the Gini criteria rightly peaks at this point.

Interpreting it as a probability it represents the probability that two consecutively drawn labels are different. Answer by @anony-mousse explains this further in general case.