Cost-Sensitive Test Strategies

Shengli Sheng, Charles X. Ling, Ailing Ni, Shichao ZhangAAAI 2006

Abstract

In high-stakes domains such as clinical medicine, data acquisition is rarely free. Every diagnostic test—from simple blood work to complex imaging—carries a financial cost and potential risk. This paper introduces a novel framework for machine learning that treats feature acquisition as a financial optimization problem. By utilizing cost-sensitive decision trees and three distinct testing strategies (Sequential, Single Batch, and Multiple Batch), the authors demonstrate how to minimize the "total cost," which encompasses both the price of medical attributes and the potential economic burden of misdiagnosis.

Introduction

Traditional machine learning models typically assume that all features for a test case are readily available at no cost. However, in fields like medicine or credit scoring, "features" are actually results of expensive procedures. The core challenge is a classic optimization trade-off: ordering every possible test ensures high diagnostic accuracy but may bankrupt the patient or system, while ordering no tests saves immediate funds but risks catastrophic misclassification costs. This research addresses the "test strategy" problem—determining which tests to order and in what sequence to minimize the combined cost of attributes and errors.

Methodology

The researchers developed a framework centered on cost-sensitive decision trees, introducing three primary innovations to the standard model-building process.

1. Cost-Reduction Splitting

Unlike standard decision trees that use Information Gain or Entropy, this model employs a "total cost reduction" metric. A split is only executed if the financial cost of the attribute is lower than the expected reduction in misclassification costs it provides. This ensures that every data point gathered has a positive expected return on investment.

2. Group Discounts

In clinical settings, performing multiple tests simultaneously often results in lower costs (e.g., extracting multiple values from a single blood draw). The authors integrated a discount mechanism into the tree-building process, incentivizing the model to group related tests together.

Figure 3: Comparison of cost-sensitive decision trees for heart disease diagnosis with and without group discounts. Note how low-cost attributes like 'cp' ($1) and 'sex' ($1) are prioritized at the top of the tree.

3. Three Test Strategies

To accommodate different clinical needs, the paper evaluates three strategies:

  • Sequential Test: Requests one test at a time, waits for the result, and then decides the next step. This is the most cost-efficient but time-intensive.
  • Single Batch Test: Requests a predetermined set of tests all at once. This is faster for the patient but involves "guesswork," as some tests may prove redundant.
  • Multiple Batch Test: A hybrid approach that requests tests in several rounds. It introduces a "Batch Cost" (overhead for each round) and uses a Return on Investment (ROI) heuristic to decide which tests are worth including in a given batch.

Experimental Evaluation

The approach was tested on 13 real-world datasets from the UCI Machine Learning Repository, including a primary case study on Heart Disease (Heart-D) using actual costs from the Ontario Health Insurance Program. The researchers also created imbalanced variants of the Thyroid and Kr-vs-kp datasets to simulate rare but critical medical conditions.

Figure 4: Total cost performance of Sequential, Single Batch, and Multiple Batch strategies across varying ratios of unknown attributes.

Key Findings

  • The Efficiency of Sequentialism: The Sequential Test consistently emerged as the optimal strategy for cost minimization because it avoids redundant data acquisition. However, its time-intensive nature makes it less suitable for emergency scenarios.
  • Superiority over Naive Bayes: The proposed tree-based strategies significantly outperformed previous state-of-the-art methods, such as Cost-Sensitive Naive Bayes, across all datasets. Furthermore, the tree-based approach was 60 to 300 times faster computationally.
  • Cost-Driven Hierarchy: In the Heart-D study, the model correctly prioritized inexpensive tests (age and sex) at the root of the tree, only resorting to expensive tests (like 'thal', costing ~$100) when cheaper data proved inconclusive.
  • Batch Cost Dynamics: Experiments demonstrated that as the "Batch Cost" (the penalty for waiting) increases, the Multiple Batch strategy naturally adapts to resemble the Single Batch strategy, proving the flexibility of the ROI heuristic.

Conclusion

This research provides a robust, computationally efficient framework for decision-making under financial constraints. By treating information gathering as a financial portfolio, the model successfully balances the need for accuracy with the reality of limited resources. Future work will focus on collaborating with medical professionals to integrate more complex clinical data and explore non-financial "risk" factors within the model.

Summary updated

BibTeX
@inproceedings{sheng2006cost,
  author = {Shengli Sheng and Charles X. Ling and Ailing Ni and Shichao Zhang},
  title = {{Cost-Sensitive Test Strategies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure