大數(shù)據(jù)云清洗系統(tǒng)的設(shè)計與實現(xiàn)

黃沈濱　王海潔　朱振華

摘 要：數(shù)據(jù)清洗時是大數(shù)據(jù)中一個重要的主題。本文基于Hadoop設(shè)計并實現(xiàn)了一個大數(shù)據(jù)的云清洗系統(tǒng)。通過Map-Reduce計算模型，該系統(tǒng)能夠檢測并修復(fù)數(shù)據(jù)質(zhì)量方面的各類問題。該系統(tǒng)包含以下特征：（1）支持?jǐn)?shù)據(jù)質(zhì)量方面各類問題的清洗工作；（2）數(shù)據(jù)云清洗進度可視化的以及參數(shù)設(shè)置；（3）友好的數(shù)據(jù)集輸入接口以及清洗后的數(shù)據(jù)集輸出接口。該大數(shù)據(jù)云清洗系統(tǒng)對文本數(shù)據(jù)和數(shù)據(jù)庫數(shù)據(jù)均是一個有效且高效的數(shù)據(jù)清洗系統(tǒng)。

關(guān)鍵詞：大數(shù)據(jù)；數(shù)據(jù)質(zhì)量；云清洗；Map-Reduce

中圖分類號：TP391 文獻(xiàn)標(biāo)識號：A

Design and Implementation of Cloud Clean System on Big Data

HUANG Shenbin1 ， WANG Haijie1 ， ZHU Zhenhua2

（1 Network and Information Center， Harbin Institute of Technology， Harbin 150001， China；

2 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract： Data cleaning is one of the central issues in big data. The paper describes a cloud clean system based on Hadoop for data cleaning. Using Map-Reduce model， the system detects and repairs various data quality problems in big data. The paper designs the system from the following features： （1） the support for cleaning multiple data quality problems in big data； （2） a visual tool for watching the status of big data cleaning process and tuning the parameters for data cleaning； （3） the friendly interface for data input and setting and cleaned data collection for big data. The cloud clean system is a promising system that provides efficient and effect data cleaning mechanism for big data in either files or database.

Keywords： Big Data； Data Quality； Cloud Clean； Map-Reduce

0 引 言

大數(shù)據(jù)已經(jīng)廣泛地應(yīng)用于各個領(lǐng)域，其數(shù)據(jù)質(zhì)量問題逐漸被人們所關(guān)注。這主要是由兩方面的因素導(dǎo)致的：一方面大數(shù)據(jù)由海量的數(shù)據(jù)源獲得，不同的數(shù)據(jù)來源使其更可能存在不一致沖突和不完整性；另一方面則是因為大數(shù)據(jù)頻繁地變化且難以手動地獲取。數(shù)據(jù)質(zhì)量問題嚴(yán)重影響著大數(shù)據(jù)應(yīng)用的效率，因為低質(zhì)量數(shù)據(jù)上的分析和查詢?nèi)菀讓?dǎo)致錯誤結(jié)果或者誤導(dǎo)性的決策。數(shù)據(jù)清洗無疑能夠提升大數(shù)據(jù)的利用效率。本文設(shè)計并實現(xiàn)了一個大數(shù)據(jù)云清洗系統(tǒng)，提取了數(shù)據(jù)清洗任務(wù)中的基本操作并基于Map-Reduce[1]計算框架實現(xiàn)相應(yīng)的算法。該系統(tǒng)對多種數(shù)據(jù)清洗任務(wù)均有可觀的性能。

1相關(guān)工作

雖然已經(jīng)有很多數(shù)據(jù)清洗的技術(shù)和算法被相繼提出，但卻并非都適用于大數(shù)據(jù)上。主要原因如下。

首先，現(xiàn)有的數(shù)據(jù)清洗算法的效率并不能滿足大數(shù)據(jù)的需求。并行計算是大數(shù)據(jù)算法的一個常用手段。然而，除了少數(shù)實體識別的算法[2-3]外，幾乎沒有其他的并行數(shù)據(jù)清洗算法獲得提出。具有多種數(shù)據(jù)質(zhì)量問題的大數(shù)據(jù)清洗工作的整體效率往往也都不高。

其次，現(xiàn)有的數(shù)據(jù)清洗系統(tǒng)[4-7]集中于數(shù)據(jù)質(zhì)量的某一方面。NADEEF[8]支持各種形式的規(guī)則，但是缺少數(shù)據(jù)清洗領(lǐng)域的一些重要問題如缺值填充和沖突屬性的真值發(fā)現(xiàn)等。對于具有多種數(shù)據(jù)質(zhì)量問題的大數(shù)據(jù)而言，這往往是不夠高效的。究其原因，一方面多種數(shù)據(jù)質(zhì)量問題需要多個不同的系統(tǒng)來完成各自的數(shù)據(jù)清洗工作，從而導(dǎo)致清洗過程需要多次的導(dǎo)入和導(dǎo)出數(shù)據(jù)；另一方面，多個數(shù)據(jù)質(zhì)量問題往往可能會共享相同的操作，如去除數(shù)據(jù)冗余[9]和流通數(shù)據(jù)發(fā)現(xiàn)[10]即都需要實體識別。如果不同的數(shù)據(jù)質(zhì)量問題均由各自的清洗系統(tǒng)來完成，那么這些相同的操作便將多次執(zhí)行，不利于全局的優(yōu)化。

最后，現(xiàn)有的數(shù)據(jù)清洗系統(tǒng)常常需要設(shè)置參數(shù)，例如不一致性檢測[11]的約束規(guī)則，實體識別[12]的閾值。對于小規(guī)模數(shù)據(jù)來說，這些規(guī)則能夠通過人工的觀測和理解來設(shè)置。然而對于大數(shù)據(jù)，僅靠觀察來設(shè)置是不合理的，而對整個數(shù)據(jù)人工的遍歷一遍更是不可能的。

2云清洗系統(tǒng)概述

清洗大數(shù)據(jù)的一個很直觀、很自然的想法便是將云計算的技術(shù)應(yīng)用其中，并將計算任務(wù)分布式地分發(fā)給多個節(jié)點以提高并行度。本文設(shè)計的大數(shù)據(jù)云清洗系統(tǒng)采用的便是這個思路，基于Map-Reduce封裝實現(xiàn)了數(shù)據(jù)清洗領(lǐng)域的各類基本問題和清洗操作，包括實體識別、不一致性檢測和修復(fù)、缺值填充和真值發(fā)現(xiàn)。

云清洗系統(tǒng)基于Hadoop來實現(xiàn)架構(gòu)，利用Map-Reduce框架系統(tǒng)能夠高效地控制硬件資源執(zhí)行分布式計算。整個系統(tǒng)的數(shù)據(jù)流如圖1所示。

圖1 數(shù)據(jù)流

Fig.1 Data Flow

系統(tǒng)的數(shù)據(jù)是組織在分布式文件系統(tǒng)中。而輸入數(shù)據(jù)則是通過文件或者數(shù)據(jù)庫來提供，前者由用戶上傳，后者將是用戶提供數(shù)據(jù)庫的連接信息而由系統(tǒng)來訪問。數(shù)據(jù)輸入后存在于分布式文件系統(tǒng)中，而集群中節(jié)點的數(shù)據(jù)則通過分布式文件系統(tǒng)來訪問。在清洗過程中，數(shù)據(jù)在mapper和reducer間傳遞，清洗結(jié)束后數(shù)據(jù)被送回到分布式文件系統(tǒng)。和輸入類似，用戶可以將清洗后的數(shù)據(jù)以文件的形式下載或者提供數(shù)據(jù)庫連接信息再由系統(tǒng)輸出到數(shù)據(jù)庫中。

系統(tǒng)的結(jié)構(gòu)如圖2所示，其中包含一個Master和多個Slave節(jié)點。具體地，Master 節(jié)點接收數(shù)據(jù)清洗任務(wù)的輸入數(shù)據(jù)、清洗計劃以及參數(shù)設(shè)置。而清洗計劃即是一個清洗操作序列，由系統(tǒng)提供的四種清洗的基本操作構(gòu)成，這四種操作分別為實體識別、不一致性檢測和修復(fù)、缺值填充和真值發(fā)現(xiàn)，并且四種操作可以重復(fù)選擇。

圖2 系統(tǒng)結(jié)構(gòu)圖

Fig.2 Architecture of the System

大數(shù)據(jù)的清洗任務(wù)，往往需要很長的時間。在清洗時，云清洗系統(tǒng)給用戶提供一個接口來實時查看清洗的進度情況以及通過結(jié)果預(yù)覽來調(diào)整算法參數(shù)。

3 數(shù)據(jù)清洗操作

本節(jié)將簡要介紹四個數(shù)據(jù)清洗操作的功能以及基本Map-Reduce計算框架下的算法實現(xiàn)。

3.1 清洗操作

為了使清洗系統(tǒng)能夠復(fù)用共享的操作以提升清洗的效率，研究提取了數(shù)據(jù)質(zhì)量問題中的四類基本的操作，分別是實體識別、不一致性檢測和修復(fù)、缺值填充和真值發(fā)現(xiàn)。對其概述如下

實體識別：識別元組是否代表現(xiàn)實世界的同一實體。

不一致性檢測和修復(fù)：檢測違反規(guī)則集的元組，并修復(fù)數(shù)據(jù)使之符合規(guī)則。

缺值填充：根據(jù)其他完整的元組數(shù)據(jù)來填充元組的缺失屬性值。

真值發(fā)現(xiàn)：選擇代表同一實體的不同元組存在取值沖突時的真實取值。

這些操作涵蓋了數(shù)據(jù)質(zhì)量方面的大多數(shù)問題。本文的系統(tǒng)可以利用如上的基本操作并根據(jù)實際需求來組合形成新的數(shù)據(jù)清洗的復(fù)雜操作。

3.2 算法實現(xiàn)

這些操作對應(yīng)的算法可在Map-Reduce框架下獲得實現(xiàn)，再并行地在各個slave上運行。限于篇幅，此處僅給出其簡要介紹。

（1）實體識別。該算法有兩階段。第一階段，構(gòu)建屬性索引表，使得索引表中擁有相同屬性值的數(shù)據(jù)對象對應(yīng)于同一個實體。這一階段由一輪Map-Reduce實現(xiàn)并完成。其中的Map階段劃分主要根據(jù)屬性的取值來進行數(shù)據(jù)劃分，而Reduce階段則根據(jù)屬性取值來對元組決定其分群。第二階段，完成實體的識別，執(zhí)行相似度連接查詢生成相似實體對集合。該階段由五輪Map-Reduce實現(xiàn)并完成。其中的第一輪分別統(tǒng)計每個實體及每個實體對的出現(xiàn)次數(shù)。第二輪和第三輪分別根據(jù)同時出現(xiàn)在實體對中的第一個實體和第二個進行聚集，生成相似實體對集合。稍后的第四輪和第五輪則根據(jù)閾值和計算的相似度，完成實體劃分。

（2）不一致性檢測和修復(fù)。該操作需要三輪Map-Reduce來實現(xiàn)并完成。第一輪實現(xiàn)了常量CFD的不一致性檢測和修復(fù)。Map過程是根據(jù)約束規(guī)則對元組進行劃分，并從規(guī)則中得到修復(fù)值，Reduce過程則根據(jù)得到的修復(fù)值對不一致的數(shù)據(jù)項進行相關(guān)修復(fù)。隨后的兩輪則完成FD和CFD的不一致性檢測和修復(fù)。兩者中，前一輪的Map過程依然是根據(jù)約束規(guī)則來劃分元組，此過程檢測的是變量CFD的違反，因此一個元組可能重復(fù)地劃分；而Reduce過程則針對獲得的分組以判斷組內(nèi)是否發(fā)生變量違反，制定修復(fù)方案。基于前一輪Reduce的輸出，后一輪將以其作為輸入，并按照計算的解決方案對不一致的數(shù)據(jù)項進行修復(fù)。Map階段對每條元組的修復(fù)方案進行整合。Reduce階段將繼續(xù)根據(jù)整合后的修復(fù)方案對不一致的數(shù)據(jù)項進行修復(fù)。

（3）缺值填充。研究根據(jù)不同的屬性取值設(shè)計了多種不同的算法類型來實現(xiàn)缺值填充。對于連續(xù)變量值的缺失而言，就是利用其他的屬性取值通過回歸來實現(xiàn)缺值填充。此處的回歸包含三個子過程，分別是：標(biāo)準(zhǔn)化、排序和回歸，每一個操作均對應(yīng)一輪的Map-Reduce。具體來說，標(biāo)準(zhǔn)化階段將所有屬性進行標(biāo)準(zhǔn)化，并計算各個屬性的最小值，構(gòu)成最小值向量。排序則對所有元組的最小值向量計算相對大小并排序。回歸將完成回歸并填充缺失值。離散變量值缺失，則通過分類來實現(xiàn)缺值填充。分類也同樣包含三個子過程，分別是：概率計算、參數(shù)聚集和缺值填充，每個操作也都對應(yīng)一輪Map-Reduce。具體地，概率計算過程需要計算每個特征屬性的條件概率和分類屬性的邊緣概率，生成概率表。參數(shù)聚集則根據(jù)概率表來聚集缺值填充需要的參數(shù)。而缺值填充主要根據(jù)聚集的參數(shù)來完成填充。

（4）真值發(fā)現(xiàn)。真值發(fā)現(xiàn)的基本框架是貝葉斯模型。該框架迭代地計算真值和數(shù)據(jù)源的相關(guān)性。每次迭代均需要兩輪的Map-Reduce。第一輪通過數(shù)據(jù)源的可靠性來計算真值，map將根據(jù)屬性與實體序號的匹配來生成屬性值與數(shù)據(jù)源的可靠性的對應(yīng)，reduce階段則通過投票來確定真值。第二輪通過上一輪得到的真值來重新評估數(shù)據(jù)源的可靠性。兩輪一直迭代執(zhí)行，直至收斂。

4用戶功能接口

研究設(shè)計的云清洗系統(tǒng)部署在一個32節(jié)點的Hadoop集群上，該系統(tǒng)為用戶提供了一個基于Web的訪問接口。本節(jié)簡要介紹該系統(tǒng)的用戶功能接口。

（1）任務(wù)提交。提交一個數(shù)據(jù)清洗任務(wù)總共需要四類輸入：待清洗的數(shù)據(jù)、由清洗基本操作序列構(gòu)成的清洗計劃、算法的參數(shù)和并行節(jié)點數(shù)。用戶可以通過文件的形式或者遠(yuǎn)程數(shù)據(jù)庫連接的形式提交待清洗的數(shù)據(jù)。清洗計劃則是選擇系統(tǒng)提供的四種數(shù)據(jù)清洗操作中的某幾項，組成一個操作序列告訴系統(tǒng)用戶的清洗計劃。算法的參數(shù)則是清洗計劃中選擇的基本操作所對應(yīng)的算法中需要的參數(shù)輸入，這是由用戶進行提供的。而并行節(jié)點數(shù)就是用于進行這次清洗所使用的節(jié)點數(shù)目。

（2）進度觀測。進度觀測的作用是讓用戶獲取清洗的進度信息。系統(tǒng)的Web頁面可向用戶展示出當(dāng)前進行的清洗任務(wù)，該任務(wù)的操作序列中各個操作的完成情況，以及正在進行的操作中各個節(jié)點的分布式完成情況。為此，用戶即能隨時地觀察整個任務(wù)的進度信息。

（3）結(jié)果預(yù)覽。對于已經(jīng)完成的清洗任務(wù)，系統(tǒng)會對清洗結(jié)果進行小樣本的抽樣，生成各個操作的清洗前后的對比效果，提供給用戶展示和查看。用戶根據(jù)效果清晰與否來選擇是調(diào)整參數(shù)再次清洗還是下載清洗后的數(shù)據(jù)。

（4）結(jié)果獲取。當(dāng)清洗完成之后，系統(tǒng)提供給用戶獲取清洗結(jié)果的接口。和數(shù)據(jù)輸入類似地，用戶可以直接以文件的形式下載數(shù)據(jù)或者提供數(shù)據(jù)庫連接信息用于遠(yuǎn)程導(dǎo)出到數(shù)據(jù)庫。

5結(jié)束語

本文設(shè)計并實現(xiàn)了大數(shù)據(jù)的云清洗系統(tǒng)，提出了數(shù)據(jù)質(zhì)量問題的四種基本操作，實體識別、不一致性檢測和修復(fù)、缺值填充和真值發(fā)現(xiàn)，并組合成更復(fù)雜的數(shù)據(jù)清洗任務(wù)。該系統(tǒng)采用Map-Reduce框架實現(xiàn)，能夠更為高效地處理大數(shù)據(jù)的清洗任務(wù)。同時，系統(tǒng)還為用戶提供了一個簡潔而友好的Web功能接口，從而交互式地實現(xiàn)了大數(shù)據(jù)的清洗功能。

參考文獻(xiàn)：

[1] DEAN J， GHEMAWAT S. MapReduce： Simplified data processing on large clusters [C]//OSDI， San Francisco， USA： USENIX， 2004.

[2] KOLB L， THOR A， RAHM E. Dedoop： Efficient deduplication with hadoop[J]. PVLDB， 2012，5（12）：1878-1881.

[3] KOLB L， THOR A， RAHM E. Load balancing for map-reduce-based entity resolution[C]//ICDE， [S.l.]：IEEE，2012：618-629.

[4] RAMAN V， HELLERSTEIN J M. Potters wheel： An interactive data cleaning system[C]//VLDB， Rome， Italy： VLDB， 2001.

[5] WEIS M， MANOLESCU I. Xclean in action （demo）[C]//CIDR， Asilomar， CA， USA：[s.n.]，2007.

[6] FAN W， GEERTS F， JIA X. Semandaq： a data quality system based on conditional functional dependencies[J]. PVLDB， 2008，1（2）：1460-1463.

[7] FAN W， LI J， MA S， et al. Yu. CerFix： A system for cleaning data with certain fixes[J]. PVLDB， 2011，4（12）：1375-1378.

[8] EBAID A， ELMAGARMID A K， ILYAS I F， et al. Nadeef： A generalized data cleaning system[J]. PVLDB， 2013，6（12）：1218–1221.

[9] ELMAGARMID A K， IPEIROTIS P G， VERYKIOS V S. Duplicate record detection： A survey[J]. IEEE Trans. Knowl. Data Eng.， 2007，19（1）：1-16.

[10] FAN W， GEERTS F， WIJSEN J. Determining the currency of data[J]. ACM Trans. Database Syst.， 2012， 37（3）：1-45 .

[11] FAN W. Dependencies revisited for improving data quality[C]//PODS， Vancouver， Canada：ACM， 2008：159-170.

[12] LI L， WANG H， GAO H， et al. Eif： A framework of effective entity identification[C]// WAIM， Berlin： Springer， 2010：717-728.