Introduction

Greetings! In this session on Decision Trees, we aim to implement a full Decision Tree from scratch in C++. Decision Trees are a type of Supervised Machine Learning in which data is continuously split according to certain parameters.

Refreshing the Structure of Decision Tree

A Decision Tree has a tree-like structure with each internal node denoting a test on an attribute, each branch representing an outcome of the test, and each terminal node (leaf) holding a class label. Here are the parts of a Decision Tree:

  • Root Node: This houses the entire dataset.
  • Internal Nodes: These make decisions based on conditions.
  • Edges/branches: These connections implement decision rules.
  • Leaves: These are terminal nodes for making predictions.

Decisions on attributes depend on how well they help to purify the data.

The tree-building process begins with the full dataset at the root node, iteratively partitioning the data based on chosen attributes. Each child node becomes a new root that can be split further. This recursive process continues until predefined stopping criteria are met.

Stopping Criteria for Tree Building

Standard stopping criteria include:

  • Maximum Tree Depth: Limiting the maximum depth of the tree.
  • Minimum Node Records: No more partitioning if less than a threshold number of records.
  • Node Purity: Stop if all instances at a node belong to the same class.

These criteria ensure the model is consistent, which prevents overfitting.

Implementing Decision Tree Building in C++

Now, we'll use C++ to build the decision tree. We'll rely on the existing get_split function from the previous lesson to find the optimal split for our data.

Here is how a terminal node is created:

string create_terminal(const vector<vector<string>>& group) {
    map<string, int> outcomes;
    for (const auto& row : group) {
        outcomes[row.back()]++;
    }

    string majority_class;
    int max_count = 0;
    for (const auto& pair : outcomes) {
        if (pair.second > max_count) {
            max_count = pair.second;
            majority_class = pair.first;
        }
    }
    return majority_class;
}

The create_terminal function determines the most common class value in a group of rows and assigns that value as the final decision for that subset of data.

Let's proceed to the actual tree building:

struct TreeNode {
    int index;
    double value;
    vector<vector<vector<string>>> groups;
    TreeNode* left;
    TreeNode* right;

    TreeNode() : index(-1), value(0.0), left(nullptr), right(nullptr) {}
};

TreeNode* build_tree(const vector<vector<string>>& train, int max_depth, int min_size) {
    TreeNode* root = get_split(train);
    recurse_split(root, max_depth, min_size, 1);
    return root;
}

This function begins the tree-building process.

Implementing the Recursive Split

The recurse_split function is responsible for creating children nodes:

void recurse_split(TreeNode* node, int max_depth, int min_size, int depth) {
    // Split into left and right groups
    auto left = node->groups[0];
    auto right = node->groups[1];
    node->groups.clear();

    // If left or right groups are empty, create a terminal node
    if (left.empty() || right.empty()) {
        vector<vector<string>> combined;
        combined.insert(combined.end(), left.begin(), left.end());
        combined.insert(combined.end(), right.begin(), right.end());
        string terminal_value = create_terminal(combined);
        node->left = new TreeNode();
        node->right = new TreeNode();
        node->left->value = stod(terminal_value);
        node->right->value = stod(terminal_value);
        return;
    }

    // Check for max depth
    if (depth >= max_depth) {
        node->left = new TreeNode();
        node->right = new TreeNode();
        node->left->value = stod(create_terminal(left));
        node->right->value = stod(create_terminal(right));
        return;
    }

    // Process the children nodes
    if (left.size() <= min_size) {
        node->left = new TreeNode();
        node->left->value = stod(create_terminal(left));
    } else {
        node->left = get_split(left);
        recurse_split(node->left, max_depth, min_size, depth+1);
    }

    if (right.size() <= min_size) {
        node->right = new TreeNode();
        node->right->value = stod(create_terminal(right));
    } else {
        node->right = get_split(right);
        recurse_split(node->right, max_depth, min_size, depth+1);
    }
}
Building and Printing a Tree

We can then build and print the decision tree based on the dataset and chosen parameters:

// Sample dataset
vector<vector<string>> dataset = {
    {"5", "3", "0"}, {"6", "3", "0"}, {"6", "4", "0"}, {"10", "3", "1"},
    {"11", "4", "1"}, {"12", "8", "0"}, {"5", "5", "0"}, {"12", "4", "1"}
};

int max_depth = 2;
int min_size = 1;
TreeNode* tree = build_tree(dataset, max_depth, min_size);

// Print the tree
void print_tree(TreeNode* node, int depth = 0) {
    if (node->left != nullptr && node->right != nullptr) {
        string indent(depth * 2, ' ');
        cout << indent << "[X" << (node->index + 1) << " < " << fixed << setprecision(3) << node->value << "]" << endl;
        print_tree(node->left, depth + 1);
        print_tree(node->right, depth + 1);
    } else {
        string indent(depth * 2, ' ');
        cout << indent << "[" << node->value << "]" << endl;
    }
}

print_tree(tree);
/*Output:
[X1 < 10.000]
  [X1 < 5.000]
    [0]
    [0]
  [X2 < 8.000]
    [1]
    [0]
*/

The print_tree output shows a decision tree. [X1 < 10.000] checks if feature X1 is less than 10.000. Left branch ([X1 < 5.000]) and its subsequent nodes ([0] and [0]) indicate the conditions and predictions if 'Yes'. The right branch ([X2 < 8.000]) and its nodes ([1] and [0]) cover the cases for 'No'. Indentations imply tree depth.

Lesson Summary

Congratulations! You've now built a decision tree from scratch in C++. Proceed to the practice to reinforce your understanding. Keep progressing and keep implementing! Happy tree building!

Previous
Sign up
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal