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
I know the differences between entropy and Gini impurity and why we use Gini in order to construct trees. But I would like to find some relation between those two measures. It leads me to one particular question:
Are there any two distributions X and Y such that entropy of X is greater than the entropy of Y but the Gini impurity of X is smaller than the Gini impurity of Y?
The answer depends on the distribution: specifically, on whether more than two of the probabilities are nonzero.
For a discrete distribution with nonzero probabilities $\mathbb{P}=(p_1,p_2,\ldots,p_n)$ (where $n=\infty$ is possible), the entropy (in natural units) is
$$H(\mathbb P) = -\sum_{i=1}^n p_i \log(p_i)$$
and the Gini Impurity is
$$G(\mathbb P) = \sum_{i=1}^n p_i(1-p_i).$$
When $n=2$ there are just two probabilities, which I will express as $p_1=p$ and $p_2 = 1-p$ because they must sum to unity. In this case
$$H(\mathbb P) = -p\log(p) - (1-p)\log(1-p)$$
and
$$G(\mathbb P) = p(1-p) + (1-p)p = 2p(1-p)$$
Values of $G$ in this case must lie between $0$ and $1/2.$ Given such a value $g,$ we can solve
$$p(g) = \frac{1}{2}\left(1 \pm \sqrt{1-2g}\right)$$
and plug that into $H$ to give two values. They will be equal to each other, yielding a unique corresponding entropy. Thus $H$ is a function of $G$ in this case. Here's its graph:
Because the graph is strictly increasing, the orderings given by $H$ and $G$ are equivalent.
With more than two (nonzero) probabilities, it is possible to find exceptions. For instance, let $\mathbb{P}_1 = (1/16, 7/16, 1/2)$ and $\mathbb{P}_2 = (1/8, 1/4, 5/8).$ Then you can compute these values of $H$ and $G$:
$$\begin{array}{lrr} \text{Distribution} & G & H \\ \hline \mathbb{P}_1 & 0.55& 0.88 \\ \mathbb{P}_2 & 0.53& 0.90 \end{array}$$
They show a reversal of the ordering.
Generally, here are the possible values of $(G(\mathbb{P}), H(\mathbb{P}))$ for all distributions $\mathbb{P}$ with three nonzero probabilities:
Any pair of distributions will form two dots in the gray area. When those dots are oriented negatively--that is, one is to the right and below the other--the orderings are reversed. The preceding example corresponds to the two orange points.
This exhibits a relation, not a function. You can see, for instance, that when the entropy is approximately $0.64$, the Gini Impurity could be anywhere from around $0.35$ to almost $0.5.$
Nevertheless, there is an approximate monotonic relationship between $G$ and $H$ in this case, as shown by the thinness of the gray area. The additional flexibility with larger $n$ indicates the relationship between $G$ and $H$ will grow even more tenuous as $n$ increases, though.
Because $H$ and $G$ are continuous functions and can be continuously extended to include zero probabilities, for larger $n$ (interpreted as the maximum number of nonzero probabilities in a distribution) it will be possible to find similar examples simply by setting all but three of the probabilities to zero. Using Lagrange multipliers, we can work out formulas for the range of possible entropies $H$ for any given $n$ and Gini Impurity value $g.$
The smallest entropies are attained by distributions having $k$ probabilities of $q$ and one probability of $1-kq$ where $k = \lceil g/(1-g)\rceil$ is the smallest possible number for which $g$ is a feasible Gini Impurity. The value $q$ is the solution of a quadratic equation, given by $$q = \frac{1 - \sqrt{\Delta(g)}}{k+1};\quad \Delta(g) = 1 - g\frac{k+1}{k}.$$ Notice that $q$ is less than the average of the positive probabilities, $1/(k+1).$ These distributions therefore have a "spike" of probability $1-kq$ and the rest is spread among the minimal number $k$ of other values in order to attain a Gini Impurity of $g.$
The largest entropies are attained by distributions having $k=n-1$ probabilities of $q$ and one probability of $1-(n-1)q.$ This time $q$ is the other root of the same quadratic equation, $$q = \frac{1 + \sqrt{\Delta(g)}}{n}.$$ Now $q$ slightly exceeds the average probability of $1/n.$ These distributions spread the total probability as evenly as possible over all $n$ values but decrease one of them in order to attain a Gini Impurity of $g.$
Here is a plot of ranges of $H$ as a function of $G$ and $n.$ The additional possibilities for larger $H$ are colored by $n.$ As $n$ grows arbitrarily large, eventually the entire gray area is filled in to arbitrarily high values. Thus, in general the only possible simultaneous values of $(G,H)$ that are excluded are those lying beneath the lower (black) curve.
