Understanding Split Criteria: Gini Impurity & Information Gain

Part 1: Quantifying Purity

In the last lesson, we described a "good" split as one that makes the resulting groups (the child nodes) as homogeneous as possible.

• A node is perfectly pure (homogeneous) if all data points in it belong to a single class.
• A node is maximally impure (heterogeneous) if the data points are evenly distributed among all classes.

For a computer to find the best split, we need to translate this idea into a number. This number is called an impurity measure. The goal of the algorithm is to perform a split that leads to the largest reduction in impurity. Two of the most common impurity measures used in classification trees are Gini Impurity and Entropy.

Part 2: Gini Impurity

Gini Impurity is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it were randomly labeled according to the distribution of labels in the subset. It's the default criterion used in scikit-learn's DecisionTreeClassifier.

The formula for Gini Impurity for a set of items with $k$ classes is:

where $p_i$ is the probability of a data point belonging to class $i$.

• For a pure node, the probability of the single class is 1 ($p_1=1$), and all others are 0. The Gini impurity is $1-(1^2)=0$.
• For a maximally impure node with two classes (50/50 split), $p_1=0.5$ and $p_2=0.5$. The Gini impurity is $1-(0.5^2+0.5^2)=1-(0.25+0.25)=0.5$.

The following video from StatQuest provides a fantastic, step-by-step walkthrough of how to calculate Gini impurity for individual nodes and then for an entire split.

How Gini Impurity is Used to Find the Best Split

As the video explained, the process to find the best split using Gini Impurity is:

1. Calculate the Gini Impurity of the current (parent) node before any split.
2. For every possible split (i.e., for each feature and each unique value/threshold):
   a. Calculate the Gini Impurity of each potential child node.
   b. Calculate the weighted average Gini Impurity for the split:
   ${\text{Gini}}_{\text{split}}={\sum }_{j=1}^m\frac{N_j}{N}\times \text{Gini}(j)$
   where $N$ is the total number of samples in the parent node, $m$ is the number of child nodes (usually 2), $N_j$ is the number of samples in child node $j$, and $\text{Gini}(j)$ is the Gini impurity of child node $j$.
3. Calculate the Gini Gain (or impurity reduction): $$\text{Gini Gain}={\text{Gini}}_{\text{parent}}-{\text{Gini}}_{\text{split}}$$
4. The algorithm selects the split with the highest Gini Gain.

This image clearly illustrates this comparison process. The algorithm calculates the weighted Gini score for splits on different features and chooses the one with the lowest score (which corresponds to the highest Gini Gain).

Part 3: Entropy and Information Gain

Another popular splitting criterion is Information Gain, which is based on the concept of Entropy from information theory.

Entropy is also a measure of impurity or disorder. Its formula is:

where $p_i$ is the probability of a data point belonging to class $i$.

• For a pure node ($p_1=1$), the Entropy is $-(1\cdot {\log }_2(1))=0$.
• For a maximally impure node with two classes (50/50 split), the Entropy is $-(0.5\cdot {\log }_2(0.5)+0.5\cdot {\log }_2(0.5))=1$.

The value log_2(p_i) can be thought of as the "amount of information" needed to identify the class of a new data point. Entropy is the expected value of this information. A pure node requires no new information, so its entropy is zero.

The video below explains Entropy and Information Gain in detail.

Just like with Gini Gain, the algorithm calculates the Information Gain for every possible split and chooses the one that maximizes it.

Information Gain = ${\text{Entropy}}_{\text{parent}}-{\text{Entropy}}_{\text{split}}$

where ${\text{Entropy}}_{\text{split}}$ is the weighted average of the entropy of the child nodes.

Part 4: Gini Impurity vs. Entropy

You might be wondering which criterion to use. In practice, both Gini Impurity and Entropy are effective and often lead to very similar trees. However, there are some subtle differences.

The same video resource provides an excellent comparison.

Here's a summary of the key differences:

Despite these differences, choosing between them is rarely the most critical hyperparameter to tune. In most scenarios, the resulting trees will be very similar. Gini's computational efficiency is why it's a common default.

Conclusion

You now have the statistical foundation to understand exactly how a decision tree learns. Instead of being a black box, you can see that the tree-building process is a methodical search for splits that maximize purity.

Key Takeaways:

• Decision trees use splitting criteria to find the best feature and threshold to split the data at each node.
• Gini Impurity and Entropy are the two primary metrics used to measure the impurity or disorder of a node in a classification tree. A score of 0 indicates a perfectly pure node.
• The algorithm seeks to maximize the impurity reduction, which is called Gini Gain (when using Gini) or Information Gain (when using Entropy).
• Gini Impurity is computationally faster and the default in libraries like scikit-learn, but both criteria are effective and typically yield similar results.

Preview of the Next Lesson:
While powerful and interpretable, single decision trees have a significant weakness: they are prone to overfitting and can be unstable, meaning small changes in the training data can lead to a completely different tree. In our next lesson, we will address this by introducing bootstrap aggregating (bagging), an ensemble technique that combines multiple decision trees to create a much more robust and accurate model, leading us directly to the famous Random Forest algorithm.