K-Fold Cross-Validation Indices - Model Evaluation

K-Fold Cross-Validation Indices

What you'll build

kfold_indices(n_samples, k): the train and validation index lists for each of the k folds of k-fold cross-validation, without shuffling.

Background

A single train/validation split gives a noisy estimate of model quality. K-fold cross-validation splits the indices into k contiguous folds; fold i is the validation set once while the other k - 1 folds train the model, and the k scores are averaged. Every sample is validated exactly once. This is scikit-learn's KFold(n_splits=k, shuffle=False).

Algorithm

1. Fold sizes: every fold gets n_samples // k samples, and the first n_samples % k folds get one extra.
2. Walk through 0 .. n_samples-1 in order: fold i takes the next size_i consecutive indices as its validation set.
3. The training set of fold i is every other index, in increasing order.

Inputs

• n_samples: int, n_samples >= k
• k: int number of folds, k >= 2

Expected return format

A list of k tuples (train_indices, val_indices), in fold order. Both are Python lists of ints in increasing order.

Edge cases and conventions

• Uneven folds: with n_samples = 7, k = 3 the sizes are 3, 2, 2 (the extra samples go to the first folds).
• k = n_samples is leave-one-out cross-validation.
• No shuffling: the folds are contiguous blocks. (Shuffle the data first, or use a seeded permutation, if its order carries information such as time or class.)

Constraints

• Plain Python or NumPy; no sklearn.

Follow-up

• Why is shuffled k-fold wrong for time series, and what do you use instead? (Forward-chaining splits such as TimeSeriesSplit.)
• How would you make the folds stratified by class?

Input: kfold_indices(6, 3)
Output: [([2, 3, 4, 5], [0, 1]), ([0, 1, 4, 5], [2, 3]), ([0, 1, 2, 3], [4, 5])]

Input: kfold_indices(7, 3)
Output: [([3, 4, 5, 6], [0, 1, 2]), ([0, 1, 2, 5, 6], [3, 4]), ([0, 1, 2, 3, 4], [5, 6])]

import numpy as np

def kfold_indices(n_samples: int, k: int) -> list:
    """
    Train/validation indices for k-fold cross-validation (no shuffling).

    Args:
        n_samples: Total number of samples (>= k)
        k: Number of folds

    Returns:
        List of k tuples (train_indices, val_indices), each a sorted list of ints;
        the first n_samples % k folds have one extra validation sample
    """
    # Your code here
    pass