Cost-Sensitive Decision Trees with Completion Time Requirements

Hung-Pin Kao, Kwei Tang and Jen Tang

Purdue University Economics Working Papers from Purdue University, Department of Economics

Abstract: In many classification tasks, managing costs and completion times are the main concerns. In this paper, we assume that the completion time for classifying an instance is determined by its class label, and that a late penalty cost is incurred if the deadline is not met. This time requirement enriches the classification problem but posts a challenge to developing a solution algorithm. We propose an innovative approach for the decision tree induction, which produces multiple candidate trees by allowing more than one splitting attribute at each node. The user can specify the maximum number of candidate trees to control the computational efforts required to produce the final solution. In the tree-induction process, an allocation scheme is used to dynamically distribute the given number of candidate trees to splitting attributes according to their estimated contributions to cost reduction. The algorithm finds the final tree by backtracking. An extensive experiment shows that the algorithm outperforms the top-down heuristic and can effectively obtain the optimal or near-optimal decision trees without an excessive computation time.

Keywords: classification; decision tree; cost and time sensitive learning; late penalty (search for similar items in EconPapers)
Pages: 14 pages
Date: 2010-09
New Economics Papers: this item is included in nep-cmp
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://business.purdue.edu/research/Working-papers-series/2010/1264.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pur:prukra:1264

Access Statistics for this paper

More papers in Purdue University Economics Working Papers from Purdue University, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Business PHD ().