Journal of Computer Applications 计算机应用，2012，32( 9) : 2463 － 2465，2469 ISSN 1001-9081 CODEN JYIIDU 2012-09-01 http: / / www． joca． cn 文章编号: 1001 － 9081 ( ) 2012 09 － 2463 － 03 : doi 10． 3724 / SP． J． 1087． 2012． 02463 基于 MapReduce 的决策树算法并行化 * 陆 秋 ，程小辉 桂林理工大学 信息科学与工程学院 广西 桂林 ， 541004) ( 通信作者电子邮箱 ( * 23578650@ qq． com) 摘 要: 针对传统决策树算法不能解决海量数据挖掘以及 ID3 算法的多值偏向问题，设计和实现了一种基于 MapReduce 架构的并行决策树分类算法。该算法采用属性相似度作为测试属性的选择标准来避免 ID3 算法的多值偏 向问题，采用 MapReduce 模型来解决海量数据挖掘问题。在用普通 PC 搭建的 Hadoop 集群的实验结果表明: 基于 MapReduce 的决策树算法可以处理大规模数据的分类问题，具有较好的可扩展性，在保证分类正确率的情况下能获得 接近线性的加速比。 关键词: MapReduce; 属性相似度; Hadoop; 决策树; ID3 算法 中图分类号: TP311． 133． 2 文献标志码: A Parallelization of decision tree algorithm based on MapReduce ( School of Information Science and Engineering， Guilin University of Technology， Guilin Guangxi 541004， China) LU Qiu * ， CHENG Xiao-hui Abstract: In view of that the traditional decision tree algorithm that cannot solve the mass data mining and the multi- value bias problem of ID3 algorithm， the paper designed and realized a parallel decision tree classification algorithm based on the MapReduce framework． This algorithm adopted attribute similarity as the choice standard to avoid the multi-value bias problem of ID3 algorithm， and used the MapReduce model to solve the mass data mining problems． According to the experiments on the Hadoop cluster set up by ordinary PCs， the decision tree algorithm based on MapReduce can deal with massive data classification． What's more， the algorithm has good expansibility while ensuring the classification accuracy and can get close to linear speedup rate． Key words: MapReduce; attribute similarity; Hadoop; decision tree; ID3 algorithm 0 引言 。 。 决策树技术是数据挖掘算法的关键技术，基于决策树的 近年来，关于 分类算法研究一直是国内外学者研究的热点 决策树挖掘算法的研究很多，主要集中在对挖掘算法的改进 这些算法虽然不同程度地提高了挖掘系统的有效性， 方面 但挖掘系统对数据的处理能力并没有明显提高 随着计算机 技术和网络技术的迅猛发展，数据量也已经呈指数级形式飞 速增长，利用大规模处理技术来实现海量数据的挖掘分析任 并行机制是解决这种海量数据挖掘的一种解 务越来越重要 决方 法 传 统 的 并 行 算 法 主 要 有 消 息 传 递 接 口 ( 。 。 Message 。 ， ］ 1 ) 和 并 行 虚 拟 机 ( ， MPI 。PVM Machine 好，而 Passing Interface ) ［ Parallel Virtual 在负载平衡和容错性上表现比较 PVM 简单易用，但是传统的并行方法抽象度不高，而由 模型可以降低并行程序设计的复杂 并行处理 、 Google 度，它主要从底层开始对数据进行分割 等操作进行封装，对用户而言只需要设计并行计算任务 分配任务 、 MPI 提出的 MapReduce 在并行数据挖掘研究中，主要的研究方法是采用现有的 挖掘算法进行并行化处理 算法 提出的一种并行决策树算法方案，文献［ ］提出了一种基于 4 平台的聚类算法方案，文献［ ］则对遗传算法的并行 Hadoop 5 研究进行了探讨，这些算法各有千秋，而且有相应的应用领 ］是针对 文献［ SPRINT 2 － 3 。 。 算法来说应用领域比较广，但是针对 算法为理论基础，以 ID3 算法 数 平台的决策树算 UCI MapReduce 。 ID3 对于 域 的并行研究比较少，本文将以 ID3 据集作为测试数据集，研究基于 法的实现 1 MapReduce 相关技术 。 是 Google MapReduce 提出的一个软件框架，是当前各种 云计算平台的基本计算模型，主要功能是海量数据的处理 。 提供了一种在大规模计算机集群上对海量数据进 MapReduce 行分布式处理的方法，它采用分而治之的方式，通过将海量数 据集分割成小数据集交给不同的计算机进行处理，从而实现 并行化，对于数据， MapReduce 对，对数据处理过程则简化成 段 成若 干 个 独 立 的 数 据 库，由 ， 〈key value〉 规约两个阶 平台里，往往将一个作业的输入数据集分 ， 〈key 的输 所示， value〉 入，执行相关操作 由输入 任务 将输入文件分成大小相等的 Map ， value〉 的计算流程［ 输出四部分构成 、 。 份 。MapReduce 任务 并 行 处 理，将 一 组 对映射成一组新的 将其看作一系列的 对，作为 MapReduce 映射和 ］如图 Reduce Reduce 〈key Map 在 。 6 － 8 1 、Reduce 、Map ) 输入 1 信息及相关配置信息存储在 ， 。 Split ( M Split ，并将 分布式文件系统 ) 后，提 交 任 务 给 Hadoop Distributed File System HDFS Hadoop JobTracker。JobTracker 初始化任务，找出空闲的 TrackTracker 收稿日期: 2012-02-23; 修回日期: 2012-06-18。 基金项目: 国家自然科学基金资助项目( 作者简介: 陆秋( 1979 － 研究方向: 数据库 嵌入式系统 、 计算机网络 、 。 ) ，女，广西钦州人，讲师，硕士，主要研究方向: 数据库 61063001 / F020207 计算机网络; 程小辉( 、 1961 － ICT1109 ) ，男，江西樟树人，教授，主要 。 ) ; 浙江大学工业控制技术国家重点实验室项目( ) 

4642 计算机应用 第 32 卷 节点并为它们分配子任务( M 任务) ，将构成该子任务的所有 队列 个 子任务， R 个 Map 任务和 Map Reduce 子 Reduce 任务放入 根据知识粒度的定义，可以知道在信息系统 为论域， 为条件属性集 Q 与 的相似度可用粒度来表示，即: 和决策属性 D C 中， U 义属性 ( ) ， Q 组成的集合，定 L = U 任务 被分配到 Map 。 Map 子任务的 获取与任务相关的数据，处理后生成 TrackTracker ， 节点 ( S 〈key Value〉 } ) A ( ) 2 。 ) 2 从 HDFS 对，调用 D A ∈ C ， A ) D = ( ) D ∪ * { A } ) ( { GD 槡 GD ( D槡 D GD ) 表示 的粒度值: n | Di | 2 = ∑ ) 可以得出条件属性 i = 1 ( GD D ( GD D 由式( ) 2 相似度计算公式: 与决策属性 A D 之间的属性 ( S ) ， A D = n m ∑ i = 1 ∑ j = 1 2 ai ， j n m ( ) 3 2 ， ， A j = 1 i = 1 D ai Ai aij 式( 。 的记录数 表示属性 2 * ∑ m +1槡 ∑ 取 A 和条件属性 an +1 j槡 ) 其中: 的记录中属于类 Dj 的相似度程度，其值越大，则 度量了决策属性 它们之间的属性相似度越大 因此属性相似度可以作为决策 。 树算法中的属性选取标准，在生成决策树时与决策属性相似 ］从实验和理 度大的属性被优先作为测试属性选取 算法的多值倾向问题，且 论分别证明了该算法可以避免 具有较高的分类准确率，在此不作详述 下面给出基于属性相 。 似度的决策树算法流程 文献［ 。 ID3 11 3 。 ( : 候 选 属 性 集， T C : 一 个 训 练 Function Similarity_Dtree 集) 返回一个决策树 。 训练样本集 一棵决策树 ，条件属性集 T C。 。 输入 输出 { ) ) ) ) ) ) ) ) 1 2 3 4 5 6 7 8 / / 创建根节点 ; Root If T 个带有该值的单个节点; 是由其值均为相同类别属性值的记录组成，返回一 为空，则返回 If R 出现最多的类; Root 为叶节点，标记 Root 为 T 记录中 中的条件属性 Ci For each T ( Similarity 函数 Ci ) ; ( ) 计算 属性的相似度; 3 候选属性中具有最大相似 Ci ) 为通过式( Similarity 的当前测试属性 Ci ; Root 度的属性 将 返回一棵树，其根标记为 从 Ci R Test = Ci 中删除，形成新的候选属性集 ; C' ，树枝标记为 Test ， d2 ， … ， d1 ; { 由 IF dm for each Test = C' 的取值 节点长出一个新子节点; Root 新叶节点对应的样本子集 则删除此节点; 为空 T' 函数处理后的中间结果通过分区函数分成 函数，将 Map Map Map 本地磁盘的位置信息发给 置信息发送给执行任务的 函数的中间结果写入本地磁盘; 个区，并将 将位 R JobTracker JobTracker ，然后由 子任务节点 Reduce 。 ) 3 Reduce 任务 中间数据，并对数据的 key 对进行合并， 。Reduce 值进行排序，将具有相同 子任务从位置信息中获取相关 的 节点将合并后的结果传递给 函数运行完后将输出结果输出到输出文 Reduce key ， Value〉 函数， Reduce 〈key Reduce 件 。 4 ) 输出 完成 和 子任务后， 。 R 结果返回给客户端程序，客户端程序根据结果进行 JobTracker Reduce Map 将 份 合并得到最终结果 Reduce 。 图 1 MapReduce 计算流程 从计算流程可知，该模型的核心操作是 两 操作都可以高度并行运行，从而 Reduce Map 和 Map 操作与 个函数， Reduce 实现数据处理的高度并行化 2 基于 MapReduce 的属性相似度算法 2． 1 基于属性相似度的决策树算法 。 ］ 9 ID3 。ID3 。ID3 在决策树 算法中，主要是引入信息论中的信息增益 算法选择信息增益最大的属 作为测试属性选择的标准 性作为产生决策树的节点，由该属性的不同取值建立相应的 分枝，再对各分枝的训练实例子集递归，使用该方法建立决策 树的下一级节点和分枝，直到某一子集中的实例属于同一 算法虽然计算速度较快，容易实现而且适用于处 类［ 理规模较大的学习问题，得到较为优化的决策树形式，但是 多值偏向 ID3 指决策树算法在选择测试属性时，倾向于优先选取取值较多 针对多值偏向问题，人们 的属性，这会使挖掘结果不够准确 提出了很多解决办法，主要分为两类: 标准化和二值化 但是 这又会引起新的问题，例如二值化降低了决策树的可理解 算法的多值偏向问题，笔者提出了一种决策 性［ 针对 ID3 ］，该算法是以属性相似度作为测试属性选择的 树改进算法［ 11 标准 算法在选择测试属性时存在着多值偏向问题 。 。 。 。 ］ 10 属性相似度是指由测试属性不同取值代替决策 。 定义 1 属性进行正确决策的支持度 。 定义 2 在信息系统 ( ， Q ) 中， U 为论域， Q U L = 和决策属性 组成的集合，定义属性 A ∈ C D 属性集 相似度如下: C ( S ) ， A D = | D ∪ { } A | 槡| D | * | 槡 越大，则 ) 可知， S 1 A 是完全相似的; 相反， S 由式( 与 D 则 A | { } A 与 越小，则 D 越相似，特别是 S = 1 越不相似 时， 。 与 A D 为条件 与 的 D ( ) 1 ELSE Similarity_Dtree ( C' ， T' m ) ; } } 2． 2 决策树算法的并行化 从 2． 1 节的算法描述可知: 决策树的生成是一个反复迭 代的过程，如果用传统的串行算法来实现的话，规模很小的数 据量也需要花费大量的资源，更不用说超大规模的数据集，而 并行程序设计方法能很好地解决这个问题 决策树构建过程 中最费时间的就是属性相似度计算，而对于这个问题，由于属 性之间 的 计 算 是 可 以并 行 执 行 的 ，可 以 将 该 算 法 运 用 在 的并行算法主要由两部 实 MapReduce 实现数据处理; MapReduce 分构成: 平台中 基于 ) 用 ) 用 。 。 2 JobTracker2 1 JobTracker1 

第 9 期 陆秋等: 基于 MapReduce 的决策树算法并行化 5642 现决策树算法的构建 。 本文重点介绍第二部分 。 2． 2． 1 基于 MapReduce 的决策树算法流程 地计算条件属性的相似度，对每个条件属性，首先求出 值存储在数组中，称为取值记录数矩阵 根据前面对相似度理论的介绍，本文实现时为了更方便 的 的 操作主要任务就是对数据进行预处理，并 生 成 这样的键值对，作为 详细流程， 取值记录数矩阵 为 ， 〈 函数的输入，图 aij JobTracker1 节点，属性名 MapReduce 对于 〉〉 〉 。 〈〈 2 JobTracker2 JobTracker2 Map 主要实现决策树的构建 。 图 2 基于 MapReduce 的决策树并行算法流程 对于 例如对于 值记录 数 矩 阵 度 操作及相应的 〉〉。 根据图 类 2 2． 2． 2 基于 MapReduce 的决策树算法的具体实现 〈key MapReduce 来说数据就是一系列的 的 输入的是 JobTracker2 Map ，而 输 出 则 变 成 〉〉 〈〈 由此可见，在算法实现过程中，关键是设计 节点，属性名 ， 〈〈 节 点，属 性 名 对， ， value〉 ， 取 〈 相 似 〉 〉 〈 MapReduce ， value〉 对 〈key ，本文算法主要设计 。 类 类来实现图中主要过程 Decision_Driver 、Decision _Mapper 、Decision_Reduce ) 1 该类 作 为 一 个 程 序 入 口，初 始 化 Decision_Driver 类 。 setMapperClass setReducerClass ( ) ， JobTracker ( ) 方 法 设 定 Decision_Reduce Map、Reduce 类分别作为 ，通 过 Decision _ 函数的实 和 Mapper 现类 。 ) 2 该类用来实现 Decision_Mapper 类 。 过程 中读入 先从 ， 〈 的输出结果，将 据对象读入 Map 。 节点，属性名 JobTracker1 作为数 〈〈 计算该数据对象的属性相似度，并将结果形成 ， 。 的键值对输出模式，其中 HDFS 取值记录数矩阵 节点，属性名 ， value〉 为当前数据对象相对于分类属性的属性相似度 〉〉 key 为 〉 〉 〈 〈key 。Map value 过程伪代码如下所示: ， value〉。 ， value'〉 的值 输入 〈key 输出 〈key ) ) 读 value Value' = similarity ( ) value ，其中 value' 为属性相似度 。 1 2 3 4 ) ) context． write 结束 / / similarity ) ， value' ( key ( ) 利用式( ) 求相似度 3 ) 3 该类实现 Decision_Reduce Reduce 类 。 局部结果，然后对这个结果进行汇总，求 过程，首先获得来自各节点 过程的 的最大值，得到 Map value 测试属性，最后实现属性的分裂，重新分割数据集并写回结 果 。 输出 。 Map ，同 ， value〉 ， value'〉。 创建节点 输入 〈key 输出 〈key' ) 1 ) ( 2 ) ) ) 3 4 5 value For 等于相似度最大的条件属性; } 调用 割处理 MakeTree ， T N ( 。 ( key' context． write 的各个分支节点 结束 。 N ) { 求最大相似度值，保存在 中，并让节点 N max ) 构建节点，对非叶节点的各分支做分 ， value' ) ，其中 key' 的值为当前节点 N 3 实验分析 Hadoop 是 此框架实现的 服务器组成的集群 。 节点; TaskTracker 同时，采取 多个 Xen MapReduce 和 0． 20． 0 本实验主要实现基于 JDK。 H_S_Decision 算法的准确率 据从 用 UCI http ( Breast-cancer Java 框架的 其中，一台是 MapReduce 首先搭建了仿真实验平台，该平台是由 实现，本文算法是基于 台 节点; 一台是 。 台都可以作为计算节点及数据存储节点 。 的虚拟化技术，使同一节点上同时并发执行 操作 其次在 8 平台程序采用 台服务器中均安装 JobTracker Hadoop- 。 8 8 MapReduce 和串行的属性相似度决策树算法 加速比和可扩展性等性能进行分析 、 : / / archive． ics． uci． edu / ml / datasets． html 数 据 集 ( 简 称 ) 。 集成开发环境完成 Eclipse 的属性相似度决策树算法 ，从 实验数 ) 上选 S_Decision 。 、Audlt A 样本有 9 数 据 集 ( 简 称 个属性，共有 48 842 个样本 。C B ) 、 个 286 数据集 个属性，共有 ) C 14 。A Waveform 样本 有 数据集( 简称 数据集有 。B 个属性，共有 ) 准确率 1 在实验中对数据集进行划分 测试数据集，部分实验结果如表 时间复杂度 、 个样本 5 000 。 41 。 70% 所示 。 表 1 算法运行结果数据 1 为训练数据集， 为 30% 1 1 2 3 1 A B B B C 66． 66 91． 34 91． 23 91． 36 78． 23 0． 31 292． 00 211． 00 139． 00 160． 00 66． 66 91． 34 91． 23 91． 36 76． 98 0． 23 233． 00 155． 00 110． 00 103． 00 1 。 由表 H_S_Decision 可 知: 虽 然 都 是 用 一 个 节 点 进 行 测 试，采 用 算法运算时间缩短了， 并行策略的 MapReduce 而从并行角度看，随着节点的增加， 而准确率基本保持不变 算法的时间复杂度下降，算法的准确率也能维持在一定的水 平，说明了将 ) 加速比 2 加速比 50 ，是描述并行算法运行时间减少而获得的性能 ］ 4 是衡量并行算法性能的一个重要指 指单 个节点并行求解算法 ， 标［ 个节点上求解问题所花的时间， Tm 所花的时间 m 实验所用数据参照数据集 算法进行并行化是可行的 S = TS / Tm 随机产生 S_Decision 。TS 指 。 。 B 50 000 。 ， 100 000 200 000 ， 500 000 条记录，这些数据集分别称为 D1 、 D2 、D3 、D4 。 3 从图 可看出: 随着节点的增加，加速比趋于缓和，主要 原因是因为随着节点的增加，各个节点之间的通信开销亦增 ( 下转第 2469 页) 。 节点数 数据集 S_Decision 准确率 / % 时间 / s H_S_Decision 准确率 / % 时间 / s 

第 9 期 贺毅辉等: 基于 CUDA 的大规模群体行为实时仿真并行实现及优化 9642 New York: ACM Press， 2006: 113 － 121． ［C］ / / EGGH-04: Proceedings of ACM SIGGRAPH / Euro Graphics ［5］ QUINN M J， METOYER R A． Parallel implementation of the social Workshop on Graphics Hardware． New York: ACM Press， 2004: forces model［C］ / / Proceedings of the 2nd International Conference 115 － 122． in Pedestrian and Evacuation Dynamics． London: CMS Press， ［12］ GRAND S L． Broad-phase collision detection with CUDA ［M ］． 2003: 63 － 74． Upper Saddle River: Addison Wesley， 2007． ［6］ CHIARA R D， ERRA U． Massive simulation using GPU of a dis- ［13］ SIMON G． CUDA particles ［EB / OL］． ［2010-10-10 ］． http: / / tributed behavioral model of a flock with obstacle avoidance ［C］ / / www． mendeley． com / research / cuda-particles / ． Proceedings of Vision， Modeling and Visualization． Stanford: ［s． ［14］ SANDERS J， KANDROT E． CUDA by example: An introduction n． ］， 2004: 233 － 240． to general-purpose GPU programming ［M］． Upper Saddle River: ［7］ RICHMOND P， DANIELA R． High performance cellular level A- Addison Wesley， 2010． gent-based simulation with FLAME for the GPU ［J ］． Briefings in ［15］ STATISH N， HARRIS M， GARLAND M． Designing efficient sor- Bioinformatics， 2010， 11( 3) : 334 － 347． ting algorithms for manycore GPUs［C］ / / IPDPS  09: Proceedings ［8］ RICHMOND P ， ROMANO D ． Agent -based GPU ， a real -time 3 D of the 2009 IEEE International Symposium on Parallel ＆ Distribu- simulation and interactive visualisation framework for massive Agent- ted Processing． Washington， DC: IEEE Computer Society， 2009: 1 based modelling on the GPU［C］ / / Proceedings International Work- － 10． shop on Super Visualization． New York: ACM Press， 2008: 185 － ［16］ HARRIS M ， SENGUPTA S ， OWENS J D ． Parallel prefix sum 192． ( Scan) with CUDA ［M］． Upper Saddle River: Addison Wesley， ［9］ MAO T， JIANG H． Parallelizing continuum crowds［C］ / / Proceed- 2007． ings of the 17th ACM Symposium on Virtual Reality Software and ［17］ SENGUPTA S， HARRIS M， ZHANG Y， et al． Scan primitives for Technology． New York: ACM Press， 2010: 231 － 234． GPU computing ［C］ / / GH'07: Proceedings of the 22nd ACM SIG- ［10］ NVIDIA． CUDA programming guide: V3． 0 ［EB / OL］． ［2010-10- GRAPH / EUROGRAPHICS Symposium on Graphics Hardware． 10］． http: / / www． nvidia． com / object / cuda_home． html． Aire-la-Ville Switzerland: Eurographics Association， 2007: 97 － ［11］ KIPFER P， SEGAL M． Uber-flow: A GPU-based particle engine 106． 对于较大的数据集算法的效率更明显，其加速比曲线接 算法可 的 。 ( 上接第 2465 页) 加 近线性增加，这说明基于 用来解决海量数据的挖掘问题 H_S_Decision MapReduce 。 图 3 H_S_Decision 算法加速比曲线 。 。 概念 ，其中 ) 可扩展性 3 为了反映并行算法集群的利用率情况，引入算法效率的 并行算法的效率是算法的加速比与节点数的比值，即 可看出，算法 4 曲线相对 为加速比， 为节点数 N 从图 可看出 平稳一些，这说明当数据集规模越大， D1 、 算法 D2 的效率曲线越平稳，所以该算法对海量数据具有较好的可扩 展性 E = S / N 效率整体来说呈下降趋势 H_S_Decision 从图 D4 。 。 4 S 。 图 4 H_S_Decision 算法效率曲线 4 结语 决策树算法的并行性是当前解决海量数据分类问题的研 算法在决策树算法中占着重要地位，如何将 究重点，而 ID3 算法并行化是一项重要的课题 算法的基础 ID3 上提出 了 基 于 属 性 相 似度 的 决 策 树 算 法 ，并 将 其 应 用 平台构建了一种并行性能比较好的决策树算法 算法具有较好的 实验结果表明 MapReduce 本文在 ID3 。 H_S_Decision 较低的时间复杂度和较好并行性能 、 。 基于 SPRINT 方法的并行决策树分类研究 计算机 ［J］． ，2005，25( 1) : 39 － 41． 基于 万剑怡 王明文 ， MR 广西师范大学学报 ． 的并行决策树分类算法的设计 自然科学版 ，2011，29 ( 1 ) : 82 － : H_S_Decision。 分类正确率 参考文献: 魏红宁 应用 朱敏 ， 与实现 ［2］ ［1］ ． ［J］． ［3］ ［4］ ［5］ ［6］ 84． 杨宸铸 基于 ． HADOOP 的数据挖掘研究 ［D］． 重庆 : 重庆大学 ， ． 2010: 45 － 46． 李应安 基于 中山大学 程苗 陈华平 ， MapReduce 的聚类算法的并行化研究 ［D］． 广州 ． ，2010: 50 － 51． 基于 Hadoop 的 Web 日志挖掘 ［J］． 计算机工程 ， ． 2011，37( 11) : 37 － 38． 雷万云 社 云计算技术 ，2011: 22 － 224． ． 平台及应用案例 、 ［M］． 北京 : 清华大学出版 ［7］ LIU YANG， LI MAOZHEN， ALHAM N K． HSIM: A MapReduce simulator in enabling cloud computing ［EB / OL］． ［2012-01-20 ］． http: / / www． sciencedirect． com / science / article / pii / S0167739X110 00884． ［8］ ALHAM N K， LI MAOZHEN， LIU YANG． A MapReduce-based distributed SVM algorithm of automatic image annotation［J］． Com- puters and Mathematics with Applications， 2011， 62 ( 7 ) : 2801 － ， 2811． 毛国君 大学出版社 韩松来 张辉 计算机应用 陆秋 程小辉 ， ， ［9］ ［10］ ［11］ 段立娟 王实 等 ． ， ， 数据挖掘原理与算法 ［M］． 北京 : 清华 ，2005: 117 － 125． 周华平 ． ， 基于关联度函数的决策树分类算法 ［J］． ，2005，25( 11) : 2655 － 2657． 基于属性相似度的决策树算法 ［J］． 计算机工程 ， ． 2009，35( 6) : 82 － 84．