摘  要： 大數(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)境下該算法的并行性和有效性。

　　關(guā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

　　Repeat steps 2 to 6 until there is no change in 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)物的樂趣，而這一切，也需要通過(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)題。現(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所示。

　　當(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算法

　?。?）Input：DATA

　?。?）Map（DATA）MAPDATA={<KEY1，List<VALUE1>，<KEY2，List<VALUE2>，…}

　?。?）For each MAPDATA <KEY，List<VALUE>

　　（4）Get medoids by using K-MEDOIDS algorithm

　?。?）Get the max-count medoid

　?。?）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聚類算法

　?。?）Input：DATA{DATA1，DATA2，…，DATAn}

　?。?）Map（DATA）MAPDATA={<KEY1，List<VALUE1>，<KEY2，List<VALUE2>，…}

　?。?）For each MAPDATA<KEY，List<VALUE>

　?。?）M1=VALUE1

　?。?）For each non-medoid object o

　?。?）If GetDis（o，medoids）>E，M.Add（o）

　?。?）Associate each object to the closest medoid

　　（5）For each medoid m

　?。?）For each non-medoid object Di

　?。?）Get DISi

　?。?）If DISi=min（DIS）

　?。?）m=Di

　?。?0）Repeat steps 11 to 16 until there is no change in the medoids

　　（11）Get the max-count medoid

　?。?2）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à)的，沒有權(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：基于MAP-REDUCE的EW-MEDOIDS聚類算法

　　（1）Input：DATA

　?。?）Map（DATA）MAPDATA={<KEY1，List<VALUE1>，<KEY2，List<VALUE2>，…}

　　（3）For each MAPDATA<KEY，List<VALUE>

　?。?）M1=VALUE1

　?。?）For each non-medoid object o

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

　　（7）M.Add（o）

　?。?）Associate each object to the closest medoid

　　（9）For each medoid m

　?。?0）For each non-medoid object Di

　　（11）Get DISi with weight

　?。?2）If DISi=min（DIS）

　?。?3）m=Di

　　（14）Repeat steps 11 to 16 until there is no change in the medoids

　?。?5）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)安裝有UBUNTU 14.10操作系統(tǒng)、HADOOP 2.4.0平臺(tái)，具有AMD 3.10 GHz雙核處理器和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~1 000條不一致的數(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算法有一定的提高。

　　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.3 HADOOP平臺(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ù)文件大小從20 MB~200 MB不等。HADOOP實(shí)驗(yàn)平臺(tái)運(yùn)行20個(gè)MAP-REDUCE任務(wù)，實(shí)驗(yàn)結(jié)果如圖3所示。

　　由圖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)重值方面開展工作，盡量減少不必要的人工操作。

參考文獻(xià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， DOROTOVI 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（1）：1-6.

　　[8] TEWARI N C， KODUVELY H M， GUHA S， et al. MapReduce implementation of variational bayesian probabilistic matrix factorization algorithm[C]. Big Data， 2013 IEEE International Conference on. IEEE， 2013：145-152.