, 冯建华2, 王宁1 1. 北京交通大学 计算机与信息技术学院, 北京 100044;
2. 清华大学 计算机科学与技术系, 数据库组, 北京 100084
收稿日期：2018-07-31
基金项目：国家重点研发计划项目（2018YFC0809800）；国家自然科学基金项目（61373024，61632016，61422205，61521002）
作者简介：郝爽(1990-), 女, 讲师
通信作者：李国良, 副教授, E-mail:liguoliang@tsinghua.edu.cn
摘要：数据清洗是对脏数据进行检测和纠正的过程，是进行数据分析和管理的基础。该文对经典和新兴的数据清洗技术进行分类和总结，为进一步的研究工作提供方向。形式化定义了数据清洗问题，对数据缺失、数据冗余、数据冲突和数据错误这4种数据噪声的检测技术进行详细阐述。按照数据清洗方式对数据噪声的消除技术进行分类概述，包括基于完整性约束的数据清洗算法、基于规则的数据清洗算法、基于统计的数据清洗算法和人机结合的数据清洗算法。介绍了常用的测评数据集和噪声注入工具，并对未来重点的研究方向进行了探讨和展望。
关键词：数据清洗数据噪声噪声检测噪声消除
Survey of structured data cleaning methods
HAO Shuang1,2, LI Guoliang2
, FENG Jianhua2, WANG Ning11.School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China;
2.Database Group, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Abstract: Data cleaning is the process of detecting and repairing dirty data which is often needed in data analysis and management. This paper classifies and summarizes the traditional and advanced data cleaning techniques and identifies potential directions for further work. This study first formally defines the cleaning problem for structured data and then describes error detection methods for missing data, redundant data, conflicting data and erroneous data. The data cleaning methods are then summarized based on their error elimination method, including constraint-based data cleaning, rule-based data cleaning, statistical data cleaning and human-in-the-loop data cleaning. Some important datasets and noise injection tools are introduced as well. Open research problems and future research directions are also discussed.
Key words: data cleaningdirty dataerror detectionerror elimination
在信息时代，数据即是资源。数据可靠无误才能准确地反映现实状况，有效地支持组织决策。但是，现实世界中脏数据无处不在，数据不正确或者不一致会严重影响数据分析的结果，从而产生消极作用。在美国，脏数据导致14%的医疗支出被浪费[1]，导致美国公司一年共损失6 000亿美元[2]。因此，数据清洗在数据分析与管理的过程中扮演着越来越重要的角色。
数据清洗方面的研究最早出现在美国[3]，时至今日，已经涌现出不胜枚举的算法。随着时代的变迁，错误数据的形式变幻多样，数据量的增长也为数据清洗算法的设计提出新的要求，许多传统的数据清洗算法已无法满足大数据时代的需求，因此如何准确高效地清洗脏数据始终是值得研究的课题。
数据清洗旨在识别和纠正数据中的噪声，将噪声对数据分析结果的影响降至最低。数据中的噪声主要包括不完整的数据、冗余的数据、冲突的数据和错误的数据。对数据噪声的检测和消除可以通过自动的算法来实现，也可借助数据清洗的规则, 或者依靠用户的参与。
当下，机器学习和众包技术的发展为数据清洗的研究工作注入了新的活力。机器学习技术可以从用户记录中学习制定清洗决策的规律，从而减轻用户标注数据的负担[4-6]。同时，从清洗规则到机器学习模型的转换使得用户不再需要制定大量的数据清洗规则。众包技术把数据清洗任务发布到互联网，从而集中众多用户的知识和决策[7-8]，众包的形式可以充分利用外部资源优势，在降低清洗代价的同时，提高数据清洗的准确度和效率。
本文对结构化数据的数据清洗技术进行综述和展望。结构化数据是指可以使用二维表结构表示和存储的数据，具有易于输入、存储、查询和分析的特点，因此在现实世界中被广泛应用，例如企业资源计划、医疗信息系统等。目前，国内外已有一些研究人员对数据清洗的相关技术进行了较为全面的综述[9-15]。不同于上述文章，本文着重对各类数据噪声的检测和消除技术进行全面系统化的总结，不仅包含最为经典和最新的研究成果，还展望了数据清洗领域未来的研究方向。
1 问题描述1.1 结构化数据的清洗相关概念数据清洗是识别和消除脏数据中数据噪声的过程，数据清洗的过程可以描述为：给定具有模式R的数据库实例I以及数据质量需求；数据清洗是指找到数据库实例I'，它可以满足所有的数据质量需求，同时清洗代价最小。
不同学科背景下，数据质量需求的表示方式各不相同。在数据内容层面，要求数据具有正确性、完整性、一致性、可靠性等。在数据效用层面，要求数据具有及时性、相关性、背景性等。学术界的研究多聚焦于数据内容质量的提升，特别是缺失数据补全、数据去重和错误数据纠正，此时指导数据清洗的指标可以具体表示为：
1) 完整性约束。实体完整性约束规定数据表的主键不能空和重复；域完整性约束要求表中的列必须满足某种特定的数据类型约束；参照完整性约束规定了数据表主键和外键的一致性；此外，还有用户定义的完整性约束。这些约束大多可以反映属性或属性组之间互相依存和制约的关系，干净的数据需满足这些约束条件。例如，函数依赖X→Y，其中X和Y均为属性集R={A1, A2, …, Am}的子集。给定实例I中的两个元组t1和t2，如果t1[X]=t2[X]，那么必须有t1[Y]=t2[Y]。常用的完整性约束还有条件函数依赖[16-17]、包含依赖[18]、度量依赖[19]、差别依赖[20]等。
2) 数据清洗规则。数据清洗规则可以指明数据噪声及其对应的正确值，当数据表中的属性值与规则指出的真值匹配时，该数据满足数据质量需求。有的清洗规则直接把正确值编码在规则里，例如修复规则[21-22]；而有的清洗规则需要通过建立外部数据源与数据库实例之间的对应关系来获取正确的数据，例如编辑规则[23-24]、Sherlock规则[25]和探测规则[26-27]。常用的外部数据源有主数据和知识库。数据清洗规则含义广泛，数据质量标准和规范多可以形式化为数据清洗规则。
3) 用户需求。这里的用户需求是指由用户直接指明数据库实例中的错误数据和修复措施。用户标注部分数据后，可以通过监督式学习方法(比如支持向量机和随机森林)来模拟用户行为。
1.2 清洗质量的评价指标清洗质量主要是指清洗的准确性和全面性，常用的评价指标有准确率、召回率和F值。考虑一个二分类问题，即实例被分为正类和负类，那么：准确率定义为被分类器判断为正类的实例中正确分类的比例；召回率定义为分类器将正类判断为正类的比例；而F值如式(1)所示，是准确率和召回率的调和平均值。
| $F = 2 \times \frac{{准确率 \times 召回率}}{{准确率 + 召回率}}.$ | (1) |
在利用上述3个度量指标衡量数据清洗的准确性时，需要获得数据库实例I对应的干净数据库实例Ic。现实世界中往往无法直接获取Ic，一种可行的方法是数据经过清洗后，交付于领域专家核实每一步的修改，由此来计算准确率。在学术领域，有人工标注错误数据的数据集非常少，为了衡量数据清洗算法的性能，研究人员往往会在干净的数据库实例Ic中手动注入数据噪声，得到包含脏数据的数据库实例I，通过数据清洗算法获得I'后，利用Ic和I'计算相应的准确率、召回率和F值。
2 数据噪声检测数据清洗的第1步就是检测脏数据中的数据噪声。下面通过表 1中本文作者杜撰的数据，给出结构化数据中可能存在的数据噪声类型以及相应的检测算法。
表 1 员工信息表
| 元组 | 姓名 | 级别 | 城市 | 州 | 年薪/千美元 |
| t1 | Rabin | P8 | San Diego | CA | 400 |
| t2 | Leoan | P5 | New York | NY | -1 |
| t3 | Rabin | P9 | Sa Diego | CA | 400 |
| t4 | Mattan | N/A | San Diego | CE | 310 |
| t5 | Javier | P2 | Chicago | IL | 100 |
表选项
1) 数据缺失。它是指数据库实例中某些属性值缺失或者包含无效值，例如表 1中的t4[级别]。值得注意的是，t2[年薪]也是缺失值，因为“-1”不是有效的工资表达形式。
空数据的检测相对简单，只需要检查不允许为空的属性值是否为空、“NULL”或者“N/A”。DiMaC系统[28]和FAHES系统[29]可以用来检测伪装缺失值，即无效值。对于超出属性域的无效值，由于这些值在语法上不符合给定属性中的常规值，因此可以通过学习每个属性的数据模式来检测这些无效值。特别地，对于数值数据，可以通过基于密度的异常值来检测。对于没有超出属性域的伪装缺失值，FAHES通过计算该值对整个关系表的数据分布的影响来判断是否是无效值。
2) 数据冗余。它是指同一数据在数据库实例中多次出现，即存在数据之间的重复。例如表 1中的元组t1和t3，它们均表示员工Rabin的信息，因此这两条数据存在冗余。如何检测冗余数据这一问题已经得到了广泛研究[13, 30-31]。检测冗余数据的算法多分为3步：数据分组、数据比对和冗余判断。
数据分组即对数据进行聚类操作，把可能指代现实世界中同一事物的数据(即重复数据)聚到一组，这样在进行数据匹配时只需比较相同组别的数据，从而能够大大缩小搜索空间。在过去的几年中涌现出许多数据分组算法[32]，基本上均是通过比较关键属性是否相等或相似来对数据进行分组，对关键属性常见的处理方式有Hash[33-35]、排序[34, 36]、冠层聚类[37]、双标索引[32]等。
数据比对即在每一组内计算每对数据的相似程度，在接下来的冗余判断阶段会根据该相似程度判定是否存在冗余。这里把数据比对和冗余判断阶段的算法分为以下几类：
(1) 基于相似度函数的算法。相似度函数以数据对作为输入，输出一个相似度分值。两条数据越相似，输出的值越大。若两条数据的相似度大于给定的阈值，那么它们就是冗余的[38-40]。
(2) 基于规则的算法。规则是多个断言的组合，若一对数据满足所有的断言，那么它们将满足这个规则，从而被判定为冗余数据。每个断言包含一个相似度函数和一个阈值，许多算法[41-43]需要用户来制定规则，也可以利用现有的技术[44]从正例和负例中学出合适的相似度函数和阈值。
(3) 基于机器学习的算法。冗余判断问题在机器学习技术中可以看作分类问题[36, 45]。在数据比对阶段，计算组内每对数据在某些属性上的相似度，并表示成数据对的特征向量。在接下来的冗余判断阶段，利用训练集训练出分类模型，其中训练集中的正例和负例分别表示冗余和不冗余的数据对。训练出的分类模型可以标记新的数据，常用的模型有决策树[33, 45]、支持向量机[36, 45]等。
(4) 人机结合的算法。用户会参与到基于规则的算法中制定规则，或者基于机器学习的算法中标注数据以获得训练集。此外，也有研究者[7-8]利用众包平台解决数据冗余的问题，例如图 1中的CrowdER[7]。它首先利用机器算法得到可能冗余的数据对，再由众包用户判断一对或一组数据是否冗余。
 |
| 图 1 CrowdER中的数据冗余检测[7] |
| 图选项 |
3) 数据冲突。无法满足完整性约束的两条数据之间存在数据冲突。假设表 1中存在函数依赖[城市]→[州]，那么元组t1和t4存在数据冲突，因为它们具有相同的城市“San Diego”，但是t1[州]和t4[州]不同。
通过完整性约束可以检测数据冲突，而完整性约束可以从干净的数据集中学得。不同的完整性约束有不同的学习方法，但许多完整性约束都是基于函数依赖设计的。函数依赖的学习算法分为自上而下和自下而上两类[46-47]。自上而下的算法首先从高到底依次遍历属性点阵，生成候选函数依赖，然后检查每个候选函数依赖在关系表上的符合度，通过检查的函数依赖会用来过滤其他的候选函数依赖。自上而下的函数依赖生成算法包括TANE[48]、FD_Mine[49]、FUN[50]等。与自上而下的生成算法不同的是，自下而上的算法不会检查候选函数依赖是否符合关系表，而是通过元组的协同集和差异集过滤候选函数依赖。自下而上的函数依赖生成算法有FastFDs[51]、Dep-Miner[52]等。除此之外，条件函数依赖的生成可以参考文[53], 包含依赖的生成可以参考文[54], 差别依赖的生成可以参考文[20]。
4) 数据错误。它是指数据库实例中某些不为空的属性值是错误的，例如属性域错误、拼写错误、格式错误等。数据错误有时会引发数据冲突，但是不冲突的数据不一定是正确数据。举例来说，t3[城市]和t4[州]均是表 1中的错误数据，t4[州]中的错误引发了函数依赖上的数据冲突，但t3[城市]没有导致任何数据冲突。用户可以直接指明错误的数据，除此之外，错误数据的检测算法还可以分为以下几类：
(1) 基于完整性约束的错误检测。完整性约束可以用来检测数据冲突，但是约束本身无法指出冲突的发生是由哪个属性值引发的。举例来说，表 1中元组t1和t4在函数依赖[城市]→[州]上存在冲突，但是仅凭此函数依赖无法判断t1[城市]、t4[城市]、t1[州]和t4[州]中哪个值是错误的，因此基于完整性约束的错误检测多是通过启发式方法猜测错误的值。为了最小化清洗代价，这种情况下往往断定出现频率高的属性值组合是正确的属性值组合[55-56]。此外，还可以利用整体错误检测技术[57-58]，该技术通过建立超图来识别错误数据。超图中的顶点代表的是关系表中的属性值，若一组属性值存在冲突，相应的顶点就属于同一个超边，比如表 1中的t1[城市]、t4[城市]、t1[州]和t4[州]这4个顶点就属于同一个超边。同一个顶点可能属于不同的超边，这样只需要在超图上运行最小顶点覆盖算法就可以找到错误的数据。Hao等提出了一种基于极大独立集的错误检测技术[59]。给定关系表上的一个完整性约束后，可以为关系表建立图模型，其中图模型中的顶点代表关系表中的元组，若两个元组之间存在冲突，对应的顶点之间就有一条边，边上的权值是两个元组之间的清洗代价。若在图模型中找到对应清洗代价最小的极大独立集，那么不在极大独立集中的元组就可以认定为错误的数据。
(2) 基于规则的错误检测。编辑规则[23-24]在关系表和主数据之间建立匹配关系，若关系表中的属性值和与其匹配到的主数据中的属性值不相等，就可以判断关系表中的数据存在错误。编辑规则的形式化定义如式(2)所示,
| $\psi :\left( {\left( {X, {X_{\rm{m}}}} \right) \to \left( {B, {B_{\rm{m}}}} \right), {t_{\rm{p}}}\left[ {{X_{\rm{p}}}} \right]} \right).$ | (2) |
| $\varphi :\left( {\left( {X, {t_{\rm{p}}}\left[ X \right]} \right), \left( {B, T_{\rm{p}}^ - \left[ B \right]} \right)} \right) \to T_{\rm{p}}^ + \left[ B \right].$ | (3) |
 |
| 图 2 数据清洗规则举例 |
| 图选项 |
其中：X是属性集R的子集，tp[X]是属性集X一种可能的取值，代表证据值；属性B属于R\X，Tp-[B]是B的属性域中的一组常量，代表B的错误值，而tp+[B]属于B的属性域但不属于Tp-[B]，代表B的正确值。修复规则的语义是:如果元组t在属性集X上的值t[X]等于tp[X]，在属性B上的值t[B]属于Tp-[B]，那么t[B]就是错误的，正确的值应是Tp+[B]。因此，利用修复规则中的tp[X]和Tp-[B]就可以检测错误的值。Sherlock规则通过在关系表I和主数据Im之间建立匹配关系来清洗关系表，它的形式化定义为
| $\rho :\left( {\left( {X, {X_{\rm{m}}}} \right), \left( {B, B_{\rm{m}}^ - , B_{\rm{m}}^ + } \right), \mathop \approx \limits^ \to } \right).$ | (4) |
(3) 基于统计和机器学习的错误检测。基于统计和机器学习的错误检测算法多是基于统计分析[4-6]的：通过概率模型或关系依赖模型获得输入数据集的定量统计信息，比如属性值的共现信息，然后通过真值推理来检查原始数据值是否在期望范围内，或者查找不符合输入数据整体分布的属性值，这些属性值就是错误的属性值。
数据噪声的类型及检测方法汇总见表 2。
表 2 数据噪声的类型及检测方法汇总
| 噪声类型 | 噪声定义 | 检测方法 |
| 数据缺失 | 数据库实例中某些属性值缺失或者包含无效值 | ①对于缺失数据，可直接检查不允许为空的属性值是否为空、“NULL”或者“N/A” ②对于无效值的检测可参考DiMaC系统[28]和FAHES系统[29] |
| 数据冗余 | 同一数据在数据库实例中多次出现，即存在数据之间的重复 | 包含3个步骤： ①数据分组：可参考文[32] ②数据比对和③冗余判断：基于相似度函数的算法[38-40]、基于规则的算法[41-44]、基于机器学习的算法[36, 45]、人机结合的算法[7-8] |
| 数据冲突 | 无法满足完整性约束的两条数据之间存在数据冲突 | 从干净数据集中学习完整性约束[46-47]以检测脏数据中的数据冲突 |
| 数据错误 | 数据库实例中某些不为空的属性值是错误的，例如属性域错误、拼写错误、格式错误等 | ①基于完整性约束的错误检测：频率[55-56]、整体错误检测技术[57-58]、基于极大独立集的错误检测技术[59] ②基于规则的错误检测：编辑规则[23-24]、修复规则[21-22]、Sherlock规则[25]、探测规则[26-27] ③基于统计和机器学习的错误检测[4-6] ④由用户指出数据集中的错误 |
表选项
3 数据噪声消除真实世界中的脏数据往往不只包含一种类型的数据噪声，因此本节不再讨论每种类型的数据噪声如何消除，而是根据消除方式对数据清洗算法进行分类。
传统的算法[60-66]多是通过元组的增加和删除来清洗关系表中的脏数据，比如删除包含缺失值的元组或者冗余的数据，增加特定的元组使关系表满足包含依赖，删除引发冲突的元组使得关系表满足给定的完整性约束。但是，元组的删除会导致重要信息的流失，元组的增加也不会使查询的结果更加准确。因此，这里主要讨论数据的修复，即把错误的属性值修改成算法推测出的正确值。通过数据修复来清洗数据的算法可以分为基于完整性约束的数据清洗、基于规则的数据清洗、基于统计和机器学习的数据清洗和人机结合的数据清洗。数据清洗结果可能不是唯一的，在这种情况下，可以把所有的清洗可能性枚举出来[67]，若有用户参与到清洗过程中，可以由用户来指明某项数据更新是否可以执行[68]。除此之外，自动的数据清洗算法大多选择对应清洗代价最小的修复方式。清洗代价的定义基于文[55]：若关系表I中的元组t修复成I'中的元组t'，假设元组t的权值是w(t)，那么元组t对应的清洗代价为
| ${\rm{cost}}\left( t \right) = w\left( t \right)\sum\limits_{A \in R} {{\rm{dis}}\left( {t\left[ A \right], t'\left[ A \right]} \right)} .$ | (5) |
| ${\rm{cost}}\left( I \right) = \sum\limits_{t \in I} {{\rm{cost}}\left( t \right)} .$ | (6) |
3.1 基于完整性约束的数据清洗基于完整性约束的数据清洗即给定包含脏数据的关系表I和I中的一组完整性约束Σ，修改关系表或者约束后使得I'满足Σ'中的所有完整性约束。这里首先假设完整性约束Σ是完全正确的，而且仅需要清洗数据，接下来再讨论当Σ存在错误时，如何利用统一的清洗模型来清洗约束和数据。
对数据进行清洗的算法分为局部清洗算法和全局清洗算法，它们的区别在于：局部清洗算法在检测和清洗错误数据时仅考虑当前检测出冲突的完整性约束，而全局清洗算法综合考虑若干个有联系的完整性约束。
局部清洗算法中较为经典的是由Bohannon等在2005年提出的[55]，该算法利用等价类消除函数依赖冲突和包含依赖冲突，NADEEF系统[71]就利用了这种思想。在第2.2节中曾论述过当元组t1和t4在函数依赖X→Y上存在冲突时，仅凭函数依赖无法判断t1[X]、t4[X]、t1[Y]和t4[Y]中哪个值是错误的，因此可以把t1[Y]和t4[Y]修改成相同的值来消除这个冲突，也可以把t1[X]和t4[X]修改成不同的值。Bohannon等的研究[55]仅支持修改Y属性集：所有在X属性集上取值相同的元组会被加入到相同的等价类eqA中，其中A∈Y，而eqA中所有的元组在属性A上均会取相同的值。文[55]中定义了等价类的清洗代价，若等价类中的所有元组在属性A上取值v，那么等价类清洗代价为
| ${\rm{cost}}\left( {{\rm{e}}{{\rm{q}}_A}, v} \right) = \sum\limits_{\left( {t, A} \right) \in {\rm{e}}{{\rm{q}}_A}} {\left( {w\left( t \right) \cdot {\rm{dis}}\left( {v, t\left[ A \right]} \right)} \right)} , $ |
Bohannon等的算法可以通过扩展来解决条件函数依赖上的冲突[72]。在此基础上，Kolahi等的算法[58]除了支持把一个属性值修改成另外一个属性值，还支持在没有足够的信息时把一个属性值修改成一个变量以消除冲突。该思想同样应用在LLUNATIC系统[73]中。Beskales等的算法[74]通过用户定义的强制约束来指定清洗过程中不允许变动的属性值，以此来得到更符合用户预期的清洗结果。
BIGDANSING系统[75]扩展了该等价类的思想以解决分布式数据清洗问题。当得到等价类eqA后，BIGDANSING系统设计了两组map-reduce函数。第1组map函数的键值对表示为＜＜等价类号，属性值＞，计数器＞，用于统计每个等价类中每个属性值的个数，第2组map函数的键值对表示为＜等价类号，＜属性值, 计数器＞＞，用于把同一等价类的统计结果聚在一起，出现频率最高的属性值就选定为该等价类的目标值。
全局清洗算法是由Chu等在2013年提出的[57]。该算法解决的是否定约束上的冲突，但其思路可以扩展到其他完整性约束上。全局清洗算法的系统架构如图 3[57]所示。给定包含脏数据的关系表和一组否定约束，在第2.2节中已讨论如何通过构建数据冲突图来检测错误的属性值，在这里重点讨论寻找取值约束和取值决策模块，即如何确定元组的某个属性t[A]的正确取值。
 |
| 图 3 完整性约束的全局清洗算法[57] |
| 图选项 |
寻找取值约束即寻找t[A]取值方面的约束条件，也就是文[57]中给出的修复上下文这一概念。修复上下文包含两个部分：修复内容和修复表达式。其中修复表达式包含了与修复内容相关的赋值和约束。举例来说，假设关系表I上存在否定约束，
| $\neg \left( {I\left( {X, A} \right), I\left( {X', A'} \right), \left( {X = X'} \right), \left( {A \ne A'} \right)} \right)。$ |
当获得t[A]的修复上下文后，取值决策模块用于确定t[A]的最终赋值。由于修复表达式中可能会存在冲突，比如“t[A]＞6”和“t[A]＜4”这两个修复表达式可能会同时存在于t[A]的修复上下文中，因此取值决策模块的第1步操作就是获得最大的不存在冲突的修复表达式集合。接下来，该模块根据这些修复表达式计算t[A]的最佳赋值策略，该赋值可以满足所有的修复表达式，同时使得清洗代价最小。
上面描述的算法均假设给出的完整性约束是正确的，但是随着数据的集成和业务规则的变化，约束也可能随着时间的推移而发生变化，若使用过时或错误的约束来清洗关系表，不但无法正确地修复错误数据，还可能把正确数据修改错误。因此，学术界提出了数据和约束统一清洗的模型[56, 76-77]。
Chiang等提出的URM模型(unified repair model)[56]利用了最小描述长度原则[78-79]，即给定一组函数依赖Σ，找到一个模型M，它可以利用最小的描述长度来表示关系表I。模型M的描述长度DL(M)=L(M)+L(I|M)。其中：L(M)是模型M的长度，L(I|M)是给定模型M后关系表I的长度。给定函数依赖X→Y，L(M)=|X∪Y|·S，L(I|M)=|X∪Y|·E。其中：|X∪Y|表示函数依赖中包含的属性个数，S表示模型M中的签名个数，E表示关系表I中不能用签名表示的元组个数。在数据清洗方面，URM模型以元组模式为单位来修复数据，元组模式p∈ΠXY(t)表示元组t在函数依赖X→Y相关属性上的投影。URM模型还定义了核心元组模式和异常元组模式，分别表示出现频率高于和低于指定阈值的元组模式，异常元组模式会被修改成和它足够相似且对应清洗代价最小的核心元组模式。由于核心元组模式就是模型M中的签名，因此这个过程可以降低描述长度。在约束修复方面，URM支持在函数依赖的左端X增加属性，以增强约束的满足条件。完整性约束的修改可以增加核心元组模式的个数，降低异常元组模式的个数，因此也可以降低模型的描述长度。对于原始数据表中的冲突，URM中定义了代价模型来衡量数据清洗和约束清洗的代价，并选择清洗代价较小的修复方式。Beskales等的工作[76]也支持数据和约束的统一清洗，但与URM模型不同的是，该工作首先根据给定条件清洗完整性约束，再利用清洗后的约束指导数据的清洗。
Volkovs等提出了连续数据清洗算法[77]以应对数据和约束会发生变化的动态环境。该算法首先利用用户的清洗记录训练分类器，给定一组冲突后，该分类器可以决定通过何种清洗策略来消除冲突：修改数据、修改约束还是数据和约束同时修改。确定清洗策略后，该算法利用代价模型计算出一组代价较小的清洗措施，并交由用户作最终判断，用户的决定可以用来修正分类器。在动态数据环境中，该算法可以通过统计信息捕获数据分布和约束的变化，以支持分类器进行正确的策略分类。
3.2 基于规则的数据清洗数据清洗规则在工业界被广泛利用。这里主要论述4种数据清洗规则，分别是编辑规则[23-24]、修复规则[21-22]、Sherlock规则[25]和探测规则[26-27]。这4种规则的形式化定义已在第2.2节中给出。
规则执行前需要探究规则具有的性质，这些性质包括：1)终止性，即给定一组规则Σ，它们在任意元组上执行都能够达到清洗终止点。经证明，上述4种规则均可满足终止性。2)一致性，即给定一组规则Σ，它们在任意元组上按照不同的顺序执行可以得到相同的清洗结果。经证明，验证修复规则是否满足一致性是多项式时间内可以解决的，但其余3种规则的验证复杂度均是co-NP难。3)决定性，即给定一组规则Σ，它们在任意元组上所有可终止的清洗过程均会得到相同的清洗结果。经证明，满足一致性的规则集合均可以满足决定性。4)蕴含性，即给定一组规则Σ和不在Σ中的规则φ，Σ∪{φ}满足一致性且对于任意元组t，执行Σ和Σ∪{φ}得到的清洗结果是相同的，也就是说规则φ蕴含在规则集Σ中。经证明，验证修复规则、Sherlock规则和探测规则的蕴含性的复杂度均是co-NP难。
编辑规则的执行需要定义域(Z, T)，其中Z是R中的一组属性，T是元组在属性组Z上需要满足的模式。当t[Z]是正确的，即t[Z]满足Tc中定义的某种模式时，编辑规则才能正确修复元组t中的错误，因此计算编辑规则的可执行域是编辑规则执行的首要目标。修复规则、Sherlock规则和探测规则在执行时同时会标记数据：POS(t)是元组t中确定正确的属性值；NEG(t)是元组t中确定错误的属性值；FREE(t)是元组t中正确性未知的属性值。在规则执行前，所有属性均标记为FREE；当规则正确执行后，证据属性X(探测规则中的col(Ve))标记为POS；负面属性B(探测规则中的col(Vn))标记为NEG；若属性B可以被正确修复(主数据和知识库中可以找到对应的值)，B会标记为POS。标记为POS的属性不再被改动。从上述过程可以看出，若规则集满足一致性，那么修复规则、Sherlock规则和探测规则的执行算法是基于Chase的算法，即在每一步选择一个可以执行的规则，直到元组的标记不再被规则集修改。此外，还可以建立倒排索引或者进行规则排序来增加规则的执行效率。
3.3 基于统计的数据清洗基于统计的错误检测算法[4-6]把数据清洗问题转换为统计学习和推理问题，其大致流程如图 4所示。脏数据中的每一个属性值都可以表示成一个随机变量，若属性值是错误的，该随机变量为不确定的值；若属性值是正确的，该随机变量为定值，可以作为训练数据来训练概率模型。此外，完整性约束或参照数据都会被转换为推理规则融入到概率模型中，以获得关于输入数据的一系列定量统计，例如属性值对的共现统计。
 |
| 图 4 基于统计的数据修复[4] |
| 图选项 |
对于每个随机变量，算法计算它的最大后验值以及其属性域中所有值的概率分布，若有用户的参与，属性域的概率分布可用于获得用户的反馈以进一步训练概率模型。这些算法也可以用来推测缺失值。
3.4 人机结合的数据清洗Yakout等提出的GDR(guided data repair)模型[67]是较为经典的人机结合数据清洗模型，该模型流程图如图 5所示。
 |
| 图 5 GDR模型流程图[67] |
| 图选项 |
GDR模型的输入是数据库中的关系表和一组条件函数依赖。首先，该模型检测出在条件函数依赖上存在冲突的脏数据并利用现有算法[72]计算出脏数据可能的清洗方式，加入到更新列表中。更新列表里的数据的结构为＜t, A, v, s＞。其中：v是属性值t[A]一种可能的清洗方式，s代表这条数据清洗措施的置信度。接下来，将更新列表中所有的清洗方式分组后排序，获得收益最大的组会被首先呈现给用户，由用户决定是否执行组内的数据更新。所有被用户确定的数据更新会立刻执行，GDR也会重新检测关系表中是否出现了新的数据冲突。
为了减轻用户负担，用户的决策作为训练集被用于训练机器学习模型。当新的数据清洗策略到来时，由该模型首先判断这些清洗策略是否可以执行，因此最终呈现给用户的除了清洗策略外还有该机器学习模型的判定结果。用户对某些清洗策略的判定结果给出反馈，修正其中的错误判定并重新训练学习模型，直到该模型的判定结果与用户一致或者所有的清洗策略都被用户作出判定。
FALCON系统[80]也是人机结合的数据清洗系统，不同于GDR的是，FALCON不依赖任何数据清洗规则，而是单纯通过与用户的交互来修复数据。用户更新了某个属性值后，FALCON可以通过用户的决策来猜测其他可能的更新并交由用户判断是否可以执行。
该系统的执行流程如图 6[80]所示。用户首先检测数据噪声并提供关系表上的数据修复措施Δ。给定Δ后，FALCON生成一组数据更新策略，它包含的SQL UPDATE语句更少，同时还可以修复数据中更多的错误。接下来，FALCON从这组语句中选择一个有效性未知的语句Q，交由用户判断是否可以执行。如果Q可以执行，那么它会被用来修复关系表中的数据错误。FALCON可以利用Q的执行情况过滤掉一定不会被执行的更新策略，从而提高系统效率。表 3对4类数据清洗算法进行了汇总。
 |
| 图 6 FALCON系统[80] |
| 图选项 |
表 3 数据清洗算法汇总
| 数据清洗方式 | 相关算法 | 适用范围 | 优点 | 缺点 |
| 基于完整性约束 | ①仅清洗数据：局部清洗算法[55, 58, 72, 74]和全局清洗算法[57] ②数据和约束统一清洗算法[56, 76-77] | 存在完整性约束的关系表，数据有一定的重复度 | 不需要依赖主数据、知识库、用户等外部资源 | 数据清洗算法是启发式的，有时无法找到正确的数据修复方式 |
| 基于规则 | ①编辑规则[23-24] ②修复规则[21-22] ③ Sherlock规则[25] ④探测规则[26-27] | 关系表被主数据或知识库覆盖 | 规则可以指明错误的属性值及其修复方式，准确度高 | 依赖外部资源，若主数据或知识库中存在知识缺失，就无法检测和修复关系表中的错误 |
| 基于统计 | ① HoloClean[4] ② ERACER[5] ③ SCARE[6] | 关系表中的数据有一定的统计规律 | 可用于缺失值的推测 | 需要大量的标注数据、效率低 |
| 人机结合 | ① GDR[67] ② FALCON[80] | 存在可以参与清洗过程的用户 | 准确度高 | 需要用户的大量投入 |
表选项
4 常用测评数据集用于数据清洗质量测评的真实脏数据集分为有人工标注错误数据的脏数据集和无人工标注的脏数据集。下面介绍几种常用的测评数据集：
1) RESTAURANT：有人工标注的检测数据冗余的常用数据集。该数据集包含858条、36万对餐馆信息，其中106对数据指代的是同一个餐馆，即冗余数据。
2) WEBTABLE：检测错误数据常用的数据集。WEBTABLE包含两组网页表格，分别是WWT和WEX。WWT有人工标注，包含6 318个网页表格；WEX无人工标注，包含24万个网页表格。
3) PIMA IND.DIA.：来自UCI-ML REPOSITORY的数据集，可用于检测伪装缺失值。该数据集包含768条记录，脏数据没有被人工标出。
除此之外，常用于注入噪声的干净数据集有：
1) HOSPITAL：来自美国卫生署，检测数据冲突常用的数据集。该数据集包含11万条关于医院信息的记录，每条记录包含19个属性。该数据集上有9个函数依赖。
2) TAX：检测数据冲突常用的数据生成器，可生成任意条记录。该数据集存储了个人的地址和纳税信息，每条记录包含13个属性。该数据集上有9个函数依赖。
用于生成数据噪声的工具有：
1) BART[81]：它是注入数据噪声的基准程序，支持注入拼写错误、冗余数据、离群数据和缺失数据。除此之外，BART还可以根据用户输入的否定约束生成数据噪声。很多清洗规则都可以转换成否定约束，例如函数依赖、条件函数依赖、修复规则等。BART还允许用户声明某些数据是不可变动的，因此间接支持了编辑规则。
2) QNOISE：它是一种基于Java的噪声数据生成器，由卡塔尔计算研究所的数据分析小组开发。QNOISE支持注入如下4种类型的噪声：空数据(NULL)、伪缺失数据、冗余数据和基于特定完整性约束的冲突数据。
5 机遇与挑战尽管在结构化数据的清洗方面已经有了很多丰硕的研究成果，但目前在这一课题上仍然存在许多亟待解决的问题。大数据时代的来临和新兴技术的发展为数据清洗带来了新的机遇与挑战，概括下来有以下几个方面：
1) 标准测试集。数据清洗领域缺少大规模的标准测试集，这使得无法统一衡量数据清洗算法的优劣。目前的实验测评多是依赖噪声生成工具或由测评人员人工标注脏数据中的错误。噪声生成工具无法完全模拟真实世界中的数据错误，而通过人工标注方式生成的脏数据往往数据量小，无法全面衡量清洗算法的效率，因此如何获取标准测试集是当前亟待解决一个问题。
2) 对大数据的支持。大数据具有数据量大、类型繁多和数据增长速度快等特点。如何把数据清洗技术应用于数据量大且快速增长的数据集是在大数据时代面临的首要挑战。在大数据场景下，还需解决分布式存储数据、在线增量式数据和多租户共享数据的清洗问题，但是这些领域的数据清洗工作较少且大多依赖于定量分析，如何保证高质量的确定性修复仍是值得研究的方向。另外，数据清洗的过程通常会包含很多代价极高的操作，比如枚举元组对、处理不等式连接等。目前的算法加速策略多是构建数据索引[21, 26]、数据分区[82]和抽样数据清洗[83-84]，但是这些技术仍然无法完全满足大数据时代的需求，新的可扩展性技术有待研发。
3) 众包技术在数据清洗上的应用。众包技术[7-8, 85-86]可以集中众多用户的知识和决策，提高数据清洗的效率，在数据清洗方面有着不可替代的优势。目前已有工作利用众包系统进行数据去重[7, 87]、清洗多版本数据[88]。除上述应用外，当数据清洗所依赖的主数据和知识库存在缺失或错误时，也可以利用众包用户补全、纠正信息，以及清洗关系表。当需要从脏数据中学习出数据清洗规则时，可以利用众包用户标注数据、检测规则的有效性和适用性。让众包用户替代传统清洗算法中的领域专家，需要设计有效的数据分组策略和答案整合策略。但是，由于众包用户的专业程度有限，基于众包的数据清洗算法必须有一定的检错容错机制。
4) 深度学习技术在数据清洗上的应用。深度学习是当下热门技术，已经在许多领域展现了其不可替代的优势，例如计算机视觉、自然语言处理等。深度学习技术在这些领域上的成功使得许多****寻求将其应用于计算机其他领域，其中也包括结构化数据清洗。目前，机器学习技术在数据清洗上的应用多是通过数理统计推测真值或者训练分类树以决定某项数据更新是否执行。若要利用深度学习技术完成更加复杂的数据清洗任务，就必须要像计算机视觉中的卷积神经网络(CNN)和自然语言处理中的递归神经网络(RNN)一样设计新的适用于数据清洗的深度学习模型。同时，还要解决数据表示的问题，即如何把某一个元组、某一列甚至某一个关系表转换成向量表示。
5) 跨领域的数据清洗。数据清洗规则和策略的学习是一项耗时的工作，它需要大量的历史数据和人工投入。若通过迁移学习技术[89]，使获得的清洗规则和策略应用到其他领域的数据集上，那么将大大减少数据清洗的开销。因此，跨领域的数据清洗是日后很有研究价值的一个方向。
6) 私密数据的清洗。许多数据中包含着个人的隐私信息，例如金融数据和医学数据，而数据清洗本身是一项需要检查和还原原始数据的任务。当原始数据无法直接访问，而只能获取到加密或者转换后的数据时，一项重要的工作就是依然能从这些数据中检测出错误信息，并进行数据纠正，修复后的数据经过解密或者转换后，就是表达真实用户信息的干净数据。
6 总结本文在对结构化数据清洗的相关概念和算法进行深入研究的基础上，总结了4类结构化数据中常见的数据噪声以及相应的检测方法，包括数据缺失、数据冗余、数据冲突和数据错误。脏数据中包含多种类型的数据噪声，因此本文从消除的方式上把数据清洗算法分为基于完整性约束的清洗算法、基于规则的清洗算法、基于统计的清洗算法和人机结合的清洗算法，并总结了各类算法的适用范围和优缺点。最后，本文还探讨了大数据时代的来临和新兴技术的发展对数据清洗带来的机遇与挑战，以期促进数据清洗技术在大数据时代稳步发展。
参考文献
| [1] | SHALLCROSS S. 2 Reasons why your data is lying to you[R/OL]. (2016-09-15)[2018-06-25]. http://hollistibbetts.sys-con.com/node/1975126. |
| [2] | BUCKLEY J. Causes of dirty data and how to combat them[R/OL]. (2018-07-13)[2018-06-25]. https://www.qubole.com/blog/causes-of-dirty-data-and-how-to-combat-them. |
| [3] | GALHARDAS H, FLORESCU D, SHASHA D, et al. An extensible framework for data cleaning[C]//IEEE 16th International Conference on Data Engineering. San Diego, USA, 2000. |
| [4] | REKATSINAS T, CHU X, ILYAS I F, et al. HoloClean:Holistic data repairs with probabilistic inference[J]. Proceedings of the VLDB Endowment, 2017, 10(11): 1190-1201. DOI:10.14778/3137628 |
| [5] | MAYFIELD C, NEVILLE J, PRABHAKAR S. ERACER: A database approach for statistical inference and data cleaning[C]//2010 ACM SIGMOD International Conference on Management of Data. Indianapolis, USA, 2010: 75-86. |
| [6] | YAKOUT M, BERTI-éQUILLE L, ELMAGARMID A K. Don't be SCAREd: Use scalable automatic repairing with maximal likelihood and bounded changes[C]//2013 ACM SIGMOD International Conference on Management of Data. New York, USA, 2013: 553-564. |
| [7] | WANG J N, KRASKA T, FRANKLIN M J, et al. CrowdER:Crowdsourcing entity resolution[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1483-1494. DOI:10.14778/2350229 |
| [8] | CHAI C, LI G L, LI J, et al. Cost-effective crowdsourced entity resolution: A partial-order approach[C]//2016 International Conference on Management of Data. San Francisco, USA, 2016: 969-984. |
| [9] | 郭志懋, 周傲英. 数据质量和数据清洗研究综述[J]. 软件学报, 2002, 13(11): 2076-2082. GUO Z M, ZHOU A Y. Research on data quality and data cleaning:A survey[J]. Journal of Software, 2002, 13(11): 2076-2082. (in Chinese) |
| [10] | 杨辅祥, 刘云超, 段智华. 数据清理综述[J]. 计算机应用研究, 2002, 19(3): 3-5. YANG F X, LIU Y C, DUAN Z H. An overview of data cleaning[J]. Application Research of Computers, 2002, 19(3): 3-5. DOI:10.3969/j.issn.1001-3695.2002.03.002 (in Chinese) |
| [11] | 王曰芬, 章成志, 张蓓蓓, 等. 数据清洗研究综述[J]. 现代图书情报技术, 2007, 2(12): 50-56. WANG Y F, ZHANG C Z, ZHANG B B, et al. A survey of data cleaning[J]. New Technology of Library and Information Service, 2007, 2(12): 50-56. (in Chinese) |
| [12] | 赵一凡, 卞良, 丛昕. 数据清洗方法研究综述[J]. 软件导刊, 2017(12): 222-224. ZHAO Y F, BIAN L, CONG X. Survey of data cleaning method in data preprocessing[J]. Software Guide, 2017(12): 222-224. (in Chinese) |
| [13] | ELMAGARMID A K, IPEIROTIS P G, VERYKIOS V S. Duplicate record detection:A survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(1): 1-16. DOI:10.1109/TKDE.2007.250581 |
| [14] | CHU X, ILYAS I F, KRISHNAN S, et al. Data cleaning: Overview and emerging challenges[C]//2016 International Conference on Management of Data. San Francisco, USA, 2016: 2201-2206. |
| [15] | ILYAS I F, CHU X. Trends in cleaning relational data:Consistency and deduplication[J]. Foundations and Trends in Databases, 2015, 5(4): 281-393. DOI:10.1561/1900000045 |
| [16] | FAN W F, GEERTS F, JIA X B, et al. Conditional functional dependencies for capturing data inconsistencies[J]. ACM Transactions on Database Systems (TODS), 2008, 33(2): 6. |
| [17] | BOHANNON P, FAN W F, GEERTS F, et al. Conditional functional dependencies for data cleaning[C]//IEEE 23rd International Conference on Data Engineering. Istanbul, Turkey, 2007: 746-755. |
| [18] | ABITEBOUL S, HULL R, VIANU V. Foundations of databases:The logical level[M]. Boston, USA: Addison-Wesley Longman Publishing, 1995. |
| [19] | KOUDAS N, SAHA A, SRIVASTAVA D, et al. Metric functional dependencies[C]//IEEE 25th International Conference on Data Engineering. Shanghai, China, 2009: 1275-1278. |
| [20] | SONG S X, CHEN L. Differential dependencies:Reasoning and discovery[J]. ACM Transactions on Database Systems (TODS), 2011, 36(3): 16. |
| [21] | WANG J N, TANG N. Towards dependable data repairing with fixing rules[C]//2014 ACM SIGMOD International Conference on Management of Data. Snowbird, USA, 2014: 457-468. |
| [22] | WANG J N, TANG N. Dependable data repairing with fixing rules[J]. Journal of Data and Information Quality (JDIQ), 2017, 8(3-4): 16. |
| [23] | FAN W F, LI J Z, MA S, et al. Towards certain fixes with editing rules and master data[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2): 173-184. DOI:10.14778/1920841 |
| [24] | FAN W F, LI J Z, MA S, et al. Towards certain fixes with editing rules and master data[J]. The VLDB Journal, 2012, 21(2): 213-238. DOI:10.1007/s00778-011-0253-7 |
| [25] | INTERLANDI M, TANG N. Proof positive and negative in data cleaning[C]//IEEE 31st International Conference on Data Engineering. Seoul, Republic of Korea, 2015: 18-29. |
| [26] | HAO S, TANG N, LI G L, et al. Cleaning relations using knowledge bases[C]//IEEE 33rd International Conference on Data Engineering. San Diego, USA, 2017: 933-944. |
| [27] | HAO S, TANG N, LI G L, et al. Distilling relations using knowledge bases[J]. The VLDB Journal, 2018, 27(4): 497-519. DOI:10.1007/s00778-018-0506-9 |
| [28] | HUA M, PEI J. DiMaC: A disguised missing data cleaning tool[C]//14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas, USA, 2008: 1077-1080. |
| [29] | QAHTAN A A, ELMAGARMID A, CASTRO FERNANDEZ R, et al. FAHES: A robust disguised missing values detector[C]//24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. London, UK, 2018: 2100-2109. |
| [30] | K?PCKE H, RAHM E. Frameworks for entity matching:A comparison[J]. Data & Knowledge Engineering, 2010, 69(2): 197-210. |
| [31] | HE Q L, LI Z H, ZHANG X. Data deduplication techniques[C]//2010 IEEE International Conference on Future Information Technology and Management Engineering (FITME). Changzhou, China, 2010: 430-433. |
| [32] | BAXTER R, CHRISTEN P, CHURCHES T. A comparison of fast blocking methods for record linkage[C]//2003 KDD Workshop on Data Cleaning, Record Linkage, and Object Consolidation. Washington, DC, USA, 2003, 3: 25-27. |
| [33] | TEJADA S, KNOBLOCK C A, MINTON S. Learning object identification rules for information integration[J]. Information Systems, 2001, 26(8): 607-633. DOI:10.1016/S0306-4379(01)00042-4 |
| [34] | ELFEKY M G, VERYKIOS V S, ELMAGARMID A K. TAILOR: A record linkage toolbox[C]//18th International Conference on Data Engineering. San Jose, USA, 2002. |
| [35] | TEJADA S, KNOBLOCK C A, MINTON S. Learning domain-independent string transformation weights for high accuracy object identification[C]//International Conference on Knowledge Discovery and Data Mining. Edmonton, Canada, 2002: 350-359. |
| [36] | CHRISTEN P. Febrl: A freely available record linkage system with a graphical user interface[C]//2nd Australasian Workshop on Health Data and Knowledge Management. Wollongong, Australia, 2008: 17-25. |
| [37] | MCCALLUM A, NIGAM K, UNGAR L H. Efficient clustering of high-dimensional data sets with application to reference matching[C]//6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Boston, USA, 2000: 169-178. |
| [38] | BAYARDO R J, MA Y M, SRIKANT R. Scaling up all pairs similarity search[C]//16th International Conference on World Wide Web. Banff, Canada, 2007: 131-140. |
| [39] | CHAUDHURI S, GANTI V, KAUSHIK R. A primitive operator for similarity joins in data cleaning[C]//22nd International Conference on Data Engineering. Atlanta, USA, 2006. |
| [40] | XIAO C, WANG W, LIN X M, et al. Efficient similarity joins for near-duplicate detection[J]. ACM Transactions on Database Systems (TODS), 2011, 36(3): 15. |
| [41] | ARASU A, Ré C, SUCIU D. Large-scale deduplication with constraints using Dedupalog[C]//2009 IEEE 25th International Conference on Data Engineering. Shanghai, China, 2009: 952-963. |
| [42] | HERNáNDEZ M A, STOLFO S J. The merge/purge problem for large databases[C]//1995 ACM SIGMOD International Conference on Management of Data. San Jose, USA, 1995: 127-138. |
| [43] | LEE M L, LING T W, LOW W L. IntelliClean: A knowledge-based intelligent data cleaner[C]//Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Boston, USA, 2000: 290-294. |
| [44] | WANG J N, LI G L, YU J X, et al. Entity matching:How similar is similar[J]. Proceedings of the VLDB Endowment, 2011, 4(10): 622-633. DOI:10.14778/2021017 |
| [45] | BILENKO M, MOONEY R J. Adaptive duplicate detection using learnable string similarity measures[C]//Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, DC, USA, 2003: 39-48. |
| [46] | PAPENBROCK T, EHRLICH J, MARTEN J, et al. Functional dependency discovery:An experimental evaluation of seven algorithms[J]. Proceedings of the VLDB Endowment, 2015, 8(10): 1082-1093. DOI:10.14778/2794367 |
| [47] | LIU J X, LI J Y, LIU C F, et al. Discover dependencies from data:A review[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(2): 251-264. DOI:10.1109/TKDE.2010.197 |
| [48] | HUHTALA Y, K?RKK?INEN J, PORKKA P, et al. TANE:An efficient algorithm for discovering functional and approximate dependencies[J]. The Computer Journal, 1999, 42(2): 100-111. |
| [49] | YAO H, HAMILTON H J. Mining functional dependencies from data[J]. Data Mining and Knowledge Discovery, 2008, 16(2): 197-219. |
| [50] | NOVELLI N, CICCHETTI R. FUN: An efficient algorithm for mining functional and embedded dependencies[C]//International Conference on Database Theory. London, UK, 2001: 189-203. |
| [51] | WYSS C, GIANNELLA C, ROBERTSON E. FastFDs: A heuristic-driven, depth-first algorithm for mining functional dependencies from relation instances extended abstract[C]//International Conference on Data Warehousing and Knowledge Discovery. Munich, Germany, 2001: 101-110. |
| [52] | LOPES S, PETIT J M, LAKHAL L. Efficient discovery of functional dependencies and Armstrong relations[C]//International Conference on Extending Database Technology. Konstanz, Germany, 2000: 350-364. |
| [53] | FAN W F, GEERTS F, LI J Z, et al. Discovering conditional functional dependencies[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(5): 683-698. DOI:10.1109/TKDE.2010.154 |
| [54] | DE MARCHI F, LOPES S, PETIT J M. Efficient algorithms for mining inclusion dependencies[C]//8th International Conference on Extending Database Technology. Prague, Czech Republic, 2002: 464-476. |
| [55] | BOHANNON P, FAN W F, FLASTER M, et al. A cost-based model and effective heuristic for repairing constraints by value modification[C]//2005 ACM SIGMOD International Conference on Management of Data. Baltimore, USA, 2005: 143-154. |
| [56] | CHIANG F, MILLER R J. A unified model for data and constraint repair[C]//2011 IEEE 27th International Conference on Data Engineering. Hannover, Germany, 2011: 446-457. |
| [57] | CHU X, ILYAS I F, PAPOTTI P. Holistic data cleaning: Putting violations into context[C]//2013 IEEE 29th International Conference on Data Engineering (ICDE). Brisbane, Australia, 2013: 458-469. |
| [58] | KOLAHI S, LAKSHMANAN L V S. On approximating optimum repairs for functional dependency violations[C]//12th International Conference on Database Theory. St. Petersburg, Russia, 2009: 53-62. |
| [59] | HAO S, TANG N, LI G L, et al. A novel cost-based model for data repairing[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(4): 727-742. DOI:10.1109/TKDE.2016.2637928 |
| [60] | ARENAS M, BERTOSSI L, CHOMICKI J. Consistent query answers in inconsistent databases[C]//18th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. Philadelphia, USA, 1999: 68-79. |
| [61] | BRAVO L, BERTOSSI L. Logic programs for consistently querying data integration systems[C]//18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 10-15. |
| [62] | CALí A, LEMBO D, ROSATI R. On the decidability and complexity of query answering over inconsistent and incomplete databases[C]//22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. San Diego, USA, 2003: 260-271. |
| [63] | CALI A, LEMBO D, ROSATI R. Query rewriting and answering under constraints in data integration systems[C]//18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 16-21. |
| [64] | CHOMICKI J, MARCINKOWSKI J. Minimal-change integrity maintenance using tuple deletions[J]. Information and Computation, 2005, 197(1-2): 90-121. DOI:10.1016/j.ic.2004.04.007 |
| [65] | GERTZ M, LIPECK U W. A diagnostic approach for repairing constraint violations in databases[M]//JAJODIA S, LIST W, MCGREGOR G, et al, eds. Integrity and internal control in information systems. ⅡCIS 1997. Boston, USA: Springer, 1997, 1: 89-111 |
| [66] | GRECO G, GRECO S, ZUMPANO E. A logical framework for querying and repairing inconsistent databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(6): 1389-1408. DOI:10.1109/TKDE.2003.1245280 |
| [67] | YAKOUT M, ELMAGARMID A K, NEVILLE J, et al. Guided data repair[J]. Proceedings of the VLDB Endowment, 2011, 4(5): 279-289. DOI:10.14778/1952376 |
| [68] | CHU X, MORCOS J, ILYAS I F, et al. KATARA: A data cleaning system powered by knowledge bases and crowdsourcing[C]//2015 ACM SIGMOD International Conference on Management of Data. Melbourne, Australia, 2015: 1247-1261. |
| [69] | COHEN W, RAVIKUMAR P, FIENBERG S. A comparison of string metrics for matching names and records[C]//KDD Workshop on Data Cleaning and Object Consolidation. Washington, DC, USA, 2003: 73-78. |
| [70] | JIANG Y, LI G L, FENG J H, et al. String similarity joins:An experimental evaluation[J]. Proceedings of the VLDB Endowment, 2014, 7(8): 625-636. DOI:10.14778/2732296 |
| [71] | EBAID A, ELMAGARMID A, ILYAS I F, et al. NADEEF:A generalized data cleaning system[J]. Proceedings of the VLDB Endowment, 2013, 6(12): 1218-1221. DOI:10.14778/2536274 |
| [72] | CONG G, FAN W F, GEERTS F, et al. Improving data quality: Consistency and accuracy[C]//33rd International Conference on Very Large Data Bases. Vienna, Austria, 2007: 315-326. |
| [73] | GEERTS F, MECCA G, PAPOTTI P, et al. The LLUNATIC data-cleaning framework[J]. Proceedings of the VLDB Endowment, 2013, 6(9): 625-636. DOI:10.14778/2536360 |
| [74] | BESKALES G, ILYAS I F, GOLAB L. Sampling the repairs of functional dependency violations under hard constraints[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2): 197-207. DOI:10.14778/1920841 |
| [75] | KHAYYAT Z, ILYAS I F, JINDAL A, et al. BIGDANSING: A system for big data cleansing[C]//2015 ACM SIGMOD International Conference on Management of Data. Melbourne, Australia, 2015: 1215-1230. |
| [76] | BESKALES G, ILYAS I F, GOLAB L, et al. On the relative trust between inconsistent data and inaccurate constraints[C]//2013 IEEE 29th International Conference on Data Engineering. Brisbane, Australia, 2013: 541-552. |
| [77] | VOLKOVS M, CHIANG F, SZLICHTA J, et al. Continuous data cleaning[C]//2014 IEEE 30th International Conference on Data Engineering. Chicago, USA, 2014: 244-255. |
| [78] | RISSANEN J. Modeling by shortest data description[J]. Automatica, 1978, 14(5): 465-471. DOI:10.1016/0005-1098(78)90005-5 |
| [79] | COVER T M, THOMAS J A. Elements of information theory[M]. New York, USA: John Wiley & Sons, 1991. |
| [80] | HE J, VELTRI E, SANTORO D, et al. Interactive and deterministic data cleaning[C]//2016 International Conference on Management of Data. San Francisco, USA, 2016: 893-907. |
| [81] | AROCENA P C, GLAVIC B, MECCA G, et al. Messing up with BART:Error generation for evaluating data-cleaning algorithms[J]. Proceedings of the VLDB Endowment, 2015, 9(2): 36-47. DOI:10.14778/2850578 |
| [82] | ANANTHAKRISHNA R, CHAUDHURI S, GANTI V. Eliminating fuzzy duplicates in data warehouses[C]//28th International Conference on Very Large Databases. Hong Kong, China, 2002: 586-597. |
| [83] | WANG J N, KRISHNAN S, FRANKLIN M J, et al. A sample-and-clean framework for fast and accurate query processing on dirty data[C]//2014 ACM SIGMOD International Conference on Management of Data. Snowbird, USA, 2014: 469-480. |
| [84] | KRISHNAN S, WANG J N, FRANKLIN M J, et al. SampleClean: Fast and reliable analytics on dirty data[C/OL]//Bulletin of the IEEE Computer Society Technical Committee on Data Engineering. 2015: 59-75[2018-06-19]. https://www.ocf.berkeley.edu/~sanjayk/old/pubs/sc.pdf. |
| [85] | LI G L, WANG J N, ZHENG Y D, et al. Crowdsourced data management: A survey[C]//2017 IEEE 33rd International Conference on Data Engineering. San Diego, USA, 2017: 39-40. |
| [86] | PARK H, WIDOM J. CrowdFill: Collecting structured data from the crowd[C]//2014 ACM SIGMOD International Conference on Management of Data. Snowbird, USA, 2014: 577-588. |
| [87] | WHANG S E, LOFGREN P, GARCIA-MOLINA H. Question selection for crowd entity resolution[J]. Proceedings of the VLDB Endowment, 2013, 6(6): 349-360. DOI:10.14778/2536336 |
| [88] | TONG Y X, CAO C C, ZHANG C J, et al. CrowdCleaner: Data cleaning for multi-version data on the web via crowdsourcing[C]//2014 IEEE 30th International Conference on Data Engineering. Chicago, USA, 2014: 1182-1185. |
| [89] | MICHALSKI R S. A theory and methodology of inductive learning[M]//MICHALSKI R S, CARBONELL J G, MITCHELL T M. Machine learning. Berlin, Germany: Springer, 1983: 83-134. |
