Abstract
This paper introduces a new ensemble approach, Feature-Subspace Aggregating (Feating), which builds local models instead of global models. Feating is a generic ensemble approach that can enhance the predictive performance of both stable and unstable learners. In contrast, most existing ensemble approaches can improve the predictive performance of unstable learners only. Our analysis shows that the new approach reduces the execution time to generate a model in an ensemble through an increased level of localisation in Feating. Our empirical evaluation shows that Feating performs significantly better than Boosting, Random Subspace and Bagging in terms of predictive accuracy, when a stable learner SVM is used as the base learner. The speed up achieved by Feating makes feasible SVM ensembles that would otherwise be infeasible for large data sets. When SVM is the preferred base learner, we show that Feating SVM performs better than Boosting decision trees and Random Forests. We further demonstrate that Feating also substantially reduces the error of another stable learner, k-nearest neighbour, and an unstable learner, decision tree.
Introduction
Traditional ensemble methods like Bagging and Boosting have long been the gold standard for improving predictive accuracy. However, these methods are primarily effective for "unstable" learners—algorithms like decision trees where small changes in training data lead to significant model variations. "Stable" learners, such as Support Vector Machines (SVM) or k-Nearest Neighbors (k-NN), typically do not benefit from these methods because they lack the necessary model diversity when data is perturbed.
Furthermore, training global models like SVMs on massive datasets is computationally expensive due to their high-order polynomial time complexity. The authors propose Feating (Feature-Subspace Aggregating) to address both the lack of diversity for stable learners and the scalability issues of large-scale global modeling.
Methodology: The Level Tree Approach
Feating shifts the paradigm from global model perturbation to local model aggregation. Instead of training a single complex model on the entire dataset, Feating subdivides the feature space into non-overlapping local regions.
To implement this partitioning, the authors utilize a structure called a Level Tree. Unlike a standard decision tree, a Level Tree is restricted such that every node at a specific level must split on the same attribute. Each leaf node in this tree represents a localized region of the feature space and contains a local model trained exclusively on the data subset falling into that region.
An ensemble is constructed by creating multiple Level Trees, either through exhaustive enumeration of attribute combinations (for small feature sets) or random selection (for larger sets). Predictions are made by passing a new data point through all trees and aggregating the outputs of the corresponding local models via majority voting.
Computational Efficiency and Scalability
One of the most significant advantages of Feating is its ability to bypass the complexity constraints of global models. If a learning algorithm has a time complexity of $O(m^2)$ or $O(m^3)$, training one global model on $m$ instances is far more computationally intensive than training $N$ local models on $m/N$ instances.
As shown in the experimental analysis, increasing the level of localisation ($h$) leads to a dramatic reduction in execution time. For example, on the connect-4 dataset (over 67,000 instances), training 100 local SVM models via Feating took approximately 1.7 days, whereas a single global SVM required 16.3 days. The authors estimate that Boosting an SVM on the same data would have taken over four years, making Feating a critical tool for scaling stable learners to big data.
Key Results
Empirical evaluations across 11 UCI datasets demonstrated that Feating SVM significantly outperforms traditional ensemble methods like Boosting, Bagging, and Random Subspace. The average error rate across eight benchmark datasets dropped from 12.79% for a single SVM to 9.36% for Feating SVM at a localization level of $h=3$.
Beyond SVMs, Feating proved versatile by substantially reducing error rates for both k-NN (stable) and J48 decision trees (unstable). Additionally, the "Feating-mix" approach allows for an ensemble of heterogeneous base learners, often matching the performance of the best individual learner without requiring prior selection.
Conclusion and Future Work
Feating provides a robust framework for creating diverse ensembles from stable learners while offering massive speedups for large-scale datasets. While highly effective, the method faces a "sparsity trap" if the localization level $h$ is set too high, leading to insufficient data for local models. Future research will focus on automated heuristics for determining the optimal $h$ and exploring functional subdivisions of the feature space beyond simple attribute splits.
Summary updated