Bagging with Decision Trees

Welcome to our exploration of Implementing Bagging. This lesson expands your machine learning toolkit by introducing the bagging technique and illustrating its use with decision trees. You will also gain hands-on experience with these concepts through a C++ implementation. Let's embark on our bagging adventure using C++!

Bagging, or bootstrap aggregating, is a technique in ensemble learning that aims to reduce the variance of a machine learning model. The essence of bagging involves generating multiple subsets from the original dataset and then using these subsets to train separate models. The subsets are chosen with replacement, so it is possible to have duplicate data points in a single subset. The final prediction is made by aggregating the predictions from these individual models. Essentially, it is a vote for the best answer: the final class prediction is the class that was predicted by the majority of votes.

We will use decision trees as our base models. Decision trees can handle both categorical and continuous input variables, and they follow sequential, hierarchical decision rules to output a final decision.

A decision tree is a supervised learning algorithm used for both classification and regression tasks. It works by recursively splitting the dataset into subsets based on feature values, forming a tree-like structure of decisions. At each node, the algorithm selects the feature and threshold that best separates the data according to a chosen criterion (such as Gini impurity or information gain). The process continues until the data in a node is sufficiently pure or another stopping condition is met. The final predictions are made at the leaf nodes, which represent the output class (for classification) or value (for regression).

Decision trees are popular because they are easy to interpret and can handle both numerical and categorical data. However, they have a major drawback: high variance. This means that small changes in the training data can lead to very different tree structures and predictions. As a result, a single decision tree may overfit the training data and perform poorly on unseen data.

Bagging addresses this weakness by training multiple decision trees on different bootstrapped samples of the data and aggregating their predictions. This ensemble approach reduces the variance of the model, leading to improved accuracy and more robust predictions compared to a single decision tree.

• n_trees: This is the number of decision trees in the ensemble. Increasing n_trees generally improves performance up to a point, as more trees provide a better average and reduce variance, but it also increases computational cost.
• min_leaf_size: This parameter sets the minimum number of samples required to form a leaf node. A smaller min_leaf_size allows the tree to grow deeper and capture more detail, but may lead to overfitting. A larger value makes the tree more conservative and can help prevent overfitting.
• max_depth: This limits how deep the tree can grow. Restricting max_depth can prevent the tree from modeling noise in the data, thus reducing overfitting, but if set too low, it may underfit and miss important patterns.

Tuning these hyperparameters allows you to control the complexity of each decision tree and the overall ensemble, balancing bias and variance for optimal performance.

Before we load our dataset, let's clarify the format of the data we are using. In our example, the iris dataset is stored in a CSV file where each column represents a data point. The first four rows contain the features (sepal length, sepal width, petal length, petal width), and the last row contains the labels (species encoded as integers). For example, the first few columns of the CSV might look like this:

5.1,4.9,4.7,4.6,5.0,...
3.5,3.0,3.2,3.1,3.6,...
1.4,1.4,1.3,1.5,1.4,...
0.2,0.2,0.2,0.2,0.2,...
0,0,0,0,0,...

• Rows 0-3: Features (float values)
• Row 4: Labels (integer values: 0, 1, or 2)

This is different from some CSV formats where each row is a data point and the label is in the last column. Here, each column is a data point, and the label is in the last row.

Now, let's proceed to load the data in C++. For our C++ implementation, we will use the mlpack library, which provides efficient machine learning algorithms and utilities. We will also use the Armadillo library for matrix operations, which is included with mlpack.

First, we load our dataset. For this lesson, we use the well-known iris dataset, which we split into training and test data. The iris dataset contains measurements of 150 iris flowers from three different species: setosa, versicolor, and virginica. The measurements include the lengths and widths of the sepals and petals of the flowers.

The variable n_trees, set here as 100, determines the number of decision tree classifiers we plan to build.

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

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

int main() {
    // Load the data
    std::mt19937 rng(42); // Random number generator for reproducibility
    mat X;
    Row<size_t> y;
    data::Load("iris.csv", X, true); // Load the iris dataset from a CSV file
    y = conv_to<Row<size_t>>::from(X.row(X.n_rows - 1)); // Last row is the label
    X.shed_row(X.n_rows - 1); // Remove label row from features

    // Split the data into train and test sets
    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); // 20% test set

    // Parameters
    int n_trees = 100;
    std::vector<DecisionTree<>> tree_models;
    // ... (rest of the code follows)
}

Next, we define our helper functions, bootstrapping and predict, which are pivotal to constructing our bagging model.

The bootstrapping function generates bootstrapped datasets by randomly sampling with replacement from the training data.

// Helper function for bootstrapping
std::pair<mat, Row<size_t>> bootstrapping(const mat& X, const Row<size_t>& y, std::mt19937& rng) {
    size_t n_samples = X.n_cols;
    std::uniform_int_distribution<size_t> dist(0, n_samples - 1);
    mat X_sample(X.n_rows, n_samples);
    Row<size_t> y_sample(n_samples);

    for (size_t i = 0; i < n_samples; ++i) {
        size_t idx = dist(rng);
        X_sample.col(i) = X.col(idx);
        y_sample(i) = y(idx);
    }

    return {X_sample, y_sample};
}

The mode function finds the most frequent value in a column, which is used for majority voting.

// Helper function to compute the mode (most frequent value)
size_t mode(const arma::Col<size_t>& col)
{
    std::unordered_map<size_t, size_t> freq;
    size_t max_count = 0;
    for (size_t i = 0; i < col.n_elem; ++i)
    {
        size_t val = col(i);
        size_t count = ++freq[val];
        if (count > max_count)
            max_count = count;
    }
    size_t min_val = std::numeric_limits<size_t>::max();
    for (const auto& kv : freq)
    {
        if (kv.second == max_count && kv.first < min_val)
            min_val = kv.first;
    }
    return min_val;
}

The predict function consolidates predictions from all trained models and returns the majority vote for each data point.

// Helper function for bagging prediction
Row<size_t> predict(const mat& X, const std::vector<DecisionTree<>>& trees) {
    arma::Mat<size_t> predictions(trees.size(), X.n_cols);

    for (size_t i = 0; i < trees.size(); ++i) {
        Row<size_t> pred;
        trees[i].Classify(X, pred);
        predictions.row(i) = pred;
    }

    Row<size_t> final_predictions(X.n_cols);
    for (size_t j = 0; j < X.n_cols; ++j) {
        final_predictions(j) = mode(predictions.col(j));
    }
    return final_predictions;
}

Now, we iteratively train decision trees on bootstrapped samples, make predictions, and store the models.

// Iteratively train decision trees on bootstrapped samples
for (int i = 0; i < n_trees; ++i) {
    auto [X_sample, y_sample] = bootstrapping(X_train, y_train, rng);
    DecisionTree<> tree(X_sample, y_sample, 3, 1, .0); // 3 classes, min leaf size 1, no minimum gain
    tree_models.push_back(tree);
}

// Predict on the test set
Row<size_t> y_pred = predict(X_test, tree_models);

After implementing a model, we must evaluate its performance. In our bagging model, the accuracy score serves as a performance metric: the ratio of correct predictions to the total number of predictions. In C++, we can calculate accuracy by comparing the predicted labels to the true labels and dividing the number of correct predictions by the total number of predictions.

// Calculate accuracy
size_t correct = arma::accu(y_pred == y_test);
double accuracy = static_cast<double>(correct) / y_test.n_elem;

std::cout << "Accuracy: " << accuracy << std::endl;

Congratulations! You've successfully navigated the basics of bagging with decision trees in C++. You've learned about the fundamentals of bagging, implemented a bagging algorithm using decision trees, and assessed the model's accuracy. Your understanding of these concepts will be further solidified through exercises in the next section. Have fun practicing!