Deriving Gini Impurity

Why Gini Impurity Measures Class Mixing

A classification-tree node contains cases belonging to one or more classes. A node is pure when every case has the same class; it is mixed when several classes are represented. Gini impurity assigns a number to that mixing. Its probability interpretation makes the formula easier to derive and helps distinguish it from the error rate of a majority-class prediction.

The setting here is a single node with $K$ possible, mutually exclusive, and exhaustive classes. Write $p_k$ for the proportion of cases in the node that belong to class $k$, where $k=1,\ldots,K$. Thus $p_k\geq 0$ and $\sum_{k=1}^K p_k=1$. In an observed node containing $n$ cases, $p_k$ is the number in class $k$ divided by $n$; it can also be viewed as an estimate of the class probability for cases represented by the node.

Definition: The Gini impurity of a node with class proportions $p_1,\ldots,p_K$ is $$ G=1-\sum_{k=1}^{K}p_k^2. $$ It is the probability of disagreement between two independent labels drawn from the node’s class proportions: one treated as the true label and the other as a randomly assigned predicted label.

The independence and sampling convention matter. For this interpretation, each label is drawn independently from the distribution that assigns probability $p_k$ to class $k$. Equivalently, the label draws are made with replacement from the empirical class proportions. This is not the same as selecting two distinct observed cases without replacement, which would give a different finite-sample probability.

Deriving the Formula

For the two labels to agree, both must be class 1, or both must be class 2, and so on. The chance that both are class $k$ is $p_kp_k=p_k^2$, by independence. These matching events cannot occur at the same time for different classes, so their probabilities add. Therefore the probability of agreement is $\sum_{k=1}^K p_k^2$. Disagreement is the complementary event, giving the Gini formula.

P(\text{agreement})=\sum_{k=1}^{K}P(\text{both labels are }k) =\sum_{k=1}^{K}p_k^2, \qquad P(\text{disagreement})=1-\sum_{k=1}^{K}p_k^2=G.

The same derivation can be written by summing the probabilities of all mismatched pairs. For a predicted label from class $j$ and a true label from a different class $k$, the joint probability is $p_jp_k$. Summing over all $j\ne k$ gives $G$. The complement form is usually quicker to calculate, while the mismatched-pairs form makes the interpretation explicit.

\sum_{j\ne k}p_jp_k = \left(\sum_{j=1}^{K}p_j\right)^2-\sum_{k=1}^{K}p_k^2 = 1-\sum_{k=1}^{K}p_k^2.

This is a probability model for a random label assignment, not a claim that a fitted tree always predicts labels randomly. A tree commonly predicts the majority class in a terminal node. Gini impurity instead summarizes how mixed the node’s class proportions are.

Worked Example: A Binary Node With Two Claim Categories

In a hypothetical training node for an insurance classification task, 18 cases have label “renewed” and 12 have label “not renewed.” Find the class proportions and Gini impurity. Then compare the result with the error rate from always predicting the majority class.

Method. Divide each class count by the total to obtain the node proportions, then apply $G=1-\sum_k p_k^2$. The probability interpretation uses independent draws from these proportions. This method avoids treating Gini as the deterministic majority-class error rate.

Step 1: Find the total and proportions. There are $18+12=30$ cases. Thus $p_{\text{renewed}}=18/30=0.6$ and $p_{\text{not renewed}}=12/30=0.4$. The proportions sum to $0.6+0.4=1$.

Step 2: Calculate the probability of agreement. Both labels are “renewed” with probability $0.6^2=0.36$. Both are “not renewed” with probability $0.4^2=0.16$. The total agreement probability is $0.36+0.16=0.52$.

Step 3: Take the complement. The Gini impurity is $G=1-0.52=0.48$. As a check, the probability of mismatch is $0.6(0.4)+0.4(0.6)=0.24+0.24=0.48$.

Step 4: Compare with majority-class error. Always predicting “renewed” misclassifies the 12 “not renewed” cases, so its error proportion is $12/30=0.40$. This is not the Gini impurity: $0.40\ne0.48$. The two values differ because the majority prediction is fixed, whereas the Gini interpretation draws a predicted label randomly using the class proportions.

Check. Agreement plus disagreement is $0.52+0.48=1$, as required. The majority class is “renewed,” and its deterministic error proportion is $0.40$.

Binary and Multiclass Calculations

For two classes with proportions $p$ and $1-p$, the general formula simplifies to a product. This form shows directly that the impurity is zero at either endpoint and is largest when the two classes are equally represented.

G=1-\left[p^2+(1-p)^2\right] =1-\left[p^2+1-2p+p^2\right] =2p(1-p).

With three or more classes, square every class proportion separately and add those squares before subtracting from 1. Do not combine all non-majority classes into one group unless the problem has explicitly defined that grouping as a new binary classification. Combining classes changes the set of labels and therefore changes the impurity being calculated.

Worked Example: Three Classes in a Claims Node

A hypothetical claims-triage node contains 12 cases labeled “routine,” 8 labeled “review,” and 5 labeled “urgent.” Calculate the class proportions and Gini impurity, and verify the result by summing the probabilities of mismatched ordered label pairs.

Method. Use the multiclass formula, with each of the three labels kept separate. The check by mismatched pairs avoids accidentally omitting pairs in one direction.

Step 1: Calculate the total and proportions. The total is $12+8+5=25$. The proportions are $p_{\text{routine}}=12/25=0.48$, $p_{\text{review}}=8/25=0.32$, and $p_{\text{urgent}}=5/25=0.20$. They sum to $0.48+0.32+0.20=1.00$.

Step 2: Square each proportion. The squared proportions are $0.48^2=0.2304$, $0.32^2=0.1024$, and $0.20^2=0.0400$. Their sum is $0.2304+0.1024+0.0400=0.3728$.

Step 3: Subtract from 1. The Gini impurity is $G=1-0.3728=0.6272$.

Step 4: Verify by counting mismatch directions. Routine-review mismatches have total probability $0.48(0.32)+0.32(0.48)=0.3072$. Routine-urgent mismatches have probability $0.48(0.20)+0.20(0.48)=0.1920$. Review-urgent mismatches have probability $0.32(0.20)+0.20(0.32)=0.1280$. The total is $0.3072+0.1920+0.1280=0.6272$.

Check. Agreement is $0.3728$ and disagreement is $0.6272$; their sum is $1.0000$. The mismatch calculation includes both possible orders for each distinct pair.

Range and Interpretation

Gini impurity is always nonnegative because each $p_k^2$ is nonnegative and the sum of squares cannot exceed $(\sum_k p_k)^2=1$. It equals zero exactly when one class has proportion 1 and all other classes have proportion 0: the node is pure, and two independent labels must agree.

For a fixed number $K$ of available classes, impurity is largest when the class proportions are equal. One justification is that $\sum_{k=1}^K(p_k-1/K)^2\geq0$. Expanding and using $\sum_k p_k=1$ gives $\sum_k p_k^2\geq1/K$. Therefore $G\leq1-1/K$, with equality when every $p_k=1/K$. In a binary node, the maximum is $1/2$, reached at proportions $1/2$ and $1/2$. With $K$ classes, the maximum is $1-1/K$.

Theorem: For a node with $K$ possible classes, $0\leq G\leq1-1/K$. The lower bound is attained by a pure node; the upper bound is attained when all $K$ class proportions are equal. If some classes are absent from the node, the stated upper bound remains valid, although the node cannot attain it unless all $K$ classes are represented equally.

For example, a four-class node with equal proportions has $G=1-4(1/4)^2=1-1/4=0.75$. That value is larger than the maximum for a binary node because the number of possible classes differs. When interpreting an impurity value, consider how many classes are available as well as the value itself.

Worked Example: Recovering Binary Proportions From Gini

A binary classification node has Gini impurity $0.32$, and both classes occur. Determine its two class proportions. Explain why the impurity alone does not identify which named class has which proportion.

Method. Let one class proportion be $p$, so the other is $1-p$. Use the binary identity $G=2p(1-p)$, then solve the resulting quadratic. This avoids assuming that the first class is necessarily the majority.

Step 1: Set up the equation. $0.32=2p(1-p)$, so $0.32=2p-2p^2$. Rearranging gives $2p^2-2p+0.32=0$.

Step 2: Simplify and solve. Divide by 2 to get $p^2-p+0.16=0$. The quadratic formula gives $p=[1\pm\sqrt{1-4(0.16)}]/2=[1\pm\sqrt{0.36}]/2=[1\pm0.6]/2$. Thus $p=0.8$ or $p=0.2$.

Step 3: State the proportions. The two class proportions are $0.8$ and $0.2$, in either order. The impurity does not distinguish which class is the more common one; swapping class names leaves the sum of squared proportions unchanged.

Check. $1-(0.8^2+0.2^2)=1-(0.64+0.04)=0.32$. Both classes occur, as specified.

Common Mistakes and Why the Distinction Matters

A frequent mistake is to square the proportions and report their sum as the impurity. That sum is the probability of agreement, not disagreement; Gini impurity is its complement. Another mistake is to calculate only one direction of a mismatch. For two classes, the events “true class 1, predicted class 2” and “true class 2, predicted class 1” are distinct and both count. The complement calculation automatically includes both.

A separate confusion is treating Gini impurity as the error rate from predicting the majority class. If the largest proportion is $p_{\max}$, the error proportion from always predicting that class is $1-p_{\max}$. Gini instead is $1-\sum_k p_k^2$. These quantities answer different questions and generally are not equal. A node’s impurity describes its full class composition; the majority-class error depends on the largest class alone.

Gini also depends on proportions rather than the raw node size. A node with counts 6 and 4 has the same empirical Gini as one with counts 60 and 40, because both have proportions $0.6$ and $0.4$. The proportions are identical, although the smaller node’s estimated composition is based on fewer cases. Do not multiply or divide the Gini formula by the number of cases unless a separate quantity has explicitly been requested.

Key takeaway: Square each class proportion, add the squares, and subtract from 1. The result is the probability of disagreement between independent true and randomly assigned labels drawn from the node proportions—not the deterministic error rate from predicting the majority class.

Check Your Understanding

For each problem, use the class proportions in the stated node and keep the named classes separate.

A binary node has 9 cases in class A and 11 in class B. Find its Gini impurity. (Answer: $0.495$)
A three-class node has counts 6, 3, and 1. Calculate the proportions and Gini impurity. (Answer: proportions $0.6, 0.3, 0.1$; $G=0.54$)
A node has four equally represented classes. What is its Gini impurity, and is this the largest possible value for four classes? (Answer: $0.75$; yes)
A binary node has Gini impurity $0.32$, with both classes represented. What are its class proportions? (Answer: $0.8$ and $0.2$, in either order)
A four-class node has counts 20, 10, 6, and 4. Calculate its Gini impurity and the error proportion if every case is assigned to the majority class. (Answer: $G=0.655$; majority-class error proportion $=0.50$)

What You'll Learn