Cost-Sensitive Decision Trees with Completion Time Requirements
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.
|Date of creation:||Sep 2010|
|Date of revision:|
|Contact details of provider:|| Postal: |
Web page: http://www.krannert.purdue.edu/programs/phd
More information through EDIRC
When requesting a correction, please mention this item's handle: RePEc:pur:prukra:1264. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Krannert PHD)
If references are entirely missing, you can add them using this form.