范令

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

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

范令

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

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

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

0　引言

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

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

1　相關(guān)工作

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

在大數(shù)據(jù)環(huán)境下，數(shù)據(jù)呈現(xiàn)規(guī)模性、多樣性、高速性和價(jià)值性等多種特性［6］。聚類算法是研究分類問(wèn)題的一種統(tǒng)計(jì)分析方法，基于MAP-REDUCE的聚類方法可以有效解決大數(shù)據(jù)環(huán)境中的一些問(wèn)題。神經(jīng)網(wǎng)絡(luò)［7］、貝葉斯網(wǎng)絡(luò)［8］等算法也都在MAP-REDUCE框架下實(shí)現(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ù)的功能是獲取對(duì)象 Di和Dj之間的距離。本文主要解決文本型數(shù)據(jù)的不一致性問(wèn)題，所以選擇文本的最小編輯距離函數(shù)，即Levenshtein距離。

2　基于MAP-REDUCE的聚類算法

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

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

表1　來(lái)自5個(gè)網(wǎng)站的數(shù)據(jù)

當(dāng)發(fā)現(xiàn)List＜VALUE〉中的數(shù)據(jù)不同時(shí)（表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〉

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

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

算法2中，首先設(shè)定分類個(gè)數(shù)為K，然后取隨機(jī)值作為K個(gè)分類的中心點(diǎn)。但在具體應(yīng)用中，不容易確定K的具體取值。針對(duì)此情況，對(duì)K-MEDOIDS進(jìn)行了初步的改進(jìn)，提出了初始誤差值E，以改進(jìn)聚類初始化時(shí)的中心點(diǎ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〉的第一個(gè)值作為第一個(gè)分類的中心點(diǎn)（M1）。然后遍歷余下的對(duì)象，若此對(duì)象與所有分類的中心點(diǎn)距離均大于初始誤差值E，則把此對(duì)象作為新類的中心點(diǎn)添加到Medoids中。算法3用若干分散的對(duì)象作為分類的中心點(diǎn)代替算法2中的隨機(jī)對(duì)象，目的是讓中心點(diǎn)分布得更加離散，聚類的速度也有所提高。而且用E代替K更適用于本領(lǐng)域，同時(shí)還可以通過(guò)對(duì)初始誤差值E的設(shè)定控制每個(gè)分類的范圍。

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

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

表4　為每個(gè)數(shù)據(jù)節(jié)點(diǎn)設(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｝來(lái)自若干個(gè)不同節(jié)點(diǎn)。通過(guò)評(píng)價(jià)節(jié)點(diǎn)的可信度，人工設(shè)定節(jié)點(diǎn)的權(quán)重值分別為（W1，W2，…，Wn）。這樣數(shù)據(jù)集D可以表示為｛＜D1，W1〉，＜D2，W2〉，…，＜Dn，Wn〉｝。算法3和算法2的不同之處在于（13）行，即更新中心點(diǎn)時(shí)，權(quán)重值屬性參與了計(jì)算。

3　仿真實(shí)驗(yàn)

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

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

3.1單節(jié)點(diǎn)數(shù)據(jù)規(guī)模對(duì)運(yùn)行時(shí)間的影響

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

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

圖1　單節(jié)點(diǎn)數(shù)據(jù)規(guī)模對(duì)運(yùn)行時(shí)間的影響

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

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

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

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

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

圖3　HADOOP平臺(tái)上實(shí)驗(yàn)數(shù)據(jù)規(guī)模對(duì)算法的影響

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

4　結(jié)束語(yǔ)

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

目前，EW-MEDOIDS算法的權(quán)重值是通過(guò)人工設(shè)定的。當(dāng)數(shù)據(jù)節(jié)點(diǎn)量很大時(shí)，人工設(shè)置的方法將不適用。未來(lái)可以在自動(dòng)設(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］.計(jì)算機(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］.微型機(jī)與應(yīng)用，2015，34（15）：18-21.

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