A Cost-Sensitive Decision Tree Learning Algorithm Based on a Multi-Armed Bandit Framework
Authors:
- 30 March 2016
- journal article
- research article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 60 (7) , 941-956
Abstract
This paper develops a new algorithm for inducing cost-sensitive decision trees that is inspired by the multi-armed bandit problem, in which a player in a casino has to decide which slot machine (bandit) from a selection of slot machines is likely to pay out the most. Game theory proposes a solution to this multi-armed bandit problem by using a process of exploration and exploitation in which reward is maximized. This paper utilizes these concepts to develop a new algorithm by viewing the rewards as a reduction in costs, and utilizing the exploration and exploitation techniques so that a compromise between decisions based on accuracy and decisions based on costs can be found. The algorithm employs the notion of lever pulls in the multi-armed bandit game to select the attributes during decision tree induction, using a look-ahead methodology to explore potential attributes and exploit the attributes which maximizes the reward. The new algorithm is evaluated on 15 datasets and compared with six well-known algorithms J48, EG2, MetaCost, AdaCostM1, ICET and ACT. The results obtained show that the new multi-armed-based algorithm can produce more cost-effective trees without compromising accuracy. The paper also includes a critical appraisal of the limitations of the new algorithm and proposes avenues for further research.Keywords
This publication has 36 references indexed in Scilit:
- A survey of cost-sensitive decision tree induction algorithmsACM Computing Surveys, 2013
- An empirical comparison of cost‐sensitive decision tree induction algorithmsExpert Systems, 2011
- Automatic model selection in cost-sensitive boostingInformation Fusion, 2003
- 10.1162/153244301753344605Applied Physics Letters, 2000
- Boosting trees for cost-sensitive classificationsLecture Notes in Computer Science, 1998
- STATLOG: COMPARISON OF CLASSIFICATION ALGORITHMS ON LARGE REAL-WORLD PROBLEMSApplied Artificial Intelligence, 1995
- Cost-sensitive learning of classification knowledge and its applications in roboticsMachine Learning, 1993
- The use of background knowledge in decision tree inductionMachine Learning, 1991
- Induction of decision treesMachine Learning, 1986
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952