Gini Impurity

Q: What is the largest possible Gini value?

It is $1 - \frac{1}{K}$, reached when all $K$ classes have equal shares. With two classes that is 0.5, and with three classes it is about 0.667.

In one sentence: Gini impurity is a score for how mixed the kinds of items are in one group, where 0 means every item in the group is the same kind.

$G = 1 - \sum_{k=1}^{K} p_k^2$

Read it out loud: “G equals one minus the sum, for k running from 1 up to K, of p sub k squared. The sum sign is the Greek capital letter sigma, which means add up. The small k under the sign says where to start counting, and the capital K above it says where to stop. Here K is the number of kinds, and p sub k is the share of items that belong to kind number k. The little 2 means squared, which is the number multiplied by itself. G is the Gini impurity.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Decision tree, node, class and share: A decision tree is a flowchart of yes-or-no questions that sorts examples into groups. Each example has a label called its class, such as red or blue. A node is one box in the tree that holds some examples. The share of a class in a node is the fraction of that node’s examples that carry that label. A share of 0.6 means 6 out of every 10 examples, so every share is a number between 0 and 1.
The sum sign, $\sum$: The capital Greek letter sigma, $\sum$ , means add up. Read $\sum_{k=1}^{K} p_k$ as: start with $k = 1$ , take $p_k$ for that $k$ , then move to $k = 2$ , and keep going until $k = K$ . The small label under the sign says where to start counting, and the label above it says where to stop. So $\sum_{k=1}^{K} p_k$ means $p_1 + p_2 + \cdots + p_K$ , where the dots mean and so on.
Subscripts, like $p_k$: A small letter or number written below a symbol is a subscript. It is a label that picks out one item from a list. $p_1$ is the share of class number 1, $p_2$ is the share of class number 2, and $p_k$ stands for the share of whichever class $k$ we are looking at. The letter $K$ is the total number of classes, so the list runs from $p_1$ to $p_K$ .
Squares, like $p_k^2$: A small raised 2 after a symbol means squared: the symbol multiplied by itself. So $p^2 = p \times p$ . For example, $0.6^2 = 0.6 \times 0.6 = 0.36$ , and $0.4^2 = 0.16$ . The square of a number between 0 and 1 is always smaller than the number itself, and a bigger share gives a bigger square.
Pure and mixed nodes: A pure node holds examples of only one class, such as five red marbles and nothing else. A mixed node holds two or more classes. The more evenly the classes are mixed, the higher the Gini score. A pure node always scores 0, and a node whose classes have equal shares scores the largest value possible for its number of classes.
Weighted average: A weighted average is an average in which some values count more than others. Each value is multiplied by its weight, the results are added, and the weights add up to 1. In the split step, each child node gets a weight equal to its share of all the examples. A child that holds 5 of 10 examples has the weight $\frac{5}{10} = 0.5$ , so it counts for half of the average.

What each symbol means

Symbol	Meaning
$G$	The Gini impurity of one node, a score that says how mixed the node is. It runs from 0 for a pure node up to $1 - \frac{1}{K}$ for a perfectly even mix. It has no unit, because it is built from shares, which are plain fractions. With two classes it ranges from 0 to 0.5.
$K$	The number of classes, a whole count of the kinds of label the examples can have. Two classes, red and blue, give $K = 2$ . Three classes, cat, dog and bird, give $K = 3$ . It has no unit.
$k$	The running number for the classes, counting 1, 2, up to $K$ . It is only a label for one class at a time, like class number one. It has no unit.
$p_k$	The share of examples in this node that belong to class $k$ . It is a fraction between 0 and 1 with no unit, so 0.6 means 60 percent. The shares of all $K$ classes add up to exactly 1.
$\sum_{k=1}^{K}$	The add-up sign over every class from $k = 1$ to $k = K$ . The result is a single number: the total of all the terms written after the sign.
$1$	The number 1, which stands for the whole node. The shares of all the classes add up to 1, so subtracting the sum of squared shares from 1 turns a measure of how concentrated the node is into a measure of how mixed it is. It has no unit.

The formula piece by piece

$p_k$: Start with one share. $p_k$ is the fraction of the node that belongs to class $k$ . If the node has 6 red examples out of 10, the share for red is $p_{\text{red}} = 0.6$ , a number between 0 and 1 that tells how common that class is in this node.
$p_k^2$: Square each share. Squaring makes the big shares count much more than the small ones. The share 0.6 squares to 0.36, while the share 0.4 squares to only 0.16. When one class fills the whole node, its share is 1, and its square is also 1.
$\sum_{k=1}^{K} p_k^2$: Add up the squares of all the shares. If one class fills the node, this sum is exactly 1. If the classes are evenly mixed, the sum becomes smaller, down to $\frac{1}{K}$ . The sum measures how concentrated the node is, which is the opposite of how mixed it is.
$G = 1 - \sum_{k=1}^{K} p_k^2$: The Gini impurity of a node equals 1 minus the sum, over every class, of the square of that class’s share. A pure node gives 1 minus 1, which is 0.
$G = \sum_{k=1}^{K} p_k (1 - p_k)$: A second standard form of the same law. Each class contributes its share times one minus its share, and the contributions add up. It gives the same number as the form above, because $p_k(1 - p_k) = p_k - p_k^2$ , and the shares add up to 1.

What the formula is doing, and why

The input is one node: a group of examples, each with a known class. We measure the share of each class, from $p_1$ up to $p_K$ . The output is one number, $G$ . A value of 0 means the node is pure, with one class only. Bigger values mean a more mixed node, and the largest value, $1 - \frac{1}{K}$ , comes when every class has the same share.

Why square the shares? Shares always add up to 1, so we need a way to tell a lopsided mix from an even one. Squaring does this. For two classes split 50-50, the squares add up to $0.5^2 + 0.5^2 = 0.5$ . For a split of 90-10, the squares add up to $0.9^2 + 0.1^2 = 0.82$ , which is bigger. A lopsided node has a larger sum of squares, so the sum measures how concentrated the node is.

Why subtract from 1? We want a pure node to score 0 and a mixed node to score more. The sum of squares does the opposite: it is 1 for a pure node and smaller for a mixed node. Subtracting it from 1 flips the direction, so the score grows with mixing. If all $K$ shares are equal, each share is $\frac{1}{K}$ , the sum of squares is $K \times \frac{1}{K^2} = \frac{1}{K}$ , and $G = 1 - \frac{1}{K}$ .

The chance reading. Draw two examples from the node at random, put the first one back, and draw again. The sum of squares is the chance that both draws have the same class. So $G$ is the chance that the two draws have different classes. In the marble bag analogy, that is the chance that the second marble has a different color from the first.

Why a weighted average for splits? A tree judges a question by the impurity of the groups it creates. It takes the Gini score of each child group and averages them, weighting each child by its number of examples divided by the parent’s number. A large mixed child then counts for more than a tiny one. The tree picks the question that lowers this average the most. This is how the CART method works for classification trees. When the goal is to predict a number, a regression tree uses a different measure.

An everyday picture

Picture a bag of marbles. Draw one marble, note its color, put it back and draw again. Gini impurity is the chance that the second marble has a different color from the first. A bag with only red marbles never gives a different color, so its impurity is 0. A bag with equal numbers of two colors gives a different color half the time, so its impurity is 0.5.

Worked example: A question that sorts marbles

A bag holds 10 marbles: 6 red and 4 blue. A question sorts them into two smaller bags. The left bag gets 5 red marbles and no blue. The right bag gets the remaining 1 red marble and all 4 blue marbles. We want to know how much this question lowers the mix of colors.

Score the full bag before the split. The full bag has 6 red marbles out of 10, so the red share is $p_{\text{red}} = 0.6$ , and the blue share is $p_{\text{blue}} = 0.4$ . Their squares are $0.36$ and $0.16$ , which add to $0.52$ , so $G = 1 - 0.52 = 0.48$ . This is the mix the question will try to make purer.
Score the left bag. It holds only red marbles, so its red share is $1$ and its blue share is $0$ . The squares add up to $1$ , so $G = 1 - 1 = 0$ . A bag with one color has no mixing at all, so its score is exactly zero.
Score the right bag. It holds 5 marbles: 1 red and 4 blue. The shares are $\frac{1}{5} = 0.2$ for red and $\frac{4}{5} = 0.8$ for blue. Their squares are $0.04$ and $0.64$ , which add to $0.68$ , so $G = 1 - 0.68 = 0.32$ .
Weight each bag by its size. Each bag holds 5 of the 10 marbles, so each weight is $\frac{5}{10} = 0.5$ . The weighted average is $0.5 \times 0 + 0.5 \times 0.32 = 0.16$ . Weights make a bag with more marbles count for more, so the average reflects where most of the marbles went.
Find the drop in impurity. The full bag scored 0.48, and the weighted average of the two smaller bags is 0.16. The drop is $0.48 - 0.16 = 0.32$ . A tree would compare this drop with the drop from every other question it could ask.
Put the drop in context. The largest Gini value for two colors is $1 - \frac{1}{2} = 0.5$ , so the starting score of 0.48 was already close to the most mixed a two-color bag can be. The split brings the average down to 0.16, which is much closer to pure.

Answer: The split lowers the Gini impurity from 0.48 to 0.16, a drop of 0.32. The left bag is pure, and the right bag is mostly blue. Among all the questions a tree could ask, it would prefer the one that gives the largest drop.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Confusing Gini impurity with the Gini coefficient, a different measure of income inequality. The two share a name but not a purpose.
Forgetting to weight the children. A small pure bag should count for less than a large mixed bag, and the weight $\frac{\text{child size}}{\text{parent size}}$ is what makes that happen.
Treating $G$ as the error rate. $G$ measures how mixed a node is, not how many predictions are wrong. Always predicting the largest class gives an error rate of one minus the largest share, $1 - \max_k p_k$ , which is a different number.
Using Gini to score a regression tree. A regression tree predicts a number, and it uses a different measure, such as how spread out the target numbers are in each node.

Where you will meet it

CART decision trees, which use Gini impurity to choose each split when the goal is to sort examples into classes.
Random forests, which build many decision trees and often use Gini impurity to score their splits.
The decision tree classifier in the scikit-learn Python library, where Gini is the default way to score a split.

Questions people ask

Is Gini impurity the same as entropy?

No, but both measure how mixed a node is. Entropy is another mixing score, measured in bits. It uses a different formula, so the numbers differ, but the two often pick the same split. The information gain page on this site covers entropy.

What is the largest possible Gini value?

It is $1 - \frac{1}{K}$ , reached when all $K$ classes have equal shares. With two classes that is 0.5, and with three classes it is about 0.667.

What does a Gini value of 0 mean?

The node is pure: every example belongs to one class. No split can lower its impurity, so a tree stops splitting that branch.

Is a low Gini always good?

A low value at a leaf, which is an end box of the tree, looks good on the training data. Training data is the set of examples the tree learns from. But a tree that splits until every leaf is pure can memorize noise. Limits such as a maximum depth, which stops the tree after a set number of questions, guard against that.

Information Gain: Information gain is a score for how much a yes-or-no question reduces our uncertainty about the class of each example, so a tree can ask the question that sorts its examples best.
Shannon Entropy: Shannon entropy is one number, measured in bits, that says how unpredictable a source of messages is on average: the more predictable it is, the fewer bits its messages need.
Classification Accuracy: Accuracy is the share of a model’s guesses that were right, out of all the guesses it made.