Implement a Random Forest Classifier from Scratch

Implement a random forest classifier by hand: write the decision trees and the ensemble yourself instead of calling a machine learning library's tree or forest. The report gives only this instruction, so agree the scope first. A usual expectation is a class with `fit(X, y)` and `predict(X)`, where `X` is a numeric array of shape `(n_samples, n_features)` and `y` holds one class label per row. Assume NumPy may be used for array arithmetic unless the interviewer rules it out. ```hint Two sources of randomness A forest of identical trees predicts exactly like one tree. Identify the two places where randomness enters a random forest, and where in your code each one belongs. ``` ```hint Where the time goes Most training time is spent choosing splits. Think about how to score every threshold of one feature without rescanning all of the node's rows for each threshold. ``` ### Constraints and Clarifications - Not given: whether the task is classification or regression, the feature types, missing values, the data size, and which hyperparameters to support. The prompt assumes classification on numeric features with no missing values; confirm it. ### Clarifying Questions - Classification, regression, or both? How many classes? - Are all features numeric, or are there categorical features and missing values? - Which hyperparameters must be supported: the number of trees, the maximum depth, the minimum samples to split a node or to form a leaf, the number of features tried at each split? - Should prediction return labels, class probabilities, or both? - Is an out-of-bag error estimate or a feature importance expected? - Roughly how many rows and features, so we know whether a simple split search is fast enough? ### What a Strong Answer Covers - A working decision tree: an impurity measure, the best-split search over features and thresholds, stopping rules, and leaf predictions - An efficient split search, with its complexity per node and per tree - The ensemble: a bootstrap sample per tree, a fresh random subset of features at every split, and aggregation of the trees' predictions - Edge cases: pure nodes, constant features, repeated feature values, vote ties, and classes missing from a bootstrap sample - Why the randomness reduces variance, and how each hyperparameter trades bias against variance - Clean, testable code with a sanity check on a small dataset ### Follow-up Questions - How would you estimate the forest's accuracy without a separate validation set? - How would you compute feature importance from your trees, and what is the known bias of the simplest method? - Training is too slow on a large dataset. Where would you parallelize, and what else would you change? - What changes to turn the classifier into a regressor?