No Access

HARDWARE IMPLEMENTATION OF DECISION TREE ENSEMBLES

RASTISLAV J. R. STRUHARIK

Faculty of Technical Sciences, University of Novi Sad, Trg Dositeja Obradovića 6, Novi Sad 21000, Serbia

Corresponding author.

Search for more papers by this author

and

LADISLAV A. NOVAK

Faculty of Technical Sciences, University of Novi Sad, Trg Dositeja Obradovića 6, Novi Sad 21000, Serbia

Search for more papers by this author

https://doi.org/10.1142/S0218126613500321Cited by:7 (Source: Crossref)

Abstract

In this paper, several hardware architectures for the realization of ensembles of axis-parallel, oblique and nonlinear decision trees (DTs) are presented. Hardware architectures for the implementation of a number of ensemble combination rules are also presented. These architectures are universal and can be used to combine predictions from any type of classifiers, such as decision trees, artificial neural networks (ANNs) and support vector machines (SVMs). Proposed architectures are suitable for the implementation using Field Programmable Gate Arrays (FPGA) and Application Specific Integrated Circuits (ASIC). Experiment results obtained using 29 datasets from the standard UCI Machine Learning Repository database suggest that the FPGA implementations offer significant improvement in the classification time in comparison with the traditional software implementations. Greatest improvement can be achieved using the SP2-P architecture implemented on the FPGA achieving 416.53 times faster classification speed on average, compared with the software implementation. This result has been achieved on the FPGA working at 135.51 MHz on average, which is 33.21 times slower than the operating frequency of the general purpose computer on which the software implementation has been executed.

This paper was recommended by Regional Editor Piero Malcovati.

Keywords:

References

T. M. Mitchell , Machine Learning ( McGraw-Hill , New York , 1997 ) . Google Scholar
K. P. Murphy , Machine Learning: A Probabilistic Perspective ( MIT Press , Cambridge, USA , 2012 ) . Google Scholar
S. Haykin , Neural Networks and Learning Machines , 3rd edn. ( Prentice Hall , New Jersey , 2008 ) . Google Scholar
L. Rokach and O. Maimon , IEEE Trans. Syst. Man Cybernet. 35 , 476 ( 2005 ) . Crossref, Web of Science, Google Scholar
C. Grosan and A. Abraham , Intelligent Systems: A Modern Approach ( Springer , New York , 2011 ) . Crossref, Google Scholar
C. Cortes and V. Vapnik , Mach. Learning 20 , 273 ( 1995 ) . Crossref, Web of Science, Google Scholar
L. Rokach , Artif. Intell. Rev. 33 , 1 ( 2010 ) . Crossref, Web of Science, Google Scholar
P. Bühlmann, Handbook of Computational Statistics, eds. T. Moris and J. E. Gentle (Springer, 2012) pp. 985–1022. Crossref, Google Scholar
M. Ozay and F. Vural , Performance analysis of stacked generalization classifiers , Signal Process. Commun. Appl. Conf. ( 2008 ) . Google Scholar
R. A. Jacobs et al. , Neural Comput. 3 , 79 ( 1991 ) . Crossref, Web of Science, Google Scholar
Y. S. Huang and C. Y. Suen , Behavior-knowledge space method for combination of multiple classifiers , Proc. of IEEE Computer Vision and Pattern Recog. ( 1993 ) . Google Scholar
A. Bermak and D. Martinez , IEEE Trans. Neural Networks 14 , 1097 ( 2003 ) . Crossref, Web of Science, Google Scholar
I. H. Witten and E. Frank , Data Mining: Practical Machine Learning Tools and Techniques , 3rd edn. ( Morgan Kaufmann , San Francisco , 2011 ) . Google Scholar
X. Wu and V. Kumar , The Top Ten Algorithms in Data Mining ( Chapman and Hall , UK , 2009 ) . Crossref, Google Scholar
L. Rokach and O. Maimon , Data Mining with Decision Trees: Theory and Applications ( World Scientific Publishing , Singapore , 2008 ) . Google Scholar
B. Gaster et al. , Heterogeneous Computing with OpenCL ( Morgan Kaufmann , Burlington , 2011 ) . Google Scholar
P. Pacheco , An Introduction to Parallel Programming ( Morgan Kaufmann , Burlington , 2011 ) . Google Scholar
R. Bekkerman , M. Bilenko and J. Lanqford , Scaling Up Machine Learning: Parallel and Distributed Approaches ( Cambridge University Press , Cambridge, UK , 2011 ) . Crossref, Google Scholar
D. G. Perera and K. F. Li, FPGA-based reconfigurable hardware for compute intensive data mining applications, Int. Conf. P2P, Parallel, Grid, Cloud and Internet Computing (2011) pp. 100–108. Google Scholar
A. N. Choudhary et al. , Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 1 , 41 ( 2011 ) . Crossref, Web of Science, Google Scholar
M. Papadonikolakis and C. S. Bouganis , IEEE Trans. Neural Networks Learning Syst. 23 , 1040 ( 2012 ) . Crossref, Web of Science, Google Scholar
B. Van Essenet al., Accelerating a random forest classifier: Multi-core, GP-GPU, or FPGA?, 20th International IEEE Symposium on Field-Programmable Custom Computing Machines (2012) pp. 232–239. Google Scholar
S. J. D. Prince , Computer Vision: Models, Learning, and Inference ( Cambridge University Press , Cambridge, UK , 2012 ) . Crossref, Google Scholar
S. Challa et al. , Fundamentals of Object Tracking ( Cambridge University Press , Cambridge, UK , 2011 ) . Crossref, Google Scholar
E. Maggio and A. Cavallaro , Video Tracking: Theory and Practice ( John Wiley & Sons , New Jersey , 2011 ) . Crossref, Google Scholar
T. Beckeret al., Hardware-accelerated object tracking, computer vision on low-power reconfigurable architectures workshop, 21st Int. Conf. Field Programmable Logic and Applications (2011) pp. 5–6. Google Scholar
S. Jin et al. , IEEE Trans. Industrial Informatics 8 , 158 ( 2012 ) . Crossref, Web of Science, Google Scholar
M. Yang et al. , Comput. Vision Image Understand. 114 , 1116 ( 2010 ) . Crossref, Web of Science, Google Scholar
K. Padmaja and T. N. Prabakar, FPGA based real time face detection using Adaboost and histogram equalization, Int. Conf. Advances in Engineering, Science and Management (2012) pp. 111–115. Google Scholar
J. R. Quinlan , Mach. Learning 1 , 81 ( 1986 ) . Crossref, Google Scholar
J. R. Quinlan , C4.5: Programs for Machine Learning ( Morgan Kaufmann Publishers , Burlington , 1993 ) . Google Scholar
D. Heath, S. Kasif and S. Salzberg, Induction of oblique decision trees, Proc. 13th Int. Joint Conf. Artificial Intelligence (1993) pp. 1002–1007. Google Scholar
L. Breiman et al. , Classification and Regression Trees ( Wadsworth and Brooks , Pacific Grove , 1984 ) . Google Scholar
S. K. Murthy , S. Kasif and S. Salzberg , J. Artific. Intell. Res. 2 , 1 ( 1994 ) . Crossref, Web of Science, Google Scholar
F. E. B. Otero , A. A. Freitas and C. G. Johnson , Appl. Soft Comput. 12 , 3615 ( 2012 ) . Crossref, Web of Science, Google Scholar
R. Struharik and L. Novak, Evolving Oblique and Non-Linear Decision Trees, Internal FTN Report (2007) . Google Scholar
R. C. Barros et al. , IEEE Trans. Syst. Man Cybernet. Part C: Appl. Rev. 42 , 291 ( 2011 ) . Crossref, Web of Science, Google Scholar
K. Barker and K. J. Wilson , Decision Anal. 9 , 348 ( 2012 ) . Crossref, Google Scholar
A. Ittner et al. , Feature space partitioning by non-linear and fuzzy decision trees , IFSA'97 ( 1997 ) . Google Scholar
L. Breiman , Mach. Learning 45 , 2 ( 2001 ) . Google Scholar
L. Breiman , Mach. Learning 36 , 85 ( 1999 ) . Crossref, Web of Science, Google Scholar
D. H. Wolpert , Neural Networks 5 , 241 ( 1992 ) . Crossref, Web of Science, Google Scholar
R. Struharik and L. Novak , IET Comput. Digital Tech. 3 , 259 ( 2009 ) . Crossref, Web of Science, Google Scholar
R. Struharik and L. Novak , J. Circuits Syst. Comput. 18 , 1033 ( 2009 ) . Link, Web of Science, Google Scholar
R. Struharik , Implementing decision trees in hardware , 9th IEEE Int. Symp. Intelligent Systems and Informatics ( 2012 ) . Google Scholar
C. L. Blake and C. J. Merz, UCI repository of machine learning databases, http://www.ics.uci.edu/~mlearn/ML-Repository.html (1998) . Google Scholar