周健昌，卜媛媛

0 引言

隨著信息技術(shù)的進(jìn)一步推廣，人們在獲得大量信息，享受信息化帶來便捷的同時，數(shù)據(jù)質(zhì)量引起的問題—garbage in，garbage out，也日益突現(xiàn)。質(zhì)量存在問題的數(shù)據(jù)，常誤導(dǎo)決策者做出錯誤決定，輕則造成經(jīng)濟(jì)損失，重則帶來毀滅性打擊。

經(jīng)研究指出，在美國，因?yàn)閿?shù)據(jù)質(zhì)量的問題，每年造成經(jīng)濟(jì)損失達(dá) 6000億美元以上[1]。普化永道會計事務(wù)所調(diào)查表明，75%被調(diào)查公司存在因數(shù)據(jù)質(zhì)量問題而致經(jīng)濟(jì)損失現(xiàn)象；在數(shù)據(jù)庫挖掘項(xiàng)目中，近90%的研究者花在數(shù)據(jù)清洗和數(shù)據(jù)準(zhǔn)備上的時間，超過項(xiàng)目時間40%，25%研究者甚至超過80%[2]。以上數(shù)據(jù)明證：數(shù)據(jù)質(zhì)量問題普遍存在，也已造成嚴(yán)重威脅，且隨信息技術(shù)進(jìn)一步推廣，形勢必將更加嚴(yán)峻。

提高數(shù)據(jù)質(zhì)量的一個重要技術(shù)，是將“臟”的數(shù)據(jù)進(jìn)行清洗以使其變“干凈”，這實(shí)際上就是數(shù)據(jù)清洗。臟數(shù)據(jù)是指含錯誤的、冗余的、不一致的數(shù)據(jù)，它的來源是多樣的：數(shù)據(jù)來源繁多、時效性不一致或錄入錯誤等主客觀原因。

目前，對數(shù)據(jù)清洗的研究大多是領(lǐng)域相關(guān)的，不同的應(yīng)用領(lǐng)域?qū)ζ溆胁煌慕忉?，因而對?shù)據(jù)清洗還沒有統(tǒng)一的定義。然而，數(shù)據(jù)清洗的目的是基本一致的[3]:檢測數(shù)據(jù)中存在的錯誤和不一致，剔除或改正它們，以提高數(shù)據(jù)的質(zhì)量。數(shù)據(jù)清洗可按數(shù)據(jù)清洗對象、來源領(lǐng)域、產(chǎn)生原因、實(shí)現(xiàn)方式與范圍等不同指標(biāo)有各種劃分，但數(shù)據(jù)清洗的基本任務(wù)是相同的，都是過濾或修改那些不符合要求的數(shù)據(jù)，其基本流程都是相同的[4]：數(shù)據(jù)分析與定義，識別錯誤記錄，修正錯誤。

本文首先介紹條件函數(shù)依賴CFD的相關(guān)定義和性質(zhì)，主要研究了利用CFD進(jìn)行數(shù)據(jù)清洗的基本流程，并對其核心步驟提出了優(yōu)化方案，通過實(shí)驗(yàn)對比了FD、CFD用于數(shù)據(jù)清洗的差別，以及CFD受相關(guān)度量的影響，得出了與以往用于數(shù)據(jù)清洗的FD相比，CFD更優(yōu)勝的結(jié)論。

1 條件函數(shù)依賴

函數(shù)依賴(Functional Dependency,FD)在數(shù)據(jù)庫及知識發(fā)現(xiàn)領(lǐng)域，都是一個重要的的概念，然而它對規(guī)則的挖掘而言卻不太充分，因?yàn)楝F(xiàn)實(shí)中的規(guī)則往往是帶有條件的，如[郵編]→[街道名]在整個世界范圍內(nèi)是不成立的，但若前提是在英國，則它是成立的。

文獻(xiàn)[5]正是考慮到這種情況，最初出于數(shù)據(jù)清洗的目的而提出了條件函數(shù)依賴(Conditional Funcitonal Dependencies，CFD)。CFD是在FD的基礎(chǔ)上加入語義約束擴(kuò)展而來的，比FD表達(dá)更具體的約束，從而更適合于大量數(shù)據(jù)中數(shù)據(jù)特征的描述。定義1 CFD[5]:

設(shè)存在一個關(guān)系模式R，attr(R) 表示定義在其上的屬性集，對每個屬性A ，有A?attr(R)，A 的值域可以表示成dom(A)，定義在R 上的一個條件函數(shù)依賴φ可以表示成φ:(X→Y,Tp)。其中：

（1）X?attr(R)、Y?attr(R)；

（2）{X→Y}是一個標(biāo)準(zhǔn)函數(shù)依賴；

（3）Tp是與X和Y相關(guān)的模板，定義了相關(guān)屬性在取值上的約束條件，取值可以是定值常量也可以是"_"（"_"為變量，表示對應(yīng)屬性可取域中的任何值，但應(yīng)符合存在的蘊(yùn)涵及約束關(guān)系）。

可把ψ記為:ψ= (X→Y,Tp[X]|| Tp[Y])，則稱ψ中X相關(guān)的一方模板Tp[X]稱為LHS，將Y相關(guān)的一方模板Tp[Y]稱為RHS，則從FD、CFD語義可推知一成立的CFDψ有如下特點(diǎn)：

1) LHS、RHS要么兩方都含變量，這稱全變量CFD，要么兩方都不含變量，這稱常量CFD，除以上兩種情況外的僅LHS或RHS一方含變量是不可能出現(xiàn)CFD的.

2) 類似FD的Armstrong公理的合并律，設(shè)Y=A1∪A2∪…∪An，則任何(X→Y,Tp[X]|| Tp[Y])型CFD都可由(X→A1,Tp[X]||Tp[A1])、(X→A2,Tp[X]||Tp[A2]) … ( X→An,Tp[X]|| Tp[An])合成。

3) FD與CFD的關(guān)系：若將模板中關(guān)于LHS的部分Tp[X]看作約束條件，關(guān)于RHS的部分看作結(jié)果，符合Tp[X]這個條件的記錄組成的一個關(guān)系實(shí)例 r′（r的一個子集），則CFD就是r′上標(biāo)準(zhǔn)的FD(此即上述CFD定義中“標(biāo)準(zhǔn) FD”的含義)。

本文將通過下述表1來說明CFD及其特性和示例，說明如何將CFD應(yīng)用于數(shù)據(jù)清洗，如表1所示：

表1 信息學(xué)院學(xué)生信息表

據(jù)CFD的定義，我們可從表1中得到以下CFD：

ψ1:{(生源)→(性別),(湖北) || (男)}，意為：信息學(xué)院中，所有湖北籍學(xué)生均男性。

ψ2:{(層次)→(導(dǎo)師),(-) || (-)}，意為：“層次→導(dǎo)師”導(dǎo)師是一個FD關(guān)系.

ψ3:{(層次，專業(yè))→(生源),(研究生，-) || (-)}，意為：研究生中，不同專業(yè)的學(xué)生都來源于不同地方。

定義2：模板間的泛化關(guān)系[5]

為給CFD賦予語義，我們?yōu)槟０宓淖兞恐蹬c常量值定義出一個關(guān)系符“≤”，稱泛化。

首先，對模板的同一屬性分量取值n1、n2的泛化關(guān)系定義如下[5]：

n1≤n2，則n1==n2或n1是常量而n2是變量。

這種泛化關(guān)系很容易擴(kuò)展到有相同屬性集的模板Tp1[x],Tp2[x]上：

當(dāng)且僅當(dāng)? B∈X，都有 Tp1[B]≤Tp2[B]時，則有Tp1[X]≤Tp2[X],稱 Tp2[X]泛化 Tp1[X]或 Tp1[X]具化 Tp2[X]。

為方便后文表達(dá)，我們引入“!≤”符號，其含義為:n1!≤n2，則 n1≤n2不成立。

例如：ψ4:{(層次)→(導(dǎo)師),(-)||(-)}就是對ψ2:{(層次)→(導(dǎo)師),(本科生) || (無)}的泛化。

2 基于CFD的數(shù)據(jù)清洗步驟

基于CFD的數(shù)據(jù)清洗是一種基于規(guī)則的數(shù)據(jù)清洗方案，它的基本處理流程可歸納為：

1） 數(shù)據(jù)分析與定義：為檢測“臟數(shù)據(jù)”的類型，首先要對其進(jìn)行詳細(xì)的數(shù)據(jù)分析，除人工檢查數(shù)據(jù)屬性外，還應(yīng)通過分析程序自動取得關(guān)于數(shù)據(jù)質(zhì)量的元數(shù)據(jù)。

2） 獲得描述數(shù)據(jù)集特征的CFD集：取得足以描述數(shù)據(jù)特征的規(guī)則集，是任何基于規(guī)則的數(shù)據(jù)清洗技術(shù)的核心步驟之一。對基于CFD的數(shù)據(jù)清洗，取得CFD集的方法主要是依賴數(shù)據(jù)挖掘的方法，從數(shù)據(jù)集中取得CFD集，再根據(jù)業(yè)務(wù)領(lǐng)域知識或元數(shù)據(jù)約束等增刪CFD，以來進(jìn)一步充實(shí)CFD集。

3） 利用CFD規(guī)則檢測并標(biāo)識錯誤：為從數(shù)據(jù)集中消除重復(fù)記錄，首要的問題就是如何判斷兩條記錄是否相似重復(fù)。

4） 沖突處理：根據(jù)一定的清洗規(guī)則合并或刪除檢測出的錯誤、相似重復(fù)記錄，只保留其中正確的那些記錄。

5） 重復(fù)2～4項(xiàng)，直至數(shù)據(jù)質(zhì)量達(dá)標(biāo)為止。

3 基于CFD數(shù)據(jù)清洗的核心步驟

3.1 挖掘描述數(shù)據(jù)集的CFD集:

對不同的規(guī)則類型，各有不同的規(guī)則集獲得方法，而對于CFD，學(xué)者們已提出幾種有效CFD挖掘算法，如CTANE、CFDMiner、FastCFD等[6]。不同挖掘算法適用領(lǐng)域可能不同，但它們的最終結(jié)果應(yīng)一致—得出給定數(shù)據(jù)集中滿足的所有非冗余CFD集。我們的實(shí)驗(yàn)采用的是CTANE算法，它的基本原理利用了CFD的以下性質(zhì):

對于ψ:{ X→A,Tp[X]|| Tp[A]}有Count(X,Tp[X])-Class(X,Tp[X]) = Count(X∪A,Tp[X∪A]) -Class(X∪A,Tp[X∪A]),則ψ成立，則其中

1) Count(X,Tp[X])是指在整個關(guān)系實(shí)例r中，在X上取值符合Tp[X]的記錄的頻數(shù)，

2) X∪A是屬性集合的并(準(zhǔn)確應(yīng)寫作X∪{A}，本文中以此作簡寫)

3) Class(X,Tp[X])是指Tp[X]包含的等價類個數(shù)，即Tp[X]所蘊(yùn)含的不含變量的不同取值的種類數(shù)。

從示例表來看，除ψ1、ψ2、ψ3因滿足上述性質(zhì)而被定為CFD外,{(生源)→(專業(yè))，(貴州) || (軟工)}也是CFD，因?yàn)镃ount(生源，貴州)-Class(生源，貴州)=2-1，Count([生源，專業(yè)]，[貴州，軟工])- Class([生源，專業(yè)]，[貴州，軟工])=2-1。而{(姓名) || (生源)，(-) || (-)}則不成立，因?yàn)镃ount(姓名，-)-Class(姓名，-)=10-9，而Count([姓名，-])- Class(姓名，-)=10-10。

3.2 利用CFD檢測相似重復(fù)記錄

相似重復(fù)記錄的清洗，是數(shù)據(jù)清洗過程中最為關(guān)鍵的問題之一，也是研究最多的領(lǐng)域。解決相似重復(fù)記錄的問題，就是要對數(shù)據(jù)集合中的記錄進(jìn)行對象識別，即根據(jù)記錄所含的各種描述信息來確定與之相應(yīng)的現(xiàn)實(shí)實(shí)體。

文獻(xiàn)[7]與文獻(xiàn)[8]中提出了利用SQL查詢語句來實(shí)現(xiàn)檢測相似重復(fù)，其基本原理是:

若有ψ':{X→A,Tp[X]|| Tp[A]}、ψ'':{X→A,Tp[X]||Tp[A]},若Tp'[X]= Tp''[X]≤Tp[X]，但Tp'[A]≠Tp''[A]，則X取值為Tp'[X]、Tp''[X]的記錄中存在錯誤，用類SQL語句來描述如下：

一般地，檢測分兩個步驟進(jìn)行[9]:

例如，我們得出如下的CFD:

ψ5:{(導(dǎo)師)→(層次)，(-) || (-)}

ψ6:{(導(dǎo)師)→(層次)，(有) || (本科生)}，則我們可構(gòu)造如下Tp，如表2所示：

表2 θ1:{(導(dǎo)師)→(層次),Tp1}

顯然，表2所表過的θ1融合了ψ5、ψ6，而對于θ1，我們只要用就可以檢測出t2、t4、t5、t7、t8間存在違例記錄。

ψ7:{(層次，專業(yè))→(學(xué)制)，(-，軟工)→(-)}，如表3所示：

表3 θ2:{(層次,專業(yè))→(學(xué)制),Tp1}

從表3知，θ2包含了ψ7，而對θ2，我們僅通過是無法檢測出違例記錄的，只有使用時才能確定t1、t5、t6、t8是違例記錄。

實(shí)際應(yīng)用中，每個數(shù)據(jù)庫可能有多個CFDs作為約束條件。直觀地來說，可以針對每個CFD按上述的查詢進(jìn)行檢測操作，即每個CFD對應(yīng)一組查詢語句對，顯然隨著CFDs 數(shù)量的增加，檢索會顯得愈加繁雜。因此，文獻(xiàn)[8]提出，對多CFDs條件進(jìn)行整合，形成形式上新的約束條件和查詢語句對，實(shí)質(zhì)就是對相似CFD抽象它們的共性，引入了更泛化的CFD，以構(gòu)造一個更通用的SQL查詢對，從而將查詢的次數(shù)大大降低，我們并不深入探討此方法。

4 我們的改進(jìn)

4.1 為規(guī)則的挖掘引入支持度

現(xiàn)實(shí)數(shù)據(jù)中常受到噪聲的干擾，從而產(chǎn)生不一致的數(shù)據(jù)記錄。盡量消除噪聲也正是本文的目標(biāo)，然而，現(xiàn)實(shí)情況是，有時候我們只對記錄數(shù)達(dá)到一定限度的錯誤才作出修正，也就是說，允許存在一定的錯誤容忍度，這或許是對經(jīng)常進(jìn)行數(shù)據(jù)增刪的數(shù)據(jù)集對錯誤檢測效率的折衷，或者是實(shí)際應(yīng)用的需要，如網(wǎng)絡(luò)入侵檢測中，不能稍微一點(diǎn)錯誤都認(rèn)為是入侵的發(fā)生，因此，我們提出在規(guī)則檢測時，使用支持度閾值，只有達(dá)到一閾值的錯誤規(guī)則才予以考慮并修正。這樣做還有一個好處，正如Apriori算法中使用支持度剪枝，利用支持度的反單調(diào)性，我們可提前將不可能出現(xiàn)CFD規(guī)則的分枝剪去，從而大大速了規(guī)則挖掘的效率。

當(dāng)然，必需說明的是由于引入了支持度使得一些規(guī)則可能會被忽視，需根據(jù)應(yīng)用的情況來決定是否決定使得支持度。

4.2 為規(guī)則的挖掘與保存引入近似CFD概念

由前面的敘述知，對于無錯的數(shù)據(jù)，挖掘得的CFD其置信度總是100%的，而對于含錯的數(shù)據(jù)基本上是在大量的正確數(shù)據(jù)之余，含有零星的錯誤數(shù)據(jù)。這些少量的錯誤數(shù)據(jù)中其置信度總是較小的，而相應(yīng)受到干擾的大量數(shù)據(jù)，其CFD置信度總是接近1而又小于1。

于是提出使用兩個置信度閾值，conf_lo與conf_hi（conf_lo＜conf_hi），按挖掘得出的置信度conf，將CFD放在不同的集合：

1) 0＜conf ≤conf_lo,則將CFD放到可能含錯的CFD集，記為∑e。

2) conf_hi≤conf ≤1, 將受到干擾CFD放入到∑n。

3) conf=1, 是正確CFD,將它放入到∑中。

4) conf_lo＜conf ＜conf_hi，因?yàn)樗霈F(xiàn)的頻度足夠多，故不認(rèn)為是錯誤的CFD。

這樣的分類的好處是在使用基于SQL檢測違例時，我們只需要∑e與∑n構(gòu)建相應(yīng)的更泛化的模板表，而無須理會∑，而∑e與∑n的規(guī)模較于∑一般而言是十分小的，從而加快了違例檢測的效率。

插入記錄時，我們先檢測∑的規(guī)則，看是否符合其中的CFD，符合則直接加入數(shù)據(jù)集中，否則，檢測∑e、∑n，若在其中發(fā)現(xiàn)有相應(yīng)的CFD規(guī)則，則更改相應(yīng)規(guī)則的置信度，再將記錄插入數(shù)據(jù)集中，若插入記錄使得∑e、∑n中相應(yīng)規(guī)則的置信度conf有conf_lo＜con＜conf_hi，則將相應(yīng)的CFD規(guī)則從∑e、∑n中除去，因?yàn)檫_(dá)到相應(yīng)置信度后的規(guī)則極可能不是“錯誤”，只是可能相應(yīng)記錄順序問題，才使前面檢測出現(xiàn)“錯誤”的假象。刪除記錄時可以采取類似策略。

通過這種方法不僅可以高效地檢測違例記錄，而且在插入刪除記錄時，避免重新檢測帶來的時間空間的浪費(fèi)。

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

為分析基于 CFD的數(shù)據(jù)清洗方案的性能，使用 UCI中的adult[10]實(shí)驗(yàn)數(shù)據(jù)集進(jìn)行FD與CFD對規(guī)則挖掘的比較，實(shí)驗(yàn)數(shù)據(jù)集的基本信息，如表4所示：

表4 實(shí)驗(yàn)數(shù)據(jù)集的基本信息

在實(shí)驗(yàn)中，涉及到數(shù)據(jù)的記錄數(shù)目N是只取數(shù)據(jù)集的前N個記錄，涉及到M個屬性時，是只取它的前M個屬性。實(shí)驗(yàn)平臺：

處理器：Intel Pentium E21802.0GHz×2

操作系統(tǒng)：Windows XP SP3

內(nèi)存：1.0 GB 實(shí)現(xiàn)語言：Java

5.1 FD與CFD的比較：

對FD挖掘使用的是TANE算法，對CFD挖掘使用的是CTANE，后者是前者的擴(kuò)展，從挖掘原理與基本優(yōu)化策略來說都有一定的相似性，因而在一定程度上它們的性能差異可以反映出FD與CFD之間的某些差異性，故而是可比的。

實(shí)驗(yàn)得出結(jié)果，如圖1～圖4所示：

圖1 Tane與CTane對記錄數(shù)目(|r|)的敏感程度

圖2 Tane與CTane 對屬性數(shù)目(|R|)的敏感程度

圖3 Tane與CTane對支持度的敏感程度（1）

圖4 Tane與CTane對支持度的敏感程度（2）

從圖1、圖2 可看出，CTANE、TANE的時間復(fù)雜度大致均隨|R|呈指數(shù)級增長，隨|r|呈線性增長，但CTANE的增長系數(shù)明顯比TANE大，這是因?yàn)镃TANE在TANE的基礎(chǔ)上還要進(jìn)行語義分析工作，它處理的對象粒度比 TANE細(xì)。因而，相同的|R|、|r|的情況下，CTANE的時空代價肯定比TANE大。

從圖3、圖4 可看出，CTANE比TANE對支持度更敏感一些。利用支持度，一般對CFD挖掘的提速幅度比TANE大，但相對來說，精度的損失也較嚴(yán)重，因而使用支持度應(yīng)針對相應(yīng)的領(lǐng)域知識，謹(jǐn)慎選擇支持度閾值。

由圖4還可知，對相同的數(shù)據(jù)集，相同的實(shí)驗(yàn)實(shí)例情況下，CTANE挖掘得的CFD遠(yuǎn)較TANE得出的FD要多，故而也間接說明了CFD對數(shù)據(jù)集的描述遠(yuǎn)較FD要具體，從而更適合于數(shù)據(jù)清洗。

5.2 改進(jìn)前后的數(shù)據(jù)清洗方案進(jìn)行了對比。

如圖5所示：

圖5 改進(jìn)前后的基于SQL數(shù)據(jù)清洗方案對比

對引入支持度的改進(jìn)可以從上面的圖中已得出結(jié)論，在此不再重復(fù)。

對引入近似CFD的改進(jìn)，可從圖5得出結(jié)論，改進(jìn)后的清洗方案確實(shí)比原有的清洗方案，有了較大的性能上的改善。

6 總結(jié)

本文介紹了CFD的定義及其基本性質(zhì)，并說明了應(yīng)用CFD進(jìn)行數(shù)據(jù)清洗的基本步驟，同時還對已提出的基于CFD數(shù)據(jù)清洗方案的改進(jìn)，實(shí)驗(yàn)也表明，提出的改進(jìn)，基本可以達(dá)到一定程度的優(yōu)化。

[1]Eckerson, W.“Data quality and the bottom line,” [M]TDWI Report Series,Tech.Rep., 2002.

[2]曹建軍,刁興春,汪挺,王芳瀟.領(lǐng)域無關(guān)數(shù)據(jù)清洗研究綜述[J].計算機(jī)科學(xué), 2010,(05) .

[3]Erhard Rahm, Hong Hai Do.Data cleaning: problems and current approaches .[M]IEEE Data Engineering Bulletin,2000,23(4):3-13.

[4]王曰芬,章成志,張蓓蓓,吳婷婷.數(shù)據(jù)清洗研究綜述[J].現(xiàn)代圖書情報技術(shù), 2007,(12) .

[5]Bohannon P, Fan W, Geerts F, et al, Conditional functional dependencies for data cleaning[C]IEEE 23rd International Conference on Data Enginering, 2007: 746-755.

[6]Fan W,Geerts F,Li J,et al.Discovering conditional functional dependencies[C].IEEE25th International Conference on Data En-gineering.2009, :683-698 .

[7]Fan W,Geerts F,Jia X,et al.Conditional functional dependencies for capturing data inconsistencies[J].ACM Transactions on Data-base Systems, 2008, 33(2) :1-44 .

[8]Bohannon P, Fan W, Geerts F, et al, Conditional functional dependencies for data cleaning[C]IEEE 23rd International Conference on Data Enginering，2007：746-755.

[9]耿寅融,劉波.基于條件函數(shù)依賴的數(shù)據(jù)庫一致性檢測研究[J].計算機(jī)工程與應(yīng)用，2012.

[10]實(shí)驗(yàn)數(shù)據(jù)源：http://archive.ics.uci.edu/ml/datasets/Adult