《并行大数据清洗经过优化.docx》由会员分享，可在线阅读，更多相关《并行大数据清洗经过优化.docx（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、并行大数据清洗经过优化摘要数据质量问题会对大数据的应用产生致命影响，因而需要对存在数据质量问题的大数据进行清洗编程框架能够利用并行技术实现高可扩展性的大数据清洗，然而，由于缺乏有效的设计，在基于的数据清洗经过中存在计算的冗余，导致性能降低因而文中的目的是对并行数据清洗经过进行优化进而提高效率通过研究，作者发现数据清洗中一些任务往往都运行在同一输入文件上或者利用同样的运算结果，基于该发现文中提出了一种新的优化技术基于任务合并的优化技术针对冗余计算和利用同一输入文件的简单计算进行合并，通过这种合并能够减少的轮数进而减少系统运行的时间，最终到达系统优化的目的文中针对数据清洗经过中多个复杂的模块进行了
2、优化，详细来讲分别对实体识别模块、不一致数据修复模块和缺失值填充模块进行了优化实验结果表明，文中提出的策略能够有效提高数据清洗的效率关键词大数据；多任务优化；海量数据；数据清洗；引言本节主要介绍研究背景及其意义、海量数据清洗系统、本文优化方法的主要思想、本文的奉献与构造研究背景及其意义现今企业的成功和社会的进步，越来越依靠于数据和对其所做的分析为了获得竞争优势即便是小企业也会投入时间和精神来收集和分析数据很多大公司都部署了本人的云服务平台，国内比拟著名的有百度云、阿里云、天翼云等但是假如一味地将精神投入到对数据所做的分析而不关注数据本身，很可能产生灾难性的后果统计表明，美国企业中的数据存在各类
3、错误和误差，医疗数据库中的关键数据不完好或陈旧根据市场研究公司的调查，全球财富强公司超过的关键数据不正确或不准确数据质量问题会使基于其的分析和研究毫无意义甚至还会产生灾难性的后果，在美国由于数据错误引起的医疗事故每年使名患者丧生上述实例表明数据质量问题存在于社会生活的方方面面，数据清洗系统应运而生在海量数据处理领域，编程框架作为当下最流行的并行编程开发框架已被、！、以及国内的腾讯、阿里巴巴等大型互联网公司奉为珍宝将用于海量数据处理主要有如下优势：易用性、高可扩展性、高容错性上述优势使得基于的海量数据清洗顺其自然的产生了海量数据上的数据分析往往需要相对高昂的硬件成本和时间成本，这就引起了人们对优
4、化数据分析的兴趣当前已经有不少人开场研究大数据上的数据清洗系统，有对整个数据清洗系统进行研究，也有对其中的数据一致性，实体识别如文献等问题进行研究的然而如今还没有人对基于的数据清洗系统的优化进行研究如今几乎所有的数据分析任务都能够用编程框架来实现，但是在实现经过中往往会存在冗余的，基于的海量数据清洗系统也不例外本文提出的基于任务合并的优化方法着眼于系统中冗余的，从细节和流程的各个方面施行海量数据清洗系统海量数据清洗系统如图所示，它在平台上施行，以一个灵敏的构造来处理不同类型的数据质量问题，每种类型的数据质量问题都由一个或多个模块来处理，由哈尔滨工业大学海量数据计算与研究中心提供源代码系统中的交
5、互模块提供一个输入接口来输入需要清洗的文件以及清洗数据的要求结果展示模块提供清洁数据的下载链接以及脏数据和清洗后的数据的比照情况实体识别和真值发现模块用于消冗，其中实体识别把指向同一现实世界实体的元组聚类，而真值发现用来在冲突中寻找出真实值不一致检测模块发现数据中违背依靠规则的部分并且尝试把数据修复到符合规则的状态数值填充部分检测数据缺失部分并填充用户能够选择适宜的模块来处理所碰到的数据质量问题。本文优化方法概要和其他优化方法本节首先给出基于任务合并的优化方法，然后对基于平台的海量数据清洗系统进行优化一个实际的系统往往需要很多轮来实现有文献表明，对于比拟复杂的单一型人物，拆分开来执行的话性能反
6、而更好但是根据编程方式的特点，往往需要将一个问题分解成很多简单的任务，每一个任务由一轮实现在大多数情况下，这种“分解是过度的，由此而产生冗余的将能够合并的任务进行适当的合并，并且在不改变原系统的算法复杂度与迭代可终止性等前提下，知足能够减少原系统的轮数和次数等条件进而到达优化的目的与本文研究方向一样的工作最出色的优化方法有，后者是在前者的基础上发展而来的优化方法并且实现经过复杂，优化效率提升不是很明显把多个分享一样的输入或输出的任务合并成一个任务，减少扫描文件的次数，进而到达优化的目的但当合并后的任务的较大的输出的代价高于合并之前的多个独立的较小的输出的代价时，就不会有任何优化效果本文提出的基
7、于任务合并的优化技术针对冗余计算和利用同一输入文件的简单计算进行合并，通过这种合并能够减少的轮数进而减少系统运行的时间通过对整个系统的框架与流程进行优化设计，有效地提高系统的效率本文的奉献本文的主要奉献有：提出一种基于的应用系统的优化方法对海量数据清洗系统中计算较为复杂的个模块进行讨论并提出优化方案对海量数据清洗系统的各个模块优化前后进行了大量的比照实验本文的构造本文第节介绍背景、主要内容和本文构造；第、节具体讨论优化方法与施行经过；第节给出实验结果和分析；最后在第节给出结论优化的缺失值填充在实际的生产生活中，数据缺失是一种不可避免的现象，尤其是在数据收集工作日趋自动化的今天本模块是一种利用朴
8、素贝叶斯分类的缺失值填充机制缺失值填充模块介绍举一个例子，假设一个学校有的男生和的女生女生穿裤子的人数和穿裙子的人数相等，所有男生都穿裤子一个人在远处随机看到了一个穿裤子的学生，那么该学生的性别是什么？参数估计模块整个缺失值填充系统是用贝叶斯分类的思想来计算出概率最大的取值作为填充值参数估计模块的任务是利用式计算出所有的概率，其中对所有取值为常数，所以只需要计算即可在各个取值的先验概率未知的情况下，不妨假设其是等概率的，因而只需计算即可。连接模块系统在填充模块会根据式计算出含有缺失值的元组在它的依靠属性取值确定的所确定的各个待填充值的概率但是由于函数在阶段和阶段一次只能处理一条记录，所以系统必
9、须使依靠属性取值和其条件概率关联起来，这就是连接模块存在的必要性和需要解决的问题连接模块的输入数据为参数估计模块的输出数据和原待填充数据，输出数据是将含缺失数据的元组中依靠属性取值与该取值条件概率相关联的文件此模块的输入数据为原待填充数据和连接模块的输出，输出数据为经过填充之后的数据利用式计算出每个待填充属性可能的取值对应的条件概率，选择其中概率最大的进行填充填充模块填充模块由一轮实现，首先将连接模块的输出结果和原始输入数据以偏移量为键值进行连接运算，阶段和连接模块类似，在此不再讲明阶段利用式计算出每个待填充属性可能的取值对应的条件概率，选择其中概率最大的进行填充填充效果见图以上是对缺失值填充
10、模块的扼要介绍，具体介绍参考文献，本文仅对其离散类型的缺失值填充做考虑系统分析与优化首先分析一下整个模块各个子模块之间的数据流和联络纽带参数估计子模块利用输入数据中的不包含缺失数据元组来计算以依靠属性的不同取值为条件的待填充属性的各种取值的条件概率在计算填充值的经过中需要用到以各依靠属性的当前取值为条件的待填充属性的各种可能取值的条件概率，是中的一组特定的值，和的联络纽带是依靠属性的取值而和原始数据中的待填充元组之间的联络是该元组的偏移量因而在参数估计模块和填充模块之间增加了连接模块仔细观察系统各阶段数据流能够发现，在参数估计的输入和输出数据中均包含元组的偏移量，但是输出数据中只要属性值和这种
11、情况使系统必须通过增加一个连接运算才能将与待填充元组的偏移量结合在一起针对上述情况本文提出了一种将参数估计模块和连接模块的任务合并的优化方案，即在参数估计模块就将输出的条件概率与含有缺失值的元组偏移量关联起来其算法如下下面举例讲明优化后的算法流程，表为包含缺失值的数据，缺失值可能为或前两条元组不含缺失值，故仅将其按属性拆分；第条元组含有缺失值，我们在每种可能取值的情况下按属性拆分，阶段输出结果见表阶段检查所有输入数据的前缀，若不包含缺失值则进入条件概率计算环节；若包含缺失值则将其录入用于断定条件概率能否需要输出最后选择属性值存在于中的条件概率进行输出，输出结果见表优化后的参数估计子模块，阶段的
12、算法复杂度为，其中为不包含缺失值的元组的数量，为包含缺失值的元组的数量，为缺失值可能取值的数目一般情况下，故由于为一个远小于的常数，所以阶段的算法复杂度为阶段的算法复杂度为故整个参数估计子模块的算法复杂度为优化前后，参数估计子模块的算法复杂度一直是，填充子模块未做优化整个缺失值填充模块的轮数和次数均由优化前的变为，加速比为，优化效果明显优化的实体识别实体识别，就是识别出同一实体的不同表现形式不同的数据来源对同一对象的表示形式往往有着不同的要求，并且在数据的存储和传递经过中均会产生不可避免的错误，因而产生了同一实体的不同表现形式关于框架下的实体识别技术，如今已经有了相关研究工作，但是他们只解决了
13、异名实体识别问题，对同名问题没有进行研究；而我们的工作能够同时解决了异名和同名问题实体识别模块介绍预处理系统读入海量数据文件并进行预处理，给每一条输入元组加上一个唯一的序号实体，方便后续处理初步聚类读取预处理模块生成的数据，根据一样属性值进行初步聚类，生成属性索引表实体识别对实体进行识别，对同一属性索引表中的实体对计算类似度并与阈值进行比拟，大于阈值的类似对输出成类似对集合文件实体划分根据类似对集合文件生成图，通过对图的划分获得实体划分结果以上是对实体识别模块的扼要介绍，具体介绍参考文献系统分析与优化通过研究发现初步聚类模块和实体识别模块，对预处理结果重复利用了次为待处理数据每条元组包含的属性
14、个数，而且后续的实体识别模块也是在单一属性上处理的假如将预处理模块和实体识别模块看作一个整体系统实际应用中也是这样的，那么就是对输入数据文件扫描屡次，并且只能利用输入数据中的一部分，系统对输入数据的利用率很低此外系统每次分配任务都需要消耗额外的资源我们需要将分开处理各个属性的初步聚类和实体识别合并成一次能处理所有属性进而只运行一轮就能处理每条元组所有属性的解决方案为此本文针对实体识别模块提出的优化思想是：在初步聚类子模块一次处理所有属性，生成所有属性值的属性索引表这样就能将原来按属性分开处理的预处理和实体识别合并起来下面给出详细的优化方案和算法初步聚类子模块，阶段不是仅仅输出第个属性值，而是将
15、所有属性值都输出但是为了区分初步聚类产生的结果属性索引表集合中的期杨东华等：基于任务合并的并行大数据清洗经过优化实体是来自不同的属性，系统在输出数据的上做了一些改动，在原前加上了一个前缀，由“属性值变成“属性序号属性值由于是根据进行分类的，所以只要同一属性的具有一样属性值的实体才会进入同一属性索引表阶段将属性序号作为实体的前缀加在实体中下面是优化后的初步聚类算法其中实体是每个元组的编号，在预处理阶段为每一个元组一行数据设定唯一的实体属性是属性在元组中的顺序下面举例讲明优化后的算法流程，待识别数据如表所示阶段将所有元组的按属性拆分后输出，结果如表所示属性值一样的实体会进入同一个，并输出成属性索引
16、表，如表所示。优化后的初步聚类模块，阶段的算法复杂度为，其中为属性个数，实际应用中为一个很小的常数值，故其计算复杂度为阶段除了在附加的读取属性序号外没有任何改动，其计算复杂度为综上整个初步聚类模块的算法复杂度为实体识别子模块，由于整个实体识别模块是在初步聚类生成的属性索引表中进行的，而初步聚类模块的改动保证了同一属性的具有一样属性值的实体聚集在同一个属性索引表中，所以这一模块的算法不需要修改除了在第个的阶段去除实体中包含的前缀外，没有任何更改这样做的目的是为了使同一实体的类似度能够在第个中汇合整个实体识别模块的算法没有经过改动，所以其算法的时间复杂度仍保持由于本文只对系统上运行部分进行优化处理
17、，所以将实体划分模块视作常量在时间复杂度方面，从上一小节对实体识别子系统的介绍和本小节前面的一部分的优化方案中算法的计算复杂度能够看出，优化前后没有改变各个模块以及各个模块内部的各个的计算复杂度优化前的轮数为，优化之后的轮数为，加速比为正常情况下大于，所以加速比大于，并且越大加速效果越明显次数也由先前的次变为次，次数减少使得系统用于的时间减少另外由于的轮数减少，系统用于任务调度的时间和资源也相应减少综上，从理论上讲，通过本文的提供的优化方案能产生明显的优化效果优化的不一致数据修复在实际的数据库系统及相关应用中由于种种原因，其中包含的数据违背最初定义的完好性约束，所以存在大量不一致数据本系统利用
18、数据依靠理论中的条件函数依靠原理，定义完好性约束，利用完好性约束进行不一致数据修复本文的重点在于提高不一致数据修复模块的性能和效率，使之一致至于怎样保证这样的修改正程是正确的，是由条件函数依靠理论所决定的，本文相关的理论证实和推导详见文献不一致数据修复模块介绍不一致数据修复模块步骤的扼要介绍如下：系统读入待修复的海量数据文件和文件并进行预处理，将数据格式更改成符合系统要求的格式并对进行初步检测，方便后续处理对预处理结果中的数据文件进行检测与修复，得到初次修复结果对初次修复结果进行检测，判定修复工作能否引入了新的不一致若引入了新的不一致则返回步骤，否则进入步骤当然为了避免系统陷入死循环，系统为检
19、测与修复的次数设置了一个上限对修复结果进行后处理，将数据格式更改成数据的原始格式，使得修复结果能正常被其他系统使用以上是对实体识别模块的扼要介绍，具体介绍见参考文献系统分析与优化不一致数据修复子系统的个模块中除第个模块的一致性检测子模块外都是在编程框架上实现的，在本文的研究范围内本模块的一个重要缺点是没有把握编程“分解与合并的精华，将本来仅需要一个或者一轮便可完成的任务拆分成一轮或多轮，由此使系统效率下降为此我们在不改变系统算法复杂度的条件下进行任务合并预处理模块预处理模块的脏数据预处理子模块功能很简单，就是给输入数据建立索引，施行经过中没有涉及到数据的分解与合并，能够通过一个函数实现算法如下
20、不一致数据检测与修复模块不一致数据的检测与修复模块中常量违背检测与修复模块通过一轮实现，阶段将元组重新分发了份为输入元组发生常量违背的次数，尽管实际值一般不大，对阶段的计算复杂度几乎没有影响但是的存在会使中间数据量扩大倍，对系统通信造成很大负担更重要的是在系统计算出建议修复值的同时就能够将其修复，那么就没有必要将找到建议修复值的经过和修复经过分开为此本文提出的优化方案是利用一个函数实现常量违背检测与修复子模块将常量违背与修复子模块通过一个函数实现之后，经过常量违背修复的数据直接进入变量违背修复环节两者输入数据的格式是一样的，假设原始数据中不存在常量违背，那么两者输入文件就是完全一样的基于上述观
21、点，本文提出了将常量违背修复与变量违背修复合并的优化方案在这个优化方案中常量违背修复位于原变量违背修复的第轮的前端，让常量违背的结果在函数内部直接应用于变量违背算法如下其中，为元组索引值，表示该条元组，为修复标志，用来区分能否发生违背需要修复，表示发生违背需要修复，表示不需要修复是违背的的序号，是该违背的的形式表中的形式元组序号，标志该的不一致数据项的属性序号，即为该属性值应修复的结果下面举例讲明优化后的算法流程，待修复数据如表所示为了便于讲明，本例中仅使用条和一个，分别为：，和：，阶段将每一条输入的待修复元组与形式元组作比拟，进行常量违背修复，然后再进行变量违背修复第条元组没有发生常量违背，
22、遂进入变量违背修复环节，其输出为表中第行第条元组发生常量违背，经常量违背修复进入变量违背修复环节，其输出为表中第行下同在时间复杂度方面，从预处理小节和本小节优化方案中算法的计算复杂度能够看出，优化前后没有改变各个模块以及各个模块内部的各个的计算复杂度在轮数和次数方面，系统的轮数由优化前的变成优化后的仅从轮数来看系统的加速比为此外系统的优化工作还使得预处理模块的变成了，这也会相应地减少系统的运行时间随着轮数的减少，系统的次数也相应地减少，这也使得系统的负担减小。综上所述，通过本文提供的优化方案，不一致修复子系统会获得理想的优化效果实验结果整个系统在操作系统中的平台上，用语言实现，软件开发环境为实
23、验运行的集群采用个节点，个，个集群由台机器组成，硬件环境为处理器，主频为，内存，硬盘空间实体识别优化实验为了使系统的优化效果更有讲服力，所有实验数据是来自的真实数据集针对系统的特点，实验分别从扩展性、集群的并行化程度和数据的属性个数个方面验证系统的优化效果的数据规模并不大，看似不需要在上实现但大家公认的数据源往往数据量比拟小，使用数据集的意义不是由于其规模而是在于数据集是真实数据，这样做能够增加本文实验结果的可信度扩展性实验本实验考虑数据集合大小对优化效果的影响，实验采用由真实数据集数据集，选择其中的，这个属性，选择大小分别为、的数据作为实验数据实验中各属性的权值分别为、，实验结果如图所示实验
24、中比照了基本的实现、文献中的和与基于本文中任务合并的优化方法优化后的实体识别种方法在不同数据集合大小下的运行结果随着数据集合的增大，优化前后系统的运行时间都在增加，但是优化前和优化后系统运行时间的比值加速比均在左右这是由于本次实验所使用的数据具有个属性，根据节中对优化效果的分析，应具有的理论加速比为与实验结果一致由于基于和方法的实体识别实现经过的运行时间比基于任务合并的优化方法复杂，故其运行时间均比本文提出的优化方法对应的运行时间长本实验讲明优化设计方案有良好的扩展性集群的并行化程度对优化效果的影响实验考虑集群中个数对优化效果的影响，实验采用由真实数据集数据集，选择其中的，这个属性，选择大小分
25、别为含有条记录的数据作为实验数据实验中各属性的权值分别为、，设置个数为、，实验结果如图所示，在不同的并行化程度下优化效果明显从图中能够看出系统运行时间随并行化程度的加强而变长，这不符合大家普遍以为的“并行化程度越高，系统运行时间越短的常识产生这一现象的原因是，实验数据集数据量较小，增加系统的并行度给系统带来的开销要大于由此带来的好处无论怎样，系统在不同的并行度下到达了大约的加速比，优化效果符合预期数据集的属性个数对优化效果的影响针对优化方案的主要思想：充分利用输入记录中的所有属性，设计了本实验实验研究输入元组中的属性个数对优化效果的影响实验结果如图所示，在处理同样大小记录条数的记录时，随着记录
26、中包含的属性的增加，优化效果越来越好从上述数据能够看到：当处理的元组包含一条属性时，系统的优化效果最差，比优化前运行效率还要低；但是随着属性的增加优化效果越来越好本文的优化工作针对的是系统在处理多属性时不能充分利用输入数据，并且通过循环处理每一个属性增加了轮数；但是处理单属性元组时优化后的方案产生的中间数据量多于优化前，并且处理经过变得愈加复杂，因而产生了上述实验现象不一致数据数据修复优化实验为了验证系统在真实生产环境中的工作状态，实验采用来自真实数据集的数据和由生成的数据集进行了在数据集上的加速比验证明验、在人工数据集上的扩展性和并行性验证明验加速比实验实验采用条件函数依靠总共包含条，共有条
27、形式元组根据及其形式元组为来自数据集中的无缺失值元组注入错误，使其违背一条或者多条约束实验条件和实验结果如表所示，通过实验证实系统在真实数据集上的加速效果明显，符合优化方案设计预期此次实验加速比为，理论加速比大于，优化效果符合预期扩展性实验为验证优化工作在不同大小的数据集上同样有明显的优化效果设计了本实验实验利用了由生成的表中的个属性生成的数据集，由一条包含条构成实验结果如图所示，可见随着数据集合的增大优化效果会变好，讲明优化设计方案有良好的扩展性从图能够看出优化前系统运行时间随数据集增加呈线性增加，优化后系统运行时间随数据集的增加也呈线性增加，但前者的斜率更大此外，系统优化前后的加速比从一直
28、上升到一方面，优化前各个模块的计算任务相当，但是优化工作大大减轻了除不一致数据检测与修复模块之外各模块的负载；另一方面，实验中为了突出数据集的大小对系统运行时间的影响，仅设置个数为，故随着数据集的增大优化前的系统率先满负荷运行进而出现了图中比照鲜明的实验结果。并行性实验为验证并行程度对优化效果的影响，设计了本实验实验利用了由生成的表中的个属性生成的数据集，由一条包含条构成，详见图从图能够看出系统在并行度较低个数为的情况下加速比最高到达，之后随着系统并行化程度增高优化效果变差，加速比降低并且优化前的系统随着系统的并行度的提高使得运行时间缩短，而优化后的系统基本保持不变这是由于优化之前的系统处理数
29、据的能力减弱，很容易满负载运行，只能通过增加系统的并行化程度提高数据处理的效率，故随着并行度增加系统运行时间减小；而优化后的系统吞吐量大，与处理和前者一样的数据一直都没有处于满负载状态运行，故增加系统的并行度带来的好处不明显缺失值填充优化实验为了验证系统在真实生产环境中的工作状态，本文的实验采用来自真实数据集的数据和由生成的数据集进行了在数据集上的缺失率对优化效果的验证明验、在人工数据集上的扩张性实验和并行性验证明验缺失率对优化效果的影响实验主要研究不同的数据缺失率对优化结果的影响，通过将完好数据集按一定的比例缺失率随机置空数据生成实验所需的各种缺失率的数据本文选取其中个离散属性，缺失属性有种
30、取值，实验结果见图在图中所示缺失率下，加速比稳定在左右，与本模块的理论加速比相吻合扩展性验证明验本实验利用由生成的数据表选取其中个属性，分别选择不同的记录条数生成实验所需的数据图所示实验结果表明，无论优化前后，系统的运行时间均随数据集的增大而增大，但是加速比均保持在左右，与本模块的理论加速比相吻合并行性验证明验为了验证系统在不同并行化程度下的优化效果，设计了本实验实验利用由生成的数据表，数据表共包含个属性，条元组随机置空数据表第列的数据缺失率，记录在不同的并行化程度下系统的优化效果实验结果见图在给定数据集上，系统优化前后的运行效率都未随着并行化程度的提高而变好这是由于对于特定大小的数据集最适宜的数目是确定的，一味地提高并行化程度只会给系统带来更多地任务分配的开销无论怎样，在不同的并行化程度下优化效果明显结论固然整个行业对的研究和使用已经有了相当的积累，但是由于使用者对编程框架理解不够深入，所以利用设计的软件系统大都效率低下为此本文提出了一种针对编程框架设计的系统的优化方法，并通过了在海量数据清洗系统上的施行本文提出的优化方法仅需对原系统解决问题的思路稍作改动，几乎不影响其算法复杂性，通过减少轮数和次数到达优化的目的优化方法简单，实用性强将来的工作包括将这种思想利用到更多基于的系统中，对实验结果进行更为深化的分析以发现本文提供的优化方法的缺乏进而提出更好的优化方法