The Conditioning Bias in Binary Decision Trees and Random Forests and
  Its Elimination
Gábor Timár György Kovács
Decision tree and random forest classification and regression are some of the
most widely used in machine learning approaches. Binary decision tree
implementations commonly use conditioning in the form 'feature $\leq$ (or $<$)
threshold', with the threshold being the midpoint between two observed feature
values. In this paper, we investigate the bias introduced by the choice of
conditioning operator (an intrinsic property of implementations) in the
presence of features with lattice characteristics. We propose techniques to
eliminate this bias, requiring an additional prediction with decision trees and
incurring no cost for random forests. Using 20 classification and 20 regression
datasets, we demonstrate that the bias can lead to statistically significant
differences in terms of AUC and $r^2$ scores. The proposed techniques
successfully mitigate the bias, compared to the worst-case scenario,
statistically significant improvements of up to 0.1-0.2 percentage points of
AUC and $r^2$ scores were achieved and the improvement of 1.5 percentage points
of $r^2$ score was measured in the most sensitive case of random forest
regression. The implementation of the study is available on GitHub at the
following repository: \url{https://github.com/gykovacs/conditioning_bias}.