论文部分内容阅读
数据密集型计算随着大数据时代的到来受到了业界的广泛关注,而针对数据密集型计算环境下大数据的数据挖掘的研究却仍然处于起步阶段。目前针对数据密集型计算环境下数据挖掘的研究主要集中在如何利用大规模集群系统所具有的可伸缩性和容错性等优势,实现高效的数据挖掘和管理功能。本文首先阐述了数据密集型计算的特点和典型应用,讨论了数据密集型计算环境下数据挖掘的研究现状和传统分类方法,着重介绍了ID3、C4.5、CART、SLIQ和SPRINT等典型决策树算法和并行挖掘策略,同时也对Hadoop开源分布式系统架构这一分布式数据处理的最佳平台做了简要的介绍。本文提出了一种基于MapReduce编程框架和SPRINT算法的决策树分类算法MR-DIDC,结合MapReduce的优秀特性,使其更适用于数据密集型计算应用,然后以一个实例为基础介绍算法的运行过程,最后指出了算法的改进策略。MR-DIDC算法通过MapReduce编程框架的并行计算能力优化决策树节点扩展过程、最佳分裂属性选择及其分裂点计算和属性列表分割,提高算法的执行效率。MR-DIDC改进和引入了以下几种数据结构,分别为直方图、块计数矩阵、块哈希表和块直方图,通过改进策略提高算法的并行性能。属性列表的结构与SPRINT算法相同,用来记录属性取值和所属类标的对应关系,连续属性的属性列表需进行预排序。连续属性维护直方图信息,直方图为两行,分别对应Cabove和Cbelow,记录当前数据节点分裂点前后的类标数量分布；离散属性维护块计数矩阵信息,块计数矩阵的行数为离散属性值域的大小,每行表示当前数据节点该属性为某值时类标的数量分布；块直方图是算法引入的新型数据结构,用来记录每一数据节点的类标数量分布,辅助直方图简化分裂点的计算过程。分裂点的计算过程中,各数据节点间无需相互通信,可通过块直方图来获得全局的类标分布,减少各分片间互相通信而产生的I/O次数,有效的提高算法的数据可用性。块哈希表在节点扩展的过程中用来记录当前数据节点分裂点两侧的数据划分。最后通过实验对MR-DIDC算法的时间效率、可伸缩性、并行性、准确性等方面进行了测试。实验结果证明,MR-DIDC算法具有良好的可伸缩性和较高的数据可用性,当数据量很大时,在大规模集群上的运行时间将明显缩短。