Building a Decision Tree from Scratch in C++

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: C++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: C++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.

Join the 1M+ learners on CodeSignal

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

Implementing the Recursive Split

The recurse_split function is responsible for creating children nodes:

C++

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);
    }
}

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:

C++

// 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]
*/

// 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.