杜岳峰¹, 申德荣¹, 张亮², 于戈¹
1.东北大学 信息科学与工程学院，辽宁 沈阳 110819;
2.中国人民解放军 65154部队，辽宁 凌源 122513
收稿日期: 2015-07-31
基金项目: 国家重点基础研究发展计划项目(2012CB316201)；国家自然科学基金资助项目(61033007)。
作者简介: 杜岳峰(1986-)，男，辽宁沈阳人, 东北大学博士研究生;
申德荣(1964-), 女, 辽宁铁岭人, 东北大学教授，博士生导师;
于戈(1962-)，男，辽宁大连人，东北大学教授，博士生导师。

摘要: 基于条件函数依赖提出了一种内容相关的条件函数依赖，并给出基于内容相关的条件函数依赖的一致性清洗方法.通过分析条件函数依赖之间的关系，将相关联的条件函数依赖合并组成内容相关的条件函数依赖.内容相关的条件函数依赖可以检测多条件值下的数据一致性问题并提供可用于一致性修复的参考值.同时，提出了一种一致性修复的代价模型.模型参考内容相关的条件函数依赖对应元组的实际情况进行修复，实现代价最优，同时保证数据一致性.通过在两组真实数据集上进行试验测试，证明提出的基于内容相关的条件函数依赖的一致性清洗方法能够准确地检测数据的一致性问题并加以修复.
关键词：数据清洗条件函数依赖内容相关数据一致性修复代价模型
A Consistency Cleaning Method Based on Content-related Conditional Functional Dependencies
DU Yue-feng¹, SHEN De-rong¹, ZHANG Liang², YU Ge¹
1.School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2.PLA 65154 Troops, Lingyuan 122513, China
Corresponding author: DU Yue-feng, E-mail: dr.duyuefeng@gmail.com
Abstract: Based on conditional functional dependencies, content-related conditional functional dependencies (CCFDs) and the consistency cleaning method were presented based on CCFDs. By analyzing the relationship of the conditional functional dependencies, the related conditional functional dependencies were combined into CCFDs. The CCFDs can not only detect the consistencies under multi-conditional values, but also provide reference values for the consistency repairing. A consistency repairing-cost model was presented. Then the data was corrected to be consistent with the minimal repairing cost according to the actual data. And the repaired results are approved accuracy for both the inconsistency detection and the inconsistency repairing via the experimental evaluation on two real-life datasets.
Key Words: data cleaningconditional functional dependencycontent relativitydata consistencyrepairing-cost model
美国商业调查显示美国每年因数据质量造成的损失高达6000亿美元^[1].数据一致性^[2-3]是数据质量管理的一项重要内容.不一致数据会使数据产生歧义进而对数据分析造成影响，所以必须加以更正.
随着对数据质量的研究愈加深入，关于数据一致性的管理技术也在不断成熟.近年来，对数据一致性的研究主要包括：不一致数据的检测，不一致数据的修复，以及相关的质量管理系统.文献[4-5]提出了一种条件函数依赖，通过对函数依赖进行扩展^[6]，可以更准确地对数据进行一致性检测.文献[7]证明了一致性修复是一个NP完全问题，进而提出了一种启发式的修复方法.文献[8]提出了一种质量管理系统，可以将一致性检测和修复融合在一起，对数据进行清洗.数据内容之间是存在关联关系的，以上方法并没有加以考虑，因此，本文提出了一种基于内容相关的条件函数依赖，并以此对数据进行清洗.
内容相关的条件函数依赖将相关联的条件函数依赖进行合并，可以检测多条件值下的数据一致性问题，并提供可用于一致性修复的参考值.结合内容相关的条件函数依赖，还提出了一种一致性的修复代价模型，首先计算修复代价，然后选择代价最低的修复策略，最终得到准确的修复结果.
1 修复规则定义和问题的提出对于一个关系R，R上所有的属性集合记作attr (R)，R中的元组数记作n.
1.1 内容相关的条件函数依赖定义1 ?内容相关的条件函数依赖CCFD (content-related conditional functional dependency)：ψ:(C|Y→A, S_c).其中，C是条件属性集合，Y是变量属性集合，C和Y由“|”分隔，并且C, Y?attr (R)，C∩Y=?，C, Y合在一起称为规则左部，属性A称为规则右部；Y→A是一个标准函数依赖；S_c是合并后的条件值集合.
表 1是1994年美国人口普查信息，下划线部分为错误数据，括号内为其真实值.同时，本文使用图 1给出的条件函数依赖.一方面，条件函数依赖虽然可以检测出t₁, t₂之间存在的不一致问题，但是无法给出可用于修复的参考值；另一方面，条件函数依赖虽然可以保证t₃的一致性，但是无法检测出t₃中存在的错误信息.
表 1(Table 1)

表 1 1994年美国人口普查信息Table 1 1994 US adult census data tid Country Workclass SalaryLevel t0 Brazil employee 30~50 k t1 China employee 30~50 k t2 China employee 70~90 k(30~50 k) t3 India employee 20~30 k(30~50 k)

表 1 1994年美国人口普查信息 Table 1 1994 US adult census data

通过分析表 1中的数据关系，巴西、中国和印度的雇员工资水平是相互联系的.一方面，对于t₁, t₂之间的不一致问题，可以由t₀提供SalaryLevel值进行修复；另一方面，单独的t₃是满足一致性需求的，如果将t₀和t₃放在一起进行检测，就可以发现t₃中存在的错误，进而加以改正.
例1关于表 1的条件函数依赖：
ψ:(Country, Workclass→SalaryLevel, tp).tp=
(tp₀(Brazil, _‖_), tp₁(China, _‖_), tp₂(India, _‖_))
本文得到的内容相关的条件函数依赖为
ψ:(Country|Workclass→SalaryLevel, S_c).
S_c={Brazil, China, India}.
如果一条内容相关的条件函数依赖ψ关于R是成立的，当且仅当对于?u, v∈R，在u[C], v[C]∈S_c的条件下，如果u[Y]=v[Y]，那么u[A]=v[A].
定理1 ?如果一条内容相关的条件函数依赖ψ关于R是成立的，当且仅当| σ_Yπ_C=Ci(R)|=| σ_Y∪Aπ_C=Ci(R)|.其中，σ_Yπ_C=Ci(R)表示在R上选择C=C_i的元组，然后进行属性Y的投影操作.|σ_Yπ_C=Ci(R)|表示S_c中所有情况下σ_Yπ_C=Ci(R)得到的结果总和中的不同值的个数.
证明：反证法证明充分性.设|σ_Yπ_C=Ci(R)|≠ |σ_Y∪Aπ_C=Ci(R)|，那么至少存在一个非空集合S_c′?S_c，使得在u[C], v[C]∈S_c′的情况下，对于u[Y]=v[Y]，u[A]≠v[A].这与命题的题设相违背，所以假设不成立，原命题充分性成立.必要性的证明方法与充分性相同.定理1成立.
对于关系R上的一个实例I，如果I满足内容相关的条件函数依赖ψ，记作Iψ.Σ是内容相关的条件函数依赖的集合，如果I满足Σ，记作IΣ.
需要说明的是，本文只考虑合并具有相同C, Y, A属性的条件函数依赖.在此基础上，通过数据专家的分析将相关的条件函数依赖进行合并.
在现实生活中，内容相关的条件函数依赖表示相似的事物遵循相同的规则.在多条件值的记录中，如果某一条件值的记录出现数据一致性问题，可以通过其他条件值的记录进行检测和修复.
1.2 数据修复的代价模型对于使用内容相关的条件函数依赖ψ检测出的R中存在的不一致元组集合E={t_k, …, t_m}，本文设计了一种修复代价模型来修复不一致数据，首先给出一些与模型有关的定义.
定义2 ?修复权重(repairing weight)：ω_i=n_i/n.其中，对于?C_i∈S_c, n_i表示R中C=C_i条件下的元组数.权重越高表示修复C=C_i的元组的代价也越大.
定义3 ?修复目标值集合(repairing target set)：

(1)

其中，t_k[Y]是检测出的不一致元组t_k关于Y的属性值.针对出现的不一致元组t_k，从包含在S_c的元组中，找出所有Y=t_k[Y]的元组，选取这些元组关于A的属性值作为修复t_k的参考值.
定理2 ?对于t_k, t_l∈E(k≠l)，如果t_l[Y]=t_k[Y], 那么RT (t_l)=RT (t_k).
对于包含相同Y属性值的不一致元组，它们拥有相同的修复目标值集合.进而，本文提出下面的修复代价模型.
定义4 ?修复代价模型(repairing-cost model)：

(2)

其中：rt (t_k)是需要修复的目标值，rt (t_k)∈RT (t_k); Isrepair_i(rt (t_k))是修复判定函数,

(3)

如果元组的Y属性值与修复的目标值相同，那么不进行修改；否则，考虑将t_i[A]修改为rt[t_k].修复代价模型cost (rt (t_k))用于计算将所有满足t_i[Y]=t_k[Y]条件的不一致数据的A属性值修改为rt[t_k]的代价.
例2使用例1中给出的内容相关的条件函数依赖以及表 1中的数据，首先得到修复权重ω₀=ω₃=0.25，ω₁=ω₂=0.5，修复目标值集合RT (t₀)={“20~30 k”，“30~50 k”，“70~90 k”}.接下来，将“Brazil，China，India”3个国家“employee”的“SalaryLevel”修复为“30~50 k”，其cost (30~50 k)=0.5+0.25=0.75.
对于使用ψ检测出的不一致数据，为每一类包含相同Y属性值的不一致元组集合E′(其中E′?E，并且对于?E′_i, E′_j∈E′，有E′_i[Y]=E′_j[Y])，选择相同的修复目标值rt[t_i]，那么使用ψ进行修复的代价记作cost (ψ).对于使用内容相关的条件函数依赖的集合Σ进行修复的代价记作cost (Σ).
1.3 问题的提出本文要解决的问题是：给定关系R上的一个实例I以及关于R的内容相关的条件函数依赖的集合Σ，使用Σ检测出I中的不一致数据并进行修复，使修复代价cost (Σ)最小并且满足IΣ.
2 内容相关的条件函数依赖的清洗方法2.1 数据一致性清洗方法给定关系R上实例I以及内容相关的条件函数依赖集合Σ，结合修复代价模型，本文提出的数据一致性清洗方法包括一致性检测和一致性修复两个过程，清洗方法如下：
算法1的第5行中，CCFDdetect ()用ψ来检测I中的数据是否一致，并将不一致的数据存在E中；第7行中，CCFDrepair ()对不一致进行修复，并将修复后的结果存在I′中.其中，CCFDdetect ()和CCFDrepair ()会在2.2节和2.3节中介绍.对于算法1，只要发现数据中存在不一致，就会使用Σ进行检测和修复，直到所有的数据一致为止.
表 (Table )

表 算法1: CCFD cleaning method Input：Instance I, CCFDs Σ Output：Consistent Instance I′ 1: Initialize I′=I, E=null, tag=true; 2: while (tag) do 3: ??tag=false; 4: ??for each ψ in Σ do 5: ???E=CCFDdetect (I′, ψ); 6: ???if (E is not empty) then 7: ????I′=CCFDrepair (), tag=true; 8: return I′;

表

需要说明的是文中内容相关的条件函数依赖是不相互蕴含的^[9].规则的蕴含关系的证明是一个NP完全问题，这里不进行详细讨论.使用不相互蕴含的依赖进行修复一定会达到终止状态.
2.2 数据一致性检测方法给定实例I′及内容相关的条件函数依赖ψ，本文提出下面的数据一致性检测方法：
算法2的第1~2行使用定理1来判断I′中的数据是否一致，如果I′中的元组关于属性C的值包含在ψ中，那么使用select (I′, ψ)返回这类元组的集合T；如果数据存在不一致问题，通过第4~7行返回不一致的数据集合E.
表 (Table )

表 算法2: CCFDdetect Input：Instance I′, CCFD ψ Output：Error dataset E 1:T=select (I′, ψ); 2: if (|T[Y]|=|T[Y∪A]|) then 3: ??E=null; 4: else for i=0 to |T| do 5: ??for j=i+1 to |T| do 6: ???if (Ti[Y]=Tj[Y] & & Ti[A]≠Tj[A]) then 7: ????E=E∪Ti∪Tj; 8: return E;

表

2.3 数据一致性修复方法给定不一致的数据集合E及内容相关的条件函数依赖ψ, 本文提出数据一致性修复方法.
算法3的第1行中，对于E中的所有错误数据，将所有包含相同Y属性值的错误归为一类，使用selectY(E, ψ)划分出所有错误类别存在集合S中；第2~3行，使用repairtargets (E, S_i)找出每一类错误的修复目标集合RT (S_i)；第4~7行找出修复代价最小的目标值rt，进而使用repair (I′, ψ, S_i, rt)将I′中处于ψ规则下满足S_i错误的元组统一修改为rt，并返回修改后的结果I′.
表 (Table )

表 算法3: CCFDrepair Input：Instance I′, Error dataset E, CCFD ψ Output：Consistent Instance I′ 1: S=selectY(E, ψ); 2: for i=0 to |S| do 3: ??RT (Si)=repairtargets (E, Si), rt=rt0(Si); 4: ??for j=1 to |RT (Si)| do 5: ????if (cost (rtj(Si)) < cost (rt)) then 6: ??????rt=rtj; 7: ????I′=repair (I′, ψ, Si, rt); 8: return I′;

表

3 实验评估本文使用两组真实数据进行实验，通过可扩展性实验和准确性实验验证清洗方法的效果.
3.1 实验设置本实验使用的两组真实数据(Adults数据集和Census-Income数据集)可以从UCI机器学习数据库中下载.规则集合方面，本实验通过单独使用条件函数依赖和内容相关的条件函数依赖进行对比.其中，Adults数据集使用1 172个条件函数依赖，并将其合并成为462个内容相关的条件函数依赖；Census-Income数据集使用的规则分别为3 772和1 012.进行一致性修复时，使用本文提出的代价模型同传统的Voting方法^[10]进行对比.Voting使用投票的方法选取修改次数最少的修改策略进行一致性修复.本实验的硬件环境为Intel i7-2600(3.4 GHz)处理器及8 GB内存，使用Java语言实现.
3.2 可扩展性实验本实验通过改变数据集中元组数量，观察一致性检测和修复的运行时间.
图 2和图 3描述了清洗方法在Adults及Census-Income数据集上的运行时间.对于检测过程，由于内容相关的条件函数依赖将规则进行了合并，减少了检测的次数，所以花费的运行时间较短.对于修复过程，由于内容相关的条件函数依赖检测出的错误更多，另外在修复时需要考虑更多的参考值，所以花费的运行时间稍长.当元组数量 > 25 000时，运行时间开始趋于平缓.
图 2(Fig. 2)

图 2 Adults数据集上关于元组数量的运行时间Fig.2 Running time w.r.t.n over Adults

图 3(Fig. 3)

图 3 Census-Income数据集上关于元组数量的运行时间Fig.3 Running time w.r.t.n over Census-Income

3.3 准确性实验本实验通过改变数据集中错误数据的比例(noi)，观察一致性检测和修复的结果.其中，本文使用错误检测率(D-precision)=来描述检测的结果，使用错误修复准确率(R-precision)=来描述修复的结果.
图 4表明内容条件函数依赖和函数依赖在Adults及Census-Income数据集上的错误检测率基本贴合数据集中的实际错误情况.总体上CFD和CCFD保持了较高的错误检测率.内容条件函数依赖在进行检测时需要借助其他条件下的数据进行检测，所以错误检测率稍高.
图 4(Fig. 4)

图 4 关于错误数据比例的错误检测率Fig.4 D-precision w.r.t.noi

图 5表明内容相关的条件函数在进行修复时比Voting方法的修复准确率更高.其原因在于两个方面：1)内容相关的条件函数依赖参考其他条件下的数据，检测出的错误更多；2)内容相关的条件函数依赖修复时参考其他的数据，修复更准确.另外，随着错误数据比例的上升，内容条件函数依赖的修复准确率的变化更为平缓.
图 5(Fig. 5)

图 5 关于错误数据比例的错误修复准确率Fig.5 R-precision w.r.t.noi

此外，针对Adults数据集的原始数据，表 2给出了检测和修复的实际结果.
表 2(Table 2)

表 2 Adults数据集上检测和修复的实测数据Table 2 Cleaning results and repair results on Adults 方法 检测错误数 实际错误数 检测次数 正确修复数 Voting CCFDrepair CFD 42 619 46 322 127 410 40 351 - CCFD 43 541 46 322 127 410 - 42 881

表 2 Adults数据集上检测和修复的实测数据 Table 2 Cleaning results and repair results on Adults

从表 2的结果可以看出，不论一致性检测还是一致性修复，考虑数据关联关系的方法都比传统方法更为准确.此外，准确的检测是进行修复的基础，CCFD方法的高准确性检测也为修复提供了良好的基础，得到的修复结果也更为准确.
4 结论在条件函数依赖的基础之上，通过分析条件函数依赖的关系，本文提出了一种内容相关的条件函数依赖.同时，本文提出了一种修复代价模型.使用内容相关的条件函数依赖和修复代价模型进行数据一致性检测和修复，通过将关联的数据放在一起进行分析，可以更为准确地检测数据中存在的不一致问题并进行修复.
参考文献

[1]	Fan W.Data quality:theory and practice[C]// Proceedings of International Conference on Web-Age Information Management.Berlin:Springer-Verlag, 2012:1-16.
[2]	Fan W, Geerts F. Foundations of data quality management[M].San Rafael: Morgan & Claypool, 2012: 1-201.
[3]	Du Y F, Shen D R, Nie T, et al.Discovering condition-combined functional dependency rules[C]// Proceedings of the 16th Asia-Pacific Web Conference.Berlin:Springer-Verlag, 2014:247-257.
[4]	Fan W, Geerts F, Jia X, et al. Conditional functional dependencies for capturing data inconsistencies[J].ACM Transactions on Database Systems Tods Homepage, 2008, 33(2) : 1–44.
[5]	Fan W, Geerts F, Li J, et al. Discovering conditional functional dependencies[J].IEEE Transactions on Knowledge & Data Engineering, 2011, 23(5) : 683–698.
[6]	Flesca S, Furfaro F, Parisi F. Consistency checking and querying in probabilistic databases under integrity constraints[J].Journal of Computer & System Sciences, 2014, 80(7) : 1448–1489.
[7]	Fan W, Ma S, Tang N, et al. Interaction between record matching and data repairing[J].Journal of Data and Information Quality, 2014, 4(4) : 1–16.
[8]	Dallachiesa M, Ebaid A, Eldawy A, et al.NADEEF:a commodity data cleaning system[C]// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data.New York:ACM, 2013:541-552.
[9]	Fan W.Dependencies revisited for improving data quality[C]// Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.Vancouver, 2008:159-170.
[10]	Bohannon P, Fan W, Flaster M, et al.A cost-based model and effective heuristic for repairing constraints by value modification[C]// Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data.New York:ACM, 2005:143-154.