Understanding and Implementing Decision Tree Splits

Welcome to another exciting lesson! Today, we will unlock the mechanism behind the key operation of the Decision Tree algorithm: splitting. We will start with a glance at the structure of Decision Trees, understand the mechanics of splitting, and then dive into the application of the Gini Index, a measure of the quality of a split. Inspired by these insights, we will finish by creating a split function using C++ and running it on a sample dataset. So, let's roll up our sleeves and dig into the world of Decision Trees!

A Decision Tree is a tree-like graph that models decisions and their potential consequences. It starts at a single node, called the root, which splits into branches. Each branch, in turn, splits into more branches, forming a hierarchical network. The final branches with no further splits are referred to as leaf nodes. Each split is determined by whether the data satisfies a specific condition.

For instance, if we build a Decision Tree to predict whether a patient will recover from a disease, the root could be temperature> 101F. The tree would then split into two branches - one for yes and another for no. Each branch could further split based on another attribute, such as cough present. This process of splitting continues until we conclude the leaf nodes, such as recovery probable or recovery doubtful. Isn't this a straightforward and intuitive way to make complex decisions?

Let's better understand the Gini Index concept using a tangible example. Imagine we have a basket full of socks of different colors, say red and blue. The goal of a Decision Tree in this context would be to split these socks into separate baskets (or groups) based on their colors. This process is essentially what the Gini Index endeavors to quantify -- the disorder within these groups. A greater Gini Index score signifies more disorder.

The formula is the following: $G = 1 - \sum_{i=1}^{n} p_i^2$

Where:

• $G$ is the Gini index or Gini coefficient for a single group,
• $p_i$ is the proportion of individuals in the $i$-th class within that group, and the sum is taken over $n$ classes.

The Gini score is first calculated for each group individually. If we are successful in segregating the socks into two distinct piles, one with all red socks and the other with all blue socks, each group is perfectly ordered, and the Gini Index for each group is 0. However, in a case where red and blue socks are randomly mixed together, the group has more disorder, resulting in a higher Gini Index for that group.

When we have multiple groups (for example, after a split), we combine their Gini scores into an overall Gini Index for the split. This is done by weighting each group's Gini score by the proportion of items it contains relative to the total number of items. The overall Gini Index for the split is the sum of these weighted scores.

Let's take a C++ approach to this.

First, assume that we have the following sample data of socks:

vector<vector<vector<string>>> groups = {
    {{"Red"}, {"Blue"}, {"Red"}},
    {{"Blue"}, {"Red"}, {"Blue"}, {"Blue"}}
};
vector<string> classes = {"Red", "Blue"};

In C++, to calculate our Gini Index, we'll need to tackle several things. The first step is to count the total number of instances or socks:

double n_instances = 0.0;
for (const auto& group : groups) {
    n_instances += group.size();
}

Next, we look at each group (a basket filled with socks of a specific color) and calculate their Gini score based on the number of each type of sock (class values). The more mixed the colors in a group, the higher the score.

for (const auto& group : groups) {
    double size = group.size();
    double score = 0.0;
    for (const string& class_val : classes) {
        int count = 0;
        for (const auto& row : group) {
            if (row.back() == class_val) count++;
        }
        double p = count / size;
        score += p * p;
    }
    // The Gini score for this group is (1.0 - score)
}

To get the overall Gini Index for the split, we weight each group's Gini score by the size of the group relative to the total number of socks, and sum these weighted scores:

gini += (1.0 - score) * (size / n_instances);

This way, larger groups have a bigger impact on the overall Gini Index, reflecting their importance in the split.