基于統(tǒng)計(jì)推理的不一致數(shù)據(jù)清洗方法

摘 要：不一致數(shù)據(jù)修復(fù)是數(shù)據(jù)清洗領(lǐng)域的一個(gè)重要研究方向，現(xiàn)有方法大多是基于完整性約束規(guī)則的，采用最小代價(jià)原則進(jìn)行修復(fù)，然而，代價(jià)最小的修復(fù)方案通常是不正確的，導(dǎo)致現(xiàn)有修復(fù)方法的準(zhǔn)確率較低。針對(duì)現(xiàn)有方法準(zhǔn)確率較低的問題，提出了一種基于統(tǒng)計(jì)推理的不一致數(shù)據(jù)清洗方法BayesOUR，兼顧修復(fù)的代價(jià)與質(zhì)量，提高修復(fù)準(zhǔn)確性。BayesOUR主要分為三個(gè)階段：首先根據(jù)完整性約束規(guī)則進(jìn)行錯(cuò)誤檢測(cè)；然后利用貝葉斯網(wǎng)絡(luò)推理所有可能的一致性修復(fù)方案概率；最后選擇概率最大的修復(fù)方案進(jìn)行數(shù)據(jù)清洗。真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果表明，該方法與目前領(lǐng)先的方法相比，能夠顯著提高不一致數(shù)據(jù)修復(fù)的準(zhǔn)確性。

關(guān)鍵詞：不一致數(shù)據(jù)；貝葉斯網(wǎng)絡(luò)；統(tǒng)計(jì)推理

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2024）10-015-2987-06

doi：10.19734/j.issn.1001-3695.2024.02.0055

Cleaning inconsistent data based on statistical inference

Zhang Anzhen1，2，Hu Shengji2，Xia Xiufeng2

（1.Shenyang Institute of Computing Technology，Chinese Academy of Sciences，Shenyang 110168，China;2.School of Computer Science，Shenyang Aerospace University，Shenyang 110136，China）

Abstract：Inconsistent data repair is an important research direction in the field of data repair.Most of the existing methods are based on integrity constraint rules and use the principle of minimum cost for repair.However，the repair scheme with the minimum cost is usually incorrect，which leads to the low accuracy rate of the existing repair methods.To address the problem of low accuracy of existing methods，this paper proposed an inconsistent data repair method based on statistical inference BayesOUR，to balance the cost and quality of repair and improve the repair accuracy.It mainly divided BayesOUR into three phases.Firstly，it performed error detection based on the integrity constraint rule，and then utilized Bayesian network to reason about the probability of all the possible consistent repair schemes.Finally，it selected the repair scheme with the largest probabGKv+QZu+Td7KJLWmUnZiFA==ility for data repair.Experimental results on real data show that the method in this paper can significantly improve the accuracy of inconsistent data repair compared with the current leading methods.

Key words：inconsistent data;Bayesian network;probabilistic inference

0 引言

數(shù)據(jù)清洗（data cleaning）是數(shù)據(jù)預(yù)處理過程中的一個(gè)重要步驟，旨在識(shí)別和糾正數(shù)據(jù)中的錯(cuò)誤、缺失、重復(fù)或者不一致之類的問題。數(shù)據(jù)清洗有助于提高數(shù)據(jù)的質(zhì)量、準(zhǔn)確性和可用性，使其更適合分析和挖掘。隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)質(zhì)量問題也隨之而來，嚴(yán)重影響了生產(chǎn)生活的方方面面，數(shù)據(jù)清洗變得越發(fā)重要。

本文主要研究數(shù)據(jù)不一致問題的數(shù)據(jù)清洗［1］，現(xiàn)有的數(shù)據(jù)清洗方法一是為了盡可能減少對(duì)原始數(shù)據(jù)的改動(dòng)，通常遵循最小化修復(fù)代價(jià)原則，將對(duì)數(shù)據(jù)改動(dòng)最少的修復(fù)方案作為最優(yōu)修復(fù)；二是單純地統(tǒng)計(jì)數(shù)據(jù)整體出現(xiàn)的頻率估計(jì)概率，將概率最大的修復(fù)方案作為最優(yōu)修復(fù)方案。然而，這些方法僅僅考慮了整體的修復(fù)代價(jià)或者修復(fù)概率，沒有考慮整體上的修復(fù)質(zhì)量，導(dǎo)致修復(fù)的準(zhǔn)確率較低。

為此，本文提出了一種基于統(tǒng)計(jì)推理的不一致數(shù)據(jù)清洗方法BayesOUR，該方法利用貝葉斯網(wǎng)絡(luò)上的數(shù)據(jù)結(jié)構(gòu)，考慮其相關(guān)屬性之間的概率信息，進(jìn)行概率的統(tǒng)計(jì)推理來計(jì)算每種修復(fù)方案的正確性概率，選擇概率最大的修復(fù)方案作為最優(yōu)修復(fù)方案，進(jìn)而提高了修復(fù)準(zhǔn)確性。具體過程如下：首先，利用完整性約束規(guī)則進(jìn)行不一致檢測(cè)，識(shí)別不一致元組以及可能出錯(cuò)的屬性；其次，對(duì)每個(gè)出錯(cuò)元組，計(jì)算其所有可能的一致性修復(fù)方案；最后，利用貝葉斯網(wǎng)絡(luò)建模屬性之間的關(guān)聯(lián)關(guān)系，并在此基礎(chǔ)上設(shè)計(jì)高效的統(tǒng)計(jì)推理方法，計(jì)算每種修復(fù)方案的正確概率并從中選擇概率最大的作為最優(yōu)方案。

綜上所述，本文的主要貢獻(xiàn)如下：

a）提出一種高效的啟發(fā)式錯(cuò)誤檢測(cè)方法，可以有效減小不一致元組規(guī)模，提高修復(fù)效率。

b）提出了正確性概率模型來量化修復(fù)方案質(zhì)量，并提出一種高效的統(tǒng)計(jì)推理方法計(jì)算每種修復(fù)方案的正確性概率。

c）通過大量實(shí)驗(yàn)評(píng)估，驗(yàn)證本文方法在真實(shí)世界數(shù)據(jù)集上的有效性和高效性。

1 相關(guān)工作

目前，數(shù)據(jù)清洗領(lǐng)域的研究工作主要分為基于完整性約束規(guī)則的以及規(guī)則與概率相結(jié)合的兩大類［2～6］?；谕暾约s束規(guī)則的方法通常采用最小化修復(fù)代價(jià)原則，選擇對(duì)數(shù)據(jù)改動(dòng)最小的方案進(jìn)行數(shù)據(jù)修復(fù)［7～12］。例如，文獻(xiàn)［13～16］提出了多種啟發(fā)式修復(fù)方法來提高修復(fù)準(zhǔn)確性；文獻(xiàn)［17］提出了迭代式修復(fù)框架DEC，利用聯(lián)合概率分布修復(fù)數(shù)據(jù)錯(cuò)誤；文獻(xiàn)［18］提出了“統(tǒng)計(jì)失真”定義修復(fù)后的數(shù)據(jù)分布與理想數(shù)據(jù)分布之間的距離；文獻(xiàn)［19］提出了基于最大似然估計(jì)的錯(cuò)誤修復(fù)框架SCARE；文獻(xiàn)［20］設(shè)計(jì)了增量式數(shù)據(jù)清洗框架ActiveClean；文獻(xiàn)［21］提出了基于信念傳播和關(guān)系依賴網(wǎng)絡(luò)的迭代修復(fù)框架ERACER。這類方法忽視了數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系，導(dǎo)致修復(fù)準(zhǔn)確性不高。

為了提高修復(fù)準(zhǔn)確率，Prokoshyna等人［22］最早將概率與規(guī)則相結(jié)合，提出了概率擾動(dòng)最小的修復(fù)方案求解方法。隨后，文獻(xiàn)［23，24］提出了基于馬爾可夫邏輯網(wǎng)絡(luò)與拒絕約束規(guī)則的混合式數(shù)據(jù)清洗框架。Rekatsinas等人［25］提出了將完整性約束、知識(shí)庫、統(tǒng)計(jì)學(xué)等多種修復(fù)方法相結(jié)合的HoloClean系統(tǒng)。由于滿足約束規(guī)則的方法不止一個(gè)，Yu等人［26］提出選取概率較大的幾種修復(fù)方案提交給用戶，讓用戶從中選擇真實(shí)值，然后根據(jù)反饋結(jié)果更新概率計(jì)算模型。Mahdavi等人［27］同樣提出結(jié)合統(tǒng)計(jì)學(xué)習(xí)、完整性約束以及概率推理的Raha系統(tǒng)來進(jìn)行錯(cuò)誤數(shù)據(jù)修復(fù)。這些方法在一定程度上提高了修復(fù)準(zhǔn)確率，然而還未達(dá)到實(shí)際應(yīng)用場(chǎng)景對(duì)數(shù)據(jù)質(zhì)量的要求。

2 預(yù)備知識(shí)以及問題定義

本章首先介紹函數(shù)依賴與數(shù)據(jù)修復(fù)背景知識(shí)，其次給出基于統(tǒng)計(jì)推理的不一致數(shù)據(jù)清洗方法的問題定義，最后介紹基于統(tǒng)計(jì)推理的數(shù)據(jù)修復(fù)方法。值得一提的是，本文只考慮由拼寫錯(cuò)誤、替換錯(cuò)誤等引發(fā)的數(shù)據(jù)不一致問題，其他類型的錯(cuò)誤（如缺失值、重復(fù)值等）不在本文研究范圍內(nèi)。

2.1 函數(shù)依賴和數(shù)據(jù)修復(fù)

函數(shù)依賴（functional dependency，F(xiàn)D）是數(shù)據(jù)清洗領(lǐng)域中經(jīng)常使用的一種完整性約束規(guī)則，可以簡(jiǎn)潔有效地表達(dá)屬性之間的關(guān)聯(lián)關(guān)系。為了討論方便，本文也采用函數(shù)依賴作為完整性約束規(guī)則。值得一提的是，本文方法可以通過一些擴(kuò)展應(yīng)用于其他類型的完整性約束規(guī)則。下面，首先介紹本文用到的一個(gè)真實(shí)數(shù)據(jù)集。表1展示了部分訂單信息表（ZIP表示郵政編碼，CT表示城市，STR表示街道，AC表示區(qū)編碼），其中標(biāo)紅的數(shù)據(jù)表示錯(cuò)誤，括號(hào)中的是其真實(shí)值。

定義1 函數(shù)依賴。給定一個(gè)關(guān)系模式R，X和A是R上屬性集，I是R上的實(shí)例。R中FD：X→A，表示X中的屬性取值能夠唯一地確定A中的屬性取值。更正式地說，令ti［A］表示ti元組在A屬性中的取值，F(xiàn)D：X→A對(duì)于所有元組對(duì)ti，tj∈I成立的充要條件如下：如果對(duì)所有B∈X，ti［B］=tj［B］，則ti［A］=tj［A］。稱X為FD的左部屬性（left hand side，LHS），A為右部屬性（right hand side，RHS）。

定義2 屬性字典。給定關(guān)系實(shí)例I及FD集合Σ，Ic是I上的干凈數(shù)據(jù)，若存在Σ中任意FD：X→A，那該FD對(duì)應(yīng)的屬性字典為Ic上X屬性和A屬性的所有取值集合。

例1 假設(shè)表1上的FD為ZIP→CT（即郵政編碼能夠唯一確定城市名稱）。對(duì)應(yīng)的屬性字典為{（6037，Berlin），（2135，Brighton），（2137，Britain）}。

定義3 不一致元組。給定關(guān)系實(shí)例I及FD集合Σ，對(duì)于I中任意元組ti，若存在Σ中任意FD：X→A以及元組tj，j≠i，使得ti［X］=tj［X］，但ti［A］=tj［A］，則ti是不一致元組；反之，ti是一致元組。

例2 假設(shè)表1上的FD為ZIP→CT。對(duì)于t1元組，由于存在t3元組使得t1［ZIP］=t3［ZIP］，但t1［CT］≠t3［CT］，所以t1是不一致元組。

定義4 不一致數(shù)據(jù)集。給定數(shù)據(jù)集實(shí)例D及FD集合Σ，若I中所有元組都是一致元組，則D是一致的，記作D|=Σ;否則，D不一致，記作D|≠Σ。

例3 表1中元組t1、t2和元組t3是不一致的，可以通過修改t1、t2或者修改t3解決不一致問題，形成一致數(shù)據(jù)集。由此看出，表中存在指數(shù)多個(gè)一致數(shù)據(jù)集，即，經(jīng)過錯(cuò)誤檢測(cè)后，會(huì)得到多種修復(fù)方案，為了兼顧數(shù)據(jù)修復(fù)的質(zhì)量與數(shù)量，通過統(tǒng)計(jì)推理的方法得到最優(yōu)的修復(fù)方案。

2.2 問題定義

給定關(guān)系實(shí)例I及一組FD集合Σ，Iu是I的一個(gè)更新集合，對(duì)于Iu中的元組t的最大概率修復(fù)方案J為

J=argmax{∏t∈Iup（tui）：tui∈Ut，Σ}（1）

其中：Ut，Σ表示t的所有一致性修復(fù)方案集合；tui為更新后的元組t，概率為p（ti），p（ti）∈［0，1］。

3 數(shù)據(jù)修復(fù)框架BayesOUR

基于統(tǒng)計(jì)推理的不一致數(shù)據(jù)清洗方法BayesOUR的總體流程如圖1所示，輸入是關(guān)系實(shí)例I以及FD集合Σ，輸出是修復(fù)后的數(shù)據(jù)元組集合，BayesOUR框架主要包括三個(gè)階段：錯(cuò)誤檢測(cè)、概率建模以及最優(yōu)修復(fù)方案求解。錯(cuò)誤檢測(cè)階段利用FD導(dǎo)出矩陣進(jìn)行錯(cuò)誤檢測(cè)，將數(shù)據(jù)分成錯(cuò)誤元組和正確元組；概率計(jì)算階段對(duì)修復(fù)方案正確性概率進(jìn)行建模并給出一種高效的概率推理方法；修復(fù)階段計(jì)算所有一致性修復(fù)方案，并從中選擇概率最大的作為最終的修復(fù)方案。

3.1 錯(cuò)誤檢測(cè)

本節(jié)介紹錯(cuò)誤檢測(cè)階段的具體過程，并且給出FD導(dǎo)出矩陣的定義以及檢測(cè)流程。

定義5 FD導(dǎo)出矩陣。給定實(shí)例I及FD：X→A，若I中元組在X屬性集合上有m種可能取值x1，x2，…，xm，在A屬性上有n種可能的取值a1，a2，…，an，將I中元組按X與A的取值劃分到m×n的導(dǎo)出矩陣Mφ中。矩陣的行表示按X劃分的分組，第i行代表X=xi分組，每個(gè)分組按照A屬性值劃分為不同單元格，位于第j列的格子稱為A=aj單元格，Mφ反映了I中元組在X屬性和A屬性上的取值分布情況。

例4 假設(shè)表1中數(shù)據(jù)按照FD：ZIP→CT，按照ZIP和CT取值劃分得到FD導(dǎo)出矩陣Mφ，結(jié)果如圖2所示。根據(jù)FD語義可知，ZIP值可以確定唯一的CT值，因此FD導(dǎo)出矩陣的每個(gè)分組中應(yīng)有且僅有一個(gè)單元格非空。

錯(cuò)誤檢測(cè)階段遵循少數(shù)服從多數(shù)的原則，將每個(gè)分組中規(guī)模最大的單元格中的元組標(biāo)記為正確元組，其余單元格內(nèi)的元組標(biāo)記為錯(cuò)誤元組。例如，圖2中對(duì)于ZIP=6037分組，CT=Brighton單元格中的元組數(shù)量大于其他分組中的數(shù)量，因此將該單元格內(nèi)的元組t1和t2標(biāo)記為正確，t3標(biāo)記為錯(cuò)誤。

算法1 FD導(dǎo)出矩陣錯(cuò)誤檢測(cè)算法

輸入：實(shí)例I以及函數(shù)依賴集合Σ。

輸出：不一致數(shù)據(jù)修復(fù)元組集合U。

1 for i←1 to|Σ|do

2 根據(jù)給定函數(shù)依賴Σ以及數(shù)據(jù)構(gòu)建FD導(dǎo)出矩陣Mφ

3 計(jì)算每個(gè)分組|X=xi|內(nèi)所有單元格的大小

4 for X=xi∈Mφi do

5 if |X=xi|分組的任一單元格內(nèi)元組數(shù)量最大

6 將該單元格內(nèi)的元組標(biāo)記為正確

7 else

8 將該單元格內(nèi)的元組標(biāo)記為錯(cuò)誤

9 將標(biāo)記錯(cuò)誤的元組放入更新數(shù)據(jù)修復(fù)集U

FD導(dǎo)出矩陣的錯(cuò)誤檢測(cè)算法如算法1所示。算法的輸入是關(guān)系實(shí)例I和FD集合Σ，輸出是不一致數(shù)據(jù)修復(fù)集合U。算法首先對(duì)Σ中的每條函數(shù)依賴φi構(gòu)建FD導(dǎo)出矩陣Mφ，并計(jì)算每個(gè)分組內(nèi)單元格的大小，然后檢測(cè)Mφ中的分組，并將其中錯(cuò)誤元組進(jìn)行標(biāo)記（行1～3）;其次，遍歷FD導(dǎo)出矩陣Mφi，若分組內(nèi)某個(gè)單元格內(nèi)元組數(shù)量最大，確定該單元格內(nèi)元組是正確的，將不在正確單元格內(nèi)的元組標(biāo)記為錯(cuò)誤（行4～8）;最后，將標(biāo)記的元組加入U(xiǎn)中（行9）。

定理1 FD導(dǎo)出矩陣錯(cuò)誤檢測(cè)算法的時(shí)間復(fù)雜度為O（|Σ|N）。

證明 算法1遍歷函數(shù)依賴規(guī)則共進(jìn)行|Σ|次循環(huán)，每次循環(huán)遍歷FD導(dǎo)出矩陣中的元組并標(biāo)記錯(cuò)誤，實(shí)例I中共有N個(gè)元組，因此，總時(shí)間開銷為O（|Σ|N）。

3.2 概率建模與推理

本節(jié)給出修復(fù)方案正確性概率模型，并給出一種基于馬爾可夫毯的概率推理方法，可以有效提高推理效率。

對(duì)于錯(cuò)誤元組t∈U和FD ：X→A，錯(cuò)誤可能出現(xiàn)在FD的左部屬性X或者右部屬性A，在沒有進(jìn)一步分析的情況下，無法確定錯(cuò)誤發(fā)生的具體位置。因此，將X中的屬性和A中的屬性都添加到查詢集合Q中，該查詢集合表示可能發(fā)生錯(cuò)誤的噪聲屬性，稱其他屬性E=A-Q為證據(jù)屬性，它代表干凈的屬性（本文僅考慮不一致性錯(cuò)誤）。因此，錯(cuò)誤元組t可以分為兩部分：噪聲部分t［Q］和干凈部分t［E］。本文目標(biāo)是使用干凈的屬性值來預(yù)測(cè)修改后錯(cuò)誤元組的噪聲屬性的概率。

設(shè)t［E］=t［E1，E2，…，EL］且t［Q］=t［Q1，Q2，…，QL］，SE=DOM（E1）×DOM（E2）×…×DOM（EL）表示證據(jù)屬性的空間，SQ=DOM（Q1）×DOM（Q2）×…×DOM（QK）表示t的查詢屬性的空間。假設(shè)根據(jù)SQ×SE上的概率分布P（Q，E）隨機(jī)生成元組。本文將t修改后的元組tui正確概率建模為給定證據(jù)屬性值的查詢屬性值的條件概率，即P（Q=tui［Q］|E=tui［E］）（簡(jiǎn)稱P（tui［Q］|tui［E］））。根據(jù)貝葉斯理論，得到

p（tui）=P（tui［Q］|tui［E］）=P（tui［Q］，tui［E］）P（tui［E］）（2）

例5 以錯(cuò)誤元組t3為例。由于t3違反了FD：ZIP→CT，在其查詢集合中添加噪聲屬性ZIP和CT，即Q={ZIP，CT}，而其他屬性添加到證據(jù)屬性中，即E={AC，STR}。在給定E的情況下，依據(jù)屬性字典元組t3的一致性修復(fù)方案共有兩種，兩種修復(fù)方案的正確概率分別為p（tu13）=P（ZIP=6037，CT=Berlin|STR=Cindy，AC=203）和p（tu23）=P（ZIP=6037，CT=Brighton|STR=Cindy，AC=203）。

為了推斷正確的概率，本文使用了一個(gè)廣泛的概率圖模型——貝葉斯網(wǎng)絡(luò)，它提供了一種簡(jiǎn)潔地描述屬性的概率分布的方法（圖3）。根據(jù)貝葉斯網(wǎng)絡(luò)中的局部馬爾可夫性質(zhì)，網(wǎng)絡(luò)中所有變量的聯(lián)合分布都可以因式分解為以其父變量為條件的單個(gè)密度函數(shù)的乘積。給定A=Q∪E上的貝葉斯網(wǎng)絡(luò)，式（2）中的P（tui［Q］，tui［E］）可以用以下方程式來近似。

P（tui［Q］，tui［E］）=∏Ki=1P（tui［Qi］|parent（Qi））∏Lj=1P（t［Ei］|parent（Ei））（3）

其中：父節(jié)點(diǎn)parent（Qi）和parent（Ei）分別表示Qi和Ej的父節(jié)點(diǎn)集。由于所有屬性的值都是已知的，所以P（tui［Qi］|parent（Qi））和P（tui［Ej］|parent（Ej））是貝葉斯網(wǎng)絡(luò)中的條件概率表（CPT）中的常量。

式（2）中的P（tui［E］）是證據(jù)屬性的邊際分布，可以通過邊際化查詢屬性上的聯(lián)合分布來計(jì)算，如式（4）所示。類似于先前的分析，對(duì)于Q={Q1，Q2，…，Qk}中的每個(gè)Q，可以根據(jù)CPT有效地確定P（q，tui［E］）。

P（tui［E］）=∑q∈SQP（q，tui［E］）（4）

事實(shí)上，Qi的分布取決于其馬爾可夫毯子中屬性的聯(lián)合分布。因此，本文提出在馬爾可夫毯子的基礎(chǔ)上對(duì)Qi進(jìn)行剪枝。具體地說，設(shè)MB（Q）表示Q的馬爾可夫毯，且MB（Q）=MB（Q1）∩MB（Q2）∩…∩MB（QK）是所有查詢變量的馬爾可夫毯的交集。然后使用MB（Q）中的證據(jù)屬性來剪枝Q，即只考慮與E∩MB（Q）的值在數(shù)據(jù)集中至少出現(xiàn)一次的查詢屬性值。貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)以及條件概率表如圖3所示。

例6 以元組t3為例，當(dāng)t3修復(fù)為tu13時(shí)，其正確性概率計(jì)算過程如下：P（tu13［Q］，tu13［E］）=P（ZIP=6037|CT=Berlin）·P（CT=Berlin|AC=203）·P（STR=Cindy|CT=Berlin，ZIP=6037）·P（AC=203）=0.5×0.67×1×0.33=0.111，對(duì)應(yīng)的MB（Q）={STR}。原始數(shù)據(jù)中STR=Cindy，則ZIP和CT的組合可以是{6037，Berlin}或者{6037，Brighton}。因此，P（tu13［E］）=P（ZIP=6037，CT=Berlin，STR=Cindy，AC=203）+P（ZIP=6037，CT=Brighton，STR=Cindy，AC=203）=0.1105+0.0154=0.1259，則p（tu13）=P（tu13［Q］，tu13［E］）/P（tu13［E］）=0.88。

3.3 最優(yōu)修復(fù)方案求解

通過概率建模和推理檢測(cè)出錯(cuò)誤元組，根據(jù)FD規(guī)則為錯(cuò)誤元組建立屬性字典，其中包含了錯(cuò)誤屬性在e9DVJSLY/gDjqjrqWbJVuGNVt7QSjogsbgz2knQ+q84=干凈數(shù)據(jù)（標(biāo)記為正確的元組）中的所有取值情況。給定證據(jù)屬性下，將屬性字典中的屬性取值賦給錯(cuò)誤元組對(duì)應(yīng)的屬性，從而得到錯(cuò)誤元組所有可能的一致性修復(fù)方案。針對(duì)所有一致性修復(fù)方案，利用式（2）計(jì)算每種一致性修復(fù)方案的正確性概率，并選擇其中概率最高的修復(fù)方案作為錯(cuò)誤元組的最終修復(fù)方案。

例7 依據(jù)屬性字典并計(jì)算一致性修復(fù)方案的正確性概率如圖4所示。在給定E={STR，AC}時(shí)，t3僅有一種修復(fù)方案，選擇概率為0.88的一致性修復(fù)方案。同理，t5和t8選擇概率為0.52的一致性修復(fù)方案。通過對(duì)比表1中的真實(shí)值可以發(fā)現(xiàn)，BayesOUR的修復(fù)結(jié)果都是正確的。

4 實(shí)驗(yàn)

在本章中，本文在不同的數(shù)據(jù)集上將BayesOUR和最先進(jìn)的方法HoloClean進(jìn)行對(duì)比，此外，還對(duì)不同的錯(cuò)誤率以及錯(cuò)誤類型進(jìn)行分析。

4.1 實(shí)驗(yàn)設(shè)置

BayesOUR以及對(duì)比方法HoloClean均采用Python實(shí)現(xiàn)，實(shí)驗(yàn)運(yùn)行環(huán)境配置為IntelCoreTMi7-7700HQ CPU @ 2.80 GHz處理器，8 GB內(nèi)存，運(yùn)行Windows 10操作系統(tǒng)。

本文在三個(gè)真實(shí)世界的數(shù)據(jù)集和一個(gè)生成的數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，這些數(shù)據(jù)集大多用于測(cè)試數(shù)據(jù)清理工作。表2中給出了數(shù)據(jù)集、大小、錯(cuò)誤率以及錯(cuò)誤類型。

Flights是一個(gè)真實(shí)世界的數(shù)據(jù)集，該數(shù)據(jù)集包含網(wǎng)絡(luò)上不同數(shù)據(jù)源報(bào)告的航班起飛和到達(dá)時(shí)間的信息。本文使用四個(gè)函數(shù)依賴來確保每個(gè)航班都有唯一的預(yù)計(jì)和實(shí)際的出發(fā)和到達(dá)時(shí)間。

Hospital是一個(gè)真實(shí)世界的數(shù)據(jù)集，該數(shù)據(jù)集是多篇數(shù)據(jù)清理論文中使用的基準(zhǔn)數(shù)據(jù)集，其擁有高達(dá)十五個(gè)函數(shù)依賴并且具有多屬性列決定一個(gè)屬性列，通過Hospital數(shù)據(jù)集來確定BayesOUR具有處理多數(shù)量以及多屬性的函數(shù)依賴的數(shù)據(jù)集性能。

Rayyan是一個(gè)真實(shí)世界的數(shù)據(jù)集，該數(shù)據(jù)是關(guān)于文章的相關(guān)信息，里面數(shù)據(jù)的重復(fù)率極低。

Tax是一個(gè)合成數(shù)據(jù)集，該數(shù)據(jù)集來自于BART存儲(chǔ)庫的綜合數(shù)據(jù)集，獲取其中的一部分用于測(cè)試BayesOUR對(duì)合成數(shù)據(jù)集的清理性能。

分別給這些數(shù)據(jù)集注入5%、10%、15%、20%、25%和30%的替換錯(cuò)誤和拼寫錯(cuò)誤，并且控制拼寫錯(cuò)誤比例為20%、40%、60%、80%、100%，來檢測(cè)BayesOUR對(duì)于兩種不同錯(cuò)誤造成數(shù)據(jù)不一致的修復(fù)性能。

1）對(duì)比方法 本文與先進(jìn)的數(shù)據(jù)修復(fù)方法HoloClean以及通用數(shù)據(jù)清理平臺(tái)NADEEF進(jìn)行數(shù)據(jù)修復(fù)的實(shí)驗(yàn)對(duì)比，并評(píng)估BayesOUR的性能。

HoloClean是最先進(jìn)的基于機(jī)器學(xué)習(xí)的數(shù)據(jù)清理系統(tǒng)，具有完整性約束、外部數(shù)據(jù)和統(tǒng)計(jì)分析。它將現(xiàn)有的依賴于完整性約束或外部數(shù)據(jù)的定性數(shù)據(jù)修復(fù)方法與利用輸入數(shù)據(jù)的統(tǒng)計(jì)屬性的定量數(shù)據(jù)修復(fù)方法統(tǒng)一結(jié)合起來。

NADEEF是一個(gè)規(guī)則違規(guī)檢測(cè)系統(tǒng)，允許用戶指定多種類型的規(guī)則來檢測(cè)數(shù)據(jù)錯(cuò)誤。

2）評(píng)估方法 本實(shí)驗(yàn)采用準(zhǔn)確率、召回率和F1-score來評(píng)估這些方法在錯(cuò)誤檢測(cè)以及修復(fù)的有效性。F1-score被定義為

F1=2×Precision×RecallPrecision+Recall（5）

表3是四個(gè)數(shù)據(jù)集在錯(cuò)誤率為0.2，type錯(cuò)誤比例為0.5情況下，BayesOUR、HoloClean和NADEEF運(yùn)行后的準(zhǔn)確率、召回率和F1-score。從表中可以看出，BayesOUR在不一致數(shù)據(jù)集（替換錯(cuò)誤和拼寫錯(cuò)誤）上面，相比于其他方法擁有更高的準(zhǔn)確率、召回率以及F1-score。

4.2 實(shí)驗(yàn)分析

為了證明BayesOUR對(duì)不一致數(shù)據(jù)具有很好的修復(fù)結(jié)果，本文分別對(duì)Flights、Hospital、Rayyan和Tax數(shù)據(jù)集進(jìn)行不同錯(cuò)誤率以及錯(cuò)誤類型比例的注錯(cuò)，來測(cè)試錯(cuò)誤率以及錯(cuò)誤類型對(duì)BayesOUR性能的影響。通過大量實(shí)驗(yàn)結(jié)果分析表明了BayesOUR對(duì)于不同錯(cuò)誤率和錯(cuò)誤類型的數(shù)據(jù)集都具有良好的修復(fù)結(jié)果，能夠準(zhǔn)確修復(fù)大部分錯(cuò)誤數(shù)據(jù)。

4.2.1 錯(cuò)誤率分析

為了考察錯(cuò)誤率對(duì)BayesOUR的影響，在錯(cuò)誤率為5%～30%的不同數(shù)據(jù)集上運(yùn)行BayesOUR、HoloClean和NADEEF，分別得到準(zhǔn)確率、召回率以及F1-score實(shí)驗(yàn)結(jié)果，如圖5～7所示。

在準(zhǔn)確率方面，隨著錯(cuò)誤率的不斷增加，BayesOUR在四種數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果均優(yōu)于HoloClean和NADEEF，這表明了BayesOUR的基于統(tǒng)計(jì)推理的算法能夠準(zhǔn)確建立數(shù)據(jù)的正確概率并識(shí)別出錯(cuò)誤數(shù)據(jù)。NADEEF在四種數(shù)據(jù)集上的準(zhǔn)確率不高，因?yàn)樗歉鶕?jù)FD規(guī)則去識(shí)別錯(cuò)誤，并沒有結(jié)合概率。HoloClean在Rayyan數(shù)據(jù)集上表現(xiàn)不佳是因?yàn)閿?shù)據(jù)集中數(shù)據(jù)重復(fù)率很低，在注入錯(cuò)誤后仍具有數(shù)據(jù)唯一性，無法利用概率信息檢測(cè)到錯(cuò)誤數(shù)據(jù)，在Tax數(shù)據(jù)集上表現(xiàn)不佳是因?yàn)樵摂?shù)據(jù)集由BART自動(dòng)生成的，生成的數(shù)據(jù)中有很多數(shù)據(jù)符合不一致錯(cuò)誤，使得其無法識(shí)別其中的錯(cuò)誤。

在召回率方面，隨著錯(cuò)誤率的不斷增加，BayesOUR在四種數(shù)據(jù)集上均有良好的數(shù)值，表明了其能夠識(shí)別出數(shù)據(jù)集中大量的錯(cuò)誤數(shù)據(jù)，這得益于其將規(guī)則與概率相結(jié)合以及依據(jù)數(shù)據(jù)在貝葉斯網(wǎng)絡(luò)中的相關(guān)性來建立概率模型進(jìn)行統(tǒng)計(jì)推理。HoloClean表現(xiàn)不佳是因?yàn)槠鋵⒄麄€(gè)數(shù)據(jù)集劃分為噪聲和干凈的部分，使用誤差檢測(cè)方法選取的干凈值來學(xué)習(xí)統(tǒng)計(jì)模型以推斷每個(gè)噪聲值的概率。隨著誤碼率的增加，噪聲部分和干凈部分之間的統(tǒng)計(jì)差異增大，導(dǎo)致其無法識(shí)別大部分錯(cuò)誤。NADEEF僅靠FD規(guī)則來識(shí)別數(shù)據(jù)中的錯(cuò)誤是不行的，尤其是在數(shù)據(jù)錯(cuò)誤較多時(shí)，會(huì)把正確數(shù)據(jù)識(shí)別成錯(cuò)誤數(shù)據(jù)。

在F1-score方面，通過圖中數(shù)據(jù)分析可以知道，BayesOUR的實(shí)驗(yàn)效果均優(yōu)于其他兩種方法，對(duì)于Rayyan這種重復(fù)率極低的數(shù)據(jù)集，BayesOUR只能識(shí)別出少量錯(cuò)誤，其他兩種方法同樣很難識(shí)別出這種數(shù)據(jù)集中的錯(cuò)誤。而在人工合成數(shù)據(jù)集Tax上，BayesOUR雖然表現(xiàn)不如Flights和Hospital數(shù)據(jù)集上的效果好，但是F1-score也高于HoloClean和NADEEF。

4.2.2 錯(cuò)誤類型分析

為了考察不同錯(cuò)誤類型（替換錯(cuò)誤和拼寫錯(cuò)誤）對(duì)BayesOUR性能的影響，在type錯(cuò)誤比例為20%～100%的數(shù)據(jù)集上運(yùn)行BayesOUR、HoloClean和NADEEF，得到準(zhǔn)確率、召回率以及F1-score結(jié)果，如圖8～10所示。

通過分析圖8的實(shí)驗(yàn)信息可以發(fā)現(xiàn)，錯(cuò)誤類型對(duì)BayesOUR的準(zhǔn)確率并無影響，僅存在微乎其微的波動(dòng)，而HoloClean和NADEEF的準(zhǔn)確率卻有較大的影響。造成這種情況的原因是HoloClean和NADEEF對(duì)于替換錯(cuò)誤的識(shí)別能力很弱，當(dāng)替換錯(cuò)誤過多時(shí)，會(huì)造成局部錯(cuò)誤數(shù)據(jù)數(shù)量大于正確數(shù)據(jù)數(shù)量，進(jìn)而使得其將正確數(shù)據(jù)識(shí)別為錯(cuò)誤數(shù)據(jù)。

通過分析圖9的實(shí)驗(yàn)信息可以發(fā)現(xiàn)，BayesOUR在高度的準(zhǔn)確率情況下能夠識(shí)別出數(shù)據(jù)集中大部分錯(cuò)誤，而HoloClean和NADEEF僅能夠識(shí)別出數(shù)據(jù)集中的個(gè)別錯(cuò)誤或者錯(cuò)誤識(shí)別正確數(shù)據(jù)，同樣證明了不同的錯(cuò)誤類型對(duì)其有一定的影響。

通過分析圖10的實(shí)驗(yàn)信息可以發(fā)現(xiàn)，不同錯(cuò)誤類型的數(shù)據(jù)集下，BayesOUR都具有比HoloClean和NADEEF更高的F1-score，充分體現(xiàn)了數(shù)據(jù)中的不同錯(cuò)誤類型并不會(huì)影響B(tài)ayesOUR的數(shù)據(jù)清洗性能。

5 結(jié)束語

本文研究了不一致數(shù)據(jù)修復(fù)問題，提出了基于統(tǒng)計(jì)推理的不一致數(shù)據(jù)清洗方法。該方法通過FD導(dǎo)出矩陣進(jìn)行數(shù)據(jù)錯(cuò)誤檢測(cè)，并利用貝葉斯網(wǎng)絡(luò)進(jìn)行概率推理建立概率模型，計(jì)算元組的正確性概率。最后，通過對(duì)錯(cuò)誤元組數(shù)據(jù)建立屬性字典以及計(jì)算所有一致性修復(fù)方案的概率確定最終的修復(fù)方案。通過真實(shí)數(shù)據(jù)以及生成數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果驗(yàn)證了提出方法的準(zhǔn)確性優(yōu)于現(xiàn)有的修復(fù)方法。然而，在重復(fù)率較低的數(shù)據(jù)上，修復(fù)性能可能會(huì)受到影響。未來的研究將致力于解決這些挑戰(zhàn)。

參考文獻(xiàn)：

［1］徐耀麗，李戰(zhàn)懷，陳群，等.基于可能世界模型的關(guān)系數(shù)據(jù)不一致性的修復(fù)［J］.軟件學(xué)報(bào)，2016，27（7）：1685-1699. （Xu Yaoli，Li Zhanhuai，Chen Qun，et al.Repairing inconsistent relational data based on possible world model［J］.Journal of Software，2016，27（7）：1685-1699.）

［2］Bertossi L，Kolahi S，Lakshmanan L V S.Data cleaning and query answering with matching dependencies and matching functions［C］//Proc of the 14th International Conference on Database Theory.New York：ACM Press，2011：268-279.

［3］Chu Xu，Ilyas I F，Papotti P.Holistic data cleaning：putting violations into context［C］//Proc of the 29th IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2013：458-469.

［4］張安珍，司佳宇，梁天宇，等.規(guī)則與概率相結(jié)合的不一致數(shù)據(jù)子集修復(fù)方法［J］.軟件學(xué)報(bào)，2024，35（9）：4448-4468. （Zhang Anzhen，Si Jiayu，Liang Tianyu，et al.Subset repair method combining rules and probabilities for inconsistent data［J］.Journal of Software，2024，35（9）：4448-4468.

［5］Livshits E，Kimelfeld B，Roy S.Computing optimal repairs for functional dependencies［J］.ACM Trans on Database Systems，2020，45（1）：1-46.

［6］Sun Yu，Song Shaoxu.From minimum change to maximum density：on S-Repair under integrity constraints［C］//Proc of the 37th IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2021：1943-1948.

［7］Chomicki J，Marcinkowski J.Minimal-change integrity maintenance using tuple deletions［J］.Information and Computation，2005，197（1-2）：90-121.

［8］Afrati F N，Kolaitis P G.Repair checking in inconsistent databases：algorithms and complexity［C］//Proc of the 12th International Confe-rence on Database Theory.New York：ACM Press，2009：31-41.

［9］Arenas M，Bertossi L，Chomicki J，et al.Scalar aggregation in inconsistent databases［J］.Theoretical Computer Science，2003，296（3）：405-434.

［10］Lopatenko A，Bravo L.Efficient approximation algorithms for repairing inconsistent databases［C］//Proc of the 23rd IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2007：216-225.

［11］Kolahi S，Lakshmanan L V S.On approximating optimum repairs for functional dependency violations［C］//Proc of the 12th International Conference on Database Theory.New York：ACM Press，2009：53-62.

［12］Bohannon P，F(xiàn)an Wenfei，F(xiàn)laster M，et al.A cost-based model and effective heuristic for repairing constraints by value modification［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2005：143-154.

［13］Dallachiesa M，Ebaid A，Eldawy A，et al.NADEEF：a commodity data cleaning system［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2013：541-552.

［14］Khayyat Z，Ilyas I F，Jindal A，et al.BigDansing：a system for big data cleansing［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2015：1215-1230.

［15］Abedjan Z，Akcora C G，Ouzzani M，et al.Temporal rules discovery for Web data cleaning［J］.Proceedings of the VLDB Endowment，2015，9（4）：336-347.

［16］Geerts F，Mecca G，Papotti P，et al.The LLUNATIC data-cleaning framework［J］.Proceedings of the VLDB Endowment，2013，6（9）：625-636.

［17］Berti-équille L，Dasu T，Srivastava D.Discovery of complex glitch patterns：a novel approach to quantitative data cleaning［C］//Proc of the 27th IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2011：733-744.

［18］Dasu T，Loh J M.Statistical distortion：consequences of data cleaning［J］.Proceedings of the VLDB Endowment，2012，5（11）：1674-1683.

［19］Yakout M，Berti-Equille L，Elmagarmid A K.Don’t be SCAREd：use SCalable automatic REpairing with maximal likelihood and bounded changes［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2013：553-564.

［20］Krishnan S，Wang Jiannan，Wu E，et al.Active-Clean：interactive data cleaning for statistical modeling［J］.Proceedings of the VLDB Endowment，2016，9（12）：948-959.

［21］Mayfield C，Neville J，Prabhakar S.ERACER：a database approach for statistical inference and data cleaning［C］//Proc of ACM SIGMOD International Conference on Management of data.New York：ACM Press，2010：75-86.

［22］Prokoshyna N，Szlichta J，Chiang F，et al.Combining quantitative and logical data cleaning［J］.Proceedings of the VLDB Endowment，2015，9（4）：300-311.

［23］Ge Congcong，Gao Yunjun，Miao Xiaoye，et al.A hybrid data cleaning framework using Markov logic networks［J］.IEEE Trans on Know-ledge and Data Engineering，2022，34（5）：2048-2062.

［24］Ge Congcong，Gao Yunjun，Miao Xiaoye，et al.IHCS：an integrated hybrid cleaning system［J］.Proceedings of the VLDB Endowment，2019，12（12）：1874-1877.

［25］Rekatsinas T，Chu Xu，Ilyas I F，et al.HoloClean：holistic data repairs with probabilistic inference［EB/OL］.（2017-02-02）.https：//arxiv.org/abs/1702.00820.

［26］Yu Zhuoran，Chu Xu.PIClean：a probabilistic and interactive data cleaning system［C］//Proc of International Conference on Management of Data.New York：ACM Press，2019：2021-2024.

［27］Mahdavi M，Abedjan Z，F(xiàn)ernandez R C，et al.Raha：a configuration-free error detection system［C］//Proc of International Conference on Management of Data.New York：ACM Press，2019：865-882.