K-Fold Split (Indices Only)

Data Processing

Hard

Problem

Theory

K-Fold Cross-Validation is a resampling technique used to evaluate machine learning models on limited data. Instead of using a single train-test split, the data is divided into k equal parts (folds), and the model is trained and evaluated k times, each time using a different fold as the test set and the remaining folds as training data.

Why Use K-Fold Cross-Validation?

Better use of data: In a single train-test split, a portion of data is never used for training. K-Fold uses all data for both training and testing across different iterations.

More reliable estimates: A single split can be lucky or unlucky depending on which samples end up in test set. K-Fold averages over multiple splits for more stable performance estimates.

Detecting overfitting: If training scores are high but cross-validation scores are low, the model is overfitting.

Model selection: Compare different models or hyperparameters using cross-validation scores rather than a single test set.

The K-Fold Procedure

Given a dataset with N samples and chosen k value:

Step 1 - Partition data into k folds:

\text{fold\_size} = \lfloor N / k \rfloor

Each fold contains approximately N/k samples. If N is not divisible by k, some folds will have one extra sample.

Step 2 - Iterate k times:

• In iteration i, fold i becomes the validation set
• The remaining k-1 folds form the training set
• Train the model on training set, evaluate on validation set
• Record the performance metric

Step 3 - Aggregate results:

\text{CV\_score} = \frac{1}{k} \sum_{i=1}^{k} \text{score}_i

The final cross-validation score is the average across all folds.

Choosing the Number of Folds

Common choices:

• k=5: Good balance between bias and variance, computationally reasonable
• k=10: Standard choice, slightly lower bias than k=5
• k=N (Leave-One-Out): Each sample is a fold, lowest bias but highest variance and computational cost

Trade-offs:

Small k (e.g., k=2 or k=3):

• Fewer training samples per iteration (higher bias)
• Faster to compute
• Higher variance in estimates

Large k (e.g., k=10 or k=20):

• More training samples per iteration (lower bias)
• More computation required
• Training sets overlap more, which can increase variance

Worked Example

Dataset: 10 samples with indices [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

k=5 folds (fold_size = 10/5 = 2):

Fold 0: samples [0, 1] Fold 1: samples [2, 3] Fold 2: samples [4, 5] Fold 3: samples [6, 7] Fold 4: samples [8, 9]

Iteration 1:

• Validation: Fold 0 → [0, 1]
• Training: Folds 1,2,3,4 → [2, 3, 4, 5, 6, 7, 8, 9]
• Score: 0.85

Iteration 2:

• Validation: Fold 1 → [2, 3]
• Training: Folds 0,2,3,4 → [0, 1, 4, 5, 6, 7, 8, 9]
• Score: 0.82

Iteration 3:

• Validation: Fold 2 → [4, 5]
• Training: Folds 0,1,3,4 → [0, 1, 2, 3, 6, 7, 8, 9]
• Score: 0.88

Iteration 4:

• Validation: Fold 3 → [6, 7]
• Training: Folds 0,1,2,4 → [0, 1, 2, 3, 4, 5, 8, 9]
• Score: 0.79

Iteration 5:

• Validation: Fold 4 → [8, 9]
• Training: Folds 0,1,2,3 → [0, 1, 2, 3, 4, 5, 6, 7]
• Score: 0.86

Final CV Score:

\text{CV\_score} = \frac{0.85 + 0.82 + 0.88 + 0.79 + 0.86}{5} = 0.84

Standard deviation of fold scores provides uncertainty estimate: std = 0.034

Handling Uneven Splits

When N is not divisible by k, the remainder samples must be distributed:

Example: N=23 samples, k=5

\text{base\_size} = \lfloor 23/5 \rfloor = 4

\text{remainder} = 23 \mod 5 = 3

Distribution: First 3 folds get 5 samples, last 2 folds get 4 samples

• Fold 0: 5 samples
• Fold 1: 5 samples
• Fold 2: 5 samples
• Fold 3: 4 samples
• Fold 4: 4 samples

Total: 5 + 5 + 5 + 4 + 4 = 23 samples

Shuffling Before Splitting

Why shuffle? If data is ordered (e.g., sorted by class label or time), consecutive samples may be similar. Without shuffling, folds might contain biased subsets.

Implementation consideration: Shuffle indices before assigning to folds, not the data itself. This preserves original data order while ensuring random fold assignment.

Reproducibility: Set a random seed before shuffling to ensure the same fold assignments across runs.

Important Considerations

Data leakage: Any preprocessing that uses information from the full dataset (e.g., scaling, feature selection) must be performed inside each fold to avoid leakage. The test fold should never influence training.

Computational cost: Training k models takes k times longer than a single train-test split. For expensive models, k=5 may be preferred over k=10.

Variance of estimates: Report both mean CV score and standard deviation across folds. High variance suggests the model is sensitive to the specific training data.

Nested cross-validation: When tuning hyperparameters, use an inner CV loop for hyperparameter selection and outer CV loop for unbiased performance estimation.

Leave-One-Out Cross-Validation (LOOCV)

Special case where k=N:

• Each sample is its own validation set
• Training on N-1 samples, testing on 1 sample
• Repeat N times

Advantages:

• Maximum use of training data
• Deterministic (no random splitting)

Disadvantages:

• Computationally expensive for large N
• High variance in error estimates
• Training sets are nearly identical (high correlation)

Where K-Fold Cross-Validation Shows Up

• Model Evaluation: Comparing different algorithms (Random Forest vs SVM vs Neural Network) fairly

• Hyperparameter Tuning: Grid search or random search uses CV to evaluate each hyperparameter configuration

• Feature Selection: Evaluating which features improve or hurt model performance

• Ensemble Methods: Some ensemble techniques use CV-style splits to generate diverse base models

• Medical Research: Limited patient data requires efficient use through cross-validation

• Kaggle Competitions: Cross-validation scores often correlate better with leaderboard scores than single splits

• Time Series: Modified versions (TimeSeriesSplit) respect temporal ordering

• Class Imbalance: Stratified K-Fold ensures class proportions are maintained in each fold

Examples

Hints

1. Use np.array_split(indices, k) to create balanced validation folds.
2. Concatenate every fold except the current validation fold for train_idx.

Requirements

• Place every index in exactly one validation fold
• Keep validation fold sizes within one element of each other
• Use the supplied seed when shuffling
• Return a list of dictionaries containing train_idx and val_idx arrays

Constraints

• 2 <= k <= N
• seed is a nonnegative integer
• Use NumPy only

Starter Code

import numpy as np

def kfold_split(N: int, k: int, shuffle: bool = True, seed: int = 0) -> list:
    """
    Returns a list of dictionaries with train_idx and val_idx.
    """
    # Write code here
    pass

Test Cases