并行大数据清洗过程优化范文

《计算机学报》2016年第一期

摘要

数据质量问题会对大数据的应用产生致命影响，因此需要对存在数据质量问题的大数据进行清洗．MapReduce编程框架可以利用并行技术实现高可扩展性的大数据清洗，然而，由于缺乏有效的设计，在基于MapReduce的数据清洗过程中存在计算的冗余，导致性能降低．因此文中的目的是对并行数据清洗过程进行优化从而提高效率．通过研究，作者发现数据清洗中一些任务往往都运行在同一输入文件上或者利用同样的运算结果，基于该发现文中提出了一种新的优化技术———基于任务合并的优化技术．针对冗余计算和利用同一输入文件的简单计算进行合并，通过这种合并可以减少MapReduce的轮数从而减少系统运行的时间，最终达到系统优化的目标．文中针对数据清洗过程中多个复杂的模块进行了优化，具体来说分别对实体识别模块、不一致数据修复模块和缺失值填充模块进行了优化．实验结果表明，文中提出的策略可以有效提高数据清洗的效率．

关键词

大数据；多任务优化；海量数据；数据清洗；Hadoop；MapReduce

1引言

本节主要介绍研究背景及其意义、海量数据清洗系统、本文优化方法的主要思想、本文的贡献与结构．

1．1研究背景及其意义现今企业的成功和社会的进步，越来越依赖于数据和对其所做的分析．为了获得竞争优势即使是小企业也会投入时间和精力来收集和分析数据．很多大公司都部署了自己的云服务平台，国内比较著名的有百度云、阿里云、天翼云①等．但是如果一味地将精力投入到对数据所做的分析而不关注数据本身，很可能产生灾难性的后果．统计表明，美国企业中1％～30％的数据存在各类错误和误差［1］，医疗数据库中13．6％～81％的关键数据不完整或陈旧［2］．根据市场研究公司Gartner的调查，全球财富1000强公司超过25％的关键数据不正确或不准确［3］．数据质量问题会使基于其的分析和研究毫无意义甚至还会产生灾难性的后果，在美国由于数据错误引起的医疗事故每年使98000名患者丧生［4］．上述实例表明数据质量问题存在于社会生活的方方面面，数据清洗系统应运而生．在海量数据处理领域，MapReduce编程框架作为当下最流行的并行编程开发框架已被Google、Amazon、Yahoo！、Facebook以及国内的腾讯、阿里巴巴等大型互联网公司奉为至宝．将Hadoop用于海量数据处理主要有如下优势：易用性、高可扩展性、高容错性．上述优势使得基于MapReduce的海量数据清洗顺其自然的产生了．海量数据上的数据分析往往需要相对高昂的硬件成本和时间成本，这就引起了人们对优化数据分析的兴趣．当前已经有不少人开始研究大数据上的数据清洗系统，有对整个数据清洗系统进行研究［5－7］，也有对其中的数据一致性［8－10］，实体识别如文献［11－14］等问题进行研究的．然而现在还没有人对基于MapReduce的数据清洗系统的优化进行研究．现在几乎所有的数据分析任务都可以用MapReduce编程框架来实现，但是在实现过程中往往会存在冗余的MapReduce，基于MapReduce的海量数据清洗系统也不例外．本文提出的基于任务合并的优化方法着眼于系统中冗余的MapReduce，从细节和流程的各个方面实施．

1．2海量数据清洗系统海量数据清洗系统如图1所示，它在Hadoop平台上实施，以一个灵活的结构来处理不同类型的数据质量问题，每种类型的数据质量问题都由一个或多个模块来处理，由哈尔滨工业大学海量数据计算与研究中心提供源代码．系统中的交互模块提供一个输入接口来输入需要清洗的文件以及清洗数据的要求．结果展示模块提供清洁数据的下载链接以及脏数据和清洗后的数据的对比情况．实体识别和真值发现模块用于消冗，其中实体识别把指向同一现实世界实体的元组聚类，而真值发现用来在冲突中寻找出真实值．不一致检测模块发现数据中违反依赖规则的部分并且尝试把数据修复到符合规则的状态．数值填充部分检测数据缺失部分并填充．用户可以选择合适的模块来处理所遇到的数据质量问题。

1．3本文优化方法概要和其他优化方法本节首先给出基于任务合并的优化方法，然后对基于Hadoop平台的海量数据清洗系统进行优化．一个实际的系统往往需要很多轮MapReduce来实现．有文献表明，对于比较复杂的单一型人物，拆分开来执行的话性能反而更好．但是根据MapReduce编程方式的特点，往往需要将一个问题分解成很多简单的任务，每一个任务由一轮MapReduce实现．在大多数情况下，这种“分解”是过度的，由此而产生冗余的MapReduce．将可以合并的任务进行适当的合并，并且在不改变原系统的算法复杂度与迭代可终止性等前提下，满足可以减少原系统的MapReduce轮数和IO次数等条件进而达到优化的目的．与本文研究方向相同的工作最杰出的优化方法有MRShare［15－16］，后者是在前者的基础上发展而来的优化方法并且实现过程复杂，优化效率提升不是很明显．MRShare把多个共享相同的map输入或输出的任务合并成一个任务，减少扫描文件的次数，从而达到优化的目的．但当合并后的任务的较大的map输出的sort代价高于合并之前的多个独立的较小的map输出的代价时，就不会有任何优化效果．本文提出的基于任务合并的优化技术针对冗余计算和利用同一输入文件的简单计算进行合并，通过这种合并可以减少MapReduce的轮数从而减少系统运行的时间．通过对整个系统的框架与流程进行优化设计，有效地提高系统的效率．

1．4本文的贡献本文的主要贡献有：（1）提出一种基于MapReduce的应用系统的优化方法．（2）对海量数据清洗系统中计算较为复杂的3个模块进行讨论并提出优化方案．（3）对海量数据清洗系统的各个模块优化前后进行了大量的对比实验．

1．5本文的结构本文第1节介绍背景、主要内容和本文结构；第2、3、4节详细讨论优化方法与实施过程；第5节给出实验结果和分析；最后在第6节给出结论．

2优化的缺失值填充

在实际的生产生活中，数据缺失是一种不可避免的现象，尤其是在数据收集工作日趋自动化的今天．本模块是一种利用朴素贝叶斯分类的缺失值填充机制．

2．1缺失值填充模块介绍举一个例子，假设一个学校有60％的男生和40％的女生．女生穿裤子的人数和穿裙子的人数相等，所有男生都穿裤子．一个人在远处随机看到了一个穿裤子的学生，那么该学生的性别是什么？（1）参数估计模块整个缺失值填充系统是用贝叶斯分类的思想来计算出概率最大的取值作为填充值．参数估计模块的任务是利用式（1）计算出所有的概率，其中P（X）对所有取值为常数，所以只需要计算P（X｜Ci）×P（Ci）即可．在各个取值的先验概率未知的情况下，不妨假设其是等概率的，因此只需计算P（X｜Ci）即可。（2）连接模块系统在填充模块会根据式（2）计算出含有缺失值的元组在它的依赖属性取值确定的所确定的各个待填充值的概率．但是由于MapReduce函数在map阶段和reduce阶段一次只能处理一条记录，所以系统必须使依赖属性取值和其条件概率关联起来，这就是连接模块存在的必要性和需要解决的问题．连接模块的输入数据为参数估计模块的输出数据和原待填充数据，输出数据是将含缺失数据的元组中依赖属性取值与该取值条件概率相关联的文件．此模块的输入数据为原待填充数据和连接模块的输出，输出数据为经过填充之后的数据．利用式（2）计算出每个Ci（待填充属性可能的取值）对应的条件概率，选择其中P（Ci｜X）概率最大的Ci进行填充．（3）填充模块填充模块由一轮MapReduce实现，首先将连接模块的输出结果和原始输入数据以偏移量为键值进行连接运算，map阶段和连接模块类似，在此不再说明．reduce阶段利用式（2）计算出每个Ci（待填充属性可能的取值）对应的条件概率，选择其中P（Ci｜X）概率最大的Ci进行填充．填充效果见图3．以上是对缺失值填充模块的简要介绍，详细介绍参考文献［17］，本文仅对其离散类型的缺失值填充做考虑．

2．2系统分析与优化首先分析一下整个模块各个子模块之间的数据流和联系纽带．参数估计子模块利用输入数据中的不包含缺失数据元组来计算以依赖属性的不同取值为条件的待填充属性的各种取值的条件概率①．在计算填充值的过程中需要用到以各依赖属性的当前取值为条件的待填充属性的各种可能取值的条件概率②，②是①中的一组特定的值，②和①的联系纽带是依赖属性的取值．而②和原始数据中的待填充元组之间的联系是该元组的偏移量．因此在参数估计模块和填充模块之间增加了连接模块．仔细观察系统各阶段数据流可以发现，在参数估计的map输入和map输出数据中均包含元组的偏移量，但是reduce输出数据中只有属性值和②．这种情况使系统必须通过增加一个连接运算才能将②与待填充元组的偏移量结合在一起．针对上述情况本文提出了一种将参数估计模块和连接模块的任务合并的优化方案，即在参数估计模块就将输出的条件概率与含有缺失值的元组偏移量关联起来．其算法如下．下面举例说明优化后的算法流程，表1为包含缺失值的数据，缺失值可能为y或n．前两条元组不含缺失值，故仅将其按属性拆分；第3条元组含有缺失值，我们在每种可能取值的情况下按属性拆分，Map阶段输出结果见表2．Reduce阶段检查所有输入数据的前缀，若不包含缺失值则进入条件概率计算环节；若包含缺失值则将其录入likelihood（用于判定条件概率是否需要输出）．最后选择属性值存在于likelihood中的条件概率进行输出，输出结果见表3．优化后的参数估计子模块，Map阶段的算法复杂度为O（n＋ML），其中n为不包含缺失值的元组的数量，M为包含缺失值的元组的数量，L为缺失值可能取值的数目．一般情况下Mn，故O（n＋ML）＝O（（1＋L）n）．因为L为一个远小于n的常数，所以Map阶段的算法复杂度为O（n）．Reduce阶段的算法复杂度为O（n）．故整个参数估计子模块的算法复杂度为O（n）．优化前后，参数估计子模块的算法复杂度一直是O（n），填充子模块未做优化．整个缺失值填充模块的MapReduce轮数和IO次数均由优化前的3变为2，加速比为3／2，优化效果明显．

3优化的实体识别

实体识别，就是识别出同一实体的不同表现形式．不同的数据来源对同一对象的表示形式往往有着不同的要求，并且在数据的存储和传递过程中均会产生不可避免的错误，因此产生了同一实体的不同表现形式．关于MapReduce框架下的实体识别技术，现在已经有了相关研究工作［18－19］，但是他们只解决了异名实体识别问题，对同名问题没有进行研究；而我们的工作可以同时解决了异名和同名问题．

3．1实体识别模块介绍（1）预处理．系统读入海量数据文件并进行预处理，给每一条输入元组加上一个唯一的序号———实体ID，方便后续处理．（2）初步聚类．读取预处理模块生成的数据，按照相同属性值进行初步聚类，生成属性索引表．（3）实体识别．对实体进行识别，对同一属性索引表中的实体对计算相似度并与阈值进行比较，大于阈值的相似对输出成相似对集合文件．（4）实体划分．依据相似对集合文件生成图，通过对图的划分获得实体划分结果．以上是对实体识别模块的简要介绍，详细介绍参考文献［20］

3．2系统分析与优化通过研究发现初步聚类模块和实体识别模块，对预处理结果重复利用了N次（N为待处理数据每条元组包含的属性个数），而且后续的实体识别模块也是在单一属性上处理的．如果将预处理模块和实体识别模块看作一个整体（系统实际应用中也是这样的），那么就是对输入数据文件扫描多次，并且只能利用输入数据中的一部分，系统对输入数据的利用率很低．此外系统每次分配任务都需要消耗额外的资源．我们需要将分开处理各个属性的初步聚类和实体识别合并成一次能处理所有属性进而只运行一轮就能处理每条元组所有属性的解决方案．为此本文针对实体识别模块提出的优化思想是：在初步聚类子模块一次处理所有属性，生成所有属性值的属性索引表．这样就能将原来按属性分开处理的预处理和实体识别合并起来．下面给出具体的优化方案和算法．（1）初步聚类子模块，map阶段不是仅仅输出第i个属性值，而是将所有属性值都输出．但是为了区分初步聚类产生的结果———属性索引表集合中的1101期杨东华等：基于任务合并的并行大数据清洗过程优化实体ID是来自不同的属性，系统在map输出数据的key上做了一些改动，在原key前加上了一个前缀，由“属性值”变成“属性序号＄属性值”．因为MapReduce是按照key进行分类的，所以只有同一属性的具有相同属性值的实体才会进入同一属性索引表．reduce阶段将属性序号作为实体ID的前缀加在实体ID中．以下是优化后的初步聚类算法．其中实体ID是每个元组的编号，在预处理阶段为每一个元组（一行数据）设定唯一的实体ID．属性ID是属性在元组中的顺序．下面举例说明优化后的算法流程，待识别数据如表4所示．Map阶段将所有元组的按属性拆分后输出，结果如表5所示．属性值相同的实体会进入同一个reduce，并输出成属性索引表，如表6所示。优化后的初步聚类模块，map阶段的算法复杂度为O（n（x＋x2）），其中x为属性个数，实际应用中x为一个很小的常数值，故其计算复杂度为O（n）．reduce阶段除了在附加的读取属性序号外没有任何改动，其计算复杂度为O（n）．综上整个初步聚类模块的算法复杂度为O（n）．（2）实体识别子模块，因为整个实体识别模块是在初步聚类生成的属性索引表中进行的，而初步聚类模块的改动保证了同一属性的具有相同属性值的实体ID聚集在同一个属性索引表中，所以这一模块的算法不需要修改．除了在第3个MapReduce的reduce阶段去除实体ID中包含的前缀外，没有任何更改．这样做的目的是为了使同一实体的相似度能够在第4个MapReduce中汇合．整个实体识别模块的算法没有经过改动，所以其算法的时间复杂度仍保持O（n）．由于本文只对系统Hadoop上运行部分进行优化处理，所以将实体划分模块视作常量．在时间复杂度方面，从上一小节对实体识别子系统的介绍和本小节前面的一部分的优化方案中算法的计算复杂度可以看出，优化前后没有改变各个模块以及各个模块内部的各个MapReduce的计算复杂度．优化前的MapReduce轮数为1＋N（1＋4）＝5N＋1，优化之后的MapReduce轮数为1＋1＋4＝6，加速比为（5N＋1）／6．正常情况下N大于1，所以加速比大于1，并且N越大加速效果越明显．IO次数也由先前的5N＋1次变为6次，IO次数减少使得系统用于IO的时间减少．另外由于MapReduce的轮数减少，系统用于任务调度的时间和资源也相应减少．综上，从理论上讲，通过本文的提供的优化方案能产生明显的优化效果．

4优化的不一致数据修复

在实际的数据库系统及相关应用中由于种种原因，其中包含的数据违反最初定义的完整性约束，所以存在大量不一致数据．本系统利用数据依赖理论中的条件函数依赖原理，定义完整性约束，利用完整性约束进行不一致数据修复．本文的重点在于提高不一致数据修复模块的性能和效率，使之一致．至于如何保证这样的修改过程是正确的，是由条件函数依赖理论所决定的，本文相关的理论证明和推导详见文献［9－10］．

4．1不一致数据修复模块介绍不一致数据修复模块步骤的简要介绍如下：（1）系统读入待修复的海量数据文件和cfds文件并进行预处理，将数据格式更改成符合系统要求的格式并对cfds进行初步检测，方便后续处理．（2）对预处理结果中的数据文件进行检测与修复，得到初次修复结果．（3）对初次修复结果进行检测，判断修复工作是否引入了新的不一致．若引入了新的不一致则返回步骤（1），否则进入步骤（3）．当然为了避免系统陷入死循环，系统为检测与修复的次数设置了一个上限．（4）对修复结果进行后处理，将数据格式更改成数据的原始格式，使得修复结果能正常被其他系统使用．以上是对实体识别模块的简要介绍，详细介绍见参考文献［21］．

4．2系统分析与优化不一致数据修复子系统的4个模块中除第1个模块的CFD一致性检测子模块外都是在MapReduce编程框架上实现的，在本文的研究范围内．本模块的一个重要缺点是没有掌握MapReduce编程“分解与合并”的精髓，将本来仅需要一个Map或者一轮MapReduce便可完成的任务拆分成一轮或多轮MapReduce，由此使系统效率下降．为此我们在不改变系统算法复杂度的条件下进行任务合并．（1）预处理模块预处理模块的脏数据预处理子模块功能很简单，就是给输入数据建立索引，实施过程中没有涉及到数据的分解与合并，可以通过一个map函数实现．算法如下．（2）不一致数据检测与修复模块不一致数据的检测与修复模块中常量违反检测与修复模块通过一轮MapReduce实现，map阶段将元组重新分发了M份（M为输入元组发生常量违反的次数），尽管M实际值一般不大，对reduce阶段的计算复杂度几乎没有影响．但是M的存在会使中间数据量扩大M倍，对系统通信造成很大负担．更重要的是在系统计算出建议修复值的同时就可以将其修复，那么就没有必要将找到建议修复值的过程和修复过程分开．为此本文提出的优化方案是利用一个map函数实现常量违反检测与修复子模块．将常量违反与修复子模块通过一个map函数实现之后，经过常量违反修复的数据直接进入变量违反修复环节．两者输入数据的格式是相同的，假如原始数据中不存在常量违反，那么两者输入文件就是完全相同的．基于上述观点，本文提出了将常量违反修复与变量违反修复合并的优化方案．在这个优化方案中常量违反修复位于原变量违反修复的第1轮MapReduce的前端，让常量违反的结果在Map函数内部直接应用于变量违反．算法如下．其中，offset为元组索引值，tuple表示该条元组，fix＿tag为修复标志，用来区分是否发生违反需要修复，0表示发生违反需要修复，1表示不需要修复．cfdindex是tuple违反的CFD的序号，ptindex是该tuple违反的CFD的模式表中的模式元组序号，attrindex标志该tuple的不一致数据项的属性序号，fixvalue即为该属性值应修复的结果．下面举例说明优化后的算法流程，待修复数据如表7所示．为了便于说明，本例中仅使用1条cfd和一个tp，分别为1：（［CC，AC，PN］→［STR，CT，ST］）和T1：01，908，＿，＿，MH，＿．Map阶段将每一条输入的待修复元组与模式元组tp作比较，进行常量违反修复，然后再进行变量违反修复．第1条元组没有发生常量违反，遂进入变量违反修复环节，其map输出为表8中第1行．第2条元组发生常量违反，经常量违反修复进入变量违反修复环节，其map输出为表8中第2行．下同．在时间复杂度方面，从预处理小节和本小节优化方案中算法的计算复杂度可以看出，优化前后没有改变各个模块以及各个模块内部的各个MapReduce的计算复杂度．在MapReduce轮数和IO次数方面，系统的MapReduce轮数由优化前的1＋1＋2＋1＋1＋1＝7变成优化后的1＋2＋1＋1＝5．仅从MapReduce轮数来看系统的加速比为7／5．此外系统的优化工作还使得预处理模块的MapReduce变成了map，这也会相应地减少系统的运行时间．随着MapReduce轮数的减少，系统的IO次数也相应地减少，这也使得系统的IO负担减小。综上所述，通过本文提供的优化方案，不一致修复子系统会获得理想的优化效果．

5实验结果

整个系统在Ubuntu12．04．1操作系统中的Hadoop1．2．1平台上，用java语言实现，软件开发环境为Eclipse．实验运行的集群采用12个节点，1个tasktraker（namenode），11个jobtracker（data－node）．集群由12台机器组成，硬件环境为Inteli73770处理器，主频为3．4GHz，内存8GB，1TB硬盘空间．

5．1实体识别优化实验为了使系统的优化效果更有说服力，所有实验数据是来自DBLP的真实数据集．针对系统的特点，实验分别从扩展性、集群的并行化程度和数据的属性个数3个方面验证系统的优化效果．DBLP的数据规模并不大，看似不需要在Hadoop上实现．但大家公认的数据源往往数据量比较小，使用DBLP数据集的意义不是因为其规模而是在于DBLP数据集是真实数据，这样做可以增加本文实验结果的可信度．

5．1．1扩展性实验本实验考虑数据集合大小对优化效果的影响，实验采用由真实数据集DBLP数据集，选择其中的title，authorandco－author，journalorurl这3个属性，选择大小分别为13．2MB、32．3MB、64．9MB、97．1MB、128．9MB的数据作为实验数据．实验中各属性的权值分别为0．9、0．05、0．05，实验结果如图7所示．实验中对比了基本的实现（Nave）、文献［19］中的BlockSplit和PairRange与基于本文中任务合并的优化方法优化后的实体识别4种方法在不同数据集合大小下的运行结果．随着数据集合的增大，优化前后系统的运行时间都在增加，但是优化前和优化后系统运行时间的比值（加速比）均在2．3左右．这是因为本次实验所使用的数据具有3个属性，按照2．2节中对优化效果的分析，应具有的理论加速比为（5×3＋1）／6＝2．67与实验结果一致．由于基于BlockSplit和Pair－Range方法的实体识别实现过程的运行时间比基于任务合并的优化方法复杂，故其运行时间均比本文提出的优化方法对应的运行时间长．本实验说明优化设计方案有良好的扩展性．

5．1．2集群的并行化程度对优化效果的影响实验考虑集群中Reduce个数对优化效果的影响，实验采用由真实数据集DBLP数据集，选择其中的title，authorandco－author，journalorurl这3个属性，选择大小分别为128．9MB含有100000条记录的数据作为实验数据．实验中各属性的权值分别为0．9、0．05、0．05，设置Reduce个数为2、4、6、8、10，实验结果如图8所示，在不同的并行化程度下优化效果明显．从图8中可以看出系统运行时间随并行化程度的增强而变长，这不符合大家普遍认为的“并行化程度越高，系统运行时间越短”的常识．产生这一现象的原因是，实验数据集数据量较小，增加系统的并行度给系统带来的开销要大于由此带来的好处．无论如何，系统在不同的并行度下达到了大约2．3的加速比，优化效果符合预期．5．1．3数据集的属性个数对优化效果的影响针对优化方案的主要思想：充分利用输入记录中的所有属性，设计了本实验．实验研究输入元组中的属性个数对优化效果的影响．实验结果如图9所示，在处理同样大小（记录条数）的记录时，随着记录中包含的属性的增多，优化效果越来越好．从上述数据可以看到：当处理的元组包含一条属性时，系统的优化效果最差，比优化前运行效率还要低；但是随着属性的增加优化效果越来越好．本文的优化工作针对的是系统在处理多属性时不能充分利用输入数据，并且通过循环处理每一个属性增加了MapReduce轮数；但是处理单属性元组时优化后的方案产生的中间数据量多于优化前，并且处理过程变得更加复杂，因此产生了上述实验现象．

5．2不一致数据数据修复优化实验为了验证系统在真实生产环境中的工作状态，实验采用来自真实数据集Adult的数据和由TPC－H生成的数据集．进行了在Adult数据集上的加速比验证实验、在人工数据集上的扩展性和并行性验证实验．

5．2．1加速比实验实验采用条件函数依赖总共包含2条cfd，共有5条模式元组．根据cfd及其模式元组为来自Adult数据集中的无缺失值元组注入错误，使其违反一条或者多条约束．实验条件和实验结果如表9所示，通过实验证明系统在真实数据集上的加速效果明显，符合优化方案设计预期．此次实验加速比为1．39，理论加速比大于1．4，优化效果符合预期．

5．2．2扩展性实验为验证优化工作在不同大小的数据集上同样有明显的优化效果设计了本实验．实验利用了由TPC－H生成的lineitem．tbl表中的5个属性生成的数据集，CFDs由一条cfd包含2条tp构成．实验结果如图9所示，可见随着数据集合的增大优化效果会变好，说明优化设计方案有良好的扩展性．从图9可以看出优化前系统运行时间随数据集增加呈线性增加，优化后系统运行时间随数据集的增加也呈线性增加，但前者的斜率更大．此外，系统优化前后的加速比从1．59一直上升到2．20．一方面，优化前各个模块的计算任务相当，但是优化工作大大减轻了除不一致数据检测与修复模块之外各模块的负载；另一方面，实验中为了突出数据集的大小对系统运行时间的影响，仅设置Reduce个数为2，故随着数据集的增大优化前的系统率先满负荷运行．从而出现了图10中对比鲜明的实验结果。

5．2．3并行性实验为验证并行程度对优化效果的影响，设计了本实验．实验利用了由TPC－H生成的lineitem．tbl表中的5个属性生成的数据集，CFDs由一条cfd包含2条tp构成，详见图11．从图10可以看出系统在并行度较低（Reduce个数为2）的情况下加速比最高达到2．20，之后随着系统并行化程度增高优化效果变差，加速比降低．并且优化前的系统随着系统的并行度的提高使得运行时间缩短，而优化后的系统基本保持不变．这是因为优化之前的系统处理数据的能力减弱，很容易满负载运行，只能通过增加系统的并行化程度提高数据处理的效率，故随着并行度增加系统运行时间减小；而优化后的系统吞吐量大，与处理和前者相同的数据一直都没有处于满负载状态运行，故增加系统的并行度带来的好处不明显．

5．3缺失值填充优化实验为了验证系统在真实生产环境中的工作状态，本文的实验采用来自真实数据集Adult（www．archive．ics．uci．edu／ml／datasets．html）的数据和由TPC－H生成的数据集．进行了在Adult数据集上的缺失率对优化效果的验证实验、在人工数据集上的扩张性实验和并行性验证实验．

5．3．1缺失率对优化效果的影响实验主要研究不同的数据缺失率对优化结果的影响，通过将完整数据集按一定的比例（缺失率）随机置空数据生成实验所需的各种缺失率的数据．本文选取其中9个离散属性，缺失属性有7种取值，实验结果见图12．在图中所示缺失率下，加速比稳定在1．5左右，与本模块的理论加速比3／2相吻合．

5．3．2扩展性验证实验本实验利用由TPC－H生成的数据表lineitem．tbl选取其中5个属性，分别选择不同的记录条数生成实验所需的数据．图13所示实验结果表明，无论优化前后，系统的运行时间均随数据集的增大而增大，但是加速比均保持在1．5左右，与本模块的理论加速比相吻合．

5．3．3并行性验证实验为了验证系统在不同并行化程度下的优化效果，设计了本实验．实验利用由TPC－H生成的lineitem．tbl数据表，数据表共包含5个属性，3000000条元组．随机置空数据表第1列5％的数据（缺失率5％），记录在不同的并行化程度下系统的优化效果．实验结果见图14．在给定数据集上，系统优化前后的运行效率都未随着并行化程度的提高而变好．这是因为对于特定大小的数据集最适宜的Reduce数目是确定的，一味地提高并行化程度只会给系统带来更多地任务分配的开销．无论如何，在不同的并行化程度下优化效果明显．

6结论

虽然整个行业对Hadoop的研究和使用已经有了相当的积累，但是由于使用者对MapReduce编程框架理解不够深刻，所以利用MapReduce设计的软件系统大都效率低下．为此本文提出了一种针对MapReduce编程框架设计的系统的优化方法，并通过了在海量数据清洗系统上的实施．本文提出的优化方法仅需对原系统解决问题的思路稍作改动，几乎不影响其算法复杂性，通过减少MapReduce轮数和IO次数达到优化的目的．优化方法简单，实用性强．未来的工作包括将这种思想利用到更多基于MapReduce的系统中，对实验结果进行更为深入的分析以发现本文提供的优化方法的不足从而提出更好的优化方法．

作者：杨东华 李宁宁 王宏志 李建中 高宏 单位：哈尔滨工业大学计算机科学与技术学院 哈尔滨工业大学基础与交叉科学研究院