Skip to the content

Cost-sensitive decision tree learning using a multi-armed bandit framework

Lomax, SE 2013, Cost-sensitive decision tree learning using a multi-armed bandit framework , PhD thesis, University of Salford.

[img]
Preview
PDF (Thesis) - Submitted Version
Download (1MB) | Preview
[img] Microsoft Word (Appendix Item D1) - Supplemental Material
Download (146kB)
[img] Microsoft Excel (Appendix Item D1) - Supplemental Material
Download (53kB)
[img] Microsoft Word (Appendix Item D2) - Supplemental Material
Download (191kB)
[img] Microsoft Excel (Appendix Item D2) - Supplemental Material
Download (39kB)
[img] Microsoft Word (Appendix Item D3) - Supplemental Material
Download (206kB)
[img] Microsoft Excel (Appendix Item D3) - Supplemental Material
Download (38kB)
[img] Microsoft Excel (Appendix Item D3) - Supplemental Material
Download (49kB)
[img] Microsoft Word (Appendix Item D4) - Supplemental Material
Download (968kB)
[img] Microsoft Excel (Appendix Item D4) - Supplemental Material
Download (161kB)
[img] Microsoft Word (Appendix Item D5) - Supplemental Material
Download (293kB)
[img] Microsoft Word (Appendix Item D6) - Supplemental Material
Download (274kB)
[img] Microsoft Excel (Appendix Item D7) - Supplemental Material
Download (66kB)
[img] Microsoft Excel (Appendix Item D8) - Supplemental Material
Download (61kB)
[img] Microsoft Excel (Appendix Item D9 (CSV file of results)) - Supplemental Material
Download (41MB)

Abstract

Decision tree learning is one of the main methods of learning from data. It has been applied to a variety of different domains over the past three decades. In the real world, accuracy is not enough; there are costs involved, those of obtaining the data and those when classification errors occur. A comprehensive survey of cost-sensitive decision tree learning has identified over 50 algorithms, developing a taxonomy in order to classify the algorithms by the way in which cost has been incorporated, and a recent comparison shows that many cost-sensitive algorithms can process balanced, two class datasets well, but produce lower accuracy rates in order to achieve lower costs when the dataset is less balanced or has multiple classes. This thesis develops a new framework and algorithm concentrating on the view that cost-sensitive decision tree learning involves a trade-off between costs and accuracy. Decisions arising from these two viewpoints can often be incompatible resulting in the reduction of the accuracy rates. The new framework builds on a specific Game Theory problem known as the multi-armed bandit. This problem concerns a scenario whereby exploration and exploitation are required to solve it. For example, 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 of this problem which is solved by a process of exploration and exploitation in which reward is maximized. This thesis utilizes these concepts from the multi-armed bandit game to develop a new algorithm by viewing the rewards as a reduction in costs, 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 adapted 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 thesis also includes a critical appraisal of the limitations of the developed algorithm and proposes avenues for further research.

Item Type: Thesis (PhD)
Contributors: Vadera, S (Supervisor)
Themes: Subjects outside of the University Themes
Schools: Schools > School of Computing, Science and Engineering
Schools > School of Computing, Science and Engineering > Salford Innovation Research Centre (SIRC)
Funders: Graduate Teaching Assistantship Programme
Depositing User: SE Lomax
Date Deposited: 16 Jul 2013 11:35
Last Modified: 30 Nov 2015 23:54
URI: http://usir.salford.ac.uk/id/eprint/29308

Actions (login required)

Edit record (repository staff only) Edit record (repository staff only)

Downloads

Downloads per month over past year