A cost-sensitive decision tree learning algorithm based on a multi-armed bandit framework

Lomax, S; Vadera, S

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 fifteen datasets and compared to 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.

Citation

Lomax, S., & Vadera, S. (2017). A cost-sensitive decision tree learning algorithm based on a multi-armed bandit framework. Computer Journal, 60(7), 941-956. https://doi.org/10.1093/comjnl/bxw015

• Journal Article Type: Article
• Acceptance Date: Mar 1, 2016
• Online Publication Date: Mar 30, 2016
• Publication Date: Jul 1, 2017
• Deposit Date: Mar 14, 2016
• Publicly Available Date: Mar 30, 2018
• Journal: The Computer Journal
• Print ISSN: 0010-4620
• Electronic ISSN: 1460-2067
• Publisher: Oxford University Press
• Volume: 60
• Issue: 7
• Pages: 941-956
• DOI: https://doi.org/10.1093/comjnl/bxw015
• Publisher URL: http://dx.doi.org/10.1093/comjnl/bxw015
• Related Public URLs: http://www.oxfordjournals.org/our_journals/computer_journal/about.html