Gini Impurity for Decision-Tree Splits - Supervised Learning

Gini Impurity for Decision-Tree Splits

Compute the Gini impurity of a set of class labels, the score a classification tree uses to judge how "mixed" a node is.

Background

A decision tree grows by picking, at each node, the split that makes the children as pure as possible. Gini impurity is the probability that two labels drawn at random (with replacement) from the node disagree. It is the default criterion of scikit-learn's DecisionTreeClassifier, and you will use it to grow full trees in Decision Tree Classifier with Bagging.

Formula

Gini(S) = 1 - sum_c p_c^2,     p_c = (number of labels equal to c) / |S|

The sum runs over the classes that appear in S. For a split into L and R, a tree scores the weighted average (|L| * Gini(L) + |R| * Gini(R)) / |S| and picks the split with the lowest value.

Labels	Proportions	Gini
[0, 0, 0, 0]	1.0	0.0 (pure)
[0, 0, 0, 1]	0.75, 0.25	0.375
[0, 0, 1, 1]	0.5, 0.5	0.5 (max for 2 classes)
[0, 1, 2]	1/3 each	0.6667

With K classes the maximum is 1 - 1/K, so Gini is always in [0, 1).

Inputs

• labels: 1D array of class labels (non-negative integers), shape (n,). Labels need not be contiguous ([3, 7, 7] is fine).

Expected Return Format

A float (Python or NumPy scalar), not rounded.

Edge Cases and Conventions

• An empty array has impurity 0.0.
• Only the proportions matter, not the label values themselves.

Constraints

• NumPy only; no sklearn.

Follow-up

• Entropy -sum p_c log2 p_c is the other common criterion. Why do Gini and entropy usually pick the same split, and why is Gini slightly cheaper?

Input: gini_impurity(np.array([0, 0, 0, 0]))
Output: 0.0

Input: gini_impurity(np.array([0, 0, 0, 1]))
Output: 0.375

Input: gini_impurity(np.array([3, 3, 7, 7, 7]))
Output: 0.48

import numpy as np

def gini_impurity(labels: np.ndarray) -> float:
    """
    Calculate the Gini impurity of a set of labels.

    Args:
        labels: 1D array of class labels (non-negative integers), shape (n,)

    Returns:
        Gini impurity 1 - sum_c p_c^2, in [0, 1) (0.0 for an empty array)
    """
    # Your code here
    pass