FastPrepRandom Forest Classifier from Scratch

Random Forest Classifier from Scratch

Microsoft logoMicrosoft● HardFULLTIMEPHONE SCREEN

Problem statement

Build a random forest classifier and use it to label new points. The training data has n rows: row i has the feature values features[i] (length d) and the class labels[i].

A random forest normally picks random rows and random features. Here those choices are given to you so that every answer is fixed. The forest has T trees. Tree t is trained on the rows listed in bootstrapSamples[t], where a row may appear more than once and each copy counts. It may only split on the feature indices in featureSubsets[t].

Training one tree

The root holds the whole sample at depth 0. For a node at depth depth holding a list of rows:

  • If depth == maxDepth, the node is a leaf.
  • Otherwise, try every candidate split. A candidate is a feature f from the tree's subset and a threshold v equal to one of the values of feature f in the node, except the largest one. Rows with features[row][f] <= v go to the left child, the others go to the right child, so both sides are non-empty.
  • The Gini impurity of a list of rows is 1 - sum(p_k^2), where p_k is the share of rows with label k. The score of a split is the weighted impurity (|L| * gini(L) + |R| * gini(R)) / |node|, where L and R are the two sides.
  • Pick the split with the lowest score. If several tie, pick the smallest feature index, then the smallest threshold.
  • If there is no candidate, or the best score is not strictly lower than the node's own impurity, the node is a leaf. Otherwise the node splits, and both children are trained the same way at depth + 1.
  • A leaf predicts the label that appears most often among its rows, counting repeated rows. If several labels tie, it predicts the smallest one.

Compare scores exactly. For example, compare fractions by cross-multiplying integers instead of using floating-point numbers, so that equal scores are seen as ties.

Predicting

To label a query point, send it down each tree: at a split on feature f with threshold v, go left when query[f] <= v and right otherwise, until you reach a leaf. Each tree votes for its leaf's label. The forest predicts the label with the most votes, and the smallest label on ties.

Return the predicted label of every point in queries, in order.

Function

randomForestPredict(features: int[][], labels: int[], bootstrapSamples: int[][], featureSubsets: int[][], maxDepth: int, queries: int[][]) → int[]

Examples

Example 1

features = [[1],[2],[3],[4]]labels = [0,0,1,1]bootstrapSamples = [[0,1,2,3]]featureSubsets = [[0]]maxDepth = 1queries = [[0],[2],[3],[10]]return = [0,0,1,1]

There is one tree, trained on all four rows, that may split on feature 0. The candidate thresholds are 1, 2, and 3. Threshold 2 sends labels [0, 0] left and [1, 1] right, so both sides are pure and the score is 0. Thresholds 1 and 3 each score 1/3. The root's own impurity is 0.5, so it splits at 2, and the depth limit 1 makes both children leaves.

Queries 0 and 2 go left to label 0. Queries 3 and 10 go right to label 1.

Example 2

features = [[1,5],[2,1],[3,4],[4,2],[5,3]]labels = [0,1,0,1,1]bootstrapSamples = [[0,1,2,3,4],[0,0,2,2,3],[1,3,4,4,1]]featureSubsets = [[1],[0,1],[0]]maxDepth = 2queries = [[3,5],[5,1],[2,2]]return = [0,1,1]

Tree 0 uses all five rows and only feature 1. Threshold 3 sends rows 1, 3, 4 (all label 1) left and rows 0, 2 (label 0) right, a perfect split.

Tree 1 uses rows [0, 0, 2, 2, 3], with labels 0, 0, 0, 0, 1. Feature 0 at threshold 3 and feature 1 at threshold 2 both split it perfectly. The tie goes to the smaller feature, so the tree splits on feature 0 at 3. Tree 2 uses rows [1, 3, 4, 4, 1], which all have label 1, so it is a single leaf.

Query [3, 5] gets votes 0, 0, 1 and is labeled 0. Query [5, 1] gets 1, 1, 1. Query [2, 2] gets 1, 0, 1 and is labeled 1.

Example 3

features = [[0,0],[0,1],[1,0],[1,1]]labels = [0,1,1,0]bootstrapSamples = [[0,1,2,3],[0,3,3,1]]featureSubsets = [[0,1],[0,1]]maxDepth = 3queries = [[0,1],[1,0]]return = [0,0]

The labels follow an XOR pattern. Tree 0 holds all four rows, and every candidate split leaves two mixed sides with score 0.5, the same as the root's impurity. The score is not strictly lower, so the root is a leaf. Its labels tie 2 to 2, so it predicts 0.

Tree 1 holds rows [0, 3, 3, 1] with labels 0, 0, 0, 1 and impurity 0.375. Feature 0 at threshold 0 scores 0.25, better than feature 1 at 0 with 1/3. Its left child, rows 0 and 1, then splits on feature 1 at 0 into two pure leaves. The right child holds two copies of row 3 and is a leaf with label 0.

Query [0, 1] gets votes 0 and 1; the tie goes to label 0. Query [1, 0] gets 0 from both trees.

Constraints

  • 1 <= n == features.length <= 50
  • 1 <= d == features[i].length <= 5, and every row has the same length d.
  • -100 <= features[i][j] <= 100
  • labels.length == n and 0 <= labels[i] <= 4
  • 1 <= T == bootstrapSamples.length == featureSubsets.length <= 15
  • 1 <= bootstrapSamples[t].length <= 50 and 0 <= bootstrapSamples[t][k] < n
  • 1 <= featureSubsets[t].length <= d, and each featureSubsets[t] holds distinct indices with 0 <= featureSubsets[t][k] < d.
  • 0 <= maxDepth <= 6
  • 1 <= queries.length <= 50, queries[q].length == d, and -100 <= queries[q][j] <= 100

More Microsoft problems

See Microsoft hiring insights
Saved
public int[] randomForestPredict(int[][] features, int[] labels, int[][] bootstrapSamples, int[][] featureSubsets, int maxDepth, int[][] queries) {
    // Write your code here.
}
Checking account…