基于MapReduce的ID3决策树分类算法研究.doc

计 算 机 与 现 代 化jisuanji yu xiandaihua2012 年第 2 期总第 198 期文章编号: 1006-2475( 2012) 02-0026-05mapreduceid3基于的决策树分类算法研究钱网伟( 同济大学电子与信息工程学院，上海 201804)摘要: 决策树算法是经典的分类挖掘算法之一，具有广泛的实际应用价值。经典的 id3 决策树算法是内存驻留算法，只能处理小数据集，在面对海量数据集时显得无能为力。为此，对经典 id3 决策树生成算法的可并行性进行了深入分析和 研究，利用云计算的 mapreduce 编程技术，提出并实现面向海量数据的 id3 决策树并行分类算法。实验结果表明该算法 是有效可行的。关键词: 云计算; 数据挖掘; 决策树;id3; mapreduce中图分类号: tp301 6文献标识码: adoi: 10 3969 / j issn 1006-2475 2012 02 008research on id3 decision tree classification algorithm based on mapreduceqian wang-wei( school of electronics and information engineering，tongji university，shanghai 201804，china)abstract: decision tree is widely used in data mining which is one of the typical classification algorithms traditional id3 treelearning algorithms require training data to reside in memory on a single machine，so they cannot deal with massive datasets to solve this problem，this paper analyzes the parallel algorithm of id3 decision tree based on mapreduce model，then proposes a parallel and distributed algorithm for id3 decision tree learning the experimental results demonstrate the algorithm can scale well and efficiently process large-scale datasets on commodity computerskey words: cloud computing; data mining; decision tree; id3;mapreducempi 的并行分布式 sprint5决策树算法。该算法通过每个节点保存相应的属性表以及维护属性表的 hash 表来实现并行运算，这将导致数据过度冗余，从 而影响超大规模数据处理效率，这就需要一种新的计 算模型。云计算( cloud computing) 是一种新近提出的计算模式，是分布式计算( distributed computing) 、并行0引言分类是数据挖掘的主要任务，其中决策树分类是分类挖掘的常用模型，是经典的机器学习算法之一。 它能够通过训练数据集的学习来产生相应的决策规 则树，目前已成功地应用于 web 智能、金融分析、天 文学和分子生物学等领域1。c4 5 决策树算法更是 被 icdm 评为十大经典的数据挖掘算法之一并位居榜首2。传统的决策树算法有 id33、c4 54等。但是， 随着信息量爆发性地增长，传统内存驻留的决策树算 法在处理海量数据时性能问题日益突出，大规模海量 数据与处理任务不可能由一般的计算机在规定的时 间内完成。为了解决算法内存驻留问题，通过引入高 效的数据结构和数据调度策略等来改造决策树学习 过程的算法相继提出，如 john shafer 等提出了基于计算( parallel computing) 和网格计算( gridcompu-mapre-6。ting)的 发 展 云 计 算 的 兴 起，尤 其 是7-8duce框架( 如图 1 ) 的提出，使得大规模数据集可以在普通机器集群上实现并行运算，通过 map 和 re-duce 两 个 阶 段 实 现 大 规 模 数 据 的 映 射 和 化 简。9作为分布式文件系统也是云计算的关键技术，gfs它是 google 云计算海量的数据存储的有力平台，并采用数据冗余等技术提供了一套完善的容错机制。10是云计算的开源系统并实现了 google 云计hadoop算的主要技术( mapreduce、gfs 等) ，是 apache 开源组织的一个并行分布式计算框架，它具有较高的可靠收稿日期: 2011-10-21作者简介: 钱网伟( 1986-) ，男，江苏镇江人，同济大学电子与信息工程学院硕士研究生，研究方向: 数据挖掘，云计算。性和扩展性。近年来云计算技术发展迅猛，并且运用于机器学习领域11-12，其中 mapreduce 已经广泛应 用于 amazon、google、baidu、阿里巴巴等国内外知名 企业的云计算系统，具有强大的生命力。dm ) 。递归划分步骤仅当下列条件之一成立时停止: ( 1) 集合 d 所有元组属于同一类;( 2) 没有剩余属性可以进一步划分元组，那么就使用多数类表决;( 3) 给定的分支中没有元组( 即 di 为空) ，此时用父节点中的多数类标记。1 2 属性度量选择不同的决策树算法之间的一个重要区别就在于 决策属性选取标准的不同。生成决策树时，常用属性 度量 标 准 有 以 下 几 种: 信 息 增 益、增 益 率、gini 指标1。信息增益是 id3 使用的属性选择度量，在节点 n存放的 d 的元组，选择最高信息增益的属性作为 n 的分裂属性。该属性使结果划分中的元组分类所需 的信息量最小，并反映这些划分中的最小随机性或“不纯性”。对于 d 元组分类所需的期望信息:m图 1 mapreduce 的工作模式本文深入研究 mapreduce 编程框架，对经典决 策树算法进行了深入的研究和剖析，利用决策树度量 属性重要性是基于属性间的相互独立性的原则，提出 了面向海量数据的云计算环境下决策树生成算法，并 利用 hadoop 开源平台实现了该算法。实验结果表明 该算法不仅具有高效性，而且能够处理海量数据。1经典决策树算法hong j r 已经证明决策树生成算法是一个 np-info( d)= pi log2 ( pi )( 1)i = 1其中，pi 是 d 中 任 意 元 组 属 于 类 ci 的 概 率，并 用| ci，d | / | d | 估计。基于按属性 a( v 个不同值) 划分对 d 的元组分 类所需要的期望信息:hard 问题13，所以经典决策树一般采用贪心、分治的思想，由顶向下的递归方式生成。它通过在决策树内部节点上进行评估来选择最佳决策属性，并根据该 属性的不同属性值对该节点进行分支，最终在决策树 的叶子节点上得到分类结论。决策树从根节点开始的每一条路径均对应着一条分类规则，整棵决策树则对应了一组决策规则集。vinfoa ( d) = info( dj )( 2)j = 1信息增益为原来的信息需求与新的需 求 之 间的差:gain( a) = info( d) info ( d)( 3)a1 1经典 id3 算法经典的深度优先生成决策树 id3 算法如下:本文采用 c4 5 的增益率度量标准。增益率在选取属性时避免了信息增益中对大量值属性的偏倚，算法 1decision tree( r，c，d) 。从而提高了决策树的分类准确率。它定义了一个分裂信息:输入: 属性集 r，类别属性集 c，训练集 d。输出: 决策树。vsplitinfoa ( d)= j = 1 log2( 4)( 1)( 2)记 n;( 3)创建节点 n;由公式( 3) 、( 4) 进一步得到增益率，并选取具有最大增益率的属性作为分裂属性:ifd 为空 then 返回父节点中的多数类标gain( a)else if d 中属于同一个类别 c then 以类 cgainratio( a) =( 5)splitinfo( a)标记 n 为叶节点;( 4) else if记 n;r 为 空then返 回 d 中 多 数 类 标2云计算下决策树算法中并行化思想云计算技术传统的决策树算法是内存驻留算法，整个生成决2 1( 5) else 计算并选出 r 中增益率最大的属性 s并用 s 标记节点 n;( 6) 根据属性 s 的取值 si | i = 1，2，m 将训 练集合 d 分割为 di | i = 1，2，m ;策树过程的所有数据计算必须同时在内存中进行，并且它只能在单机上运行，这就大大地影响了算法的伸( 7)递归执行 decisiontree ( r-s，c，d1 ) ，deci-缩性，因此它不能处理大规模数据。云计算的出现，sion tree ( r-s，c，d2 ) ， decision tree ( r-s，c，为解决这一问题提供了强有力的工具，使得用传统经djddjddjd28计 算 机与现 代 化2012 年第 2 期典的数据挖掘算法处理大规模数据成为可能。mapreduce 是一种处理海量数据的并行编程模 式。用户将实际应用问题分解成若干可并行操作的 子问题，设计相应的 map 和 reduce 两个函数，就能 将自己的应用程序运行在云计算环境中。map 函数 是接收一组输入键值对 in-key，in-value ，然后通 过某种计算，产生中间结果键值对，而 reduce 函数接 收一个中间结果 key 和对应此 key 的一组 value 值，value-sum 进行 hash 映射。根据计算增益率所需的参数建立若干个 hash 表。然后，能通过 hash 查询从 而快速地批处理地计算同一层次的各个训练集 di 的 每个属性的增益率，并选取 di 中最大增益率的属性 作为分裂属性。3基于 mapreduce 的决策树算法实现本算法通过一个划分条件集队列 q，来实现基于然后 通 过 归 并 处 理，最 终 形 成value 。 final-key，final-层次切分数据和同一层次各个训练集分裂属性的选取。利用队列先进先出原则，从队头到队尾依次对 q中每个对象( 即划分条件) 进行标记临时 nid 号( 1，2，| q | ) 。根 据 上 一 节 描 述 的 设 计 思 想，结 合 al- lelectronic 顾客数据训练集( 见表 1) 以及该数据训练2 2决策树的并行化通过分析发现，属性选择度量在决策树生成阶段是最为关键的任务，选取最佳分裂属性的阶段是整个决策树生成中占用计算资源最大的阶段。利用云计 算的 mapreduce 对这个阶段进行最大化的并行计算 是决策树算法并行化的突破口。由于信息增益率计算是基于属性间相互独立的，所以可以利用 mapreduce 并行地统计出计算增益率 所需要的各个属性的相关信息。最后，在主程序中可 以快速地计算增益率，并选取最佳分裂属性。具体设 计思想如下:1集产生的决策树( 如图 2)，简述 3 个关键函数的算法实现:表 1 allelectronic 顾客数据训练集2 2 1map 阶段设计思想map 阶段主要是对大规模数据按照划分条件进行切分，划分条件就是该节点在决策树中的路径。通 过实验证明，切分数据的时间几乎覆盖了整个程序运 行的时间。为此，本文提出的是基于层次切分数据的 广度优先生成多叉树算法。假设对训练集 d，划分在决策树的同一层的 n 个节点: d1 ，d2 ，dn ，必定满足:d d = d1 d2 dn其中，d为已生成叶节点的子训练集，且满足:d1 d2 dn = 那么，map 函数的主要任务就是以单个元组的形式分解数据，并以 key，value 的形式输出 d1 ，d2 ，dn 。其中 key 由子训练集的临时 nid ( 记为 i，则di 表示同一层次的第 i 个子训练集) ，决策表的某个属性 s，该元组对应属性 s 的值 s 以及该元组的所属决策类 c 组成的; value 值为 1 即可。2 2 2 reduce 阶段设计思想reduce 阶段的任务相对单一，即完成对 map 输出的 key，value 进行以相同 key 值的 value 值累 加得到 value-sum。同时，输出 key，value-sum 到 分布式文件系统 hdfs 中。对上述决策表有决策树模型:图 2 allelectronic 顾客数据训练集产生的决策树算法 2map( dataitem，q) 。输入: 训练数据集 d，条件集队列 q( map 以元组dataitem 的形式分解训练集 d) 。输出: key，value 组。( 1)( 2) ( 3)value = 1;if q 为空 thenfor 所有属性 dokey = 1 #属性号，对应属性值，所属类 ，( 4) else if条件 thenq 非空且 dataitem 满足 q 中第 i 个( 5) for 所有候选属性 do( 6)key = i#候选属性号，对应属性值，所属类2 2 3 ，value = 1;主程序的设计思想该阶 段 首 先 对 mapreduce 的 最 终 输 出 key，( 7)输出 key，value ridageincomestucreditbuy1youthhighnofairno2youthhighnoexcellentno3middlehighnofairyes4seniormediumnofairyes5seniorlowyesfairyes对于表 1 中数据，生成在决策树( 图 2 ) 第 3 层节( 4 )hash 表; ( 5)( 6)mapreduce读 取输 出 结 果 并 映 射 若 干点的 条 件 集 队 列 q 为 ( 1，youth ) ( 3，no ) ，( 1，ifq 为空 then i = 1 并跳至步骤( 7) ;youth) ( 3，yes) ，( 1，senior) ( 4，fair) ，( 1，senior) ( 4，excellent) ，该队列 q 对应的树模型如图 3 的虚框内:for i from 1 to | q |do / for 循环对 1 至 | q |号节点进行了最佳分裂属性的选取和类的决策。( i代表同一层次自左向右的第 i 节点，以下操作皆为对每个 hash 表中 nid 号为 i 的数据进行处理)( 7)if 划分数据为空then将划分条件 + 父节点多数类放入决策规则集 r;( 8) elseif 所有类同为类 c then 将划分条件 +类 c 放入决策规则集 r;( 9) elseif 划分条件长度 = 阈值 then 将划分条件 + 该节点的多数类放入决策规则集 r;( 10) else 计算各属性的增益率，取最大的作为 分裂属性，分别将划分条件 + 该属性的每个属性值依 次放入数据划分条件队列 q;( 11) end for;图 3 map 函数处理第三层数据map 函数利用虚框中条件集 q 分解整个训练集 d，对于 rid = 9 的元组: 因为该元组满足 q 中第 2 个 元素( 1，youth) ( 3，yes) ，所以把其归入 nid = 2 的节 点中，那么该元组的 key，value 组为 ( 2 #2，low， yes) ，1 ， ( 2 #4，fair，yes) ，1 ; 其它所有元组的 key，value 组依此类推得到。( 12) while( q 非空) 根据 allelectronic 顾客数据训练集，本算法通过实验输出的规则集 r 为: ( 1，middle: yes) ，( 1，youth 3，no: no) ，( 1，youth 3，yes: yes) ，( 1，senior 4，fair: yes) ，( 1，senior 4，excellent: no) 。算法 3reduce( key，value) 。4实验输入: map 输出的 key，value 组。输出: key，value-sum 组。( 1) for 所有相同 key 则 value-sum + = value;( 2) 输出 key，value-sum / key = ( nid #属性 号，属性值，类名) ; value-sum = 相同 key 的总数。根据之前 map 的输出得到，nid = 1 节点的 3 条数据对应的 map 输出的 key，value 组为 ( 1 #2， high，no) ，1 ， ( 1 #4，fair，no) ，1 ， ( 1 #2，high， no) ，1 ， ( 1 #4，excellent，no ) ，1 ， ( 1 #2，medi- um，no) ，1 ， ( 1 #4，fair，no) ，1 ; 那么 reduce 输 出的 key，value-sum 组为 ( 1 #2，high，no) ，2 ， ( 1#4，fair，no) ，2 ， ( 1 #4，excellent，no) ，1 ，( 1#2，medium，no) ，1 。其它所有节点的 key，val- ue 组依此类推得到。基于层次切分数据的广度优先生成多叉树算法:因为本算法是对传统算法实现并行化，算法对allelectronic 顾客数据集分类输出的决策规则集与传 统算法产生的决策树是一致的，并未改变传统决策树 算法的分类精确度，所以实验仅对算法的高效性和可 扩展性进行论证。软件环境: hadoop-0 20 2，ubuntulinux 9 04，jdk6 0。硬件环境: 7 台 pc 机，其中 1 台 master 和 6台 slave。每台的机器配置为: cpu p4，内存 512m，网卡 100m。实验数据来自 uci，具体描述如表 2 所示。表 2 nursery 数据集描述算法 4generating-decisiontree( d) 。为产生大规模数据，本实验采用了 nursery 数据输入: 大规模数据训练集 d。输出: 决策规则集 r。集复制的手段分别产生了 100m、300m、500m、800m、1g 的数据集，并分别在 1、2、4、6 台机器组成的集群运行，得到如图 4 的运行时间图。( 1)( 2) ( 3)模数据创建条件队列 q;do执行 mapreduce( d，q) ;/ 并行处理大规数据集特征:多变量元组数:12960领域:社会属性类型:离散属性个数:8捐献日期:1997-06-01缺失值:不包含web 点击量:2258930计 算 机与现代 化2012 年第 2 期图 6 不同机器数的加速比图 4 不同数据量的运行时间由于切分数据的 map 函数覆盖了程序运行的绝 大多数时间，其中决策树一层的节点越多切分数据的 时间就越长，图 5 是 1g 数据( 即 1 107 条数据) 在不 同层次的运行时间。在图 5 中，笔者发现在第 7 层的时候运行时间达 到最大，是因为此时的节点数是最多的。从第一层开 始每层的节点数分别为: 1、3、10、31、74、100、160、16、4。在图 5 中可以看到随着 slave 数的增加，各节点尤 其是第 7 层切分数据的时间得到大幅度下降。所以 随着属性值个数的增加引起同一层次节点数的增加，可以通过动态添加 slave 来提高算法的效率。因此本算法具有较高的可扩展性。5结束语传统的决策树算法是内存驻留算法，不能对海量数据进行决策分类。本文提出一种基于 mapreduce的大规模数据集决策树生成的算法，并将其运行在 hadoop 的云计算平台上，通过实验和分析发现，该算 法对大规模数据分类是高效可行的，具有较好的扩展 性，是可以处理大规模海量数据的。参考文献:1韩家炜，坎伯 数据挖掘概念与技术( 第 2 版) m 范明，孟小峰译 北京: 机械工业出版社，2007kumar v the top ten algorithms in data miningj knowl- edge and information systems，2008，14( 1) : 1-37quinlan j r induction of decision treej machine learn- ing，1986，1( 1) : 81-106quinlan j r c45: programs for machine learningm morgan kaufmann publisher，1993: 27-48shafer j，agrawal r，mehta m sprint: a scalable parallel classifier for data miningr research report ibm alma- den research center，san jose，california，1996: 544-555刘鹏 云计算m 北京: 电子工业出版社，2010 陈康，郑纬民 云计算: 系统实例与研究现状j 软件 学报，2009，20( 5) : 1337-1348jeffrey d，sanjay g mapreduce: simplied data processing onlarge clustersc/ proceedings of the 6th sympesium on op- erating system design and implementation 2004: 137-150 ghemawat s，gobioff h，leung s