基于MAP-REDUCE的大數據不一致性解決算法

范令

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

基于MAP-REDUCE的大數據不一致性解決算法

范令

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

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

大數據；數據質量；數據不一致性；MAP-REDUCE；聚類算法

0　引言

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

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

1　相關工作

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

在大數據環境下，數據呈現規模性、多樣性、高速性和價值性等多種特性［6］。聚類算法是研究分類問題的一種統計分析方法，基于MAP-REDUCE的聚類方法可以有效解決大數據環境中的一些問題。神經網絡［7］、貝葉斯網絡［8］等算法也都在MAP-REDUCE框架下實現了并行化。

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）函數的功能是獲取對象 Di和Dj之間的距離。本文主要解決文本型數據的不一致性問題，所以選擇文本的最小編輯距離函數，即Levenshtein距離。

2　基于MAP-REDUCE的聚類算法

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

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

表1　來自5個網站的數據

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

把K-MEDOIDS聚類算法應用到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操作把數據集具有相同KEY值的VALUE聚集在一起。然后，通過K-MEDOIDS算法把List＜VALUE〉中的數據分為K個類，有效排除數量少但誤差過大的數據，對于數量較多且誤差較小的數據，取其對象最多的分類的中心點作為理想數據。

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

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

算法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更適用于本領域，同時還可以通過對初始誤差值E的設定控制每個分類的范圍。

2.3具有權重值的EW-MEDOIDS聚類算法

算法3中，把所有節點的數據視作等價的，沒有權重大小的區別。然而現實生活中并非如此。例如，政府網站提供的數據往往比其他的網站具有更高的可信度。因此，在所有節點上加上權重值，以此表明此節點數據的可信度。通過權重值的設置，可以調整分類中心點的偏移，使得結果更加精確，如表4所示。

表4　為每個數據節點設置權重值

算法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〉

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

3　仿真實驗

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

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

3.1單節點數據規模對運行時間的影響

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

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

圖1　單節點數據規模對運行時間的影響

3.2參數E對算法的影響

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

3.3HADOOP平臺上數據集規模對算法的影響

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

圖2　參數E對算法的影響

圖3　HADOOP平臺上實驗數據規模對算法的影響

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

4　結束語

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

目前，EW-MEDOIDS算法的權重值是通過人工設定的。當數據節點量很大時，人工設置的方法將不適用。未來可以在自動設置權重值方面開展工作，盡量減少不必要的人工操作。

［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］孟小峰，慈祥.大數據管理：概念，技術與挑戰［J］.計算機研究與發展，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的大數據不一致性解決算法［J］.微型機與應用，2015，34（15）：18-21.

范令（1990-），男，在讀碩士，主要研究方向：數據質量、大數據。