摘要：數(shù)據(jù)清洗是對(duì)臟數(shù)據(jù)進(jìn)行檢測(cè)和糾正的過程，是進(jìn)行數(shù)據(jù)分析和管理的基礎(chǔ)。該文對(duì)經(jīng)典和新興的數(shù)據(jù)清洗技術(shù)進(jìn)行分類和總結(jié)，為進(jìn)一步的研究工作提供方向。形式化定義了數(shù)據(jù)清洗問題，對(duì)數(shù)據(jù)缺失、數(shù)據(jù)冗余、數(shù)據(jù)沖突和數(shù)據(jù)錯(cuò)誤這4種數(shù)據(jù)噪聲的檢測(cè)技術(shù)進(jìn)行詳細(xì)闡述。按照數(shù)據(jù)清洗方式對(duì)數(shù)據(jù)噪聲的消除技術(shù)進(jìn)行分類概述，包括基于完整性約束的數(shù)據(jù)清洗算法、基于規(guī)則的數(shù)據(jù)清洗算法、基于統(tǒng)計(jì)的數(shù)據(jù)清洗算法和人機(jī)結(jié)合的數(shù)據(jù)清洗算法。介紹了常用的測(cè)評(píng)數(shù)據(jù)集和噪聲注入工具，并對(duì)未來重點(diǎn)的研究方向進(jìn)行了探討和展望。

Abstract: Data cleaning is the process of detecting and repairing dirty data which is often needed in data analysis and management. This paper classifies and summarizes the traditional and advanced data cleaning techniques and identifies potential directions for further work. This study first formally defines the cleaning problem for structured data and then describes error detection methods for missing data, redundant data, conflicting data and erroneous data. The data cleaning methods are then summarized based on their error elimination method, including constraint-based data cleaning, rule-based data cleaning, statistical data cleaning and human-in-the-loop data cleaning. Some important datasets and noise injection tools are introduced as well. Open research problems and future research directions are also discussed.

在信息時(shí)代，數(shù)據(jù)即是資源。數(shù)據(jù)可靠無誤才能準(zhǔn)確地反映現(xiàn)實(shí)狀況，有效地支持組織決策。但是，現(xiàn)實(shí)世界中臟數(shù)據(jù)無處不在，數(shù)據(jù)不正確或者不一致會(huì)嚴(yán)重影響數(shù)據(jù)分析的結(jié)果，從而產(chǎn)生消極作用。在美國(guó)，臟數(shù)據(jù)導(dǎo)致14%的醫(yī)療支出被浪費(fèi)[1]，導(dǎo)致美國(guó)公司一年共損失6 000億美元[2]。因此，數(shù)據(jù)清洗在數(shù)據(jù)分析與管理的過程中扮演著越來越重要的角色。

數(shù)據(jù)清洗方面的研究最早出現(xiàn)在美國(guó)[3]，時(shí)至今日，已經(jīng)涌現(xiàn)出不勝枚舉的算法。隨著時(shí)代的變遷，錯(cuò)誤數(shù)據(jù)的形式變幻多樣，數(shù)據(jù)量的增長(zhǎng)也為數(shù)據(jù)清洗算法的設(shè)計(jì)提出新的要求，許多傳統(tǒng)的數(shù)據(jù)清洗算法已無法滿足大數(shù)據(jù)時(shí)代的需求，因此如何準(zhǔn)確高效地清洗臟數(shù)據(jù)始終是值得研究的課題。

數(shù)據(jù)清洗旨在識(shí)別和糾正數(shù)據(jù)中的噪聲，將噪聲對(duì)數(shù)據(jù)分析結(jié)果的影響降至最低。數(shù)據(jù)中的噪聲主要包括不完整的數(shù)據(jù)、冗余的數(shù)據(jù)、沖突的數(shù)據(jù)和錯(cuò)誤的數(shù)據(jù)。對(duì)數(shù)據(jù)噪聲的檢測(cè)和消除可以通過自動(dòng)的算法來實(shí)現(xiàn)，也可借助數(shù)據(jù)清洗的規(guī)則, 或者依靠用戶的參與。

當(dāng)下，機(jī)器學(xué)習(xí)和眾包技術(shù)的發(fā)展為數(shù)據(jù)清洗的研究工作注入了新的活力。機(jī)器學(xué)習(xí)技術(shù)可以從用戶記錄中學(xué)習(xí)制定清洗決策的規(guī)律，從而減輕用戶標(biāo)注數(shù)據(jù)的負(fù)擔(dān)[4-6]。同時(shí)，從清洗規(guī)則到機(jī)器學(xué)習(xí)模型的轉(zhuǎn)換使得用戶不再需要制定大量的數(shù)據(jù)清洗規(guī)則。眾包技術(shù)把數(shù)據(jù)清洗任務(wù)發(fā)布到互聯(lián)網(wǎng)，從而集中眾多用戶的知識(shí)和決策[7-8]，眾包的形式可以充分利用外部資源優(yōu)勢(shì)，在降低清洗代價(jià)的同時(shí)，提高數(shù)據(jù)清洗的準(zhǔn)確度和效率。

本文對(duì)結(jié)構(gòu)化數(shù)據(jù)的數(shù)據(jù)清洗技術(shù)進(jìn)行綜述和展望。結(jié)構(gòu)化數(shù)據(jù)是指可以使用二維表結(jié)構(gòu)表示和存儲(chǔ)的數(shù)據(jù)，具有易于輸入、存儲(chǔ)、查詢和分析的特點(diǎn)，因此在現(xiàn)實(shí)世界中被廣泛應(yīng)用，例如企業(yè)資源計(jì)劃、醫(yī)療信息系統(tǒng)等。目前，國(guó)內(nèi)外已有一些研究人員對(duì)數(shù)據(jù)清洗的相關(guān)技術(shù)進(jìn)行了較為全面的綜述[9-15]。不同于上述文章，本文著重對(duì)各類數(shù)據(jù)噪聲的檢測(cè)和消除技術(shù)進(jìn)行全面系統(tǒng)化的總結(jié)，不僅包含最為經(jīng)典和最新的研究成果，還展望了數(shù)據(jù)清洗領(lǐng)域未來的研究方向。

1 問題描述1.1 結(jié)構(gòu)化數(shù)據(jù)的清洗相關(guān)概念

數(shù)據(jù)清洗是識(shí)別和消除臟數(shù)據(jù)中數(shù)據(jù)噪聲的過程，數(shù)據(jù)清洗的過程可以描述為：給定具有模式R的數(shù)據(jù)庫(kù)實(shí)例I以及數(shù)據(jù)質(zhì)量需求；數(shù)據(jù)清洗是指找到數(shù)據(jù)庫(kù)實(shí)例I'，它可以滿足所有的數(shù)據(jù)質(zhì)量需求，同時(shí)清洗代價(jià)最小。

不同學(xué)科背景下，數(shù)據(jù)質(zhì)量需求的表示方式各不相同。在數(shù)據(jù)內(nèi)容層面，要求數(shù)據(jù)具有正確性、完整性、一致性、可靠性等。在數(shù)據(jù)效用層面，要求數(shù)據(jù)具有及時(shí)性、相關(guān)性、背景性等。學(xué)術(shù)界的研究多聚焦于數(shù)據(jù)內(nèi)容質(zhì)量的提升，特別是缺失數(shù)據(jù)補(bǔ)全、數(shù)據(jù)去重和錯(cuò)誤數(shù)據(jù)糾正，此時(shí)指導(dǎo)數(shù)據(jù)清洗的指標(biāo)可以具體表示為：

1) 完整性約束。實(shí)體完整性約束規(guī)定數(shù)據(jù)表的主鍵不能空和重復(fù)；域完整性約束要求表中的列必須滿足某種特定的數(shù)據(jù)類型約束；參照完整性約束規(guī)定了數(shù)據(jù)表主鍵和外鍵的一致性；此外，還有用戶定義的完整性約束。這些約束大多可以反映屬性或?qū)傩越M之間互相依存和制約的關(guān)系，干凈的數(shù)據(jù)需滿足這些約束條件。例如，函數(shù)依賴X→Y，其中X和Y均為屬性集R={A1, A2, …, Am}的子集。給定實(shí)例I中的兩個(gè)元組t1和t2，如果t1[X]=t2[X]，那么必須有t1[Y]=t2[Y]。常用的完整性約束還有條件函數(shù)依賴[16-17]、包含依賴[18]、度量依賴[19]、差別依賴[20]等。

2) 數(shù)據(jù)清洗規(guī)則。數(shù)據(jù)清洗規(guī)則可以指明數(shù)據(jù)噪聲及其對(duì)應(yīng)的正確值，當(dāng)數(shù)據(jù)表中的屬性值與規(guī)則指出的真值匹配時(shí)，該數(shù)據(jù)滿足數(shù)據(jù)質(zhì)量需求。有的清洗規(guī)則直接把正確值編碼在規(guī)則里，例如修復(fù)規(guī)則[21-22]；而有的清洗規(guī)則需要通過建立外部數(shù)據(jù)源與數(shù)據(jù)庫(kù)實(shí)例之間的對(duì)應(yīng)關(guān)系來獲取正確的數(shù)據(jù)，例如編輯規(guī)則[23-24]、Sherlock規(guī)則[25]和探測(cè)規(guī)則[26-27]。常用的外部數(shù)據(jù)源有主數(shù)據(jù)和知識(shí)庫(kù)。數(shù)據(jù)清洗規(guī)則含義廣泛，數(shù)據(jù)質(zhì)量標(biāo)準(zhǔn)和規(guī)范多可以形式化為數(shù)據(jù)清洗規(guī)則。

3) 用戶需求。這里的用戶需求是指由用戶直接指明數(shù)據(jù)庫(kù)實(shí)例中的錯(cuò)誤數(shù)據(jù)和修復(fù)措施。用戶標(biāo)注部分?jǐn)?shù)據(jù)后，可以通過監(jiān)督式學(xué)習(xí)方法(比如支持向量機(jī)和隨機(jī)森林)來模擬用戶行為。

1.2 清洗質(zhì)量的評(píng)價(jià)指標(biāo)

清洗質(zhì)量主要是指清洗的準(zhǔn)確性和全面性，常用的評(píng)價(jià)指標(biāo)有準(zhǔn)確率、召回率和F值?？紤]一個(gè)二分類問題，即實(shí)例被分為正類和負(fù)類，那么：準(zhǔn)確率定義為被分類器判斷為正類的實(shí)例中正確分類的比例；召回率定義為分類器將正類判斷為正類的比例；而F值如式(1)所示，是準(zhǔn)確率和召回率的調(diào)和平均值。

$ F = 2 times frac{{準(zhǔn)確率 times 召回率}}{{準(zhǔn)確率 + 召回率}}. $ (1)

不同的數(shù)據(jù)清洗場(chǎng)景下, 這些評(píng)價(jià)指標(biāo)有不同的含義。例如：在數(shù)據(jù)去重方面，準(zhǔn)確率可表示為所有被判斷為冗余的數(shù)據(jù)中真實(shí)的冗余數(shù)據(jù)所占的比例，而召回率為成功檢測(cè)出的冗余數(shù)據(jù)占所有冗余數(shù)據(jù)的比例；在數(shù)據(jù)修復(fù)方面，準(zhǔn)確率是指正確修改的屬性值個(gè)數(shù)占所有被修改的屬性值個(gè)數(shù)的比例，召回率是指正確修改的屬性值個(gè)數(shù)占所有應(yīng)修改的屬性值個(gè)數(shù)的比例。

在利用上述3個(gè)度量指標(biāo)衡量數(shù)據(jù)清洗的準(zhǔn)確性時(shí)，需要獲得數(shù)據(jù)庫(kù)實(shí)例I對(duì)應(yīng)的干凈數(shù)據(jù)庫(kù)實(shí)例Ic。現(xiàn)實(shí)世界中往往無法直接獲取Ic，一種可行的方法是數(shù)據(jù)經(jīng)過清洗后，交付于領(lǐng)域?qū)＜液藢?shí)每一步的修改，由此來計(jì)算準(zhǔn)確率。在學(xué)術(shù)領(lǐng)域，有人工標(biāo)注錯(cuò)誤數(shù)據(jù)的數(shù)據(jù)集非常少，為了衡量數(shù)據(jù)清洗算法的性能，研究人員往往會(huì)在干凈的數(shù)據(jù)庫(kù)實(shí)例Ic中手動(dòng)注入數(shù)據(jù)噪聲，得到包含臟數(shù)據(jù)的數(shù)據(jù)庫(kù)實(shí)例I，通過數(shù)據(jù)清洗算法獲得I'后，利用Ic和I'計(jì)算相應(yīng)的準(zhǔn)確率、召回率和F值。

2 數(shù)據(jù)噪聲檢測(cè)

數(shù)據(jù)清洗的第1步就是檢測(cè)臟數(shù)據(jù)中的數(shù)據(jù)噪聲。下面通過表 1中本文作者杜撰的數(shù)據(jù)，給出結(jié)構(gòu)化數(shù)據(jù)中可能存在的數(shù)據(jù)噪聲類型以及相應(yīng)的檢測(cè)算法。

表 1 員工信息表

元組 姓名 級(jí)別 城市 州 年薪/千美元 t1 Rabin P8 San Diego CA 400 t2 Leoan P5 New York NY -1 t3 Rabin P9 Sa Diego CA 400 t4 Mattan N/A San Diego CE 310 t5 Javier P2 Chicago IL 100

1) 數(shù)據(jù)缺失。它是指數(shù)據(jù)庫(kù)實(shí)例中某些屬性值缺失或者包含無效值，例如表 1中的t4[級(jí)別]。值得注意的是，t2[年薪]也是缺失值，因?yàn)椤?1”不是有效的工資表達(dá)形式。

空數(shù)據(jù)的檢測(cè)相對(duì)簡(jiǎn)單，只需要檢查不允許為空的屬性值是否為空、“NULL”或者“N/A”。DiMaC系統(tǒng)[28]和FAHES系統(tǒng)[29]可以用來檢測(cè)偽裝缺失值，即無效值。對(duì)于超出屬性域的無效值，由于這些值在語法上不符合給定屬性中的常規(guī)值，因此可以通過學(xué)習(xí)每個(gè)屬性的數(shù)據(jù)模式來檢測(cè)這些無效值。特別地，對(duì)于數(shù)值數(shù)據(jù)，可以通過基于密度的異常值來檢測(cè)。對(duì)于沒有超出屬性域的偽裝缺失值，F(xiàn)AHES通過計(jì)算該值對(duì)整個(gè)關(guān)系表的數(shù)據(jù)分布的影響來判斷是否是無效值。

2) 數(shù)據(jù)冗余。它是指同一數(shù)據(jù)在數(shù)據(jù)庫(kù)實(shí)例中多次出現(xiàn)，即存在數(shù)據(jù)之間的重復(fù)。例如表 1中的元組t1和t3，它們均表示員工Rabin的信息，因此這兩條數(shù)據(jù)存在冗余。如何檢測(cè)冗余數(shù)據(jù)這一問題已經(jīng)得到了廣泛研究[13, 30-31]。檢測(cè)冗余數(shù)據(jù)的算法多分為3步：數(shù)據(jù)分組、數(shù)據(jù)比對(duì)和冗余判斷。

數(shù)據(jù)分組即對(duì)數(shù)據(jù)進(jìn)行聚類操作，把可能指代現(xiàn)實(shí)世界中同一事物的數(shù)據(jù)(即重復(fù)數(shù)據(jù))聚到一組，這樣在進(jìn)行數(shù)據(jù)匹配時(shí)只需比較相同組別的數(shù)據(jù)，從而能夠大大縮小搜索空間。在過去的幾年中涌現(xiàn)出許多數(shù)據(jù)分組算法[32]，基本上均是通過比較關(guān)鍵屬性是否相等或相似來對(duì)數(shù)據(jù)進(jìn)行分組，對(duì)關(guān)鍵屬性常見的處理方式有Hash[33-35]、排序[34, 36]、冠層聚類[37]、雙標(biāo)索引[32]等。

數(shù)據(jù)比對(duì)即在每一組內(nèi)計(jì)算每對(duì)數(shù)據(jù)的相似程度，在接下來的冗余判斷階段會(huì)根據(jù)該相似程度判定是否存在冗余。這里把數(shù)據(jù)比對(duì)和冗余判斷階段的算法分為以下幾類：

(1) 基于相似度函數(shù)的算法。相似度函數(shù)以數(shù)據(jù)對(duì)作為輸入，輸出一個(gè)相似度分值。兩條數(shù)據(jù)越相似，輸出的值越大。若兩條數(shù)據(jù)的相似度大于給定的閾值，那么它們就是冗余的[38-40]。

(2) 基于規(guī)則的算法。規(guī)則是多個(gè)斷言的組合，若一對(duì)數(shù)據(jù)滿足所有的斷言，那么它們將滿足這個(gè)規(guī)則，從而被判定為冗余數(shù)據(jù)。每個(gè)斷言包含一個(gè)相似度函數(shù)和一個(gè)閾值，許多算法[41-43]需要用戶來制定規(guī)則，也可以利用現(xiàn)有的技術(shù)[44]從正例和負(fù)例中學(xué)出合適的相似度函數(shù)和閾值。

(3) 基于機(jī)器學(xué)習(xí)的算法。冗余判斷問題在機(jī)器學(xué)習(xí)技術(shù)中可以看作分類問題[36, 45]。在數(shù)據(jù)比對(duì)階段，計(jì)算組內(nèi)每對(duì)數(shù)據(jù)在某些屬性上的相似度，并表示成數(shù)據(jù)對(duì)的特征向量。在接下來的冗余判斷階段，利用訓(xùn)練集訓(xùn)練出分類模型，其中訓(xùn)練集中的正例和負(fù)例分別表示冗余和不冗余的數(shù)據(jù)對(duì)。訓(xùn)練出的分類模型可以標(biāo)記新的數(shù)據(jù)，常用的模型有決策樹[33, 45]、支持向量機(jī)[36, 45]等。

(4) 人機(jī)結(jié)合的算法。用戶會(huì)參與到基于規(guī)則的算法中制定規(guī)則，或者基于機(jī)器學(xué)習(xí)的算法中標(biāo)注數(shù)據(jù)以獲得訓(xùn)練集。此外，也有研究者[7-8]利用眾包平臺(tái)解決數(shù)據(jù)冗余的問題，例如圖 1中的CrowdER[7]。它首先利用機(jī)器算法得到可能冗余的數(shù)據(jù)對(duì)，再由眾包用戶判斷一對(duì)或一組數(shù)據(jù)是否冗余。

圖 1 CrowdER中的數(shù)據(jù)冗余檢測(cè)[7]

3) 數(shù)據(jù)沖突。無法滿足完整性約束的兩條數(shù)據(jù)之間存在數(shù)據(jù)沖突。假設(shè)表 1中存在函數(shù)依賴[城市]→[州]，那么元組t1和t4存在數(shù)據(jù)沖突，因?yàn)樗鼈兙哂邢嗤某鞘小癝an Diego”，但是t1[州]和t4[州]不同。

通過完整性約束可以檢測(cè)數(shù)據(jù)沖突，而完整性約束可以從干凈的數(shù)據(jù)集中學(xué)得。不同的完整性約束有不同的學(xué)習(xí)方法，但許多完整性約束都是基于函數(shù)依賴設(shè)計(jì)的。函數(shù)依賴的學(xué)習(xí)算法分為自上而下和自下而上兩類[46-47]。自上而下的算法首先從高到底依次遍歷屬性點(diǎn)陣，生成候選函數(shù)依賴，然后檢查每個(gè)候選函數(shù)依賴在關(guān)系表上的符合度，通過檢查的函數(shù)依賴會(huì)用來過濾其他的候選函數(shù)依賴。自上而下的函數(shù)依賴生成算法包括TANE[48]、FD_Mine[49]、FUN[50]等。與自上而下的生成算法不同的是，自下而上的算法不會(huì)檢查候選函數(shù)依賴是否符合關(guān)系表，而是通過元組的協(xié)同集和差異集過濾候選函數(shù)依賴。自下而上的函數(shù)依賴生成算法有FastFDs[51]、Dep-Miner[52]等。除此之外，條件函數(shù)依賴的生成可以參考文[53], 包含依賴的生成可以參考文[54], 差別依賴的生成可以參考文[20]。

4) 數(shù)據(jù)錯(cuò)誤。它是指數(shù)據(jù)庫(kù)實(shí)例中某些不為空的屬性值是錯(cuò)誤的，例如屬性域錯(cuò)誤、拼寫錯(cuò)誤、格式錯(cuò)誤等。數(shù)據(jù)錯(cuò)誤有時(shí)會(huì)引發(fā)數(shù)據(jù)沖突，但是不沖突的數(shù)據(jù)不一定是正確數(shù)據(jù)。舉例來說，t3[城市]和t4[州]均是表 1中的錯(cuò)誤數(shù)據(jù)，t4[州]中的錯(cuò)誤引發(fā)了函數(shù)依賴上的數(shù)據(jù)沖突，但t3[城市]沒有導(dǎo)致任何數(shù)據(jù)沖突。用戶可以直接指明錯(cuò)誤的數(shù)據(jù)，除此之外，錯(cuò)誤數(shù)據(jù)的檢測(cè)算法還可以分為以下幾類：

(1) 基于完整性約束的錯(cuò)誤檢測(cè)。完整性約束可以用來檢測(cè)數(shù)據(jù)沖突，但是約束本身無法指出沖突的發(fā)生是由哪個(gè)屬性值引發(fā)的。舉例來說，表 1中元組t1和t4在函數(shù)依賴[城市]→[州]上存在沖突，但是僅憑此函數(shù)依賴無法判斷t1[城市]、t4[城市]、t1[州]和t4[州]中哪個(gè)值是錯(cuò)誤的，因此基于完整性約束的錯(cuò)誤檢測(cè)多是通過啟發(fā)式方法猜測(cè)錯(cuò)誤的值。為了最小化清洗代價(jià)，這種情況下往往斷定出現(xiàn)頻率高的屬性值組合是正確的屬性值組合[55-56]。此外，還可以利用整體錯(cuò)誤檢測(cè)技術(shù)[57-58]，該技術(shù)通過建立超圖來識(shí)別錯(cuò)誤數(shù)據(jù)。超圖中的頂點(diǎn)代表的是關(guān)系表中的屬性值，若一組屬性值存在沖突，相應(yīng)的頂點(diǎn)就屬于同一個(gè)超邊，比如表 1中的t1[城市]、t4[城市]、t1[州]和t4[州]這4個(gè)頂點(diǎn)就屬于同一個(gè)超邊。同一個(gè)頂點(diǎn)可能屬于不同的超邊，這樣只需要在超圖上運(yùn)行最小頂點(diǎn)覆蓋算法就可以找到錯(cuò)誤的數(shù)據(jù)。Hao等提出了一種基于極大獨(dú)立集的錯(cuò)誤檢測(cè)技術(shù)[59]。給定關(guān)系表上的一個(gè)完整性約束后，可以為關(guān)系表建立圖模型，其中圖模型中的頂點(diǎn)代表關(guān)系表中的元組，若兩個(gè)元組之間存在沖突，對(duì)應(yīng)的頂點(diǎn)之間就有一條邊，邊上的權(quán)值是兩個(gè)元組之間的清洗代價(jià)。若在圖模型中找到對(duì)應(yīng)清洗代價(jià)最小的極大獨(dú)立集，那么不在極大獨(dú)立集中的元組就可以認(rèn)定為錯(cuò)誤的數(shù)據(jù)。

(2) 基于規(guī)則的錯(cuò)誤檢測(cè)。編輯規(guī)則[23-24]在關(guān)系表和主數(shù)據(jù)之間建立匹配關(guān)系，若關(guān)系表中的屬性值和與其匹配到的主數(shù)據(jù)中的屬性值不相等，就可以判斷關(guān)系表中的數(shù)據(jù)存在錯(cuò)誤。編輯規(guī)則的形式化定義如式(2)所示,

$ psi :left( {left( {X, {X_{rm{m}}}} right) to left( {B, {B_{rm{m}}}} right), {t_{rm{p}}}left[ {{X_{rm{p}}}} right]} right). $ (2)

其中：X和Xm分別是屬性集R和Rm的子集，并且|X|=|Xm|；屬性B屬于RX，屬性Bm屬于Rm；tp指明了屬性集Xp上的取值要求，劃定了編輯規(guī)則的執(zhí)行范圍。編輯規(guī)則的語義是：如果存在關(guān)系表中的元組t和主數(shù)據(jù)中的元組tm滿足t[Xp]符合tp[Xp]，且t[X]=tm[Xm]，那么t[B]的值應(yīng)為tm[Bm]。若t[B]和tm[Bm]不相等，那么就可以判斷t[B]中存在錯(cuò)誤。修復(fù)規(guī)則[21-22]、Sherlock規(guī)則[25]和探測(cè)規(guī)則[26-27]均可以證明負(fù)面語義，從而找出錯(cuò)誤的屬性值。圖 2中給出了這些規(guī)則的示例。修復(fù)規(guī)則的形式化定義如式(3)所示,

$ varphi :left( {left( {X, {t_{rm{p}}}left[ X right]} right), left( {B, T_{rm{p}}^ - left[ B right]} right)} right) to T_{rm{p}}^ + left[ B right]. $ (3)圖 2 數(shù)據(jù)清洗規(guī)則舉例

其中：X是屬性集R的子集，tp[X]是屬性集X一種可能的取值，代表證據(jù)值；屬性B屬于RX，Tp-[B]是B的屬性域中的一組常量，代表B的錯(cuò)誤值，而tp+[B]屬于B的屬性域但不屬于Tp-[B]，代表B的正確值。修復(fù)規(guī)則的語義是:如果元組t在屬性集X上的值t[X]等于tp[X]，在屬性B上的值t[B]屬于Tp-[B]，那么t[B]就是錯(cuò)誤的，正確的值應(yīng)是Tp+[B]。因此，利用修復(fù)規(guī)則中的tp[X]和Tp-[B]就可以檢測(cè)錯(cuò)誤的值。Sherlock規(guī)則通過在關(guān)系表I和主數(shù)據(jù)Im之間建立匹配關(guān)系來清洗關(guān)系表，它的形式化定義為

$ rho :left( {left( {X, {X_{rm{m}}}} right), left( {B, B_{rm{m}}^ - , B_{rm{m}}^ + } right), mathop approx limits^ to } right). $ (4)

其中：X和Xm分別是屬性集R和Rm的子集，并且|X|=|Xm|；屬性B屬于RX，屬性Bm-和Bm+是RmXm里不同的兩個(gè)屬性；$ {mathop approx limits^ to } $代表的是(X, Xm)、(B, Bm-)和(B, Bm+)之間的匹配操作。Sherlock規(guī)則的語義是:如果I中的元組t和Im中的元組tm滿足(t[X], tm[Xm])、(t[B], tm[Bm-])匹配，那么t[X]是正確的，t[B]是錯(cuò)誤的，正確的值應(yīng)是tm[Bm+]。因此，利用Sherlock規(guī)則中關(guān)系表與主數(shù)據(jù)建立的聯(lián)系就可以檢測(cè)原始關(guān)系表中的錯(cuò)誤。探測(cè)規(guī)則通過在關(guān)系表I和知識(shí)庫(kù)K之間建立匹配關(guān)系來清洗關(guān)系表。探測(cè)規(guī)則是一個(gè)有向圖，規(guī)則中的節(jié)點(diǎn)u代表關(guān)系表中的屬性列col(u)和知識(shí)庫(kù)中的類型type(u)之間的匹配關(guān)系，節(jié)點(diǎn)u和v之間的邊e代表了屬性col(u)和col(v)之間的關(guān)系是rel(e)。探測(cè)規(guī)則有3種類型的節(jié)點(diǎn)，分別是證據(jù)節(jié)點(diǎn)Ve、正面節(jié)點(diǎn)p和負(fù)面節(jié)點(diǎn)n。它的語義是：如果知識(shí)庫(kù)中存在一些實(shí)例可以和元組t滿足Ve∪{n}以及對(duì)應(yīng)的邊中指明的匹配關(guān)系，那么t[col(n)]中的值就是錯(cuò)誤的，正確的值可以從正面節(jié)點(diǎn)p中獲得，因此探測(cè)規(guī)則也可以用來檢測(cè)錯(cuò)誤數(shù)據(jù)。

(3) 基于統(tǒng)計(jì)和機(jī)器學(xué)習(xí)的錯(cuò)誤檢測(cè)?；诮y(tǒng)計(jì)和機(jī)器學(xué)習(xí)的錯(cuò)誤檢測(cè)算法多是基于統(tǒng)計(jì)分析[4-6]的：通過概率模型或關(guān)系依賴模型獲得輸入數(shù)據(jù)集的定量統(tǒng)計(jì)信息，比如屬性值的共現(xiàn)信息，然后通過真值推理來檢查原始數(shù)據(jù)值是否在期望范圍內(nèi)，或者查找不符合輸入數(shù)據(jù)整體分布的屬性值，這些屬性值就是錯(cuò)誤的屬性值。

數(shù)據(jù)噪聲的類型及檢測(cè)方法匯總見表 2。

表 2 數(shù)據(jù)噪聲的類型及檢測(cè)方法匯總

噪聲類型 噪聲定義 檢測(cè)方法 數(shù)據(jù)缺失 數(shù)據(jù)庫(kù)實(shí)例中某些屬性值缺失或者包含無效值 ①對(duì)于缺失數(shù)據(jù)，可直接檢查不允許為空的屬性值是否為空、“NULL”或者“N/A”
②對(duì)于無效值的檢測(cè)可參考DiMaC系統(tǒng)[28]和FAHES系統(tǒng)[29] 數(shù)據(jù)冗余 同一數(shù)據(jù)在數(shù)據(jù)庫(kù)實(shí)例中多次出現(xiàn)，即存在數(shù)據(jù)之間的重復(fù) 包含3個(gè)步驟：
①數(shù)據(jù)分組：可參考文[32]
②數(shù)據(jù)比對(duì)和③冗余判斷：基于相似度函數(shù)的算法[38-40]、基于規(guī)則的算法[41-44]、基于機(jī)器學(xué)習(xí)的算法[36, 45]、人機(jī)結(jié)合的算法[7-8] 數(shù)據(jù)沖突 無法滿足完整性約束的兩條數(shù)據(jù)之間存在數(shù)據(jù)沖突 從干凈數(shù)據(jù)集中學(xué)習(xí)完整性約束[46-47]以檢測(cè)臟數(shù)據(jù)中的數(shù)據(jù)沖突 數(shù)據(jù)錯(cuò)誤 數(shù)據(jù)庫(kù)實(shí)例中某些不為空的屬性值是錯(cuò)誤的，例如屬性域錯(cuò)誤、拼寫錯(cuò)誤、格式錯(cuò)誤等 ①基于完整性約束的錯(cuò)誤檢測(cè)：頻率[55-56]、整體錯(cuò)誤檢測(cè)技術(shù)[57-58]、基于極大獨(dú)立集的錯(cuò)誤檢測(cè)技術(shù)[59]
②基于規(guī)則的錯(cuò)誤檢測(cè)：編輯規(guī)則[23-24]、修復(fù)規(guī)則[21-22]、Sherlock規(guī)則[25]、探測(cè)規(guī)則[26-27]
③基于統(tǒng)計(jì)和機(jī)器學(xué)習(xí)的錯(cuò)誤檢測(cè)[4-6]
④由用戶指出數(shù)據(jù)集中的錯(cuò)誤

3 數(shù)據(jù)噪聲消除

真實(shí)世界中的臟數(shù)據(jù)往往不只包含一種類型的數(shù)據(jù)噪聲，因此本節(jié)不再討論每種類型的數(shù)據(jù)噪聲如何消除，而是根據(jù)消除方式對(duì)數(shù)據(jù)清洗算法進(jìn)行分類。

傳統(tǒng)的算法[60-66]多是通過元組的增加和刪除來清洗關(guān)系表中的臟數(shù)據(jù)，比如刪除包含缺失值的元組或者冗余的數(shù)據(jù)，增加特定的元組使關(guān)系表滿足包含依賴，刪除引發(fā)沖突的元組使得關(guān)系表滿足給定的完整性約束。但是，元組的刪除會(huì)導(dǎo)致重要信息的流失，元組的增加也不會(huì)使查詢的結(jié)果更加準(zhǔn)確。因此，這里主要討論數(shù)據(jù)的修復(fù)，即把錯(cuò)誤的屬性值修改成算法推測(cè)出的正確值。通過數(shù)據(jù)修復(fù)來清洗數(shù)據(jù)的算法可以分為基于完整性約束的數(shù)據(jù)清洗、基于規(guī)則的數(shù)據(jù)清洗、基于統(tǒng)計(jì)和機(jī)器學(xué)習(xí)的數(shù)據(jù)清洗和人機(jī)結(jié)合的數(shù)據(jù)清洗。數(shù)據(jù)清洗結(jié)果可能不是唯一的，在這種情況下，可以把所有的清洗可能性枚舉出來[67]，若有用戶參與到清洗過程中，可以由用戶來指明某項(xiàng)數(shù)據(jù)更新是否可以執(zhí)行[68]。除此之外，自動(dòng)的數(shù)據(jù)清洗算法大多選擇對(duì)應(yīng)清洗代價(jià)最小的修復(fù)方式。清洗代價(jià)的定義基于文[55]：若關(guān)系表I中的元組t修復(fù)成I'中的元組t'，假設(shè)元組t的權(quán)值是w(t)，那么元組t對(duì)應(yīng)的清洗代價(jià)為

$ {rm{cost}}left( t right) = wleft( t right)sumlimits_{A in R} {{rm{dis}}left( {tleft[ A right], t'left[ A right]} right)} . $ (5)

關(guān)系表I的總清洗代價(jià)是I中所有元組清洗代價(jià)之和，

$ {rm{cost}}left( I right) = sumlimits_{t in I} {{rm{cost}}left( t right)} . $ (6)

其中dis(t[A], t'[A])表示t[A]和t'[A]利用距離函數(shù)(可參考相關(guān)綜述[69-70])計(jì)算出的距離值。

3.1 基于完整性約束的數(shù)據(jù)清洗

基于完整性約束的數(shù)據(jù)清洗即給定包含臟數(shù)據(jù)的關(guān)系表I和I中的一組完整性約束Σ，修改關(guān)系表或者約束后使得I'滿足Σ'中的所有完整性約束。這里首先假設(shè)完整性約束Σ是完全正確的，而且僅需要清洗數(shù)據(jù)，接下來再討論當(dāng)Σ存在錯(cuò)誤時(shí)，如何利用統(tǒng)一的清洗模型來清洗約束和數(shù)據(jù)。

對(duì)數(shù)據(jù)進(jìn)行清洗的算法分為局部清洗算法和全局清洗算法，它們的區(qū)別在于：局部清洗算法在檢測(cè)和清洗錯(cuò)誤數(shù)據(jù)時(shí)僅考慮當(dāng)前檢測(cè)出沖突的完整性約束，而全局清洗算法綜合考慮若干個(gè)有聯(lián)系的完整性約束。

局部清洗算法中較為經(jīng)典的是由Bohannon等在2005年提出的[55]，該算法利用等價(jià)類消除函數(shù)依賴沖突和包含依賴沖突，NADEEF系統(tǒng)[71]就利用了這種思想。在第2.2節(jié)中曾論述過當(dāng)元組t1和t4在函數(shù)依賴X→Y上存在沖突時(shí)，僅憑函數(shù)依賴無法判斷t1[X]、t4[X]、t1[Y]和t4[Y]中哪個(gè)值是錯(cuò)誤的，因此可以把t1[Y]和t4[Y]修改成相同的值來消除這個(gè)沖突，也可以把t1[X]和t4[X]修改成不同的值。Bohannon等的研究[55]僅支持修改Y屬性集：所有在X屬性集上取值相同的元組會(huì)被加入到相同的等價(jià)類eqA中，其中A∈Y，而eqA中所有的元組在屬性A上均會(huì)取相同的值。文[55]中定義了等價(jià)類的清洗代價(jià)，若等價(jià)類中的所有元組在屬性A上取值v，那么等價(jià)類清洗代價(jià)為

$ {rm{cost}}left( {{rm{e}}{{rm{q}}_A}, v} right) = sumlimits_{left( {t, A} right) in {rm{e}}{{rm{q}}_A}} {left( {wleft( t right) cdot {rm{dis}}left( {v, tleft[ A right]} right)} right)} , $

而v的選取目標(biāo)是使得cost(eqA, v)最小。對(duì)于包含依賴R1[A]?R2[B]，其中A和B分別是關(guān)系表R1和R2中的屬性，若t1∈R1不滿足該包含依賴，那么可以把t1[A]修改成R2中與其相似的元組t2在屬性B上的取值，也可以把R2中某些元組在屬性B上的取值修改成t1[A]。在這兩種情況下，t1[A]和t2[B]均會(huì)劃分到相同的等價(jià)類。若R2[B]中不存在與t1[A]較為相似的值，即元組的清洗代價(jià)大大超過了元組插入的代價(jià)，這時(shí)會(huì)在R2中插入一個(gè)新的元組使得t1滿足包含依賴。這個(gè)新的元組在屬性B上取值為t1[A]，在其他屬性上均取空值。

Bohannon等的算法可以通過擴(kuò)展來解決條件函數(shù)依賴上的沖突[72]。在此基礎(chǔ)上，Kolahi等的算法[58]除了支持把一個(gè)屬性值修改成另外一個(gè)屬性值，還支持在沒有足夠的信息時(shí)把一個(gè)屬性值修改成一個(gè)變量以消除沖突。該思想同樣應(yīng)用在LLUNATIC系統(tǒng)[73]中。Beskales等的算法[74]通過用戶定義的強(qiáng)制約束來指定清洗過程中不允許變動(dòng)的屬性值，以此來得到更符合用戶預(yù)期的清洗結(jié)果。

BIGDANSING系統(tǒng)[75]擴(kuò)展了該等價(jià)類的思想以解決分布式數(shù)據(jù)清洗問題。當(dāng)?shù)玫降葍r(jià)類eqA后，BIGDANSING系統(tǒng)設(shè)計(jì)了兩組map-reduce函數(shù)。第1組map函數(shù)的鍵值對(duì)表示為＜＜等價(jià)類號(hào)，屬性值＞，計(jì)數(shù)器＞，用于統(tǒng)計(jì)每個(gè)等價(jià)類中每個(gè)屬性值的個(gè)數(shù)，第2組map函數(shù)的鍵值對(duì)表示為＜等價(jià)類號(hào)，＜屬性值, 計(jì)數(shù)器＞＞，用于把同一等價(jià)類的統(tǒng)計(jì)結(jié)果聚在一起，出現(xiàn)頻率最高的屬性值就選定為該等價(jià)類的目標(biāo)值。

全局清洗算法是由Chu等在2013年提出的[57]。該算法解決的是否定約束上的沖突，但其思路可以擴(kuò)展到其他完整性約束上。全局清洗算法的系統(tǒng)架構(gòu)如圖 3[57]所示。給定包含臟數(shù)據(jù)的關(guān)系表和一組否定約束，在第2.2節(jié)中已討論如何通過構(gòu)建數(shù)據(jù)沖突圖來檢測(cè)錯(cuò)誤的屬性值，在這里重點(diǎn)討論尋找取值約束和取值決策模塊，即如何確定元組的某個(gè)屬性t[A]的正確取值。

圖 3 完整性約束的全局清洗算法[57]

尋找取值約束即尋找t[A]取值方面的約束條件，也就是文[57]中給出的修復(fù)上下文這一概念。修復(fù)上下文包含兩個(gè)部分：修復(fù)內(nèi)容和修復(fù)表達(dá)式。其中修復(fù)表達(dá)式包含了與修復(fù)內(nèi)容相關(guān)的賦值和約束。舉例來說，假設(shè)關(guān)系表I上存在否定約束，

$ neg left( {Ileft( {X, A} right), Ileft( {X', A'} right), left( {X = X'} right), left( {A ne A'} right)} right)。$

該否定約束與函數(shù)依賴X→A表達(dá)相同的約束條件。因此，若存在元組t'使得t[X]=t'[X]而t[A] ≠ t'[A]，數(shù)據(jù)沖突圖中t[X]、t'[X]、t[A]和t'[A]就包含在同一個(gè)超邊內(nèi)，修復(fù)上下文中的修復(fù)內(nèi)容是t[A]和t'[A]，而修復(fù)表達(dá)式為t[A]=t'[A]，若t[A]和t'[A]還包含在其他的超邊里，其對(duì)應(yīng)的約束條件也會(huì)被加入到t[A]的修復(fù)上下文中。

當(dāng)獲得t[A]的修復(fù)上下文后，取值決策模塊用于確定t[A]的最終賦值。由于修復(fù)表達(dá)式中可能會(huì)存在沖突，比如“t[A]＞6”和“t[A]＜4”這兩個(gè)修復(fù)表達(dá)式可能會(huì)同時(shí)存在于t[A]的修復(fù)上下文中，因此取值決策模塊的第1步操作就是獲得最大的不存在沖突的修復(fù)表達(dá)式集合。接下來，該模塊根據(jù)這些修復(fù)表達(dá)式計(jì)算t[A]的最佳賦值策略，該賦值可以滿足所有的修復(fù)表達(dá)式，同時(shí)使得清洗代價(jià)最小。

上面描述的算法均假設(shè)給出的完整性約束是正確的，但是隨著數(shù)據(jù)的集成和業(yè)務(wù)規(guī)則的變化，約束也可能隨著時(shí)間的推移而發(fā)生變化，若使用過時(shí)或錯(cuò)誤的約束來清洗關(guān)系表，不但無法正確地修復(fù)錯(cuò)誤數(shù)據(jù)，還可能把正確數(shù)據(jù)修改錯(cuò)誤。因此，學(xué)術(shù)界提出了數(shù)據(jù)和約束統(tǒng)一清洗的模型[56, 76-77]。

Chiang等提出的URM模型(unified repair model)[56]利用了最小描述長(zhǎng)度原則[78-79]，即給定一組函數(shù)依賴Σ，找到一個(gè)模型M，它可以利用最小的描述長(zhǎng)度來表示關(guān)系表I。模型M的描述長(zhǎng)度DL(M)=L(M)+L(I|M)。其中：L(M)是模型M的長(zhǎng)度，L(I|M)是給定模型M后關(guān)系表I的長(zhǎng)度。給定函數(shù)依賴X→Y，L(M)=|X∪Y|·S，L(I|M)=|X∪Y|·E。其中：|X∪Y|表示函數(shù)依賴中包含的屬性個(gè)數(shù)，S表示模型M中的簽名個(gè)數(shù)，E表示關(guān)系表I中不能用簽名表示的元組個(gè)數(shù)。在數(shù)據(jù)清洗方面，URM模型以元組模式為單位來修復(fù)數(shù)據(jù)，元組模式p∈ΠXY(t)表示元組t在函數(shù)依賴X→Y相關(guān)屬性上的投影。URM模型還定義了核心元組模式和異常元組模式，分別表示出現(xiàn)頻率高于和低于指定閾值的元組模式，異常元組模式會(huì)被修改成和它足夠相似且對(duì)應(yīng)清洗代價(jià)最小的核心元組模式。由于核心元組模式就是模型M中的簽名，因此這個(gè)過程可以降低描述長(zhǎng)度。在約束修復(fù)方面，URM支持在函數(shù)依賴的左端X增加屬性，以增強(qiáng)約束的滿足條件。完整性約束的修改可以增加核心元組模式的個(gè)數(shù)，降低異常元組模式的個(gè)數(shù)，因此也可以降低模型的描述長(zhǎng)度。對(duì)于原始數(shù)據(jù)表中的沖突，URM中定義了代價(jià)模型來衡量數(shù)據(jù)清洗和約束清洗的代價(jià)，并選擇清洗代價(jià)較小的修復(fù)方式。Beskales等的工作[76]也支持?jǐn)?shù)據(jù)和約束的統(tǒng)一清洗，但與URM模型不同的是，該工作首先根據(jù)給定條件清洗完整性約束，再利用清洗后的約束指導(dǎo)數(shù)據(jù)的清洗。

Volkovs等提出了連續(xù)數(shù)據(jù)清洗算法[77]以應(yīng)對(duì)數(shù)據(jù)和約束會(huì)發(fā)生變化的動(dòng)態(tài)環(huán)境。該算法首先利用用戶的清洗記錄訓(xùn)練分類器，給定一組沖突后，該分類器可以決定通過何種清洗策略來消除沖突：修改數(shù)據(jù)、修改約束還是數(shù)據(jù)和約束同時(shí)修改。確定清洗策略后，該算法利用代價(jià)模型計(jì)算出一組代價(jià)較小的清洗措施，并交由用戶作最終判斷，用戶的決定可以用來修正分類器。在動(dòng)態(tài)數(shù)據(jù)環(huán)境中，該算法可以通過統(tǒng)計(jì)信息捕獲數(shù)據(jù)分布和約束的變化，以支持分類器進(jìn)行正確的策略分類。

3.2 基于規(guī)則的數(shù)據(jù)清洗

數(shù)據(jù)清洗規(guī)則在工業(yè)界被廣泛利用。這里主要論述4種數(shù)據(jù)清洗規(guī)則，分別是編輯規(guī)則[23-24]、修復(fù)規(guī)則[21-22]、Sherlock規(guī)則[25]和探測(cè)規(guī)則[26-27]。這4種規(guī)則的形式化定義已在第2.2節(jié)中給出。

規(guī)則執(zhí)行前需要探究規(guī)則具有的性質(zhì)，這些性質(zhì)包括：1)終止性，即給定一組規(guī)則Σ，它們?cè)谌我庠M上執(zhí)行都能夠達(dá)到清洗終止點(diǎn)。經(jīng)證明，上述4種規(guī)則均可滿足終止性。2)一致性，即給定一組規(guī)則Σ，它們?cè)谌我庠M上按照不同的順序執(zhí)行可以得到相同的清洗結(jié)果。經(jīng)證明，驗(yàn)證修復(fù)規(guī)則是否滿足一致性是多項(xiàng)式時(shí)間內(nèi)可以解決的，但其余3種規(guī)則的驗(yàn)證復(fù)雜度均是co-NP難。3)決定性，即給定一組規(guī)則Σ，它們?cè)谌我庠M上所有可終止的清洗過程均會(huì)得到相同的清洗結(jié)果。經(jīng)證明，滿足一致性的規(guī)則集合均可以滿足決定性。4)蘊(yùn)含性，即給定一組規(guī)則Σ和不在Σ中的規(guī)則φ，Σ∪{φ}滿足一致性且對(duì)于任意元組t，執(zhí)行Σ和Σ∪{φ}得到的清洗結(jié)果是相同的，也就是說規(guī)則φ蘊(yùn)含在規(guī)則集Σ中。經(jīng)證明，驗(yàn)證修復(fù)規(guī)則、Sherlock規(guī)則和探測(cè)規(guī)則的蘊(yùn)含性的復(fù)雜度均是co-NP難。

編輯規(guī)則的執(zhí)行需要定義域(Z, T)，其中Z是R中的一組屬性，T是元組在屬性組Z上需要滿足的模式。當(dāng)t[Z]是正確的，即t[Z]滿足Tc中定義的某種模式時(shí)，編輯規(guī)則才能正確修復(fù)元組t中的錯(cuò)誤，因此計(jì)算編輯規(guī)則的可執(zhí)行域是編輯規(guī)則執(zhí)行的首要目標(biāo)。修復(fù)規(guī)則、Sherlock規(guī)則和探測(cè)規(guī)則在執(zhí)行時(shí)同時(shí)會(huì)標(biāo)記數(shù)據(jù)：POS(t)是元組t中確定正確的屬性值；NEG(t)是元組t中確定錯(cuò)誤的屬性值；FREE(t)是元組t中正確性未知的屬性值。在規(guī)則執(zhí)行前，所有屬性均標(biāo)記為FREE；當(dāng)規(guī)則正確執(zhí)行后，證據(jù)屬性X(探測(cè)規(guī)則中的col(Ve))標(biāo)記為POS；負(fù)面屬性B(探測(cè)規(guī)則中的col(Vn))標(biāo)記為NEG；若屬性B可以被正確修復(fù)(主數(shù)據(jù)和知識(shí)庫(kù)中可以找到對(duì)應(yīng)的值)，B會(huì)標(biāo)記為POS。標(biāo)記為POS的屬性不再被改動(dòng)。從上述過程可以看出，若規(guī)則集滿足一致性，那么修復(fù)規(guī)則、Sherlock規(guī)則和探測(cè)規(guī)則的執(zhí)行算法是基于Chase的算法，即在每一步選擇一個(gè)可以執(zhí)行的規(guī)則，直到元組的標(biāo)記不再被規(guī)則集修改。此外，還可以建立倒排索引或者進(jìn)行規(guī)則排序來增加規(guī)則的執(zhí)行效率。

3.3 基于統(tǒng)計(jì)的數(shù)據(jù)清洗

基于統(tǒng)計(jì)的錯(cuò)誤檢測(cè)算法[4-6]把數(shù)據(jù)清洗問題轉(zhuǎn)換為統(tǒng)計(jì)學(xué)習(xí)和推理問題，其大致流程如圖 4所示。臟數(shù)據(jù)中的每一個(gè)屬性值都可以表示成一個(gè)隨機(jī)變量，若屬性值是錯(cuò)誤的，該隨機(jī)變量為不確定的值；若屬性值是正確的，該隨機(jī)變量為定值，可以作為訓(xùn)練數(shù)據(jù)來訓(xùn)練概率模型。此外，完整性約束或參照數(shù)據(jù)都會(huì)被轉(zhuǎn)換為推理規(guī)則融入到概率模型中，以獲得關(guān)于輸入數(shù)據(jù)的一系列定量統(tǒng)計(jì)，例如屬性值對(duì)的共現(xiàn)統(tǒng)計(jì)。

圖 4 基于統(tǒng)計(jì)的數(shù)據(jù)修復(fù)[4]

對(duì)于每個(gè)隨機(jī)變量，算法計(jì)算它的最大后驗(yàn)值以及其屬性域中所有值的概率分布，若有用戶的參與，屬性域的概率分布可用于獲得用戶的反饋以進(jìn)一步訓(xùn)練概率模型。這些算法也可以用來推測(cè)缺失值。

3.4 人機(jī)結(jié)合的數(shù)據(jù)清洗

Yakout等提出的GDR(guided data repair)模型[67]是較為經(jīng)典的人機(jī)結(jié)合數(shù)據(jù)清洗模型，該模型流程圖如圖 5所示。

圖 5 GDR模型流程圖[67]

GDR模型的輸入是數(shù)據(jù)庫(kù)中的關(guān)系表和一組條件函數(shù)依賴。首先，該模型檢測(cè)出在條件函數(shù)依賴上存在沖突的臟數(shù)據(jù)并利用現(xiàn)有算法[72]計(jì)算出臟數(shù)據(jù)可能的清洗方式，加入到更新列表中。更新列表里的數(shù)據(jù)的結(jié)構(gòu)為＜t, A, v, s＞。其中：v是屬性值t[A]一種可能的清洗方式，s代表這條數(shù)據(jù)清洗措施的置信度。接下來，將更新列表中所有的清洗方式分組后排序，獲得收益最大的組會(huì)被首先呈現(xiàn)給用戶，由用戶決定是否執(zhí)行組內(nèi)的數(shù)據(jù)更新。所有被用戶確定的數(shù)據(jù)更新會(huì)立刻執(zhí)行，GDR也會(huì)重新檢測(cè)關(guān)系表中是否出現(xiàn)了新的數(shù)據(jù)沖突。

為了減輕用戶負(fù)擔(dān)，用戶的決策作為訓(xùn)練集被用于訓(xùn)練機(jī)器學(xué)習(xí)模型。當(dāng)新的數(shù)據(jù)清洗策略到來時(shí)，由該模型首先判斷這些清洗策略是否可以執(zhí)行，因此最終呈現(xiàn)給用戶的除了清洗策略外還有該機(jī)器學(xué)習(xí)模型的判定結(jié)果。用戶對(duì)某些清洗策略的判定結(jié)果給出反饋，修正其中的錯(cuò)誤判定并重新訓(xùn)練學(xué)習(xí)模型，直到該模型的判定結(jié)果與用戶一致或者所有的清洗策略都被用戶作出判定。

FALCON系統(tǒng)[80]也是人機(jī)結(jié)合的數(shù)據(jù)清洗系統(tǒng)，不同于GDR的是，F(xiàn)ALCON不依賴任何數(shù)據(jù)清洗規(guī)則，而是單純通過與用戶的交互來修復(fù)數(shù)據(jù)。用戶更新了某個(gè)屬性值后，F(xiàn)ALCON可以通過用戶的決策來猜測(cè)其他可能的更新并交由用戶判斷是否可以執(zhí)行。

該系統(tǒng)的執(zhí)行流程如圖 6[80]所示。用戶首先檢測(cè)數(shù)據(jù)噪聲并提供關(guān)系表上的數(shù)據(jù)修復(fù)措施Δ。給定Δ后，F(xiàn)ALCON生成一組數(shù)據(jù)更新策略，它包含的SQL UPDATE語句更少，同時(shí)還可以修復(fù)數(shù)據(jù)中更多的錯(cuò)誤。接下來，F(xiàn)ALCON從這組語句中選擇一個(gè)有效性未知的語句Q，交由用戶判斷是否可以執(zhí)行。如果Q可以執(zhí)行，那么它會(huì)被用來修復(fù)關(guān)系表中的數(shù)據(jù)錯(cuò)誤。FALCON可以利用Q的執(zhí)行情況過濾掉一定不會(huì)被執(zhí)行的更新策略，從而提高系統(tǒng)效率。表 3對(duì)4類數(shù)據(jù)清洗算法進(jìn)行了匯總。

圖 6 FALCON系統(tǒng)[80]

表 3 數(shù)據(jù)清洗算法匯總

數(shù)據(jù)清洗方式 相關(guān)算法 適用范圍 優(yōu)點(diǎn) 缺點(diǎn) 基于完整性約束 ①僅清洗數(shù)據(jù)：局部清洗算法[55, 58, 72, 74]和全局清洗算法[57]
②數(shù)據(jù)和約束統(tǒng)一清洗算法[56, 76-77] 存在完整性約束的關(guān)系表，數(shù)據(jù)有一定的重復(fù)度 不需要依賴主數(shù)據(jù)、知識(shí)庫(kù)、用戶等外部資源 數(shù)據(jù)清洗算法是啟發(fā)式的，有時(shí)無法找到正確的數(shù)據(jù)修復(fù)方式 基于規(guī)則 ①編輯規(guī)則[23-24]
②修復(fù)規(guī)則[21-22]
③ Sherlock規(guī)則[25]
④探測(cè)規(guī)則[26-27] 關(guān)系表被主數(shù)據(jù)或知識(shí)庫(kù)覆蓋 規(guī)則可以指明錯(cuò)誤的屬性值及其修復(fù)方式，準(zhǔn)確度高 依賴外部資源，若主數(shù)據(jù)或知識(shí)庫(kù)中存在知識(shí)缺失，就無法檢測(cè)和修復(fù)關(guān)系表中的錯(cuò)誤 基于統(tǒng)計(jì) ① HoloClean[4]
② ERACER[5]
③ SCARE[6] 關(guān)系表中的數(shù)據(jù)有一定的統(tǒng)計(jì)規(guī)律 可用于缺失值的推測(cè) 需要大量的標(biāo)注數(shù)據(jù)、效率低 人機(jī)結(jié)合 ① GDR[67]
② FALCON[80] 存在可以參與清洗過程的用戶 準(zhǔn)確度高 需要用戶的大量投入

4 常用測(cè)評(píng)數(shù)據(jù)集

用于數(shù)據(jù)清洗質(zhì)量測(cè)評(píng)的真實(shí)臟數(shù)據(jù)集分為有人工標(biāo)注錯(cuò)誤數(shù)據(jù)的臟數(shù)據(jù)集和無人工標(biāo)注的臟數(shù)據(jù)集。下面介紹幾種常用的測(cè)評(píng)數(shù)據(jù)集：

1) RESTAURANT：有人工標(biāo)注的檢測(cè)數(shù)據(jù)冗余的常用數(shù)據(jù)集。該數(shù)據(jù)集包含858條、36萬對(duì)餐館信息，其中106對(duì)數(shù)據(jù)指代的是同一個(gè)餐館，即冗余數(shù)據(jù)。

2) WEBTABLE：檢測(cè)錯(cuò)誤數(shù)據(jù)常用的數(shù)據(jù)集。WEBTABLE包含兩組網(wǎng)頁表格，分別是WWT和WEX。WWT有人工標(biāo)注，包含6 318個(gè)網(wǎng)頁表格；WEX無人工標(biāo)注，包含24萬個(gè)網(wǎng)頁表格。

3) PIMA IND.DIA.：來自UCI-ML REPOSITORY的數(shù)據(jù)集，可用于檢測(cè)偽裝缺失值。該數(shù)據(jù)集包含768條記錄，臟數(shù)據(jù)沒有被人工標(biāo)出。

除此之外，常用于注入噪聲的干凈數(shù)據(jù)集有：

1) HOSPITAL：來自美國(guó)衛(wèi)生署，檢測(cè)數(shù)據(jù)沖突常用的數(shù)據(jù)集。該數(shù)據(jù)集包含11萬條關(guān)于醫(yī)院信息的記錄，每條記錄包含19個(gè)屬性。該數(shù)據(jù)集上有9個(gè)函數(shù)依賴。

2) TAX：檢測(cè)數(shù)據(jù)沖突常用的數(shù)據(jù)生成器，可生成任意條記錄。該數(shù)據(jù)集存儲(chǔ)了個(gè)人的地址和納稅信息，每條記錄包含13個(gè)屬性。該數(shù)據(jù)集上有9個(gè)函數(shù)依賴。

用于生成數(shù)據(jù)噪聲的工具有：

1) BART[81]：它是注入數(shù)據(jù)噪聲的基準(zhǔn)程序，支持注入拼寫錯(cuò)誤、冗余數(shù)據(jù)、離群數(shù)據(jù)和缺失數(shù)據(jù)。除此之外，BART還可以根據(jù)用戶輸入的否定約束生成數(shù)據(jù)噪聲。很多清洗規(guī)則都可以轉(zhuǎn)換成否定約束，例如函數(shù)依賴、條件函數(shù)依賴、修復(fù)規(guī)則等。BART還允許用戶聲明某些數(shù)據(jù)是不可變動(dòng)的，因此間接支持了編輯規(guī)則。

2) QNOISE：它是一種基于Java的噪聲數(shù)據(jù)生成器，由卡塔爾計(jì)算研究所的數(shù)據(jù)分析小組開發(fā)。QNOISE支持注入如下4種類型的噪聲：空數(shù)據(jù)(NULL)、偽缺失數(shù)據(jù)、冗余數(shù)據(jù)和基于特定完整性約束的沖突數(shù)據(jù)。

5 機(jī)遇與挑戰(zhàn)

盡管在結(jié)構(gòu)化數(shù)據(jù)的清洗方面已經(jīng)有了很多豐碩的研究成果，但目前在這一課題上仍然存在許多亟待解決的問題。大數(shù)據(jù)時(shí)代的來臨和新興技術(shù)的發(fā)展為數(shù)據(jù)清洗帶來了新的機(jī)遇與挑戰(zhàn)，概括下來有以下幾個(gè)方面：

1) 標(biāo)準(zhǔn)測(cè)試集。數(shù)據(jù)清洗領(lǐng)域缺少大規(guī)模的標(biāo)準(zhǔn)測(cè)試集，這使得無法統(tǒng)一衡量數(shù)據(jù)清洗算法的優(yōu)劣。目前的實(shí)驗(yàn)測(cè)評(píng)多是依賴噪聲生成工具或由測(cè)評(píng)人員人工標(biāo)注臟數(shù)據(jù)中的錯(cuò)誤。噪聲生成工具無法完全模擬真實(shí)世界中的數(shù)據(jù)錯(cuò)誤，而通過人工標(biāo)注方式生成的臟數(shù)據(jù)往往數(shù)據(jù)量小，無法全面衡量清洗算法的效率，因此如何獲取標(biāo)準(zhǔn)測(cè)試集是當(dāng)前亟待解決一個(gè)問題。

2) 對(duì)大數(shù)據(jù)的支持。大數(shù)據(jù)具有數(shù)據(jù)量大、類型繁多和數(shù)據(jù)增長(zhǎng)速度快等特點(diǎn)。如何把數(shù)據(jù)清洗技術(shù)應(yīng)用于數(shù)據(jù)量大且快速增長(zhǎng)的數(shù)據(jù)集是在大數(shù)據(jù)時(shí)代面臨的首要挑戰(zhàn)。在大數(shù)據(jù)場(chǎng)景下，還需解決分布式存儲(chǔ)數(shù)據(jù)、在線增量式數(shù)據(jù)和多租戶共享數(shù)據(jù)的清洗問題，但是這些領(lǐng)域的數(shù)據(jù)清洗工作較少且大多依賴于定量分析，如何保證高質(zhì)量的確定性修復(fù)仍是值得研究的方向。另外，數(shù)據(jù)清洗的過程通常會(huì)包含很多代價(jià)極高的操作，比如枚舉元組對(duì)、處理不等式連接等。目前的算法加速策略多是構(gòu)建數(shù)據(jù)索引[21, 26]、數(shù)據(jù)分區(qū)[82]和抽樣數(shù)據(jù)清洗[83-84]，但是這些技術(shù)仍然無法完全滿足大數(shù)據(jù)時(shí)代的需求，新的可擴(kuò)展性技術(shù)有待研發(fā)。

3) 眾包技術(shù)在數(shù)據(jù)清洗上的應(yīng)用。眾包技術(shù)[7-8, 85-86]可以集中眾多用戶的知識(shí)和決策，提高數(shù)據(jù)清洗的效率，在數(shù)據(jù)清洗方面有著不可替代的優(yōu)勢(shì)。目前已有工作利用眾包系統(tǒng)進(jìn)行數(shù)據(jù)去重[7, 87]、清洗多版本數(shù)據(jù)[88]。除上述應(yīng)用外，當(dāng)數(shù)據(jù)清洗所依賴的主數(shù)據(jù)和知識(shí)庫(kù)存在缺失或錯(cuò)誤時(shí)，也可以利用眾包用戶補(bǔ)全、糾正信息，以及清洗關(guān)系表。當(dāng)需要從臟數(shù)據(jù)中學(xué)習(xí)出數(shù)據(jù)清洗規(guī)則時(shí)，可以利用眾包用戶標(biāo)注數(shù)據(jù)、檢測(cè)規(guī)則的有效性和適用性。讓眾包用戶替代傳統(tǒng)清洗算法中的領(lǐng)域?qū)＜?，需要設(shè)計(jì)有效的數(shù)據(jù)分組策略和答案整合策略。但是，由于眾包用戶的專業(yè)程度有限，基于眾包的數(shù)據(jù)清洗算法必須有一定的檢錯(cuò)容錯(cuò)機(jī)制。

4) 深度學(xué)習(xí)技術(shù)在數(shù)據(jù)清洗上的應(yīng)用。深度學(xué)習(xí)是當(dāng)下熱門技術(shù)，已經(jīng)在許多領(lǐng)域展現(xiàn)了其不可替代的優(yōu)勢(shì)，例如計(jì)算機(jī)視覺、自然語言處理等。深度學(xué)習(xí)技術(shù)在這些領(lǐng)域上的成功使得許多學(xué)者尋求將其應(yīng)用于計(jì)算機(jī)其他領(lǐng)域，其中也包括結(jié)構(gòu)化數(shù)據(jù)清洗。目前，機(jī)器學(xué)習(xí)技術(shù)在數(shù)據(jù)清洗上的應(yīng)用多是通過數(shù)理統(tǒng)計(jì)推測(cè)真值或者訓(xùn)練分類樹以決定某項(xiàng)數(shù)據(jù)更新是否執(zhí)行。若要利用深度學(xué)習(xí)技術(shù)完成更加復(fù)雜的數(shù)據(jù)清洗任務(wù)，就必須要像計(jì)算機(jī)視覺中的卷積神經(jīng)網(wǎng)絡(luò)(CNN)和自然語言處理中的遞歸神經(jīng)網(wǎng)絡(luò)(RNN)一樣設(shè)計(jì)新的適用于數(shù)據(jù)清洗的深度學(xué)習(xí)模型。同時(shí)，還要解決數(shù)據(jù)表示的問題，即如何把某一個(gè)元組、某一列甚至某一個(gè)關(guān)系表轉(zhuǎn)換成向量表示。

5) 跨領(lǐng)域的數(shù)據(jù)清洗。數(shù)據(jù)清洗規(guī)則和策略的學(xué)習(xí)是一項(xiàng)耗時(shí)的工作，它需要大量的歷史數(shù)據(jù)和人工投入。若通過遷移學(xué)習(xí)技術(shù)[89]，使獲得的清洗規(guī)則和策略應(yīng)用到其他領(lǐng)域的數(shù)據(jù)集上，那么將大大減少數(shù)據(jù)清洗的開銷。因此，跨領(lǐng)域的數(shù)據(jù)清洗是日后很有研究?jī)r(jià)值的一個(gè)方向。

6) 私密數(shù)據(jù)的清洗。許多數(shù)據(jù)中包含著個(gè)人的隱私信息，例如金融數(shù)據(jù)和醫(yī)學(xué)數(shù)據(jù)，而數(shù)據(jù)清洗本身是一項(xiàng)需要檢查和還原原始數(shù)據(jù)的任務(wù)。當(dāng)原始數(shù)據(jù)無法直接訪問，而只能獲取到加密或者轉(zhuǎn)換后的數(shù)據(jù)時(shí)，一項(xiàng)重要的工作就是依然能從這些數(shù)據(jù)中檢測(cè)出錯(cuò)誤信息，并進(jìn)行數(shù)據(jù)糾正，修復(fù)后的數(shù)據(jù)經(jīng)過解密或者轉(zhuǎn)換后，就是表達(dá)真實(shí)用戶信息的干凈數(shù)據(jù)。

6 總結(jié)

本文在對(duì)結(jié)構(gòu)化數(shù)據(jù)清洗的相關(guān)概念和算法進(jìn)行深入研究的基礎(chǔ)上，總結(jié)了4類結(jié)構(gòu)化數(shù)據(jù)中常見的數(shù)據(jù)噪聲以及相應(yīng)的檢測(cè)方法，包括數(shù)據(jù)缺失、數(shù)據(jù)冗余、數(shù)據(jù)沖突和數(shù)據(jù)錯(cuò)誤。臟數(shù)據(jù)中包含多種類型的數(shù)據(jù)噪聲，因此本文從消除的方式上把數(shù)據(jù)清洗算法分為基于完整性約束的清洗算法、基于規(guī)則的清洗算法、基于統(tǒng)計(jì)的清洗算法和人機(jī)結(jié)合的清洗算法，并總結(jié)了各類算法的適用范圍和優(yōu)缺點(diǎn)。最后，本文還探討了大數(shù)據(jù)時(shí)代的來臨和新興技術(shù)的發(fā)展對(duì)數(shù)據(jù)清洗帶來的機(jī)遇與挑戰(zhàn)，以期促進(jìn)數(shù)據(jù)清洗技術(shù)在大數(shù)據(jù)時(shí)代穩(wěn)步發(fā)展。

參考文獻(xiàn)

[1]

SHALLCROSS S. 2 Reasons why your data is lying to you[R/OL]. (2016-09-15)[2018-06-25]. http://hollistibbetts.sys-con.com/node/1975126.

[2]

BUCKLEY J. Causes of dirty data and how to combat them[R/OL]. (2018-07-13)[2018-06-25]. https://www.qubole.com/blog/causes-of-dirty-data-and-how-to-combat-them.

[3]

GALHARDAS H, FLORESCU D, SHASHA D, et al. An extensible framework for data cleaning[C]//IEEE 16th International Conference on Data Engineering. San Diego, USA, 2000.

[4]

REKATSINAS T, CHU X, ILYAS I F, et al. HoloClean:Holistic data repairs with probabilistic inference[J]. Proceedings of the VLDB Endowment, 2017, 10(11): 1190-1201. DOI:10.14778/3137628

[5]

MAYFIELD C, NEVILLE J, PRABHAKAR S. ERACER: A database approach for statistical inference and data cleaning[C]//2010 ACM SIGMOD International Conference on Management of Data. Indianapolis, USA, 2010: 75-86.

[6]

YAKOUT M, BERTI-éQUILLE L, ELMAGARMID A K. Don't be SCAREd: Use scalable automatic repairing with maximal likelihood and bounded changes[C]//2013 ACM SIGMOD International Conference on Management of Data. New York, USA, 2013: 553-564.

[7]

WANG J N, KRASKA T, FRANKLIN M J, et al. CrowdER:Crowdsourcing entity resolution[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1483-1494. DOI:10.14778/2350229

[8]

CHAI C, LI G L, LI J, et al. Cost-effective crowdsourced entity resolution: A partial-order approach[C]//2016 International Conference on Management of Data. San Francisco, USA, 2016: 969-984.

[9]

郭志懋, 周傲英. 數(shù)據(jù)質(zhì)量和數(shù)據(jù)清洗研究綜述[J]. 軟件學(xué)報(bào), 2002, 13(11): 2076-2082.
GUO Z M, ZHOU A Y. Research on data quality and data cleaning:A survey[J]. Journal of Software, 2002, 13(11): 2076-2082. (in Chinese)

[10]

楊輔祥, 劉云超, 段智華. 數(shù)據(jù)清理綜述[J]. 計(jì)算機(jī)應(yīng)用研究, 2002, 19(3): 3-5.
YANG F X, LIU Y C, DUAN Z H. An overview of data cleaning[J]. Application Research of Computers, 2002, 19(3): 3-5. DOI:10.3969/j.issn.1001-3695.2002.03.002 (in Chinese)

[11]

王曰芬, 章成志, 張蓓蓓, 等. 數(shù)據(jù)清洗研究綜述[J]. 現(xiàn)代圖書情報(bào)技術(shù), 2007, 2(12): 50-56.
WANG Y F, ZHANG C Z, ZHANG B B, et al. A survey of data cleaning[J]. New Technology of Library and Information Service, 2007, 2(12): 50-56. (in Chinese)

[12]

趙一凡, 卞良, 叢昕. 數(shù)據(jù)清洗方法研究綜述[J]. 軟件導(dǎo)刊, 2017(12): 222-224.
ZHAO Y F, BIAN L, CONG X. Survey of data cleaning method in data preprocessing[J]. Software Guide, 2017(12): 222-224. (in Chinese)

[13]

ELMAGARMID A K, IPEIROTIS P G, VERYKIOS V S. Duplicate record detection:A survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(1): 1-16. DOI:10.1109/TKDE.2007.250581

[14]

CHU X, ILYAS I F, KRISHNAN S, et al. Data cleaning: Overview and emerging challenges[C]//2016 International Conference on Management of Data. San Francisco, USA, 2016: 2201-2206.

[15]

ILYAS I F, CHU X. Trends in cleaning relational data:Consistency and deduplication[J]. Foundations and Trends in Databases, 2015, 5(4): 281-393. DOI:10.1561/1900000045

[16]

FAN W F, GEERTS F, JIA X B, et al. Conditional functional dependencies for capturing data inconsistencies[J]. ACM Transactions on Database Systems (TODS), 2008, 33(2): 6.

[17]

BOHANNON P, FAN W F, GEERTS F, et al. Conditional functional dependencies for data cleaning[C]//IEEE 23rd International Conference on Data Engineering. Istanbul, Turkey, 2007: 746-755.

[18]

ABITEBOUL S, HULL R, VIANU V. Foundations of databases:The logical level[M]. Boston, USA: Addison-Wesley Longman Publishing, 1995.

[19]

KOUDAS N, SAHA A, SRIVASTAVA D, et al. Metric functional dependencies[C]//IEEE 25th International Conference on Data Engineering. Shanghai, China, 2009: 1275-1278.

[20]

SONG S X, CHEN L. Differential dependencies:Reasoning and discovery[J]. ACM Transactions on Database Systems (TODS), 2011, 36(3): 16.

[21]

WANG J N, TANG N. Towards dependable data repairing with fixing rules[C]//2014 ACM SIGMOD International Conference on Management of Data. Snowbird, USA, 2014: 457-468.

[22]

WANG J N, TANG N. Dependable data repairing with fixing rules[J]. Journal of Data and Information Quality (JDIQ), 2017, 8(3-4): 16.

[23]

FAN W F, LI J Z, MA S, et al. Towards certain fixes with editing rules and master data[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2): 173-184. DOI:10.14778/1920841

[24]

FAN W F, LI J Z, MA S, et al. Towards certain fixes with editing rules and master data[J]. The VLDB Journal, 2012, 21(2): 213-238. DOI:10.1007/s00778-011-0253-7

[25]

INTERLANDI M, TANG N. Proof positive and negative in data cleaning[C]//IEEE 31st International Conference on Data Engineering. Seoul, Republic of Korea, 2015: 18-29.

[26]

HAO S, TANG N, LI G L, et al. Cleaning relations using knowledge bases[C]//IEEE 33rd International Conference on Data Engineering. San Diego, USA, 2017: 933-944.

[27]

HAO S, TANG N, LI G L, et al. Distilling relations using knowledge bases[J]. The VLDB Journal, 2018, 27(4): 497-519. DOI:10.1007/s00778-018-0506-9

[28]

HUA M, PEI J. DiMaC: A disguised missing data cleaning tool[C]//14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas, USA, 2008: 1077-1080.

[29]

QAHTAN A A, ELMAGARMID A, CASTRO FERNANDEZ R, et al. FAHES: A robust disguised missing values detector[C]//24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. London, UK, 2018: 2100-2109.

[30]

K?PCKE H, RAHM E. Frameworks for entity matching:A comparison[J]. Data & Knowledge Engineering, 2010, 69(2): 197-210.

[31]

HE Q L, LI Z H, ZHANG X. Data deduplication techniques[C]//2010 IEEE International Conference on Future Information Technology and Management Engineering (FITME). Changzhou, China, 2010: 430-433.

[32]

BAXTER R, CHRISTEN P, CHURCHES T. A comparison of fast blocking methods for record linkage[C]//2003 KDD Workshop on Data Cleaning, Record Linkage, and Object Consolidation. Washington, DC, USA, 2003, 3: 25-27.

[33]

TEJADA S, KNOBLOCK C A, MINTON S. Learning object identification rules for information integration[J]. Information Systems, 2001, 26(8): 607-633. DOI:10.1016/S0306-4379(01)00042-4

[34]

ELFEKY M G, VERYKIOS V S, ELMAGARMID A K. TAILOR: A record linkage toolbox[C]//18th International Conference on Data Engineering. San Jose, USA, 2002.

[35]

TEJADA S, KNOBLOCK C A, MINTON S. Learning domain-independent string transformation weights for high accuracy object identification[C]//International Conference on Knowledge Discovery and Data Mining. Edmonton, Canada, 2002: 350-359.

[36]

CHRISTEN P. Febrl: A freely available record linkage system with a graphical user interface[C]//2nd Australasian Workshop on Health Data and Knowledge Management. Wollongong, Australia, 2008: 17-25.

[37]

MCCALLUM A, NIGAM K, UNGAR L H. Efficient clustering of high-dimensional data sets with application to reference matching[C]//6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Boston, USA, 2000: 169-178.

[38]

BAYARDO R J, MA Y M, SRIKANT R. Scaling up all pairs similarity search[C]//16th International Conference on World Wide Web. Banff, Canada, 2007: 131-140.

[39]

CHAUDHURI S, GANTI V, KAUSHIK R. A primitive operator for similarity joins in data cleaning[C]//22nd International Conference on Data Engineering. Atlanta, USA, 2006.

[40]

XIAO C, WANG W, LIN X M, et al. Efficient similarity joins for near-duplicate detection[J]. ACM Transactions on Database Systems (TODS), 2011, 36(3): 15.

[41]

ARASU A, Ré C, SUCIU D. Large-scale deduplication with constraints using Dedupalog[C]//2009 IEEE 25th International Conference on Data Engineering. Shanghai, China, 2009: 952-963.

[42]

HERNáNDEZ M A, STOLFO S J. The merge/purge problem for large databases[C]//1995 ACM SIGMOD International Conference on Management of Data. San Jose, USA, 1995: 127-138.

[43]

LEE M L, LING T W, LOW W L. IntelliClean: A knowledge-based intelligent data cleaner[C]//Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Boston, USA, 2000: 290-294.

[44]

WANG J N, LI G L, YU J X, et al. Entity matching:How similar is similar[J]. Proceedings of the VLDB Endowment, 2011, 4(10): 622-633. DOI:10.14778/2021017

[45]

BILENKO M, MOONEY R J. Adaptive duplicate detection using learnable string similarity measures[C]//Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, DC, USA, 2003: 39-48.

[46]

PAPENBROCK T, EHRLICH J, MARTEN J, et al. Functional dependency discovery:An experimental evaluation of seven algorithms[J]. Proceedings of the VLDB Endowment, 2015, 8(10): 1082-1093. DOI:10.14778/2794367

[47]

LIU J X, LI J Y, LIU C F, et al. Discover dependencies from data:A review[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(2): 251-264. DOI:10.1109/TKDE.2010.197

[48]

HUHTALA Y, K?RKK?INEN J, PORKKA P, et al. TANE:An efficient algorithm for discovering functional and approximate dependencies[J]. The Computer Journal, 1999, 42(2): 100-111.

[49]

YAO H, HAMILTON H J. Mining functional dependencies from data[J]. Data Mining and Knowledge Discovery, 2008, 16(2): 197-219.

[50]

NOVELLI N, CICCHETTI R. FUN: An efficient algorithm for mining functional and embedded dependencies[C]//International Conference on Database Theory. London, UK, 2001: 189-203.

[51]

WYSS C, GIANNELLA C, ROBERTSON E. FastFDs: A heuristic-driven, depth-first algorithm for mining functional dependencies from relation instances extended abstract[C]//International Conference on Data Warehousing and Knowledge Discovery. Munich, Germany, 2001: 101-110.

[52]

LOPES S, PETIT J M, LAKHAL L. Efficient discovery of functional dependencies and Armstrong relations[C]//International Conference on Extending Database Technology. Konstanz, Germany, 2000: 350-364.

[53]

FAN W F, GEERTS F, LI J Z, et al. Discovering conditional functional dependencies[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(5): 683-698. DOI:10.1109/TKDE.2010.154

[54]

DE MARCHI F, LOPES S, PETIT J M. Efficient algorithms for mining inclusion dependencies[C]//8th International Conference on Extending Database Technology. Prague, Czech Republic, 2002: 464-476.

[55]

BOHANNON P, FAN W F, FLASTER M, et al. A cost-based model and effective heuristic for repairing constraints by value modification[C]//2005 ACM SIGMOD International Conference on Management of Data. Baltimore, USA, 2005: 143-154.

[56]

CHIANG F, MILLER R J. A unified model for data and constraint repair[C]//2011 IEEE 27th International Conference on Data Engineering. Hannover, Germany, 2011: 446-457.

[57]

CHU X, ILYAS I F, PAPOTTI P. Holistic data cleaning: Putting violations into context[C]//2013 IEEE 29th International Conference on Data Engineering (ICDE). Brisbane, Australia, 2013: 458-469.

[58]

KOLAHI S, LAKSHMANAN L V S. On approximating optimum repairs for functional dependency violations[C]//12th International Conference on Database Theory. St. Petersburg, Russia, 2009: 53-62.

[59]

HAO S, TANG N, LI G L, et al. A novel cost-based model for data repairing[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(4): 727-742. DOI:10.1109/TKDE.2016.2637928

[60]

ARENAS M, BERTOSSI L, CHOMICKI J. Consistent query answers in inconsistent databases[C]//18th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. Philadelphia, USA, 1999: 68-79.

[61]

BRAVO L, BERTOSSI L. Logic programs for consistently querying data integration systems[C]//18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 10-15.

[62]

CALí A, LEMBO D, ROSATI R. On the decidability and complexity of query answering over inconsistent and incomplete databases[C]//22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. San Diego, USA, 2003: 260-271.

[63]

CALI A, LEMBO D, ROSATI R. Query rewriting and answering under constraints in data integration systems[C]//18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 16-21.

[64]

CHOMICKI J, MARCINKOWSKI J. Minimal-change integrity maintenance using tuple deletions[J]. Information and Computation, 2005, 197(1-2): 90-121. DOI:10.1016/j.ic.2004.04.007

[65]

GERTZ M, LIPECK U W. A diagnostic approach for repairing constraint violations in databases[M]//JAJODIA S, LIST W, MCGREGOR G, et al, eds. Integrity and internal control in information systems. ⅡCIS 1997. Boston, USA: Springer, 1997, 1: 89-111

[66]

GRECO G, GRECO S, ZUMPANO E. A logical framework for querying and repairing inconsistent databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(6): 1389-1408. DOI:10.1109/TKDE.2003.1245280

[67]

YAKOUT M, ELMAGARMID A K, NEVILLE J, et al. Guided data repair[J]. Proceedings of the VLDB Endowment, 2011, 4(5): 279-289. DOI:10.14778/1952376

[68]

CHU X, MORCOS J, ILYAS I F, et al. KATARA: A data cleaning system powered by knowledge bases and crowdsourcing[C]//2015 ACM SIGMOD International Conference on Management of Data. Melbourne, Australia, 2015: 1247-1261.

[69]

COHEN W, RAVIKUMAR P, FIENBERG S. A comparison of string metrics for matching names and records[C]//KDD Workshop on Data Cleaning and Object Consolidation. Washington, DC, USA, 2003: 73-78.

[70]

JIANG Y, LI G L, FENG J H, et al. String similarity joins:An experimental evaluation[J]. Proceedings of the VLDB Endowment, 2014, 7(8): 625-636. DOI:10.14778/2732296

[71]

EBAID A, ELMAGARMID A, ILYAS I F, et al. NADEEF:A generalized data cleaning system[J]. Proceedings of the VLDB Endowment, 2013, 6(12): 1218-1221. DOI:10.14778/2536274

[72]

CONG G, FAN W F, GEERTS F, et al. Improving data quality: Consistency and accuracy[C]//33rd International Conference on Very Large Data Bases. Vienna, Austria, 2007: 315-326.

[73]

GEERTS F, MECCA G, PAPOTTI P, et al. The LLUNATIC data-cleaning framework[J]. Proceedings of the VLDB Endowment, 2013, 6(9): 625-636. DOI:10.14778/2536360

[74]

BESKALES G, ILYAS I F, GOLAB L. Sampling the repairs of functional dependency violations under hard constraints[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2): 197-207. DOI:10.14778/1920841

[75]

KHAYYAT Z, ILYAS I F, JINDAL A, et al. BIGDANSING: A system for big data cleansing[C]//2015 ACM SIGMOD International Conference on Management of Data. Melbourne, Australia, 2015: 1215-1230.

[76]

BESKALES G, ILYAS I F, GOLAB L, et al. On the relative trust between inconsistent data and inaccurate constraints[C]//2013 IEEE 29th International Conference on Data Engineering. Brisbane, Australia, 2013: 541-552.

[77]

VOLKOVS M, CHIANG F, SZLICHTA J, et al. Continuous data cleaning[C]//2014 IEEE 30th International Conference on Data Engineering. Chicago, USA, 2014: 244-255.

[78]

RISSANEN J. Modeling by shortest data description[J]. Automatica, 1978, 14(5): 465-471. DOI:10.1016/0005-1098(78)90005-5

[79]

COVER T M, THOMAS J A. Elements of information theory[M]. New York, USA: John Wiley & Sons, 1991.

[80]

HE J, VELTRI E, SANTORO D, et al. Interactive and deterministic data cleaning[C]//2016 International Conference on Management of Data. San Francisco, USA, 2016: 893-907.

[81]

AROCENA P C, GLAVIC B, MECCA G, et al. Messing up with BART:Error generation for evaluating data-cleaning algorithms[J]. Proceedings of the VLDB Endowment, 2015, 9(2): 36-47. DOI:10.14778/2850578

[82]

ANANTHAKRISHNA R, CHAUDHURI S, GANTI V. Eliminating fuzzy duplicates in data warehouses[C]//28th International Conference on Very Large Databases. Hong Kong, China, 2002: 586-597.

[83]

WANG J N, KRISHNAN S, FRANKLIN M J, et al. A sample-and-clean framework for fast and accurate query processing on dirty data[C]//2014 ACM SIGMOD International Conference on Management of Data. Snowbird, USA, 2014: 469-480.

[84]

KRISHNAN S, WANG J N, FRANKLIN M J, et al. SampleClean: Fast and reliable analytics on dirty data[C/OL]//Bulletin of the IEEE Computer Society Technical Committee on Data Engineering. 2015: 59-75[2018-06-19]. https://www.ocf.berkeley.edu/~sanjayk/old/pubs/sc.pdf.

[85]

LI G L, WANG J N, ZHENG Y D, et al. Crowdsourced data management: A survey[C]//2017 IEEE 33rd International Conference on Data Engineering. San Diego, USA, 2017: 39-40.

[86]

PARK H, WIDOM J. CrowdFill: Collecting structured data from the crowd[C]//2014 ACM SIGMOD International Conference on Management of Data. Snowbird, USA, 2014: 577-588.

[87]

WHANG S E, LOFGREN P, GARCIA-MOLINA H. Question selection for crowd entity resolution[J]. Proceedings of the VLDB Endowment, 2013, 6(6): 349-360. DOI:10.14778/2536336

[88]

TONG Y X, CAO C C, ZHANG C J, et al. CrowdCleaner: Data cleaning for multi-version data on the web via crowdsourcing[C]//2014 IEEE 30th International Conference on Data Engineering. Chicago, USA, 2014: 1182-1185.

[89]

MICHALSKI R S. A theory and methodology of inductive learning[M]//MICHALSKI R S, CARBONELL J G, MITCHELL T M. Machine learning. Berlin, Germany: Springer, 1983: 83-134.

相關(guān)知識(shí)

健康風(fēng)險(xiǎn)評(píng)估接口2
妊娠期糖尿病孕婦飲食行為改變特征及原因的質(zhì)性研究
機(jī)器學(xué)習(xí)技術(shù)在環(huán)境健康領(lǐng)域中的應(yīng)用進(jìn)展
旅游型海島景觀生態(tài)健康評(píng)價(jià)
基于機(jī)器學(xué)習(xí)的冠心病風(fēng)險(xiǎn)預(yù)測(cè)模型構(gòu)建與比較
基于保護(hù)動(dòng)機(jī)理論的妊娠期糖尿病孕婦血糖管理決策行為模型的構(gòu)建
妊娠期糖尿病孕婦血糖管理行為改變動(dòng)機(jī)的質(zhì)性研究
The Health Benefits of Dietary Fibre
結(jié)構(gòu)健康監(jiān)測(cè)的傳感器優(yōu)化布置研究進(jìn)展與展望
國(guó)內(nèi)大數(shù)據(jù)與膳食營(yíng)養(yǎng)健康的研究及應(yīng)用進(jìn)展

網(wǎng)址: Survey of structured data cleaning methods http://www.u1s5d6.cn/newsview340788.html