基于粒计算的决策树并行算法的应用

周 浩，刘 萍，邱桃荣，白小明

（南昌大学 计算机科学与技术系，江西 南昌330031）

0 引 言

现已有许多研究学者对传统的决策树算法进行了改进，但是他们大部分的改进只是为了提高分类精度，并未解决算法在处理海量数据挖掘时产生的延时问题。决策树算法和当前比较流行的云平台Hadoop的结合是解决这一问题的有效途径之一。

Zadeh引入了信息粒度化的思想［1］，粒度化的本质其实就是聚类，所以它已被广泛应用于海量数据挖掘和复杂问题处理等方面。本文将粒计算引入，结合Hadoop平台，提出了一种ID3决策树分类算法。通过使用UCI标准数据集以及真实的雷电数据进行多次测试，测试结果表明，本文算法实用有效，能很好解决传统算法在处理海量数据挖掘时产生的延时问题。

1 MapReduce相关技术

MapReduce是一个分布式框架［2］，主要由编程模型和运行时环境这两部分组成。其中编程模型为用户提供了非常易用的编程接口，用户只需要像编写串行程序一样实现两个简单的函数 （map函数和reduce函数）即可实现一个分布式程序，而其它比较复杂的工作比如说节点的失效、数据的切分和节点之间的通信等，都是由运行时环境来完成。

MapReduce通过把海量数据集划分成多个不同的小数据集然后交给搭建好的Hadoop集群中的各个计算机进行处理来实现并行化。MapReduce编程模型［3］将问题抽象成Map和Reduce两个阶段。每个阶段都是以＜key，value＞对作为输入和输出，而key和value的类型是可以由程序员自己定义或选择的。其中Map 阶段将数据解析成＜key，value＞对，迭代调用用户编写的map函数之后再以＜key，value＞的形式输出到本地目录；Reduce阶段则将key相同的value进行规约处理，并将最终结果写到Hadoop分布式文件系统上 （Hadoop distributed file system，HDFS）上。其计算流程［4］如图1所示。

图1 MapReduce计算流程

2 基于粒计算的属性信息增益获取

2.1 粒的二进制表示

给定信息系统 （决策表）S＝（U，C∪D），其中条件属性集C ＝｛c1，c2，…，cm｝，不失一般性设决策属性只有一个，即D ＝｛d｝。对任意一个属性ci∈C，i＝1，2，…，m，其中有离散属性值的个数为ki，i＝1，2，…，m 个，那么以等价关系Ind（ci）可将U 划分成ki个互不相交等价类，即构成ki个信息粒。设决策属性有h 个决策值，即有h 个不同的类型，那么就可以把U 划分为h 个两两不相交的等价类，这h个等价类即为h 个信息粒。

用m 位二进制串来表示的信息粒称为二进制信息粒［5］，m 为论域中对象的个数。若一个个体属于该信息粒，那么就把该二进制串中的相应位的值置为1，否则置为0。该信息粒的粒度即为该二进制串中所包含的1的个数。

2.2 基于二进制信息粒的关联矩阵与属性信息增益

2.2.1 两个具有不同属性的二进制信息粒之间的关联运算

任意两个不同属性ci∈C，cj∈C，i≠j下对应的两个二进制信息粒分别为cit，t∈｛1，2，…，ki｝和cjs，s∈｛1，2，…，kj｝，它们之间的关联运算用符号∧表示，设运算结果所得到的信息粒用符号g表示，记为g＝cit∧cjs，该运算结果对应的二进制串是两个二进制信息粒的二进制串之间的与运算，即有（g）b＝（cit）b∧（cjs）b。

2.2.2 二进制信息粒向量

由属性ci∈C，i＝1，2，…，m 对论域U 进行粒化所构成的ki个信息粒，并且每个信息粒以二进制表示，即形成ki个二进制信息粒的集合称为属性ci的二进制信息粒向量，简记为［ci］＝［ci1，ci2，…，ciki］。

2.2.3 二进制信息粒关联矩阵

由任一条件属性ci∈C，i＝1，2，…，m 所构成的ki个二进制信息粒与决策属性d 所构成h 个二进制信息粒向量之间进行关联运算，即建立如下关联矩阵［5］

该关联矩阵对应的二进制串矩阵表示记为

属性ci的信息增益计算

经过整理变为

3 基于MapReduce和粒计算的决策树生成算法

3.1 决策树分类的并行化设计思想

（1）二进制信息粒关联矩阵的并行化计算。通过设计实现一个Map函数和Reduce函数可以实现计算决策树中任一结点下的关联矩阵，以便为后续计算属性信息增益提供数据。

（2）决策树的任何分支结点进行最佳分裂属性选择的并行化计算。

3.2 两阶段MapReduce函数的设计

本文采用数据和任务两种并行方式［7－10］，在训练阶段用了两个MapReduce任务，第一个MapReduce任务是数据处理的并行化，对读入的数据生成＜key，value＞对，用于计算相应的二进制信息粒关联矩阵，便于后续阶段计算属性的信息增益大小。第二个MapReduce任务对树的分枝结点并行计算出每一个子数据集的最佳分裂属性，然后根据输出结果生成决策规则或者构建一层决策树。训练阶段的两个MapReduce任务迭代执行，直至构建出满足约束条件的决策树。在测试阶段用了一个MapReduce任务，读入测试集的数据并根据已经生成的决策规则进行分类，计算出相应的分类准确率。

具体的两个阶段Map函数和Reduce函数设计［11－13］简要描述如下：

算法1：TrainDataMap （）

算法2：TrainDataReduce （＜key，value＞，＜key’，value’＞）

/＊说明：这个阶段完成对具有相同key值的数据进行统计，即在每个决策树结点下，计算二进制信息粒关联矩阵中的每个元素。

算法3：DecisionMap （＜key，value＞，＜key’，value’＞）

/＊说明：在已经生成某结点下的关联矩阵后，将计算各候选属性的信息增益，以便确定最佳分裂属性。

算法4：DecisionReduce （＜key，value＞，＜key’，value’＞）

3.3 剪枝处理

通过判断sum ≤σ是否成立？σ是事先确定的最小记录剪枝数据。

如果成立，则对结点不再进行分枝，该结点即为叶子结点，取集合中具有最多的决策值作为该结点的决策类别，输出＜结点号，决策值＞。

否则找出min｛si｝的那个属性，设为cf，作为最佳分裂属性。

4 实验分析

4.1 测试环境

软件环境：Hadoop－1.0.4，Ubuntu Linux 10.04.4，Jdk1.6.0＿41。

硬件环境：4 台PC 机，其中1 台为master，3 台为slave。Master的配置为：CPU Pentium T4200 （双核），内存2G，网卡10Mbps，每台slave 的配置为：CPU AMD A10－5800K （四核），内存2G，网卡10Mbps。

4.2 测试数据

测试数据取自两个领域：一是使用公共测试数据，即采用UCI（http：//archive.ics.uci.edu/ml/datasets.html）［14］的一些数据集，见表1；二是采用实际气象领域的真实数据集。

4.3 测试结果与分析

4.3.1 算法准确率的测试

本文在测试分类准确性时，从原始数据集中随机选取90%的数据作为训练集建立决策树，选择10%的数据作为测试集，对每个数据集都重复测试10次，取平均值作为测试准确率。测试结果见表2。

采用本并行算法与文献 ［15］的算法的准确率比较结果见表3。

表1 UCI数据集信息

表2 准确率测试结果

表3 准确率比较结果

从比较结果可以看出本文算法优于文献 ［15］的算法。

此外，本文还对来自于江西省气象局的2010年4月20日0时的真实雷电数据进行了测试，由于真实的雷电数据都是连续型数据，所以在做测试之前运用了基于信息熵的离散化方法对数据集进行了离散化。数据集描述见表4。

表4 雷电数据信息描述

测试方法是随机提取该数据集中的30%作为测试数据。其余全部作为训练集。重复10次这样的测试，取最后的平均值作为准确率。测试结果见表5。

由表5可知，本文算法对真实的雷电数据的预测准确率也有95%，说明本文算法是具有实际应用价值的。

表5 雷电数据准确率测试结果

4.3.2 算法运行时间测试及加速比

实验数据来自UCI机器学习数据库中的若干标准数据集，为产生大规模数据，本实验采用重复复制的手段将每个数据集放大到100M，300M，500M，1000M。并分别在slave为1台，2台，3台机器组成的集群上运行，运行时间和加速比测试结果如图2～图7所示。

图2 nursery数据集运行时间

图3 zoo数据集运行时间

图4 mushroom 数据集运行时间

从图2到图4可看出，在处理同一大小的数据集的时候，随着集群节点的增加，处理时间越来越短，因为MapReduce对数据的处理在默认的情况下是64M 为一个单位，所以在处理大于64M 的数据的时候都会把数据进行分块，然后分给各个节点并行处理，可想而知，当节点越多，一次性处理的块数就越多，这样处理完整个数据集的时间就越短。

图5 nursery数据集加速比

图6 zoo数据集加速比

图7 mushroom 数据集加速比

从图5到图7中我们还可以发现，在处理100M 的数据集的时候，1个节点，2个节点和3个节点的集群的处理时间都差不多 （加速比在1 附近），而在处理1000M 的数据集的时候处理时间却差别很大，加速比几乎呈一条直线，这说明本文算法可以用来解决海量数据挖掘问题。

5 结束语

本文提出了一种基于粒计算的ID3 算法，并且在Hadoop平台上对其进行了并行化研究。对提出的并行化算法用UCI数据集和真实的雷电数据进行多次的测试分析，测试结果表明该算法具有较好的分类正确率、有效性和实用性，适用于处理规模较大的数据集。由于本文着重研究算法的并行化方法，所以本文的算法并未解决传统的ID3算法选择属性取值较多的属性作为分裂属性这一缺点，这有待于后续的改进。另外，还要进一步开展包括算法的优化和基于增量的并行化处理等方面的研究。

［1］ZHANG Sulan，GUO Ping，ZHANG Jifu，et al.Automatic semantic image annotation with granular analysis method ［J］.Acta Automatica Sinica，2012，38 （5）：689－690 （in Chinese）.［张素兰，郭平，张继福，等.图像语义自动标注及其粒度分析方法 ［J］.自动化学报，2012，38 （5）：689－690.］

［2］DONG Xicheng.Hadoop internals：In－depth study of MapReduce［M］.Beijing：China Machine Press，2013：32－34 （in Chinese）.［董西成.Hadoop技术内幕：深入解析MapReduce架构设计与实现原理 ［M］.北京：机械工业出版社，2013：32－34.］

［3］Lam C.Hadoop in action ［M］.Beijing：Posts and Telecom Press，2011：37－49 （in Chinese）. ［Lam C.Hadoop 实战［M］.北京：人民邮电出版社，2011：37－49.］

［4］White T.Hadoop：The definitive guide［M］.Beijing：Tsinghua University Press，2011：28－31 （in Chinese）. ［White T.Hadoop权威指南 ［M］.北京：清华大学出版社，2011：28－31.］

［5］XU Jianfeng，LIU Lan，QIU Taorong，et al.Binary system matrix based on Ganular computing and its applications in decision－tree［J］.Journal of Guangxi Normal University，2008，26 （3）：158－159 （in Chinese）. ［徐剑锋，刘斓，邱桃荣，等.基于粒计算的二进制矩阵及在决策树算法的应用 ［J］.广西师范大学学报，2008，26 （3）：158－159.］

［6］JIANG Shengyi，LI Xia，ZHENG Qi.Principles and practice of data mining ［M］.Beijing：Publishing House of Electronics Industry，2011：52－53 （in Chinese）.［蒋盛益，李霞，郑琪.数据挖掘原理与实践 ［M］.北京：电子工业出版社，2011：52－53.］

［7］XING Xiaoyu.Research and application of parallel decision tree classification algorithm ［D］.Kunming：Yunnan University of Finance and Economics，2010：25－29 （in Chinese）.［邢晓宇.决策树分类算法的并行化研究及其应用 ［D］.昆明：云南财经大学，2010：25－29.］

［8］PAN Tianming.Research of the parallel decision tree algorithm based on Haddop ［D］.Shanghai：East China Normal University，2012：30－33 （in Chinese）.［潘天鸣.基于Hadoop平台的决策树算法并行化研究 ［D］.上海：华东师范大学，2012：30－33.］

［9］ZHU Min.Research and implementation of parallel decision tree classification algorithm based on MapReduce ［D］.Nanchang：Jiangxi Normal University，2011：13－14 （in Chinese）.［朱敏.基于MapReduce的并行决策树分类算法研究与实现［D］.南昌：江西师范大学，2011：13－14.］

［10］Alham N K，Li Maozhen，Liu Yang.A MapReduce－based distributed SVM algorithm of automatic image annotation ［J］.Computers and Mathematics with Applications，2011，62（7）：2801－2811.

［11］QIAN Wangwei.Research of the ID3decision tree classification algorithm based on MapReduce ［J］.Computer and Modernization，2012，28 （2）：28－29 （in Chinese）. ［钱网伟.基于MapReduce的ID3决策树分类算法研究 ［J］.计算机与现代化，2012，28 （2）：28－29.］

［12］Wu G，Li H，Hu X，et al.MReC4.5：C4.5ensemble classification with MapReduce ［C］//ChinaGrid Annual Conference.IEEE，2009：249－255.

［13］He Q，Zhuang F，Li J，et al.Parallel implementation of classification algorithms based on MapReduce ［M］.Rough Set and Knowledge Technology.Springer Berlin Heidelberg，2010：655－662.

［14］Lichman K B A M.｛UCI｝machine learning repository ［DB/OL］.University of California，Irvine，School of Information and Computer Sciences.http：//archive.ics.uci.edu/ml，2013－04－26.

［15］LU Qiu.Parallelization of decision tree algorithm based on MapReduce［J］.Journal of Computer Applications，2012，32 （9）：2465－2465 （in Chinese）. ［陆秋.基于MapReduce的决策树算法并行化 ［J］.计算机应用，2012，32 （9）：2465－2465.］