Building a Decision Tree from Scratch in C++

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.

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.

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.

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.