首页资源分类DSP > 基于Hadoop平台的C4_5算法的分析与研究

基于Hadoop平台的C4_5算法的分析与研究

已有 451559个资源

下载专区

文档信息举报收藏

标    签:Hadoop平台的C4_5算法

分    享:

文档简介

Hadoop平台的C4_5算法

文档预览

第 24 卷 第 11 期 2014 年 11 月 计算机技术与发展 COMPUTER TECHNOLOGY AND DEVELOPMENT Vol. 24 No. 11 Nov. 2014 基于 Hadoop 平台的 C4. 5 算法的分析与研究 孙 媛,黄 刚 ( 南京邮电大学 计算机学院,江苏 南京 210003) 摘 要: 如何能从海量数据中以更快速、高效、低成本的方式挖掘出有价值的信息成为如今数据挖掘技术面临的新课题。 文中在研究 Hadoop 平台的特征和决策树的 C4. 5 算法的过程中,决定在决策树算法领域中引入云计算思维,实现其在 Ha- doop 平台上的并行化,并且采用 MapReduce 模型来解决海量数据挖掘问题。最后用打高尔夫球的数据集对新的算法进行 验证。实验结果表明对海量数据,基于 Hadoop 平台的决策树算法可以明显提高数据挖掘的效率,具有可观的高效性和可 扩展性,在一定程度上解决了 C4. 5 算法在处理海量数据时计算量大、构建决策树时间长的问题。 关键词: Hadoop; MapReduce; 数据挖掘; C4. 5 算法 中图分类号: TP301. 6 文献标识码: A 文章编号: 1673-629X( 2014) 11-0083-04 doi: 10. 3969 / j. issn. 1673-629X. 2014. 11. 021 Analysis and Study of C4. 5 Algorithm Based on Hadoop Platform SUN Yuan,HUANG Gang ( School of Computer,Nanjing University of Posts and Telecommunications, Nanjing 210003,China) Abstract: How can dig out the valuable information from the vast amount of data in a more rapid,efficient and low -cost w ay now become a new task faced by the data mining technology. In this paper,in the study of the characteristics of the Hadoop platform and the process of decision tree C4. 5 algorithm,decide to introduce the cloud computing thinking to the field of decision tree algorithm,achieve its parallelization on Hadoop platform and use MapReduce model to solve the problem of massive data mining. Finally w ith using a round of golf data sets to verify this new algorithm,the results of the experiments show that for the huge amounts of data,the decision tree algorithm based on Hadoop platform can significantly improve the efficiency of data mining. It has a good efficiency and scalability. In a certain extent,it also solves the problems of computing huge amounts of data and building the decision tree taking long time that C4. 5 algorithm faced w hen dealing w ith large amount of calculation. Key words: Hadoop; MapReduce; data mining; C4. 5 algorithm 0引言 随着计算机技术 和 互 联 网 技 术 的 快 速 发 展 ,数 据 量也以指数级规模 飞 速 增 长 ,进 而 演 变 成 今 天 众 所 周 知的超大规模的数据量。这些海量数据中有很多对商 家而言可以称之为巨额财富的商业信息,因此通过高 效的数据挖掘技术将这些数据挖掘出来,以实现其该 有的价值成为当今数据挖掘行业的需求热点。但是这 对于现有 的 数 据 挖 掘 技 术 来 说 是 一 个 重 大 的 挑 战。 Hadoop 正是为了互联网时代的海量数据存储与处理 而设计、开发的。简单的说,Hadoop 是一个可以更容 易开发和并行处 理 大 规 模 数 据 的 分 布 式 计 算 平 台[1], 它的主要特 点 是 扩 展 能 力 强、成 本 低、高 效 率、可 靠。 目前 Hadoop 的用户已经从传统的互联网公司,扩展 到科学计算、电信行业、电力行业、生物行业以及金融 公司,并得到越来越广泛的应用。所以将 Hadoop 平台 与数据挖掘技术结合产生新的数据挖掘算法可以有效 地解决现有的数据挖掘算法在解决海量数据挖掘时所 体现出的弊端。 1 Hadoop 概述 Hadoop 起源于开源网络搜索引擎 Nutch,并且因 为借鉴了 Google 的 GFS[2]和 MapReduce 的设计思想而 收稿日期: 2013-12-22 修回日期: 2014-03-24 网络出版时间: 2014-09-11 基金项目: 国家自然科学基金资助项目( 61171053) 作者简介: 孙 媛( 1989-) ,女,硕士研究生,研究方向为信息网络与通信软件、海量数据管理; 黄 刚,教授,研究生导师,研究方向为计算机在 通信中的应用、海量数据管理、移动商务平台设计开发。 网络出版地址: http: / / www. cnki. net / kcms / detail /61. 1450. TP. 20140911. 1001. 023. html ·84· 计算机技术与发展 第 24 卷 日渐成熟,于 2008 年 1 月成为 Apache[3]的顶级开源项 目,并于 2011 年底发布 1. 0. 0 版本[4],说明该产品已 完全做好了应用于生产的准备。Hadoop 的基础架构 是利用集群威力 的 高 速 运 算[5] 和 存 储 分 布 式 系 统 ,即 使在不了解分布式底层细节的情况下,用户也可以自 行开发分布式程序[6]。作为一个开源的软件平台,Hadoop 使得编写和运行用于处理海量数据的应用程序 更加 容 易。 Hadoop 框 架 由 Java 语 言 编 写,运 行 在 Linux 操 作 系 统 之 上,由 Hadoop Common、HDFS、Hadoop MapReduce 核心部件组成。 最核 心 的 设 计 就 是 MapReduce 和 HDFS。而 由 Google 的一篇论文所提及而被广为流传的 MapReduce 思想,简单的一句话解释 MapReduce 就是任务的分解 与结果的汇总。HDFS 是 Hadoop 分布式文件系统 Hadoop Distributed File System 的缩写,为分布式计算存储 提供了底层支持。从 MapReduce 的名字上就大致可 以看出其基本功能,两个动词 Map 和 Reduce,由 Map 将一个任务分解成为多个任务,然后 Reduce 将分解后 的多任务 处 理 结 果 汇 总 起 来,得 到 最 终 的 分 析 结 果。 在分布式系统中,可以将机器集群看作硬件资源池,并 行的任务被拆分后,交由空闲机器资源去处理,可以很 大地提高计算效率,并且由于资源无关性,扩展计算集 群得到了最好的设计保证。这样的功能划分使得 MapReduce 非常适合在大量计算机组成的分布式并行环 境里进行数据处理[7]。HDFS 的高容 错 性、高 伸 缩 性 的特点,允许用户部署在低廉的硬件上,而且它提供高 传输率来访问应用程序的数据。HDFS 简化了文件的 一致性模型,通过流式数据访问,提供高吞吐量应用程 序数据访问功能,适合那些有着超大数据集的应用程 序,所以得到了 Yahoo、Amazon 和 Face book 等大型公 司的广泛应用。 2 数据挖掘概述 数据挖掘 的 产 生 与 数 据 库 技 术 发 展 是 息 息 相 关 的,可以把它看作 是 信 息 技 术 自 然 演 化 的 结 果 。 数 据 挖掘的概念出现在 20 世纪 80 年代中期,在 90 年代中 期获得快速发展,并在进入 21 世纪后继续繁荣演进。 “数据挖掘”可 以 说 是 从 大 量 数 据 中 提 取 或“挖 掘 ”知 识。而更正确的说法是“从数据中挖掘知识”,挖掘出 隐藏在数据中的使人感兴趣或者说有价值的知识,并 且可以通过不同的角度来观察或浏览它们。而那些被 发现的知识则可以被用于做决策、过程控制、信息管理 和查询处理。因此明确所要发现的是何种知识是整个 数据挖掘过程中第一个也是最重要的一个阶段。 广义上认为数据 挖 掘 是 从 存 放 在 数 据 库 、数 据 仓 库或其他信息库中的大量数据中发现有趣知识的过 程。所以典型的数据挖掘系统包含了数据库、数据仓 库、万维网或其他信息库、数据库或数据仓库服务器、 知识库、数据挖掘引擎、模式评估模块、用户界面等几 个主要成分,如图 1 所示。 图 1 典型数据挖掘系统的结构 在实践中,数据挖掘的两个基本目标往往是预测 和描述。预测通常是指可以利用数据集中的一些变量 或域,对所关心的变量进行预测,预测其所具备的其他 的未知或未来的值。而描述的重点则是找出描述可由 人类解释的数据模式。因此,数据挖掘活动可以分成 预测性数据挖掘和描述性数据挖掘。在预测领域的后 期,数据挖掘的目标是得出一种以可执行码来表示的 模型。可以将这种可执行码用于执行分类、预测、评估 或者其他相似的任务。而描述性领域的后期,数据挖 掘的目标是利用大型数据集中的未知模式和关系获得 对所分析系统的理解。对特定的数据挖掘的应用,预 测和描述的相对意义有相当大的变化。预测和描述的 目标都是通过数据挖掘技术来实现的[8]。 3 决策树 C4. 5 算法及其并行化 决策树( Decision Tree) 是指在对数据进行决策分 类时按照树的结构 将 数 据 记 录 进 行 分 类 ,其 中 树 的 每 个叶节点都代表符 合 某 个 条 件 的 属 性 集 ,根 据 属 性 的 不同取值建立决策树的各个分支; 随后递归地构造每 个子节点的子树[9]。以一种类似流程图的树结构( 如 图 2 所示) 展现在人们眼前,便于理解和接受,因此决 策树算法是数据挖掘分类算法中非常重要的一个算法 分支[10]。 3. 1 C4. 5 算法简介 C4. 5 算法是在保留 ID3 优点的基础上针对其不 第 11 期 孙 媛等: 基于 Hadoop 平台的 C4. 5 算法的分析与研究 ·85· 足之处做了一些改进以后得到的算法[11]。和 ID3 算 法 相 比,在 选 择 分 裂 属 性 上 没 有 采 用 信 息 增 益[12],而 是采用信息增益率作为标准。这是为了去除高分支属 性的影响而对信息增益的一种改进。信息增益的方法 同时考虑了每一次花费你所产生的子节点的个数和每 个子节点的大小( 包括数据实例的个数) ,考虑的对象 主要是一个个的划 分,而 不 再 考 虑 分 类 所 蕴 含 的 信 息 量。 计算公式为 GainRatio( A) = Gain( A) / SplitI( S1 ,S2 ,…,Sv ) ( 1) v ∑ SplitI( S1 ,S2 ,…,Sv ) = pj lb( pj ) ( 2) j=1 其中,v 为该节点的分支数; Sv 为第 v 分支下记录 的个数。 图 2 决策树生成操作流程 主要介绍 的 是 通 过 数 据 预 处 理[13] 得 到 训 练 集 再 对数据集进行归纳得到最初的决策树的过程: ( 1) 对数据源进行数据预处理,去掉与决策树无 关的属性和高分支 属 性 ,将 数 值 型 属 性 进 行 归 纳 概 化 以及处理包含空缺值的属性,形成决策树的训练集。 ( 2) 在对训练集进行训练时,计算每个属性的信 息增益 Gain( A) 和信息增益率 Gain Ratio( A) ,选择信 息增益率最大的且同时获取的信息增益又不低于所有 属性平均值的属性,作为当前的主属性节点,为该子节 点所包含的样本自己递归地执行上述过程,直到子集 中的数据记录在主属性上取值都相同,或没有属性可 供再划分使用为止,生成初始的决策树[14]。 3. 2 C4. 5 算法 MapReduce 化 根据 MapReduce 的工作原理[15]以及 C4. 5 算法的 特点,主要改进的是 计 算 每 个 属 性 的 信 息 增 益 和 信 息 增益率这个过程,因为这样一个个计算会浪费大量的 时间与效率,所以可以借助 Hadoop 的并行特点改进 C4. 5 算法,将计算信息增益以及信息增益率的过程并 行化,得到并行化以后的算法 C4. 5bH ( C4. 5 based on Hadoop) ,将这个计算过程所花费的时间大大缩短,达 到提高数据挖掘的效率的目的。 Map 阶段主要负责找出所需要的信息,并将其作 为输出发送,然后 map 函数的输出会由 MapReduce 框 架处理。主要处理过程就是根据键来对键值对进行排 序和分组,然后将属于同一个键的键值对分发给一个 reduce 函数,然后由 reduce 函数输出所需要的结果,在 reduce 阶段,对具有连续属性值的数据集进行排序,但 是对具有离散属性值的数据集就可以不进行排序。文 中主要涉及三个 MapReduce 作业,第一个 MapReduce 作业主要负责计算所有节点的信息增益,第二个 MapReduce 作业主 要 负 责 计 算 所 有 节 点 的 平 均 信 息 增 益,第三个 MapReduce 作业主要负责计算所有节点的 信息增益率; 然后将上述的三个 MapReduce 作业的输 出存放在一个表格中,并且以信息增益率的降序进行 排列; 最后找出信息增益率最大且不低于平均信息增 益的属性节点作为最终的划分节点。 改进的 C4. 5 算法的伪代码如下: Function C4. 5bH( R,S,C ) / / 建立一个决策树 / / R : 除目标属性外的所有属性; C : 目标属性; S : 一个训练集 Begin if S is empty then return 一个值为 failure 的节点; if 训练集 S 中所有记录的目标属性 为 同 一 个 a then return 具有值为 a 的节点; if R 为空 then return 一个节点,节点的值为训练集中目标属性 中出现最多的目标属性; for R 中的每个属性 Ri do GainMapper 函数; GainReducer 函数; AGainMapper 函数; AGainReducer 函数; GainRatioMapper 函数; GainRatioReducer 函数; 将上述的三个 MapReduce 作业的输 出 存 放 在 一 个表格中,并且以信息增益率的降序进行排列,找出信 息增益率最大且不低于平均信息增益的属性节点作为 最终的划分节点 end; D 为 R 属性具有最大 Gain( D,S ) 的属性; D 的属性值为{ dj | j = 1,2,…,m } ; S 的子集{ Sj | j = 1,2,…,m } 各自包含属性 D 的 值为 dj 的记录; return 根节点标记为 D 树和到 d1 ,d2 ,…,dm 的弧; ·86· 计算机技术与发展 第 24 卷 C4. 5( R - { D} ,C,S1 ) ,C4. 5 ( R - { D} ,C,S2 ) , …,C4. 5( R - { D} ,C,Sm ) ; end 4 实验与结果分析 将基于 Hadoop 平台下的 C4. 5 算法的并行化算法 在打高尔夫球的训练数据集上做了实验,其分布如表 1 所示。实验主要是为了验证优化以后的算法的高效 性和扩展性。用来判断某种天气是否适合打高尔夫。 该数据集属于天气领域的,所以包含了 Outlook、Temperature、Humidity 和 Windy 这 四 个 属 性。没 有 缺 省 值,所以被用来完成分类任务。 实验环境: 5 台 PC 机( 其中 1 台主机,4 台从机) , 采用 SUSE 以及 Hadoop,Eclipse,JDK。 表 1 打高尔夫球的训练数据集 Outlook Sunny Sunny Overcast Rain Rain Rain Overcast Sunny Sunny Rain Sunny Overcast Overcast …… Temperature Humidity 85 85 80 90 83 78 70 96 68 0 65 70 64 65 72 95 69 70 75 80 75 70 72 90 81 75 …… …… Windy False True False False True True False False False True True True False …… Class: Play No No Yes Yes No No Yes No Yes Yes Yes Yes Yes …… 根据这些属性对天气是否适合打高尔夫进行评 估,将天气分为适合打高尔夫和不适合打高尔夫,训练 产生的决策树模型如图 3 所示,用此模型对数据进行 分类。 图 3 最终打高尔夫决策树图 实验内容: 通过 distcp 复制的手段将数据集分割, 然后通过实验测试相同节点数量不同大小的数据集的 运行时间,以及相同 大 小 数 据 集 不 同 数 量 的 节 点 数 的 运行时间。运行结果统计如表 2 所示。 表 2 运行结果统计表 节点数 1 1 2 3 1 数据集 A B B B C C4. 5 / s 0. 31 292. 00 211. 00 139. 00 160. 00 C4. 5bH / s 0. 23 233. 00 155. 00 110. 00 103. 00 由表 2 可知,虽然都是用一个节点进行测试,但是 采用 MapReduce 并行化以后的 C4. 5bH 算法的运算时 间明显缩短了。从并行角度看,随着节点数量的增加, 算法的时间复杂度降低,说明了将 C4. 5 算法进行并 行化是可行的,也说明了优化以后的算法具有可观的 高效性和可扩展性。 5 结束语 决策树算法的并行化是如今解决海量数据挖掘的 重点,而 C4. 5 算法在决策树算法中占有重要地位,如 何将 C4. 5 算 法 并 行 化 是 一 项 重 要 的 课 题。文 中 在 C4. 5 算法的基础上提出了基于属性划分的决策树算 法,并将其应用在 Hadoop 平台构建了一种并行性能良 好的决策树算法 C4. 5bH。实验结果表明 C4. 5bH 算 法具有较好的并行性能、较低的时间复杂度以及可观 的高效性和可扩展性。 参考文献: [1] Liu Yang,Li Maozhen,Alham N K. HSIM: A MapReduce sim- ulator in enabling cloud computing[EB / OL]. [2012 - 01 - 20]. http: / / www. sciencedirect. com / science / article / pii / S0167739X11000884. [2] Ghemawat S,Gobioff H,Leung S T. The Google file system [C]/ / Proceedings of the 19th ACM symposium on operating systems principles. New York: ACM Press,2003: 29-43. [3] 周 婷,张君瑛,罗 成. 基于 Hadoop 的 K-means 聚类算 法的实现[J]. 计算机技术与发展,2013,23( 7) : 18-21 [4] 张明辉. 基于 Hadoop 的数据挖掘算法的分析与研究[D]. 昆明: 昆明理工大学,2012. [5] Alham N K,Li Maozhen,Liu Yang,et al. A MapReduce - based distributed SVM algorithm of automatic image annotation[J]. Computers and Mathematics with Applications,2011, 62( 7) : 2801-2811. [6] 陈 康,郑纬民. 云计算: 系统实例与研究现状[J]. 软件学 报,2009,20( 5) : 1337-1348. [7] 洑云龙. 云计算平台下的数据挖掘研究[D]. 南京: 南京邮 电大学,2013. [8] 康塔尼克. 数据挖掘: 概念、模型、方法和算法[M]. 北京: ( 下转第 90 页) ·90· 计算机技术与发展 第 24 卷 3. 2. 2 收敛精度不变,算法迭代进化次数分析 实验,并与相关文献中的改进算法进行比较分析,结果 3 个标准函数采用 SFLA1、SFLA2、CA - SFLA1 和 表明文中提出的算法具有更好的优化性能,并且在优 CA-SFLA2 独立运行 30 次,达到表 1 要求精度的迭代 化高维多峰函数方面具有较好的效果。 次数( 最大迭代次数取 500) 。其中,成功率为达到要 求精度的迭代次数与实验总次数( 30) 的比值。从表 3 参考文献: 中可以看出: CA -SFLA1 和 CA -SFLA2 对 3 个标准函 数的成功率明显好于 SFLA1 和 SFLA2; CA-SFLA2 对 3 个标准函数取得 70% ~ 100% 的成功率,是 4 种算法 中最高的。从达到固 定 优 化 精 度 的 平 均 迭 代 次 数 、最 小迭代次数和最大迭代次数 三 个 指 标 来 看,CA - SFLA2 都是最好的,优化成功率高、收敛速度快,且具有 较好的稳定性。 表 3 收敛精度不变的实验结果 [1] 齐仲纪,刘漫丹. 文化算法研究[J]. 计算机技术与发展, 2008,18( 5) : 126-130. [2] 兰成章,高洪元,李诗桓. 基于差分文化算法的 FIR 数字滤 波器设计[J]. 自动化技术与应用,2010,29( 6) : 65-68. [3] ChentoufiA J,El Imrani A A,Bouroumi A. A multipopulation cultural algorithm using fuzzy clustering[J]. Applied Soft Computing,2007,7( 2) : 506-519. [4] Vitale K,Reynoldsa R,O’Sheab J,et al. Exploring ancient landscapes under lake Huron using cultural algorithms[J]. 函数 f1 算法 SFLA1 SFLA2 CA-SFLA1 CA-SFLA2 SFLA1 成功 率/% 90 93 95 100 10 平均迭 代次数 375 354 79 66 445 最小迭 代次数 245 248 46 34 362 最大迭 代次数 496 406 284 235 498 Procedia Computer Science,2011,6: 303-310. [5] Eusuff M M,Lansey K E. Optimization of waterdistribution network design using the shuffled frog leaping algorithm[J]. Journal of Water Resources Planning and Management,2003, 129( 3) : 210-225. [6] 李 鑫. 基于混合进化的 SFL 算法及其应用[D]. 保定: 河 北大学,2010. [7] 赵鹏军,刘三阳. 求解复杂函数优化问题的混合蛙跳算法 SFLA2 30 f2 CA-SFLA1 50 CA-SFLA2 70 SFLA1 0 SFLA2 0 f3 CA-SFLA1 50 CA-SFLA2 70 395 343 422 362 156 408 203 92 365 - - - - - - 265 213 434 99 60 140 [J]. 计算机应用研究,2009,26( 7) : 2435-2437. [8] 代永强,王联国. 带记忆功能的混合蛙跳算法[J]. 计算机 工程与设计,2011,32( 9) : 3170-3173. [9] 王奕首,艾景波,史彦军,等. 文化粒子群优化算法[J]. 大 连理工大学学报,2007,47( 4) : 539-544. [10] Passino K M. Biomimicry of bacterial foraging for distributed optimization and control[J]. IEEE Control Systems,2002,22 ( 3) : 52-67. [11] Mehrabian A R,Lucas C. A novel numerical optimization algo- 4 结束语 从进化角度来分 析 ,任 何 一 种 进 化 算 法 都 可 以 嵌 入到文化算法框架中,作为种群空间的进化过程,但就 目前来看,这方面的研究内容还不是太多,基于混合蛙 跳算 法、细 菌 觅 食 算 法[10]、杂 草 算 法[11] 和 猫 群 算 法[12 -14]等的文化算法的研究还没有真正开展。文中 rithm inspired from weed colonization [J]. Ecological Informatics,2006,1( 4) : 355-366. [12] 王光彪,杨淑莹,冯 帆,等. 基于猫群算法的图像分类研 究[J]. 天津理工大学学报,2011,27( 5) : 35-39. [13] 范凯波. 基于几何特征的车辆目标分类研究[D]. 天津: 天 津理工大学,2012. [14] 邢文训,谢金星. 现代优化计算方法[M]. 北京: 清华大学 提出的文化蛙跳算法,通过对 3 个标准函数进行优化 出版社,2005. 檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪 ( 上接第 86 页) 掘算法[J]. 中南大学学报: 自然科学版,2003,34( z1) : 69- 清华大学出版社,2003. 71. [9] 潘天鸣. 基于 Hadoop 平台的决策树算法并行化研究[D]. [13] Li Wenlong,Xing Changzheng. Parallel decision tree algorithm 上海: 华东师范大学,2012. based on combination[C]/ / Proc of international forum on in- [10] 唐华松,姚耀文. 数据挖掘中决策树算法的探讨[J]. 计算 formation technology and applications. Kunming: IEEE,2010: 机应用研究,2001,18( 8) : 18-19. 99 - 101 . [11] 朱 敏,万剑怡,王明文. 基于 MR 的并行决策树分类算法 [14] 王 晖,王 琪,何 琼. 数据挖掘理论与实例[M]. 北京: 的设计与实现[J]. 广西师范大学学报: 自然科学版,2011, 经济科学出版社,2012. 29( 1) : 82-84. [15] 李远方,贾时银,邓世昆,等. 基于树结构的 MapReduce 模 [12] 蒋良孝,蔡之华,刘 钊. 一种基于信息增益的分类规则挖 型[J]. 计算机技术与发展,2011,21( 8) : 149-152.

Top_arrow
回到顶部
EEWORLD下载中心所有资源均来自网友分享,如有侵权,请发送举报邮件到客服邮箱bbs_service@eeworld.com.cn 或通过站内短信息或QQ:273568022联系管理员 高进,我们会尽快处理。