Feature value acquisition in testing: a sequential batch test algorithm

ABSTRACT

In medical diagnosis, doctors often have to order sets of medical tests in sequence in order to make an accurate diagnosis of patient diseases. While doing so they have to make a trade-off between the cost of the tests and possible misdiagnosis. In this paper, we use cost-sensitive learning to model this process. We assume that test examples (new patients) may contain missing values, and their actual values can be acquired at cost (similar to doing medical tests) in order to reduce misclassification errors (misdiagnosis). We propose a novel Sequential Batch Test algorithm that can acquire sets of attribute values in sequence, similar to sets of medical tests ordered by doctors in sequence. The goal of our algorithm is to minimize the total cost (i.e., the trade-off) of acquiring attribute values and misclassifications. We demonstrate the effectiveness of our algorithm, and show that it outperforms previous methods significantly. Our algorithm can be readily applied in real-world diagnosis tasks. A case study on the heart disease is given in the paper.

REFERENCES

• 1: Blake, C. L. and Merz, C. J. 1998. UCI Repository of machine learning databases (website). Irvine, CA: University of California, Department of Information and Computer Science.
• 2: Xiaoyong Chai , Lin Deng , Qiang Yang , Charles X. Ling, Test-Cost Sensitive Naive Bayes Classification, Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04), p.51-58, November 01-04, 2004
• 3: Cohn, D., Ghahramani, Z., and Jordan, M. 1996. Active learning with statistical models. Journal of Artificial Intelligence Research, 4: 129--145.
• 4: Pedro Domingos, MetaCost: a general method for making classifiers cost-sensitive, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.155-164, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312220]
• 5: Elkan, C. 2001. The Foundations of Cost-Sensitive Learning. In Proceedings of the Seventeenth International Joint Conference of Artificial Intelligence, 973--978. Seattle, Washington: Morgan Kaufmann.
• 6: Fayyad, U. M. and Irani, K. B. 1993. Multi-interval discretization of continuous-valued attributes for classification learning. In Proceedings of the 13th International Joint Conference on Artificial Intelligence, 1022--1027. France: Morgan Kaufmann.
• 7: Friedman, J., Yun, Y., and Kohavi, R. 1996. Lazy Decision Trees. In proceedings of 13th National Conference Artificial Intelligence.
• 8: Gorry, G. and Barnett, G., 1968. "Experience with a model of sequential diagnosis", Computers and Biomedical Research.
• 9: Russell Greiner , Adam J. Grove , Dan Roth, Learning cost-sensitive active classifiers, Artificial Intelligence, v.139 n.2, p.137-174, August 2002 [doi>10.1016/S0004-3702(02)00209-6]
• 10: Charles X. Ling , Qiang Yang , Jianning Wang , Shichao Zhang, Decision trees with minimal costs, Proceedings of the twenty-first international conference on Machine learning, p.69, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015369]
• 11: Lizotte, D., Madani, O., and Greiner R. 2003. Budgeted Learning of Naïve-Bayes Classifiers. In Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence. Acapulco, Mexico: Morgan Kaufmann.
• 12: Prem Melville , Maytal Saar-Tsechansky , Foster Provost , Raymond Mooney, Active Feature-Value Acquisition for Classifier Induction, Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04), p.483-486, November 01-04, 2004
• 13: Prem Melville , Foster Provost , Maytal Saar-Tsechansky , Raymond Mooney, Economical active feature-value acquisition through Expected Utility estimation, Proceedings of the 1st international workshop on Utility-based data mining, p.10-16, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1089827.1089828]
• 14: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 15: Marlon Núñez, The Use of Background Knowledge in Decision Tree Induction, Machine Learning, v.6 n.3, p.231-250, May 1991 [doi>10.1023/A:1022609710832]
• 16: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 17: Maytal Saar-Tsechansky , Foster Provost, Active Sampling for Class Probability Estimation and Ranking, Machine Learning, v.54 n.2, p.153-178, February 2004 [doi>10.1023/B:MACH.0000011806.12374.c3]
• 18: Ming Tan, Cost-Sensitive Learning of Classification Knowledge and Its Applications in Robotics, Machine Learning, v.13 n.1, p.7-33, Oct. 1993 [doi>10.1023/A:1022679428250]
• 19: Kai Ming Ting, Inducing Cost-Sensitive Trees via Instance Weighting, Proceedings of the Second European Symposium on Principles of Data Mining and Knowledge Discovery, p.139-147, September 23-26, 1998
• 20: Turney, P. D. 1995. Cost-Sensitive Classification: Empirical Evaluation of a Hybrid Genetic Decision Tree Induction Algorithm. Journal of Artificial Intelligence Research 2:369--409.
• 21: Turney, P. D. 2000. Types of cost in inductive concept learning. In Proceedings of the Workshop on Cost-Sensitive Learning at the Seventeenth International Conference on Machine Learning, Stanford University, California.
• 22: Bianca Zadrozny , Charles Elkan, Learning and making decisions when costs and probabilities are both unknown, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.204-213, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502540]
• 23: Valentina Bayer Zubek , Thomas G. Dietterich, Pruning Improves Heuristic Search for Cost-Sensitive Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.19-26, July 08-12, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms