基于CUDA平台的C4.5算法研究

论文摘要

21世纪是信息爆炸的时代，如何有效利用已有信息和数据发现规律，无疑成为重要课题。当前许多公司或企业的数据库中存储有海量数据，如餐饮业的顾客消费记录、顾客登记记录；网络运营商的客户通话和短信记录；大型超市的销售记录等等，从这些海量数据中发现规律，进而指导决策者进行决策就是数据挖掘的任务。进行数据挖掘，选取适当的数据挖掘算法是必要的。数据挖掘算法有很多类别，主要包括关联规则分析、聚类分析、分类分析等。关联规则算法中最经典的莫过于apriori算法，本文在apriori算法的基础上讨论了FP-growth算法，并给出了FP-growth算法的并行计算思路；聚类分析算法部分重点介绍了K-MEANS算法及其并行处理思想；分类分析中决策树算法是比较重要的，本文重点讨论了C4.5决策树算法，介绍了算法中测试属性的选择、包含未知属性值样本的处理、窗口机制、离散属性值分组、决策树剪枝等问题。在详细讨论该算法的基础上给出了其并行处理思路。有了并行处理思路，本文借助于NVIDIA公司推出的CUDA平台实现了C4.5算法的并行化。CUDA平台是实现GPU通用计算的平台，使用扩展的C语言进行编程，编译器为nvcc。实验表明，CUDA平台的并行C4.5算法效率有极大提升。本文通过实验证实了GPU计算的高效性，将更多的数据挖掘算法并行化，通过CUDA平台实现，将会有效提高数据挖掘的效率。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 概述
• 1.2 研究背景及意义
• 1.3 研究思路及创新点
• 1.4 论文框架
• 第二章 决策树算法
• 2.1 构建 C4.5 决策树
• 2.1.1 测试属性的选择
• 2.1.2 测试属性的分类
• 2.1.3 包含连续属性的测试属性
• 2.2 未知属性值的处理
• 2.2.1 修改测试属性选择标准
• 2.2.2 分割样本集
• 2.2.3 判断一个未知类别样本
• 2.3 窗口机制和离散属性值分组
• 2.3.1 窗口机制
• 2.3.2 离散属性值分组
• 2.4 决策树剪枝
• 2.5 C5.0 算法概述
• 2.6 本章小结
• 第三章 高性能计算平台 CUDA
• 3.1 CUDA 编程模型
• 3.1.1 主机与设备
• 3.1.2 Kernel 函数的定义与调用
• 3.1.3 线程结构
• 3.2 CUDA 软件体系
• 3.2.1 CUDA C 语言
• 3.2.2 nvcc 编译器
• 3.2.3 运行时 API 与驱动 API
• 3.3 本章小结
• 第四章 算法的并行设计方案
• 4.1 FP-growth 算法的并行设计
• 4.1.1 FP-growth 算法概述
• 4.1.2 FP-growth 算法的并行化研究
• 4.2 K-means 算法的并行设计
• 4.2.1 K-means 算法概述
• 4.2.2 K-means 算法的并行化研究
• 4.3 快速 C4.5 算法
• 4.3.1 算法并行化的可行性
• 4.3.2 改进算法的主要技术
• 4.3.3 快速 C4.5 算法描述
• 4.4 本章小结
• 第五章 快速 C4.5 算法的实现及应用
• 5.1 算法并行实现
• 5.1.1 实现细节
• 5.1.2 算法实现平台
• 5.2 实验结果及分析
• 5.2.1 并行算法实验
• 5.2.2 性能分析
• 5.3 本章小结
• 第六章 总结和展望
• 致谢
• 参考文献