Thresholding for Making Classifiers Cost-sensitive

Victor S. Sheng, Charles X. LingAAAI 2006

Abstract

Traditional machine learning often treats all classification errors as equal, yet real-world applications frequently involve asymmetric costs. This paper introduces Thresholding, a robust meta-learning approach that transforms any probabilistic classifier into a cost-sensitive one. By empirically searching for the optimal probability threshold on training data and employing a "widest valley" heuristic, Thresholding overcomes the limitations of theoretical formulas that assume perfect probability calibration. Experimental results across 12 UCI datasets demonstrate that Thresholding consistently outperforms established methods like MetaCost and is significantly more resilient to high cost-imbalance ratios.

Introduction

In many domains, such as medical diagnosis or fraud detection, the cost of a false negative (e.g., missing a disease) far outweighs the cost of a false positive. While cost-sensitive algorithms exist, many are model-specific or rely on theoretical threshold formulas ($T = \frac{C(1,0)}{C(1,0) + C(0,1)}$). These formulas assume that classifiers produce perfectly calibrated probability estimates—a condition rarely met by popular models like decision trees. This paper proposes a general-purpose meta-learning wrapper called Thresholding to bridge this gap.

Methodology: The Thresholding Approach

Thresholding treats the base classifier as a black box that outputs probability estimates. The method follows a three-step process:

  1. Internal Cross-Validation: To prevent overfitting, $m$-fold cross-validation is performed on the training set to generate probability estimates for all training instances.
  2. Empirical Search: The algorithm evaluates the total misclassification cost for every possible probability threshold present in the training data, identifying the threshold that minimizes this cost.
  3. Widest Valley Heuristic: In cases where multiple thresholds yield the same minimum cost, the algorithm selects the one situated in the "widest valley." This heuristic ensures the chosen threshold is stable and less sensitive to minor fluctuations in probability estimates.
Figure 1: The 'widest valley' heuristic for selecting stable optimal thresholds.

Experimental Evaluation

The authors evaluated Thresholding against other meta-learning techniques, including MetaCost (relabeling training data), CostSensitiveClassifier (relabeling test data), and Weighting (instance weighting). Testing was conducted on 12 binary classification datasets from the UCI repository, with costs assigned based on the inverse of class distributions to simulate real-world imbalances.

Key Insights and Results

The study revealed that empirical thresholding consistently outperforms the theoretical threshold formula in 9 out of 12 datasets. This confirms that searching for a threshold on actual training data compensates for the systematic biases and poor calibration inherent in real-world classifiers.

Figure 2: Total cost comparison on the 'Sick' dataset across varying bagging iterations.

Furthermore, Thresholding demonstrated superior robustness to extreme cost ratios (e.g., 20:1). While the total costs for competing methods often spiked as penalties increased, Thresholding maintained a flatter, more stable cost curve. As shown in Figure 2, Thresholding is particularly effective even with a low number of bagging iterations, offering a computationally efficient alternative to more complex ensemble methods.

Conclusion

Thresholding provides a simple yet powerful framework for adapting any classifier to cost-sensitive environments. By prioritizing empirical performance and threshold stability over rigid theoretical assumptions, it achieves state-of-the-art results across diverse datasets. Future work will focus on extending this binary classification logic to multi-class problems involving complex cost matrices.

Summary updated

BibTeX
@inproceedings{sheng2006thresholding,
  author = {Victor S. Sheng and Charles X. Ling},
  title = {{Thresholding for Making Classifiers Cost-sensitive}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure