More Web Proxy on the site http://driver.im/

article

Parallel construction of classification trees on a GPU

Authors:

A. NeratAuthors Info & Claims

Concurrency and Computation: Practice & Experience, Volume 28, Issue 5

Pages 1417 - 1436

https://doi.org/10.1002/cpe.3660

Published: 10 April 2016 Publication History

Abstract

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.

References

[1]

Wu X, Kumar V. The Top Ten Algorithms in Data Mining. Chapman & Hall/CRC: Boca Raton, Florida, 2009.

Digital Library

[2]

Appel R, Fuchs T, Dollar P, Perona P. Quickly boosting decision trees - pruning underachieving features early. Proceedings of the 30th International Conference on Machine Learning: Atlanta, Georgia, 2013; pp.594-602.

[3]

Kukar M. Quality assessment of individual classifications in machine learning and data mining. Knowledge and Information Systems 2006; Volume 9 Issue 3: pp.364-384.

[4]

Narlikar GJ. A parallel, multithreaded decision tree builder. CMU-CS-98-184, Computer Science Department, Carnegie Mellon University,Pittsburgh, Pennsylvania, 1998.

[5]

Aldinucci M, Ruggieri S, Torquati M. Porting decision tree algorithms to multicore using FastFlow. Proceedings of the 2010 European Conference on Machine Learning and Knowledge Discovery in Databases: Part I, Barcelona, Spain, 2010; pp.7-23.

Digital Library

[6]

Kufrin R. Generating C4.5 production rules in parallel. Proceedings of the 14th National Conference on Artificial Intelligence: Providence, Rhode Island, 1997; pp.565-570.

Digital Library

[7]

McConnell CC. *CART: Parallel CART on the CM-2. 1995. Available electronically from: "http://www.cs.cmu. edu/afs/cs.cmu.edu/user/ccm/www/papers/cmcart.ps", 1995, {Accessed on 15 July 2015}.

[8]

Joshi MV, Karypis G, Kumar V. ScalParC: a new scalable and efficient parallel classification algorithm for mining large datasets. Proceedings of the 12th International Parallel Processing Symposium: Orlando, Florida, 1998; pp.573-579.

Digital Library

[9]

Goil S, Choudhary AN. Efficient parallel classification using dimensional aggregates. Workshop on Large-Scale Parallel KDD Systems, San Diego, California, 1999; pp.197-210.

Digital Library

[10]

Shafer J, Agrawal R, Mehta M. SPRINT: a scalable parallel classifier for data mining. Proceedings of the 22th International Conference on Very Large Data Bases: Mumbai, India, 1996; pp.544-555.

Digital Library

[11]

Zaki MJ, Ho CT, Agrawal R. Parallel classification for data mining on shared-memory multiprocessors. Proceedings of the 15th International Conference on Data Engineering: Sydney, Australia, 1999; pp.198-205.

Digital Library

[12]

Jin R, Agrawal G. Communication and memory efficient parallel decision tree construction. Proceedings of the 3rd SIAM International Conference on Data Mining, San Francisco, California, 2003; pp.119-129.

[13]

Sreenivas MK, Alsabti K, Ranka S. Parallel out-of-core divide-and-conquer techniques with application to classification trees. Proceedings of the 13th International Parallel Processing Symposium, San Juan, Puerto Rico, 1999; pp.555-562.

Digital Library

[14]

Srivastava A, Han E-H, Kumar V, Singh V. Parallel formulations of decision-tree classification algorithms. Data Mining and Knowledge Discovery 1999; Volume 3 Issue 3: pp.237-261.

Digital Library

[15]

Ben-Haim Y, Yom-Tov E. A streaming parallel decision tree algorithm. Journal of Machine Learning Research 2010; Volume 11 Issue 2: pp.849-872.

Digital Library

[16]

Tyree S, Weinberger KQ, Agrawal K, Paykin J. Parallel boosted regression trees for web search ranking. Proceedings of the 20th International Conference on World Wide Web, Hyderabad, India, 2011; pp.387-396.

Digital Library

[17]

Steinkraus D, Buck I, Simard PY. Using GPUs for machine learning algorithms. Proceedings of the 8th International Conference on Document Analysis and Recognition, Seoul, South Korea, 2005; pp.1115-1120.

Digital Library

[18]

Fang W, Lau KK, Lu M, Xiao X, Lam CK, Yang PY, He B, Luo Q, Sander PV, Yang K. Parallel data mining on graphics processors. Technical Report HKUST-CS08-07, The Hong Kong University of Science and Technology,Hong Kong, China, 2008.

[19]

Bai H, He L, Ouyang D, Li Z, Li H. K-means on commodity GPUs with CUDA. Proceedings of the 2009 WRI World Congress on Computer Science and Information Engineering - Volume 03, Los Angeles, California, 2009; pp.651-655.

Digital Library

[20]

Herrero-Lopez S, Williams JR, Sanchez A. Parallel multiclass classification using SVMs on GPUs. Proceedings of the 3rd Workshop on General-Purpose Computation on Graphics Processing Units, Pittsburgh, Pennsylvania, 2010; pp.2-11.

Digital Library

[21]

Lopes N, Ribeiro B, Quintas R. GPUMLib: a new library to combine machine learning algorithms with graphics processing units. Proceedings of 10th International Conference on Hybrid Intelligent Systems, Atlanta, Georgia, 2010; pp.229-232.

[22]

Spencer J. Speculative parallel evaluation of classification trees on GPGPU compute engines. ArXiv e-prints 2011. Available electronically from: "http://arxiv.org/pdf/1111.1373v1.pdf", 2011, {Accessed on 15 July 2015}.

[23]

Sharp T. Implementing decision trees and forests on a GPU. Proceedings of 10th European Conference on Computer Vision: Part IV, Marseille, France, 2008; pp.595-608.

Digital Library

[24]

Grahn H, Lavesson N, Lapajne MH, Slat D. CudaRF: a CUDA-based implementation of random forests. Proceedings of the 9th IEEE/ACS International Conference on Computer Systems and Applications, Sharm El-Sheikh, Egypt, 2011; pp.95-101.

Digital Library

[25]

Hall M, Frank E, Holmes G, Pfahringer B, Reutemann P, Witten IH. The WEKA data mining software: an update. SIGKDD Explorations Newsletter 2009; Volume 11 Issue 1: pp.10-18.

Digital Library

[26]

Chiu CC, Luo GH, Yuan SM. A decision tree using CUDA GPUs. Proceedings of the 13th International Conference on Information Integration and Web-based Applications and Services, Ho Chi Minh City, Vietnam, 2011; pp.399-402.

Digital Library

[27]

Lo WT, Chang YS, Sheu RK, Chiu CC, Yuan SM. CUDT: A CUDA based decision tree algorithm. The Scientific World Journal 2014; Volume 2014: pp.1-12.

[28]

Nasridinov A, Lee Y, Park YH. Decision tree construction on GPU: ubiquitous parallel computing approach. Computing 2014; Volume 96 Issue 5: pp.403-413.

[29]

Quinlan JR. Induction of decision trees. Machine Learning 1986; Volume 1 Issue 1: pp.81-106.

Digital Library

[30]

Cook S. CUDA Programming: A Developer's Guide to Parallel Computing with GPUs. Morgan Kaufmann: San Francisco, CA, USA, 2012.

Digital Library

[31]

Munshi A, Gaster B, Mattson TG, Fung J, Ginsburg D. OpenCL Programming Guide. Addison-Wesley Professional: Boston, USA, 2011.

Digital Library

[32]

Zhang K, Li J, Chen G, Wu B. GPU accelerate parallel odd-even merge sort: an OpenCL method. Proceedings of the 2011 15th International Conference on Computer Supported Cooperative Work in Design, Lausanne, Switzerland, 2011; pp.76-83.

[33]

Huang B, Gao J, Li X. An empirically optimized radix sort for GPU. Proceedings of the IEEE International Symposium on Parallel and Distributed Processing with Applications, Roma, Italy, 2009; pp.234-241.

[34]

Bache K, Lichman M. UCI machine learning repository, 2013. Available from: "http://archive.ics.uci.edu/ml" {Accessed on 15 July 2015}.

[35]

Blackard JA, Dean DJ. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and Electronics in Agriculture 1999; Volume 24 Issue 3: pp.131-151.

[36]

Roe BP, Yang HJ, Zhu J, Liu Y, Stancu I, McGregor G. Boosted decision trees as an alternative to artificial neural networks for particle identification. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 2005; Volume 543 Issue 2-3: pp.577-584.

[37]

Cuturi M. Fast global alignment kernels. Proceedings of the 28th International Conference on Machine Learning: Washington, USA, 2011; pp.929-936.

[38]

Stolfo SJ, Fan W, Lee W, Prodromidis A, Chan PK. Cost-based modeling for fraud and intrusion detection: results from the JAM project. Proceedings of the 2000 DARPA Information Survivability Conference and Exposition, Hilton Head, SC, USA, 2000; pp.130-144.

[39]

Meek C, Thiesson B, Heckerman D. The learning-curve sampling method applied to model-based clustering. Journal of Machine Learning Research 2002; Volume 2 Issue 2: pp.397-418.

Digital Library

[40]

Hickey RJ. Structure and majority classes in decision tree learning. Journal of Machine Learning Research 2007; Volume 8 Issue 8: pp.1747-1768.

Digital Library

Cited By

Loreti DVisani G(2024)Parallel approaches for a decision tree-based explainability algorithmFuture Generation Computer Systems10.1016/j.future.2024.04.044158:C(308-322)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.future.2024.04.044
Wyrzykowski RDeelman EJurczuk KCzajkowski MKretowski M(2021)Fitness evaluation reuse for accelerating GPU-based evolutionary induction of decision treesInternational Journal of High Performance Computing Applications10.1177/109434202095739335:1(20-32)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1177/1094342020957393
Jurczuk KCzajkowski MKretowski M(2021)Multi-GPU approach to global induction of classification trees for large-scale data miningApplied Intelligence10.1007/s10489-020-01952-551:8(5683-5700)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s10489-020-01952-5
Show More Cited By

Parallel construction of classification trees on a GPU
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Architecture-Aware Mapping and Optimization on a 1600-Core GPU
ICPADS '11: Proceedings of the 2011 IEEE 17th International Conference on Parallel and Distributed Systems

The graphics processing unit (GPU) continues to make in-roads as a computational accelerator for high-performance computing (HPC). However, despite its increasing popularity, mapping and optimizing GPU code remains a difficult task, it is a multi-...
A Translation Framework for Virtual Execution Environment on CPU/GPU Architecture
PAAP '10: Proceedings of the 2010 3rd International Symposium on Parallel Architectures, Algorithms and Programming

GPUs are many-core processors with tremendous computational power. However, as automatic parallelization has not been realized yet, developing high-performance parallel code for GPUs is still very challenging. The paper presents a novel translation ...
SIMD Monte-Carlo Numerical Simulations Accelerated on GPU and Xeon Phi

The efficiency of a pleasingly parallel application is studied for several computing platforms. A real world problem, i.e., Monte-Carlo numerical simulations of stratospheric balloon envelope drift descent is considered. We detail the optimization of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Concurrency and Computation: Practice & Experience

Concurrency and Computation: Practice & Experience Volume 28, Issue 5

April 2016

296 pages

ISSN:1532-0626

EISSN:1532-0634

Issue’s Table of Contents

Publisher

John Wiley and Sons Ltd.

United Kingdom

Publication History

Published: 10 April 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Loreti DVisani G(2024)Parallel approaches for a decision tree-based explainability algorithmFuture Generation Computer Systems10.1016/j.future.2024.04.044158:C(308-322)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.future.2024.04.044
Wyrzykowski RDeelman EJurczuk KCzajkowski MKretowski M(2021)Fitness evaluation reuse for accelerating GPU-based evolutionary induction of decision treesInternational Journal of High Performance Computing Applications10.1177/109434202095739335:1(20-32)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1177/1094342020957393
Jurczuk KCzajkowski MKretowski M(2021)Multi-GPU approach to global induction of classification trees for large-scale data miningApplied Intelligence10.1007/s10489-020-01952-551:8(5683-5700)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s10489-020-01952-5
Jurczuk KCzajkowski MKretowski M(2018)Evolutionary induction of a decision tree for large-scale dataSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-016-2280-121:24(7363-7379)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s00500-016-2280-1

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents