Bootstrap Decision Tree Classifier

Train an ensemble of decision trees using bootstrap samples. For each tree, draw training rows with replacement, train that tree on its own sampled rows, and use it to predict every query. Return the class with the most votes for each query. If several classes tie for the most votes, choose the smallest class label.

trainingData[i] is a training row and labels[i] is its class. The rows in queries have the same number of features. Return one class label per query, in the original query order.

Practice training rules

For this exercise, use the following deterministic sampler and full CART rules. These rules complete details that the report does not specify.

Let n = trainingData.length. Start the random state at seed. For each tree, draw exactly n row indexes. Before each draw, update state = (state * 48271) % 2147483647, then draw row state % n. Keep the state from one tree to the next. Drawing rows is the only operation that advances it. Repeated indexes remain repeated training examples.

Train each tree as follows:

1. At a node, count the classes in its sampled rows. If all rows have one class, make a leaf with that class.
2. Consider every feature. Sort its distinct values at this node. Each midpoint between two consecutive distinct values is a candidate split. A row goes left when its feature value is at most the midpoint; otherwise it goes right. Every candidate has two nonempty children.
3. For a nonempty set S, define G(S) = 1 - sum_c (count_c / |S|)^2. Choose the split minimizing (|L| * G(L) + |R| * G(R)) / |S|. Break a tie by the smallest feature index, then the smallest midpoint.
4. If no candidate split exists, make a leaf with the most frequent class at this node, choosing the smallest label in a tie.
5. Otherwise split and apply these rules recursively to both children. Grow the tree even when the best split does not reduce impurity. Do not prune the tree, limit its depth, or select a random subset of features.

A query follows the same at-most-midpoint rule at each internal node until it reaches a leaf. Each tree casts one vote for that leaf class. All feature indexes are zero-based. Since the feature values are integers, a midpoint between a and b can be compared exactly with 2 * value <= a + b.