基于MAP-REDUCE的大數(shù)據(jù)不一致性解決算法

范令

（中國海洋大學(xué)　信息科學(xué)與工程學(xué)院，山東　青島 266100）

基于MAP-REDUCE的大數(shù)據(jù)不一致性解決算法

范令

（中國海洋大學(xué)信息科學(xué)與工程學(xué)院，山東青島 266100）

大數(shù)據(jù)時代悄然而至，數(shù)據(jù)質(zhì)量也引起人們的關(guān)注。在提高數(shù)據(jù)質(zhì)量方面，很重要的一部分是解決數(shù)據(jù)不一致性問題。針對大數(shù)據(jù)情況下的數(shù)據(jù)不一致問題，本文提出了在MAP-REDUCE框架下的聚類算法。本文在MAP-REDUCE框架下對K-MEDOIDS聚類算法進(jìn)行了改進(jìn)，增強了算法的適用性和精確性，并通過仿真實驗驗證了在大數(shù)據(jù)環(huán)境下該算法的并行性和有效性。

大數(shù)據(jù)；數(shù)據(jù)質(zhì)量；數(shù)據(jù)不一致性；MAP-REDUCE；聚類算法

0　引言

隨著大數(shù)據(jù)時代的到來，龐大的數(shù)據(jù)被賦予了新的生命，而數(shù)據(jù)質(zhì)量問題也引起了越來越多的關(guān)注。數(shù)據(jù)質(zhì)量涉及數(shù)據(jù)的一致性、正確性、完整性和最小性等多個方面［1-2］。當(dāng)分布在多個節(jié)點的數(shù)據(jù)集成時，若提供的數(shù)據(jù)出現(xiàn)重疊，容易引起數(shù)據(jù)不一致性的問題。如何從若干個不一致的數(shù)據(jù)中獲得理想的數(shù)據(jù)答案在數(shù)據(jù)清洗中就顯得至關(guān)重要［3］。

本文提出了基于MAP-REDUCE的聚類算法解決大數(shù)據(jù)環(huán)境中數(shù)據(jù)不一致性問題。改進(jìn)了K-MEDOIDS聚類算法，提高了算法的適用性和精確性。

1　相關(guān)工作

目前，解決數(shù)據(jù)不一致性問題的方案很多，如參考文獻(xiàn)［4］討論了太陽黑子探測數(shù)據(jù)不一致性問題，并提出了一種加權(quán)匹配技術(shù)減小數(shù)據(jù)的不一致性。針對數(shù)據(jù)復(fù)制時產(chǎn)生的數(shù)據(jù)不一致問題，參考文獻(xiàn)［5］定義了不同版本數(shù)據(jù)的距離函數(shù)，以此消除復(fù)制數(shù)據(jù)時的不一致性。參考文獻(xiàn)［2］是通過屬性間的條件依賴（CFD）探測數(shù)據(jù)間的不一致性進(jìn)而進(jìn)行數(shù)據(jù)修復(fù)。然而，當(dāng)數(shù)據(jù)量急劇增大時，現(xiàn)有的清洗算法將不再適用。

在大數(shù)據(jù)環(huán)境下，數(shù)據(jù)呈現(xiàn)規(guī)模性、多樣性、高速性和價值性等多種特性［6］。聚類算法是研究分類問題的一種統(tǒng)計分析方法，基于MAP-REDUCE的聚類方法可以有效解決大數(shù)據(jù)環(huán)境中的一些問題。神經(jīng)網(wǎng)絡(luò)［7］、貝葉斯網(wǎng)絡(luò)［8］等算法也都在MAP-REDUCE框架下實現(xiàn)了并行化。

K-MEDOIDS聚類算法介紹如下。

算法1：K-MEDOIDS聚類算法

Initialize：Random k objects in D as medoids

Associate each object to the closest medoid

For each medoid m

For each non-medoid object o

Get DISi

Select the new medoid with the lowest distance

Repeatsteps2to6untilthereisnochangein the medoids

其中，GetDis（Di，Dj）函數(shù)的功能是獲取對象 Di和Dj之間的距離。本文主要解決文本型數(shù)據(jù)的不一致性問題，所以選擇文本的最小編輯距離函數(shù)，即Levenshtein距離。

2　基于MAP-REDUCE的聚類算法

2.1基于MAP-REDUCE的K-MEDOIDS算法

互聯(lián)網(wǎng)的進(jìn)步讓人們足不出戶就可以完成火車票、汽車票、機票等的訂購，享受網(wǎng)上購物的樂趣，而這一切，也需要通過在各個網(wǎng)站注冊并保留個人身份信息，包括網(wǎng)上銀行等，才能完成這一系列操作。假設(shè)將這些網(wǎng)絡(luò)的身份信息匯總到一起，就有可能出現(xiàn)數(shù)據(jù)不一致情況，如表1所示，T1～T7共7條含有身份證號和姓名的數(shù)據(jù)來自5個不同的網(wǎng)站，由于某些原因，如拼寫錯誤（T3、T4、T6）、字段截?。═5）等，產(chǎn)生了數(shù)據(jù)不一致問題。現(xiàn)在定義一條數(shù)據(jù)的格式為＜KEY，VALUE〉，如＜ID，NAME〉。數(shù)據(jù)集DATA含有n條數(shù)據(jù)：｛DATA1，DATA2，…，DATAn｝，即｛＜KEY1，VALUE1〉，＜KEY2，VALUE2〉，…，＜KEYn，VALUEn〉｝。DATA中的數(shù)據(jù)分布在不同的節(jié)點上，當(dāng)數(shù)據(jù)集成時，利用MAP-REDUCE框架的MAP過程把具有相同KEY的數(shù)據(jù)分配到同一節(jié)點上，就得到了具有相同KEY值的數(shù)據(jù)＜KEY，List＜VALUE〉〉，如表2和表3所示。

表1　來自5個網(wǎng)站的數(shù)據(jù)

當(dāng)發(fā)現(xiàn)List＜VALUE〉中的數(shù)據(jù)不同時（表2、表3），就出現(xiàn)了數(shù)據(jù)不一致情況。若想在List＜VALUE〉中找到比較理想的數(shù)據(jù)，可以采用K-MEDOIDS聚類算法。

把K-MEDOIDS聚類算法應(yīng)用到MAP-REDUCE框架下，算法如下。

算法2：基于MAP-REDUCE的K-MEDOIDS算法

（1）Input：DATA

（2）Map（DATA）MAPDATA=｛＜KEY1，List＜VALUE1〉，＜KEY2，List＜VALUE2〉，…｝

（3）For each MAPDATA ＜KEY，List＜VALUE〉

（4）Get medoids by using K-MEDOIDS algorithm

（5）Get the max-count medoid

（6）Output：＜KEY1，VALUE1〉，＜KEY2，VALUE2〉，…，＜KEYm，VALUEm〉

首先，通過MAP操作把數(shù)據(jù)集具有相同KEY值的VALUE聚集在一起。然后，通過K-MEDOIDS算法把List＜VALUE〉中的數(shù)據(jù)分為K個類，有效排除數(shù)量少但誤差過大的數(shù)據(jù)，對于數(shù)量較多且誤差較小的數(shù)據(jù)，取其對象最多的分類的中心點作為理想數(shù)據(jù)。

2.2更加適用的E-MEDOIDS聚類算法

算法2中，首先設(shè)定分類個數(shù)為K，然后取隨機值作為K個分類的中心點。但在具體應(yīng)用中，不容易確定K的具體取值。針對此情況，對K-MEDOIDS進(jìn)行了初步的改進(jìn)，提出了初始誤差值E，以改進(jìn)聚類初始化時的中心點分布。

算法3：基于MAP-REDUCE的E-MEDOIDS聚類算法

（1）Input：DATA｛DATA1，DATA2，…，DATAn｝

（2）Map（DATA）MAPDATA=｛＜KEY1，List＜VALUE1〉，＜KEY2，List＜VALUE2〉，…｝

（3）For each MAPDATA＜KEY，List＜VALUE〉

（1）M1=VALUE1

（2）For each non-medoid object o

（3）If GetDis（o，medoids）〉E，M.Add（o）

（4）Associate each object to the closest medoid

（5）For each medoid m

（6）For each non-medoid object Di

（7）Get DISi

（8）If DISi=min（DIS）

（9）m=Di

（10）Repeatsteps11to16untilthereisno change in the medoids

（11）Get the max-count medoid

（12）Output：＜KEY1，VALUE1〉，＜KEY2，VALUE2〉，…，＜KEYm，VALUEm〉

算法3與算法2的不同之處在于（8）～（10）行：首先選取List＜VALUE〉的第一個值作為第一個分類的中心點（M1）。然后遍歷余下的對象，若此對象與所有分類的中心點距離均大于初始誤差值E，則把此對象作為新類的中心點添加到Medoids中。算法3用若干分散的對象作為分類的中心點代替算法2中的隨機對象，目的是讓中心點分布得更加離散，聚類的速度也有所提高。而且用E代替K更適用于本領(lǐng)域，同時還可以通過對初始誤差值E的設(shè)定控制每個分類的范圍。

2.3具有權(quán)重值的EW-MEDOIDS聚類算法

算法3中，把所有節(jié)點的數(shù)據(jù)視作等價的，沒有權(quán)重大小的區(qū)別。然而現(xiàn)實生活中并非如此。例如，政府網(wǎng)站提供的數(shù)據(jù)往往比其他的網(wǎng)站具有更高的可信度。因此，在所有節(jié)點上加上權(quán)重值，以此表明此節(jié)點數(shù)據(jù)的可信度。通過權(quán)重值的設(shè)置，可以調(diào)整分類中心點的偏移，使得結(jié)果更加精確，如表4所示。

表4　為每個數(shù)據(jù)節(jié)點設(shè)置權(quán)重值

算法4：基于MAP-REDUCE的EW-MEDOIDS聚類算法

（1）Input：DATA

（2）Map（DATA）MAPDATA=｛＜KEY1，List＜VALUE1〉，＜KEY2，List＜VALUE2〉，…｝

（3）For each MAPDATA＜KEY，List＜VALUE〉

（4）M1=VALUE1

（5）For each non-medoid object o

（6）If GetDis（o，medoids）〉E

（7）M.Add（o）

（8）Associate each object to the closest medoid

（9）For each medoid m

（10）For each non-medoid object Di

（11）Get DISiwith weight

（12）If DISi=min（DIS）

（13）m=Di

（14）Repeatsteps11to16untilthereisno change in the medoids

（15）Get the max-count medoid

（16）Output：＜KEY1，VALUE1〉，＜KEY2，VALUE2〉，…，＜KEYm，VALUEm〉

數(shù)據(jù)集D=｛D1，D2，…Dn｝來自若干個不同節(jié)點。通過評價節(jié)點的可信度，人工設(shè)定節(jié)點的權(quán)重值分別為（W1，W2，…，Wn）。這樣數(shù)據(jù)集D可以表示為｛＜D1，W1〉，＜D2，W2〉，…，＜Dn，Wn〉｝。算法3和算法2的不同之處在于（13）行，即更新中心點時，權(quán)重值屬性參與了計算。

3　仿真實驗

為了評估本文提出的算法的效率、并行程度，搭建了HADOOP平臺進(jìn)行實驗。實驗的編程語言采用Java語言，在HADOOP平臺上實現(xiàn)算法1、算法2和算法3。實驗平臺包含6個節(jié)點，每個節(jié)點安裝有UBUNTU14.10操作系統(tǒng)、HADOOP2.4.0平臺，具有AMD3.10GHz雙核處理器和4 GB內(nèi)存。

本實驗數(shù)據(jù)要求文本型數(shù)據(jù)，而且其中部分?jǐn)?shù)據(jù)呈現(xiàn)錯亂現(xiàn)象，因此采用人工生成的測試數(shù)據(jù)集。具有權(quán)重值的EW-MODOIDS算法是在E-MEDOIDS算法的基礎(chǔ)上加上節(jié)點的權(quán)重值控制中心點的偏移，因此只要權(quán)重值的設(shè)定符合實際情況，EW-MEDOIDS算法的精確性就大于無權(quán)重干預(yù)的K-MEDOIDS算法和E-MEDOIDS算法，無需實驗驗證。

3.1單節(jié)點數(shù)據(jù)規(guī)模對運行時間的影響

為了評估算法的運行效率，生成100～1000條不一致的數(shù)據(jù)分別用K-MEDOIDS算法和E-MEDOIDS算法（EW-MEDOIDS算法和E-MEDOIDS算法效率相當(dāng)）在單一節(jié)點實現(xiàn)。在生成單節(jié)點實驗數(shù)據(jù)時，首先設(shè)置固定詞條作為正確答案，然后按一定比例隨機挑選數(shù)據(jù)條目進(jìn)行增加、刪除、修改、調(diào)換順序等操作，每組實驗數(shù)據(jù)均取十次相同重復(fù)實驗結(jié)果的平均值。

E-MEDOIDS算法中參數(shù)E的引入不僅提高了聚類算法的適用性，而且從圖1可以看出，E-MEDOIDS算法的運行效率比K-MEDOIDS算法有一定的提高。

圖1　單節(jié)點數(shù)據(jù)規(guī)模對運行時間的影響

3.2參數(shù)E對算法的影響

分別采用400、500、600條目的數(shù)據(jù)集進(jìn)行實驗，每次實驗更改參數(shù)E的大小，然后收集程序的運行時間。圖2表明E-MEDOIDS參數(shù)E對算法的運行效率整體影響不大，但是當(dāng)參數(shù)E取得某一恰當(dāng)值（約等于固定詞條的長度）時，程序運行時間取得最小值。因此，正確設(shè)置參數(shù)E，可以提高算法的效率。

3.3HADOOP平臺上數(shù)據(jù)集規(guī)模對算法的影響

為了驗證在大數(shù)據(jù)環(huán)境下算法的并行性，在HADOOP平臺上使用大小不等的10組數(shù)據(jù)進(jìn)行實驗。實驗數(shù)據(jù)集由不同數(shù)量的單節(jié)點實驗數(shù)據(jù)組成，生成的實驗數(shù)據(jù)文件大小從20MB～200MB不等。HADOOP實驗平臺運行20個MAP-REDUCE任務(wù)，實驗結(jié)果如圖3所示。

圖2　參數(shù)E對算法的影響

圖3　HADOOP平臺上實驗數(shù)據(jù)規(guī)模對算法的影響

由圖3可以看出，隨著數(shù)據(jù)量增加，HADOOP任務(wù)運行時間也平緩增加。當(dāng)數(shù)據(jù)量較小時，算法運行時間增長較快；當(dāng)數(shù)據(jù)量較大時，運行時間增長比較緩慢。這是因為當(dāng)數(shù)據(jù)量較大時才能發(fā)揮HADOOP平臺下算法并行運算的優(yōu)勢，因此算法具有良好的并行性。所以本文提出的基于MAP-REDUCE的聚類算法可以有效解決大數(shù)據(jù)環(huán)境下數(shù)據(jù)不一致性問題。

4　結(jié)束語

大數(shù)據(jù)環(huán)境中，提高數(shù)據(jù)質(zhì)量也將成為數(shù)據(jù)價值再創(chuàng)造的關(guān)鍵之一。當(dāng)分布在不同節(jié)點上的數(shù)據(jù)集成時，很容易引起數(shù)據(jù)不一致問題，嚴(yán)重影響數(shù)據(jù)質(zhì)量。本文提出了基于MAP-REDUCE的聚類算法解決大數(shù)據(jù)環(huán)境下的數(shù)據(jù)不一致問題。通過改進(jìn)K-MEDOIDS算法提出E-MEDOIDS算法，使聚類算法在處理數(shù)據(jù)不一致問題上適用性更強。又提出了EW-MEDOIDS算法，引入節(jié)點的權(quán)重值對聚類算法進(jìn)行干預(yù)，進(jìn)一步提高聚類算法的精確性。而算法采用MAP-REDUCE框架實現(xiàn)，有效增強了聚類算法的并行性，可高效解決大數(shù)據(jù)環(huán)境下的數(shù)據(jù)不一致問題。

目前，EW-MEDOIDS算法的權(quán)重值是通過人工設(shè)定的。當(dāng)數(shù)據(jù)節(jié)點量很大時，人工設(shè)置的方法將不適用。未來可以在自動設(shè)置權(quán)重值方面開展工作，盡量減少不必要的人工操作。

［1］AEBI D，PERROCHON L.Towards improving data quality ［C］.CiSMOD，1993：273-281.

［2］FAN W，GEERTS F.Foundations of data quality management［J］.Synthesis Lectures on Data Management，2012，4 （5）：1-217.

［3］RAHM E，DO H H.Data cleaning：problems and current approaches［J］.IEEE Data Eng.Bull.，2000，23（4）：3-13.

［4］SHAHAMATNIA E，DOROTOVICˇI，MORA A，et al.Data inconsistency in sunspot detection［C］.Intelligent Systems′2014，Springer International Publishing，2015：567-577.［5］DANILOWICZ C，NGUYEN N T.Consensus methods for solving inconsistency of replicated data in distributed systems［J］.Distributed and Parallel Databases，2003，14（1）：53-69.

［6］孟小峰，慈祥.大數(shù)據(jù)管理：概念，技術(shù)與挑戰(zhàn)［J］.計算機研究與發(fā)展，2013，50（1）：146-169.

［7］KUMAR V V，DINESH K.Job scheduling using fuzzy neural network algorithm in cloud environment［J］.Bonfring International Journal of Man Machine Interface，2012，2

An inconsistency solution in big data based on MAP-REDUCE

Fan Ling

（College of Information Science and Engineering，Ocean University of China，Qingdao 266100，China）

With the arrival of the era of big data，data quality attracts more and more attention recently.An important part of improving data quality is to solve the problem of inconsistency.In this paper，we propose the clustering algorithm based on Map-Reduce to solve the problem of data inconstancy in big data.Moreover，we improve the clustering algorithm named K-MEDOIDS for better applicability and accuracy.At the last，we simulate the experiment on the HADOOP platform.The experiment results evaluate the concurrency and effectiveness of our algorithm in big data.

big data；data quality；inconsistency；MAP-REDUCE；clustering algorithm

TP301

A

1674-7720（2015）15-0018-04

范令.基于MAP-REDUCE的大數(shù)據(jù)不一致性解決算法［J］.微型機與應(yīng)用，2015，34（15）：18-21.

范令（1990-），男，在讀碩士，主要研究方向：數(shù)據(jù)質(zhì)量、大數(shù)據(jù)。