Beyond the ROC Curve: Classification Trees Using Cost-Optimal Curves, with Application to Imbalanced Datasets

Magzhan Gabidolla, Arman Zharmagambetov, Miguel Á. Carreira-Perpiñán

Introduction

In high-stakes fields like fraud detection, medical diagnosis, and churn prediction, datasets are often heavily imbalanced. In these scenarios, the "cost" of a false negative (e.g., missing a fraudulent transaction) is typically much higher than a false positive (e.g., flagging a legitimate user).

The standard industry tool for navigating this trade-off is the Receiver Operating Characteristic (ROC) curve. Typically, practitioners generate an ROC curve by training a single model for overall accuracy and then varying a classification threshold on its output probabilities. However, this paper argues that this post-processing approach is fundamentally suboptimal. A model trained purely for raw accuracy might ignore the minority class entirely during training. Simply shifting a threshold after the fact cannot recover the complex decision boundaries needed to truly optimize for specific cost ratios.

To address this, the authors introduce the Cost-Optimal Curve (COC) as a superior alternative to the standard ROC curve. By using a novel global optimization algorithm to directly minimize weighted 0/1 loss, they produce a family of decision trees that provably and experimentally dominate ROC-based classifiers.

Methodology

Rather than post-processing a single model, the authors propose training a sequence of models, each explicitly optimized for a specific cost level.

  1. The Cost-Optimal Curve (COC): The COC is defined as the set of classifiers that minimize the false negative rate for every possible maximum false positive rate. The authors prove that finding this curve is mathematically equivalent to minimizing a weighted 0/1 loss.
  2. Tree Alternating Optimization (TAO): Optimizing the "ideal" weighted 0/1 loss is notoriously difficult because it is NP-hard and non-differentiable. Most researchers rely on "easier" surrogate losses (like cross-entropy) or heuristic greedy algorithms (like CART). To solve the true 0/1 loss optimization, the authors adapt the TAO algorithm. Unlike standard decision tree algorithms that use greedy local splits, TAO optimizes a global loss function, iteratively updating decision nodes and leaves to monotonically decrease the total weighted error.
  3. Oblique Trees: The method focuses on oblique trees, where each node can use a linear combination of features (hyperplanes) rather than just a single feature. This makes them more powerful than traditional axis-aligned trees while remaining highly interpretable.
  4. Warm-Starting: To efficiently generate the entire COC, the algorithm "warm-starts" each new model using the parameters of the previous one along the cost path. This significantly speeds up the training of the model sequence.

Key Insights and Results

ROC Dominance

The COC is theoretically guaranteed to dominate the ROC curve. Because the COC optimizes the tree structure for each specific cost point, it will always find a classifier at least as good as—and usually better than—one found by just thresholding a fixed tree.

For decision trees, an ROC curve is essentially just a sequence of leaf prunings. As you change the threshold, you eventually just turn the tree into a constant predictor. In contrast, the COC allows the decision boundaries themselves to shift and rotate to better capture the minority class as costs change.

Theoretical comparison showing how optimizing for specific cost ratios (COC, red) yields a curve that strictly dominates standard thresholding (ROC, blue).

0/1 Loss vs. Surrogates

The paper demonstrates that optimizing the true weighted 0/1 loss yields better results than using differentiable surrogates like weighted cross-entropy. While surrogates are easier to compute, they often lead to "optimal" solutions that are far from the true cost-minimum.

Empirical results across multiple datasets demonstrating that the COC (red) outperforms both standard ROC curves (green) and surrogate-loss models (blue).

Empirical Performance

The researchers evaluated their approach on a wide array of benchmarks, including synthetic datasets (like a modified MNIST) and real-world imbalanced datasets (e.g., SensIT, Telco Churn, ULB Credit Card Fraud, and Email Spam).

  • Higher Accuracy: Across nearly all datasets, the TAO-optimized COC reached higher True Positive rates at lower False Positive rates compared to baselines like CART, C5.0, and OC1.
  • Stability: The COC produced much smoother and more stable curves than greedy methods, which often produce "jumpy" results because small changes in cost can lead to entirely different greedy splits.
  • Efficiency: While training multiple models is naturally slower than training one, the warm-starting strategy made the process highly practical. For example, training 14 models for the MNIST dataset took only about 150 seconds.
  • Multiclass Success: In multiclass scenarios, TAO achieved significantly lower cost-based error while using fewer leaves and shallower trees than baseline models.

Limitations and Future Work

While highly effective, generating a full COC still requires training multiple models. For extremely large-scale datasets or environments requiring real-time cost updates, this computational complexity might be a bottleneck. Additionally, the current work focuses on single classification trees. Extending this global optimization of weighted 0/1 loss to tree ensembles (like Random Forests or Gradient Boosted Trees) represents a promising and necessary next step for the field.

Summary updated

Abstract

Important applications such as fraud or spam detection or churn prediction involve binary classification problems where the datasets are imbalanced and the cost of false positives greatly differs from the cost of false negatives. We focus on classification trees, in particular oblique trees, which subsume both the traditional axis-aligned trees and logistic regression, but are more accurate than both while providing interpretable models. Rather than using ROC curves, we advocate a loss based on minimizing the false negatives subject to a maximum false positive rate, which we prove to be equivalent to minimizing a weighted 0/1 loss. This yields a curve of classifiers that provably dominates the ROC curve, but is hard to optimize due to the 0/1 loss. We give the first algorithm that can iteratively update the tree parameters globally so that the weighted 0/1 loss decreases monotonically. Experiments on various datasets with class imbalance or class costs show this indeed dominates ROC-based classifiers and significantly improves over previous approaches to learn trees based on weighted purity criteria or over- or undersampling.
BibTeX
@inproceedings{gabidolla2024beyond,
  author = {Magzhan Gabidolla and Arman Zharmagambetov and Miguel Á. Carreira-Perpiñán},
  title = {{Beyond the ROC Curve: Classification Trees Using Cost-Optimal Curves, with Application to Imbalanced Datasets}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=mXLcbRBA8v},
}
Figure