臺灣博碩士論文加值系統

分類(classification)在機器學習(Machine Learning)和資料探勘(Data mining)中是一個很重要的議題。其中，決策樹被廣為運用在這個領域中，然而在現實生活中，資料多為高維度且資料量非常鉅量，在大量的資料下，整個決策樹建立的時間大多消耗在計算上，也就是這是一個運算密集的問題，也因此相當多的研究專注於加速分類模型的建立。

圖形處理器(GPU)是專門為處理圖形而設計的，因為影像的處理具高度平行化的特性，造就GPGPU 的產生; 許多研究專注於使用GPU 來處理非圖形處理的大量運算，其加速的效果非常驚人，因此也有著極高的性價比。而CUDA(Compute Unified Device Architecture)即為NVIDIA 所提出的GPGPU 的方案。

本論文基於NVIDIA’s CUDA 提出一個新的決策樹的演算法，在此架構中CPU 負責流程處理，而GPU 負責處理大量資料的運算。我們與著名的資料探勘軟體Weka 和SPRINT來做比較，結果顯示我們的CUDT 比起Weka 在效能上有6~5x 倍的加速，較大的資料上比起SPRINT 我們在效能上有18 倍的加速。

Classification is an important issue both in Machine Learning and Data Mining. Decision tree is one of the famous classification models. In the reality case, the dimension of data is high and the data size is huge. Building a decision in large data base cost much time in computation. It is a computationally expensive problem.

GPU is a special design processor of graphic. The highly parallel features of graphic processing made today’s GPU architecture. GPGPU means use GPU to solve non-graphic problems which need amounts of computation power. Since the high performance and capacity/price ratio, many researches use GPU to process lots computation. Compute Unified Device Architecture (CUDA) is a GPGPU solution provided by NVIDIA.

This paper provides a new parallel decision tree algorithm base on CUDA. The algorithm parallel computes building phase of decision tree. In our system, CPU is responsible for flow control and GPU is responsible for computation. We compare our system to the Weka-j48
algorithm. The result shows out system is 6~5x times faster than Weka-j48. Compare with SPRINT on large data set, our CUDT has about 18 times speedup.

摘要…………………………………………………………………I
Abstract……………………………………………………………II
Acknowledgements ......................................................................... IV
Table of Contents ............................................................................. V
List of Figures .................................................................................. VI
List of Tables .................................................................................. VII
Chapter 1 Introduction ..................................................................... 1
1.1 Motivation ......................................................................................... 1
1.2 Objectives .......................................................................................... 2
1.3 Outline of the Thesis ........................................................................ 2
Chapter 2 Background and Related Work ..................................... 3
2.1 Decision Tree ..................................................................................... 3
2.2 GPU ................................................................................................... 4
2.3 Compute Unified Device Architecture (CUDA) ............................ 6
2.4 Prefix-sum ......................................................................................... 8
2.5 Related Work .................................................................................... 8
Chapter 3 System Architecture ...................................................... 14
3.1 System Overview ............................................................................ 14
3.2 System Flowchart ........................................................................... 16
3.3 System Components ....................................................................... 18
Chapter 4 Evaluation ...................................................................... 30
4.1 Evaluation Environment ................................................................ 30
4.2 Data Sets .......................................................................................... 31
4.3 Evaluation of System ...................................................................... 32
4.4 Evaluation of Each Level ............................................................... 36
Chapter 5 Conclusion ..................................................................... 43
Chapter 6 Future Work .................................................................. 44
Reference .......................................................................................... 45

[1]. “NVIDIA CUDA Programming Guild, 3.2 edition”, NVIDIA Corporation 2010.
[2]. “NVIDIA CUDA Best Practices Guild, 3.2 edition”, NVIDIA Corporation 2010.
[3]. Mark Harris, “Optimizing Parallel Reduction in CUDA”, NVIDIA Corporation
<http://developer.download.nvidia.com/compute/cuda/1_1/Website/projects/reduction/d
oc/reduction.pdf>.
[4]. Mark Harris, “CUDPP: CUDA Data-Parallel Primitives Library 1.1.1”, NIVIDA,
UCDAVIS, 29 April 2010 <http://code.google.com/p/cudpp/ >.
[5]. Manish Mehta, Rakesh Agrawal, and Jorma Rissanen, “SLIQ: A fast scalable classifier
for data mining”. In Proc.of the fifth Int’l Conference on Extending Database
Technology (EDBT), Avigon, France, March 1996.
[6]. J. C. Shafer, R. Agrawal, and M. Mehta. “SPRINT: A scalable parallel classifier for data
mining”. In Proc. 22nd Int. Conf. Very Large Databases, VLDB, pages 544–555, 1996.
[7]. Venu Satuluri, ”A survey of parallel algorithms for classification”, 15 March 2007.
[8]. Mark Harris, “Parallel Prefix Sum (Scan) with CUDA”, April 2007.
[9]. J. R. Quinlan, “C4.5: Programs for Machine Learning”, Morgan Kaufman, 1993.
[10]. Toby Sharp, “Implementing Decision Trees and Forests on a GPU”, Microsoft Research,
Cambridge UK.
[11]. Daniel Slat, Mikael Hell borg Lapajne, “Random Forests for CUDA GPUs”, 2010.
[12]. L. Breiman, Random forests. Machine Learning, 45:5–32, 2001.
[13]. Guy E. Blelloch, “Prefix Sums and Their Applications”, CMU-CS-90-190, November
1990.
[14]. L. Breimain, J.H. Friedman, R. A. Olshen, and C.J. Stone, “Classification and
Regression Trees.” Wadsworth, Belmont, 1984.
[15]. Weka 3, <http://www.cs.waikato.ac.nz/ml/weka/ >.