Random Forests in C++

Welcome to our exploration of ensemble machine learning with the Random Forest algorithm — this time, using C++. Random Forests are a powerful extension of decision trees, where multiple trees are combined to form a "forest" that makes more robust predictions. In this lesson, you'll learn the core ideas behind Random Forests and how to implement a basic version in C++. We'll focus on how to construct and aggregate decision trees and how to introduce randomness to make the ensemble effective.

A Random Forest is an ensemble machine learning method that builds many decision trees to solve classification or regression problems. Each tree in the forest makes its own prediction, and the final output is determined by a majority vote among all the trees. This approach helps reduce overfitting and increases the model's accuracy.

Key parameters in a Random Forest include:

• n_trees: The number of trees in the forest. More trees generally improve performance but require more computation.
• max_depth: The maximum depth of each tree, controlling how complex each tree can become.

A decision tree is the basic building block of a Random Forest. Each tree is structured as a series of decision points (branches) leading to outcomes (leaves). The strength of a Random Forest comes from the diversity among its trees. This diversity is achieved by training each tree on a different random subset of the data and by introducing randomness in the way features are selected for splitting at each node.

To implement a Random Forest in C++, we will use the mlpack library, which provides efficient machine learning algorithms, including decision trees. We'll also use standard C++ libraries for data handling and random number generation.

Below is a basic implementation of a Random Forest classifier in C++. The class manages a collection of decision trees, handles bootstrapping (random sampling with replacement), and aggregates predictions by majority vote.

Let's start by defining the class and the fit method:

#include <mlpack/core.hpp>
#include <mlpack/methods/decision_tree/decision_tree.hpp>
#include <vector>
#include <random>
#include <map>
#include <iostream>

using namespace mlpack;
using namespace mlpack::tree;
using namespace arma;

class RandomForest {
public:
    RandomForest(size_t n_trees = 100, size_t max_depth = 0)
        : n_trees(n_trees), max_depth(max_depth) {}

    void fit(const mat& X, const Row<size_t>& y) {
        trees.clear();
        std::mt19937 rng(42); // Fixed seed for reproducibility
        for (size_t i = 0; i < n_trees; ++i) {
            mat Xb;
            Row<size_t> yb;
            bootstrap(X, y, Xb, yb, rng);

            DecisionTree<> tree;
            tree.Train(Xb, yb, arma::max(y) + 1, 10, .0, max_depth);
            trees.push_back(std::move(tree));
        }
    }

Let's look at the tree.Train method, which takes several parameters:

• The third parameter, arma::max(y) + 1, specifies the number of classes.
• The fourth parameter, 10, is the minimum leaf size — the minimum number of samples required to form a leaf node.
• The fifth parameter, .0, is the minimum information gain — the minimum gain required to split a node.
• The last parameter, max_depth, sets the maximum depth of the tree.

These parameters control the complexity and stopping criteria for each decision tree in the forest.

Now, let's add the predict method and the private members, including the bootstrapping function:

    Row<size_t> predict(const mat& X) const {
        std::vector<Row<size_t>> all_preds;
        for (const auto& tree : trees) {
            Row<size_t> preds;
            tree.Classify(X, preds);
            all_preds.push_back(std::move(preds));
        }

        Row<size_t> final_preds(X.n_cols);
        for (size_t i = 0; i < X.n_cols; ++i) {
            std::map<size_t, size_t> counts;
            for (const auto& preds : all_preds) {
                counts[preds[i]]++;
            }
            size_t best_class = 0, best_count = 0;
            for (const auto& p : counts) {
                if (p.second > best_count || (p.second == best_count && p.first < best_class)) {
                    best_count = p.second;
                    best_class = p.first;
                }
            }
            final_preds[i] = best_class;
        }
        return final_preds;
    }

private:
    size_t n_trees;
    size_t max_depth;
    std::vector<DecisionTree<>> trees;

    void bootstrap(const mat& X, const Row<size_t>& y, mat& Xb, Row<size_t>& yb, std::mt19937& rng) {
        size_t n_samples = X.n_cols;
        Xb.set_size(X.n_rows, n_samples);
        yb.set_size(n_samples);
        std::uniform_int_distribution<size_t> dist(0, n_samples - 1);
        for (size_t i = 0; i < n_samples; ++i) {
            size_t idx = dist(rng);
            Xb.col(i) = X.col(idx);
            yb[i] = y[idx];
        }
    }
};

Bootstrapping is a statistical technique where we create new datasets by sampling from the original data with replacement. In the context of Random Forests, each tree is trained on a different bootstrapped dataset, which introduces randomness and ensures that the trees are diverse.

In C++, we can implement bootstrapping using vectors or Armadillo matrices, along with the <random> library for generating random indices. Here is how the bootstrapping function works in our RandomForest class:

void bootstrap(const mat& X, const Row<size_t>& y, mat& Xb, Row<size_t>& yb, std::mt19937& rng) {
    size_t n_samples = X.n_cols;
    Xb.set_size(X.n_rows, n_samples);
    yb.set_size(n_samples);
    std::uniform_int_distribution<size_t> dist(0, n_samples - 1);
    for (size_t i = 0; i < n_samples; ++i) {
        size_t idx = dist(rng);
        Xb.col(i) = X.col(idx);
        yb[i] = y[idx];
    }
}

This function creates a new dataset (Xb, yb) by randomly selecting columns (samples) from the original data, with replacement.

Let's see how to use our Random Forest implementation in practice. We'll use the Iris dataset, a classic dataset for classification tasks. In C++, we can load the data, split it into training and testing sets, train the Random Forest, and evaluate its accuracy.

#include <mlpack/core.hpp>
#include <mlpack/core/data/split_data.hpp>
#include <armadillo>
#include <iostream>

using namespace mlpack;
using namespace mlpack::data;
using namespace arma;

int main() {
    // Load the Iris dataset (assumed to be in CSV format, last row as labels)
    mat dataset;
    data::Load("iris.csv", dataset, true);

    // Split the dataset into features and labels
    mat X = dataset.submat(0, 0, dataset.n_rows - 2, dataset.n_cols - 1);
    Row<size_t> y = conv_to<Row<size_t>>::from(dataset.row(dataset.n_rows - 1));

    // Split into train and test sets (80% train, 20% test)
    mat X_train, X_test;
    Row<size_t> y_train, y_test;
    data::Split(X, y, X_train, X_test, y_train, y_test, 0.2, true);

    // Initialize and fit the RandomForest classifier
    RandomForest rf(100, 2);
    rf.fit(X_train, y_train);

    // Predict and evaluate the accuracy
    Row<size_t> y_pred = rf.predict(X_test);
    size_t correct = arma::accu(y_pred == y_test);
    double accuracy = (double)correct / y_test.n_elem;

    std::cout << "Accuracy: " << accuracy << std::endl;
    return 0;
}

In this example:

• The Iris dataset is loaded from a CSV file.
• Features and labels are separated.
• The data is split into training and testing sets.
• The Random Forest is trained on the training data.
• Predictions are made on the test data, and the accuracy is calculated and printed.

Congratulations! You've learned how Random Forests work, how to build them from decision trees, and how to implement a basic Random Forest classifier in C++. You now understand the importance of randomness and bootstrapping in creating a strong ensemble. To solidify your understanding, try experimenting with different numbers of trees, tree depths, or even different datasets. Practice is key to mastering these concepts — happy coding in C++!