大数据云清洗系统的设计与实现

计划以及参数设置。而清洗计划即是一个清洗操作序列，由系统提供的四种清洗的基本操作构成，这四种操作分别为实体识别、不一致性检测和修复、缺值填充和真值发现，并且四种操作可以重复选择。

图2 系统结构图

Fig.2 Architecture of the System

大数据的清洗任务，往往需要很长的时间。在清洗时，云清洗系统给用户提供一个接口来实时查看清洗的进度情况以及通过结果预览来调整算法参数。

3 数据清洗操作

本节将简要介绍四个数据清洗操作的功能以及基本Map-Reduce计算框架下的算法实现。

3.1 清洗操作

为了使清洗系统能够复用共享的操作以提升清洗的效率，研究提取了数据质量问题中的四类基本的操作，分别是实体识别、不一致性检测和修复、缺值填充和真值发现。对其概述如下

实体识别：识别元组是否代表现实世界的同一实体。

不一致性检测和修复：检测违反规则集的元组，并修复数据使之符合规则。

缺值填充：根据其他完整的元组数据来填充元组的缺失属性值。

真值发现：选择代表同一实体的不同元组存在取值冲突时的真实取值。

这些操作涵盖了数据质量方面的大多数问题。本文的系统可以利用如上的基本操作并根据实际需求来组合形成新的数据清洗的复杂操作。

3.2 算法实现

这些操作对应的算法可在Map-Reduce框架下获得实现，再并行地在各个slave上运行。限于篇幅，此处仅给出其简要介绍。

（1）实体识别。该算法有两阶段。第一阶段，构建属性索引表，使得索引表中拥有相同属性值的数据对象对应于同一个实体。这一阶段由一轮Map-Reduce实现并完成。其中的Map阶段划分主要根据属性的取值来进行数据划分，而Reduce阶段则根据属性取值来对元组决定其分群。第二阶段，完成实体的识别，执行相似度连接查询生成相似实体对集合。该阶段由五轮Map-Reduce实现并完成。其中的第一轮分别统计每个实体及每个实体对的出现次数。第二轮和第三轮分别根据同时出现在实体对中的第一个实体和第二个进行聚集，生成相似实体对集合。稍后的第四轮和第五轮则根据阈值和计算的相似度，完成实体划分。

（2）不一致性检测和修复。该操作需要三轮Map-Reduce来实现并完成。第一轮实现了常量CFD的不一致性检测和修复。Map过程是根据约束规则对元组进行划分，并从规则中得到修复值，Reduce过程则根据得到的修复值对不一致的数据项进行相关修复。随后的两轮则完成FD和CFD的不一致性检测和修复。两者中，前一轮的Map过程依然是根据约束规则来划分元组，此过程检测的是变量CFD的违反，因此一个元组可能重复地划分；而Reduce过程则针对获得的分组以判断组内是否发生变量违反，制定修复方案。基于前一轮Reduce的输出，后一轮将以其作为输入，并按照计算的解决方案对不一致的数据项进行修复。Map阶段对每条元组的修复方案进行整合。Reduce阶段将继续根据整合后的修复方案对不一致的数据项进行修复。

（3）缺值填充。研究根据不同的属性取值设计了多种不同的算法类型来实现缺值填充。对于连续变量值的缺失而言，就是利用其他的属性取值通过回归来实现缺值填充。此处的回归包含三个子过程，分别是：标准化、排序和回归，每一个操作均对应一轮的Map-Reduce。具体来说，标准化阶段将所有属性进行标准化，并计算各个属性的最小值，构成最小值向量。排序则对所有元组的最小值向量计算相对大小并排序。回归将完成回归并填充缺失值。离散变量值缺失，则通过分类来实现缺值填充。分类也同样包含三个子过程，分别是：概率计算、参数聚集和缺值填充，每个操作也都对应一轮Map-Reduce。具体地，概率计算过程需要计算每个特征属性的条件概率和分类属性的边缘概率，生成概率表。参数聚集则根据概率表来聚集缺值填充需要的参数。而缺值填充主要根据聚集的参数来完成填充。

（4）真值发现。真值发现的基本框架是贝叶斯模型。该框架迭代地计算真值和数据源的相关性。每次迭代均需要两轮的Map-Reduce。第一轮通过数据源的可靠性来计算真值，map将根据属性与实体序号的匹配来生成属性值与数据源的可靠性的对应，reduce阶段则通过投票来确定真值。第二轮通过上一轮得到的真值来重新评估数据源的可靠性。两轮一直迭代执行，直至收敛。

4用户功能接口

研究设计的云清洗系统部署在一个32节点的Hadoop集群上，该系统为用户提供了一个基于Web的访问接口。本节简要介绍该系统的用户功能接口。

（1）任务提交。提交一个数据清洗任务总共需要四类输入：待清洗的数据、由清洗基本操作序列构成的清洗计划、算法的参数和并行节点数。用户可以通过文件的形式或者远程数据库连接的形式提交待清洗的数据。清洗计划则是选择系统提供的四种数据清洗操作中的某几项，组成一个操作序列告诉系统用户的清洗计划。算法的参数则是清洗计划中选择的基本操作所对应的算法中需要的参数输入，这是由用户进行提供的。而并行节点数就是用于进行这次清洗所使用的节点数目。

（2）进度观测。进度观测的作用是让用户获取清洗的进度信息。系统的Web页面可向用户展示出当前进行的清洗任务，该任务的操作序列中各个操作的完成情况，以及正在进行的操作中各个节点的分布式完成情况。为此，用户即能随时地观察整个任务的进度信息。

（3）结果预览。对于已经完成的清洗任务，系统会对清洗结果进行小样本的抽样，生成各个操作的清洗前后的对比效果，提供给用户展示和查看。用户根据效果清晰与否来选择是调整参数再次清洗还是下载清洗后的数据。

（4）结果获取。当清洗完成之后，系统提供给用户获取清洗结果的接口。和数据输入类似地，用户可以直接以文件的形式下载数据或者提供数据库连接信息用于远程导出到数据库。

5结束语

本文设计并实现了大数据的云清洗系统，提出了数据质量问题的四种基本操作，实体识别、不一致性检测和修复、缺值填充和真值发现，并组合成更复杂的数据清洗任务。该系统采用Map-Reduce框架实现，能够更为高效地处理大数据的清洗任务。同时，系统还为用户提供了一个简洁而友好的Web功能接口，从而交互式地实现了大数据的清洗功能。

参考文献：

[1]DEAN J， GHEMAWAT S. MapReduce： Simplified data processing on large clusters [C]//OSDI， San Francisco， USA： USENIX， 2004.

[2]KOLB L， THOR A， RAHM E. Dedoop： Efficient deduplication with hadoop[J]. PVLDB， 2012，5（12）：1878-1881.

[3]KOLB L， THOR A， RAHM E. Load balancing for map-reduce-based entity resolution[C]//ICDE， [S.l.]：IEEE，2012：618-629.

[4]RAMAN V， HELLERSTEIN J M. Potter’s wheel： An interactive data cleaning system[C]//VLDB， Rome， Italy： VLDB， 2001.

[5]WEIS M， MANOLESCU I. Xclean in action （demo）[C]//CIDR， Asilomar， CA， USA：[s.n.]，2007.

[6]FAN W， GEERTS F， JIA X. Semandaq： a data quality system based on conditional functional dependencies[J]. PVLDB， 2008，1（2）：1460-1463.

[7]FAN W， LI J， MA S， et al. Yu. CerFix： A system for cleaning data with certain fixes[J]. PVLDB， 2011，4（12）：1375-1378.

[8]EBAID A， ELMAGARMID A K， ILYAS I F， et al. Nadeef： A generalized data cleaning system[J]. PVLDB， 2013，6（12）：1218–1221.

[9]ELMAGARMID A K， IPEIROTIS P G， VERYKIOS V S. Duplicate record detection： A survey[J]. IEEE Trans. Knowl. Data Eng.， 2007，19（1）：1-16.

[10]FAN W， GEERTS F， WIJSEN J. Determining the currency of data[J]. ACM Trans. Database Syst.， 2012， 37（3）：1-45 .

[11]FAN W. Dependencies revisited for improving data quality[C]//PODS， Vancouver， Canada：ACM， 2008：159-170.

[12]LI L， WANG H， GAO H， et al. Eif： A framework of effective entity identification[C]// WAIM， Berlin： Springer， 2010：717-728.