Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
There's a step in the Wikipedia article regarding the formulation of the Gini Impurity that I can't understand.
They state that:
I follow everything up until this point
$1-\sum_{i=1}^Jf_i^2 = \sum_{i\ne k}f_if_k$
There is a related thread that gives an intuitive explanation, but I'm wondering if anyone knows the actual mathematics behind this step.
I remember reading this exact thing on Wikipedia thinking it was a typo. It's not though. And the math is really simple. Note that $f_if_k$ corresponds to the probability of observing an $i$ followed by a $k$ from two independent draws from the distribution $f$. Therefore, if you sum over the probabilities of all $(i,k)$ pairs you get $1$. In other words, we have the equality, $$\sum_{i=1}^J \sum_{k=1}^J f_i f_k = 1$$ But we can rewrite the double summation as $$\sum_{k=1}^J f_i f_k = \sum_{i=1}^J f_i^2 + \sum_{i=1}^J \sum_{k=1, k \ne i}^J f_i f_k$$ Then, if you subtract $\sum_{i=1}^J f_i^2$ from the top and bottom, you end up with the equality of interest.
Here is a snippet from my answer here. The easiest way (for me at least) to understand
$1-\sum f_i^2$ = $\sum_{i \neq k} f_if_k$
is by visually representing each of the elements in this equation. We'll assume that there are 4 labels below; however, this will scale to n values.
The value 1 is simply the sum of all possible probabilities. By definition this value must be 1.
The value $\sum f_i^2$ is the sum of probabilities of selecting a value and its label from the distribution of values.
Subtracting the probability that you match labels with values from 1 gives you the probability that you don't match labels and values. This is what the gini impurity provides -- the probability that you don't match labels to values.
