DR-RDC:基于校準否定約束集的數(shù)據(jù)修復方法

盧 菁,黨延領,劉 叢

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

2 DR-RDC處理流程

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

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

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

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

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

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

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

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

3 否定約束集校準

3.1 否定約束定義

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

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

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

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

3.2 符合度計算

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

3.2.1 負支持度

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

(1)

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

NS(φ)=1-Denial(φ)

(2)

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

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

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

假設存在以下否定約束:

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的元組對為〈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的元組對為〈T2,T6〉,即kcp=1,|V|=2,可得NS(c4)=0.8333.

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

3.2.2 正支持度

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

(3)

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

(4)

其中,|kE|是各類證據(jù)所對應的無沖突元組對個數(shù),k=0,1,…,|φ.predicates|-1.

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

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

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

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

(5)

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

(6)

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

3.3 校準步驟1:符合度校準

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

算法1.否定約束符合度校準算法.

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

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

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

2.for eachφin Σ

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

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

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

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

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

8. 由公式(3)計算各類證據(jù)對應的權重;

9.k++;

10.由公式(1)、(2)求出φ的負支持度分數(shù)NS(φ);

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

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

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

14.if(Conf(φ)<λ)

15. Σλ=Σλ-φ;

16.return Σλ;

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

3.4 校準步驟2:沖突消除

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

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

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

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

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

輸出:關聯(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所對應的位置為1;

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

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

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

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

10. else if(Tα.A

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

12. else

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

14.returnMatrix(Σλ,ΣA);

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

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

基于符合度記分函數(shù)和關聯(lián)矩陣的分析,我們設計出算法3對否定約束集進行校準.

算法3.否定約束集校準算法.

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

輸出:校準否定約束集Σ′

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

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

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

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

5. if (φi?φj)

6. 刪除φj;

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

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

9. 刪除φk;

10.return Σ′;

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

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

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

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

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

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

輸出:證據(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β〉添加到φ對應的沖突元組集Tc中;

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

8.return Σe,Tc;

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

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

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

(7)

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

算法5.沖突元組修復算法.

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

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

1.repeat

2.for eachφin Σe

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

4. for each conflictAinTc

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

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

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

8.until(Σe=φ);

5 實驗及結(jié)果

5.1 實驗配置與數(shù)據(jù)集

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

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

5.2 實驗結(jié)果及分析

5.2.1 符合度閾值λ的確定

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

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

1)平均精確度隨著λ的增大而增大,且增幅波動較小.這是因為λ取值越大,返回的否定約束就越少,而真實成立的否定約束相對增多,所以平均精確度隨著λ的增大而增大.

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

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

5.2.2 約束規(guī)則檢測精確度評估

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

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

從圖中可以得到:

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

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

5.2.3 數(shù)據(jù)檢測與修復效果評估

為驗證我們算法所得的校準否定約束集對數(shù)據(jù)修復的性能,本文使用錯誤檢測率和錯誤修復率這兩個指標對DR-RDC方法和使用原始否定約束集的數(shù)據(jù)修復效果進行對比分析.錯誤檢測率Dr和修復率Rr的表達式定義如下:

(8)

(9)

圖4是DR-RDC與原始否定約束集的實驗效果對比分析圖.

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

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

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

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

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

6 總結(jié)與展望

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