Dynamic Ensemble Re-Construction for Better Ranking

Jin Huang, Charles X. LingLecture Notes in Computer Science 2005 · DOI · OpenAlex

Abstract

While standard ensemble methods like Bagging and Boosting excel at classification accuracy, they often neglect the quality of the probability estimates used for ranking. This paper introduces Dynamic Ensemble Re-Construction (DERC), an algorithm that builds specialized sub-ensembles tailored to specific test instances. By leveraging the diversity within an existing ensemble and optimizing for a "softened" Area Under the ROC Curve (SAUC), DERC significantly improves ranking performance (AUC) over traditional methods.

Introduction

In many machine learning applications, the primary goal is not just binary classification but the relative ranking of instances based on their likelihood of belonging to a specific class. For instance, in lead prioritization or tiered marketing, the precision of probability estimates is more critical than simple class labels. However, standard ensemble techniques like Bagging and AdaBoost are primarily designed to minimize classification error, which does not necessarily optimize for ranking performance, typically measured by the Area Under the ROC Curve (AUC).

This paper addresses this gap by proposing DERC, a method that dynamically selects and combines classifiers from an ensemble based on the local characteristics of the test data.

Methodology: The DERC Algorithm

The DERC algorithm operates by "re-constructing" a new ensemble on the fly for specific test partitions. The process involves three fundamental steps:

1. Finding Similar Training Subsets

The unlabeled test set is partitioned into $n$ parts. For each part $T_i$, the algorithm identifies the most similar subsets of the original training data using a $k$-Nearest Neighbor approach. As shown in Figure 1, distances are calculated between test partitions and training subsets to find the most relevant local data. To accommodate mixed data types, a simplified Value Difference Metric (VDM) is used for nominal attributes, while Euclidean distance is applied to numerical ones.

Illustration of finding similar training subsets for test partitions.

2. Selecting Classifiers via SAUC

The core innovation of DERC is the use of Softened Area Under the ROC Curve (SAUC) to select the best classifiers for a specific test partition. Standard AUC is a step function and can be brittle as a selection heuristic. SAUC introduces a power parameter ($\gamma$) to "soften" the metric, creating a smoother optimization landscape. By varying $\gamma$, the algorithm can select a diverse set of classifiers that are robust to different ranking variations within the local data neighborhood.

3. Weighted Combination

Finally, the selected classifiers are combined using a weighted averaging scheme. The weights are determined by the classifiers' performance (SAUC) on the identified similar training subsets, ensuring that models with higher local reliability contribute more to the final prediction.

Experimental Evaluation

The researchers evaluated DERC using 16 representative binary datasets from the UCI Machine Learning Repository, covering medical, business, and general domains. Naive Bayes was employed as the base learner, and DERC's performance was benchmarked against standard Bagging and AdaBoost implementations from the WEKA toolkit.

Results and Discussion

The empirical results demonstrate that DERC consistently outperforms its parent ensembles in ranking performance. As seen in the comparison against Bagging (Figure 2), DERC variants with 3 or 4 partitions (DERC(3) and DERC(4)) achieved significantly better AUC in 8 out of 16 datasets, with only one loss.

Performance comparison of DERC vs. Bagging across 16 UCI datasets.

A key finding is the "Goldilocks" effect regarding the number of partitions ($n$). Too few partitions fail to capture local data characteristics, while too many partitions lead to small training subsets that increase the risk of overfitting. The optimal balance was generally found at $n=3$ or $n=4$. Against AdaBoost, DERC(3) and DERC(4) also showed strong performance, winning in 5 datasets and tying in 10.

Conclusion

Dynamic Ensemble Re-Construction (DERC) provides a robust framework for improving the ranking performance of ensemble models. By dynamically tailoring sub-ensembles to local test data and utilizing the SAUC metric for selection, DERC effectively exploits classifier diversity. Future work will explore the application of DERC to more complex base learners, such as Decision Trees and SVMs, and investigate its performance across a broader range of ensemble construction techniques.

Summary updated

BibTeX
@inproceedings{huang2005dynamic,
  author = {Jin Huang and Charles X. Ling},
  title = {{Dynamic Ensemble Re-Construction for Better Ranking}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2005},
  doi = {10.1007/11564126\_52},
}
Figure