From Scratch · C++ · Machine Learning · Data Preparation and Preprocessing

K-Fold Cross-Validation in C++

June 2026 · 13 min read

A single train/test split reports one number, and that number depends on which rows happened to land in the test set. On a small dataset the luck of the draw can move the score by several points. K-fold cross-validation removes most of that luck: it rotates the held-out fold so every row is used for validation exactly once, then averages.

The Idea

Split the data into $k$ equal folds. Train on $k-1$ of them and validate on the one left out; repeat $k$ times so each fold is the validation set once. The cross-validation estimate is the mean of the $k$ scores, and their spread tells you how stable it is:

$$\text{CV} = \frac{1}{k}\sum_{i=1}^{k} \text{acc}_i, \qquad \text{spread} = \operatorname{std}(\text{acc}_1, \dots, \text{acc}_k).$$

Every row contributes to validation exactly once and to training $k-1$ times, so the estimate uses all the data without ever testing a model on a row it trained on.

Assigning Folds

Shuffle the row indices once, then send row position $j$ to fold j % k. Fold by fold, those positions become the validation set and the rest become training, reusing the same index-list interface the decision tree already takes:

// the DecisionTree from the Decision Trees series is reused unchanged
int N = X.size(), folds = 5;
vector<int> perm(N);
iota(perm.begin(), perm.end(), 0);
shuffle(perm.begin(), perm.end(), rng);

vector<double> accs;
for (int fold = 0; fold < folds; ++fold) {
    vector<int> trainIdx, valIdx;
    for (int k = 0; k < N; ++k)                       // fold k validates, rest train
        (k % folds == fold ? valIdx : trainIdx).push_back(perm[k]);

    DecisionTree tree(6, 2, K);
    tree.fit(trainIdx, X, y);
    int ok = 0;
    for (int i : valIdx) ok += (tree.predict(X[i]) == y[i]);
    accs.push_back(100.0 * ok / valIdx.size());
}

Averaging the Folds

With the five fold accuracies in hand, the report is just their mean and standard deviation:

double mean = accumulate(accs.begin(), accs.end(), 0.0) / folds;
double var = 0;
for (double a : accs) var += (a - mean) * (a - mean);
double sd = sqrt(var / folds);

printf("%d-fold CV accuracy:", folds);
for (double a : accs) printf(" %.1f", a);
printf("\nmean = %.1f%%   std = %.1f%%\n", mean, sd);

Run on the three-blob dataset from Part 1:

5-fold CV accuracy: 95.8 95.8 95.8 91.7 97.2 mean = 95.3% std = 1.9%

The five per-fold accuracies scatter from 91.7% to 97.2% around the 95.3% mean. Reporting only one of them, as a single split would, could overstate or understate the model by up to two points.

The five folds range from $91.7\%$ to $97.2\%$. Any one of them, which is all a single split would have given, could be off the $95.3\%$ average by up to two points. The standard deviation of $1.9\%$ quantifies that wobble, and is itself a useful signal: a large spread means the score is sensitive to the partition and should be trusted less.

Cross-validation vs out-of-bag. K-fold trains $k$ separate models to score the data. The random forest gets a similar estimate for free: its out-of-bag error already validates each row on the trees that never saw it, no extra training required. Both answer the same question, how will this model do on unseen data, from opposite directions.