Understanding and Implementing Decision Tree Splits

Introduction

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!

Structuring a Decision Tree

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?

Understanding the Gini Index With An Example

G = 1 - \sum_{i=1}^{n} p_i^2

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Integrating Gini Index and Split Function

Lastly, we merge gini_index and test_split to create the get_split function. This function scans through all the attributes of our socks and finds the best attribute to split them by – which attribute makes the most distinct piles of socks.

C++

struct SplitResult {
    int index;
    double value;
    double score;
    vector<vector<vector<string>>> groups;
};

SplitResult get_split(const vector<vector<string>>& dataset) {
    vector<string> class_values;
    for (const auto& row : dataset) {
        if (find(class_values.begin(), class_values.end(), row.back()) == class_values.end()) {
            class_values.push_back(row.back());
        }
    }

    int b_index = -1;
    double b_value = 0.0;
    double b_score = std::numeric_limits<double>::max();
    vector<vector<vector<string>>> b_groups;

    for (int index = 0; index < dataset[0].size() - 1; ++index) {
        for (const auto& row : dataset) {
            auto groups_pair = test_split(index, stod(row[index]), dataset);
            vector<vector<vector<string>>> groups = {groups_pair.first, groups_pair.second};
            double gini = gini_index(groups, class_values);
            if (gini < b_score) {
                b_index = index;
                b_value = stod(row[index]);
                b_score = gini;
                b_groups = groups;
            }
        }
    }

    return {b_index, b_value, b_score, b_groups};
}

struct SplitResult {
    int index;
    double value;
    double score;
    vector<vector<vector<string>>> groups;
};

SplitResult get_split(const vector<vector<string>>& dataset) {
    vector<string> class_values;
    for (const auto& row : dataset) {
        if (find(class_values.begin(), class_values.end(), row.back()) == class_values.end()) {
            class_values.push_back(row.back());
        }
    }

    int b_index = -1;
    double b_value = 0.0;
    double b_score = std::numeric_limits<double>::max();
    vector<vector<vector<string>>> b_groups;

    for (int index = 0; index < dataset[0].size() - 1; ++index) {
        for (const auto& row : dataset) {
            auto groups_pair = test_split(index, stod(row[index]), dataset);
            vector<vector<vector<string>>> groups = {groups_pair.first, groups_pair.second};
            double gini = gini_index(groups, class_values);
            if (gini < b_score) {
                b_index = index;
                b_value = stod(row[index]);
                b_score = gini;
                b_groups = groups;
            }
        }
    }

    return {b_index, b_value, b_score, b_groups};
}

The code keeps track of the best split column, best split value, a score of the best split, and groups of the best split using variables b_index, b_value, b_score, and b_groups, respectively.

Introduction

Structuring a Decision Tree

Understanding the Gini Index With An Example

Join the 1M+ learners on CodeSignal

Defining Function for Future Use

Implementing Decision Tree Split

Integrating Gini Index and Split Function

Testing Split Function

Lesson Summary and Practice