Bird
Raised Fist0

Implement Cross-Validation - K-Fold, Stratified

CODINGintermediateInterview freq: high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Implement Cross-Validation - K-Fold, Stratified
Efficiently implement K-Fold and Stratified Cross-Validation from scratch.
codingintermediateFreq: highEvaluation Coding
Prerequisites:Cross-Validation - K-Fold, Stratified, Time Series
📝
Problem Statement

Implement K-Fold and Stratified Cross-Validation from scratch. Given a dataset and the number of folds, split the data into K subsets. For Stratified Cross-Validation, ensure each fold has the same class distribution as the entire dataset.

I/O Specification
Input:  data: np.ndarray, labels: np.ndarray, k: int
Output: List of tuples, each containing (train_indices, test_indices)
Example
Input: data = np.array([[1], [2], [3], [4], [5]]), labels = np.array([0, 1, 0, 1, 0]), k = 2 → Output: [([0, 2, 3], [1, 4]), ([1, 4], [0, 2, 3])]
🎯
Interview Angles
  • Testing understanding of stratification and its importance in model evaluation.
  • Evaluating ability to manipulate indices and arrays efficiently using NumPy.
  • Assessing knowledge of handling edge cases in data splitting.
  • Understanding of how to maintain class distribution across folds.
🔵
Naive Approach

The naive approach is to randomly shuffle the data and split it into K equal parts. For each part, use it as the test set and the rest as the training set. This does not ensure stratification.

Time: O(n log n) due to shuffling, Space: O(n) for storing indices
Why Insufficient
Does not ensure stratification, leading to potential class imbalance in folds.
🐍
Naive Code
Python
import numpy as np

def k_fold_naive(data, k):
    n = len(data)
    indices = np.arange(n)
    np.random.shuffle(indices)
    fold_sizes = np.full(k, n // k, dtype=int)
    fold_sizes[:n % k] += 1
    current = 0
    folds = []
    for fold_size in fold_sizes:
        start, stop = current, current + fold_size
        test_indices = indices[start:stop]
        train_indices = np.concatenate([indices[:start], indices[stop:]])
        folds.append((train_indices, test_indices))
        current = stop
    return folds

# Driver example
data = np.array([[1], [2], [3], [4], [5]])
labels = np.array([0, 1, 0, 1, 0])
k = 2
print(k_fold_naive(data, k))
💡
Key Insight
To ensure stratification, group data by class and split each class into K parts, then combine corresponding parts from each class to form stratified folds.
🐍
Optimized Code
Python
import numpy as np

def stratified_k_fold(data, labels, k):
    unique_classes, y_indices = np.unique(labels, return_inverse=True)
    class_counts = np.bincount(y_indices)
    class_indices = [np.where(y_indices == i)[0] for i in range(len(unique_classes))]
    folds = [[] for _ in range(k)]
    for class_idx in class_indices:
        np.random.shuffle(class_idx)
        fold_sizes = np.full(k, len(class_idx) // k, dtype=int)
        fold_sizes[:len(class_idx) % k] += 1
        current = 0
        for i in range(k):
            start, stop = current, current + fold_sizes[i]
            folds[i].extend(class_idx[start:stop])
            current = stop
    stratified_folds = []
    for i in range(k):
        test_indices = np.array(folds[i])
        train_indices = np.array([idx for j in range(k) if j != i for idx in folds[j]])
        stratified_folds.append((train_indices, test_indices))
    return stratified_folds

# Driver example
data = np.array([[1], [2], [3], [4], [5]])
labels = np.array([0, 1, 0, 1, 0])
k = 2
print(stratified_k_fold(data, labels, k))
🔍
Line-by-Line
unique_classes, y_indices = np.unique(labels, return_inverse=True)
Identify unique classes and map each label to its class index.
class_counts = np.bincount(y_indices)
Count occurrences of each class to determine how to split them.
class_indices = [np.where(y_indices == i)[0] for i in range(len(unique_classes))]
Gather indices for each class separately.
folds = [[] for _ in range(k)]
Initialize empty lists for each fold to store indices.
np.random.shuffle(class_idx)
Shuffle indices within each class to ensure random distribution.
fold_sizes = np.full(k, len(class_idx) // k, dtype=int)
Calculate fold sizes for the current class.
fold_sizes[:len(class_idx) % k] += 1
Distribute remainder indices evenly across the first few folds.
test_indices = np.array(folds[i])
Select the current fold as the test set.
train_indices = np.array([idx for j in range(k) if j != i for idx in folds[j]])
Combine all other folds to form the training set.
⚡
Complexity
Time: O(n log n) due to shuffling within each class, Space: O(n) for storing indices
Output
[([0, 2, 3], [1, 4]), ([1, 4], [0, 2, 3])]
🔲
Edge Cases
Single class
All folds will have the same class distribution, but may be empty if k > n.
class_counts = np.bincount(y_indices)
More folds than samples
Some folds will be empty.
fold_sizes[:len(class_idx) % k] += 1
⚠️
Common Mistakes
Not shuffling class indices before splitting.
Symptom: Leads to non-random distribution of samples across folds.
Incorrectly calculating fold sizes.
Symptom: Results in uneven distribution of samples, violating stratification.
Using Python loops instead of NumPy operations.
Symptom: Causes inefficient code that is slow for large datasets.
Not handling cases where k > n.
Symptom: Results in empty folds and potential index errors.

Practice

(1/5)
1. 
import numpy as np
from scipy.spatial import distance

X_train = np.array([[1, 2], [3, 4], [5, 6]])
X_test = np.array([[1, 2]])

# Calculate distances
D = distance.cdist(X_test, X_train, 'euclidean')

print(D)
What does the above code output?
easy
A. array([[0., 2.828, 5.656]])
B. array([[0., 2., 4.]])
C. array([[0., 2.236, 4.472]])
D. array([[0., 2.828, 4.472]])

Solution

  1. Step 1: Understand the function

    The cdist function computes the distance between each pair of the two collections of inputs.

  2. Step 2: Calculate the distances

    The Euclidean distance from [1, 2] to each point in X_train is calculated as [0., 2.828, 4.472].

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Euclidean distance formula: √((x2-x1)² + (y2-y1)²) [OK]
Hint: Euclidean distance formula: √((x2-x1)² + (y2-y1)²) [OK]
Common Mistakes:
2. 
import numpy as np
from sklearn.model_selection import train_test_split

X = np.array([1, 2, 3, 4, 5, 6])
y = np.array([0, 0, 1, 1, 0, 1])

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.5, stratify=y)
print(y_train)
easy
A. [0, 0, 1]
B. [0, 1, 0]
C. [1, 0, 1]
D. [0, 1, 1]

Solution

  1. Step 1: Understand stratification

    Stratification ensures that the class distribution in the train and test sets is similar to the original dataset.

  2. Step 2: Calculate class distribution

    Original y has 3 zeros and 3 ones. With stratification, y_train should have 1 zero and 2 ones.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Stratify maintains class distribution. [OK]
Hint: Stratify maintains class distribution. [OK]
Common Mistakes:
3. You implemented gradient checking but the numerical and analytical gradients differ significantly. What is the most likely cause?
medium
A. The model is overfitting.
B. The step size for numerical gradient is too large.
C. The analytical gradient is incorrect.
D. The learning rate is too high.

Solution

  1. Step 1: Identify potential causes for gradient mismatch

    Significant differences often indicate errors in the analytical gradient.

  2. Step 2: Eliminate other options

    The step size for numerical gradient is too large. would cause small numerical errors, not significant differences. The learning rate is too high. and C are unrelated to gradient checking.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Mismatch often means analytical error. [OK]
Hint: Mismatch often means analytical error. [OK]
Common Mistakes:
4. A Gaussian Naive Bayes model is giving poor performance on a dataset. Which of the following is the most likely cause?
medium
A. The model has too many parameters.
B. The features are not normally distributed.
C. The dataset is too small.
D. The features are highly correlated.

Solution

  1. Step 1: Identify Gaussian Naive Bayes assumptions

    Gaussian Naive Bayes assumes that features are normally distributed.

  2. Step 2: Evaluate each option

    The features are not normally distributed. is correct because non-normal distribution violates the model's assumptions. The model has too many parameters. is incorrect as GaussianNB is simple. The dataset is too small. is less likely as small datasets affect all models. The features are highly correlated. is incorrect as GaussianNB can handle correlated features.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    GaussianNB assumes normal distribution. [OK]
Hint: GaussianNB assumes normal distribution. [OK]
Common Mistakes:
5. How would you modify the scaled dot-product attention mechanism to handle variable-length sequences efficiently?
medium
A. Use padding and mask the padded values.
B. Use a fixed-size window for all sequences.
C. Truncate all sequences to the same length.
D. Ignore sequences longer than a threshold.

Solution

  1. Step 1: Identify the challenge

    Variable-length sequences require handling of different sequence lengths.

  2. Step 2: Choose the correct approach

    Padding with masking is efficient and maintains sequence integrity.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Pad and mask for variable lengths [OK]
Hint: Pad and mask for variable lengths [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard