Extremely fast decision tree

Chaitanya Manapragada, Geoffrey I. Webb, Mahsa Salehi

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of Hoeffding Anytime Tree'“Extremely Fast Decision Tree”, a minor modification to the MOA implementation of Hoeffding Tree'obtains significantly superior prequential accuracy on most of the largest classification datasets from the UCI repository. Hoeffding Anytime Tree produces the asymptotic batch tree in the limit, is naturally resilient to concept drift, and can be used as a higher accuracy replacement for Hoeffding Tree in most scenarios, at a small additional computational cost.

Original languageEnglish
Title of host publicationKDD' 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Subtitle of host publicationAugust 19-23, 2018, London, United Kingdom
EditorsChih-Jen Lin, Hui Xiong
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages1953-1962
Number of pages10
ISBN (Electronic)9781450355520
DOIs
Publication statusPublished - 2018
EventACM International Conference on Knowledge Discovery and Data Mining 2018 - London, United Kingdom
Duration: 19 Aug 201823 Aug 2018
Conference number: 24th
http://www.kdd.org/kdd2018/ (Conference website)

Conference

ConferenceACM International Conference on Knowledge Discovery and Data Mining 2018
Abbreviated titleSIGKDD 2018
CountryUnited Kingdom
CityLondon
Period19/08/1823/08/18
Internet address

Keywords

  • Classification
  • Decision Trees
  • Incremental Learning

Cite this

Manapragada, C., Webb, G. I., & Salehi, M. (2018). Extremely fast decision tree. In C-J. Lin, & H. Xiong (Eds.), KDD' 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining : August 19-23, 2018, London, United Kingdom (pp. 1953-1962). New York NY USA: Association for Computing Machinery (ACM). https://doi.org/10.1145/3219819.3220005
Manapragada, Chaitanya ; Webb, Geoffrey I. ; Salehi, Mahsa. / Extremely fast decision tree. KDD' 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining : August 19-23, 2018, London, United Kingdom . editor / Chih-Jen Lin ; Hui Xiong. New York NY USA : Association for Computing Machinery (ACM), 2018. pp. 1953-1962
@inproceedings{cd96d195059248c5ab7f0f7589b44d04,
title = "Extremely fast decision tree",
abstract = "We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of Hoeffding Anytime Tree'“Extremely Fast Decision Tree”, a minor modification to the MOA implementation of Hoeffding Tree'obtains significantly superior prequential accuracy on most of the largest classification datasets from the UCI repository. Hoeffding Anytime Tree produces the asymptotic batch tree in the limit, is naturally resilient to concept drift, and can be used as a higher accuracy replacement for Hoeffding Tree in most scenarios, at a small additional computational cost.",
keywords = "Classification, Decision Trees, Incremental Learning",
author = "Chaitanya Manapragada and Webb, {Geoffrey I.} and Mahsa Salehi",
year = "2018",
doi = "10.1145/3219819.3220005",
language = "English",
pages = "1953--1962",
editor = "Lin, {Chih-Jen } and Xiong, {Hui }",
booktitle = "KDD' 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",
publisher = "Association for Computing Machinery (ACM)",
address = "United States of America",

}

Manapragada, C, Webb, GI & Salehi, M 2018, Extremely fast decision tree. in C-J Lin & H Xiong (eds), KDD' 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining : August 19-23, 2018, London, United Kingdom . Association for Computing Machinery (ACM), New York NY USA, pp. 1953-1962, ACM International Conference on Knowledge Discovery and Data Mining 2018, London, United Kingdom, 19/08/18. https://doi.org/10.1145/3219819.3220005

Extremely fast decision tree. / Manapragada, Chaitanya; Webb, Geoffrey I.; Salehi, Mahsa.

KDD' 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining : August 19-23, 2018, London, United Kingdom . ed. / Chih-Jen Lin; Hui Xiong. New York NY USA : Association for Computing Machinery (ACM), 2018. p. 1953-1962.

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - Extremely fast decision tree

AU - Manapragada, Chaitanya

AU - Webb, Geoffrey I.

AU - Salehi, Mahsa

PY - 2018

Y1 - 2018

N2 - We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of Hoeffding Anytime Tree'“Extremely Fast Decision Tree”, a minor modification to the MOA implementation of Hoeffding Tree'obtains significantly superior prequential accuracy on most of the largest classification datasets from the UCI repository. Hoeffding Anytime Tree produces the asymptotic batch tree in the limit, is naturally resilient to concept drift, and can be used as a higher accuracy replacement for Hoeffding Tree in most scenarios, at a small additional computational cost.

AB - We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of Hoeffding Anytime Tree'“Extremely Fast Decision Tree”, a minor modification to the MOA implementation of Hoeffding Tree'obtains significantly superior prequential accuracy on most of the largest classification datasets from the UCI repository. Hoeffding Anytime Tree produces the asymptotic batch tree in the limit, is naturally resilient to concept drift, and can be used as a higher accuracy replacement for Hoeffding Tree in most scenarios, at a small additional computational cost.

KW - Classification

KW - Decision Trees

KW - Incremental Learning

UR - http://www.scopus.com/inward/record.url?scp=85051459443&partnerID=8YFLogxK

U2 - 10.1145/3219819.3220005

DO - 10.1145/3219819.3220005

M3 - Conference Paper

SP - 1953

EP - 1962

BT - KDD' 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

A2 - Lin, Chih-Jen

A2 - Xiong, Hui

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

ER -

Manapragada C, Webb GI, Salehi M. Extremely fast decision tree. In Lin C-J, Xiong H, editors, KDD' 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining : August 19-23, 2018, London, United Kingdom . New York NY USA: Association for Computing Machinery (ACM). 2018. p. 1953-1962 https://doi.org/10.1145/3219819.3220005