Cost-Sensitive Classification: Empirical Evaluation of a Hybrid Genetic Decision Tree Induction Algorithm

Peter D. Turney (peter@ai.iit.nrc.ca)

Abstract

This paper introduces ICET, a new algorithm for cost-sensitive classification. ICET uses a genetic algorithm to evolve a population of biases for a decision tree induction algorithm. The fitness function of the genetic algorithm is the average cost of classification when using the decision tree, including both the costs of tests (features, measurements) and the costs of classification errors. ICET is compared here with three other algorithms for cost-sensitive classification -- EG2, CS-ID3, and IDX -- and also with C4.5, which classifies without regard to cost. The five algorithms are evaluated empirically on five real-world medical datasets. Three sets of experiments are performed. The first set examines the baseline performance of the five algorithms on the five datasets and establishes that ICET performs significantly better than its competitors. The second set tests the robustness of ICET under a variety of conditions and shows that ICET maintains its advantage. The third set looks at ICET's search in bias space and discovers a way to improve the search.

Table of Contents

• 1. Introduction
• 2. Cost-Sensitive Classification
  • 2.1 Decision Trees and Cost-Sensitive Classification
  • 2.2 Calculating the Average Cost of Classification
  • 2.3 Cost and Accuracy
• 3. Algorithms
  • 3.1 C4.5
  • 3.2 EG2
  • 3.3 CS-ID3
  • 3.4 IDX
  • 3.5 ICET
• 4. Experiments
  • 4.1 Baseline Performance
    • 4.1.1 Average Cost of Classification
    • 4.1.2 Test Expenditures and Error Rates as Functions of the Penalty for Errors
    • 4.1.3 Execution Time
  • 4.2 Robustness of ICET
    • 4.2.1 All Tests Immediate
    • 4.2.2 No Group Discounts
    • 4.2.3 Complex Classification Cost Matrices
    • 4.2.4 Poorly Estimated Classification Cost
  • 4.3 Searching Bias Space
    • 4.3.1 Crossover Versus Mutation
    • 4.3.2 Search in Binary Space
    • 4.3.3 Seeded Population
• 5. Discussion
  • 5.1 Related Work
  • 5.2 Future Work
• 6. Conclusions
• Appendix A. Five Medical Datasets
  • A.1 BUPA Liver Disorders
  • A.2 Heart Disease
  • A.3 Hepatitis Prognosis
  • A.4 Pima Indians Diabetes
  • A.5 Thyroid Disease
• Acknowledgments
• References
• About this document...