论文部分内容阅读
在信息时代的今天,数据库中蕴含着大量有价值的信息和知识。这些信息和知识广泛适用于大量领域,包括商务管理、生产控制、市场分析、工程设计和科学探索等,可以为决策者做出正确的选择提供有效的支持。然而这些潜在的信息和知识隐藏在数据的海洋中,没有工具的帮助,人们很难甚至几乎不可能发现它们。因此数据挖掘越来越重要。至今,已经有多种数据挖掘的方法,其中决策树是一种重要的分类和预测手段,它既能处理离散型数据,也能处理连续型数据,并且易于理解。预测离散属性值的树模型叫做分类树,而预测连续属性值的树模型叫做回归树。决策树方法主要包括树的构建即归导和剪枝两个方面。其中,树的归导既是重点也是难点所在,本文主要关注树的归导和并行化方面的问题。经典的决策树算法要求将整个训练集放入内存,数据集增大时,算法便不能运行,可规模性极差,这使得它不能用于现实世界的数据库。SLIQ算法强调算法的可规模性,将数据集分成一个个属性表驻留磁盘,从一定程度上减少了内存的限制,但是它要求类表全部驻留内存。SPRINT算法继承了SLIQ的很多优点,并且取消了类表,完全消除了内存的限制。并且SPRINT为并行而设计,并行性能也很优秀。但SPRINT也有其不足,属性表占用过多空间,建立哈希表耗费不少的时间。雨林框架将算法的可扩展性与算法的其他部分分离开,将训练集压缩成小得多的AVC-Group,再次提高了可扩展性。树归导过程中最重要也最难的一步是节点分割,包括寻找最佳分割准则和根据此分割准则划分数据集。本文对树模型和树归导进行深入研究,对属性的候选分割谓词的选取作出了改进,大量减少了需要评估的分割谓词,从而节省了大量的计算时间。关于衡量分割质量的指标,对于分类树本文选择GINI指数,对于回归树选择计算方差的减少量。无论是GINI指数还是方差,目的都是要使分割前后数据集的不纯度的减少量达到最大。采用MapReduce编程框架来实现并行化的树归导。使用两个队列来存放待分割的节点,一个队列存放数据集过大不能放入内存的节点,另一个存放数据集能放入内存的节点。采用自顶向下的方法,宽度优先的策略,将新建立待分割的节点加入到两个不同的队列。每次尽可能多的从两个队列中取出节点,以使并行的MapReduce作业尽可能的多。使用一个模型文件来存放树的结构,包括节点、分割条件等。与通常的做法不同的是,不在各节点上存放属于它的数据集,而通过树模型来判定一个样本记录是否属于某个节点集。用一台控制器来管理归导的全过程和模型文件、节点队列的更新。