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

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

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

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

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

1 引言

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

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

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

表1 Customer Relation schema R

表2 Relation schemamR

2 相關(guān)概念

2.1 CFDs相關(guān)概念

2.1.1 CFDs定義

在關(guān)系R上的條件函數(shù)依賴φ的形式為(R: X→A, tp), 其中X→A是標(biāo)準(zhǔn)的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]等于常數(shù), 且任意B∈X上的屬性值tp[B]也都等于常數(shù), 則該φ為常CFD. 如果tp[A]=_且X中存在屬性B有tp[B]=_, 則該φ為變CFD[3].例如前面提到的φ0為變CFD, φ1, φ2, φ3為常CFDs.

2.1.3 CFDs語義[5]

為了說明CFD的語義, 我們先在屬性值上定義一個關(guān)系符≤, 如果η1=η2或者η1為常數(shù), η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當(dāng)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當(dāng)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ī)則, 當(dāng)tp[AL]=tp[AR]時, 所有的實例都能滿足, 當(dāng)tp[AL],tp[AR]為不同的常數(shù)時, 所有的實例都不能滿足. 故我們只考慮非平凡的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

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

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

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)中的某個常數(shù)a, 或者任意值, 用"_" 表示.

根據(jù)表1得出的四個CFDs, 我們只取LHS(φ)對應(yīng)的屬性值 , 結(jié)合主數(shù)據(jù)表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ī)則可以看到來自不同數(shù)據(jù)源的模式表, 代表同一實體的屬性命名是存在差異的,不一定與樣本模式表R中的屬性對應(yīng). 再者, 輸入樣本可能存在少量臟數(shù)據(jù), 為此, 我們只能通過它們的定義域相似度來確定映射關(guān)系.

2.2.2 編輯規(guī)則語義

編輯規(guī)則除了具有靜態(tài)語義還具有類似于匹配依賴[6](MDs)的動態(tài)語義, 根據(jù)上面得到的四個編輯規(guī)則ψ0-ψ3, 如果t[ X]≤tp[X]且t[ X]=tm[Xm]則t[ A]:=tm[Am], 意思是說如果待修復(fù)元組能匹配模式組且能在主數(shù)據(jù)中找到LHS(ψ)上相等的元組, 則用該元組Am屬性上的值修改待修復(fù)元組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中的數(shù)據(jù), [t1]{AC}=[t2]{AC}=[t4]{AC}=[t7]{AC}={t1, t2, t4, t7}, π{AC}={{t1, t2, t4, t7},{t3},{t5, t6, t8}}.

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

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

3.1 算法準(zhǔn)備

FastCFD的目的是對每一個屬性A∈attr( R) 作為規(guī)則的右邊, 找到所有可能對應(yīng)的規(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)組成. 這樣我們的任務(wù)主要是計算 Cover(A, r, k). 而差集的覆蓋與Cover(A, r, k)是有關(guān)系的, 差集的最小覆蓋對應(yīng)于最小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)的獲取可以使用文獻(xiàn)[12]中GCGROWTH算法得到, 這里只考慮開集, 所謂開集指的是在保持支持度不變的情況下, 不存在Y?X, sp=tp[ Y ] 這樣的模式組(Y, sp), 則(X, tp)為開集. 對常CFD和變CFD的驗證可以根據(jù)如下引理[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ī)則的算法采用改進(jìn)的FastCFD. FastCFD的主要兩個步驟是FindCover和FindMin. 根據(jù)引理2, FindCover首先要得到在r上的所有k-頻繁開集Frk(r), 并按開集大小升序排序, 即優(yōu)先考慮開集中包含屬性少的開集.為了有效地檢索Frk(r)中的元素, 用哈希表存放這些元素. 對F(r)中的每個項集(X, t), 計算Dm(r)的

rkp Atp

最小覆蓋, 在該計算過程中會調(diào)用FindMin. 下面給出BEFastER的詳細(xì)過程.

?

?

?

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

?

?

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

?

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

3.3 算法應(yīng)用

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

(1) 根據(jù)文獻(xiàn)[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中的數(shù)據(jù), 找出滿足t[CC]=01的元組有rCC=01={t1, t2, t3, t4, t8}.

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

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

STRcc=01

圖1 方法的部分過程

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

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

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

3.4 算法復(fù)雜度分析

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

4 實驗

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

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

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

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

4.2 實驗結(jié)果

在數(shù)據(jù)集HOSP和HOSPM下, 隨著支持度閾值的變化, 本文改進(jìn)的算法BEFastER和基于文獻(xiàn)[3]的FastER的響應(yīng)時間如圖2所示.

圖2 關(guān)于支持度閾值k的時間變化

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

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

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

圖4 數(shù)據(jù)集D中包含錯誤元組數(shù)對修復(fù)正確率的影響

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

5 結(jié)語

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

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 胡艷麗,張維明.條件依賴?yán)碚摷捌鋺?yīng)用展望.計算機(jī)科學(xué), 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 劉波,耿寅融.數(shù)據(jù)質(zhì)量檢測規(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