Choosing a Decision-Tree Split by Entropy

Pick the feature and threshold that most reduce label impurity, the greedy step that grows a decision tree.

Impurity

A decision tree splits data to make the resulting groups as pure - single-class - as possible. Entropy measures impurity: H = -sum p_i log2 p_i, zero for a pure node and 1 bit for a balanced two-class node. Gini impurity 1 - sum p_i^2 is a similar, cheaper alternative.

Information gain

For a candidate split, compute the weighted average entropy of the children and subtract it from the parent entropy. That reduction is the information gain. The tree greedily chooses the feature and threshold with the highest gain, then recurses on each child.

import numpy as np
def entropy(y):
    p=np.bincount(y)/len(y); p=p[p>0]
    return -(p*np.log2(p)).sum()
x=np.array([1,2,3,4,5,6.]); y=np.array([0,0,0,1,1,1])
best=None
for thr in (x[:-1]+x[1:])/2:
    L=y[x<thr]; R=y[x>=thr]
    child=(len(L)*entropy(L)+len(R)*entropy(R))/len(y)
    gain=entropy(y)-child
    if best is None or gain>best[1]: best=(thr,gain)
print('best threshold',best[0],'gain',round(best[1],3))

Reading the result

The example finds a threshold of 3.5, which perfectly separates the two classes - information gain equals the full parent entropy of 1 bit. Real data rarely split so cleanly; the tree keeps splitting until nodes are pure enough or a stopping rule fires.

Overfitting and forests

A tree grown to purity memorizes noise. Pruning, a maximum depth, or a minimum samples-per-leaf control this. Averaging many trees trained on bootstrapped data and random feature subsets - a random forest - reduces variance dramatically, and gradient-boosted trees add them sequentially to correct residual errors. The single split shown here is the atom of all of these.