MetaCost: a general method for making classifiers cost-sensitive

article1999KDD1,651 citations

Presents MetaCost, a general wrapper method that converts any standard, error-minimizing classification algorithm into a cost-sensitive classifier by relabeling training data using ensemble probability estimates and arbitrary cost matrices.

Listen

Real-world data mining and decision-making problems rarely involve equal error costs; for instance, failing to detect a critical system failure or missing a high-value customer incurs far greater losses than generating a false alarm. Despite this reality, most standard classification algorithms are designed solely to minimize error counts, implicitly treating all mistakes as equally costly. Existing workarounds, such as manually altering class frequencies in training data (stratification), suffer from severe constraints: they often distort underlying data distributions, discard valuable training examples or increase compute time, and fail to accommodate complex multiclass cost structures.

The article demonstrates and evaluates MetaCost, a general method that converts any standard classification algorithm into a cost-sensitive system without requiring internal modifications to the base algorithm.

MetaCost operates as an external wrapper. It generates multiple bootstrap resamples of the training data, trains the chosen classifier on each resample, and pools their votes to estimate the probability distribution across classes for every training example. Using these estimated probabilities alongside a specified cost matrix, it recalculates the expected cost (risk) for each decision and relabels every training example with its optimal, cost-minimizing class. Finally, it trains a single final model on the relabeled dataset. The authors evaluated MetaCost using 28 benchmark databases (15 multiclass and 12 two-class problems) alongside a large NASA space shuttle sensor dataset, using decision rule induction as the base classifier.

Empirical testing showed that MetaCost consistently achieved superior cost reductions compared to standard classifiers and traditional stratification techniques. In multiclass evaluations, MetaCost reduced costs more effectively than undersampling and oversampling in all tested datasets under realistic cost conditions, outperforming standard classification with over 99% statistical confidence and achieving cost reductions approximately twice as large as undersampling. In two-class benchmarks, MetaCost maintained lower overall costs across various cost ratios. Ablation analysis confirmed that while generating multiple models is essential to compute reliable probabilities, as few as 10 to 20 resamples are sufficient for peak performance. On the large shuttle dataset (58,000 examples), MetaCost scaled efficiently; using small resamples alongside noise-filtering effects, it lowered costs by over an order of magnitude while running more than ten times faster than the base classifier on noisy data.

These findings indicate that organizations can directly minimize financial and operational risk without abandoning their existing, well-tested data mining algorithms. Because MetaCost outputs a single, clean model rather than a complex black-box ensemble, it preserves rule comprehensibility and auditability. Furthermore, if the operational cost matrix changes, organizations only need to re-run the final relabeling and training step rather than recomputing the entire ensemble, saving substantial computational time and workflow disruption.

Decision-makers should consider adopting wrapper-based relabeling like MetaCost when deploying predictive models in high-stakes environments where error consequences are asymmetric. When scaling to larger datasets, teams can minimize compute costs by keeping the resample count near 10 and utilizing sub-sampled training partitions, or by running the independent resamples in parallel.

Confidence in these findings is high for rule-based and tree-based decision models across standard tabular benchmarks. However, the evaluation focused primarily on one underlying rule-learning algorithm, and the method relies on model instability (such as that found in decision trees) to generate diverse votes. Leaders should exercise caution before applying the standard implementation to inherently stable algorithms (such as naive Bayes or nearest-neighbor classifiers) without adapting the sampling approach to use feature subsets instead of data subsets.

Instituto Superior Técnico classification algorithm computational efficiency data mining techniques MetaCost cost-sensitive classification error-based classifiers

Domingos (1999).pdf

Paper: Addressing the Curse of Imbalanced Training Sets: One-Sided Selection, Miroslav Kubát et al. (1997). Introduces foundational sampling and ensemble techniques for handling imbalanced datasets, establishing the traditional data-resampling benchmarks that MetaCost seeks to outperform.
Paper: Classification by Pairwise Coupling, T. Hastie et al. (1997). Presents foundational methods for estimating multi-class probability distributions from ensemble votes, providing the probability estimation concepts used in MetaCost's relabeling phase.
Paper: A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection, Ron Kohavi (1995). Provides a rigorous empirical analysis of bootstrap and cross-validation sampling properties that justify the resampling mechanism MetaCost uses to generate model diversity.
Paper: Neural Network Ensembles, Lars Kai Hansen et al. (1990). Establishes how pooling votes across an ensemble of sub-sampled models reduces variance and yields superior probabilistic predictions compared to single models.
Paper: Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms, Thomas G. Dietterich (1998). Details the statistical evaluation procedures necessary for rigorously comparing classification algorithms across benchmark suites as practiced in the MetaCost validation.

Paper: The foundations of cost-sensitive learning, Charles Elkan (2001). Establishes formal theoretical foundations for cost-sensitive learning, providing mathematical justification and threshold-adjustment principles for the empirical relabeling strategies introduced in MetaCost.
Paper: Transforming classifier scores into accurate multiclass probability estimates, Bianca Zadrozny et al. (2002). Explores advanced calibration methods to produce accurate multiclass probability estimates, directly improving the class probability estimation step central to MetaCost's risk calculation.
Paper: Predicting good probabilities with supervised learning, Alexandru Niculescu-Mizil et al. (2005). Evaluates which learning algorithms produce well-calibrated probabilities, addressing MetaCost's requirement for reliable probability estimates across stable and unstable classifiers.
Paper: SMOTE: Synthetic Minority Over-sampling Technique, N. Chawla et al. (2002). Introduces synthetic minority over-sampling as an alternative data-level intervention for class-skewed and cost-asymmetric scenarios tested against cost-sensitive wrappers.
Paper: Probability Estimates for Multi-class Classification by Pairwise Coupling, Tingyao Wu et al. (2003). Develops modern linear system formulations for multi-class probability estimation that enhance the multi-category voting and relabeling stages of cost-sensitive wrappers.
Paper: A Reductions Approach to Fair Classification, Alekh Agarwal et al. (2018). Extends black-box wrapper reductions by mapping constrained fair classification tasks onto repeated cost-sensitive classification subproblems.
Paper: Imbalanced-learn: A Python Toolbox to Tackle the Curse of Imbalanced Datasets in Machine Learning, Guillaume Lemaitre et al. (2017). Implements modern open-source Python toolkits that operationalize cost-sensitive resampling, ensemble relabeling, and imbalanced learning algorithms.

Cover for MetaCost: a general method for making classifiers cost-sensitive

Abstract

Research in machine learning, statistics and related fields has produced a wide variety of algorithms for classification. However, most of these algorithms assume that all errors have the same cost, which is seldom the case in KDD problems. Individually making each classification learner cost-sensitive is laborious, and often non-trivial. In this paper we propose a principled method for making an arbitrary classifier cost-sensitive by wrapping a cost-minimizing procedure around it. This procedure, called MetaCost, treats the underlying classifier as a black box, requiring no knowledge of its functioning or change to it. Unlike stratification, MetaCost is applicable to any number of classes and to arbitrary cost matrices. Empirical trials on a large suite of benchmark databases show that MetaCost almost always produces large cost reductions compared to the cost-blind classifier used (C4.5RULES) and to two forms of stratification. Further tests identify the key components of MetaCost and those that can be varied without substantial loss. Experiments on a larger database indicate that MetaCost scales well.

Topics

classification algorithm computational efficiency data mining techniques database systems decision models frequencies k-nearest neighbors naive bayes probability distributions rule induction

Keywords

MetaCost cost-sensitive classification error-based classifiers cost matrix class probability estimates ensemble method decision trees Bayesian classifier

1 Introduction
2 The MetaCost Algorithm
3 Empirical Evaluation
3.1 Multiclass Problems
3.2 Two-Class Problems
3.3 Lesion Studies
3.4 Scaling Up
4 Related Work
5 Future Work
6 Conclusion
Acknowledgements
References

Knowls

Knowl 1 — The MetaCost Framework for Cost-Sensitive Classification
model/method
MetaCost is a meta-learning method designed to convert any arbitrary error-based (cost-blind) classification algorithm into a cost-sensitive classifier without altering the underlying learning algorithm or inspecting its internal representation.

The core intuition of MetaCost is that the optimal decision boundaries under non-uniform misclassification costs differ from zero-one loss boundaries. If training examples are relabeled according to the Bayes optimal prediction under a given cost matrix, a standard cost-blind learner trained on this relabeled dataset will implicitly learn the cost-minimizing decision boundaries.

MetaCost operates in four stages:
1. Ensemble Generation: It creates $m$ bootstrap resamples $S_1, \dots, S_m$ of the training dataset $S$ and applies the base classifier $L$ to each to learn models $M_1, \dots, M_m$ .
2. Conditional Class Probability Estimation: For each training example $x \in S$ , MetaCost estimates the conditional probability distribution $P(j|x)$ across all candidate classes $j$ by aggregating predictions (either fractional class votes or predicted class probabilities) across the ensemble models (typically excluding models trained on subsets containing $x$ ).
3. Bayes Optimal Relabeling: Using the estimated probabilities $P(j|x)$ and the cost matrix $C$ , MetaCost computes the expected conditional risk for each class and relabels $x$ with the class that minimizes this risk.
4. Final Model Induction: The original cost-blind learner $L$ is trained on the relabeled training dataset to generate a single, cost-sensitive classification model.
Knowl 2 — Conditional Risk and Bayes Optimal Class Relabeling
equation
Let $X$ denote the instance space and let $j \in \{1, \dots, K\}$ index the possible target classes. Let $C$ be an arbitrary $K \times K$ cost matrix where $C(i, j)$ represents the cost of predicting class $i$ when the true class is $j$ . Given an example $x \in X$ and conditional class probabilities $P(j|x)$ , the conditional risk $R(i|x)$ of predicting class $i$ is defined as:

$R(i|x) = \sum_{j=1}^{K} P(j|x) C(i, j)$

The Bayes optimal prediction for $x$ is the class $i^*$ that minimizes the expected conditional risk:

$i^*(x) = \arg\min_{i} R(i|x) = \arg\min_{i} \sum_{j=1}^{K} P(j|x) C(i, j)$

In the MetaCost procedure, every pre-classified training example $x \in S$ has its training label replaced by $i^*(x)$ using estimated conditional probabilities $\hat{P}(j|x)$ prior to training the final classifier.
Knowl 3 — The MetaCost Algorithm
algorithm
The MetaCost algorithm takes a training dataset, an arbitrary classification learning algorithm, a cost matrix, and ensemble hyperparameters, and returns a single cost-sensitive model.
Input:
   $S$ : training set of examples
   $L$ : classification learning algorithm
   $C$ : cost matrix where $C(i, j)$ is the cost of predicting class $i$ when true class is $j$
   $m$ : number of resamples to generate
   $n$ : number of examples in each resample
   $p$ : boolean flag, True if $L$ produces class probabilities, False otherwise
   $q$ : boolean flag, True if all resamples are used for each example, False to use only out-of-bag resamples
Output:
   $M$ : cost-sensitive classification model
for $i = 1$ to $m$ do
  Let $S_i$ be a resample of $S$ with $n$ examples drawn with replacement
  Let $M_i = L(S_i)$ (model produced by applying $L$ to $S_i$ )
end for
for each example $x$ in $S$ do
  for each class $j$ do
    if $q$ is True then
      Let $\mathcal{M}_x = \{M_1, \dots, M_m\}$
    else
      Let $\mathcal{M}_x = \{M_i \mid x \notin S_i\}$
    end if

    if $p$ is True then
       $P(j|x) = \frac{1}{|\mathcal{M}_x|} \sum_{M_i \in \mathcal{M}_x} P(j|x, M_i)$
    else
       $P(j|x) = \frac{1}{|\mathcal{M}_x|} \sum_{M_i \in \mathcal{M}_x} I(M_i(x) = j)$
    end if
  end for

  Let $x$ 's relabeled class = $\arg\min_i \sum_j P(j|x) C(i, j)$
end for
Let $S'$ be the dataset $S$ with all instance labels replaced by their relabeled classes
Let $M = L(S')$
return $M$
Knowl 4 — Experimental Evaluation Setup for Cost-Sensitive Classifiers
experimental setup
The empirical performance of MetaCost was evaluated against cost-blind learning and two variants of stratification using 28 benchmark datasets from the UCI repository (15 multiclass datasets, 12 two-class datasets, and the large Shuttle database).
- Base Learner: C4.5 decision tree learner coupled with the C4.5RULES post-processor (abbreviated C4.5R).
- Data Partitioning: 20 independent runs per dataset, using a random $2/3$ split for training and $1/3$ for testing.
- Baselines:
  1. Cost-blind C4.5R.
  2. Stratification by Undersampling: Re-weights class marginal distribution $P'(j) = \frac{C(j)P(j)}{\sum_k C(k)P(k)}$ , where $C(j) = \sum_i C(i, j)$ . Retains all examples of the highest $P'(j)$ class and samples a fraction $P'(i)/P'(j)$ of all other classes.
  3. Stratification by Oversampling: Retains all examples of the lowest $P'(j)$ class and duplicates examples of each other class $i$ approximately $P'(i)/P'(j)$ times.
- Cost Models:
  - Multiclass Fixed-Interval: $C(i, i) \sim U[0, 1000]$ and $C(i, j) \sim U[0, 10000]$ for $i \neq j$ .
  - Multiclass Class-Probability-Dependent: $C(i, i) \sim U[0, 1000]$ and $C(i, j) \sim U[0, 2000 P(i)/P(j)]$ for $i \neq j$ , reflecting higher misclassification penalties for rare classes.
  - Two-Class: $C(1, 1) = C(2, 2) = 0$ , $C(1, 2) = 1000$ , and $C(2, 1) = 1000 r$ where $r \in \{2, 5, 10\}$ (class 1 is the minority class, class 2 is the majority class).
- Default MetaCost Settings: $m = 50$ , $n = |S|$ , $p = \text{True}$ (using C4.5R rule probabilities), $q = \text{False}$ (out-of-bag probability estimation).

Knowl 5 — Multiclass Cost Reduction Performance on Benchmark Datasets

data/table

The table compares the average test cost and standard deviation over 20 runs for C4.5R, undersampling stratification, oversampling stratification, and MetaCost across 15 multiclass UCI benchmark datasets under both fixed-interval and class-probability-dependent cost matrices.

Database	Costs from fixed interval				Costs from class-prob.-dependent interval
	C4.5R	Underspl	Overspl	MetaCost	C4.5R	Underspl	Overspl	MetaCost
Annealing	$1061 \pm 23$	$1076 \pm 18$	$989 \pm 20$	$984 \pm 24$	$1258 \pm 89$	$711 \pm 44$	$1027 \pm 53$	$46 \pm 3$
Audiology	$1842 \pm 90$	$2008 \pm 81$	$1569 \pm 83$	$1769 \pm 78$	$2264 \pm 195$	$609 \pm 124$	$1833 \pm 145$	$17 \pm 10$
Glass	$1986 \pm 81$	$1856 \pm 102$	$1786 \pm 90$	$1217 \pm 64$	$1169 \pm 92$	$548 \pm 36$	$1052 \pm 86$	$221 \pm 10$
Iris	$652 \pm 30$	$618 \pm 26$	$641 \pm 25$	$513 \pm 16$	$470 \pm 22$	$454 \pm 18$	$469 \pm 20$	$345 \pm 20$
LED	$2016 \pm 92$	$2181 \pm 78$	$1897 \pm 81$	$1484 \pm 67$	$835 \pm 44$	$814 \pm 52$	$727 \pm 21$	$393 \pm 16$
Lenses	$1624 \pm 132$	$1687 \pm 159$	$1596 \pm 167$	$1515 \pm 110$	$1171 \pm 264$	$910 \pm 218$	$972 \pm 115$	$192 \pm 18$
Lung cancer	$2363 \pm 261$	$1714 \pm 148$	$1957 \pm 263$	$1577 \pm 144$	$969 \pm 135$	$624 \pm 74$	$1013 \pm 146$	$370 \pm 39$
Lymphogr.	$1055 \pm 50$	$1000 \pm 57$	$970 \pm 57$	$721 \pm 33$	$1118 \pm 110$	$489 \pm 86$	$1054 \pm 111$	$60 \pm 5$
Post-oper.	$1239 \pm 152$	$686 \pm 31$	$1614 \pm 91$	$666 \pm 31$	$2322 \pm 230$	$841 \pm 112$	$2016 \pm 151$	$83 \pm 9$
Pr. tumor	$3475 \pm 88$	$3478 \pm 123$	$3759 \pm 98$	$3446 \pm 87$	$3193 \pm 338$	$936 \pm 117$	$1691 \pm 117$	$17 \pm 7$
Solar flare	$1602 \pm 88$	$1430 \pm 94$	$1425 \pm 79$	$875 \pm 43$	$1342 \pm 98$	$542 \pm 66$	$996 \pm 70$	$133 \pm 7$
Soybean	$716 \pm 35$	$718 \pm 44$	$739 \pm 46$	$873 \pm 91$	$682 \pm 33$	$632 \pm 37$	$685 \pm 35$	$283 \pm 26$
Splice	$659 \pm 12$	$602 \pm 13$	$715 \pm 10$	$556 \pm 11$	$412 \pm 12$	$424 \pm 9$	$419 \pm 11$	$342 \pm 4$
Wine	$685 \pm 24$	$647 \pm 33$	$670 \pm 29$	$558 \pm 25$	$461 \pm 18$	$475 \pm 13$	$455 \pm 14$	$264 \pm 13$
Zoology	$1148 \pm 103$	$1153 \pm 105$	$857 \pm 49$	$873 \pm 66$	$624 \pm 85$	$650 \pm 108$	$540 \pm 62$	$169 \pm 14$

Under the fixed-interval cost model, MetaCost achieves lower cost than C4.5R and undersampling on 14 of 15 datasets, and lower cost than oversampling on 12 of 15 datasets. Under the class-probability-dependent cost model, MetaCost achieves the lowest cost across all 15 datasets, yielding an average cost reduction roughly twice as large as undersampling and five times as large as oversampling. In both settings, the performance difference favoring MetaCost is statistically significant with confidence exceeding $99\%$ under sign and Wilcoxon tests.

Knowl 6 — Two-Class Cost Reduction Across Variable Cost Ratios

data/table

The table reports average costs and standard deviations over 20 runs across 12 two-class UCI datasets for cost ratios $r \in \{2, 5, 10\}$ (where misclassifying the minority class costs $1000r$ and misclassifying the majority class costs $1000$ ).

Cost ratio	Database	C4.5R	Underspl	Overspl	MetaCost
2	Breast cancer	$505 \pm 25$	$509 \pm 14$	$577 \pm 23$	$511 \pm 20$
	Credit	$239 \pm 11$	$218 \pm 8$	$247 \pm 10$	$187 \pm 7$
	Diabetes	$404 \pm 12$	$386 \pm 10$	$395 \pm 8$	$335 \pm 7$
	Echocardiogram	$590 \pm 23$	$514 \pm 21$	$549 \pm 22$	$497 \pm 22$
	Heart disease	$323 \pm 15$	$328 \pm 11$	$350 \pm 15$	$304 \pm 10$
	Hepatitis	$346 \pm 24$	$327 \pm 21$	$337 \pm 21$	$326 \pm 25$
	Horse colic	$244 \pm 10$	$273 \pm 14$	$275 \pm 13$	$244 \pm 8$
	Labor	$226 \pm 35$	$308 \pm 33$	$245 \pm 35$	$247 \pm 24$
	Liver disease	$593 \pm 24$	$540 \pm 15$	$503 \pm 18$	$548 \pm 16$
	Promoters	$340 \pm 29$	$306 \pm 30$	$316 \pm 35$	$296 \pm 16$
	Sonar	$484 \pm 25$	$442 \pm 21$	$472 \pm 33$	$439 \pm 21$
	Voting	$65 \pm 7$	$67 \pm 5$	$71 \pm 6$	$59 \pm 4$
5	Breast cancer	$1078 \pm 70$	$821 \pm 37$	$1130 \pm 57$	$688 \pm 21$
	Credit	$491 \pm 28$	$306 \pm 15$	$557 \pm 24$	$282 \pm 11$
	Diabetes	$824 \pm 34$	$556 \pm 20$	$727 \pm 21$	$480 \pm 13$
	Echocardiogram	$1244 \pm 65$	$727 \pm 43$	$1068 \pm 67$	$688 \pm 23$
	Heart disease	$632 \pm 43$	$466 \pm 23$	$700 \pm 37$	$416 \pm 22$
	Hepatitis	$741 \pm 60$	$517 \pm 47$	$628 \pm 54$	$503 \pm 40$
	Horse colic	$520 \pm 24$	$510 \pm 31$	$531 \pm 31$	$415 \pm 24$
	Labor	$463 \pm 89$	$579 \pm 48$	$484 \pm 54$	$539 \pm 35$
	Liver disease	$1268 \pm 75$	$625 \pm 22$	$1054 \pm 46$	$616 \pm 13$
	Promoters	$743 \pm 69$	$449 \pm 40$	$829 \pm 102$	$409 \pm 32$
	Sonar	$1019 \pm 66$	$654 \pm 49$	$1001 \pm 57$	$517 \pm 23$
	Voting	$123 \pm 18$	$89 \pm 9$	$106 \pm 13$	$76 \pm 6$
10	Breast cancer	$2034 \pm 148$	$792 \pm 37$	$2039 \pm 98$	$711 \pm 16$
	Credit	$911 \pm 57$	$481 \pm 29$	$1039 \pm 53$	$396 \pm 13$
	Diabetes	$1524 \pm 72$	$684 \pm 24$	$1326 \pm 63$	$549 \pm 15$
	Echocardiogram	$2335 \pm 137$	$856 \pm 60$	$1945 \pm 151$	$668 \pm 16$
	Heart disease	$1147 \pm 90$	$567 \pm 40$	$1209 \pm 83$	$576 \pm 17$
	Hepatitis	$1400 \pm 123$	$770 \pm 62$	$1190 \pm 110$	$721 \pm 51$
	Horse colic	$979 \pm 50$	$638 \pm 17$	$946 \pm 57$	$617 \pm 16$
	Labor	$858 \pm 179$	$671 \pm 22$	$858 \pm 95$	$674 \pm 34$
	Liver disease	$2393 \pm 162$	$671 \pm 33$	$1883 \pm 103$	$580 \pm 13$
	Promoters	$1414 \pm 138$	$436 \pm 12$	$1634 \pm 173$	$506 \pm 52$
	Sonar	$1910 \pm 138$	$740 \pm 69$	$1799 \pm 132$	$498 \pm 20$
	Voting	$220 \pm 37$	$132 \pm 16$	$168 \pm 27$	$118 \pm 8$

Even in two-class problems where stratification can be applied without approximation, MetaCost outperforms C4.5R, undersampling, and oversampling across almost all datasets and cost ratios. MetaCost results are lower than each alternative baseline with statistical confidence exceeding $99\%$ under sign and Wilcoxon tests across all ratios (except sign test vs undersampling at $r=10$ , where confidence is $98\%$ ).

Knowl 7 — Ablation and Lesion Analysis of MetaCost Components

data/table

To evaluate the sensitivity of MetaCost to its constituent components, several variants were evaluated on the two-class databases across cost ratios $r \in \{2, 5, 10\}$ :

$m=20$ and $m=10$ : Reducing resample count from $m=50$ .
C4 Probs: Relabeling based on class probabilities from a single run of C4.5R on the complete training data rather than using an ensemble.
0-1 Votes: Ignoring base learner class probabilities and estimating probabilities strictly by counting binary predictions across models ( $p=\text{False}$ ).
All Ms: Relabeling each example using all models rather than strictly out-of-bag models ( $q=\text{True}$ ).

Cost ratio	Database	$m=20$	$m=10$	C4 Probs	0-1 Votes	All Ms
2	Breast cancer	$514 \pm 18$	$506 \pm 25$	$498 \pm 22$	$495 \pm 19$	$519 \pm 19$
	Credit	$188 \pm 7$	$196 \pm 6$	$227 \pm 9$	$202 \pm 8$	$193 \pm 7$
	Diabetes	$343 \pm 7$	$348 \pm 8$	$390 \pm 9$	$357 \pm 8$	$355 \pm 8$
	Echocardiogram	$477 \pm 20$	$460 \pm 20$	$542 \pm 20$	$507 \pm 26$	$547 \pm 25$
	Heart disease	$292 \pm 12$	$306 \pm 10$	$320 \pm 14$	$308 \pm 12$	$300 \pm 11$
	Hepatitis	$330 \pm 24$	$333 \pm 25$	$337 \pm 22$	$317 \pm 22$	$336 \pm 21$
	Horse colic	$247 \pm 9$	$258 \pm 10$	$255 \pm 10$	$237 \pm 8$	$255 \pm 10$
	Labor	$213 \pm 29$	$300 \pm 35$	$242 \pm 33$	$266 \pm 29$	$208 \pm 26$
	Liver disease	$535 \pm 11$	$553 \pm 17$	$566 \pm 16$	$537 \pm 13$	$546 \pm 19$
	Promoters	$310 \pm 25$	$337 \pm 20$	$327 \pm 45$	$357 \pm 31$	$330 \pm 30$
	Sonar	$436 \pm 24$	$449 \pm 26$	$451 \pm 25$	$469 \pm 18$	$429 \pm 18$
	Voting	$58 \pm 5$	$65 \pm 4$	$64 \pm 6$	$59 \pm 4$	$60 \pm 5$
5	Breast cancer	$712 \pm 24$	$732 \pm 27$	$823 \pm 45$	$809 \pm 41$	$719 \pm 25$
	Credit	$277 \pm 12$	$289 \pm 12$	$331 \pm 20$	$287 \pm 14$	$286 \pm 11$
	Diabetes	$477 \pm 10$	$511 \pm 13$	$600 \pm 27$	$490 \pm 11$	$499 \pm 11$
	Echocardiogram	$699 \pm 31$	$684 \pm 32$	$876 \pm 55$	$791 \pm 47$	$730 \pm 32$
	Heart disease	$418 \pm 20$	$442 \pm 21$	$514 \pm 42$	$404 \pm 20$	$431 \pm 24$
	Hepatitis	$546 \pm 29$	$551 \pm 30$	$640 \pm 55$	$579 \pm 48$	$513 \pm 34$
	Horse colic	$405 \pm 23$	$417 \pm 17$	$530 \pm 26$	$446 \pm 28$	$453 \pm 20$
	Labor	$582 \pm 51$	$542 \pm 44$	$484 \pm 64$	$403 \pm 54$	$534 \pm 50$
	Liver disease	$613 \pm 14$	$646 \pm 20$	$751 \pm 33$	$707 \pm 29$	$628 \pm 16$
	Promoters	$473 \pm 40$	$456 \pm 46$	$569 \pm 90$	$491 \pm 41$	$357 \pm 25$
	Sonar	$556 \pm 31$	$638 \pm 38$	$834 \pm 59$	$608 \pm 37$	$552 \pm 41$
	Voting	$76 \pm 6$	$79 \pm 6$	$86 \pm 9$	$92 \pm 6$	$73 \pm 6$
10	Breast cancer	$733 \pm 17$	$707 \pm 25$	$765 \pm 49$	$981 \pm 44$	$700 \pm 19$
	Credit	$412 \pm 14$	$403 \pm 21$	$514 \pm 35$	$427 \pm 22$	$400 \pm 16$
	Diabetes	$556 \pm 15$	$577 \pm 16$	$688 \pm 33$	$623 \pm 21$	$551 \pm 10$
	Echocardiogram	$664 \pm 15$	$678 \pm 17$	$986 \pm 92$	$884 \pm 53$	$670 \pm 15$
	Heart disease	$560 \pm 26$	$576 \pm 22$	$596 \pm 43$	$514 \pm 39$	$529 \pm 15$
	Hepatitis	$667 \pm 38$	$710 \pm 60$	$942 \pm 97$	$709 \pm 64$	$675 \pm 49$
	Horse colic	$643 \pm 14$	$615 \pm 18$	$730 \pm 37$	$585 \pm 53$	$596 \pm 13$
	Labor	$666 \pm 29$	$718 \pm 46$	$682 \pm 72$	$645 \pm 82$	$634 \pm 31$
	Liver disease	$580 \pm 13$	$628 \pm 30$	$847 \pm 48$	$673 \pm 30$	$580 \pm 13$
	Promoters	$531 \pm 91$	$429 \pm 19$	$686 \pm 91$	$573 \pm 58$	$446 \pm 13$
	Sonar	$540 \pm 26$	$590 \pm 29$	$947 \pm 88$	$617 \pm 53$	$490 \pm 20$
	Voting	$105 \pm 11$	$106 \pm 10$	$106 \pm 13$	$118 \pm 9$	$106 \pm 10$

Key takeaways from the lesion study:

Ensemble averaging is essential: Estimating probabilities with a single run (C4 Probs) yields significantly worse costs across almost all datasets.
Small resample counts suffice: Performance degrades only marginally from $m=50$ down to $m=10$ .
Probability estimates vs 0-1 voting: Using base-learner rule probabilities is moderately beneficial, but 0-1 vote counting still outperforms stratification and cost-blind C4.5R.
Out-of-bag vs All models: Differences between out-of-bag estimation ( $q=\text{False}$ ) and using all models ( $q=\text{True}$ ) are minor.

Knowl 8 — Scaling Up and Noise Robustness on the Space Shuttle Database

data/table

Evaluation on the NASA Shuttle database (43,500 training examples, 14,500 test examples, 7 classes, 9 numeric attributes) examined execution time and scalability. Costs were set to $C(i, i) = 0$ and $C(i, j) = 1000 P(i)/P(j)$ for $i \neq j$ . Tests were run on clean data and on data injected with $10\%$ uniform class noise.

Algorithm	No Noise		10% Noise
	Cost	Time	Cost	Time
C4.5R	$15.6$	1:41	$2591.2$	91:56
Undersampling	$15.9$	0:01	$232.5$	1:40
MetaCost ( $m=10, n=s/10$ )	$0.6$	1:44	$52.4$	4:18
MetaCost ( $m=10, n=s/100$ )	$0.7$	0:15	$53.2$	0:17
MetaCost ( $m=20, n=s$ )	$0.6$	2:43	–	–
MetaCost ( $m=20, n=s/10$ )	$0.6$	1:51	$52.5$	8:18
MetaCost ( $m=50, n=s$ )	$0.6$	28:49	–	–
MetaCost ( $m=50, n=s/10$ )	$0.6$	2:38	$52.5$	21:35

Note: Oversampling exceeded available memory in all runs; C4.5R under $10\%$ noise exceeded memory when running MetaCost with $n=s$ .

On clean data, MetaCost with small subsamples ( $m=10, n=s/10$ ) reduces total cost by over an order of magnitude ( $15.6 \to 0.6$ ) with run times comparable to baseline C4.5R. Under $10\%$ class noise, MetaCost with $m=10, n=s/100$ executes in 17 seconds (over $300\times$ faster than C4.5R's 91:56) while cutting misclassification cost from $2591.2$ to $53.2$ . This acceleration occurs because ensemble averaging filters out random label noise, generating a cleaner training set on which rule induction produces drastically simpler rule sets.

Knowl 9 — Computational and Structural Properties of MetaCost
theoretical result
MetaCost possesses three structural and computational properties:
1. Independence from Cost Matrix Updates: The ensemble generation and class probability estimation stages (Steps 1 and 2 of the algorithm) depend entirely on the training set $S$ and are completely independent of the cost matrix $C$ . If the cost matrix changes, only the relabeling and final model training stages need to be repeated, requiring exactly one run of the base learner $L$ .
2. Trivial Parallelization: Generating the $m$ resample models $M_1, \dots, M_m$ involves mutually independent executions of the learner $L$ . These runs can be distributed across $m$ processors, reducing the wall-clock overhead of the probability estimation stage to the cost of a single model induction.
3. Asymptotic Large-Sample Consistency: In the infinite-sample limit ( $|S| \to \infty$ ), if the base learning algorithm $L$ is statistically consistent under zero-one loss, training $L$ on a dataset relabeled according to the exact Bayes-optimal risk boundaries guarantees recovery of the true cost-minimizing decision frontiers.

Coverage note — None. All substantial contributions—including the MetaCost framework, Bayes risk relabeling formulation, algorithm specification, multiclass and binary benchmark evaluations, ablation lesion studies, and large-scale/noise scaling experiments on the Shuttle dataset—have been included.

References

1.D. W. Aha, D. Kibler, and M. K. Albert. Instance-based learning algorithms. Machine Learning, 6:37-66, 1991.
2.S. D. Bay. Combining nearest neighbor classifiers through multiple feature subsets. Proc. 17th Intl. Conf. on Machine Learning, pp. 37-45, Madison, WI, 1998.
3.C. M. Bishop. Neural Networks for Pattern Recognition. Oxford University Press, Oxford, UK, 1995.
4.C. Blake, E. Keogh, and C. J. Merz. UCI repository of machine learning databases. Dept. of Information and Computer Science, University of California at Irvine, CA, 1999. http://www.ics.uci.edu/~mlearn/MLRepository.html.
5.L. Breiman. Bagging predictors. Machine Learning, 24:123-140, 1996.
6.L. Breiman. Pasting bites together for prediction in large data sets and on-line. Technical report, Statistics Dept., University of California at Berkeley, CA, 1996.
7.L. Breiman. Out-of-bag estimation. Technical report, Statistics Dept., University of California at Berkeley, CA, 1998.
8.L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984.
9.P. Chan and S. Stolfo. Toward scalable learning with non-uniform class and cost distributions. Proc. 4th Intl. Conf. on Knowledge Discovery and Data Mining, pp. 164-168, New York, NY, 1998.
10.P. Chan, S. Stolfo, and D. Wolpert, editors. Proc. AAAI-96 Wkshp. on Integrating Multiple Learned Models for Improving and Scaling Machine Learning Algorithms. AAAI Press, Portland, OR, 1996.
11.B. W. Dasarathy, editor. Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. IEEE Computer Society Press, Los Alamitos, CA, 1991.
12.P. Domingos. Linear-time rule induction. Proc. 2nd Intl. Conf. on Knowledge Discovery and Data Mining, pp. 96-101, Portland, OR, 1996.
13.P. Domingos. Knowledge acquisition from examples via multiple models. Proc. 14th Intl. Conf. on Machine Learning, pp. 98-106, Nashville, TN, 1997.
14.P. Domingos. Why does bagging work? A Bayesian account and its implications. Proc. 3rd Intl. Conf. on Knowledge Discovery and Data Mining, pp. 155-158, Newport Beach, CA, 1997.
15.P. Domingos. How to get a free lunch: A simple cost model for machine learning applications. Proc. AAAI-98/ICML-98 Wkshp. on the Methodology of Applying Machine Learning, pp. 1-7, Madison, WI, 1998.
16.P. Domingos and M. Pazzani. On the optimality of the simple Bayesian classifier under zero-one loss. Machine Learning, 29:103-130, 1997.
17.R. O. Duda and P. E. Hart. Pattern Classification and Scene Analysis. Wiley, New York, NY, 1973.
18.U. Fayyad, G. Piatetsky-Shapiro, and P. Smyth. From data mining to knowledge discovery: An overview. In U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, pp. 1-34. AAAI Press, Menlo Park, CA, 1996.
19.Y. Freund and R. E. Schapire. Experiments with a new boosting algorithm. Proc. 13th Intl. Conf. on Machine Learning, pp. 148-156, Bari, Italy, 1996.
20.R. S. Michalski. A theory and methodology of inductive learning. Artificial Intelligence, 20:111-161, 1983.
21.F. Provost and T. Fawcett. Analysis and visualization of classifier performance. Proc. 3rd Intl. Conf. on Knowledge Discovery and Data Mining, pp. 43-48, Newport Beach, CA, 1997.
22.F. Provost, T. Fawcett, and R. Kohavi. The case against accuracy estimation for comparing induction algorithms. Proc. 15th Intl. Conf. on Machine Learning, pp. 445-453, Madison, WI, 1998.
23.J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo, CA, 1993.
24.K. M. Ting and Z. Zheng. Boosting trees for cost-sensitive classifications. Proc. 10th European Conf. on Machine Learning, pp. 191-195, Chemnitz, Germany, 1998.
25.P. Turney. Cost-sensitive learning bibliography. Online bibliography, Institute for Information Technology of the National Research Council of Canada, Ottawa, Canada, 1997. http://ai.iit.nrc.ca/bibliographies/cost-sensitive.html.
26.Z. Zheng. Naive Bayesian classifier committees. Proc. 10th European Conf. on Machine Learning, pp. 196-207, Chemnitz, Germany, 1998.

Citation

MLA

Domingos, P. “MetaCost”. Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1999, pp. 155–64, https://doi.org/10.1145/312129.312220.

APA

Domingos, P. (1999). MetaCost. Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 155–164. https://doi.org/10.1145/312129.312220

Chicago

Domingos, P. 1999. “MetaCost”. Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 155–64. https://doi.org/10.1145/312129.312220.

Harvard

Domingos, P. (1999) “MetaCost”, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp. 155–164. Available at: https://doi.org/10.1145/312129.312220.

Vancouver

1. Domingos P (1999) MetaCost. In: Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 155–164

BibTeX

@inproceedings{Domingos_1999, series={KDD99}, title={MetaCost: a general method for making classifiers cost-sensitive}, url={http://dx.doi.org/10.1145/312129.312220}, DOI={10.1145/312129.312220}, booktitle={Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher={ACM}, author={Domingos, Pedro}, year={1999}, month=Aug, pages={155–164}, collection={KDD99} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

MetaCost: a general method for making classifiers cost-sensitive

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — The MetaCost Framework for Cost-Sensitive Classification

Knowl 2 — Conditional Risk and Bayes Optimal Class Relabeling

Knowl 3 — The MetaCost Algorithm

Knowl 4 — Experimental Evaluation Setup for Cost-Sensitive Classifiers

Knowl 5 — Multiclass Cost Reduction Performance on Benchmark Datasets

Knowl 6 — Two-Class Cost Reduction Across Variable Cost Ratios

Knowl 7 — Ablation and Lesion Analysis of MetaCost Components

Knowl 8 — Scaling Up and Noise Robustness on the Space Shuttle Database

Knowl 9 — Computational and Structural Properties of MetaCost

References

Citation

BibTeX

Access the Paper