Fundamentally, how is "the probability that two randomly selected samples belong to different classes" intuitively useful in any notion of purity? The Gini impurity measure is defined by
$$\sum_{i=1}^m f_i(1 - f_i)$$
This based on the probability of two randomly selected samples belonging to two different classes, one of which is $i$, i.e. $f_i(1 - f_i)$ - but how is this useful to our intuitive understanding of purity?
That is, can anyone provide an analogy or some other such mapping for why this measure says anything about the purity of a set?
 A: In the Gini impurity measure, $f_i$ is the proportion of items in the set that belong to class $i$.  Since $\sum f_i=1$, an alternative formula is
$$
1-\sum f_i^2\tag1
$$
How is this a measure of impurity? Certainly if the set consists of only one class, then (1) has value 0, which is as low as you can get. Conversely, if the set is totally heterogeneous, so that $f_i=\frac1m$ for each $i$, then (1) attains the maximum possible value of $1-\frac1m$. To see why this is the maximum possible, you can rewrite (1) in the form
$$
1-\frac1m - \sum\left(f_i-\frac1m\right)^2\tag2
$$
which also demonstrates that the only time the max is achieved is when all classes are equally represented.
There are other ways to measure heterogeneity of a set. What is desired is some numeric score that allows us to rank order the possible splits. So for example you could calculate the entropy of the frequency distribution:
$$
-\sum f_i\log(f_i)\tag3
$$
Note that (3) is computationally more expensive than (1), which is maybe why CART decided to adopt Gini impurity over entropy. But note the two measures are roughly the same, owing to the approximation $\log(x)\sim x-1$.
A: In terms of intuition, it measures the impurity because it kind of measures how less confident you are about the sample belonging to one class. Thus, if $f_i$ is close to $0$ or $1$, then you are highly confident about the assignment and thus the impurity is low. If the value is to $0.5$ instead then the Gini impurity is maximum ($=1/4$).
You would see similar expression in the variance of a Bernoulli random variable. If $p$ is the probability that the random variable takes the value $1$ then the variance is given by $p(1-p)$. Although, in this case its an actual formula deduced by derivation (and not just intuition), but intuition is the same. If the value of $p$ are close to $0$ or $1$, you have low variance (as you are more confident whether it is $0$ or $1$).
