Basic Gini impurity derivation

Question

From wikipedia: https://en.wikipedia.org/wiki/Decision_tree_learning

I am unable to get my head around two of the steps:

1. The first equation: $f_i(1 - f_i)$. This does not immediately become apparent as the "probability of being chosen times the probability of miscategorization". Instead it looks to me like "probability of being chosen times the probability of others being chosen" (but not necessarily incorrectly)

2. The arithmetic of the last simplification eludes me: how to get from $1 - \sum(f_i^2)$ to $\sum(f_if_k)$

Tips appreciated.

Answer 1

I don't know about the algebra, but you can prove the identity with a probabilistic argument. If I roll two dice with $m$ sides and the probability of side $i$ is $f_i$, then the probability of a double is $\sum f_i^2$. Thus $1-\sum f_i^2$ is the probability that I roll distinct values. But arguing differently, the probability, say, that I get $i$ followed by $j$ is $f_if_j$. Summing over all possibilities, with $i \neq j$, I get the probability of rolling distinct outcomes: $\sum f_if_j$, and the identity is proven.

As for the first point, If you role the $m$ sided die, there is a probability $f_i$ that side $i$ comes up. Suppose I have to guess the value, and I do this by rolling a die of my own with the same weights. The probability that I guess wrong, conditional on value $i$ being true, is $1-f_i$. The probability that I get it wrong, summing over the possible values, is $\sum f_i(1-f_i)$.

Answer 2

I think it's best to answer your question in reverse order as we'll back into your first question by answering your second.

Question 2

Imagine you have a probability distribution function ($f_i$) that distributes its probabilities as such:

I can then square the probabilities ($f_i^2$) and get:

Another way of looking at it is putting each probability distribution along the axis of a grid. Each cell now represents the product of the function along the respective axes.

The grid itself sums to 1, just like you'd see in a two dice roll probability table. It should be clear that 1 minus the sum of the diagonal probabilities is the same as the non-highlighted squares below.

If we call one of the axis k to differentiate it, but still have it render the same function, we can then make the statement.

$1-\sum f_i^2$ = $\sum_{i \neq k} f_if_k$

Question 1

We can now use some of the intuition from answering question 2 to drive the intuition for question 1.

Let's take our same table from question 2, but change what the two axes mean. Across one axis we'll have labels for objects, while on the other we'll have the actual object.

For a concrete example, let's assume we have a bowl of fruit: apples, oranges and pears. In another bowl we'll have labels corresponding to apples, oranges and pears in the same proportion as the actual objects.

If we then look at the probability of choosing each at random we get the following distribution.

Now we want to look at the joint distribution. The Geni impurity tells us the probability that we select an object at random and a label at random and it is an incorrect match. The Geni impurity is the sum of the probabilities in the black shaded areas. These are where the label does not match the object, thus the impurity.

This should look very familiar to the answer to question 2. If the explanation for question 2 convinced you that $1-\sum f_i^2$, you should be able to work backwards through the algebra you provided to see that also equals $\sum f_i(1-f_i)$

Answer 3

1) Remember that the classification is done randomly proportional to the frequency of the value. $i$ is then miscategorized with probability $(1-f_i)$.

2) The $f_i$ sum to 1. So if I sum all $f_if_j$ this equals 1*1. So if I sum just the ones where $i\neq j$ this equals $1- \sum f_if_i$.

Sorry for the brevity, answering from my phone. Comment with questions.

Answer 4

Gini index

Main idea is here. We can make an example based on this statquest.

Let's say there is a machine that can detect Heart Disease (HD). The machine can predict HD 30% of the time. Following is the sample we have:

	HD	!HD
Machine	30%	70%

This means the following cases are possible:

1. Machine classify as HD and it is HD (P = 0.3*0.3)
2. Machine classify as !HD and it is !HD (P = 0.7*0.7)
3. Machine classify as HD but it is !HD
4. Machine classify as !HD but it is HD

We pray that cases 3&4 happen less often. The sum of all probabilities is 1. P(3&4) is therefore given by 1-(0.3^2)-(0.7^2)=0.42. P(3&4) is the impurity or how bad the machines' prediction is, AKA GINI=0.42.

The alternative is to check if someone is clutching his chest or not due to chest pain (CP) and then guess based on probability data if he has HD or not. The following is the sample we have. For each case we calculate the GINI. Then we take the average of it (assuming similar sample size) and this estimates the GINI impurity using CP to predict HD.

	HD	!HD	GINI
!CP	25%	75%	0.375
CP	80%	20%	0.32
avg	NA	NA	0.38

Smaller the impurity the better. So we decide instead of buying the machine (GINI=0.42) we can just use CP as an indicator (GINI=0.38).

P.S.
This is also an explanation of what happens at each node of a decision tree, which is where I came across GINI index.