Decision Tree Classifier from Scratch

Implement a decision tree classifier from scratch. You are given training rows xTrain, their numeric class labels yTrain, and unlabeled test rows xTest. Return the predicted class label for each test row.

An internal node stores a feature index and a threshold. A leaf stores a class label. To classify a row, follow the feature comparisons until reaching a leaf.

Entropy and information gain

For a nonempty set of rows, let p(c) be the fraction whose label is c. Its entropy is H = -sum(p(c) * log2(p(c))), summing only over labels present in the set. For a split into nonempty children L and R, the information gain is H(parent) - (|L| * H(L) + |R| * H(R)) / |parent|.

Rules for this exercise

The following rules make training and prediction deterministic:

1. At each node, consider feature indices in ascending order. For each feature, sort its distinct values among the rows at that node. Consider the midpoint of every adjacent pair of distinct values, in ascending order, as a candidate threshold. Compute a midpoint as a + (b - a) / 2.
2. Send rows with a feature value less than or equal to the threshold to the left child; send greater values to the right child. Ignore a threshold if floating-point rounding would leave either child empty. Positive and negative zero represent the same numeric value.
3. Start the best gain at zero. Replace the selected split only when a candidate gain is greater than the current best gain by more than 10^-12. Thus a tied gain keeps the earlier feature and then the earlier threshold.
4. If every row has the same label, create a leaf immediately. Also create a leaf when no candidate improves the initial zero gain by more than 10^-12. A leaf uses the most frequent label at that node; equal frequencies choose the smallest numeric label.
5. Otherwise, recursively train both children using the selected split. There is no depth limit or additional pruning.
6. Return labels in the original order of xTest. An empty test set returns an empty array. Labels are numeric categories and may be negative or fractional; do not round or convert them to integers.

Implement the entropy, split selection, tree construction, and prediction logic yourself. Standard containers, sorting, and logarithm functions may be used; prebuilt machine-learning implementations may not.