ACE-Cost: Acquisition Cost Efficient Classifier by Hybrid Decision Tree with Local SVM Leaves

摘要

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, Ace-Cost, 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%.