Splitting Criteria: Gini, Entropy and Variance Reduction

A decision tree grows by asking questions, and at every node it has thousands of candidates to choose from: every feature, every threshold. To pick one it needs a single number that says how much better off it is after the split than before. That number is what a splitting criterion produces, and it is the only place a tree ever consults the data. Get it right and the tree finds the structure; get it subtly wrong and the tree spends its depth budget on noise columns.

The analogy: sorting marbles into jars

You have a sack containing 400 red marbles and 400 blue ones, thoroughly mixed. You are allowed to tip it into two jars using one rule — "all the big ones left, all the small ones right", say — and then you are scored on how unmixed the jars are.

A perfect rule sends all the reds to one jar and all the blues to the other; both jars are pure and you score full marks. A useless rule sends a 50-50 mixture to each jar; you have moved marbles without learning anything. Every real rule sits in between, and what you need is a way to put a number on "how mixed is this jar" so you can compare rules. That number is an impurity, and the value of a rule is the drop in impurity it achieves.

Two details matter and both are intuitive. The jars are usually different sizes, so you must weight each jar's impurity by how many marbles it holds — a spectacularly pure jar containing three marbles is not worth much. And you always compare against the sack you started with, because a node that was already nearly pure has little left to gain.

The three impurities

Write $p_k$ for the fraction of a node belonging to class $k$. The tree's candidate measures are:

$$G \;=\; 1 - \sum_k p_k^2, \qquad H \;=\; -\sum_k p_k \log_2 p_k, \qquad E \;=\; 1 - \max_k p_k$$

In plain English, one at a time.

Gini, $G$. Draw two rows from this node at random, with replacement. $G$ is the probability they belong to different classes. Zero if the node is pure; $0.5$ for a two-class node that is exactly half and half.

Entropy, $H$. The average number of yes/no questions you would need to identify the class of a random row from this node, if you asked optimally. Zero for a pure node; exactly 1 bit for a 50-50 two-class node.

Misclassification error, $E$. If you had to guess one class for the whole node, this is the fraction you would get wrong. Also zero when pure, also $0.5$ at 50-50.

The score of a split is the same for all three. With a parent node of $n$ rows splitting into children of $n_L$ and $n_R$ rows,

$$\text{gain} \;=\; I(\text{parent}) \;-\; \frac{n_L}{n} I(\text{left}) \;-\; \frac{n_R}{n} I(\text{right})$$

In plain English: impurity before, minus the size-weighted average impurity after. The tree computes this for every candidate question and keeps the largest.

The bulge matters more than the height. An impurity curve that bows outward — strictly concave, in the jargon — guarantees that splitting can never increase the weighted impurity, so the gain is never negative. The error rate is only piecewise linear, so a split that genuinely helps can score exactly zero against it. The next example shows that happening.

For the two-class case Gini has a simple closed form, $G = 2p(1-p)$, an upside-down parabola. The explorer below is set to draw it. Only the stretch between $x = 0$ and $x = 1$ has meaning — read $x$ as the fraction of one class — and the probe readout gives you the Gini of any node you like.

Worked example 1: where the error rate fails and the other two do not

A node holds 400 rows of class 1 and 400 of class 0. Two candidate questions are on the table.

• Split A produces children of $(300, 100)$ and $(100, 300)$ — both 400 rows.
• Split B produces children of $(200, 400)$ and $(200, 0)$ — 600 rows and 200 rows.

Score them all three ways. The parent is 50-50, so $G = 0.5$, $H = 1$, $E = 0.5$.

Misclassification error. Split A's children are each 75-25, so each has $E = 0.25$; the weighted average is $0.5(0.25) + 0.5(0.25) = 0.25$ and the gain is $0.25$. Split B's first child is 200 of one class and 400 of the other, so $E = 200/600 = 0.333$; its second child is pure, so $E = 0$. The weighted average is $0.75(0.333) + 0.25(0) = 0.25$ and the gain is again $0.25$. A dead tie — the error rate cannot see the difference.

Gini. Split A: each child scores $1 - (0.75^2 + 0.25^2) = 1 - 0.625 = 0.375$, so the weighted average is $0.375$ and the gain is $0.5 - 0.375 = 0.125$. Split B: the first child scores $1 - \left(\tfrac{1}{9} + \tfrac{4}{9}\right) = \tfrac{4}{9} = 0.444$ and the pure child scores 0, so the weighted average is $0.75(0.444) = 0.333$ and the gain is $0.5 - 0.333 = 0.167$. B wins.

Entropy. Split A: each child scores $-(0.75\log_2 0.75 + 0.25 \log_2 0.25) = 0.311 + 0.5 = 0.811$, so the gain is $1 - 0.811 = 0.189$. Split B: the first child scores $-\left(\tfrac{1}{3}\log_2 \tfrac{1}{3} + \tfrac{2}{3}\log_2 \tfrac{2}{3}\right) = 0.528 + 0.390 = 0.918$, the pure child scores 0, the weighted average is $0.75(0.918) = 0.689$, and the gain is $1 - 0.689 = 0.311$. B wins again.

Split B is plainly the better question — it settles 200 rows for good, and the tree never has to look at them again. Both curved criteria say so. The straight one cannot. That is the whole argument for using Gini or entropy rather than accuracy as the splitting rule, and it is also why a tree tuned by accuracy alone can stall on data where a good split is available.

Worked example 2: variance reduction for a numeric target

For regression there are no classes, so impurity becomes the spread of the target around the node's mean — its variance. Eight days of returns in basis points land in a node: $-6, -4, -2, 0, 3, 5, 7, 9$. The mean is $12/8 = 1.5$ and the sum of squared deviations is

$$56.25 + 30.25 + 12.25 + 2.25 + 2.25 + 12.25 + 30.25 + 56.25 \;=\; 202$$

so the node's variance is $202/8 = 25.25$.

Candidate split 1 cuts it down the middle into $\{-6,-4,-2,0\}$ and $\{3,5,7,9\}$. The left child has mean $-3$ and squared deviations $9+1+1+9 = 20$, so variance 5. The right child has mean 6 and the same variance 5. The weighted average is $0.5(5) + 0.5(5) = 5$, and the variance reduction is $25.25 - 5 = 20.25$.

Candidate split 2 cuts it at a different threshold, into $\{-6,-4,-2,0,3\}$ and $\{5,7,9\}$. The left child has mean $-1.8$, squared deviations $17.64 + 4.84 + 0.04 + 3.24 + 23.04 = 48.8$, and variance $9.76$. The right child has mean 7, squared deviations $4 + 0 + 4 = 8$, and variance $8/3 = 2.67$. The weighted average is $\tfrac{5}{8}(9.76) + \tfrac{3}{8}(2.67) = 6.10 + 1.00 = 7.10$, so the reduction is $25.25 - 7.10 = 18.15$.

The first split wins, and the tree takes it.

What this means in practice

Gini and entropy disagree on the chosen split in only a small minority of cases — studies put it around two percent — and when they do, the resulting trees perform indistinguishably. Gini is the default in most libraries because it avoids a logarithm per candidate, which matters when you are scoring millions of thresholds inside a boosted ensemble. Do not spend tuning budget on this choice. Max depth, minimum samples per leaf and the number of trees each matter enormously more.

Where the criterion genuinely changes is in modern gradient boosting. Libraries like Gradient Boosting in Finance do not use Gini at all; they split to maximise the reduction in the actual training loss, using gradient and Hessian statistics accumulated per candidate bin. The structure is identical — parent score minus weighted children scores — but the score is derived from the loss you asked for rather than a generic purity measure.

And the criterion is what makes trees convenient on messy financial data. It never compares two features to each other directly, only rankings within one feature at a time, so it is completely indifferent to scale: no standardisation, no log transforms, monotone transformations of a feature leave every split unchanged.