SPAARC: A fast decision tree algorithm

Darren Yates; Zahid Islam; Junbin Gao

doi:10.1007/978-981-13-6661-1_4

SPAARC: A fast decision tree algorithm

Darren Yates, Zahid Islam, Junbin Gao

The University of Sydney

Research output: Book chapter/Published conference paper › Conference paper › peer-review

7 Citations (Scopus)

Abstract

Decision trees are a popular method of data-mining and knowledge discovery, capable of extracting hidden information from datasets consisting of both nominal and numerical attributes. However, their need to test the suitability of every attribute at every tree node, in addition to testing every possible split-point for every numerical attribute can be expensive computationally, particularly for datasets with high dimensionality. This paper proposes a method for speeding up the decision tree induction process called SPAARC, consisting of two components to address these issues – sampling of the numeric attribute tree-node split-points and dynamically adjusting the node attribute selection space. Further, these methods can be applied to almost any decision tree algorithm. To confirm its validity, SPAARC has been tested and compared against an implementation of the CART algorithm using 18 freely-available datasets from the UCI data repository. Results from this testing indicate the two components of SPAARC combined have minimal effect on decision tree classification accuracy yet reduce model build times by as much as 69%.

Original language	English
Title of host publication	Data mining
Subtitle of host publication	16th Australasian conference, AusDM 2018, revised selected papers
Editors	Rafiqul Islam, Yun Sing Koh, Yanchang Zhao, Graco Warwick, David Stirling, Chang-Tsun Li, Zahidul Islam
Place of Publication	Singapore
Publisher	Springer
Pages	43-55
Number of pages	13
Volume	996
ISBN (Electronic)	9789811366611
ISBN (Print)	9789811366604
DOIs	https://doi.org/10.1007/978-981-13-6661-1_4
Publication status	Published - 2019
Event	16th Australasian Data Mining Conference (AusDM 2018) - Charles Sturt University, Bathurst, Australia Duration: 28 Nov 2018 → 30 Nov 2018 https://web.archive.org/web/20181122224709/https://ausdm18.ausdm.org/ (Conference website) https://www.springer.com/us/book/9789811366604 (link to conf proceedings book)

Publication series

Name	Communications in Computer and Information Science
Publisher	Springer
Volume	996
ISSN (Print)	1865-0929
ISSN (Electronic)	1865-0937

Conference

Conference	16th Australasian Data Mining Conference (AusDM 2018)
Country/Territory	Australia
City	Bathurst
Period	28/11/18 → 30/11/18
Other	The Australasian Data Mining Conference (AusDM) has established itself as the premier Australasian meeting for both practitioners and researchers in data mining. It is devoted to the art and science of intelligent analysis of (usually big) data sets for meaningful (and previously unknown) insights. This conference will enable the sharing and learning of research and progress in the local context and new breakthroughs in data mining algorithms and their applications across all industries.
Internet address	https://web.archive.org/web/20181122224709/https://ausdm18.ausdm.org/ (Conference website) https://www.springer.com/us/book/9789811366604 (link to conf proceedings book)

Access to Document

10.1007/978-981-13-6661-1_4

Cite this

Yates, D., Islam, Z., & Gao, J. (2019). SPAARC: A fast decision tree algorithm. In R. Islam, Y. S. Koh, Y. Zhao, G. Warwick, D. Stirling, C.-T. Li, & Z. Islam (Eds.), Data mining: 16th Australasian conference, AusDM 2018, revised selected papers (Vol. 996, pp. 43-55). Article 77 (Communications in Computer and Information Science ; Vol. 996). Springer. https://doi.org/10.1007/978-981-13-6661-1_4

Yates, Darren ; Islam, Zahid ; Gao, Junbin. / SPAARC : A fast decision tree algorithm. Data mining: 16th Australasian conference, AusDM 2018, revised selected papers . editor / Rafiqul Islam ; Yun Sing Koh ; Yanchang Zhao ; Graco Warwick ; David Stirling ; Chang-Tsun Li ; Zahidul Islam. Vol. 996 Singapore : Springer, 2019. pp. 43-55 (Communications in Computer and Information Science ).

@inproceedings{d5125b43d91a421fa2611e9e169eb23f,

title = "SPAARC: A fast decision tree algorithm",

abstract = "Decision trees are a popular method of data-mining and knowledge discovery, capable of extracting hidden information from datasets consisting of both nominal and numerical attributes. However, their need to test the suitability of every attribute at every tree node, in addition to testing every possible split-point for every numerical attribute can be expensive computationally, particularly for datasets with high dimensionality. This paper proposes a method for speeding up the decision tree induction process called SPAARC, consisting of two components to address these issues – sampling of the numeric attribute tree-node split-points and dynamically adjusting the node attribute selection space. Further, these methods can be applied to almost any decision tree algorithm. To confirm its validity, SPAARC has been tested and compared against an implementation of the CART algorithm using 18 freely-available datasets from the UCI data repository. Results from this testing indicate the two components of SPAARC combined have minimal effect on decision tree classification accuracy yet reduce model build times by as much as 69%.",

keywords = "Decision tree, Processing speed, Classification accuracy, Note attribute sampling",

author = "Darren Yates and Zahid Islam and Junbin Gao",

note = "Includes bibliographical references.; 16th Australasian Data Mining Conference (AusDM 2018) ; Conference date: 28-11-2018 Through 30-11-2018",

year = "2019",

doi = "10.1007/978-981-13-6661-1_4",

language = "English",

isbn = "9789811366604 ",

volume = "996",

series = "Communications in Computer and Information Science ",

publisher = "Springer",

pages = "43--55",

editor = "Rafiqul Islam and Koh, {Yun Sing} and Yanchang Zhao and Graco Warwick and David Stirling and Chang-Tsun Li and Zahidul Islam",

booktitle = "Data mining",

address = "United States",

url = "https://web.archive.org/web/20181122224709/https://ausdm18.ausdm.org/, https://www.springer.com/us/book/9789811366604",

}

Yates, D , Islam, Z & Gao, J 2019, SPAARC: A fast decision tree algorithm. in R Islam, YS Koh, Y Zhao, G Warwick, D Stirling, C-T Li & Z Islam (eds), Data mining: 16th Australasian conference, AusDM 2018, revised selected papers . vol. 996, 77, Communications in Computer and Information Science , vol. 996, Springer, Singapore, pp. 43-55, 16th Australasian Data Mining Conference (AusDM 2018), Bathurst, New South Wales, Australia, 28/11/18. https://doi.org/10.1007/978-981-13-6661-1_4

SPAARC: A fast decision tree algorithm. / Yates, Darren ; Islam, Zahid; Gao, Junbin.
Data mining: 16th Australasian conference, AusDM 2018, revised selected papers . ed. / Rafiqul Islam; Yun Sing Koh; Yanchang Zhao; Graco Warwick; David Stirling; Chang-Tsun Li; Zahidul Islam. Vol. 996 Singapore: Springer, 2019. p. 43-55 77 (Communications in Computer and Information Science ; Vol. 996).

Research output: Book chapter/Published conference paper › Conference paper › peer-review

TY - GEN

T1 - SPAARC

T2 - 16th Australasian Data Mining Conference (AusDM 2018)

AU - Yates, Darren

AU - Islam, Zahid

AU - Gao, Junbin

N1 - Includes bibliographical references.

PY - 2019

Y1 - 2019

N2 - Decision trees are a popular method of data-mining and knowledge discovery, capable of extracting hidden information from datasets consisting of both nominal and numerical attributes. However, their need to test the suitability of every attribute at every tree node, in addition to testing every possible split-point for every numerical attribute can be expensive computationally, particularly for datasets with high dimensionality. This paper proposes a method for speeding up the decision tree induction process called SPAARC, consisting of two components to address these issues – sampling of the numeric attribute tree-node split-points and dynamically adjusting the node attribute selection space. Further, these methods can be applied to almost any decision tree algorithm. To confirm its validity, SPAARC has been tested and compared against an implementation of the CART algorithm using 18 freely-available datasets from the UCI data repository. Results from this testing indicate the two components of SPAARC combined have minimal effect on decision tree classification accuracy yet reduce model build times by as much as 69%.

AB - Decision trees are a popular method of data-mining and knowledge discovery, capable of extracting hidden information from datasets consisting of both nominal and numerical attributes. However, their need to test the suitability of every attribute at every tree node, in addition to testing every possible split-point for every numerical attribute can be expensive computationally, particularly for datasets with high dimensionality. This paper proposes a method for speeding up the decision tree induction process called SPAARC, consisting of two components to address these issues – sampling of the numeric attribute tree-node split-points and dynamically adjusting the node attribute selection space. Further, these methods can be applied to almost any decision tree algorithm. To confirm its validity, SPAARC has been tested and compared against an implementation of the CART algorithm using 18 freely-available datasets from the UCI data repository. Results from this testing indicate the two components of SPAARC combined have minimal effect on decision tree classification accuracy yet reduce model build times by as much as 69%.

KW - Decision tree

KW - Processing speed

KW - Classification accuracy

KW - Note attribute sampling

U2 - 10.1007/978-981-13-6661-1_4

DO - 10.1007/978-981-13-6661-1_4

M3 - Conference paper

SN - 9789811366604

VL - 996

T3 - Communications in Computer and Information Science

SP - 43

EP - 55

BT - Data mining

A2 - Islam, Rafiqul

A2 - Koh, Yun Sing

A2 - Zhao, Yanchang

A2 - Warwick, Graco

A2 - Stirling, David

A2 - Li, Chang-Tsun

A2 - Islam, Zahidul

PB - Springer

CY - Singapore

Y2 - 28 November 2018 through 30 November 2018

ER -

SPAARC: A fast decision tree algorithm

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this