随着信息技术的普及, 各行各业逐渐建立起各自的信息化系统, 并在实践中积累大量的业务数据.互联网时代的到来, 数据的种类和来源呈多样化发展, 更新周期大为缩短, 数据量大幅度飙升.如何有效而可靠地分析处理这些数据, 为各行各业的经营决策服务, 成为亟待解决的问题.然而在收集这些数据的过程中, 由于人为因素, 如拼写错误、录入格式不相同和数据更新不及时等原因, 导致数据集存在数据缺失、不一致等数据质量问题.这些问题的存在, 使得数据的价值大打折扣, 相关部门或企业在使用这些数据前需要花费大量的时间和人力审查并纠正存在的错误.数据质量专家指出, 40%~50%的工程预算用于耗时费力地纠正错误数据^[1].

数据的不一致性是指给定的数据集不满足预先给定的数据约束(如函数依赖、条件函数依赖等).不一致性修复是指通过某些数据操作, 如插入、删除或更新, 使得修复后的数据集满足给定的数据约束.不一致性修复问题面临两大挑战:一是满足给定数据约束的候选修复方案有很多, 也就是说, 候选修复方案的数目随着数据集的增加呈爆炸式增长; 二是数据约束数目的增多以及它们之间的相互制约关系增加了不一致性修复问题的难度, 可能会导致同一条元组的属性在上一轮策略中得到修改, 在下一轮又被改回.这些挑战要求修复策略一定要高效且合理.

现有的数据修复方法^{[2, 3]}采用最小代价原则, 也就是修复后的数据集与修复前的数据集的修改代价最小的方案, 但文献[2]仅仅考虑出现在函数依赖的右边的属性.然而现实场景中, 错误的出现位置是随机的, 可能是函数依赖左边的属性, 也可能是右边的属性.例如, 函数依赖f₃:CK→NN由于数字之间的差别不大, 相比用户所属国家(NN), 疲惫的录入人员更可能在输入用户编号(CK)时因走神而录入错误.虽然文献[3]提供含有变量的修改方案V-repair, 可能将函数依赖左边的属性值替换为变量v, 但该修复方案给数据集应用人员带来很大的不便, 因为变量v的正确值是什么, 还需要专家费神分析才能确定.

为了叙述上方便起见, ORDERKEY, O_ORDERSTATUS, R_NAME, P_MFGR, P_BRAND, O_SHIPPRIORITY, CUSTKEY和N_NAME属性名分别代表订单编号、订单状态、地区名、供应商名、供应商标、订单船舶优先权、用户编号和用户所属国家, 依次简记为OR, OO, RN, PM, PB, OS, CK和NN.

另一方面, 一个修复代价小的修复方案并不一定是一个修复质量高的修复方案.现有的修复策略仅仅考虑了数据集中与数据依赖相关的属性信息, 并未考虑数据依赖以外的其他属性以及这些属性之间的相互关系.例如, 在修复如图 1所示的数据依赖f₁时, 只关注与数据依赖相关的属性, 也就是订单编号(OR)和订单状态(OO), 而没有考虑数据依赖以外的属性, 如地区名(RN)、供应商名(PM)和供应商标(PB)等, 以及这些属性与订单编号(OR)、订单状态(OO)的相关信息.数据集中, 元组属性列之间的相关性信息反映了数据的某些内在规律, 使用机器学习方法可以抽取出这部分有用的信息, 为修复方案的确定提供更坚实的推理支撑.然而, 目前的修复研究中没有涉及相关性信息.本文的修复框架能够分析属性列之间的相关性并尝试修复错误出现在数据依赖左边的场景, 且修复后数据集不包含变量.

随着数据采集和处理技术在各行各业的广泛应用, 数据的不确定性普遍存在.针对这些应用场景, 研究者提供了多种描述数据不确定性的数据模型, 这些模型的核心思想是可能世界模型^[4].可能世界模型能够有效地刻画数据集合的不确定性.而概率数据库作为可能世界模型的表述方式, 用概率值量化每个可能世界实例存在的可能性, 是一种不确定性的数据库.本文借助概率数据库表述可能世界的思想, 把满足函数依赖的某个候选修复方案视为一个可能世界实例, 并用概率值量化该候选修复方案正确的可能性.其中, 概率值计算是综合分析属性列之间的相关性、修复代价而得到的.本文设计并实现基于可能世界模型的不一致性修复算法, 以解决给定函数依赖下关系数据的不一致性修复问题.本文的主要贡献如下:

(1) 提出了一种基于可能世界模型的不一致性修复框架.该框架综合分析数据集的有用信息, 如相关信息、统计信息等等, 并为候选修复方案的选择提供信息支撑;

(2) 设计并实现了一种融合了修复代价和基于相关性概率量化的关系数据不一致性修复算法.该算法将候选修复方案类比为可能世界实例, 将候选修复方案正确的可能性量化为可能世界实例的概率, 搜索概率值较高的可能世界实例作为修复方案.该算法具有较好的修复效果;

(3) 在模拟数据集上进行大量实验, 对本文提出的算法进行验证和分析.

本文第1节综述数据修复相关工作.第2节介绍相关基础知识并定义不一致性修复问题.第3节介绍基于可能世界的不一致修复框架, 详细讲述如何构建候选属性记录, 如何筛选候选属性值, 如何量化候选属性值的概率(用于表示该属性值正确的可能程度).第4节设计启发式贪心算法, 用于在满足给定数据依赖的可能世界实例集合中搜索概率值较高的作为修复方案.第5节验证算法的修复效果, 并分析各个参数对算法的影响.最后总结全文工作并对未来工作加以展望.

1 相关工作

在信息化时代, 数据成为企事业单位的重要资源之一.数据修复问题作为数据质量问题的重要组成部分, 一直被学术界广泛关注.早期的数据修复系统或ETL商业工具包的主要目的是进行数据格式的转换^[5], 或者标记差异^[6], 或者由用户定制数据转换操作^[7].这些修复方法并不能处理由函数依赖检测出的冲突情况.早期的数据修复方面的研究^[5]主要关注使用插入和删除操作, 但这样可能使得修复后的数据库实例信息流失, 特别地, 对于重要的信息, 这是无法容忍的.大数据时代的到来, 数据修复问题等数据质量问题重新得到了企事业单位和专家学者的广泛重视, 并进行了广泛的研究, 涌现出各式各样的修复算法和框架^{[1-3, 8-11]}.

这些修复算法的核心思想是:计算出一个数据集D’, 使得D’满足函数依赖, 并且从源数据集D转换成D’的修改量最小.若这个转换操作采用修改元组属性值的方式, 那么检测是否存在这样一个修复后数据集D’已被证明是NP难问题^[2].文献[2]提出了一个以修改量最小为优化目标的启发式修复模型, 该模型借助等价类技术将冲突的检测阶段和修复属性值的确定阶段在一定程度上解耦, 这样, 修复属性值的确定阶段便能汇集更多有效信息, 使得修复属性值的确定是全局最优的.文献[3]提出了一种近似最优修复算法, 该算法利用超图可以产生一个与最优修复的差异在常数范围内的V-repair.文献[8]针对概率数据库的不一致性问题, 将概率数据库描述的可能世界划分成互不重叠的组, 然后在每个组中使用文献[2]的启发式修复算法解决数据不一致性问题.这些修复方法在代价最小的假设下能够得到较好的实验效果, 但是代价最小并不一定就是最合理的, 而且数据集的信息很多, 不仅有构成函数依赖的那些属性, 还有其他的属性.而上述基于代价最小的修复框架和算法仅仅使用了函数依赖相关的属性列, 其他属性列的信息被忽略.若函数依赖包含的属性和函数依赖未包含的属性之间有一定的关系, 深入分析这部分信息有助于改进修复方案.

部分文献[1, 9-11]将数据挖掘或机器学习的信息挖掘和学习技术引入数据修复领域.文献[9]融合了置信传播和关系依赖网络的技术, 提出了一个以数据库为中心的数据清洗框架, 该框架主要是清洗缺失的数据值.文献[10]针对互联网上数据错误的形式多样化现象, 模拟各类错误的产生过程, 提出了一个彻头彻尾的概率清洗框架, 该框架包括一个基于贝叶斯的生成模块和采用最大熵综合各个错误产生过程的错误模块.生成模块主要是计算整个Internet中每个元组t的候选元组t出现的概率, 错误模块主要是综合各类错误产生过程中每个候选元组t变成数据集中元组t的概率.文献[1]统计分析数据集的概率分布, 综合各类机器学习方法为脏元组提供多个局部候选修复, 将全局修复的预测问题转换为图优化问题, 试图找到具有最大可能性并且修改量最小化的修复方案.文献[11]提出了一个最大限度地减少用户参与的交互式修复框架, 主要包括排序模块和学习模块.排序模块主要是使用决策理论的信息价值, 记为VOI, 来为待咨询的一系列修复更新组排序.学习模块主要是综合用户的反馈确定修复更新的不确定性, 使用了主动学习技术.上述文献在进行数据清洗或修复时都使用了机器学习的相关技术, 从数据集中抽取出了有用信息来提升修复的质量或者减少用户的参与, 但这些信息大都分散到数据修复过程的各个模块中, 而且有些文献[1, 9, 10]完全忽略了数据依赖.本文的修复框架考虑了数据依赖对修复的有用信息, 并将学习得到的有用信息以概率的信息形式统一整合在一起, 使得信息的效用得到最大程度的使用.

2 不一致性修复简介

在数据质量领域中, 现有的数据约束形式有很多种, 如函数依赖(FDs)、条件函数依赖(CFDs)、匹配依赖(MDs)和拒绝约束(DCs)等等.数据的不一致性是指给定数据集D和数据约束集C, 至少存在某些元组T={t|t∈D}不满足某个c∈C.本文的数据约束形式是函数依赖, 主要是修复函数依赖检测出的不一致数据.本节首先介绍函数依赖, 然后介绍数据不一致, 并引出不一致性修复问题.

2.1 函数依赖

函数依赖表示数据库中两个属性集合之间的约束关系.每个函数依赖均有如下形式:

$X \to Y, Y \subset X, X \subset Attr\left(R \right), Y \subset Y \subset Attr\left(R \right).$

其中, Attr(R)是指R中所有属性名构成的集合.平凡的函数依赖在数据库实例中始终是成立的, 它的定义为

$X \to Y, Y \subseteq X, X \subset Attr\left(R \right), Y \subset Y \subset Attr\left(R \right).$

数据库中任意元组t_i和t_j, 如果∀x∈X, t_i[x]=t_j[x]成立, 那么由于Y⊂ X, 必然有∀y∈Y, t_i[y]=t_j[y].也就是说, I始终满足平凡函数依赖.所以, 我们仅仅考虑非平凡的函数依赖, 其定义为

$X \to Y, Y\not \subseteq X, X \subset Attr\left(R \right), Y \subset Y \subset Attr\left(R \right).$

任意函数依赖f:X→Y总能使用一元形式的函数依赖集合来等价表示.如果某函数依赖f:X→Y的右边属性集Y的秩为1, 则称f是一元的.由于一般的函数依赖集总能够直接转换成一元的函数依赖集, 为了简化讨论, 本文假设给定的函数依赖集F中每个函数依赖f∈F都是一元的.

2.2 不一致性修复问题描述

所谓数据不一致是指给定数据库实例I不满足函数依赖集F.若给定数据库实例I不满足函数依赖f:X→A, 记为$I\not \models f$.它的语义是指I中存在两个元组t₁和t₂, 它们的X属性值一一对应相同, 但是A的属性值不相同, 其数学描述为:$\exists {t_1}, {t_2} \in I, {t_1}\left[X \right]={t_2}\left[X \right]$且t₁[A]≠t₂[A].类似地, 如果数据库实例I不满足函数依赖集F中某个函数依赖f∈F, 则称数据库实例I不满足F, 记为$I\not \models F$.也就是说, I相对于F是不一致的.若给定数据库实例I满足某个函数依赖f:X→A, 记为$I \models f$.它的语义是指:I中任意两个元组t₁和t₂, 如果它们的X属性值一一对应相同, 那么它们的A的属性值也相同.其数学描述为∀t₁, t₂∈I, 如果t₁[X]=t₂[X], 那么t₁[A]=t₂[A].如果对于函数依赖集F中任意函数依赖f∈F, I均满足f, 则称I满足F, 记为$I \models F$.也就是说, I相对于F是一致的.

所谓不一致性修复问题是指:给定函数依赖集F和不一致的数据库实例I, 通过某些操作, 如插入、删除或更新, 使得修复后的数据库实例I_R满足函数依赖集, 记为${I_R} \models F$.考虑到删除操作会导致有用信息的丢失, 插入操作会在数据库中引入意义不大的记录信息, 本文仅采用更新操作完成修复任务.

3 不一致性修复框架

在本节中, 我们提出了一个基于可能世界模型的不一致性修复框架, 如图 2所示.该框架在借鉴前人的基于修复代价思路的基础上, 融合机器学习方法和信息论中基于互信息的相关性分析, 将数据中对修复有用的信息量化为候选修复值的正确的可能性, 具体描述形式是概率值, 取值范围是[0, 1], 使得从候选修复方案中筛选出更具合理性且修复质量更高的修复方案.

该框架以给定的不一致数据库实例I和函数依赖集合F作为输入, 输出的是满足函数依赖集F, 即${I_R} \models F$, 且概率值较高的可能世界实例I_R.如图 2所示, 该框架主要包括3个阶段, 依次是冲突元组候选属性记录和属性值的构建阶段(Gcarav)、候选属性值的概率量化阶段(Ccavp)以及满足给定函数依赖集F且概率值较高的可能世界实例的搜索阶段(Sqi).

冲突元组候选属性记录和属性值的构建阶段(Gcarav)主要是解决两个问题.

第一, 候选属性记录的确定, 就是错误出现的位置.

所谓冲突元组, 是指那些导致数据库实例I不满足函数依赖集F的那些元组.例如图 1中, 对于f₁:OR→OO, t₁和t₂的OR属性值一一对应相等, 但OO的属性值不相同, 也就是说, t₁和t₂不满足f₁, 所以t₁和t₂是冲突元组.对于t₁而言, 可能是订单编号(OR)也可能是订单状态(OO).由于我们认为错误的位置是随机的, 所以产生两条候选属性记录, 分别是$\left\langle {} \right.$t₁, OR, Vs(t₁, OR)$\left. {} \right\rangle $和$\left\langle {} \right.$t₁, OO, Vs(t₁, OO)$\left. {} \right\rangle $.候选属性记录的形式是三元组$\left\langle {} \right.$t_i, A_k, Vs(t_i, A_k)$\left. {} \right\rangle $, 其中, t_i是指I中第i个元组的唯一标识, A_k是指t_i的第k个属性, Vs(t_i, A_k)是t_i的A_k属性的候选属性值构成的集合.

第二, 候选属性值的选择.

对于某个候选属性记录, 有哪些可能的候选属性值, 也就是Vs(t_i, A_k)的定义, 具体详见第3.1节.

候选属性值的概率量化阶段(Ccavp)主要是从数据角度分析候选属性记录的每个候选属性值作为修复属性值的正确的可能性, 并量化为概率值.简而言之, 就是候选属性值的概率量化计算.我们综合考虑修复代价和相关性两方面信息来量化候选属性值的可信程度.直观上, 假如一个候选属性值作为修复属性值的修复代价较小, 那么该候选属性值是正确值的可能性就比较大, 概率值比较高.直观上, 如果函数依赖f:X→A不包含的B属性值, 与候选属性值有比较大的正相关性, 其中, B∉X∪A, 那么该候选属性值正确的可能性比较大.基于相关性的概率量化就是借助这些函数依赖以外的属性信息, 分析候选属性值的正确的可能性, 具体详见第3.2节.

在可能世界模型中, 一个元组的某属性可能有多个取值.将某元组的所有属性进行笛卡尔乘积可得到该元组的取值的所有可能情况.所谓一个可能世界实例就是从数据集中选择某些元组, 然后对每个元组, 选择它取值的一种可能情况, 所有被选中元组的取值汇聚在一起就构成了该数据集的一个可能世界实例.考虑到修复问题需要求解所有元组的取值, 对可能世界实例进行了约束.一个可能世界实例, 不是针对数据集中的部分元组, 而是针对所有元组.也就是说, 对于数据集中每个元组选择它的一种可能情况, 所有元组的可能情况就构成一个可能世界实例.例如图 1所示, 假设数据集为I, 函数依赖集为F={f₁:OR→OO}, 可得冲突元组集, 进而可得候选属性记录集CARs.所谓候选属性记录集, 是由所有冲突元组的所有候选属性记录构成的集合.对候选属性记录集CARs中每个元素的候选属性值进行过滤操作.订单状态(OO)出现在函数依赖的右边, 所以它的候选属性值有{P, F}, 不包含O, 而订单编号(OR)出现在函数依赖的左边, 对于t₁而言, 与t₁[OO]取值相同的元组有{t₁, t₃, t₄, t₅, t₉}, 所以它的订单编号(OR)的候选属性值是{96, 131, 64, 99, 70}.类似地, 对于t₂而言, 它的订单编号(OR)的候选属性值是{96, 65}.对候选属性记录集中属性值的取值进行过滤操作后, 可得CARs, 它由4个候选属性记录构成, 分别是$\left\langle {} \right.$t₁, OR, {96, 131, 64, 99, 70}$\left. {} \right\rangle $, $\left\langle {} \right.$t₁, OO, {P, F}$\left. {} \right\rangle $, $\left\langle {} \right.$t₂, OR, {96, 65}$\left. {} \right\rangle $和$\left\langle {} \right.$t₂, OO, {P, F}$\left. {} \right\rangle $.为了减少搜索概率值较高可能世界实例的计算量, 直接忽略候选属性记录不包括的属性, 如t₁的地区名(RN)、供应商名(PM)等属性.可能世界实例的构建过程是任取两个候选属性记录, 对这两个候选属性值集合进行笛卡尔乘积, 得到一个超级候选属性记录.将已经处理的候选属性记录从CARs中移除, 并将得到的超级候选属性记录加入CARs, 循环执行, 直到只剩下一个超级候选属性记录.该超级候选记录的属性值集合的每一个元素就是一个可能世界实例.所谓超级候选记录是扩展了候选属性记录的定义后所得, 是由形式为$\left\langle {} \right.$TIDs, As, avs$\left. {} \right\rangle $的三元组构成的集合.其中, TIDs是一个n元组, 即$\left\langle {} \right.$tid₁, tid₂, …, tid_n$\left. {} \right\rangle $, 该元组的元素由元组标识组成, 与属性值集合avs中元素的属性值列表建立一一对应关系, 表示属性值的唯一元组标识.类似地, As也是一个n元组, 即$\left\langle {} \right.$A₁, A₂, …, A_n$\left. {} \right\rangle $, 该元组的元素由元组属性名组成, 与avs中元素的属性值列表建立一一对应关系, 表示属性值的唯一属性标识.TIDs和As元组的维度n由候选属性记录的数目决定.avs是As取值情况构成的集合, 该集合的元素是一个n元组, 即$\left\langle {} \right.$v₁, v₂, …, v_n$\left. {} \right\rangle $.如将$\left\langle {} \right.$t₁, OR, {96, 131, 64, 99, 70}$\left. {} \right\rangle $和$\left\langle {} \right.$t₁, OO, {P, F}$\left. {} \right\rangle $经过笛卡尔乘积操作后, 可得TIDs=$\left\langle {} \right.$t₁, t₁$\left. {} \right\rangle $, As=$\left\langle {} \right.$OR, OO$\left. {} \right\rangle $, avs={$\left\langle {} \right.$96, F$\left. {} \right\rangle $, $\left\langle {} \right.$96, P$\left. {} \right\rangle $, …}.

概率数据库可以很好地描述一个可能世界.例如, 冲突元组集${I_{\bar F}}=\{ {t_1}, {t_2}\} $描述的可能世界可表示成如图 3所示, 其中, 每个属性值都附加一个概率值, 该概率值是融合候选属性值的概率量化阶段(Ccavp)得到的候选属性值的基于相关性的概率和基于修复代价的概率而得.

一个可能世界实例的概率值计算分如下3步来计算.

• 首先, 从候选属性值的量化阶段(Ccavp)得到每个属性值的两个概率并融合为一个;

• 然后, 计算每个元组的概率, 也就是对该元组所有属性值的概率进行累加和操作, 记为p(t_i), 其计算公

式为

$p({t_i})=\sum {p({t_i}, {A_j}, {v_k})}, $

其中, p(t_i, A_j, v_k)是指元组t_i的A_j属性值为v_k的概率值;

• 最后, 将可能世界实例的所有元组的概率进行累加和操作, 记为p(I(PD)), 它的计算公式如下所示:

$p(I(PD))=\sum\limits_{{t_i} \in {I_{\bar F}}} {p({t_i})}, $

其中, PD是指表述可能世界的概率数据库, I(PD)指的是该概率数据库所描述的某个可能世界实例.

满足给定函数依赖且概率值较高的可能世界实例的搜索阶段(Sqi)主要是以可能世界的所有可能世界实例集合作为搜索空间, 从中选择出满足F且实例的概率值较高的实例I_R作为修复方案.选择概率值较高的实例是因为可能世界实例的概率值是由候选属性值的概率值表示的, 该概率值越高, 那么表示构成实例的属性值的

正确性越高、越可信.然而, 采用这种直观的先构建再判断的搜索策略是很低效的.特别是当中元组数目、候选属性数目和候选属性值的取值增大时, 可能世界实例的数目呈爆炸式增长.假设中的元组数目为n, 属性列的数目为k, 且某个元组t_i(i∈[1, 2, …, n])、某个属性A_j(j∈[1, 2, …, k])的取值都有m种, 那么该概率数据库包含的可能世界实例数目为N = n^m^k.鉴于先构建再判断的搜索策略是很低效的, 为此, 在第4节设计并实现了贪婪的搜索算法.

3.1 候选属性记录的构建

候选属性记录的构建主要用来确定哪些冲突元组是有错误的、错误元组的哪个属性含有错误、错误属性的可能取值有哪些, 它们分别对应于候选属性记录三元组形式中的t, A和Vs(t, A)的取值.冲突元组的候选属性记录的数目和候选属性值的数目直接决定了可能世界的实例数目.减少不必要的候选属性记录数目和过滤完全不可能的候选属性值, 可以减少错误值的干扰, 同时减少概率量化阶段的计算量.

直观上, 错误总是出现在小部分里面.对于违反某函数依赖f:X→A的冲突元组集而言, 我们假设小部分元组是有错误的, 而大部分的元组是正确的, 因此只需为小部分元组构建候选属性记录.所谓小部分元组是指I中与该元组t的X和A属性取值相同的元组数目, 记为Num(t[XA]).小于与该元组的X属性取值相同的元组数目, 记为Num(t[X])的一半.如图 1中f₂:PB→PM的冲突元组集{t₁, t₃, t₄}中, t₄就属于小部分元组.因为供应商标(PB)取值为Brand#53的元组数目为3, 而供应商标(PB)取值为Brand#53且供应商名(PM)取值为Manufacturer#4的元组数目为1, 小于3的一半, 所以属于小部分元组, 而t₁和t₃则属于大部分元组, 不需要为它们构建候选属性记录.如果Num(t[XA])等于Num(t[X])的一半, 那么我们为所有的冲突元组构建候选属性记录, 因为这些元组虽然不属于小部分元组, 但是有0.5的概率是含有错误的.如图 1中f₁:OR→OO的冲突元组集{t₁, t₂}, 订单编号(OR)为96的元组数目为2, 订单编号(OR)为96且订单状态(OO)为F的元组数目为1, 所以t₁虽然不属于小部分元组, 但需要为t₁构建候选属性记录.

对于某些含有错误的元组, 可以对该元组违反的函数依赖集进行分析, 事先辨别该错误元组哪部分属性含有错误.这样就可以只为含有错误的属性构建候选属性记录, 而不必为不含错误的属性构建候选属性记录, 减少了不必要的计算和干扰.假设t为违反f:X→A的小部分元组, 且|F_X|大于3, 有如下两种情况可以事先辨别t的哪部分属性含有错误.

• 情况1:t的X中含有错误.

假设该元组t违反了f, 同时违反了给定函数依赖集F_X中所有的函数依赖, 那么我们认为错误出现在函数依赖X属性中.其中, F_X是指给定函数依赖集F中所有左边为X的函数依赖.

反证法:假设对于该元组错误出现在A中, 那么它必定违反f, 但不一定同时违反所有左边为X的函数依赖.

• 情况2:t的A中含有错误.

假设该元组t违反了f, 同时不违反给定函数依赖集F_X中除去f以外的所有函数依赖, 那我们认为t的A中含有错误.

反证法:假设t的X中含有错误, 那么t至少违反F_X中两个函数依赖.

如果属于上述情况, 那么只需为含有错误的属性构建候选属性记录; 反之不属于上述两种情况, 那么, 我们假设错误元组的X属性和A属性均有可能含有错误, 为A属性构建一个候选属性记录, 即$\left\langle {} \right.$t, A, Vs(t, A)$\left. {} \right\rangle $, 为X中每个属性X_i∈X构建一个候选属性记录$\left\langle {} \right.$t, X_i, Vs(t, X_i)$\left. {} \right\rangle $.

候选属性值Vs(t, A)的过滤原则是:只添加可能的候选值, 以排除完全不可能的候选值的干扰.假设F_A是给定函数依赖集F中包含A的那些函数依赖, 过滤的方法是:找出t为满足F_A需要保持一致的那些相关联元组, 将这些相关联元组的A属性值作为候选属性值.对于F_A中某函数依赖f:X→B, 若A与B相同, 也就是在函数依赖的右边, 那么计算t为满足f需要保持一致的所有相关元组集合, 记为refTs(f)={t’|t’[X]=t[X]}.若A与B不相同, 也就是在函数依赖的左边, 那么相关元组集refTs(f)是指与t的C属性值相同的那些元组构成的集合的并集, 即:

$refTs(f)=\bigcup {\{ t'|t'[C]=t[C]\} }, $

其中, C是指除去A以外的函数依赖属性C∈X∪B\A.然后, 将F_A中所有相关元组集的并集作为t的A属性相关的元组集, 这些元组的所有A属性值就构成了候选属性值Vs(t, A), 其数学定义如公式(1)所示.

$Vs(t, A)=\left\{ {t'[A]\left| {t' \in \bigcup\limits_{f \in {F_A}} {refTs(f)} } \right.} \right\}$

(1)

如图 1所示, t₁的订单状态(OO)在f₁的右边, 所以t₁为满足F_OO的相关联元组集合refTs(f₁)为{t₁, t₂}, 那么候选属性值Vs(t₁, OO)为{F, P}.而t₁的订单编号(OR)在f₁的左边, 所以t₁为满足F_OR的相关联元组集合refTs(f₁)为{t₁, t₃, t₄, t₅, t₉}, 也就是所有订单状态(OO)值为F的那些元组.

3.2 候选属性值的概率量化

候选属性值的概率值量化包括基于相关性的概率量化和基于修复代价的概率量化两部分, 那么, 候选属性值的总概率是两者的平均值, 以表示该候选属性值正确的可能程度.

3.2.1 基于相关性的概率量化

数据集中属性列之间的相关性暗含的推理信息, 可以协助确定更合理的修复方案.鉴于本文在处理数据时把所有的属性都视为标称属性来处理, 而信息处理的互信息在量化标称属性的相关性较好, 采用互信息来进行独立性判断和相关程度度量.

相关性分析的核心思想是对某函数依赖f:X→A, 使用互信息量化函数依赖的属性A与数据集中属性B之间的相关程度, 其中, A∈U_f, B∉U_f, U_f=X∪A, U_f是函数依赖的属性集.所谓函数依赖的属性集是指出现在函数依赖的属性构成的集合.若把属性A和B视为随机变量, 那么A和B的互信息记为I(A; B), 其取值范围是[0, min(H(A), H(B))], 其数学定义为I(A; B)=H(A)-H(A|B).熵是随机变量不确定性的度量, 熵越大, 变量的不确定性越高.对于随机变量A, 它的数学定义如公式(2)所示.

$H(A)=-\sum\limits_a {p(a) \times \log p(a)} $

(2)

其中, p(a)是指变量A的取值为a事件发生的概率值.给定B后, A的条件熵H(A|B)是指观察到变量B后A的不确定性, 它的数学定义如公式(3)所示.

$H(A|B)=\sum\limits_b {H(A|B=b) \times p(B=b)} $

(3)

将B的取值为b条件下变量A视为随机变量, 那么H(A|B=b)表示该随机变量的熵; p(B=b)是指变量B的取值为b事件发生的概率值.由于A的熵H(A)量化了观察到变量B之前A的不确定程度, 而条件熵H(A|B)是观测到B后A尚存的不确定性, 所以, 互信息I(A; B)表示变量B包含多少A的信息.当I(A; B)为0时, 表明B与A是相互独立的; 当I(A; B)不为0时, 表明B与A是相关的, 并且两个变量的互信息越大, 那么它们之间的相关程度越高.所谓无冲突数据集I_F是指I中去掉那些冲突元组后, 得到的元组集合, 即I_F⊨F.如图 1所示, 假设数据集为I, 函数依赖集为F={f₁:OR→OO}, 可得无冲突元组集:

${I_F}=\{ {t_3}, {t_4}, {t_5}, {t_6}, {t_7}, {t_8}, {t_9}\}, {U_{{f_1}}}{\rm{=\{ OR, OO\}, OO}} \in {U_{{f_1}}}, {\rm{PM}} \notin {U_{{f_1}}}.$

依据I_F, 可得OO变量的值域为{F, O, P}, p(F)=4/7, p(P)=1/7, p(O)=2/7.进而, 依据公式(2)可得OO的熵H(OO)约为0.96.类似地, PM变量取值为Manufacturer#5, Manufacturer#4, Manufacturer#3, Manufacturer#2发生的概率分别为3/7, 1/7, 2/7, 1/7.OO变量在PM=Manufacturer#5的条件下取值为F, O, P发生的概率分别为2/3, 1/3, 0.可得H(OO|PM=Manufacturer#5)≈0.63, 依据公式(2), 可得:

$H{\rm{(OO|PM=Manufacturer\# 4)=0, }}H{\rm{(OO|PM=Manufacturer\# 3)}} \approx {\rm{0}}{\rm{.69, }}H{\rm{(OO|PM=Manufacturer\# 2)=0}}{\rm{. }}$

将这些值代入公式(3), 可得给定PM后OO的条件熵H(OO|PM)≈0.47.最后, 依据互信息的定义, 可得I(OO; PM)≈0.49.类似地, 可得I(OO; OS)=0, 表明订单船舶优先权(OS)与订单状态是独立的.I(OO; RN)≈0.07比0.47小, 表明供应商名(PM)与订单状态(OO)相关程度比地区名(RN)与订单状态(OO)相关程度要高.

相关性分析的处理流程以无冲突数据集I_F和函数依赖集F为输入, 输出相关信息矩阵array_c, 如过程1所示.L3是将I_F的属性分为两类U_F和, 其中, U_F是函数依赖的属性集, 是非函数依赖的属性集.L5~L12用来判断U_F中每个属性A与其他属性之间是否独立:若不独立, 则量化它们之间的相关性程度.L7是依据定义计算属性A和B的互信息I(A; B).L8~L11则是依据互信息的性质, 如果I(A; B)为0, 那么将B添加到A的独立属性列表(indANs)中; 否则, 将B添加到A的相关属性列表(dANs)中, 并将I(A; B)作为两者相关程度的量化值.L12是将计算得到的相关信息存储在array_c中.

过程1.数据相关性分析.

输入:无冲突数据集I_F, 函数依赖集F;

输出:相关信息矩阵array_c.

1. kgBEGIN

2. array_c←∅

3. $[{U_F}, {U_{\bar F}}] \leftarrow splitAttributes({I_F}, F)$

4. $U \leftarrow {U_F} \cup {U_{\bar F}}$

5. FOR EACH A∈U_F DO

6.   FOR EACH B∈U\A DO

7.     I(A; B)←computeMI(A, B)

8.     IF I(A; B)==0 THEN A.indANs.add(B)

9.     ELSE

10.       A.dANs.add(B)

11.       A.cc.add(I(A; B))

12.   array_c.add(A)

13. RETURN array_c

14. END

基于相关性的概率量化是使用机器学习算法和相关性信息矩阵array_c, 为每个候选值的正确程度进行概率量化.一方面, 由于本文关注标称属性数据的修复问题, 而k最近邻算法简单且易于改进, 在大多数情况下表现良好; 另一方面, 由于k最近邻分类算法在预测阶段使用投票的方式, 这样可以把投票比例转换为候选值的可信程度的概率值, 所以考虑使用k最近邻算法结合相关信息矩阵分析并量化每个候选值正确的可能性.相关性信息矩阵array_c可减少机器学习方法的计算量, 同时提高候选值可信程度量化的准确率.例如在计算候选属性记录$\left\langle {} \right.$t₁, OO, {P, F}$\left. {} \right\rangle $中每一个候选属性值的概率时, 机器学习方法需要考虑t₁的其他属性列的信息, 如订单编号(OR)、供应商名(PM)等.由于订单状态(OO)与订单船舶优先权(OS)的互信息I(OO; OS)为0, 那么它们独立.在计算t₁的订单状态(OO)候选属性值的概率时, 可以把订单船舶优先权(OS)排除掉, 减少计算量, 同时不影响概率量化的准确性.另一方面, 如果两个变量的互信息越大, 表明它们之间的相关程度越高, 那么在候选属性值的概率量化时, 相关属性信息按照互信息的大小进行加权处理, 使得候选属性值的概率计算更准确.具体就是在k最近邻算法的加权距离测量公式中, 如公式(4)所示, 将相关属性A_k的属性值与C属性的互信息I(C; A_k)作为它们编辑距离的权重.

$d(t, x)=\sqrt {\sum\limits_{{A_k} \in dAN{s_c}} {I(C; {A_k}) \times diff(t[{A_k}], x[{A_k}])} } $

(4)

其中, C为候选属性记录的属性, k最近邻算法把C作为类别属性来处理.

由于本文处理的是符号数据, 也就是标称属性, 所以属性值t[A_k]与x[A_k]之间的距离, 如公式(4)的diff(t[A_k], x[A_k])所示, 采用字符串的编辑距离, 而非欧式距离.如图 1所示, 假设测试元组t为t₁, 训练数据集中某元组x为t₃, 候选属性记录的属性C为OO, 与OO相关的属性集dANs_C={OR, RN, PM, PB, CK, NN}, 它们与OO的互信息依次为{0.95, 0.07, 0.48, 0.76, 0.95, 0.29}, 按照公式(4)计算可得d(t₁, t₃)≈14.25.假设k近邻的训练集为I_F={t₃, t₄, t₅, t₆, t₇, t₈, t₉}, 且k取值为2, 那么计算训练集中所有元素与t₁的距离, 并选择距离最近的前2个元组{t₄, t₅, }, 由于它们的OO属性的取值均为F, 所以候选属性记录$\left\langle {} \right.$t₁, OO, {P, F}$\left. {} \right\rangle $中候选属性值F的相关性概率值为1.

3.2.2 基于修复代价的概率量化

修复代价概率量化主要是预估每个候选属性值v’∈Vs(t, A)作为正确值更新到数据库实例后, 为保证修改后数据库实例满足F_A, 需要进行的修改操作数目或者更新操作前后冲突元组数目变化量, 然后使用指数函数将修改操作数目或者冲突元组数目变化量转换为[0, 1]的概率值.

假设t违反f:X→B.如果A∈X, 假如要把I中元组t的属性A的值改为v’, 修改后数据库实例记为I’, 那么修复代价记为RCost(t, A, v, v’, f), 其数学表示为公式(5).

$RCost\left({t, A, v, v', f} \right)=VT\left({I', f} \right)-VT\left({I, f} \right)$

(5)

VT(I, f)是指I中不满足函数依赖f的元组数目.类似地, VT(I’, f)是指修改后I’中不满足函数依赖f的元组数目, 其中, f∈F_A.如果把元组t的A属性的正确值v改为v’, 会导致修复代价变为负数, 不便于使用指数函数y=e^{-RCost(t, A, v, v’, f)}将修复代价转换为取值为[0, 1]的概率值.为此, 对公式(5)进行了一次坐标平移变换.坐标平移变换的思路是:在元组t的属性A的候选属性值的修复代价为负值时, 找到最小的修复代价, 记为minRCost(t, A, f), 其数学表示为公式(6).

$\min RCost\left({t, A, f} \right)=\min \left\{ {RCost\left({t, A, v, v', f} \right)|v' \in Vs\left({t, A} \right)} \right\}$

(6)

将该候选属性记录中所有候选属性值的修复代价加上最小的修复代价的绝对值, 这样就可以保证候选属性值的修复代价概率量化均为0~1之间的取值.

如果A与B相同, 那么对于Vs(t, A)中某候选属性值v’的修复代价是指:为保证t满足f, 需要将I中所有t’的A属性值由v改为v’的编辑距离值之和, 其中, t’是指X取值为t[X]的元组, 我们使用编辑距离作为修改操作数目.这里未使用更新操作前后冲突元组数目的变化量, 是由于修改操作数目量化在某些情况下与直观感觉相符合.如图 1所示, 直观上, t₂的订单状态(OO)候选属性值{P, F}的概率都应该是0.5, 确实无法分辨.按照修改操作数目度量t₂的候选属性值P和F的修复代价相同, 可得与直观相符合的概率值.而使用冲突元组数目变化量则会使得t₂的候选属性值P和F的修复代价不相同, 因为若更新为P, 更新前与f冲突的元组数目为2, 更新后还是2, 所以冲突变化量为0.若更新为F, 更新前与f冲突的元组数目为2, 更新后变为0, 所以冲突变化量为-2.在经过坐标变化后, 得到的概率值是不相同的, 与直观不符.

由于A属性值的修改会影响到所有与属性A有关系的函数依赖集F_A, 所以需要对F_A中每个函数依赖计算修复代价, 然后累加求和后, 使用指数函数y=e^-RCost转换为[0, 1]的概率值.

4 不一致性修复算法

本节设计并实现了一种贪心修复算法, 该算法以冲突元组候选属性记录和属性值的构建阶段和候选属性值的概率量化阶段得到的候选属性记录集合CRs为输入, 输出是满足F的数据集I_R.已有研究^[2]证明:计算满足函数依赖集, 且修复代价最小的数据修复问题是一个NP难问题.假如只考虑基于修复代价的概率值, 不考虑基于相关性的概率值, 然后使用指数函数的逆运算——对数函数, 可将修复代价的概率值变换为修复代价, 那么我们的问题就可以转化为文献所述的NP难问题.这说明, 寻找满足函数依赖集并且概率值较高的可能世界实例也是一个NP难问题.这表明了算法的启发式特点.本节的贪心搜索算法是使用贪心技术的启发式算法.本节还证明了算法的可终止性, 并分析了算法的复杂度.

该贪心算法一方面避免了计算量惊人的可能世界实例枚举操作, 另一方面能够在满足函数依赖集F的所有可能世界实例中快速地找到概率值之和较高的实例, 也就是修复解决方案.该算法的处理思路是:

首先, 将候选属性记录由原来的三元组扩展为六元组, 该六元组的形式为$\left\langle {} \right.$t_i, V_j, Vs, RPs, CPs, Ps$\left. {} \right\rangle $.其中, RPs用来存放修复代价的概率量化值, CPs用来存放基于相关性的概率量化值, Ps用来存放RPs和CPs融合后的概率值以表示该候选属性值正确的可能性.这3个概率值均与Vs建立一一对应关系.接着, 依照候选属性记录集合CRs中每个候选属性记录$\left\langle {} \right.$t_i, V_j, Vs, Ps$\left. {} \right\rangle $将数据集I中元组t_i的A_j属性的属性值设置为uncertain, 表示未确定, 此时, 数据集记为I_U.然后, 从所有的候选属性值中抽取出满足函数依赖F的所有候选属性值, 并选择概率值最高的候选属性值, 将原来设置为uncertain的位置更新为该候选属性值.此时, 数据集由原来的I_U变为.不断迭代这个过程, 直到所有的uncertain都标记为被更新过.假如该贪心算法可以找到满足函数依赖且概率值较高的可能世界实例, 那么uncertain标记位的属性值就组成了该可能世界实例.此时, 数据集由原来的I_U变为I_R.假如执行若干次迭代后数据集变为了, 找不到满足函数依赖F的候选属性值, 但还存在uncertain标记的位置, 那么将uncertain标记的元组t属性值必定与中某个元组t’一起对某函数依赖f构成了冲突, 那么将元组t的属性值改为与元组t’相同, 使得函数依赖不冲突.当所有的uncertain都处理完毕后, 该贪心算法就找到了一个满足函数依赖且概率值较高的可能世界实例.

该贪心算法的输入是数据集I、函数依赖集F和冲突元组的候选属性记录集合CRs, 其元素cr∈CRs是冲突元组的那些具有候选属性值的属性, 具体形式是一个六元组$\left\langle {} \right.$t_i, V_j, Vs, RPs, CPs, Ps$\left. {} \right\rangle $.输出满足F的数据集I_R.其伪代码如算法1所示.L2~L10是将候选属性集CRs中每个候选属性值的修复代价概率量化RP和基于相关性的概率量化CP中概率值融合成P.L8是将所有的候选属性值添加到sortedAllAVs中.L9将数据集I中元组cr.tid的cr.AN属性的属性值设置为uncertain.L11~L28是贪心搜索满足函数依赖且概率值较高的可能世界实例的过程.L14是将所有的属性值按照其概率值降序排列.L16是判断当前概率值最高的属性值sortedAllAVs.get[j]是否满足函数依赖:如果满足, 那么将isFind设置为true, 并将该属性值所属的候选属性记录的元组唯一标识、属性标识等信息存放到selectAVInfo, 跳出本次循环.L23是当找到满足函数依赖并且概率值最高的值后, 使用selectAVInfo的信息更新I_U为, 并将候选属性的候选属性值从sortedAllAVs中移除.L26就是处理还存在uncertain标记的位置, 但是未找到满足函数依赖F的候选属性值情况.L29是当所有的不确定标记都被覆盖后, 得到的数据集I_U就是修复方案I_R.

算法1.搜索满足函数依赖集且概率值较高的可能世界实例贪心算法, 记为PWM算法.

输入:数据集I, 函数依赖集F, 候选属性记录集合CRs;

输出:满足函数依赖集F的数据集I_R.

1. BEGIN

2.   FOR EACH cr∈CRs DO

3.     FOR i←0 TO CRs.Avs.length DO

4.       P←(cr.getRP(i)+cr.getCP(i))*0.5

5.       add P into Ps

6.     END FOR

7.     cr.Ps←Ps

8.     sortedAllAVs.addAll(cr.getVs())

9.     setUncertain(I, cr.tid, cr.an)

10. END FOR

11. I_U←I

12. FOR i←0 TO |CRs| DO

13.   isFind←false

14.   Sort sortedAllAVs by av.p in descending order

15.   FOR j←0 TO |sortedAllAVs| DO

16.     isFind←isConsistent(I_U, F, sortedAllAVs.get[j])

17.     IF (isFind)

18.       selectAVInfo←getCrAndAV(sortedAllAVs.get[j])

19.       BREAK

20.     END IF

21.   END FOR

22.   IF (isFind)

23.     ${I'_U} \leftarrow update\left({{I_U}, selectAVInfo} \right)$

24.     ${I_U} \leftarrow {I'_U}$

25.   IF (!isFind)

26.     ${I'_U} \leftarrow processExceptionCase\left({{I_U}, selectAVInfo} \right)$

27.     ${I_U} \leftarrow {I'_U}$

28.   END FOR

29.   Return I_R=I_U

30. END

定理1. 给定任意数据集I和函数依赖集合F, 算法PWM总能终止, 并且返回一个修复方案I_R, 使得${I_R} \models F$.证明:候选属性元组集的数目为N, 也就是数据集I_U中不确定性标记的属性值数目, 每一步都能处理掉一个不确定性标记, 得到, 且满足函数依赖集合F.所以, 算法PWM是可终止的, 并且返回一个修复方案I_R.

• 复杂性分析

该算法的关键操作是找到一个能够更新不确定性标记的候选属性值.由伪代码可知, 该算法的复杂度是O(|CRs|x|sortedAllAVs|).假设数据集I中元组的数目是N, 属性名的数目为M, 每个属性名的候选属性值的数目为L, 那么最坏情况下, |CRs|的取值为NxM, 而|sortedAllAVs|的取值为NxMxL, 所以最坏情况下, 算法复杂度为O(N²x M²xL).然而, 实际情况没有这么差, 因为冲突元组的数目远远小于N, 经过过滤操作后候选属性值的数目L会减少很多, 而且每当确定一个候选属性值, 那么下一次循环中sortedAllAVs集合中与该属性值具有相同元组标识和属性名的属性值就会被移除, 使得sortedAllAVs中元素数目很快减少.

5 实验

本节在模拟数据集上评估并描述基于可能世界模型的不一致性修复方法的实验结果.实验运行环境、数据集以及数据质量的评估标准, 如类似信息检索研究领域的查全率、查准率和F-measure, 会在第5.1节详细介绍.第5.2节则在算法的有效性方面进行详细分析.

5.1 实验配置

所有实验的运行环境配置为Intel(R) Core(TM) i7-4710MQ 2.50GHz处理器, 8GB内存, Windows 8.1中文版64位操作系统.数据集使用MySQL Workbench 5.2.47 CE存储, 编程语言是Java.

实验使用的数据集有TPCH数据集——它是事务处理性能委员会提供的TPC-H基准测试集.其中, TPCH数据集是模拟数据集.为了便于评价, 假设源数据集是正确的, 我们采用的插错策略是随机地选择数据集的一个子集, 然后以概率right%向某函数依赖f:X→A的右边属性A插入错误, 该错误是从属性A的值域DOM(A)中选择与A的原属性值不同的值a’替换掉A的属性值a; 反之, 则以概率1-right%在函数依赖的左边属性名B∈X插入错误, 最终保证插入的错误率达到noi%.其中, noi%是指错误的属性值数目与整个数据集大小的比值, 且所有含错误的元组均是冲突元组, 即, 不满足函数依赖.本实验使用了22个函数依赖.

• 评价基准

评价基准扩展信息检索中常用的查准率、查全率和F-measure.查准率是指修复算法正确更新的属性值数目与更新的属性值数目的比值, 记为Precision.查全率是指修复算法更新的属性值数目与数据集中错误的属性值数目的比值, 记为Recall.F-measure由查全率和查准率计算得到, 定义如下:

$F-measure=2 \times \frac{{Precision \times {\mathop{\rm Re}\nolimits} call}}{{Precision + {\mathop{\rm Re}\nolimits} call}}.$

5.2 实验结果分析

本节在算法的有效性方面详细分析实验效果, 其中, 本文的方法用标签PWM标记, 文献[2]中基于修复代价的修复方法用标签ECR标记.

图 4是固定错误率noi%为0.06和right%为0.8, 数据集的元组数目从200增长到1 600时, 查全率、查准率和F-measure的变化情况.

由图 4可知, 该方法在查全率、查准率和F-measure的度量上均高于基于修复代价的修复方法.

图 5是固定right%为0.8, 数据集的元组数目为1 000, 错误率noi%从0.02变化到0.1时, 查全率、查准率和F-measure的变化情况.

由图 5可知, 基于修复代价的修复方法和基于可能世界模型的修复方法随着错误率的增长, 修复质量变化不大, 但我们的方法在查全率、查准率和F-measure的度量上依然高于基于修复代价的修复方法.

图 6是固定right%为0.8, 数据集的元组数目为1 800, 错误率noi%从0.01变化到0.1时, 查全率和查准率的变化情况.

由图 6可知, 查全率随着插入错误的增多, 变化幅度较小, 而查准率则会有较大的波动, 这主要是因为错误出现形式多样, 特别是在函数依赖的左边出现错误, 且左边的属性值分布比较混乱、程度比较高时, 基于相关性的概率和修复代价的概率量化均无法有效分析真值的概率值, 使得原有错误未改正确, 而新的错误却被引入.

图 7是对比了在固定right%为0.8, noi%为0.06, 数据集的元组数目从800变化到2 000的情况下, 使用不同概率量化方法在查全率、查准率和F-measure的变化情况.其中, 候选属性值的概率值仅使用基于相关性的概率量化, 即Only Correlation所标记, 仅仅使用修复代价的概率量化, 即Only Repair Cost所标记, 以及同时使用两者的概率量化, 即Both所标记.

由图 7可知, 在仅使用修复代价的概率下, 查准率和F-measure有比较大的波动, 表现不够稳定, 而使用基于相关性的概率量化则修复效果比较稳定.

6 总结与展望

本文提出了一种基于可能世界模型的不一致性修复框架, 设计并实现了一种融合了修复代价、属性值相关性的概率量化的不一致性修复算法, 并在模拟数据上验证了算法的有效性.

在数据修复领域还有很多公开问题, 比如:

• 在不一致性修复问题上, 比较多的研究是关于文本数据的修复, 而数值型数据的相关研究比较少;

• 大多数修复是假定数据依赖是存在的, 然后以此为数据依赖提出近似算法, 若数据依赖不存在, 那么如何进行修复的研究相对较少.

今后, 我们将对上述问题进行探索性研究.