Introduction
Ensemble learning relies heavily on the diversity of its base learners. Traditionally, randomization in decision trees has been approached as a binary choice: either start with a deterministic heuristic (like C4.5) and add minor perturbations via techniques like Bagging, or build trees that are entirely random. This paper proposes that these approaches represent the extreme ends of a continuous spectrum. By introducing Variable-Random Trees (VR-Trees), the authors explore the "middle ground" of this spectrum, demonstrating that intermediate levels of randomness often yield superior predictive power, particularly in noisy environments.
The VR-Tree Framework
The core of this approach is the VR-Tree, a base learner whose level of randomization is controlled by a parameter $\alpha \in [0, 1]$. During construction, each node split is determined by a weighted coin flip:
- With probability $\alpha$, the algorithm employs a deterministic heuristic (such as Gain Ratio) to select the optimal split.
- With probability $1-\alpha$, the algorithm selects a feature and split point entirely at random.
This mechanism allows for a smooth transition from purely random trees ($\alpha = 0$) to standard deterministic trees ($\alpha = 1$). The authors also extend this to subspace methods, as detailed in the algorithm below.
Analysis of the Randomization Spectrum
Empirical results across 45 UCI datasets reveal a distinct "phase transition" around $\alpha = 0.5$. The "random-heavy" half of the spectrum ($0 \leq \alpha \leq 0.5$) tends to produce larger, highly diverse trees capable of approximating complex, non-axis-parallel decision boundaries. Conversely, the "deterministic-heavy" half ($0.5 < \alpha \leq 1$) produces more accurate individual trees that suffer from high correlation within an ensemble.
As shown in the figure above, the relationship between error and $\alpha$ is often U-shaped. This confirms that neither extreme is typically optimal; the best performance is found in the previously unexplored middle of the spectrum. A key insight is that Random Forests (RF) are "constrained" to a narrow range of this spectrum because they always select the best feature from a subset, tethering them to deterministic heuristics. VR-Trees, by contrast, can explore regions of high diversity that RF cannot reach.
Coalescence: Automating Randomness
Since the optimal $\alpha$ varies by dataset, the authors introduce Coalescence. Instead of tuning for a single $\alpha$, Coalescence builds an ensemble by sampling multiple $\alpha$ values from the random-heavy range $[0, 0.5]$. This creates a "committee of experts" with varying degrees of diversity and accuracy, providing robustness without the need for exhaustive cross-validation.
Key Results and Comparative Performance
In head-to-head comparisons using the Friedman test, Coalescence consistently outperformed established methods:
- Ranking: Coalescence achieved the top rank against Random Forests, Random Subspace, and C5 Boosting.
- Statistical Significance: Coalescence was found to be significantly better than traditional Bagging and Max-Diverse Ensembles.
- Win Conditions: Coalescence is particularly effective on datasets with non-axis-parallel boundaries or significant class noise. In contrast, Random Forests maintain an edge on very small datasets or those with a high proportion of irrelevant "noise" features.
Conclusion
The VR-Tree framework demonstrates that the diversity-accuracy trade-off in ensemble learning is best managed by exploring the full spectrum of randomization. While VR-Trees can be sensitive to irrelevant attributes at low $\alpha$ values, the Coalescence method provides a powerful, automated way to leverage high-diversity models. Future research will focus on integrating more robust feature selection into the random split process to further mitigate the impact of noise features.
Summary updated