Splitting Decisions: Gini & Information Gain

The Core Idea: Purity and Information

A decision tree works by recursively splitting a dataset into smaller and smaller subsets. The ideal split is one that separates the data into "pure" nodes, where each node contains samples of only one class.

To get a clear picture of this process, let's watch a short conceptual overview.

As the video explained, we need two things: a way to measure impurity in a node and a way to measure the improvement a split provides. Let's implement both from scratch.

1. Measuring Impurity: The Gini Index

The Gini index (or Gini impurity) is a measure of how often a randomly chosen element from a set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the set.

Its formula is:
$Gini=1-{\sum }_{i=1}^c{p}_i^2$
where $c$ is the number of classes and $p_i$ is the probability of class $i$ in the node.

• A Gini score of 0 is a perfect score. It means the node is pure (all samples belong to one class).
• For a binary classification problem, the worst-case Gini score is 0.5, which means the node is perfectly mixed (50% class A, 50% class B).

Let's look at how to translate this into a clean Python function.

Now, let's write our own NumPy-based version. This function will be a core building block.

import numpy as np
from collections import Counter

def gini_impurity(y):
    """
    Calculates the Gini impurity for a vector of labels.
    
    Args:
        y: A NumPy array of labels.
        
    Returns:
        The Gini impurity score (float).
    """
    # Count the occurrences of each class
    counts = Counter(y)
    
    # If the node is empty or pure, impurity is 0
    if len(counts) <= 1:
        return 0
        
    impurity = 1.0
    num_samples = len(y)
    
    for label in counts:
        prob_of_label = counts[label] / num_samples
        impurity -= prob_of_label**2
        
    return impurity

# --- Let's test it ---
# A pure node (all class 0)
pure_node = np.array([0, 0, 0, 0, 0])
print(f"Impurity of a pure node: {gini_impurity(pure_node):.4f}")

# A perfectly mixed node (50/50)
mixed_node = np.array([0, 1, 0, 1, 0, 1])
print(f"Impurity of a mixed node: {gini_impurity(mixed_node):.4f}")

# An imbalanced node
imbalanced_node = np.array([0, 0, 0, 0, 1])
print(f"Impurity of an imbalanced node: {gini_impurity(imbalanced_node):.4f}")

You should see an output of 0.0, 0.5, and 0.32 respectively, which confirms our understanding.

2. Measuring the Split's Quality: Information Gain

Now that we can measure how "bad" a node is, we can measure how much "better" a split makes things. This is Information Gain.

It's calculated as the impurity of the parent node minus the weighted average of the impurities of the child nodes.

$IG={\text{Impurity}}_{\text{parent}}-\left(\frac{N_{\text{left}}}{N_{\text{parent}}}{\text{Impurity}}_{\text{left}}+\frac{N_{\text{right}}}{N_{\text{parent}}}{\text{Impurity}}_{\text{right}}\right)$

Where $N$ is the number of samples in a node. A higher information gain means a better split.

Let's implement this. Our function will take the parent labels and the labels of the two children produced by a split.

def information_gain(parent_y, left_y, right_y, impurity_func=gini_impurity):
    """
    Calculates the information gain of a split.
    
    Args:
        parent_y: Labels of the data in the parent node.
        left_y: Labels of the data in the left child node.
        right_y: Labels of the data in the right child node.
        impurity_func: The function to use for calculating impurity (e.g., gini_impurity).
        
    Returns:
        The information gain score (float).
    """
    # If a child node is empty, the split is not useful
    if len(left_y) == 0 or len(right_y) == 0:
        return 0
        
    # Calculate impurity of the parent
    parent_impurity = impurity_func(parent_y)
    
    # Calculate weighted average impurity of children
    n_parent = len(parent_y)
    n_left, n_right = len(left_y), len(right_y)
    
    weight_left = n_left / n_parent
    weight_right = n_right / n_parent
    
    weighted_child_impurity = (weight_left * impurity_func(left_y) + 
                               weight_right * impurity_func(right_y))
    
    # Calculate information gain
    ig = parent_impurity - weighted_child_impurity
    return ig

# --- Let's test it with a simple split ---
parent_node = np.array([0, 0, 1, 1, 0, 1]) # Gini = 0.5

# A "perfect" split that separates the classes
perfect_split_left = np.array([0, 0, 0])
perfect_split_right = np.array([1, 1, 1])

ig_perfect = information_gain(parent_node, perfect_split_left, perfect_split_right)
print(f"Information gain of a perfect split: {ig_perfect:.4f}")


# A "useless" split that doesn't improve purity
useless_split_left = np.array([0, 1, 0])
useless_split_right = np.array([1, 0, 1])

ig_useless = information_gain(parent_node, useless_split_left, useless_split_right)
print(f"Information gain of a useless split: {ig_useless:.4f}")

The perfect split gives an information gain of 0.5, completely removing all impurity. The useless split results in an information gain of around 0.056, showing it barely helped.

3. An Alternative: Entropy

Gini impurity is not the only metric. Another popular choice is Entropy, which comes from information theory. It also measures uncertainty or randomness.

Its formula is:
$Entropy=-{\sum }_{i=1}^c{p}_i{\log }_2(p_i)$

• Entropy is 0 for a pure node.
• For a binary problem, it's 1 for a perfectly mixed node.

The concept of Information Gain remains exactly the same; you just swap out the Gini function for the Entropy function.

Here is the implementation for entropy:

def entropy(y):
    """
    Calculates the Entropy for a vector of labels.
    """
    counts = Counter(y)
    
    if len(counts) <= 1:
        return 0
        
    entropy_val = 0.0
    num_samples = len(y)
    
    for label in counts:
        prob_of_label = counts[label] / num_samples
        entropy_val -= prob_of_label * np.log2(prob_of_label)
        
    return entropy_val

# --- Test it on the same nodes ---
print(f"\nEntropy of a pure node: {entropy(pure_node):.4f}")
print(f"Entropy of a mixed node: {entropy(mixed_node):.4f}")
print(f"Entropy of an imbalanced node: {entropy(imbalanced_node):.4f}")

You'll see scores of 0.0, 1.0, and 0.7219. While the scales are different, they rank the nodes' purity in the same order as Gini. In practice, Gini is often the default because it's slightly faster to compute (no logarithm), but both are excellent choices.

Conclusion

Great work today! You have implemented the fundamental metrics that drive the construction of a decision tree. These functions allow the algorithm to make a quantitative, data-driven choice at every step of the tree-building process.

Key Takeaways:

• Impurity measures the "mixed-up-ness" of labels in a node. We implemented two common metrics: Gini Impurity and Entropy.
• Information Gain measures the reduction in impurity achieved by a split. It is the core criterion for choosing the best feature and value to split on.
• The goal of the algorithm is to always choose the split that maximizes information gain.

Preview of the Next Lesson:
We now have the tools to evaluate a split, but we still need to find the best one. In the next lesson, we will implement a function to find the best possible split for a dataset. This will involve iterating through every feature and every possible split point, calculating the information gain for each, and keeping track of the one that performs best. This is the heart of the decision tree learning algorithm.