條件函數依賴及其在領域無關數據清洗中的應用

周健昌，卜媛媛

0 引言

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

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

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

目前，對數據清洗的研究大多是領域相關的，不同的應用領域對其有不同的解釋，因而對數據清洗還沒有統一的定義。然而，數據清洗的目的是基本一致的[3]:檢測數據中存在的錯誤和不一致，剔除或改正它們，以提高數據的質量。數據清洗可按數據清洗對象、來源領域、產生原因、實現方式與范圍等不同指標有各種劃分，但數據清洗的基本任務是相同的，都是過濾或修改那些不符合要求的數據，其基本流程都是相同的[4]：數據分析與定義，識別錯誤記錄，修正錯誤。

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

1 條件函數依賴

函數依賴(Functional Dependency,FD)在數據庫及知識發現領域，都是一個重要的的概念，然而它對規則的挖掘而言卻不太充分，因為現實中的規則往往是帶有條件的，如[郵編]→[街道名]在整個世界范圍內是不成立的，但若前提是在英國，則它是成立的。

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

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

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

（2）{X→Y}是一個標準函數依賴；

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

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

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

2) 類似FD的Armstrong公理的合并律，設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的關系：若將模板中關于LHS的部分Tp[X]看作約束條件，關于RHS的部分看作結果，符合Tp[X]這個條件的記錄組成的一個關系實例 r′（r的一個子集），則CFD就是r′上標準的FD(此即上述CFD定義中“標準 FD”的含義)。

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

表1 信息學院學生信息表

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

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

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

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

定義2：模板間的泛化關系[5]

為給CFD賦予語義，我們為模板的變量值與常量值定義出一個關系符“≤”，稱泛化。

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

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

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

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

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

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

2 基于CFD的數據清洗步驟

基于CFD的數據清洗是一種基于規則的數據清洗方案，它的基本處理流程可歸納為：

1） 數據分析與定義：為檢測“臟數據”的類型，首先要對其進行詳細的數據分析，除人工檢查數據屬性外，還應通過分析程序自動取得關于數據質量的元數據。

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

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

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

5） 重復2～4項，直至數據質量達標為止。

3 基于CFD數據清洗的核心步驟

3.1 挖掘描述數據集的CFD集:

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

對于ψ:{ 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])是指在整個關系實例r中，在X上取值符合Tp[X]的記錄的頻數，

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

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

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

3.2 利用CFD檢測相似重復記錄

相似重復記錄的清洗，是數據清洗過程中最為關鍵的問題之一，也是研究最多的領域。解決相似重復記錄的問題，就是要對數據集合中的記錄進行對象識別，即根據記錄所含的各種描述信息來確定與之相應的現實實體。

文獻[7]與文獻[8]中提出了利用SQL查詢語句來實現檢測相似重復，其基本原理是:

若有ψ':{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語句來描述如下：

一般地，檢測分兩個步驟進行[9]:

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

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

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

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

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

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

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

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

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

4 我們的改進

4.1 為規則的挖掘引入支持度

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

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

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

由前面的敘述知，對于無錯的數據，挖掘得的CFD其置信度總是100%的，而對于含錯的數據基本上是在大量的正確數據之余，含有零星的錯誤數據。這些少量的錯誤數據中其置信度總是較小的，而相應受到干擾的大量數據，其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，因為它出現的頻度足夠多，故不認為是錯誤的CFD。

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

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

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

5 實驗分析

為分析基于 CFD的數據清洗方案的性能，使用 UCI中的adult[10]實驗數據集進行FD與CFD對規則挖掘的比較，實驗數據集的基本信息，如表4所示：

表4 實驗數據集的基本信息

在實驗中，涉及到數據的記錄數目N是只取數據集的前N個記錄，涉及到M個屬性時，是只取它的前M個屬性。實驗平臺：

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

操作系統：Windows XP SP3

內存：1.0 GB 實現語言：Java

5.1 FD與CFD的比較：

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

實驗得出結果，如圖1～圖4所示：

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

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

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

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

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

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

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

5.2 改進前后的數據清洗方案進行了對比。

如圖5所示：

圖5 改進前后的基于SQL數據清洗方案對比

對引入支持度的改進可以從上面的圖中已得出結論，在此不再重復。

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

6 總結

本文介紹了CFD的定義及其基本性質，并說明了應用CFD進行數據清洗的基本步驟，同時還對已提出的基于CFD數據清洗方案的改進，實驗也表明，提出的改進，基本可以達到一定程度的優化。

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

[2]曹建軍,刁興春,汪挺,王芳瀟.領域無關數據清洗研究綜述[J].計算機科學, 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]王曰芬,章成志,張蓓蓓,吳婷婷.數據清洗研究綜述[J].現代圖書情報技術, 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]耿寅融,劉波.基于條件函數依賴的數據庫一致性檢測研究[J].計算機工程與應用，2012.

[10]實驗數據源：http://archive.ics.uci.edu/ml/datasets/Adult