ACE-Cost: Acquisition cost efficient classifier by hybrid decision tree with local SVM leaves

Liyun Li, Umut Topkara, Nasir Memon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The standard prediction process of SVM requires acquisition of all the feature values for every instance. In practice, however, a cost is associated with the mere act of acquisition of a feature, e.g. CPU time needed to compute the feature out of raw data, the dollar amount spent for gleaning more information, or the patient wellness sacrificed by an invasive medical test, etc. In such applications, a budget constrains the classification process from using all of the features. We present, AceCost, a novel classification method that reduces the expected test cost of SVM without compromising from the classification accuracy. Our algorithm uses a cost efficient decision tree to partition the feature space for obtaining coarse decision boundaries, and local SVM classifiers at the leaves of the tree to refine them. The resulting classifiers are also effective in scenarios where several features share overlapping acquisition procedures, hence the cost of acquiring them as a group is less than the sum of the individual acquisition costs. Our experiments on the standard UCI datasets, a network flow detection application, as well as on synthetic datasets show that, the proposed approach achieves classification accuracy of SVM while reducing the test cost by 40%-80%.

Original languageEnglish (US)
Title of host publicationMachine Learning and Data Mining in Pattern Recognition - 7th International Conference, MLDM 2011, Proceedings
Pages60-74
Number of pages15
DOIs
StatePublished - 2011
Event7th International Conference on Machine Learning and Data Mining, MLDM 2011 - New York, NY, United States
Duration: Aug 30 2011Sep 3 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6871 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th International Conference on Machine Learning and Data Mining, MLDM 2011
CountryUnited States
CityNew York, NY
Period8/30/119/3/11

Keywords

  • Cost Efficient Classification
  • Decision Tree
  • Postpruning
  • SVM

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'ACE-Cost: Acquisition cost efficient classifier by hybrid decision tree with local SVM leaves'. Together they form a unique fingerprint.

  • Cite this

    Li, L., Topkara, U., & Memon, N. (2011). ACE-Cost: Acquisition cost efficient classifier by hybrid decision tree with local SVM leaves. In Machine Learning and Data Mining in Pattern Recognition - 7th International Conference, MLDM 2011, Proceedings (pp. 60-74). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6871 LNAI). https://doi.org/10.1007/978-3-642-23199-5_5