盧 菁,黨延領(lǐng),劉 叢

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

1 引 言

隨著數(shù)據(jù)的爆炸性增長(zhǎng),劣質(zhì)數(shù)據(jù)隨之而來(lái),極大降低了數(shù)據(jù)的可用性.國(guó)際著名科技咨詢機(jī)構(gòu)Gartner的調(diào)查顯示,全球財(cái)富1000強(qiáng)企業(yè)中超過25%的企業(yè)信息數(shù)據(jù)存在不一致性問題[1].如何提升數(shù)據(jù)質(zhì)量成為當(dāng)前研究的熱點(diǎn),各種數(shù)據(jù)清洗模型應(yīng)運(yùn)而生.其中包括:

1)最優(yōu)化修復(fù)模型.文獻(xiàn)[2]查找一個(gè)既滿足預(yù)定義函數(shù)依賴,又滿足修復(fù)代價(jià)最小的方案來(lái)修復(fù)數(shù)據(jù).文獻(xiàn)[3]使用統(tǒng)計(jì)方法抽取一個(gè)樣本,域?qū)＜覍?duì)此樣本進(jìn)行檢查和編輯,并重復(fù)調(diào)用自動(dòng)修復(fù)或增量修復(fù)方法,直到所得修復(fù)結(jié)果的精確度符合預(yù)定界限.文獻(xiàn)[2,3]基于一種或多種目標(biāo)約束條件,不增加或刪除任何記錄,通過修改某些字段,使數(shù)據(jù)集符合預(yù)設(shè)的一致性要求,產(chǎn)生單一的最優(yōu)化修復(fù)方案,然而不一致數(shù)據(jù)的可能修復(fù)方案往往不唯一,只根據(jù)修復(fù)代價(jià)最小來(lái)判斷會(huì)忽略具有相似、甚至是相同修復(fù)代價(jià)的其它修復(fù)方案.

2)抽樣修復(fù)模型.文獻(xiàn)[4,5]基于等價(jià)類的思想,不局限于單一的最優(yōu)修復(fù)方案,使用抽樣方法從所有可能的修復(fù)空間中隨機(jī)產(chǎn)生一種修復(fù),解決修復(fù)單一化問題,但因樣本集的隨機(jī)性導(dǎo)致了修復(fù)方案的不確定性.

3)按序修復(fù)模型.文獻(xiàn)[6]考慮修復(fù)代價(jià)和時(shí)序關(guān)系,使用關(guān)聯(lián)規(guī)則為定位錯(cuò)誤數(shù)據(jù)提供參考,提高了修復(fù)錯(cuò)誤數(shù)據(jù)的精度.文獻(xiàn)[7]從修復(fù)代價(jià)和屬性值相關(guān)性兩個(gè)方面量化各候選修復(fù)方案的可信程度,并最終找出最佳的修復(fù)方案.文獻(xiàn)[6,7]有效的解決了修復(fù)方案隨機(jī)性問題,但都是通過放寬某些約束條件來(lái)計(jì)算屬性值的優(yōu)先級(jí),不可避免地影響了修復(fù)結(jié)果的準(zhǔn)確度.

4)融合函數(shù)依賴、條件函數(shù)依賴和否定約束的整體修復(fù)模型.文獻(xiàn)[8,9]將不同類型的約束規(guī)則融入沖突數(shù)據(jù)集中,綜合考慮各類約束規(guī)則之間的交互性,采用整體修復(fù)的思想對(duì)數(shù)據(jù)進(jìn)行清洗.該方法既解決了文獻(xiàn)[2-7]所考慮的約束規(guī)則不能包含大于或小于的語(yǔ)義約束問題,又解決了單純將各類約束規(guī)則以線性方式或交錯(cuò)方式作用于數(shù)據(jù)集的問題,但其忽視了約束規(guī)則之間可能存在的沖突及對(duì)數(shù)據(jù)集的符合程度.

目前,數(shù)據(jù)不一致性修復(fù)研究中,僅有少量文獻(xiàn)考慮約束規(guī)則的檢測(cè).文獻(xiàn)[10]基于統(tǒng)計(jì)的置信度方法,假定數(shù)據(jù)中僅存在很小一部分錯(cuò)誤,則違反函數(shù)依賴的數(shù)據(jù)越少,其成立的可能性越大.該方法沒有考慮數(shù)據(jù)語(yǔ)義,檢測(cè)結(jié)果通常含有大量無(wú)效的函數(shù)依賴.文獻(xiàn)[11]基于數(shù)據(jù)語(yǔ)義置信度的方法,使用條件概率求出給定函數(shù)依賴的置信度.該方法只考慮錯(cuò)誤元組對(duì)函數(shù)依賴置信度的影響,根據(jù)置信度的大小來(lái)判斷函數(shù)依賴對(duì)數(shù)據(jù)集的符合程度,并未涉及函數(shù)依賴之間的沖突檢測(cè).文獻(xiàn)[12]通過擴(kuò)展阿姆斯壯定理,開發(fā)規(guī)則推理系統(tǒng)來(lái)分析條件函數(shù)依賴之間存在的沖突及其對(duì)數(shù)據(jù)集的符合程度.該方法認(rèn)為,如果元組與條件函數(shù)依賴中的常量相匹配,則支持該條件函數(shù)依賴,但否定約束中可能不含常量,所以該方法不適合否定約束之間的沖突檢測(cè).

綜上,我們提出了基于校準(zhǔn)否定約束集的數(shù)據(jù)修復(fù)方法,DR-RDC(Data Repair Approach based on Revised Denial Constraint Sets),主要貢獻(xiàn)包括:

1)我們利用否定約束發(fā)現(xiàn)算法挖掘出所有約束規(guī)則,提出符合度記分函數(shù)的概念,計(jì)算出每個(gè)否定約束對(duì)數(shù)據(jù)集的符合程度,剔除符合度小于閾值λ的否定約束.

2)我們提出關(guān)聯(lián)矩陣,用來(lái)檢測(cè)否定約束之間存在的沖突及類型,并進(jìn)行沖突消除,得到校準(zhǔn)否定約束集.

3)我們將校準(zhǔn)否定約束集作用于原始數(shù)據(jù)集,得出證據(jù)規(guī)則集及對(duì)應(yīng)的沖突元組集.

4)我們提出DR-RDC方法,以修改最少元組為目標(biāo),根據(jù)每個(gè)證據(jù)規(guī)則的符合度分?jǐn)?shù),從高到低地選取證據(jù)規(guī)則修復(fù)檢測(cè)出的沖突元組集,始終選取條件概率最大的屬性值作為沖突屬性的修復(fù)值,直到?jīng)_突元組集不違反任一否定約束.

5)實(shí)驗(yàn)表明DR-RDC方法在精確度上優(yōu)于數(shù)據(jù)語(yǔ)義置信度方法;對(duì)比分析校準(zhǔn)否定約束集與原始否定約束集的數(shù)據(jù)修復(fù)效果,發(fā)現(xiàn)DR-RDC方法在數(shù)據(jù)錯(cuò)誤檢測(cè)率和修復(fù)率方面具有顯著的提升.

2 DR-RDC處理流程

DR-RDC處理流程如圖1,輸入是原始關(guān)系數(shù)據(jù)集,輸出是干凈數(shù)據(jù)集,具體操作步驟如下:

1)利用文獻(xiàn)[13]的方法挖掘出所有否定約束.

2)使用符合度記分函數(shù)計(jì)算出否定約束對(duì)數(shù)據(jù)集的符合程度,剔除小于符合度閾值λ的否定約束,得到高符合度否定約束集.

3)將高符合度否定約束集轉(zhuǎn)化為描述其所包含謂詞表達(dá)式的關(guān)聯(lián)矩陣.

4)根據(jù)關(guān)聯(lián)矩陣檢測(cè)否定約束之間存在的沖突及類型,進(jìn)行沖突消除,得到校準(zhǔn)否定約束集.

5)使用校準(zhǔn)否定約束集對(duì)待測(cè)數(shù)據(jù)集進(jìn)行檢測(cè),得出證據(jù)規(guī)則集及其對(duì)應(yīng)的沖突元組集.

圖1 DR-RDC處理流程Fig.1 Processing flow of DR-RDC

6)根據(jù)證據(jù)規(guī)則集中否定約束的符合度分?jǐn)?shù),從高到低修復(fù)檢測(cè)出的沖突元組集,選取條件概率最大的屬性值作為沖突屬性的修復(fù)值,直到每個(gè)否定約束都沒有對(duì)應(yīng)的沖突元組集,進(jìn)而得到干凈數(shù)據(jù)集.

3 否定約束集校準(zhǔn)

3.1 否定約束定義

利用約束規(guī)則進(jìn)行數(shù)據(jù)修復(fù)是常用方法,文獻(xiàn)[14]對(duì)函數(shù)依賴和屬性蘊(yùn)含的關(guān)系進(jìn)行了統(tǒng)一建模,旨在分析兩者的共性和差異性,并未涉及具體的應(yīng)用.本文擴(kuò)展了約束規(guī)則的范圍,使用一階邏輯表達(dá)式,將約束規(guī)則與屬性蘊(yùn)含的關(guān)系統(tǒng)一為否定約束,并在此基礎(chǔ)上對(duì)數(shù)據(jù)進(jìn)行檢測(cè)和修復(fù).否定約束的定義如下.

定義1.否定約束是一種能夠表達(dá)數(shù)據(jù)之間各種約束規(guī)則的實(shí)體約束語(yǔ)言,其一階邏輯表達(dá)式如下:

φ:?Tα,Tβ,Tγ,…∈R,(p1∧p2∧…∧pm)

其中,R是關(guān)系模式,Tx是任一元組,x∈{α,β,γ,…},pi是否定約束所包含的謂詞表達(dá)式,其形式是ν1φν2或者ν1φc,ν1,ν2∈Tx.A,A是任一屬性,φ是謂詞表達(dá)式所包含的關(guān)系運(yùn)算符,包括{=,≠,>,<},c是常量.

3.2 符合度計(jì)算

如果一對(duì)元組不符合給定的否定約束φ,稱該元組對(duì)為沖突元組對(duì),反之為無(wú)沖突元組對(duì).否定約束對(duì)數(shù)據(jù)集的符合程度,既與沖突元組集對(duì)其的負(fù)支持度有關(guān),又與無(wú)沖突元組集對(duì)其的正支持度有關(guān).接下來(lái)將分別引入負(fù)支持度和正支持度這兩個(gè)質(zhì)量維度的概念.

3.2.1 負(fù)支持度

設(shè)一個(gè)否定約束φ包含的謂詞表達(dá)式個(gè)數(shù)為|φ.predicates|,根據(jù)φ所表達(dá)的約束語(yǔ)義,如果一對(duì)元組滿足的謂詞表達(dá)式個(gè)數(shù)為|φ.predicates|,則該對(duì)元組存在沖突.沖突元組集對(duì)否定約束的支持度既與φ所包含的謂詞表達(dá)式個(gè)數(shù)有關(guān),又與違反φ的沖突元組對(duì)的數(shù)量有關(guān).|φ.predicates|越大,則表明φ中假設(shè)的謂詞表達(dá)式越多,從而導(dǎo)致否定約束的各謂詞表達(dá)式之間可能存在冗余問題.另外,待測(cè)數(shù)據(jù)集的正確元組數(shù)往往遠(yuǎn)大于錯(cuò)誤元組數(shù),如果違反φ的元組對(duì)數(shù)較多,則表明φ對(duì)數(shù)據(jù)集的符合度程度較小.將否定約束形成的字母表標(biāo)識(shí)為L(zhǎng)={Tα,Tβ,A,OP,C},其中Tα,Tβ為一對(duì)元組,A是所有屬性的集合,OP是算術(shù)運(yùn)算符和邏輯運(yùn)算符的集合,C是常量,Len(φ)為L(zhǎng)中出現(xiàn)在φ中的不同元素個(gè)數(shù),如(Tα.SL<5000)包含、Tα、SL、<和5000這五種不同元素,故其Len(φ)=5.因違反同一否定約束φ的沖突元組對(duì)可能有多個(gè),所以將沖突元組集對(duì)給定否定約束的違反度定義為:

(1)

其中,kcp是違反φ的元組對(duì)數(shù),|V|表示違反φ的沖突元組數(shù),可得沖突元組集對(duì)φ的負(fù)支持度表達(dá)式為:

NS(φ)=1-Denial(φ)

(2)

例1.以表1中的稅務(wù)記錄為例,每條記錄描述具有7個(gè)屬性的個(gè)人地址和稅務(wù)信息:姓名(NE),區(qū)號(hào)(AC),城市(CT),區(qū)(DT),郵編(ZIP),工資(SL),稅率(TR).

表1 稅務(wù)數(shù)據(jù)記錄
Table 1 Tax data record

TIDNEACCTDTZIPSLTRT1劉德010北京朝陽(yáng)區(qū)10000050003T2陳超021上海黃浦區(qū)200001600004.6T3盎司010北京東城區(qū)10000050003T4陳敏022天津和平區(qū)300000850007.2T5趙軍023重慶萬(wàn)州區(qū)404100150002.4T6李偉021上海閔行區(qū)201100600004.5T7王寶024沈陽(yáng)和平區(qū)110001700007T8張麗010南京崇文區(qū)100000100004T9孫強(qiáng)010北京豐臺(tái)區(qū)10000050003T10李帥020廣州黃埔區(qū)510700400006

假設(shè)存在以下否定約束:

c1:(Tα.ZIP=Tβ.ZIP∧Tα.CT≠Tβ.CT)

c2:(Tα.AC=Tβ.AC∧Tα.CT≠Tβ.CT)

c3:(Tα.CT=Tβ.CT∧Tα.SLTβ.TR)

c4:(Tα.CT=Tβ.CT∧Tα.SL=Tβ.SL∧Tα.TR≠Tβ.TR)

c5:(Tα.ZIP=Tβ.ZIP∧Tα.SLTβ.TR)

c6:(Tα.CT=Tβ.CT∧Tα.SL>Tβ.SL∧Tα.TR

考慮例1中的數(shù)據(jù)集及給定的否定約束c1和c4,其中,|c1.predicates|=2,Len(c1)=8,違反c1的元組對(duì)為〈T1,T8〉,〈T3,T8〉和〈T8,T9〉,所涉及的沖突元組為T1,T3,T8和T9,即kcp=3,|V|=4,可得NS(c1)=0.8125.|c4.predicates|=3,Len(c4)=9,違反c4的元組對(duì)為〈T2,T6〉,即kcp=1,|V|=2,可得NS(c4)=0.8333.

如果僅考慮負(fù)支持度,由計(jì)算結(jié)果可知c4對(duì)數(shù)據(jù)集的符合程度優(yōu)于c1,但通常情況下,無(wú)沖突元組對(duì)的數(shù)量要遠(yuǎn)大于沖突元組對(duì)的數(shù)量,所以必須考慮無(wú)沖突元組集對(duì)給定否定約束的正支持度.接下來(lái)引入正支持度的概念.

3.2.2 正支持度

一個(gè)否定約束φ能夠成立的證據(jù)是存在不違反φ的元組對(duì),即無(wú)沖突元組對(duì).滿足φ的無(wú)沖突元組對(duì)往往不唯一,但匹配φ中的謂詞表達(dá)式個(gè)數(shù)可能不同,因此我們將滿足k個(gè)謂詞表達(dá)式的元組對(duì)稱為k-Evidence,簡(jiǎn)寫為kE.kE中滿足的謂詞表達(dá)式數(shù)越多,它對(duì)φ的支持度就越大.為了反映這一特性,我們?yōu)閗E引入一個(gè)權(quán)重w(k),其值從0到1變化,并且隨k的增大而增大,表達(dá)式如下:

(3)

基于這樣的證據(jù),將無(wú)沖突元組集對(duì)φ的正支持度表達(dá)式PS(φ)定義為:

(4)

其中,|kE|是各類證據(jù)所對(duì)應(yīng)的無(wú)沖突元組對(duì)個(gè)數(shù),k=0,1,…,|φ.predicates|-1.

如果僅考慮正支持度,由計(jì)算結(jié)果可知c1對(duì)數(shù)據(jù)集符合程度優(yōu)于c4,這與僅考慮負(fù)支持度的計(jì)算結(jié)果相反,所以必須綜合考慮正、負(fù)支持度這兩個(gè)質(zhì)量維度,為此我們接下來(lái)引入符合度記分函數(shù)的概念.

3.2.3 符合度記分函數(shù)

否定約束對(duì)數(shù)據(jù)集的符合程度既與負(fù)支持度有關(guān),又與正支持度有關(guān),僅考慮一種支持度具有片面性.為了準(zhǔn)確計(jì)算出否定約束對(duì)數(shù)據(jù)集的符合程度,我們引入記分函數(shù)來(lái)計(jì)算每個(gè)否定約束的符合度分?jǐn)?shù).對(duì)于給定的φ,將符合度記分函數(shù)定義為兩個(gè)質(zhì)量維度的線性加權(quán)組合.

Conf(φ)=α*PS(φ)+(1-α)*NS(φ)

(5)

其中,Conf(φ)在0到1之間取值,值越大,表明φ對(duì)數(shù)據(jù)集的符合程度越好.α是兩個(gè)質(zhì)量維度的平衡因子,其值在0到1之間,表示無(wú)沖突元組對(duì)在給定數(shù)據(jù)集的所有元組對(duì)中所占的比例,即正支持度的比例因子,則1-α就為負(fù)支持度的比例因子,α的表達(dá)式定義如下:

(6)

通過引入平衡因子α可以消除僅考慮一種支持度的片面性,使符合度的計(jì)算結(jié)果更準(zhǔn)確.

3.3 校準(zhǔn)步驟1:符合度校準(zhǔn)

為提高否定約束對(duì)數(shù)據(jù)集的符合程度,我們使用Conf(φ)計(jì)算每個(gè)否定約束的符合度分?jǐn)?shù),并與符合度閾值λ進(jìn)行比較,剔除小于λ的否定約束,從而得到滿足符合度閾值的否定約束集Σλ.算法1是否定約束符合度校準(zhǔn)算法.

算法1.否定約束符合度校準(zhǔn)算法.

輸入:數(shù)據(jù)實(shí)例I,待測(cè)否定約束集Σ,符合度閾值λ

輸出:滿足符合度閾值的否定約束集Σλ

1.Σλ的初值是待測(cè)否定約束集Σ;

2.for eachφin Σ

3.for each 〈Tα,Tβ〉 inI

4. while(k≤|φ.predicates|)

5. if(k=|φ.predicates|)

6.φ的沖突元組對(duì)數(shù)加1;

7. 統(tǒng)計(jì)φ對(duì)應(yīng)的各類證據(jù)個(gè)數(shù),并計(jì)算出證據(jù)總數(shù);

8. 由公式(3)計(jì)算各類證據(jù)對(duì)應(yīng)的權(quán)重;

9.k++;

10.由公式(1)、(2)求出φ的負(fù)支持度分?jǐn)?shù)NS(φ);

11.由公式(4)求出φ的正支持度分?jǐn)?shù)PS(φ);

12.由公式(6)求出平衡因子α的值;

13.由公式(5)求出φ的符合度分?jǐn)?shù)Conf(φ);

14.if(Conf(φ)<λ)

15. Σλ=Σλ-φ;

16.return Σλ;

其中k表示元組對(duì)〈Tα,Tβ〉滿足φ所包含的謂詞表達(dá)式個(gè)數(shù),初值為0.通過算法1我們得到了滿足符合度閾值的否定約束集.

3.4 校準(zhǔn)步驟2:沖突消除

定義2.對(duì)稱沖突是指作用于同一組屬性上的兩個(gè)否定約束,其所包含的謂詞表達(dá)式相同或相反.

定義3.冗余沖突是指給定兩個(gè)或多個(gè)否定約束,其中某個(gè)否定約束可由其它否定約束推導(dǎo)得出.

本文考慮的謂詞表達(dá)式包含{=,≠,>,<}這四種運(yùn)算符,每個(gè)否定約束包含不同的謂詞表達(dá)式.為了便于分析否定約束之間存在的沖突,我們用{1,-1,2,-2}這四個(gè)關(guān)聯(lián)因子分別對(duì)應(yīng)四種運(yùn)算符所構(gòu)成的謂詞表達(dá)式,則否定約束所包含的謂詞表達(dá)式可以通過一個(gè)關(guān)聯(lián)矩陣來(lái)表示.我們用行標(biāo)代表各否定約束,列標(biāo)代表各元組屬性,0代表否定約束與屬性之間沒有約束關(guān)系.算法2為關(guān)聯(lián)矩陣構(gòu)建算法.

算法2.關(guān)聯(lián)矩陣構(gòu)建算法.

輸入:滿足符合度閾值的否定約束集Σλ,元組屬性集ΣA

輸出:關(guān)聯(lián)矩陣Matrix(Σλ,ΣA)

1.for eachφin Σλ

2.for eachAin ΣA

3. if(Ainφ)

4. if(Tα.A=Tβ.Ainφ)

5.Matrix(Σλ,ΣA)中屬性A所對(duì)應(yīng)的位置為1;

6. else if(Tα.A≠Tβ.Ainφ)

7.Matrix(Σλ,ΣA)中屬性A所對(duì)應(yīng)的位置為-1;

8. else if(Tα.A>Tβ.Ainφ)

9.Matrix(Σλ,ΣA)中屬性A所對(duì)應(yīng)的位置為2;

10. else if(Tα.A

11.Matrix(Σλ,ΣA)中屬性A所對(duì)應(yīng)的位置為-2;

12. else

13.Matrix(Σλ,ΣA)中屬性A所對(duì)應(yīng)的位置為0;

14.returnMatrix(Σλ,ΣA);

其中Tα,Tβ是否定約束中謂詞表達(dá)式所包含的元組,A是任一屬性.考慮例1中給出的否定約束,其對(duì)應(yīng)的關(guān)聯(lián)矩陣如下:

對(duì)例1中的否定約束進(jìn)行分析可得,c3和c6只有一個(gè)謂詞表達(dá)式相同,其余均相反,兩約束之間存在對(duì)稱沖突;c5表達(dá)的語(yǔ)義與c1和c3共同表達(dá)的語(yǔ)義相同,三個(gè)約束之間出現(xiàn)了冗余沖突.作用于同一數(shù)據(jù)集的否定約束數(shù)量往往比較大,少則幾十個(gè),多則幾百個(gè).不論出現(xiàn)以上哪種情況,都會(huì)影響數(shù)據(jù)清洗質(zhì)量,因此,必須采用有效的機(jī)制,在對(duì)數(shù)據(jù)進(jìn)行清洗之前,先消除否定約束之間可能存在的沖突,以提高否定約束的精確度.

基于符合度記分函數(shù)和關(guān)聯(lián)矩陣的分析,我們?cè)O(shè)計(jì)出算法3對(duì)否定約束集進(jìn)行校準(zhǔn).

算法3.否定約束集校準(zhǔn)算法.

輸入:關(guān)聯(lián)矩陣Matrix(Σλ,ΣA)

輸出:校準(zhǔn)否定約束集Σ′

1.Σ′的初值為滿足符合度閾值的否定約束集Σλ;

2.for eachφi,φjinMatrix(Σλ,ΣA)

3. if (φi,φjsatisfy 對(duì)稱沖突)

4. 刪除φi,φj中符合度分?jǐn)?shù)較低的那一個(gè);

5. if (φi?φj)

6. 刪除φj;

7.for eachφi,φj,φkinMatrix(Σλ,ΣA)

8. if (φi+φj?φk)

9. 刪除φk;

10.return Σ′;

通過算法3我們得到了校準(zhǔn)否定約束集,下面可以利用它進(jìn)行數(shù)據(jù)檢測(cè)與修復(fù).

4 數(shù)據(jù)檢測(cè)與修復(fù)

4.1 數(shù)據(jù)檢測(cè)

證據(jù)規(guī)則是指在數(shù)據(jù)檢測(cè)過程中發(fā)現(xiàn)沖突元組對(duì)的否定約束.數(shù)據(jù)檢測(cè)階段是針對(duì)算法3返回的校準(zhǔn)否定約束集,檢測(cè)出其中的證據(jù)規(guī)則集Σe及對(duì)應(yīng)的沖突元組集Tc.算法4是數(shù)據(jù)檢測(cè)算法.

算法4.數(shù)據(jù)檢測(cè)算法.

輸入:數(shù)據(jù)實(shí)例I,校準(zhǔn)否定約束集Σ′

輸出:證據(jù)規(guī)則集Σe,沖突元組集Tc

1.Σe,Tc的初值均為空;

2.for eachφin Σ′

3.for each 〈Tα,Tβ〉 inI

4. if (〈Tα,Tβ〉 satisfyφ.predicates)

5.φ添加到Σe中;

6. 〈Tα,Tβ〉添加到φ對(duì)應(yīng)的沖突元組集Tc中;

7. 記錄φ沖突元組對(duì)數(shù)的指針加1;

8.return Σe,Tc;

其中,φ.predicates表示φ中的謂詞表達(dá)式集.通過算法4我們得到了證據(jù)規(guī)則集及對(duì)應(yīng)的沖突元組集,接下來(lái)對(duì)原始數(shù)據(jù)集進(jìn)行修復(fù).

4.2 數(shù)據(jù)修復(fù)

定義4.條件概率是指在同一個(gè)樣本空間Ω中的事件或者子集A與B,如果隨機(jī)從Ω中選出的一個(gè)元素屬于A,那么下一個(gè)隨機(jī)選擇的元素屬于B的概率.其表達(dá)式如下:

(7)

數(shù)據(jù)修復(fù)階段是針對(duì)算法4返回的證據(jù)規(guī)則集Σe,修復(fù)其對(duì)應(yīng)的沖突元組集Tc,但不同的證據(jù)規(guī)則選取順序可能產(chǎn)生不同的修復(fù)結(jié)果.因此,我們根據(jù)每個(gè)證據(jù)規(guī)則的符合度分?jǐn)?shù),從高到低修復(fù)檢測(cè)出的沖突元組集,直到每個(gè)否定約束都沒有對(duì)應(yīng)的沖突元組集.每個(gè)沖突屬性的候選取值可能有多個(gè),我們總是選取使條件概率達(dá)到最大值的屬性值作為沖突屬性的修復(fù)值.算法5是沖突元組修復(fù)算法.

算法5.沖突元組修復(fù)算法.

輸入:數(shù)據(jù)實(shí)例I,證據(jù)規(guī)則集Σe,沖突元組集Tc

輸出:修復(fù)結(jié)果I′

1.repeat

2.for eachφin Σe

3. 根據(jù)Conf(φ),從高到低選取φ及對(duì)應(yīng)的Tc;

4. for each conflictAinTc

5. 統(tǒng)計(jì)A取每一個(gè)可能值的個(gè)數(shù)及所有可能值的總數(shù);

6. 由公式(7)求出A取每一個(gè)可能值的條件概率P;

7. 選取P最大的屬性值作為A的修復(fù)值;

8.until(Σe=φ);

5 實(shí)驗(yàn)及結(jié)果

5.1 實(shí)驗(yàn)配置與數(shù)據(jù)集

實(shí)驗(yàn)運(yùn)行在使用Intel酷睿i5-2.5GHz的CPU,4GB內(nèi)存,64位Windows 10操作系統(tǒng)的計(jì)算機(jī)上.本文使用文獻(xiàn)[15]中的稅務(wù)數(shù)據(jù)Tax作為模擬數(shù)據(jù)集,每條記錄描述具有15個(gè)屬性的個(gè)人地址和稅務(wù)信息,使用從Web數(shù)據(jù)源[注]http://data.medicare.gov/data/hospital-compare獲取的由美國(guó)政府統(tǒng)計(jì)的,包含160k條記錄的Hospital數(shù)據(jù)作為真實(shí)數(shù)據(jù)集.

實(shí)驗(yàn)假定所選取的數(shù)據(jù)集都是正確的,通過某種錯(cuò)誤率e人為地引入噪聲數(shù)據(jù).

5.2 實(shí)驗(yàn)結(jié)果及分析

5.2.1 符合度閾值λ的確定

λ的選取對(duì)否定約束的檢測(cè)精確度具有較大影響.取值太小,滿足條件的否定約束就比較多,從而可能引入無(wú)效的否定約束,取值太大,滿足條件的否定約束又比較少,從而可能丟失符合條件的否定約束.λ的取值與α緊密相關(guān),由公式(5)和公式(6)可知0.5≤λ≤1.實(shí)驗(yàn)使用平均精確度這一指標(biāo)來(lái)確定λ的取值,將平均精確度定義為滿足λ的否定約束中真實(shí)成立的否定約束所占的比例.

圖2顯示了λ取不同值時(shí)否定約束檢測(cè)的平均精確度,從圖中可以看出:

1)平均精確度隨著λ的增大而增大,且增幅波動(dòng)較小.這是因?yàn)棣巳≈翟酱?返回的否定約束就越少,而真實(shí)成立的否定約束相對(duì)增多,所以平均精確度隨著λ的增大而增大.

2)當(dāng)λ=0.9時(shí),平均精確度達(dá)到最優(yōu),但這只是局部最優(yōu),并不能將λ的值設(shè)定為0.9.因?yàn)棣酥翟叫?候選的否定約束數(shù)量就越多,可能沖突的否定約束數(shù)量也隨之增多,致使所求比例的分子相對(duì)減小,所以平均精確度隨λ的減小而降低.但只要平均精確度大于0,就說明可能存在真實(shí)成立的否定約束,而否定約束精確度檢測(cè)實(shí)驗(yàn)中要引入噪聲數(shù)據(jù),可能會(huì)降低部分否定約束的符合度分?jǐn)?shù),為避免丟失符合條件的否定約束,本文選取λ=0.5.

圖2 否定約束平均精確度Fig.2 Average accuracy of the denial constraints

5.2.2 約束規(guī)則檢測(cè)精確度評(píng)估

實(shí)驗(yàn)使用精確度這一指標(biāo)來(lái)評(píng)估DR-RDC對(duì)約束規(guī)則的檢測(cè)效果.同時(shí),為了在相同條件下比較DR-RDC與最新研究文獻(xiàn)[11]采用的數(shù)據(jù)語(yǔ)義置信度(Data Semantic Confidence,簡(jiǎn)稱DSC)方法,我們使用文獻(xiàn)[16]中提出的函數(shù)依賴挖掘算法得到待測(cè)函數(shù)依賴集,這保證了DR-RDC和DSC方法針對(duì)同一約束規(guī)則集進(jìn)行檢測(cè).基于top-k算法的思想,將精確度定義為返回的前k(實(shí)驗(yàn)中按照百分比計(jì)算)個(gè)候選中真實(shí)成立的函數(shù)依賴所占的比例.圖3是DR-RDC與DSC的實(shí)驗(yàn)效果對(duì)比分析圖.

圖3 DR-RDC與DSC精確度對(duì)比分析Fig.3 Comparison between DR-RDC and DSC in accuracy

從圖中可以得到:

1)不同錯(cuò)誤率下,DR-RDC的檢測(cè)精確度明顯優(yōu)于DSC,且DSC情況下函數(shù)依賴的檢測(cè)精確度波動(dòng)比較大.這是因?yàn)镈R-RDC既考慮了函數(shù)依賴對(duì)數(shù)據(jù)集的符合程度,又考慮了函數(shù)依賴之間可能存在的沖突,其計(jì)算精確度的針對(duì)目標(biāo)是所有滿足符合度閾值λ的函數(shù)依賴,根據(jù)函數(shù)依賴之間的沖突數(shù)量來(lái)判斷檢測(cè)精確度,而DSC只考慮函數(shù)依賴置信度的大小,其計(jì)算精確度的針對(duì)目標(biāo)是所有函數(shù)依賴,且僅根據(jù)置信度的大小來(lái)判斷函數(shù)依賴的檢測(cè)精確度.這既可能引入無(wú)效的函數(shù)依賴,又可能丟失成立的函數(shù)依賴,所以精確度的檢測(cè)結(jié)果波動(dòng)比較大.

2)當(dāng)橫坐標(biāo)的取值大于0.6時(shí),DSC情況下橫縱坐標(biāo)的乘積在減小.這是因?yàn)楫?dāng)橫坐標(biāo)取值為0.6時(shí),DSC方法已經(jīng)挖掘了所有滿足置信度閾值的函數(shù)依賴,在余下的部分沒有滿足條件的函數(shù)依賴,所以橫縱坐標(biāo)的乘積在逐漸減小.由實(shí)驗(yàn)結(jié)果可得,DR-RDC優(yōu)于DSC.

5.2.3 數(shù)據(jù)檢測(cè)與修復(fù)效果評(píng)估

為驗(yàn)證我們算法所得的校準(zhǔn)否定約束集對(duì)數(shù)據(jù)修復(fù)的性能,本文使用錯(cuò)誤檢測(cè)率和錯(cuò)誤修復(fù)率這兩個(gè)指標(biāo)對(duì)DR-RDC方法和使用原始否定約束集的數(shù)據(jù)修復(fù)效果進(jìn)行對(duì)比分析.錯(cuò)誤檢測(cè)率Dr和修復(fù)率Rr的表達(dá)式定義如下:

(8)

(9)

圖4是DR-RDC與原始否定約束集的實(shí)驗(yàn)效果對(duì)比分析圖.

圖4 DR-RDC與原始否定約束集對(duì)比分析Fig.4 Comparison between DR-RDC and raw denial constraint sets

圖4中x軸表示數(shù)據(jù)集中噪聲數(shù)據(jù)的比例,y軸是對(duì)應(yīng)的檢測(cè)指標(biāo).從圖4可以看出:

1)DR-RDC對(duì)數(shù)據(jù)集的錯(cuò)誤檢測(cè)率和修復(fù)率均在90%上,這說明本文所提出的方法具有顯著的清洗效果.

2)相同條件下,原始否定約束集對(duì)數(shù)據(jù)集的錯(cuò)誤檢測(cè)率整體上略高于DR-RDC的實(shí)驗(yàn)結(jié)果,但錯(cuò)誤修復(fù)率明顯低于DR-RDC的實(shí)驗(yàn)結(jié)果,且原始否定約束集對(duì)數(shù)據(jù)集的錯(cuò)誤檢測(cè)率和修復(fù)率相差較大.這是因?yàn)樵挤穸s束集未考慮其對(duì)數(shù)據(jù)集的符合程度,及否定約束之間可能存在的沖突,致使原始否定約束集中包含一些無(wú)效的否定約束,在對(duì)數(shù)據(jù)集進(jìn)行檢測(cè)時(shí),會(huì)將一些正確的數(shù)據(jù)誤判為錯(cuò)誤數(shù)據(jù),導(dǎo)致其錯(cuò)誤檢測(cè)率偏高,而數(shù)據(jù)修復(fù)過程中,可能將原本正確的數(shù)據(jù)修改為錯(cuò)誤數(shù)據(jù),導(dǎo)致其錯(cuò)誤修復(fù)率降低,所以產(chǎn)生錯(cuò)誤檢測(cè)率與修復(fù)率相差較大的結(jié)果.

綜上分析可得,本文提出的DR-RDC方法正確可行,能夠有效的解決數(shù)據(jù)中的不一致問題,且相對(duì)于原始約束規(guī)則,數(shù)據(jù)修復(fù)效果有顯著的提升.

6 總結(jié)與展望

數(shù)據(jù)質(zhì)量規(guī)則是解決數(shù)據(jù)不一致問題的有效方法,然而含沖突的、符合度較低的約束規(guī)則卻會(huì)極大的降低數(shù)據(jù)清洗效果.本文首先利用符合度記分函數(shù)和關(guān)聯(lián)矩陣對(duì)否定約束集進(jìn)行校準(zhǔn),得出高符合度的校準(zhǔn)否定約束集,將其作用于待測(cè)數(shù)據(jù)集,得出證據(jù)規(guī)則集及對(duì)應(yīng)的沖突元組集,根據(jù)證據(jù)規(guī)則的符合度分?jǐn)?shù),從高到低地修復(fù)其對(duì)應(yīng)的沖突元組集,選取使條件概率最大的屬性值作為沖突屬性修復(fù)值,直到?jīng)_突元組集不違反任一否定約束.通過實(shí)驗(yàn)驗(yàn)證了DR-RDC方法的可行性和高效性.未來(lái)的工作中,我們將致力于提高符合度閾值λ準(zhǔn)確度的同時(shí)優(yōu)化算法,進(jìn)一步提高約束規(guī)則的檢測(cè)精確度,提升數(shù)據(jù)修復(fù)的質(zhì)量和效率.