Parallel construction of classification trees on a GPU
Authors:
- 31 October 2015
- journal article
- research article
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 28 (5) , 1417-1436
Abstract
Summary: Algorithms for constructing tree‐based classifiers are aimed at building an optimal set of rules implicitly described by some dataset of training samples. As the number of samples and/or attributes in the dataset increases, the required construction time becomes the limiting factor for interactive or even functional use. The problem is emphasized if tree derivation is part of an iterative optimization method, such as boosting. Attempts to parallelize the construction of classification trees have therefore been presented in the past. This paper describes a parallel method for binary classification tree construction implemented on a graphics processing unit (GPU) using compute unified device architecture (CUDA). By employing node‐level, attribute‐level, and split‐level parallelism, the task parallel and data parallel sections of tree induction are mapped to the architecture of a modern GPU. The GPU‐based solution is compared with the sequential and multi‐threaded CPU versions on public access datasets, and it is shown that an order of magnitude acceleration can be achieved on this data‐intensive task using inexpensive commodity hardware. The influence of dataset characteristics on the efficiency of parallel implementation is also analyzed. Copyright © 2015 John Wiley & Sons, Ltd.Keywords
This publication has 27 references indexed in Scilit:
- CUDT: A CUDA Based Decision Tree AlgorithmThe Scientific World Journal, 2014
- Decision tree construction on GPU: ubiquitous parallel computing approachComputing, 2013
- Porting Decision Tree Algorithms to Multicore Using FastFlowLecture Notes in Computer Science, 2010
- The WEKA data mining softwareACM SIGKDD Explorations Newsletter, 2009
- Implementing Decision Trees and Forests on a GPU2008
- Quality assessment of individual classifications in machine learning and data miningKnowledge and Information Systems, 2005
- Communication and Memory Efficient Parallel Decision Tree Construction2003
- Efficient Parallel Classification Using Dimensional Aggregates2000
- Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variablesComputers and Electronics in Agriculture, 1999
- Induction of decision treesMachine Learning, 1986