论文部分内容阅读
随着计算机和网络技术的迅速发展,数据呈爆炸式增长。大数据的有效存储和处理成为各大企业当前面临的最艰巨的任务之一。如何高效、低成本的从海量数据中挖掘出潜在、有用的信息是数据挖掘技术当前面临的一大难题。在数据挖掘算法中决策树分类算法占有重要地位,决策树分类算法被视为是一种重要的分类和预测手段。但传统的决策树分类算法为内存驻留算法,在单机环境下,由于内存的限制,只能处理小规模的数据;其次,决策树分类算法最耗时的阶段为分割指标的计算阶段;再者,决策树的生成过程是一个递归过程,时间复杂度高。因此本文旨在解决传统决策树算法不能处理大规模数据的问题,以及如何高效的处理大规模数据的问题。近来,云计算的出现,为数据挖掘技术的进一步发展带来了新的前景。因为云计算不仅具有海量存储的能力,而且还提供并行处理的能力;其次,云计算系统可以构建在普通的、廉价的PC机上,代替高性能计算机,大大降低了成本。因此,云计算的出现,使数据挖掘技术进入了云挖掘的时代。Hadoop是Apache基金会开发的一个分布式系统基础框架,其中,HDFS分布式存储文件系统和Map Reduce分布式计算框架是Hadoop最重要的设计。其次,Hadoop使得用户在进行分布式程序开发的时候可以不用了解分布式的底层细节,并提供了一种高效、低成本、可扩展的计算模式。本文通过分析算法本身的特点,结合Map Reduce编程模式,将决策树分类算法移植到Hadoop平台上,从而实现了高效、低成本的数据挖掘工作。本文的主要工作如下:(1)针对传统的ID3决策树分类算法不能处理大规模数据的问题,通过引入云计算的并行化思想,提出了一种基于Hadoop平台的并行决策树分类算法H_ID3H_ID3算法利用Map Reduce编程模型,实现了数据集纵向划分的并行化、横向划分的并行化以及决策树同一层所有节点最佳分裂属性选择的并行化。通过算法的实现及相关实验,验证了算法的可行性,其次还可以得到如下结论:H_ID3算法能够处理大规模的数据集,且具有良好的可扩展性和高加速比;其次,在处理的数据集规模较大时,H_ID3算法的效率明显高于ID3算法。(第3章)(2)针对传统C4.5决策树分类算法不能处理大规模数据的问题,提出了一种基于Hadoop平台的决策树分类算法H_C4.5H_C4.5算法和H_ID3算法的并行化思想大致相同,只是最佳分裂属性的选择标准不同。同样,通过算法的实现及相关实验,验证了算法的可行性,以及H_C4.5算法具有的高效性、高扩展性和高加速比。(第4章)(3)针对传统CART决策树分类算法不能处理大规模数据的问题,提出了一种基于Hadoop平台的决策树分类算法H_CARTH_CART算法利用Map Reduce模型,实现了对数据集的并行划分,以及利用Map Reduce本身具有的排序功能,实现对连续属性值的并行化排序;其次,同样也实现了决策树同一层所有节点最佳分裂属性的并行化计算,大大提高了算法效率。通过算法的实现和相关实验,验证了算法的可行性和H_CART算法具有的高效性、高可扩展性和高加速比。(第5章)