Gini Index for Decision Trees: Mechanism, Perfect & Imperfect Split With Examples

As you start learning about supervised learning, it’s important to get acquainted with the concept of decision trees. Decision trees are akin to simplified diagrams that assist in solving various types of problems by making sequential decisions. One key metric used in enhancing the efficiency of decision trees is the Gini Index. This criterion plays a crucial role in guiding decision trees on how to optimally partition the data they’re presented with.

Here, we’re looking closely at something called the Decision tree for Gini Index. It’s a tool that helps decision trees decide how to split up the information they’re given. 

In this article, I’ll explain the Gini Index in easy words. We’ll talk about perfect and imperfect splits using examples you can relate to. By the end, you’ll see how decision trees can help solve real problems, making it easier for you to use them in your own work. Let’s get started! 

What is Gini Index?

The Gini Index is a way of quantifying how messy or clean a dataset is, especially when we use decision trees to classify it. It goes from 0 (cleanest, all data points have the same label) to 1 (messiest, data points are split evenly among all labels). 

Think of a dataset that shows how much money people make. A high Gini Index for this data means that there is a huge difference between the rich and the poor, while a low Gini Index means that the income is more balanced. 

When we build decision trees, we want to use the Gini Index to find the best feature to split the data at each node. The best feature is the one that reduces the Gini Index the most, meaning that it creates the purest child nodes. This way, we can create a tree that can distinguish different labels based on the features. 

What Does a Decision Tree do?

A decision tree is a machine learning algorithm used for both classification and regression tasks. It resembles a tree-like structure with branches and leaves. Each branch represents a decision based on a specific feature of the data, and the leaves represent the predicted outcome. 

Data points navigate through the decision tree based on their respective feature values, traversing down branches determined by the split conditions that are chosen using the decision tree Gini index as a criterion for selection. Ultimately, they reach a leaf and receive the prediction assigned to that leaf. Decision trees are popular for their interpretability and simplicity, allowing easy visualization of the decision-making process. The Gini Index plays a crucial role in building an effective decision tree by guiding the selection of optimal splitting features. By minimizing the Gini index for decision tree at each node, the tree progressively separates data points belonging to different classes, leading to accurate predictions at the terminal leaves. 

Here’s a breakdown of how to build decision tree using Gini index: 

1. Calculate the Gini Index of the entire dataset. This represents the initial level of impurity before any splitting. 
2. Consider each feature and its threshold values. For each combination, calculate the Gini Index of the two resulting child nodes after splitting the data based on that feature and threshold. 
3. Choose the feature and threshold combination that leads to the smallest Gini Index for the child nodes. This indicates the most significant decrease in impurity, resulting in a more homogeneous separation of data points. 
4. Repeat the process recursively on each child node. Use the same approach to select the next split feature and threshold, further minimizing the Gini Index and separating data points based on their class labels. 
5. Continue splitting until a stopping criterion is met. This could be reaching a pre-defined tree depth, minimum data size per node, or a sufficiently low Gini Index at all terminal leaves. 

 By iteratively using the Decision Tree Gini Index to guide feature selection and data partitioning, decision trees can effectively learn complex relationships within the data and make accurate predictions for unseen instances. 

Flow of a Decision Tree 

Here I have noted the flow of a decision tree Gini index:

1. Training: The decision tree is built by applying a splitting algorithm to the training data. The algorithm chooses the feature and its threshold value that best minimizes the Gini Index within the resulting child nodes. This process is repeated recursively on each subgroup until reaching a stopping criterion, like minimum data size or maximum tree depth. 
2. Prediction: A new data point traverses the tree based on its own feature values, navigating down branches determined by the splitting conditions. Finally, it reaches a leaf and receives the prediction assigned to that leaf. 
3. Ensembles: Decision trees can be combined into ensembles like random forests or boosting to improve accuracy and reduce overfitting. This involves building multiple trees from different subsets of the data and aggregating their predictions, leading to a more robust model. 

Calculation

The Gini Index or Gini Impurity is calculated by subtracting the sum of the squared probabilities of each class from one. It favours mostly the larger partitions and are very simple to implement. In simple terms, it calculates the probability of a certain randomly selected feature that was classified incorrectly.

The Gini Index varies between 0 and 1, where 0 represents purity of the classification and 1 denotes random distribution of elements among various classes. A Gini Index of 0.5 shows that there is equal distribution of elements across some classes.

Mathematically, The Gini Index is represented by 

The Gini Index works on categorical variables and gives the results in terms of “success” or “failure” and hence performs only binary split. It isn’t computationally intensive as its counterpart – Information Gain. From the Gini Index, the value of another parameter named Gini Gain is calculated whose value is maximized with each iteration by the Decision Tree to get the perfect CART

FYI: Free NLP course!

Let us understand the calculation of the Gini Index with a simple example. In this, we have a total of 10 data points with two variables, the reds and the blues. The X and Y axes are numbered with spaces of 100 between each term. From the given Gini index Decision tree example , we shall calculate the Gini Index and the Gini Gain.

For a decision tree, we need to split the dataset into two branches. Consider the following data points with 5 Reds and 5 Blues marked on the X-Y plane. Suppose we make a binary split at X=200, then we will have a perfect split as shown below.

It is seen that the split is correctly performed and we are left with two branches each with 5 reds (left branch) and 5 blues (right branch).

But what will be the outcome if we make the split at X=250?

We are left with two branches, the left branch consisting of 5 reds and 1 blue, while the right branch consists of 4 blues. The following is referred to as an imperfect split. In training the Decision Tree model, to quantify the amount of imperfectness of the split, we can use the Gini Index. 

Checkout: Types of Binary Tree

Basic Mechanism

To calculate the Gini Impurity, let us first understand it’s basic mechanism.

• First, we shall randomly pick up any data point from the dataset
• Then, we will classify it randomly according to the class distribution in the given dataset. In our dataset, we shall give a data point chosen with a probability of 5/10 for red and 5/10 for blue as there are five data points of each colour and hence the probability.

Now, in order to calculate the Gini index decision tree formula:

Where, C is the total number of classes and p(i) is the probability of picking the data point with the class i.

In the above Gini index decision tree solved example, we have C=2 and p(1) = p(2) = 0.5, Hence the Gini Index can be calculated as,

G =p(1) ∗ (1−p(1)) + p(2) ∗ (1−p(2))

    =0.5 ∗ (1−0.5) + 0.5 ∗ (1−0.5)

    =0.5

Where 0.5 is the total probability of classifying a data point imperfectly and hence is exactly 50%.

Now, let us calculate the Gini Impurity for both the perfect and imperfect split that we performed earlier,

Perfect Split

The left branch has only reds and hence its Gini Impurity is,

G(left) =1 ∗ (1−1) + 0 ∗ (1−0) = 0

The right branch also has only blues and hence its Gini Impurity is also given by,

G(right) =1 ∗ (1−1) + 0 ∗ (1−0) = 0

From the quick calculation, we see that both the left and right branches of our perfect split have probabilities of 0 and hence is indeed perfect. A Gini Impurity of 0 is the lowest and the best possible impurity for any data set.

Imperfect Split 

In this case, the left branch has 5 reds and 1 blue. Its Gini Impurity can be given by,

G(left) =1/6 ∗ (1−1/6) + 5/6 ∗ (1−5/6) = 0.278

The right branch has all blues and hence as calculated above its Gini Impurity is given by,

G(right) =1 ∗ (1−1) + 0 ∗ (1−0) = 0

Now that we have the Gini Impurities of the imperfect split, in order to evaluate the quality or extent of the split, we will give a specific weight to the impurity of each branch with the number of elements it has.

(0.6∗0.278) + (0.4∗0) = 0.167

Now that we have calculated the Gini Index, we shall calculate the value of another parameter, Gini Gain and analyse its application in Decision Trees. The amount of impurity removed with this split is calculated by deducting the above value with the Gini Index for the entire dataset (0.5)

0.5 – 0.167 = 0.333

This value calculated is called as the “Gini Gain”. In simple terms, Higher Gini Gain = Better Split. 

Hence, in a Decision Tree algorithm, the best split is obtained by maximizing the Gini Gain, which is calculated in the above manner with each iteration. 

After calculating the Gini Gain for each attribute in the data set, the class, sklearn.tree.DecisionTreeClassifier will choose the largest Gini Gain as the Root Node. When a branch with Gini of 0 is encountered it becomes the leaf node and the other branches with Gini more than 0 need further splitting. These nodes are grown recursively till all of them are classified.

Also Read: Decision Tree in AI: Introduction, Types & Creation

Relevance of Entropy

Entropy, a key concept in decision trees, measures the uncertainty or randomness within a dataset. It specifically quantifies the degree to which a subset of data contains examples belonging to different classes, playing a crucial role in the decision-making process of the tree. By choosing features that minimize entropy within splits, we lead to purer branches and, ultimately, construct a more accurate decision tree.

While both the Gini Index and entropy are utilized in decision trees to assess data purity, they calculate the difference in impurity slightly differently. The Gini Index, like entropy, serves as a metric to evaluate the likelihood of a specific feature being misclassified when selected randomly. However, entropy in the decision tree gives a more detailed measure of the disorder or variability of the system, offering a slightly different perspective on data purity and impurity reduction strategies.

• Gini Index: Compares the proportion of each class within a data subset before and after the split, favoring features that maximize the difference. 
• Entropy: Compares the overall uncertainty of the original data to the combined uncertainty of the resulting subsets, preferring features that lead to the largest decrease in overall entropy. 

Both Gini Index and entropy have their advantages and disadvantages, and the choice depends on the specific data and task. Generally, Gini Index works well for binary classification, while entropy might be better suited for multiple classes. 

Difference between Gini Index and Entropy

Gini Index vs Information Gain

Both Gini Index and Information Gain are measures of impurity used in decision trees to choose the best feature for splitting the data at each node. However, they calculate this difference in slightly different ways and have their own strengths and weaknesses. 

Gini Index: 

• Focuses on class proportions: Compares the proportion of each class within a data subset before and after the split, favoring features that maximize the difference. This makes it sensitive to class imbalance, potentially favoring splits that isolate minority classes even if they don’t significantly improve overall clarity. 
• Simple and computationally efficient: Easier to calculate compared to Information Gain, making it faster to build decision trees. 
• Works well for binary classification: Emphasizes maximizing the gap between classes, making it effective when dealing with two distinct outcomes. 

Information Gain: 

• Measures entropy change: Compares the total entropy of the original data to the combined entropy of the resulting subsets after the split, preferring features that lead to the largest decrease in overall uncertainty. This is more nuanced and can handle multiple classes effectively. 
• Less sensitive to class imbalance: Doesn’t solely focus on isolating minority classes but accounts for overall reduction in uncertainty even if the split proportions are uneven. 
• More computationally expensive: Calculating entropy involves logarithms, making it slightly slower than Gini Index for tree construction. 
• Can be better for multi-class problems: Provides a more comprehensive picture of class distribution changes, potentially leading to better results with multiple outcomes. 

Here’s a table summarizing the key differences: 

Use in Machine Learning

There are various algorithms designed for different purposes in the world of machine learning. The problem lies in identifying which algorithm to suit best on a given dataset. The decision tree algorithm seems to show convincing results too. To recognize it, one must think that decision trees somewhat mimic human subjective power.

So, a problem with more human cognitive questioning is likely to be more suited for decision trees. The underlying concept of decision trees can be easily understandable for its tree-like structure. 

Conclusion

An alternative to the Decision tree for Gini Index is the Information Entropy which used to determine which attribute gives us the maximum information about a class. It is based on the concept of entropy, which is the degree of impurity or uncertainty. It aims to decrease the level of entropy from the root nodes to the leaf nodes of the decision tree. 

In this way, the Gini Index is used by the CART algorithms to optimise the decision trees and create decision points for classification trees. 

If you’re interested to learn more about machine learning, check out IIIT-B & upGrad’s PG Diploma in Machine Learning & AI which is designed for working professionals and offers 450+ hours of rigorous training, 30+ case studies & assignments, IIIT-B Alumni status, 5+ practical hands-on capstone projects & job assistance with top firms.