朱會娟,蔣同海,周 喜,程 力,趙 凡,馬 博

1.中國科學院新疆理化技術(shù)研究所 多語種信息技術(shù)研究室, 烏魯木齊 830011;2.中國科學院大學 計算機與控制學院, 北京 100049; 3.新疆民族語音語言信息處理重點實驗室, 烏魯木齊 830011)(*通信作者電子郵箱chengli@ms.xjb.ac.cn)

基于動態(tài)可配置規(guī)則的數(shù)據(jù)清洗方法

朱會娟1,2,3,蔣同海1,3,周 喜1,3,程 力1,3*,趙 凡1,3,馬 博1,3

1.中國科學院新疆理化技術(shù)研究所 多語種信息技術(shù)研究室, 烏魯木齊 830011;2.中國科學院大學 計算機與控制學院, 北京 100049; 3.新疆民族語音語言信息處理重點實驗室, 烏魯木齊 830011)(*通信作者電子郵箱chengli@ms.xjb.ac.cn)

針對傳統(tǒng)數(shù)據(jù)清洗方法通過硬編碼方法來實現(xiàn)業(yè)務(wù)邏輯而導致系統(tǒng)的可重用性、可擴展性與靈活性較差等問題，提出了一種基于動態(tài)可配置規(guī)則的數(shù)據(jù)清洗方法——DRDCM。該方法支持多種類型規(guī)則間的復(fù)雜邏輯運算,并支持多種臟數(shù)據(jù)修復(fù)行為,集數(shù)據(jù)檢測、數(shù)據(jù)修復(fù)與數(shù)據(jù)轉(zhuǎn)換于一體,具有跨領(lǐng)域、可重用、可配置、可擴展等特點。首先,對DRDCM方法中的數(shù)據(jù)檢測和數(shù)據(jù)修復(fù)的概念、實現(xiàn)步驟以及實現(xiàn)算法進行描述；其次,闡述了DRDCM方法中支持的多種規(guī)則類型以及規(guī)則配置；最后,對DRDCM方法進行實現(xiàn),并通過實際項目數(shù)據(jù)集驗證了該實現(xiàn)系統(tǒng)在臟數(shù)據(jù)修復(fù)中,丟棄修復(fù)行為具有很高的準確率,尤其是對需遵守法定編碼規(guī)則的屬性(例如身份證號碼)處理時其準確率可達100%。實驗結(jié)果表明,DRDCM實現(xiàn)系統(tǒng)可以將動態(tài)可配置規(guī)則無縫集成于多個數(shù)據(jù)源和多種不同應(yīng)用領(lǐng)域且該系統(tǒng)的性能并不會隨著規(guī)則條數(shù)增加而極速降低,這也進一步驗證了DRDCM方法在真實環(huán)境中的切實可行性。

大數(shù)據(jù);數(shù)據(jù)質(zhì)量;數(shù)據(jù)清洗;動態(tài)可配置規(guī)則;數(shù)據(jù)預(yù)處理

0 引言

對幾個著名的公司數(shù)據(jù)進行研究,其中有25%的重要數(shù)據(jù)是存在缺陷的[1],由它帶來的經(jīng)濟損失也是驚人的,據(jù)統(tǒng)計,“臟數(shù)據(jù)”導致美國商業(yè)每年約損失6 000億美元[2]。在大數(shù)據(jù)時代,數(shù)據(jù)預(yù)處理已經(jīng)成為一個重要的研究課題,吸引了越來越多學術(shù)界和工業(yè)界研究人員的注意,根據(jù)調(diào)查顯示,數(shù)據(jù)質(zhì)量工具的市場正以每年17%的速度增長,遠遠高出IT行業(yè)中其他分支平均7%的增長速度[3]。

典型的數(shù)據(jù)預(yù)處理過程如圖1所示,左邊的方框表示原始數(shù)據(jù)集,其中包括結(jié)構(gòu)化數(shù)據(jù)、半結(jié)構(gòu)化數(shù)據(jù)和非結(jié)構(gòu)化數(shù)據(jù)。中間的方框表示數(shù)據(jù)預(yù)處理的兩個主要任務(wù)即數(shù)據(jù)轉(zhuǎn)換和數(shù)據(jù)清洗。數(shù)據(jù)轉(zhuǎn)換(Data Transformation)是指從原始數(shù)據(jù)中提取數(shù)據(jù),并將其轉(zhuǎn)換成適合進一步分析的數(shù)據(jù)格式的過程。數(shù)據(jù)清洗(Data Cleaning、 Data Cleansing或者Data Scrubbing)主要用來檢測數(shù)據(jù)中存在的異常數(shù)據(jù)(例如錯誤、缺失、不一致等)[4]并去除或修正它們,最終目的就是提高數(shù)據(jù)的質(zhì)量[5-6]。

圖1 典型的數(shù)據(jù)預(yù)處理過程

在過去的十幾年中,數(shù)據(jù)清洗領(lǐng)域得以飛速發(fā)展,衍生出了許多數(shù)據(jù)清洗方法和系統(tǒng),基于規(guī)則的數(shù)據(jù)清洗方法因為其自身的簡單易實現(xiàn)并且清洗效果顯著等特點使其在數(shù)據(jù)清洗領(lǐng)域一直扮演著一個重要的角色[7-8]。文獻[9]對數(shù)據(jù)質(zhì)量問題作了詳細的分類和分析,并以判定樹的形式給出了檢測方法,從而有力地支持了基于規(guī)則的數(shù)據(jù)清洗技術(shù)的現(xiàn)實可行性。本文對現(xiàn)有的一些基于規(guī)則的數(shù)據(jù)清洗方法,例如NADEEF(A Commodity Data Cleaning System)、AzszpClean (A Rule-based Solution to Data Cleaning)等進行了研究并概括如表1。

表1 基于規(guī)則的數(shù)據(jù)清洗方案的比較

目前大多數(shù)的數(shù)據(jù)清洗工具或框架都是針對某些特定領(lǐng)域,如果用戶需引入新的規(guī)則或是復(fù)用其他領(lǐng)域的一些規(guī)則(例如檢查身份證號的規(guī)則在很多領(lǐng)域是通用的)則十分困難,而且擴展現(xiàn)有解決方案或部署這些方案到自己系統(tǒng)中也十分艱巨[13,19-21];目前還有一些清洗工具的臟數(shù)據(jù)檢測和修復(fù)借助硬編碼來實現(xiàn)[5],這會導致系統(tǒng)的可擴展性和靈活性較差,當清洗規(guī)則發(fā)生變化時清洗部分的代碼需要重新實現(xiàn),并且硬編碼方法對數(shù)據(jù)清洗的描述性較弱，在實現(xiàn)復(fù)雜邏輯方面的數(shù)據(jù)清洗時會比較困難,而且用戶的理解度和接受度較低;另外,有一些清洗工具是借助人工判斷來完成臟數(shù)據(jù)檢測和修復(fù)[22],該類方法在數(shù)據(jù)量較小時具有高準確性的優(yōu)勢,但在數(shù)據(jù)量龐大且多源異構(gòu)的情況下劣勢會愈發(fā)明顯。

1 DRDCM方法

基于以上問題,本文提出了一種基于動態(tài)可配置規(guī)則的數(shù)據(jù)清洗方法(Dynamic Rule-based Data Cleaning Method, DRDCM),這是一種跨領(lǐng)域的、可重用的、可配置的將臟數(shù)據(jù)檢查與臟數(shù)據(jù)修復(fù)以及數(shù)據(jù)轉(zhuǎn)換三者融為一體的新方法。該方法支持多種規(guī)則類型以及規(guī)則間的復(fù)雜邏輯運算;支持三種臟數(shù)據(jù)修復(fù)行為:保留(RETAIN)、丟棄(DISCARD)和回填(REFILL);支持用戶在運行時增加、刪除或修改規(guī)則等。

1.1 DRDCM相關(guān)定義

圖2為DRDCM的數(shù)據(jù)清洗過程。

圖2 DRDCM的數(shù)據(jù)清洗過程

首先,用戶對原始數(shù)據(jù)分析提取規(guī)則,在DRDCM支持三種類型規(guī)則,分別是:DROOLS(JBoss Rules)規(guī)則、REGEX(Regular Expression)規(guī)則和FUN(Function)規(guī)則。在規(guī)則配置階段實現(xiàn)規(guī)則與屬性、表以及領(lǐng)域的綁定。其中規(guī)則執(zhí)行包括兩部分即數(shù)據(jù)檢測以及根據(jù)檢測結(jié)果進行數(shù)據(jù)修復(fù)。DRDCM中涉及到的相關(guān)定義如下:

定義1 數(shù)據(jù)清洗(Data Cleaning)。數(shù)據(jù)清洗是把原始輸入數(shù)據(jù)通過一系列的數(shù)據(jù)檢測和數(shù)據(jù)修復(fù)后轉(zhuǎn)換為干凈數(shù)據(jù)的過程,可以形式化表示為:

其中：R代表原始數(shù)據(jù);D代表干凈數(shù)據(jù)。

定義2 數(shù)據(jù)檢測(Data Check)。用來檢測數(shù)據(jù)是否符合既定知識的過程,可用謂詞函數(shù)表示為CHECKCOND:D →{T, F}:

CHECKCOND(d)=T表示待檢測數(shù)據(jù)項d是符合清洗規(guī)則的數(shù)據(jù),即為“干凈數(shù)據(jù)”,直接存入干凈數(shù)據(jù)庫;

CHECKCOND(d)=F表示待檢測數(shù)據(jù)項d是不符合清洗規(guī)則的數(shù)據(jù),即為“臟數(shù)據(jù)”,需要進一步作數(shù)據(jù)修復(fù)(見定義3);

定義3 數(shù)據(jù)修復(fù)(Data Revise)。根據(jù)數(shù)據(jù)檢測的結(jié)果,如果為F則需要對原數(shù)據(jù)進行修改,DRDCM支持三種修改行為:保留(RETAIN)、丟棄(DISCARD)和回填(REFILL)。

定義4 DROOLS規(guī)則。抽取的規(guī)則可以通過Drools語法[23]清晰表達的,均定義為DROOLS規(guī)則類型,形如“rule 〈name〉 attributes; when 〈LHS〉; then 〈RHS〉; end”。

定義5 REGEX規(guī)則。抽取的規(guī)則可以通過Java正則表達式[24]清晰表達的,均定義為REGEX規(guī)則類型,例如“18位身份證號且支持以X結(jié)尾”,可以定義為正則表達式“(^[1-9]([0-9]{16}|[0-9]{13})[xX0-9]＄)”。

定義6 FUN規(guī)則。抽取的規(guī)則通過DROOLS規(guī)則和REGEX規(guī)則均無法表達的,可以定義為FUN規(guī)則,例如一些時間函數(shù)、轉(zhuǎn)換函數(shù)和數(shù)學函數(shù)等。

定義7 清洗規(guī)則(Clean Rule)。本文提出的清洗規(guī)則可用四元組表示為:

CleanRule ::=〈Number, Rule Type, Data Check, Data Revise〉

其中：Number是由規(guī)則組號和規(guī)則號組成；Rule Type見定義4～6；Data Check見定義2；Data Revise見定義3。

1.2 DRDCM方法的組成

DRDCM方法主要包括如下幾個組成部分:

規(guī)則模板 即規(guī)則實體定義,方便用戶閱讀、定義以及修改規(guī)則。

規(guī)則庫 集中保存跨領(lǐng)域的所有規(guī)則,以規(guī)則組號和規(guī)則號組合為唯一標識,以便進行規(guī)則的管理與重用。

規(guī)則配置與存儲 處理在實際清洗過程中規(guī)則實體與屬性、表、領(lǐng)域等的匹配關(guān)系,支持復(fù)雜邏輯描述表達式如:((規(guī)則1‖規(guī)則2)&& !規(guī)則3),支持二元組〈屬性名,規(guī)則表達式〉、三元組〈表名,屬性名,規(guī)則表達式〉和四元組〈領(lǐng)域名,表名,屬性名,規(guī)則表達式〉等。

規(guī)則引擎 是規(guī)則的運行環(huán)境,用來編譯和執(zhí)行規(guī)則。

數(shù)據(jù)清洗反饋類 負責將清洗結(jié)果和存在問題反饋給用戶。

1.3 DRDCM方法的特點

相較于其他基于規(guī)則的數(shù)據(jù)清洗方法,DRDCM方法具備以下幾個特點:

1)DRDCM采用低耦合的設(shè)計模式,因此將業(yè)務(wù)規(guī)則與業(yè)務(wù)系統(tǒng)分離。

2)DRDCM采用規(guī)則的動態(tài)編譯方法,不僅具備堅實的編譯理論基礎(chǔ),而且可以方便地在線修改和增刪規(guī)則,方便應(yīng)對特殊狀況,比如用戶一開始沒有考慮到引入規(guī)則或是規(guī)則引入有誤或引入規(guī)則不足以表達實際需求等情況。

3)DRDCM方法中規(guī)則的定義遵循最小化原則(即規(guī)則不可再被拆分為其他子規(guī)則),給數(shù)據(jù)清洗的復(fù)雜邏輯描述以及多領(lǐng)域規(guī)則重用打下基礎(chǔ)。

4)DRDCM方法中將數(shù)據(jù)轉(zhuǎn)換與規(guī)則配置相結(jié)合,使單源數(shù)據(jù)或多源數(shù)據(jù)在集成的同時,完成數(shù)據(jù)清洗和修復(fù),避免數(shù)據(jù)多次導入導出。

5)DRDCM支持三種規(guī)則類型,避免單一規(guī)則類型的局限性,能夠較全面地描述真實數(shù)據(jù)集中可以提取的規(guī)則。

6)DRDCM實現(xiàn)一種新的規(guī)則引擎,可以支持復(fù)雜的邏輯表達式和不同層次的規(guī)則配置,如屬性、表和領(lǐng)域。

1.4 DRDCM方法的工作模式

DRDCM方法的工作模式如下:首先,對原始數(shù)據(jù)集進行分析并提取有效規(guī)則,通過規(guī)則定義界面將這些規(guī)則錄入并存儲進規(guī)則庫中,其中規(guī)則的定義必須符合規(guī)則模板。接下來是數(shù)據(jù)轉(zhuǎn)換,周傲英教授在文獻[25]中闡述了數(shù)據(jù)轉(zhuǎn)換的重要性,對多源異構(gòu)數(shù)據(jù)進行分析,從非結(jié)構(gòu)化、半結(jié)構(gòu)化的源數(shù)據(jù)中抽取結(jié)構(gòu)化信息來定義XML模型從而完成數(shù)據(jù)轉(zhuǎn)換。在DRDCM方法中,是在數(shù)據(jù)轉(zhuǎn)換的過程中完成規(guī)則配置,規(guī)則配置形如:,其中1_4、1_5和1_6均標識規(guī)則庫中的唯一一條規(guī)則。最后是規(guī)則的執(zhí)行,DRDCM提供的規(guī)則執(zhí)行核心模塊根據(jù)規(guī)則配置將所需規(guī)則從規(guī)則庫中取出放入規(guī)則隊列,規(guī)則引擎會解析對應(yīng)的規(guī)則,根據(jù)規(guī)則類型編譯和執(zhí)行對應(yīng)規(guī)則,規(guī)則的執(zhí)行包括數(shù)據(jù)檢測和根據(jù)檢測結(jié)果執(zhí)行數(shù)據(jù)修復(fù)兩部分。

1.5 算法設(shè)計

DRDCM支持三種不同類型的數(shù)據(jù)清洗規(guī)則,如何把這些規(guī)則行之有效地部署到實際應(yīng)用中是其中一個關(guān)鍵。因此需要設(shè)計出一套切實有效的算法來自動地進行數(shù)據(jù)清洗。

算法1 數(shù)據(jù)清洗算法。

Input: DRL:待清洗記錄集； AttributeInfoBeanMap: 存儲記錄集中屬性的元數(shù)據(jù)。 // 類型為Map

Output: CleanRL: 干凈的記錄集。

1)

CleanRL ←{};

//存儲干凈的記錄集,初始化為空

2)

ruleExp="";

//初始化規(guī)則表達式

3)

ruleQuene←new LinkedList<>();

//初始化規(guī)則隊列為空,用于存儲規(guī)則實體

4)

checkValueMap← new Map();

//用于存儲規(guī)則的檢查結(jié)果,key值為規(guī)則編號

5)

For each record in DRL Do

6)

cleanRecord←record;

//用于存儲修復(fù)后的干凈記錄

7)

For each attribute∈ record Do

8)

If (AttributeInfoBeanMap.get(attribute) !=null)

9)

ruleExp ← 讀取對應(yīng)AttributeInfoBean中的規(guī)則表達式;

//形如"1_4 or 1_5 or 1_6"

10)

ruleQuene← ruleExp中所有規(guī)則號對應(yīng)的規(guī)則實體ruleEntity;

11)

For each ruleEntity in ruleQuene Do

12)

ruleType ← ruleEntity.getRuleType;

13)

If (ruleType=="DROOLS")

14)

checkValue← Call DroolsSemErr;

15)

Else if(ruleType=="REGEX")

16)

checkValue←Call RegextSemErr;

17)

Else If(ruleType=="FUN")

18)

checkValue ←Call FunSemErr;

19)

checkValueMap.put(ruleNumber, checkValue);

20)

expCheckValue←runLogicalExp(ruleExp, checkValueMap)

21)

if (expCheckValue== false)

22)

cleanRecord←call 數(shù)據(jù)修復(fù)算法更新cleanRecord;

23)

If (cleanRecord==null)

24)

break;

//退出循環(huán)

25)

End For each attribute;

26)

If (cleanRecord!=null)

27)

CleanRL.add(cleanRecord);

28)

End For each record;

29)

return CleanRL;

在算法2中,RetainNumMap為Map類型,用于存儲屬性名以及該屬性中不符合規(guī)則并且沒有合適修復(fù)策略的屬性值個數(shù)。

算法2 數(shù)據(jù)修復(fù)算法。

Input: Record: 待修復(fù)的記錄; AtrributeName: 待修復(fù)的屬性名; Action: 修復(fù)動作; RetainNumMap:

//Map

Output: ModifiedRecord:被修復(fù)后的記錄。

1)

modifiedRecord ← Record;

2)

if (Action==DISCARD)

3)

modifiedRecord=null;

4)

If (Action==RETAIN)

5)

更新RetainNumMap;

6)

If (Action==REFILL)

7)

//根據(jù)屬性所屬類型選擇回填值;

8)

If (AtrributeName是枚舉型屬性)

9)

ModifiedRecord←ModifiedRecord.setAttribute (AtrributeName, MaxFreqValue);

// MaxFreqValue為該屬性中出現(xiàn)頻率最高的屬性值

10)

If (AtrributeName是數(shù)值型屬性)

11) ModifiedRecord←ModifiedRecord.setAttribute (AtrributeName, MeanValue);

// MeanValue為該屬性值的樣本均值

12)

If (AtrributeName是日期型屬性)

13)

轉(zhuǎn)換日期型格式,如果為空值參考字符串型處理方法;

14)

If(AtrributeName是字符串型屬性)

15)

尋找重復(fù)記錄或最鄰近記錄對應(yīng)的屬性值作為填充值;

16)

return ModifiedRecord;

表2 元表(部分)

2 DRDCM參考實現(xiàn)系統(tǒng)

2.1 DRDCM系統(tǒng)架構(gòu)

DRDCM系統(tǒng)的總體架構(gòu)如圖3所示,主要有數(shù)據(jù)導入模塊,它給結(jié)構(gòu)化、非結(jié)構(gòu)化數(shù)據(jù)以及半結(jié)構(gòu)化數(shù)據(jù)的導入提供了一個統(tǒng)一的接口,這樣就可以實現(xiàn)綜合的管理,提高整體的使用效率,減少今后維護的成本;數(shù)據(jù)轉(zhuǎn)換與規(guī)則配置模塊,該模塊的主要任務(wù)是將結(jié)構(gòu)化、非結(jié)構(gòu)化以及半結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)換為方便后期進行數(shù)據(jù)分析的統(tǒng)一格式,并通過該模塊將規(guī)則與屬性、表以及領(lǐng)域進行匹配;規(guī)則收集模塊(包括規(guī)則模板、規(guī)則定義界面和規(guī)則庫等),該模塊主要功能是從原始數(shù)據(jù)中抽取規(guī)則并進行定義和存儲規(guī)則;規(guī)則執(zhí)行核心模塊(包括規(guī)則引擎、規(guī)則編譯、數(shù)據(jù)檢測和數(shù)據(jù)修復(fù)等),主要功能是執(zhí)行數(shù)據(jù)清洗規(guī)則以及對原始數(shù)據(jù)進行修正以獲取干凈數(shù)據(jù);數(shù)據(jù)輸出模塊(包括清洗反饋和干凈數(shù)據(jù)存儲)。

2.2 清洗規(guī)則

清洗規(guī)則可以表示為:

RULE(n, t, c, o, v)

n: 規(guī)則的名稱(字母、數(shù)字和下劃線組成);

t:規(guī)則的類型(t∈{DROOLS, FUN, REGEX});

c:清洗檢測(c∈RegexSemErr, DroolsSemErr, FunSemErr);

o:規(guī)則的操作符(o∈{ BELONGTO, NOTBELONGTO, CONTAINS, NOTCONTAINS, MATCHS, NOTMATCHS, GREATER, LESS, EQUAL, NOTEQUAL, INNER, OUTSIDE, SATISFY, NOT SATISFY});

v:標準值或標準值域。

BELONGTO與NOTBELONGTO描述個體與集合的關(guān)系,例如: 1∈{1, 2, 3}、4?{1, 2, 3};CONTAINS 與 NOTCONTAINS描述集合與集合的關(guān)系,例如:{1}?{1, 5, 6}、{1}?{4, 5, 6};GREATER、GREATEREQ、LESS、LESSEQ、EQUAL、 NOTEQUAL、 INNER、OUTSIDE分別表示大于、大于等于、小于、小于等于、等于、不等于、在區(qū)間內(nèi)和在區(qū)間外,其中INNER、OUTSIDE可以通過GREATER(GREATEREQ)與LESS(LESSEQ)的“∧”運算實現(xiàn)。

規(guī)則操作符的定義：

BELONGTO ?∈

NOTBELONGTO ??

CONTAINS ??

NOTCONTAINS ??

GREATER ?>

GREATEREQ ?≥

LESS ?<

LESSEQ ?≤

EQUAL ?=

NOTEQUAL ?≠

圖3 DRDCM參考實現(xiàn)系統(tǒng)的總體架構(gòu)

2.3 規(guī)則引擎

DRDCM參考實現(xiàn)系統(tǒng)的規(guī)則引擎分三個步驟:

步驟1 解析規(guī)則配置文件,其中配置文件涉及到的數(shù)據(jù)轉(zhuǎn)換元表和規(guī)則表達式元表,如表2所示。

步驟2 在將原數(shù)據(jù)進行數(shù)據(jù)轉(zhuǎn)換時讀取元數(shù)據(jù)模型中的規(guī)則表達式Exp,并根據(jù)規(guī)則類型調(diào)用對應(yīng)的規(guī)則執(zhí)行文件,本文有三種規(guī)則類型,對應(yīng)的規(guī)則執(zhí)行文件提供的接口分別為:

RegextSemErr(Object d1, ExpEntity e1)

DroolsSemErr(Object d1, ExpEntity e1)

FunSemErr(Object d1, ExpEntity e1)

其中:d1為待清洗數(shù)據(jù)；e1表示規(guī)則實體。這三個接口用來完成每條規(guī)則的數(shù)據(jù)檢測。

步驟3 計算規(guī)則表達式的值,如果為F則調(diào)用數(shù)據(jù)修復(fù)模塊進行數(shù)據(jù)修復(fù),最終存入干凈數(shù)據(jù)庫。

2.4 規(guī)則配置

規(guī)則是從一些領(lǐng)域知識或是復(fù)雜商業(yè)邏輯中提取出來的,不同領(lǐng)域的原始數(shù)據(jù)集中會存在一些共有的信息,例如對人的信息采集,包括人的性別、身份證號碼、族別、出生日期、年齡等信息,而從這些基本信息中可以抽取到的規(guī)則有:性別只有男/女,身份證號碼18位支持X字母結(jié)尾,民族只能是56個民族中的其中一個(中國公民),出生日期的日期格式,等等。在DRDCM系統(tǒng)中,規(guī)則從領(lǐng)域知識中提取但又不依賴于領(lǐng)域,規(guī)則庫中的規(guī)則可以跨領(lǐng)域進行重用。

DRDCM系統(tǒng)根據(jù)規(guī)則的關(guān)聯(lián)號把規(guī)則分為若干個分組,并以〈規(guī)則組號-規(guī)則號〉為索引來匹配和執(zhí)行規(guī)則,大大降低了時間復(fù)雜度。基于這個原則進行規(guī)則配置,當用戶修改規(guī)則時,規(guī)則引擎無需作任何改動;當用戶增加或刪除規(guī)則時,僅需要改動規(guī)則配置模塊,規(guī)則引擎和其他模塊無需作任何改動,從而極大提高了系統(tǒng)的重用性、擴展性和靈活性。

規(guī)則配置中涉及到規(guī)則表達式用二元組表示為:

RL=〈RN, LC〉

RN是規(guī)則組號-規(guī)則號,用來唯一標識一個規(guī)則。LC是邏輯連接詞,用“not”代表“(否定)”、用“and” 代表“∧(合取)”、用“or”代表“∨(析取)”、用“ifThen”代表“→(蘊涵)”、用“EQ”代表“?(等價)”。

規(guī)則配置支持如下幾種格式:

1)Expc::=〈A, RL〉,用來表達單個屬性下的規(guī)則約束;

2)Expc::=〈T, A, RL, LC〉,用來表達以表為單位的規(guī)則約束;

3)Expc::=〈D,T, A, RL, LC〉,用來表示不同領(lǐng)域下的規(guī)則約束。

其中：A代表屬性名；T代表表名；LC是邏輯連接詞；D代表領(lǐng)域名。

在XML規(guī)則配置文件中,Expc::=〈A, RL〉格式如下所示:

3 實際應(yīng)用

面向公安、國安等地區(qū)大數(shù)據(jù)分析的需求,結(jié)合工信部物聯(lián)網(wǎng)發(fā)展專項的“新疆電梯安全動態(tài)監(jiān)管物聯(lián)網(wǎng)系統(tǒng)研發(fā)與應(yīng)用”的數(shù)據(jù),以及國家發(fā)改委物聯(lián)網(wǎng)重大專項的“基于物聯(lián)網(wǎng)技術(shù)的車載氣瓶電子監(jiān)管系統(tǒng)及產(chǎn)業(yè)化”的數(shù)據(jù)。采用DRDCM系統(tǒng)對這些原始數(shù)據(jù)進行清洗,從而保障數(shù)據(jù)檢索、數(shù)據(jù)分析以及分析結(jié)果展示的準確性。

在實驗部分通過以下三個方面來展示該系統(tǒng)的性能:1)給出該系統(tǒng)的輸入輸出數(shù)據(jù);2)給出該系統(tǒng)數(shù)據(jù)清洗的準確性;3)給出該系統(tǒng)數(shù)據(jù)清洗的效率。

3.1 數(shù)據(jù)采集

該數(shù)據(jù)集共計10.7 GB,時間跨度為2016年1月到2016年5月。數(shù)據(jù)采集方式有三種：第一種是通過具備NFC功能的智能手機或其他智能手持設(shè)備獲?。坏诙N是通過人工錄入；第三種是和其他系統(tǒng)對接來導入數(shù)據(jù)。

“新疆電梯安全動態(tài)監(jiān)管物聯(lián)網(wǎng)系統(tǒng)研發(fā)與應(yīng)用” 和“基于物聯(lián)網(wǎng)技術(shù)的車載氣瓶電子監(jiān)管系統(tǒng)及產(chǎn)業(yè)化” 兩個項目中都引入了近距離無線通信技術(shù)(Near Field Communication, NFC),它是工作在13.56 MHz頻率,有效距離在20 cm內(nèi)。事實上,操作距離以及嵌入手機或其他手持設(shè)備的NFC設(shè)備自身的靈敏度都會影響到從電子標簽中讀取數(shù)據(jù)。第二種采集方法中,排除紙質(zhì)材料本身的完整性,在人工錄入時難免會存在錯錄或少錄的情況。在第三種采集方法中,數(shù)據(jù)來自不同系統(tǒng),因此數(shù)據(jù)具有異構(gòu)、多源、分布式、時間跨度大等特點,這些數(shù)據(jù)中不可避免地會存在著一些粗糙的、不合時宜的數(shù)據(jù)。

3.2 評價標準

為了驗證本文方法在丟棄記錄與回填記錄的有效性,本文引入準確率Accuracy來評定,其定義如下:

(1)

其中:TP是真正例的個數(shù),即不符合清洗規(guī)則且被正確地執(zhí)行了丟棄或回填動作的屬性值個數(shù);TN是真負例的個數(shù),即屬性值本身為干凈數(shù)據(jù)且沒有被執(zhí)行任何修復(fù)動作的屬性值個數(shù)；FP是假正例的個數(shù)；FN為假負例的個數(shù)。TP+TN+FP+FN為樣本總數(shù)?？偠灾?準確率就是被正確處理的樣本數(shù)除以所有的樣本數(shù),通常來說,準確率越高,則處理效果越好。

3.3 實驗結(jié)果以及分析

實驗1 限于篇幅和所屬項目數(shù)據(jù)本身的保密性,本文僅給出其中一個數(shù)據(jù)表的部分信息(如表3中的輸入數(shù)據(jù)所示)作數(shù)據(jù)清洗描述,該測試數(shù)據(jù)來源是經(jīng)數(shù)據(jù)轉(zhuǎn)換后的結(jié)構(gòu)化數(shù)據(jù)。

表3 測試數(shù)據(jù)(部分)

表1中:“idType”屬性中值1代表“idNum”中存儲的是“身份證”, 值2表示的是“組織機構(gòu)”,其中組織機構(gòu)是由8位數(shù)字組成,值3表示的是“護照”。另外因為涉及隱私問題,表3中所列數(shù)據(jù)中的身份證號碼、護照號和姓名都經(jīng)過了替換處理,并且某些數(shù)字用“*”號代替。其中idNum的規(guī)則配置見2.4節(jié)中的示例({"constraint":"1_4or1_5or1_6","ruleAction":"DISCARD"})。

因篇幅原因,只列舉在規(guī)則配置文件中的兩條規(guī)則作為示例。

ID_CARD_NUM 1_4 REGEX SATISFY (^[1-9]([0-9]{16}|[0-9]{13})[xX0-9]＄)

REPLACE_GENDER 3_1 FUN BELONGTO M:男,F:女

規(guī)則1_4是正則表達式類型規(guī)則,用于檢測身份證號碼的合法性。規(guī)則3_1是函數(shù)類型規(guī)則,它的作用是將gender屬性中的“F”值替換為“女”、“M”替換為“男”。在規(guī)則配置時,因為idNum是該表的主鍵,如果idNum不符合清洗規(guī)則表達式，則表示該條記錄為無效記錄予以丟棄。

經(jīng)DRDCM系統(tǒng)進行清洗后,表3中輸入數(shù)據(jù)部分的第一條記錄中ethnic屬性值被回填為“漢”另外,第2條和第4條因idNum不符合清洗規(guī)則表達式所以予以丟棄,具體清洗結(jié)果如表3中輸出數(shù)據(jù)部分所示。

如果使用硬編碼方法實現(xiàn)就需要冗長的if…else語句實現(xiàn),硬編碼方式不僅容易引入錯誤,而且修改起來相當困難,對不同的應(yīng)用難以復(fù)用。而DRDCM方法僅需幾條規(guī)則即可,在代碼實現(xiàn)部分無需任何改動,極大地方便和簡化了數(shù)據(jù)清洗和修復(fù)的流程。

實驗2 每次隨機抽取記錄,重復(fù)20次,統(tǒng)計出有多少條記錄被拋棄、多少屬性值被回填以及它們的準確率。在本次實驗中,用到的規(guī)則數(shù)量分別是5、10和20。數(shù)據(jù)清洗的統(tǒng)計結(jié)果如表4所示,實驗結(jié)果表明丟棄記錄的準確率是可以接受的,但是回填記錄的準確率有待提高,這在本項目目前正在開發(fā)的數(shù)據(jù)清洗和數(shù)據(jù)融合系統(tǒng)中會進一步完善。

表4 DRDCM系統(tǒng)的準確率

實驗3 對DRDCM的清洗效率進行了實驗,并與硬編碼(HardCoding,HardCode)方法作了對比。在圖4中,橫坐標表示實驗中所使用的規(guī)則條數(shù),縱坐標表示在對應(yīng)的規(guī)則條數(shù)上執(zhí)行10條、100條、1 000條和10 000條記錄所消耗的時間。從圖4可知,隨著規(guī)則數(shù)量的增加,性能緩慢下降,說明DRDCM系統(tǒng)的性能和規(guī)則條數(shù)的相關(guān)度不是很大。

圖4 DRDCM系統(tǒng)的效率

在圖5中給出了DRDCM與HardCode性能的比較。由圖5可知,在規(guī)則數(shù)為5時DRDCM系統(tǒng)在性能上要略差于HardCode方法;但隨著規(guī)則數(shù)增長,當規(guī)則數(shù)為20時和40時,DRDCM系統(tǒng)和HardCode的性能差距越來越小。另外,規(guī)則數(shù)量的增加,對HardCode和DRDCM系統(tǒng)的影響基本趨于一致。雖然較之HardCode,在性能上DRDCM系統(tǒng)的優(yōu)勢并不明顯,但是DRDCM可以使用形式化語言描述規(guī)則的復(fù)雜邏輯運算,且易于用戶理解和接受;DRDCM把業(yè)務(wù)規(guī)則和業(yè)務(wù)系統(tǒng)進行分離,也更方便用戶的擴展與修改,以及一些突發(fā)情況的處理;另外,DRDCM方法支持規(guī)則的跨領(lǐng)域重用、配置等。

圖5 DRDCM與HardCode的性能比較

4 結(jié)語

本文通過對現(xiàn)有數(shù)據(jù)清洗方法特別是基于規(guī)則的數(shù)據(jù)清洗方法進行詳細研究后,提出了一種新的基于動態(tài)可配置規(guī)則的數(shù)據(jù)清洗方法DRDCM,將規(guī)則配置、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)檢測以及數(shù)據(jù)修復(fù)融為一體;支持跨領(lǐng)域多源數(shù)據(jù)的規(guī)則重用;DRDCM方法支持三種類型的規(guī)則并提供對應(yīng)接口實現(xiàn),可以避免單一規(guī)則對源數(shù)據(jù)特征描述時的局限性。另外,本文對DRDCM方法提出一種參考實現(xiàn)系統(tǒng),它支持規(guī)則的動態(tài)編譯,利用該系統(tǒng)用戶可以方便地對規(guī)則進行閱讀、抽取、新增、修改和刪除等操作,并且支持規(guī)則的復(fù)雜邏輯描述等,綜合上述改進使該系統(tǒng)具備靈活性和擴展性。該系統(tǒng)已部署在工信部物聯(lián)網(wǎng)發(fā)展專項的“新疆電梯安全動態(tài)監(jiān)管物聯(lián)網(wǎng)系統(tǒng)研發(fā)與應(yīng)用”和國家發(fā)改委物聯(lián)網(wǎng)重大專項的“基于物聯(lián)網(wǎng)技術(shù)的車載氣瓶電子監(jiān)管系統(tǒng)及產(chǎn)業(yè)化”項目中,在這些項目中的實際運行情況以及獲取到的真實數(shù)據(jù)集進一步驗證了該方法在現(xiàn)實場景下的可行性。

)

[1]SWARTZN.Gartnerwarnsfirmsof“dirtydata” [J].InformationManagementJournal, 2007, 41(3): 6-7.

[2]ECKERSONWW.Dataqualityandthebottomline:achievingbusinesssuccessthroughacommitmenttohighqualitydata[EB/OL]. [2016- 03- 10].http://download.101com.com/pub/tdwi/Files/DQReport.pdf.

[3]GRAHAMC.Forecast:dataqualitytools,worldwide, 2006-2011 [EB/OL]. [2016- 03- 10].https://www.gartner.com/doc/507207/forecast-data-quality-tools-worldwide.

[4] 覃遠翔, 段亮, 岳昆. 基于信息熵的不確定性數(shù)據(jù)清理方法[J]. 計算機應(yīng)用, 2013, 33(9): 2490-2492.(QINYX,DUANL,YUEK.Approachforcleaninguncertaindatabasedoninformationentropytheory[J].JournalofComputerApplications, 2013, 33(9):2490-2492.)

[5]RAHME,DOHH.Datacleaning:problemsandcurrentapproaches[J].IEEEDataEngineeringBulletin, 2000, 23(4): 3-13.

[6] 楊明花, 古志民. 基于興趣特征的WUM數(shù)據(jù)預(yù)處理方法[J]. 計算機應(yīng)用, 2006, 26(10): 133-134.(YANGMH,GUZM.DatapreprocessingmethodbasedoncharacteristicofinterestsforWUM[J].JournalofComputerApplications, 2006, 26(10):2393-2388.)

[7]GALHARDASH,FLORESCUD,SHASHAD,etal.Declarativedatacleaning:language,model,andalgorithms[C]//VLDB2001:Proceedingsofthe27thInternationalConferenceonVeryLargeDataBases.SanFrancisco:MorganKaufmannPublishers, 2001: 371-380.

[8]VOLKOVSM,CHIANGF,SZLICHTAJ,etal.Continuousdatacleaning[C]//Proceedingsofthe2014IEEE30thInternationalConferenceonDataEngineering.Piscataway,NJ:IEEE, 2014: 244-255.

[9]OLIVEIRAP,RODRIGUESF,HENRIQUESP,etal.Ataxonomyofdataqualityproblems[EB/OL]. [2016- 03- 10].https://www.researchgate.net/profile/Helena_Galhardas/publication/250693546_A_Taxonomy_of_Data_Quality_Problems/links/02e7e5347984 84567c000000.pdf.

[10]EBAIDA,ELMAGARMIDA,ILYASIF,etal.NADEEF:ageneralizeddatacleaningsystem[J].ProceedingsoftheVLDBEndowment, 2013, 6(12): 1218-1221.

[11]DALLACHIESAM,EBAIDA,ELDAWYA,etal.NADEEF:acommoditydatacleaningsystem[C]//Proceedingsofthe2013ACMSIGMODInternationalConferenceonManagementofData.NewYork:ACM, 2013: 541-552.

[12] 李俊奎, 王元珍, 李專.AzszpClean: 一種基于規(guī)則的數(shù)據(jù)清洗方案[J]. 山東大學學報(理學版), 2007, 42(9):71-74.(LIJK,WANGYZ,LIZ.AzszpClean:arule-basedsolutiontodatacleaning[J].JournalofShandongUniversity(NaturalScience), 2007, 42(9):71-74.)

[13]BOHANNONP,FANW,FLASTERM,etal.Acost-basedmodelandeffectiveheuristicforrepairingconstraintsbyvaluemodification[C]//Proceedingsofthe2005ACMSIGMODInternationalConferenceonManagementofData.NewYork:ACM, 2005: 143-154.

[14]CHOMICKJJ,MARCINKOWSKIJ.Minimal-changeintegritymaintenanceusingtupledeletions[J].InformationandComputation, 2005, 197(1): 90-121.

[15]WIJSENJ.Databaserepairingusingupdates[J].ACMTransactionsonDatabaseSystems, 2005, 30(3): 722-768.

[16]FANW,GEERTSF,JIAX,etal.Conditionalfunctionaldependenciesforcapturingdatainconsistencies[J].ACMTransactionsonDatabaseSystems, 2008, 33(2): 6.

[17]BRAVOL,FANW,MAS.Extendingdependencieswithconditions[EB/OL]. [2016- 03- 10].http://www.vldb.org/conf/2007/papers/research/p243-bravo.pdf.

[18]GOLABL,KARLOFFH,KORNF,etal.Ongeneratingnear-optimaltableauxforconditionalfunctionaldependencies[J].ProceedingsoftheVLDBEndowment, 2008, 1(1): 376-390.

[19]CHUX,ILYASIF,PAPOTTIP.Holisticdatacleaning:putviolationsintocontext[C]//Proceedingsofthe2013IEEE29thInternationalConferenceonDataEngineering.Piscataway,NJ:IEEE, 2013:458-469.

[20]FANW,MAS,TANGN,etal.Interactionbetweenrecordmatchinganddatarepairing[J].JournalofDataandInformationQuality, 2014, 4(4):ArticleNo16.

[21]YAKOUTM,ELMAGARMIDAK,NEVILLEJ,etal.Guideddatarepair[J].ProceedingsoftheVLDBEndowment, 2011, 4(5): 279-289.

[22]VWRBORGHR,DEWM.UsingOpenRefine[M].Birmingham:PacktPublishing, 2013:53.

[23]PROCTORM,NEALEM,LINP,etal.Droolsdocumentation[EB/OL]. [2016- 03- 10].http://www.jboss.org/drools/documentation.html.

[24] 丁晶, 陳曉嵐, 吳萍. 基于正則表達式的深度包檢測算法[J]. 計算機應(yīng)用, 2007, 27(9): 2184-2186.(DINGJ,CHENXL,WUP.Deeppacketinspectionalgorithmbasedonregularexpressions[J].JournalofComputerApplications, 2007, 27(9):2184-2186.)

[25] 周傲英, 金澈清, 王國仁, 等. 不確定性數(shù)據(jù)管理技術(shù)研究綜述[J]. 計算機學報, 2009, 32(1): 1-16.(ZHOUAY,JINCQ,WANGGR,etal.Asurveyonthemanagementofuncertaindata[J].ChineseJournalofComputers, 2009, 32(1):1-16.)

ThisworkispartiallysupportedbytheXinjiangHigh-TechR&DProgram(201512103),theWestLightFoundationoftheChineseAcademyofSciences(XBBS201313),theXinjiangYoungScholarSupportProgram(2014721033).

ZHU Huijuan, born in 1984, Ph. D. candidate. Her research interests include data cleaning, data fusion, data analysis.

JIANG Tonghai, born in 1963, Ph. D., research fellow. His research interests include data fusion, data analysis, data mining.

ZHOU Xi, born in 1978, Ph. D., research fellow. His research interests include data cleaning, data fusion, data analysis.

CHENG Li, born in 1973, Ph. D., research fellow. His research interests include cloud computing, grid computing, high performance computing, data fusion.

ZHAO Fan, born in 1980, Ph. D. candidate, associate research fellow. His research interests include bilingual teaching, data visualization analysis.

MA Bo, born in 1984, Ph. D., associate research fellow. His research interests include semantic retrieval, data mining, knowledge discovery, data analysis.

Data cleaning method based on dynamic configurable rules

ZHU Huijuan1,2,3, JIANG Tonghai1,3, ZHOU Xi1,3, CHENG Li1,3*, ZHAO Fan1,3, MA Bo1,3

(1. Research Center for Multilingual Information Technology, Xinjiang Technical Institute of Physics and Chemistry, Chinese Academy of Sciences, Urumqi Xinjiang 830011, China;2. School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 100049, China;3. Xinjiang Laboratory of Minority Speech and Language Information Processing, Urumqi Xinjiang 830011, China)

Traditional data cleaning approaches usually implement cleaning rules specified by business requirements through hard-coding mechanism, which leads to well-known issues in terms of reusability, scalability and flexibility. In order to address these issues, a new Dynamic Rule-based Data Cleaning Method (DRDCM) was proposed, which supports the complex logic operation between various types of rules and three kinds of dirty data repair behavior. It integrates data detection, error correction and data transformation in one system and contributes several unique characteristics, including domain-independence, reusability and configurability. Besides, the formal concepts and terms regarding data detection and correction were defined, while necessary procedures and algorithms were also introduced. Specially, the supported multiple rule types and rule configurations in DRDCM were presented in detail. At last, the DRDCM approach was implemented. Experimental results show that the implemented system provides a high accuracy on the discarded behavior of dirty data repair with real-life data sets. Especially for the attribute required to comply with the statutory coding rules (such as ID card number), whose accuracy can reach 100%. Moreover, these results also indicate that this reference implementation of DRDCM can successfully support multiple data sources in cross-domain scenarios, and its performance does not sharply decrease with the increase of the number of rules. These results further validate that the proposed DRDCM is practical in real-world scenarios.

big data; data quality; data cleaning; dynamic configurable rules; data preprocessing

2016- 09- 20;

2016- 12- 22。 基金項目:新疆維吾爾自治區(qū)高技術(shù)研究發(fā)展計劃項目(201512103);中國科學院西部之光人才培養(yǎng)計劃項目(XBBS201313);新疆維吾爾自治區(qū)青年科技創(chuàng)新人才培養(yǎng)工程計劃項目(2014721033)。

朱會娟(1984—),女,河南洛陽人,博士研究生,主要研究方向:數(shù)據(jù)清洗、數(shù)據(jù)融合、數(shù)據(jù)分析; 蔣同海(1963—),男,新疆福海人,研究員,博士生導師,博士,主要研究方向:數(shù)據(jù)融合、數(shù)據(jù)分析、數(shù)據(jù)挖掘; 周喜(1978—),男,湖南雙峰人,研究員,博士,主要研究方向:數(shù)據(jù)清洗、數(shù)據(jù)融合、數(shù)據(jù)分析; 程力(1973—),男,新疆烏魯木齊人,研究員,博士生導師,博士,CCF會員,主要研究方向:云計算、網(wǎng)格計算、高性能計算、數(shù)據(jù)融合; 趙凡(1980—),男,山西介休人,副研究員,博士研究生,主要研究方向:雙語教學、數(shù)據(jù)可視化分析; 馬博(1984—),男,遼寧鞍山人,副研究員,博士,主要研究方向:語義檢索、數(shù)據(jù)挖掘、知識發(fā)現(xiàn)、數(shù)據(jù)分析。

1001- 9081(2017)04- 1014- 07

10.11772/j.issn.1001- 9081.2017.04.1014

TP311.11

A