基于輸入樣本和主數據的編輯規(guī)則挖掘算法①

楊 輝, 于守健, 陳少總(東華大學 計算機科學與技術學院, 上海 201620)

基于輸入樣本和主數據的編輯規(guī)則挖掘算法①

楊 輝, 于守健, 陳少總
(東華大學 計算機科學與技術學院, 上海 201620)

基于編輯規(guī)則和主數據的數據修復技術能自動地、確切地修復不一致數據, 但目前編輯規(guī)則的獲取主要依靠專業(yè)人員的定義. 為了實現數據清洗全自動化, 數據規(guī)則的挖掘技術近年來成為研究熱點, 針對條件函數依賴提出的挖掘算法主要有CFDMiner, CTANE, FastCFD. 在此基礎上, 擴展條件函數依賴(CFD)的定義, 在編輯規(guī)則的定義下提出了一種基于輸入樣本和主數據的編輯規(guī)則挖掘算法, 主要思路是從輸入樣本中挖掘出CFD, 然后根據輸入樣本與主數據在屬性上的定義域相似性求出輸入樣本在主數據中的對應屬性, 從而形成帶模式組的編輯規(guī)則, 此算法能有效地挖掘編輯規(guī)則. 且所挖掘的編輯規(guī)則按照編輯規(guī)則語義能有效地進行數據修復.

編輯規(guī)則; 條件函數依賴; 數據清洗; 等價類劃分

1 引言

基于編輯規(guī)則和主數據的數據修復[1]比基于CFD的數據修復[2]更有效, 主要體現在數據修復的精確性上, 且編輯規(guī)則不會引入新的錯誤. 基于編輯規(guī)則的清洗方案更有望被數據清洗工具所采用, 這樣, 從輸入樣本自動挖掘編輯規(guī)則的技術是很有必要的. 事實上, 僅僅依靠領域昂貴的專業(yè)人員和漫長的手工來定義規(guī)則往往是不現實的. 正如Gartner所報道, 清洗規(guī)則的挖掘在商業(yè)數據質量工具中至關重要.

在實際中, 關于編輯規(guī)則挖掘關心的問題是: 給定關系模式R中的樣本實例r, 找到滿足實例r的所有編輯規(guī)則集Σ的正則覆蓋. 即邏輯上等價于Σ的規(guī)則集cΣ. 挖掘編輯規(guī)則的關鍵任務是挖掘CFDs, 最后去匹配主數據中的屬性, 匹配方法是將輸入樣本在每個屬性上的定義域與主數據每個屬性上的定義域進行比較, 定義域相似度滿足定義的閾值即為對應的屬性,并將對應的屬性保存在哈希表中, 這樣我們得到CFDs后, 從哈希表中找到對應的屬性就可以得到我們所需的編輯規(guī)則了. 為了減少冗余, 應該使所挖掘的每個CFD是最小的, 即非平凡的和左約簡的. 挖掘的難點是時間復雜度高, 從實例中挖掘出CFDs的正則覆蓋集時間復雜度就已經達到指數級了. 再者, 編輯規(guī)則需要綁定主數據中的屬性, 會遇到CFDs挖掘中不曾遇到的困難, 根據表1中的實例數據0r[3], 觀察可以得到如下幾個CFDs, 分別表示為:

從上面的CFDs規(guī)則可以看出, 國家編碼(CC)和地區(qū)編碼(AC)可以決定城市, 規(guī)則0φ表明在英國,郵政編碼(ZIP)可以唯一決定街道(STR). 從上面觀察所得的CFDs可以看出有兩類CFD, 但規(guī)則左邊不是最約簡的, 因此通過算法能同時挖掘出這兩類最小CFDs是具有挑戰(zhàn)的; 另一個挑戰(zhàn)是對CFDs擴展, 即確定編輯規(guī)則中來自主數據的屬性集, 表2中的主數據, 與輸入實例數據來源不同, 字段名不能一一對應起來, 例如電話號碼可以表示成PN或TEL, 地址可以表示成STR或POST. 為了解決以上難點, 提出了能挖掘出最小的兩類CFDs和匹配主數據形成編輯規(guī)則的算法.

表1 Customer Relation schema R

表2 Relation schemamR

2 相關概念

2.1 CFDs相關概念

2.1.1 CFDs定義

在關系R上的條件函數依賴φ的形式為(R: X→A, tp), 其中X→A是標準的FD形式, X∈attr( R), tp是屬性X和A上的模式組[4]. 規(guī)則的左邊屬性集記為LHS(φ), 右邊記為RHS(φ). 例如φ0中, ([CC,ZIP]→STR)為FD形式, (44,_||_)為模式組, LHS(φ0)為[CC,ZIP], RHS(φ0)為STR.

2.1.2 CFDs分類

如果tp[A]等于常數, 且任意B∈X上的屬性值tp[B]也都等于常數, 則該φ為常CFD. 如果tp[A]=_且X中存在屬性B有tp[B]=_, 則該φ為變CFD[3].例如前面提到的φ0為變CFD, φ1, φ2, φ3為常CFDs.

2.1.3 CFDs語義[5]

為了說明CFD的語義, 我們先在屬性值上定義一個關系符≤, 如果η1=η2或者η1為常數, η2為“_”, 則有η1≤η2. 例如表1中元組, (44,"EH4 1DT","EDI)≤(44,_,_). 如果t1≤t2我們就說t1匹配t2; 如果t1≤t2, t2≤t1記為t1?t2. 例如(44,"EH4 1DT","EDI)?(44,_,_). 給定規(guī)則φ, 如果對于實例r中的每對元組t1, t2當t1[ X]=t2[ X]≤tp[X ]時, 都有t1[ A]=t2[ A]≤tp[A]成立, 則r|=φ. 如果定義滿足φ的一個r子集為rφ={t| t∈r, t[ X]≤tp[X ]}, 那么只需考慮rφ中的任意兩對t1, t2當t1[ X]=t2[X]時,是否有t1[ A]=t2[A]和t1[ A]≤tp[A]成立, 而不用考慮整個r. 如果r滿足規(guī)則集Σ中的每個φ, 則r|=Σ.對于(X→Y, tp)中Y為多屬性集合的規(guī)則, 等價于多個規(guī)則右邊只有一個屬性的規(guī)則. 這里我們只考慮RHS(φ)為單一屬性集的規(guī)則.

2.1.4 最小CFDs

給定了模式R中的樣本實例r, 挖掘算法的目的是找到所有r滿足的CFDs. 為了得到的規(guī)則集是非冗余的, 僅包含最小CFDs, 首先給出最小CFDs的形式化定義.

對于R上的CFDφ=(X→A, tp), 如果A∈X,則為平凡的CFD. 因為這樣的規(guī)則, 當tp[AL]=tp[AR]時, 所有的實例都能滿足, 當tp[AL],tp[AR]為不同的常數時, 所有的實例都不能滿足. 故我們只考慮非平凡的CFDs. 對于常CFDs, 如果Y?X, r|≠(Y→A,( tp[ Y]||a ))則為左約簡的. 對于變CFDs, 如果Y?X, r|≠(Y→A,( tp[ Y ]||_))且對任意tp?的有r|≠(Y→A,[Y ]||_))則為左約簡的.非平凡的, 左約簡的CFD稱為最小CFD. 例如, 第一部分中φ0是最小CFD; φ1不是最小CFD, 因為從LHS(φ1)可以刪掉屬性CC后, 仍有r0|=(AC→CT,(908||MH)).

2.1.5 頻繁CFDs

現實中的數據往往包含一些臟數據, 為了排除包含錯誤的CFD, 只考慮那些模式組的支持度不小于閾值的CFDs. φ=(X→A, tp) 在r中的支持度記為sup(φ,r), 表示r中滿足規(guī)則φ的元組數. 對自然數k≥1, 如果sup(φ,r)≥k, 則CFD為k-頻繁的. 例如φ1是3-頻繁的, φ2是2-頻繁的.

2.2 編輯規(guī)則相關概念

2.2.1 編輯規(guī)則定義

定義在(R, Rm)上的編輯規(guī)則是一對((X, Xm)→(A, Am),tp[X ]), 其中:

(1)X和Xm分別來自模式R和Rm,X=Xm;

(2)A∈R X, Am∈RmXm;

(3)tp是屬性X上的模式組, 對每一個B∈X 的屬性, 其值為定義域dom( B)中的某個常數a, 或者任意值, 用"_" 表示.

根據表1得出的四個CFDs, 我們只取LHS(φ)對應的屬性值 , 結合主數據表2, 可以得到如下四個編輯規(guī)則:

ψ0:(([CC,ZIP],[CC,ZIP])→(STR,POST),(44,_))

ψ1:(([CC,AC],[CC,AC])→(CT,CT),(01,908))

ψ2:(([CC,AC],[CC,AC])→(CT,CT),(44,131))

ψ3:(([CC,AC],[CC,AC])→(CT,CT),(01,212))

從上面的四個編輯規(guī)則可以看到來自不同數據源的模式表, 代表同一實體的屬性命名是存在差異的,不一定與樣本模式表R中的屬性對應. 再者, 輸入樣本可能存在少量臟數據, 為此, 我們只能通過它們的定義域相似度來確定映射關系.

2.2.2 編輯規(guī)則語義

編輯規(guī)則除了具有靜態(tài)語義還具有類似于匹配依賴[6](MDs)的動態(tài)語義, 根據上面得到的四個編輯規(guī)則ψ0-ψ3, 如果t[ X]≤tp[X]且t[ X]=tm[Xm]則t[ A]:=tm[Am], 意思是說如果待修復元組能匹配模式組且能在主數據中找到LHS(ψ)上相等的元組, 則用該元組Am屬性上的值修改待修復元組A屬性上的值.

2.2.3 等價類劃分[7]

定義在屬性集X上的等價類為一類在屬性X上值相等的元組集, 表示成[t]X={u∈r| t[ A]=u[ A],?A∈X }. 屬性X上所有的等價類組成的集合為屬性X上的劃分, 記為πX={[t]X,t∈r} . 所有等價類的并集等于實例r. 例如對于表1中的數據, [t1]{AC}=[t2]{AC}=[t4]{AC}=[t7]{AC}={t1, t2, t4, t7}, π{AC}={{t1, t2, t4, t7},{t3},{t5, t6, t8}}.

3 編輯規(guī)則挖掘算法

關于函數依賴、條件函數依賴、關聯規(guī)則挖掘算法的研究, 文獻[8]和文獻[9]將其統(tǒng)一為數據質量規(guī)則, 并提出了數據質量規(guī)則挖掘算法QRMiner. 考慮到輸入的樣本數據本來就可能存在臟數據, 文獻[10]還對所挖掘的數據質量規(guī)則從3個角度進行了評估.本文主要是對挖掘條件函數依賴算法FastCFD[3]的擴展與改進, 得到編輯規(guī)則挖掘算法BEFastER. FastCFD是一種基于深度優(yōu)先, 能挖掘最小的, k-頻繁的CFD算法.

3.1 算法準備

FastCFD的目的是對每一個屬性A∈attr( R) 作為規(guī)則的右邊, 找到所有可能對應的規(guī)則左邊Y, 形成最小的φ=(Y→A, tp), 其中Y?attr( R)A , sup(φ,r)≥k. 我們把這樣的規(guī)則集記為Cover(A, r, k),顯然所有的k-頻繁最小CFDs可以由∪A∈attr(R)Cover(A, r, k)組成. 這樣我們的任務主要是計算 Cover(A, r, k). 而差集的覆蓋與Cover(A, r, k)是有關系的, 差集的最小覆蓋對應于最小CFD的LHS(φ).

3.1.1 差集

為了計算Cover(A, r, k), 我們需引入差集的概念[11], 定義在一對元組t1, t2的差集表示為:

得到最小差集后, 需要找到其最小覆蓋. 由此, 我們引入覆蓋的概念: 令Z?attr( R) , X?P( attr( R)), P( attr( R))為集合attr( R)的冪集, 如果對每個Y∈X, Y∩Z≠? , 則Z覆蓋X; 如果不存在Z的真子集也能覆蓋X, 則Z為最小覆蓋. 這樣可以得到Dm(r)的最小覆蓋為:

{CT}

3.1.2 驗證CFDs

我們找最小差集的最小覆蓋是從模式組(X, tp)開始的, 即從滿足模式tp的元組記為rtp中計算出(r), 其最小覆蓋Y?attr( R)X∪{A}與X組成tp最小CFD φmin=([X, Y]→A,( tp,_,,,_||a)). 對于模式組(X, tp)的獲取可以使用文獻[12]中GCGROWTH算法得到, 這里只考慮開集, 所謂開集指的是在保持支持度不變的情況下, 不存在Y?X, sp=tp[ Y ] 這樣的模式組(Y, sp), 則(X, tp)為開集. 對常CFD和變CFD的驗證可以根據如下引理[3]來判斷.

3.1.3 剪枝策略

剪枝策略告訴我們沒有必要考慮所有的k-頻繁開集(Xc,tc), 即如果([Xc,Xv]→A,( tc,tv||_))滿足要

p pp求, 則所有作為Xc的超集X′, 形成的開集(X′, t′p)就不用考慮了. 這樣可以提高挖掘CFD的效率. 下面的引理[3]告訴我們開集作為CFD的常模式部分是充分的.

引理2. 對于變CFDφ=(X→A,( tp||_)), 且r|=φ, sup(φ,r)≥k, 如果φ是最小的, 則(Xc,tc)是

p k-頻繁開集.

3.2 算法描述

為了挖掘出有效的編輯規(guī)則, 挖掘編輯規(guī)則的算法采用改進的FastCFD. FastCFD的主要兩個步驟是FindCover和FindMin. 根據引理2, FindCover首先要得到在r上的所有k-頻繁開集Frk(r), 并按開集大小升序排序, 即優(yōu)先考慮開集中包含屬性少的開集.為了有效地檢索Frk(r)中的元素, 用哈希表存放這些元素. 對F(r)中的每個項集(X, t), 計算Dm(r)的

rkp Atp

最小覆蓋, 在該計算過程中會調用FindMin. 下面給出BEFastER的詳細過程.

?

?

?

從過程FindCover可以發(fā)現, 其中調用了兩個方法,分別為genDiffSets和FindMin. genDiffSets方法的作用是根據滿足模式tp的元組, 設定的支持度閾值和屬性A得到Dm(r). FindMin方法是個遞歸函數, 主要按Atp深度優(yōu)先的方式搜索一個按屬性字母順序生成的枚舉樹, 從根到某個節(jié)點的路徑可以形成Dcurr的所有子集,然后判斷子集Y是否是Dm(r)的最小覆蓋, 在該方法Atp中還用Dcurr保存當前還沒被Y覆蓋的差集, 最后返回所有X與最小覆蓋Y形成的CFD規(guī)則. 下面詳細介紹這兩種方法.

?

?

上面生成差集的方法是基于等價類劃分的, 只保留等價類中元素個數大于1 的等價類, 且盡量取大集合等價類. 第3 行計算所有屬性在tp r 中的劃分; 第4行合并所有等價類大小大于1 的等價類; 第6-9 行求MC 中所有等價類中所有元組具有相同值的屬性集;與文獻[3]中的計算差集的方法相比, 減少了元組對的比較次數. 下面介紹FindMin .

?

算法BEFastER首先計算了兩個全局變量, 一個存放屬性對的哈希表, 將CFD規(guī)則中的屬性與主數據中的屬性關聯起來; 另一個為存放所有k-頻繁開集Frk( r)的哈希表, 并作為FindCover的參數.

3.3 算法應用

為了驗證算法的有效性, 將其應用于表1和表2,過程如下:

(1) 根據文獻[12]提供的算法可以得到所有的3-頻繁開集為:

Fr3(r)={(CC,01),(CC,44),(AC,131),(PN,2222222),(ZIP,07974), (CT,MH),(AC,908),([CC,AC],[01,908]),([CC,CT],[01,MH])}

(2) 從Fr3中取一個開集(CC,01)為例, 展開下面的計算.

(3) 掃描表1中的數據, 找出滿足t[CC]=01的元組有rCC=01={t1, t2, t3, t4, t8}.

(4) 調用genDiffSets方法, 計算每個屬性的劃分取等價類中元素大于1的等價類, 得到如下結果:

這里不妨把規(guī)則右邊定為STR, NM在每個元組中都不一樣, 這里不考慮該屬性則Dm(r)={[PN],[AC,CT]}.

STRcc=01

圖1 方法的部分過程

(6) 根據(5)中得到Y, 可以得到兩個最小變CFDs, 分別為:

(7) 由于表1中存在臟數據且表1和表2的記錄分別只是模式表R和mR的部分, 這里我們設定相似度閾值為0.5, 存在于哈希表有(CC,CC), (AC,AC), (CT,CT), (PN,TEL), (STR,POST).

(8) 最后得到的編輯規(guī)則為:

3.4 算法復雜度分析

BEFastER算法的時間主要消耗在genDiffSets方法和FindMin上, genDiffSets中最耗時的是計算等價類所花的時間, 在最壞的情況下, 由關系屬性數目和滿足模式tp的元組數決定, 故此方法的時間復雜度為O(|R|); FindMin是個遞歸方法, 會占用一定的?？臻g, 但可以減少遍歷R{A}所有子集的時間, 棧空間由遞歸次數決定, 遞歸次數越多, 程序結束越遲,相應的時間開銷就越大, 在最壞情況下, 時間復雜度為O(|＞curr|log(|＞curr|)), ＞curr為最開始傳入的＞curr. 對比genDiffSets所花的時間, 這點時間可以忽略. 如果不考慮GCGROWTH計算開集的時間, 則BEFastER的總的時間開銷為O(|Frk(r)||R||, |Frk(r)|為開集數目.

4 實驗

本節(jié)主要通過來自醫(yī)院的真實數據HOSP[13]來進行實驗研究, 將從響應時間和挖掘的規(guī)則數目兩個指標來驗證算法的有效性. 并比較了改進算法與擴展的文獻[3]算法. 主要改進在計算差集的方法上和判斷常CFDs的條件上.

4.1 實驗數據和環(huán)境

實驗數據: 由于主數據的獲取比較難, 假設以處理的HOSP為主數據HOSPM, 即去除HOSP中的空值和異常值記錄, 得到干凈的主數據進行模擬. 這樣一來匹配主數據屬性這步基本可以忽略. HOSP包括七個屬性和9455條記錄.

實驗環(huán)境: 我們用java語言在window7操作系統(tǒng), Mysql數據庫管理系統(tǒng), Intel Core i5-2400 3.10GHz CPU和4G內存下實現了本文的算法. 每次實驗重復了5次, 取平均結果.

4.2 實驗結果

在數據集HOSP和HOSPM下, 隨著支持度閾值的變化, 本文改進的算法BEFastER和基于文獻[3]的FastER的響應時間如圖2所示.

圖2 關于支持度閾值k的時間變化

從上面的結果可以知道, 兩種算法基本對支持度的敏感程度都不大, 和文獻[3]的結論一致, 但在所得規(guī)則數一樣的情況下, 我們改進后的算法比直接擴展的性能更好.

另一個實驗結果是BEFastER隨支持度的變化,挖掘的規(guī)則數的變化情況, 如下圖3所示, 規(guī)則數隨支持度的加大, 不管是常規(guī)則數還是變規(guī)則數都在明顯地減少.

圖3 關于支持度閾值k的規(guī)則數變化

圖4 數據集D中包含錯誤元組數對修復正確率的影響

為了驗證所得的編輯規(guī)則是否能修復數據, 我們根據編輯規(guī)則語義進行了修復實驗, 將支持度為20得到的編輯規(guī)則應用于添加了錯誤的數據集HOSP. 由圖4 的結果可以知道, 修復準確率能穩(wěn)定達到70%-80%, 不能達到100%的主要原因是我們不能確定t[LHS(φ)]的值是否正確, 如果待修復的元組中錯誤的t[LHS(φ)]匹配了tm[LHS(φ)], 那么將會導致錯誤的修復. 另一個原因是在存在錯誤樣本情況下, 我們挖掘的編輯規(guī)則很難做到完全正確.

5 結語

本文提出了基于條件函數依賴挖掘的編輯規(guī)則挖掘算法, 從編輯規(guī)則的形式化定義來看, 與CFD相比,只是多了主數據中的屬性, 所以本文的第一個工作是重點挖掘最小CFDs包括常CFDs和變CFDs, 此工作的主要耗時任務是計算差集和最小覆蓋, 而本文計算差集的方法大大減少了元組對的比較, 在得到差集為空時, 考慮到輸入樣本中存在錯誤, 我們降低了值非得唯一的要求, 從而可以得到更多的常CFDs. 對得到的CFDs只利用其模式組的左邊部分, 用于匹配待修復的元組; 第二個工作是在主數據中找對應的屬性,由于來自不同數據源的表結構存在差異, 我們采用了基于定義域的簡單計算模型, 理想狀態(tài)下對應屬性定義域應該是一樣的. 但由于輸入樣本中存在臟數據,定義域只能近似匹配. 本文通過實驗驗證了我們所提算法的有效性, 能在有限的時間里挖掘出編輯規(guī)則,并對所得的編輯規(guī)則按照編輯規(guī)則語義進行了質量評估, 進一步驗證了我們的算法確實實用有效.

1 Fan W, Li J, Ma S, et al. Towards certain fixes with editing rules and master data. Proc. of the VLDB Endowment, 2010, 3(1-2): 173–184.

2 Cong G, Fan W, Geerts F, et al. Improving data quality: Consistency and accuracy. Proc. of the 33rd international conference on very large data bases. VLDB Endowment. 2007. 315–326.

3 Fan W, Geerts F, Li J, et al. Discovering conditional functional dependencies. IEEE Trans. on Knowledge and Data Engineering, 2011, 23(5): 683–698.

4 Fan W, Geerts F, Jia X, et al. Conditional functional dependencies for capturing data inconsistencies. ACM Trans. on Database Systems (TODS), 2008, 33(2): 6.

5 胡艷麗,張維明.條件依賴理論及其應用展望.計算機科學, 2009,36(12):115–118.

6 Fan W, Ma S, Tang N, et al. Interaction between record matching and data repairing. Journal of Data and Information Quality (JDIQ), 2014, 4(4): 16.

7 Huhtala Y, K?rkk?in J, Porkka P, et al. TANE: An efficient algorithm for discovering functional and approximate dependencies. The computer journal, 1999, 42(2): 100–111.

8 劉波,耿寅融.數據質量檢測規(guī)則挖掘方法.模式識別與人工智能,2012,25(5):835–844.

9 Medina R, Nourine L. A unified hierarchy for functional dependencies, conditional functional dependencies and association rules. Lecture Notes in Computer Science, 2009, 5548: 98–113.

10 Chiang F, Miller R J. Discovering data quality rules. Proc. of the VLDB Endowment, 2008, 1(1): 1166–1177.

11 Wyss C, Giannella C, Robertson E. Fastfds: A heuristicdriven, depth-first algorithm for mining functional dependencies from relation instances extended abstract. Data Warehousing and Knowledge Discovery. Springer Berlin Heidelberg. 2001. 101–110.

12 Li H, Li J, Wong L, et al. Relative Risk and Odds Ratio: A Data Mining Perspective (Corrected Version). Pods, 2005: 368–377.

13 http://www.hospitalcompare.hhs.gov/.

Method for Discovering Editing Rules From Sample Inputs and Master Data

YANG Hui, YU Shou-Jian, CHEN Shao-Zong
(School of Computer Science and Technology, Donghua University, Shanghai 201602, China)

Data repairing based on editing rules and master data can automatically and exactly fix inconsistent data, but editing rules mainly relies on the definition by professional staff at present. To achieve data cleaning automatically in the whole process, the techniques for discovering data rules become a hot research topic in recent years. The algorithms for mining CFDs mainly involve CFDMiner, CTANE, FastCFD. Based on the above techniques, we provide a mining algorithm for editing rule, which is based on sample inputs and master data under the extension definition of CFD and the definition of edit rules. The main ideas is as below: Mining CFD from sample inputs firstly; then according to the domain similarity between input samples and master data, we can get the corresponding properties of input samples from the master data, forming editing rules with pattern group. The algorithm can effectively discover edit rules. And the mined edit rules can effectively repair the data in accordance with the semantic of the rules.

editing rules; conditional functional dependency; data cleaning; equivalence classes partitions

2016-07-17;收到修改稿時間:2016-09-13

10.15888/j.cnki.csa.005728