Decision tree — node impurity (Gini & entropy)

Background

When a decision tree decides where to split, it measures how mixed a node's labels are. Two classic measures are Gini impurity and entropy. A node with a single class is pure (impurity 0); a node with an even mix of classes is maximally impure. Every CART/ID3 split is chosen to reduce this impurity the most.

Problem statement

Implement node_impurity(labels) returning the tuple (gini, entropy) for the class labels at a node. With $p_k$ the fraction of samples in class $k$:

$$\text{Gini} = 1 - \sum_k p_k^2, \qquad\qquad \text{Entropy} = -\sum_k p_k \log_2 p_k$$

Entropy is in bits. Use the convention $0\cdot\log_2 0 = 0$.

Input

• labels — an array-like of class labels of any hashable type (ints, strings, booleans).

Output

• A tuple (gini, entropy) of two floats.

Examples

Example 1

Input:  labels = [1, 1, 1, 1, 1, 1, 0, 0, 0, 0]
Output: (0.48, 0.9709505944546686)

Explanation: 6 of 10 are class 1 and 4 are class 0, so $p = [0.6, 0.4]$. Gini $= 1 - (0.6^2 + 0.4^2) = 0.48$ and Entropy $= -(0.6\log_2 0.6 + 0.4\log_2 0.4) \approx 0.971$ bits.

Constraints

• Works for any number of classes and any hashable label type.
• A pure node (all labels equal) returns (0.0, 0.0).
• Gini lies in $[0, 1)$; entropy is $\ge 0$ and equals $\log_2 C$ for $C$ equally-likely classes.

Notes

• Only classes that actually appear contribute, so the $0\log 0$ case never arises if you build proportions from observed counts.