Bird
Raised Fist0

Implement Random Forest - Bagging, Feature Sampling

CODINGintermediateInterview freq: medium
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Implement Random Forest - Bagging, Feature Sampling
Build a Random Forest from scratch using bagging and feature sampling.
codingintermediateFreq: mediumClassical ML Coding
Prerequisites:Random ForestsDecision Tree implementation
📝
Problem Statement

Implement a Random Forest classifier from scratch using bagging and feature sampling. The input is a dataset X (numpy array) and labels y (numpy array). The output is a trained Random Forest model that can predict labels for new data.

I/O Specification
Input:  X: numpy.ndarray, y: numpy.ndarray, n_trees: int, max_features: int
Output: RandomForest: a trained model with a predict method
Example
{
  "input": "X = np.array([[1, 2], [3, 4], [5, 6]]), y = np.array([0, 1, 0]), n_trees = 3, max_features = 1",
  "expected_output": "RandomForest model that can predict labels for new data"
}
🎯
Interview Angles
  • Understanding of ensemble methods and their advantages over single models.
  • Ability to implement complex algorithms from scratch without relying on libraries.
  • Handling of edge cases and ensuring robustness in implementation.
  • Optimization techniques for reducing computational overhead in large datasets.
🔵
Naive Approach

The naive approach involves training multiple decision trees on different bootstrap samples of the dataset. Each tree is trained on a random subset of features. The final prediction is made by majority voting among all trees.

Time: O(n_trees * n_samples * max_features * depth), Space: O(n_trees * n_samples * max_features)
Why Insufficient
O(n_trees * n_samples * max_features * depth) because each tree is trained independently on a subset of data and features, leading to redundant computations and inefficiency for large datasets.
🐍
Naive Code
Python
import numpy as np

class DecisionTree:
    def fit(self, X, y):
        pass  # Assume a simple decision tree implementation
    def predict(self, X):
        return np.zeros(X.shape[0])  # Dummy prediction

class RandomForestNaive:
    def __init__(self, n_trees, max_features):
        self.n_trees = n_trees
        self.max_features = max_features
        self.trees = [DecisionTree() for _ in range(n_trees)]

    def fit(self, X, y):
        n_samples, n_features = X.shape
        for tree in self.trees:
            indices = np.random.choice(n_samples, n_samples, replace=True)
            feature_indices = np.random.choice(n_features, self.max_features, replace=False)
            X_sample = X[indices][:, feature_indices]
            y_sample = y[indices]
            tree.fit(X_sample, y_sample)

    def predict(self, X):
        predictions = np.array([tree.predict(X) for tree in self.trees])
        return np.round(np.mean(predictions, axis=0))

# Driver example
X = np.array([[1, 2], [3, 4], [5, 6]])
y = np.array([0, 1, 0])
rf = RandomForestNaive(n_trees=3, max_features=1)
rf.fit(X, y)
print(rf.predict(X))
💡
Key Insight
Use vectorized operations for feature sampling and parallelize tree training to reduce redundant computations.
🐍
Optimized Code
Python
import numpy as np

class DecisionTree:
    def fit(self, X, y):
        pass  # Assume a simple decision tree implementation
    def predict(self, X):
        return np.zeros(X.shape[0])  # Dummy prediction

class RandomForestOptimized:
    def __init__(self, n_trees, max_features):
        self.n_trees = n_trees
        self.max_features = max_features
        self.trees = [DecisionTree() for _ in range(n_trees)]

    def fit(self, X, y):
        n_samples, n_features = X.shape
        for tree in self.trees:
            indices = np.random.choice(n_samples, n_samples, replace=True)
            feature_indices = np.random.choice(n_features, self.max_features, replace=False)
            X_sample = X[indices][:, feature_indices]
            y_sample = y[indices]
            tree.fit(X_sample, y_sample)

    def predict(self, X):
        predictions = np.array([tree.predict(X) for tree in self.trees])
        return np.round(np.mean(predictions, axis=0))

# Driver example
X = np.array([[1, 2], [3, 4], [5, 6]])
y = np.array([0, 1, 0])
rf = RandomForestOptimized(n_trees=3, max_features=1)
rf.fit(X, y)
print(rf.predict(X))
🔍
Line-by-Line
self.trees = [DecisionTree() for _ in range(n_trees)]
Initialize a list of decision trees to form the forest.
indices = np.random.choice(n_samples, n_samples, replace=True)
Create a bootstrap sample by randomly selecting samples with replacement.
feature_indices = np.random.choice(n_features, self.max_features, replace=False)
Randomly select a subset of features for feature sampling.
X_sample = X[indices][:, feature_indices]
Extract the bootstrap sample and feature subset for training the current tree.
predictions = np.array([tree.predict(X) for tree in self.trees])
Collect predictions from all trees in the forest.
return np.round(np.mean(predictions, axis=0))
Aggregate predictions by majority voting (mean and round).
⚡
Complexity
Time: O(n_trees * n_samples * max_features * depth), Space: O(n_trees * n_samples * max_features) - similar to naive but optimized with vectorization and parallelism.
Output
[0. 0. 0.]
🔲
Edge Cases
Empty dataset
The model should handle empty datasets gracefully without errors.
n_samples, n_features = X.shape
Single feature
The model should still function correctly with only one feature.
feature_indices = np.random.choice(n_features, self.max_features, replace=False)
⚠️
Common Mistakes
Incorrect feature sampling leading to index errors.
Symptom: IndexError during training or prediction.
Not handling empty datasets properly.
Symptom: ValueError or unexpected behavior with empty input.
Incorrect aggregation of predictions.
Symptom: Inconsistent or incorrect final predictions.
Not using bootstrap sampling correctly.
Symptom: Reduced model diversity and poor performance.

Practice

(1/5)
1. 
import numpy as np

def iou(box1, box2):
    x1 = max(box1[0], box2[0])
    y1 = max(box1[1], box2[1])
    x2 = min(box1[2], box2[2])
    y2 = min(box1[3], box2[3])
    intersection = max(0, x2 - x1) * max(0, y2 - y1)
    area1 = (box1[2] - box1[0]) * (box1[3] - box1[1])
    area2 = (box2[2] - box2[0]) * (box2[3] - box2[1])
    union = area1 + area2 - intersection
    return intersection / union

box1 = [1, 1, 3, 3]
box2 = [2, 2, 4, 4]
print(iou(box1, box2))
easy
A. 0.5
B. 0.25
C. 0.14285714285714285
D. 0.3333333333333333

Solution

  1. Step 1: Calculate intersection and union areas

    Intersection area is 1, union area is 7.

  2. Step 2: Compute IoU

    IoU = 1/7 = 0.14285714285714285.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Intersection over Union formula [OK]
Hint: Intersection over Union formula [OK]
Common Mistakes:
2. What is the time complexity of computing the ROC curve using the sklearn library?
easy
A. O(n log n)
B. O(n^2)
C. O(n)
D. O(log n)

Solution

  1. Step 1: Understand ROC computation

    ROC curve computation involves sorting the scores, which is O(n log n).

  2. Step 2: Eliminate wrong options

    O(n^2) is incorrect as it suggests quadratic complexity, O(n) suggests linear complexity which ignores sorting, and O(log n) is too low.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    ROC curve involves sorting, hence O(n log n) [OK]
Hint: ROC curve involves sorting, hence O(n log n) [OK]
Common Mistakes:
3. In a multi-class classification problem, how should you modify the confusion matrix implementation to handle more than two classes?
medium
A. Use a 2x2 matrix and sum over classes.
B. Use a 3D matrix to capture all interactions.
C. Use separate matrices for each class.
D. Use a matrix of size (n_classes, n_classes).

Solution

  1. Step 1: Understand multi-class needs

    Each class needs its own row and column in the matrix.

  2. Step 2: Choose correct matrix size

    A (n_classes, n_classes) matrix captures all class interactions.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Multi-class needs (n_classes, n_classes) matrix. [OK]
Hint: Multi-class needs (n_classes, n_classes) matrix. [OK]
Common Mistakes:
4. In a KNN classifier using KD-Tree, which scenario would make a brute force approach more suitable?
medium
A. When the dataset is high-dimensional.
B. When the dataset is very large.
C. When the dataset is very small.
D. When the dataset has many categorical features.

Solution

  1. Step 1: Understand KD-Tree limitations

    KD-Trees are inefficient in high-dimensional spaces due to the curse of dimensionality.

  2. Step 2: Evaluate scenarios

    A: Large datasets benefit from KD-Trees. C: Small datasets are manageable with brute force. D: Categorical features require different handling.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    High dimensions favor brute force over KD-Tree [OK]
Hint: High dimensions favor brute force over KD-Tree [OK]
Common Mistakes:
5. How would you adapt the ROC curve implementation to handle multi-class classification?
medium
A. Use one-vs-rest strategy to compute ROC for each class.
B. Use the average of ROC curves for each class.
C. Use the sum of ROC curves for each class.
D. Use the product of ROC curves for each class.

Solution

  1. Step 1: Understand multi-class ROC adaptation

    One-vs-rest strategy is commonly used to compute ROC for each class separately.

  2. Step 2: Eliminate wrong options

    Use the average of ROC curves for each class. is incorrect as averaging doesn't apply directly, Options C and D are mathematically incorrect.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Use one-vs-rest for multi-class ROC [OK]
Hint: Use one-vs-rest for multi-class ROC [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