Abstract
An approach to finding an optimal solution for an important diagnostic problem is described. Examples are taken from laboratory medicine, where the problem can be stated as finding the best combination of tests for making a diagnosis. These tests are typically numerical with unknown decision thresholds. Because of uncertainty in classification, the solution is described in terms of maximizing measures of decision rule performance on a data base of cases, for example maximizing positive predictive value, subject to a constraint of a minimum sensitivity. The resultant rules are quite similar to classification production rules, and the procedures described should be valid for many knowledge acquisition and refinement tasks. The solution is found by a heuristic search procedure, and empirical results for several data bases and published studies are described.
Introduction
In clinical medicine, a single diagnostic test typically produces a continuous numerical result. To make a diagnosis, a physician must choose a "cutoff" value—a threshold above which a patient is considered "positive" for a condition. The challenge intensifies when combining multiple tests. Determining whether to use a conjunction (e.g., "Test A > X AND Test B > Y") or a disjunction (e.g., "Test A > X OR Test C > Z") leads to an explosion of possible logical combinations. Historically, these rules were crafted based on expert intuition. This paper proposes a formal optimization method that maximizes Positive Predictive Value (PPV)—the probability that a patient has the disease given a positive result—while maintaining a minimum required sensitivity.
Methodology
The authors frame the task as a search for an optimal logical expression in Disjunctive Normal Form (DNF). To handle the computational complexity of this search, they introduced several key techniques:
- Heuristic Cutoff Selection: Instead of testing every possible numerical value, the algorithm "zooms in" on "interesting boundaries"—points where the predictive value is locally at a maximum.
- Pruning Rules: Provably correct pruning strategies are implemented. For example, if an expression already has lower specificity than required, any further "OR" operations will only degrade performance, allowing that branch of the search to be abandoned.
- Heuristic Search: Rather than an exhaustive search, which is exponentially difficult and involves Bell numbers, the algorithm maintains a table of the most promising shorter expressions and combines them to form longer, more complex rules.
Datasets and Evaluation
The approach was evaluated on two primary datasets:
- Appendicitis Data: A dataset of 106 patients and 8 diagnostic tests (e.g., WBC count, CRP) originally published in 1983.
- Laboratory Medicine Database: A larger dataset of approximately 3,000 cases from routine health screenings, used to verify if the algorithm could "re-discover" known expert rules.
Key Results
The algorithmic approach consistently outperformed or matched human-derived rules:
- Superior Accuracy: On the appendicitis dataset, the algorithm found a 2-test rule with a 91% PPV, outperforming the 3-test rule previously published in medical literature (89% PPV).
- Computational Efficiency: The heuristic search found the optimal solution for the appendicitis data in just 3 minutes of CPU time, whereas an exhaustive search took 10 hours.
- Expert Validation: In the 3,000-case database, the algorithm successfully matched five different expert-derived rules that were known to have 100% sensitivity and 100% PPV.
Discussion
A key insight of this work is that simplicity is a feature. The authors intentionally restricted their search to small "chunks" of information and simple logical connectives (AND/OR) to ensure the resulting rules remained human-interpretable. This highlights a gap in medical literature: while doctors often use combination tests, the specific logical rules are rarely optimized.
Limitations and Future Work
- Overfitting: Fitting rules to existing data can lead to inaccuracies if the sample is unrepresentative. The authors suggest using jackknifing or "train and test" experiments to estimate future performance.
- Fixed Constraints: The current implementation requires a pre-defined maximum rule length.
- Prevalence Sensitivity: Predictive values are sensitive to disease prevalence, a factor that must be managed when applying these rules to different populations.
Conclusion
This 1987 study demonstrates that computers can algorithmically discover simpler, more accurate combinations of medical tests than those previously published by human experts. By treating diagnostic rule-finding as a heuristic search problem, the authors provided a robust framework for knowledge acquisition and refinement in clinical medicine.
Summary updated