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 Python 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,
• $p_i$ is the proportion of individuals in the $i$-th group, and the sum is taken over $n$ groups.

If we are successful in segregating the socks into two distinct piles, one with all red socks and the other with all blue socks, our groups are perfectly ordered, and our Gini Index is 0. However, in a case where red and blue socks are randomly mixed together, we have more disorder, resulting in a higher Gini Index.

Let's take a Pythonic approach to this.

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

groups = [
    [['Red'], ['Blue'], ['Red']],
    [['Blue'], ['Red'], ['Blue'], ['Blue']],
]
classes = ['Red', 'Blue']

In Python, 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:

n_instances = float(sum([len(group) for group in groups]))

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

for group in groups:
    size = len(group)
    score = 0.0
    for class_val in classes:
        p = [row[-1] for row in group].count(class_val) / size
        score += p * p

In the end, we adjust each group's score in relation to its size compared to the total number of socks. The final Gini Index is the accumulation of these weighted group scores.

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