摘 要：数据清洗时是大数据中一个重要的主题。本文基于Hadoop设计并实现了一个大数据的云清洗系统。通过Map-Reduce计算模型，该系统能够检测并修复数据质量方面的各类问题。该系统包含以下特征：（1）支持数据质量方面各类问题的清洗工作；（2）数据云清洗进度可视化的以及参数设置；（3）友好的数据集输入接口以及清洗后的数据集输出接口。该大数据云清洗系统对文本数据和数据库数据均是一个有效且高效的数据清洗系统。
关键词：大数据；数据质量；云清洗；Map-Reduce
中图分类号：TP391 文献标识号：A
Design and Implementation of Cloud Clean System on Big Data
HUANG Shenbin1 ， WANG Haijie1 ， ZHU Zhenhua2
（1 Network and Information Center， Harbin Institute of Technology， Harbin 150001， China；
2 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）
Abstract： Data cleaning is one of the central issues in big data. The paper describes a cloud clean system based on Hadoop for data cleaning. Using Map-Reduce model， the system detects and repairs various data quality problems in big data. The paper designs the system from the following features： （1） the support for cleaning multiple data quality problems in big data； （2） a visual tool for watching the status of big data cleaning process and tuning the parameters for data cleaning； （3） the friendly interface for data input and setting and cleaned data collection for big data. The cloud clean system is a promising system that provides efficient and effect data cleaning mechanism for big data in either files or database.
Keywords： Big Data； Data Quality； Cloud Clean； Map-Reduce
0 引 言
大数据已经广泛地应用于各个领域，其数据质量问题逐渐被人们所关注。这主要是由两方面的因素导致的：一方面大数据由海量的数据源获得，不同的数据来源使其更可能存在不一致冲突和不完整性；另一方面则是因为大数据频繁地变化且难以手动地获取。数据质量问题严重影响着大数据应用的效率，因为低质量数据上的分析和查询容易导致错误结果或者误导性的决策。数据清洗无疑能够提升大数据的利用效率。本文设计并实现了一个大数据云清洗系统，提取了数据清洗任务中的基本操作并基于Map-Reduce[1]计算框架实现相应的算法。该系统对多种数据清洗任务均有可观的性能。
1相关工作
虽然已经有很多数据清洗的技术和算法被相继提出，但却并非都适用于大数据上。主要原因如下。
首先，现有的数据清洗算法的效率并不能满足大数据的需求。并行计算是大数据算法的一个常用手段。然而，除了少数实体识别的算法[2-3]外，几乎没有其他的并行数据清洗算法获得提出。具有多种数据质量问题的大数据清洗工作的整体效率往往也都不高。
其次，现有的数据清洗系统[4-7]集中于数据质量的某一方面。NADEEF[8]支持各种形式的规则，但是缺少数据清洗领域的一些重要问题如缺值填充和冲突属性的真值发现等。对于具有多种数据质量问题的大数据而言，这往往是不够高效的。究其原因，一方面多种数据质量问题需要多个不同的系统来完成各自的数据清洗工作，从而导致清洗过程需要多次的导入和导出数据；另一方面，多个数据质量问题往往可能会共享相同的操作，如去除数据冗余[9]和流通数据发现[10]即都需要实体识别。如果不同的数据质量问题均由各自的清洗系统来完成，那么这些相同的操作便将多次执行，不利于全局的优化。
最后，现有的数据清洗系统常常需要设置参数，例如不一致性检测[11]的约束规则，实体识别[12]的阈值。对于小规模数据来说，这些规则能够通过人工的观测和理解来设置。然而对于大数据，仅靠观察来设置是不合理的，而对整个数据人工的遍历一遍更是不可能的。
2云清洗系统概述
清洗大数据的一个很直观、很自然的想法便是将云计算的技术应用其中，并将计算任务分布式地分发给多个节点以提高并行度。本文设计的大数据云清洗系统采用的便是这个思路，基于Map-Reduce封装实现了数据清洗领域的各类基本问题和清洗操作，包括实体识别、不一致性检测和修复、缺值填充和真值发现。
云清洗系统基于Hadoop来实现架构，利用Map-Reduce框架系统能够高效地控制硬件资源执行分布式计算。整个系统的数据流如图1所示。 图1 数据流
Fig.1 Data Flow
系统的数据是组织在分布式文件系统中。而输入数据则是通过文件或者数据库来提供，前者由用户上传，后者将是用户提供数据库的连接信息而由系统来访问。数据输入后存在于分布式文件系统中，而集群中节点的数据则通过分布式文件系统来访问。在清洗过程中，数据在mapper和reducer间传递，清洗结束后数据被送回到分布式文件系统。和输入类似，用户可以将清洗后的数据以文件的形式下载或者提供数据库连接信息再由系统输出到数据库中。
系统的结构如图2所示，其中包含一个Master和多个Slave节点。具体地，Master 节点接收数据清洗任务的输入数据、清洗计划以及参数设置。而清洗计划即是一个清洗操作序列，由系统提供的四种清洗的基本操作构成，这四种操作分别为实体识别、不一致性检测和修复、缺值填充和真值发现，并且四种操作可以重复选择。
图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）任务提交。提交一个数据清洗任务总共需要四类输入：待清洗的数据、由清洗基本操作序列构成的清洗计划、算法的参数和并行节点数。用户可以通过文件的形式或者远程数据库连接的形式提交待清洗的数据。清洗计划则是选择系统提供的四种数据清洗操作中的某几项，组成一个操作序列告诉系统用户的清洗计划。算法的参数则是清洗计划中选择的基本操作所对应的算法中需要的参数输入，这是由用户进行提供的。而并行节点数就是用于进行这次清洗所使用的节点数目。
