Interactive presentation: An FPGA implementation of decision tree classification

ABSTRACT

Data mining techniques are a rapidly emerging class of applications that have widespread use in several fields. One important problem in data mining is Classification, which is the task of assigning objects to one of several predefined categories. Among the several solutions developed, Decision Tree Classification (DTC) is a popular method that yields high accuracy while handling large datasets. However, DTC is a computationally intensive algorithm, and as data sizes increase, its running time can stretch to several hours. In this paper, we propose a hardware implementation of Decision Tree Classification. We identify the compute-intensive kernel (Gini Score computation) in the algorithm, and develop a highly efficient architecture, which is further optimized by reordering the computations and by using a bitmapped data structure. Our implementation on a Xilinx Virtex-II Pro FPGA platform (with 16 Gini units) provides up to 5.58x performance improvement over an equivalent software implementation.

REFERENCES

• 1: Rakesh Agrawal , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 2: Zachary K. Baker , Viktor K. Prasanna, Efficient Hardware Data Mining with the Apriori Algorithm on FPGAs, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'05), p.3-12, April 18-20, 2005 [doi>10.1109/FCCM.2005.31]
• 3: Zachary K. Baker , Viktor K. Prasanna, An Architecture for Efficient Hardware Data Mining using Reconfigurable Computing Systems, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06), p.67-75, April 24-26, 2006 [doi>10.1109/FCCM.2006.22]
• 4: J. Catlett. Megainduction: Machine learning on very large databases. Ph.D Thesis, University of Sydney, 1991.
• 5: M. Estlick, M. Leeser, J. Szymanski, and J. Theiler. Algorithmic transformations in the implementation of k-means clustering on reconfigurable hardware. In Proc. of the IEEE Symposium on Field Programmable Custom Computing Machines(FCCM), 2001.
• 6: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 7: ScalParC: A New Scalable and Efficient Parallel Classification Algorithm for Mining Large Datasets, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.573, March 30-April 03, 1998
• 8: John C. Shafer , Rakesh Agrawal , Manish Mehta, SPRINT: A Scalable Parallel Classifier for Data Mining, Proceedings of the 22th International Conference on Very Large Data Bases, p.544-555, September 03-06, 1996
• 9: C. Wolinski, M. Gokhale, and K. McCabe. A reconfigurable computing fabric. In Proc. of the Engineering of Recongurable Systems and Algorithms Conference (ERSA), 2004.
• 10: J. Zambreno, B. Ozisikyilmaz, J. Pisharath, G. Memik, and A. Choudhary. Performance characterization of data mining applications using MineBench. In Proc. of the Workshop on Computer Architecture Evaluation using Commercial Work-loads (CAECW), 2006.