The reason why Gini index is in favor of multivalued attributes

I am a beginner in data science and I try to understand the similarity and dissimilarity between information gain and Gini index. In my lecture notes, the professor states one of disadvantage of Gini index is its bias toward multivalued attributed but did not tell us why.

My questions are why Gini index is in favor of multivalued attributes(with more distinct values)just like information gain and what node should I split if two attributes have same Gini index value.

The reason is that the expected decrease in the Gini index for splitting with a categorical variable with $$L \geq 3$$ levels grows in $$L$$. As a result, the algorithm is biased to choose a variable with a high number of levels - this "maximises" the information gain.

In the case of a binary classification problem, if the different levels provide no information about the response, the relationship between the expected increase in Gini is: \begin{align} \mathbb{E}(\hat{\Delta}_{Gini} \vert N = n) = \frac{2p_1(1-p_1)(L-1)}{n}, \end{align} where $$p_1$$ is the probability of choosing class 1 (precise definition below). Therefore, as $$L$$ increases it is luring to pick a multilevel variable for a split, despite it not giving any information!

Proof

I will not show every step, but enough to fill the gaps. This answer is a copy of my solution to an exercise from my machine learning module; the exercise can be accessed here. In case the document is taken down in the future, I will write out the notation etc. below.

Note, the proof will be in the case of binary classification, i.e. $$Y \in \{0, 1\}$$. We are at node $$t$$ in a decision tree and would like to split it based on Gini impurity. Consider a categorical variable $$C$$ with $$L \geq 3$$ levels, i.e. $$x^{(C)} \in \{c_1, c_2, \ldots, c_L\}$$.

Notation

1) For every data point reaching node $$t$$, $$X_i, Y_i$$, where $$i \in \{1, \ldots, N \}$$, denote:

\begin{align} p_k &= \mathbb{P}(Y_i = k), \ \ \ k = 0, 1; \\ q_l &= \mathbb{P}(X_i^{(C)} = c_l), \ \ \ l = 1, \ldots, L; \\ p_{k \vert l} &= \mathbb{P}(Y_i = k \vert X_i^{C} = c_l), \ \ \ k = 0, 1; \ l = 1, \ldots, L. \end{align}

Note that the case where variable $$C$$ provides no information for the response corresponds to $$p_k = p_{k \vert l}$$ for all l. We do not have the above probabilities, so we need to estimate them, e.g. using maximum likelihood estimation (MLE). The following notation will help us to do that.

2) For the same $$i$$ as in point 1):

\begin{align} N^k &= \vert \{i: Y_i = k\} \vert, \ \ \ k = 0, 1; \\ N_l &= \vert \{i: X_i^{(C)} = c_l\} \vert, \ \ \ l = 1, \ldots, L; \\ N_{k\vert l} &= \vert \{i: Y_i = k \ \text{and} \ X_i^{C} = c_l\} \vert, \ \ \ k = 0, 1; \ l = 1, \ldots, L; \end{align}

We assume that the N data vectors reaching node t are independent.

First step

Note that the following can be shown, for example, by looking at the PMFs of the random variables: \begin{align} N^{k} \vert N = n &\sim Binomial(n, p_k) \\ N_{l} \vert N = n &\sim Binomial(n, q_l) \\ N_{k \vert l} \vert N_l = n_l &\sim Binomial(n_l, p_{k \vert l}) \end{align}

From the above, we deduce that the MLE plugin estimates for the probabilities are

\begin{align} \hat{p}_k &= \frac{N^k}{N} \\ \hat{q}_l &= \frac{N_l}{N} \\ \hat{p}_{k \vert l} &= \frac{N_{k \vert l}}{N_l} \end{align}

Second step

The population Gini impurity is given by $$2p_1(1-p_1)$$. There is a two in front because the impurity is symmetric wrt the class for a binary classification problem. If we split at node $$t$$ using the categorical variable $$C$$ with $$L$$ levels, the resulting change in Gini impurity will be \begin{align} \Delta_{Gini} = 2p_1(1-p_1) - 2\sum\limits_{l = 1}^Lq_lp_{1 \vert l}(1 - p_{1 \vert l}) \end{align}

Plugging in the MLE estimates gives us the estimated change in Gini impurity $$\hat{\Delta}_{Gini}$$. We would like to find its expected value $$\mathbb{E}(\hat{\Delta}_{Gini} \vert N = n)$$ and see how it depends on $$L$$.

Third step

To calculate the expected value we will use the distributional relationships found in the first step.

\begin{align} \mathbb{E}(\hat{\Delta}_{Gini} \vert N = n) = 2\mathbb{E}(\hat{p}_1(1-\hat{p}_1) \vert N = n) - 2\sum\limits_{l =1}^{L} \mathbb{E}(\hat{q}_l \hat{p}_{1\vert l} (1 - \hat{p}_{1\vert l}) \vert N = n) \end{align}

We shall treat the two terms separately. For the first one,

\begin{align} 2\mathbb{E}(\hat{p}_1(1-\hat{p}_1) \vert N = n) &= \frac{2}{n}\mathbb{E}(N^1 \vert N = n) - \frac{2}{n^2}\left(\mathbb{E}(N^1(N^1 - 1) \vert N = n) + \mathbb{E}(N^1 \vert N = n)\right) \\ &= 2p_1 - \frac{2}{n}p_1(1 + (n-1)p_1) \\ &= \frac{2}{n}p_1(1-p_1)(n-1) \end{align} For the second one, let's look at the expected value \begin{align} \mathbb{E}(\hat{q}_l \hat{p}_{1\vert l} (1 - \hat{p}_{1\vert l}) \vert N = n) &= \frac{1}{n}\mathbb{E}(N_{1 \vert l}(1 - \frac{N_{1 \vert l}}{N_l}) \vert N = n) \\ &= \frac{1}{n} \sum\limits_{i=1}^{n} \mathbb{E}(N_{1 \vert l}(1 - \frac{N_{1 \vert l}}{N_l}) \vert N_l = i) \ \mathbb{P}(N_l = i \vert N = n) \\ &= \frac{1}{n} \sum\limits_{i=1}^{n} \left( \mathbb{E}(N_{1 \vert l} \vert N_l = i) - \frac{1}{i} \mathbb{E} (N_{1 \vert l}^2 \vert N_l = i) \right) \ \mathbb{P}(N_l = i \vert N = n) \\ &= \frac{1}{n} \sum\limits_{i=1}^{n} \left( i p_{1 \vert l} - p_{1 \vert l}(1 + (i -1)p_{1 \vert l}) \right) \ \mathbb{P}(N_l = i \vert N = n) \\ &= \frac{1}{n} \sum\limits_{i=1}^{n} p_{1 \vert l}(1 - p_{1 \vert l})(i-1) \ \mathbb{P}(N_l = i \vert N = n) \\ &= \frac{1}{n} p_{1 \vert l}(1 - p_{1 \vert l}) \left( \sum\limits_{i=1}^{n} i \ \mathbb{P}(N_l = i \vert N = n) - 1 \right) \\ &= \frac{1}{n} p_{1 \vert l}(1 - p_{1 \vert l}) \left(nq_l - 1 \right) \end{align}

So, combining the results, we get that:

\begin{align} \mathbb{E}(\hat{\Delta}_{Gini} \vert N = n) = \frac{2}{n}p_1(1-p_1)(n-1) + \frac{2}{n}\sum\limits_{l = 1}^L p_{1 \vert l}(1 - p_{1 \vert l}) \left(1 - nq_l \right) \end{align}

In the case where the categorical variable has no effect on the response, we substitute $$p_{1 \vert l} = p_1$$, which gives us the result stated at the beginning.