孟佳偉+孫紅

摘要：在科技高速發(fā)展的今天，海量數(shù)據(jù)處理問(wèn)題受到人們廣泛關(guān)注。將K-means聚類算法與Hadoop平臺(tái)相結(jié)合是處理海量數(shù)據(jù)問(wèn)題的一條可靠途徑。簡(jiǎn)單介紹Hadoop和K-means算法以及K-means聚類算法MapReduce并行化實(shí)現(xiàn)，并闡述目前Hadoop平臺(tái)下K-means算法的幾種優(yōu)化方式，最后提出研究展望。

關(guān)鍵詞：海量數(shù)據(jù)處理；Hadoop；K-means；MapReduce

DOIDOI：10.11907/rjdk.171405

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）006-0208-04

0 引言

隨著科學(xué)技術(shù)的飛速發(fā)展，互聯(lián)網(wǎng)技術(shù)已經(jīng)深入到社會(huì)的各個(gè)領(lǐng)域，由此，數(shù)據(jù)量呈現(xiàn)出一種指數(shù)級(jí)增長(zhǎng)[1]。如何高效地對(duì)這些海量數(shù)據(jù)進(jìn)行處理和分析已成為當(dāng)前研究熱點(diǎn)。隨著數(shù)據(jù)規(guī)模越來(lái)越大，在面對(duì)海量數(shù)據(jù)時(shí)，傳統(tǒng)的數(shù)據(jù)挖掘工作會(huì)出現(xiàn)儲(chǔ)存量不足、用時(shí)過(guò)長(zhǎng)等缺點(diǎn)[2]。而云計(jì)算的出現(xiàn)則為解決這些問(wèn)題提供了新思路，將云計(jì)算與傳統(tǒng)數(shù)據(jù)挖掘方法相結(jié)合并對(duì)其進(jìn)行優(yōu)化是科學(xué)工作者們不斷研究的方向。

聚類分析是數(shù)據(jù)挖掘方法中的常用方法。1975年，Hartigan對(duì)聚類算法提出了系統(tǒng)論述[3]。在眾多聚類算法中，K-means算法是被應(yīng)用與研究最廣泛的算法。如今，云計(jì)算已經(jīng)得到了人們的廣泛關(guān)注，而Hadoop平臺(tái)是一個(gè)可以開(kāi)發(fā)和并行處理大數(shù)據(jù)的云計(jì)算平臺(tái)。作為一種由分布式技術(shù)、網(wǎng)絡(luò)計(jì)算機(jī)技術(shù)及并行技術(shù)發(fā)展而來(lái)的產(chǎn)物，Hadoop可以說(shuō)是一種為了適應(yīng)大規(guī)模數(shù)據(jù)存儲(chǔ)以及計(jì)算而衍生出的模型構(gòu)架[4]。本文將對(duì)當(dāng)前基于Hadoop平臺(tái)的K-means算法的各種優(yōu)化方法進(jìn)行綜述，并提出展望。

1 Hadoop

從最初版本HDFS和MapReduce于2004年開(kāi)始實(shí)施，到2011年1.0.0版本釋出標(biāo)志Hadoop已初具生產(chǎn)規(guī)模，經(jīng)歷了短短不到十年的時(shí)間。作為一種開(kāi)源云計(jì)算模型，Hadoop模仿并實(shí)現(xiàn)了Google云計(jì)算的主要技術(shù)，不但可移植性強(qiáng)，而且使用Java語(yǔ)言進(jìn)行編寫(xiě)[5]。其最早是來(lái)自于Google的一款名為MapReduce的編程模型包。MapReduce最早是由Google公司在2004年提出的一種可伸縮并且是線性的用于處理海量數(shù)據(jù)的并行編程模型[6]。Hadoop平臺(tái)的出現(xiàn)極大地便利了對(duì)于處理海量數(shù)據(jù)和應(yīng)用程序的算法研究。Hadoop框架中最核心的部分是MapReduce和HDFS。分布式文件系統(tǒng)Hadoop Distributed File System的縮寫(xiě)即HDFS，其具有極高的容錯(cuò)性并且對(duì)機(jī)器要求不高，適合部署在廉價(jià)的機(jī)器上，為分布式計(jì)算存儲(chǔ)提供底層支持。其能夠提供高吞吐的數(shù)據(jù)訪問(wèn)，因而適合于大規(guī)模數(shù)據(jù)集上的應(yīng)用。

MapReduce可以使程序自動(dòng)分布到一個(gè)超大集群上并發(fā)執(zhí)行，并且這個(gè)超大集群可以由普通機(jī)器組成[7]。其中，Map將一個(gè)任務(wù)分解為多個(gè)任務(wù)。而Reduce則是將分解之后的多任務(wù)的處理結(jié)果進(jìn)行匯總并且得出分析結(jié)果。由大量機(jī)器組成的機(jī)器集群可以被視作分布式系統(tǒng)的資源池，通過(guò)對(duì)并行任務(wù)進(jìn)行拆分并且交給空閑機(jī)器資源處理這種方式提高了計(jì)算效率。對(duì)MapReduce的工作流程進(jìn)行展示如圖1所示，Map對(duì)任務(wù)進(jìn)行分解，Reduce則負(fù)責(zé)合并。通過(guò)Map函數(shù)及Reduce函數(shù)對(duì)一組輸入鍵值對(duì)（Key/Value）的計(jì)算，得到一組輸出鍵值對(duì)。一個(gè)Mapper類、Reducer類和一個(gè)創(chuàng)建JobConf的驅(qū)動(dòng)函數(shù)組成了運(yùn)行于Hadoop平臺(tái)下的MapReduce應(yīng)用程序。另外若有需要，還可以有一個(gè)Combiner類，實(shí)際上該類也是Reducer的一種實(shí)現(xiàn)?；居?jì)算流程首先將輸入數(shù)據(jù)劃分為數(shù)據(jù)塊，之后處理數(shù)據(jù)塊得到鍵值對(duì)。之后進(jìn)入Map操作將產(chǎn)生的中間結(jié)果被區(qū)分地寫(xiě)到輸出文件里。Mapper輸出的中間鍵值對(duì)可根據(jù)需要為Mapper指定Combiner類并對(duì)該輸出進(jìn)行合并后輸出至文件。當(dāng)Map任務(wù)結(jié)束，開(kāi)始Reduce過(guò)程。每個(gè)Reduce任務(wù)包括組合和排序以及聚集數(shù)據(jù)。根據(jù)中間結(jié)果中的鍵Key，MapReduce框架將多個(gè)Mapper產(chǎn)生的同一個(gè)Key的中間結(jié)果傳輸至處理這個(gè)Key的Reducer類。進(jìn)行組合和排序時(shí)將具有相同Key值的對(duì)進(jìn)行合并，這些對(duì)來(lái)自不同Mapper。通過(guò)組合和排序后得到的將被送至Redueer類的Reduce方法中進(jìn)行處理并且結(jié)果將寫(xiě)入HDFS管理的輸出文件[8]。

2 K-means算法

追根溯源，K-means算法是由MacQueen[9]于1967年提出，并且用數(shù)學(xué)方法對(duì)算法進(jìn)行了證明。K-means算法由于其簡(jiǎn)單、高效、易實(shí)施等特性受到科學(xué)工作者的青睞，被不斷改進(jìn)優(yōu)化并應(yīng)用于實(shí)踐，目前被廣泛應(yīng)用于文本聚類、考古和自然語(yǔ)言處理等諸多領(lǐng)域。K-means算法的第一步工作是初始聚類中心的選取，然后對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分類后通過(guò)對(duì)每個(gè)聚類平均值的計(jì)算來(lái)調(diào)整聚類中心并且不斷迭代循環(huán)，最終達(dá)到使得類間對(duì)象相似性最小，而類內(nèi)對(duì)象相似性最大的目的。算法步驟：首先是自樣本隨機(jī)選取K個(gè)對(duì)象作為初始聚類中心，然后計(jì)算其它數(shù)據(jù)對(duì)象到聚類中心距離并將其分配到相應(yīng)類，接著計(jì)算每一類中所有對(duì)象平均值作為新聚類中心，循環(huán)上一步與此步驟直至目標(biāo)函數(shù)不再變化[10]。K-means算法本身存在全局搜索能力差、對(duì)初始聚類中心依賴性大、聚類效率和精度都不高，而且容易陷入局部最優(yōu)解等缺點(diǎn)[11]。因此，這些都是科學(xué)工作者們不斷優(yōu)化和改進(jìn)K-means算法的方向。

3 K-means算法MapReduce并行化實(shí)現(xiàn)

通過(guò)MapReduce模型實(shí)現(xiàn)K-means算法并行化的基本思路實(shí)際上就是每一次迭代都啟動(dòng)一個(gè)MapReduce過(guò)程。根據(jù)計(jì)算需求，對(duì)數(shù)據(jù)做按行存儲(chǔ)的安排同時(shí)可按行分片且片間數(shù)據(jù)無(wú)相關(guān)性[12]。具體流程如圖2所示，通過(guò)Map函數(shù)從HDFS的文件中讀取數(shù)據(jù)并通過(guò)每條記錄得到其與各質(zhì)心距離，Map函數(shù)的輸入為原始文件和聚類質(zhì)心，通過(guò)比較得到各記錄到質(zhì)心的距離，對(duì)每個(gè)記錄進(jìn)行分類，將其歸到距離最近質(zhì)心所屬類，最后將記錄以及記錄所屬類寫(xiě)入中間文件，因此Map函數(shù)輸出為中間結(jié)果。在執(zhí)行Map函數(shù)之后，MapReduce首先會(huì)對(duì)輸出結(jié)果進(jìn)行合并，之后再執(zhí)行Reduce函數(shù)，根據(jù)Map函數(shù)的輸出通過(guò)Reduce函數(shù)進(jìn)行聚類中心的更新；同時(shí)對(duì)標(biāo)準(zhǔn)測(cè)度函數(shù)值進(jìn)行計(jì)算，為主函數(shù)是否結(jié)束迭代提供判斷依據(jù)。如果未結(jié)束則繼續(xù)進(jìn)行循環(huán)并且得到的新聚類中心將由下一輪Map函數(shù)使用。在主函數(shù)中調(diào)用MapReduce過(guò)程，每次迭代申請(qǐng)一個(gè)新Job。迭代結(jié)束的判斷標(biāo)準(zhǔn)就是兩次得到平方誤差和差值小于給定閾值，則最后結(jié)果就是Map函數(shù)最后一次中間結(jié)果[13]。

4 Hadoop平臺(tái)下的K-means算法優(yōu)化

4.1 粒子群算法引入

有研究者[14]提出了一種并行基于MapReduce的K-PSO算法。馬漢達(dá)，楊麗娜[15]進(jìn)一步將PSO-KM全部并行運(yùn)行，提出了一種用粒子群算法對(duì)K-means算法的初始聚類中心進(jìn)行優(yōu)化的在Hadoop平臺(tái)上加以實(shí)現(xiàn)的改進(jìn)方法，這種改進(jìn)使得K-means算法和PSO算法都可以用MapReduce模型處理。引入PSO算法在一定程度上克服了K-means算法對(duì)初始聚類中心敏感的問(wèn)題。在Map階段，更新和移動(dòng)并且評(píng)估粒子，之后判斷更新單個(gè)粒子最優(yōu)解，如果粒子有更新則進(jìn)行粒子群最優(yōu)解的更新；然后進(jìn)入Reduce階段，接收更新后粒子并對(duì)粒子信息進(jìn)行合并，且更新粒子群最優(yōu)解。

其中，進(jìn)行PSO算法處理操作的第一步是初始化和構(gòu)建初始粒子群，再以每個(gè)粒子為每個(gè)Map接收新位置、速度、價(jià)值以及單個(gè)粒子最優(yōu)適應(yīng)度，最終的Key為粒子id。Value屬性則是更新后粒子屬性字符串，接收Key和List（Value）的為PSO-Reduce函數(shù)。特定粒子的id即為這個(gè)Key，最新更新的粒子屬性信息包含于Value列表。通過(guò)Reduce函數(shù)實(shí)現(xiàn)信息合并，全局更新粒子群最優(yōu)位置以及粒子群最優(yōu)適應(yīng)度并輸出粒子群最優(yōu)粒子。

4.2 Canopy算法與K-means算法相結(jié)合

朱薔薔、張桂蕓等[16]提出了一種在Hadoop平臺(tái)下將Canopy算法與K-means算法結(jié)合使用的優(yōu)化思想，使用Canopy算法對(duì)數(shù)據(jù)經(jīng)行預(yù)處理，得到K-means算法的K值，并且K值由得到的Canopy個(gè)數(shù)決定。實(shí)驗(yàn)證明，這種優(yōu)化方式具有良好的加速比及可擴(kuò)展性。毛典輝[17]針對(duì)Canopy-Kmeans算法中的Canopy選擇具有隨意性和盲目性的問(wèn)題，提出一種使用“最大最小原則”對(duì)算法進(jìn)行改進(jìn)，并通過(guò)MapReduce并行框架進(jìn)行并行擴(kuò)展的優(yōu)化思想。改進(jìn)后的算法在抗噪能力和分類準(zhǔn)確率上明顯優(yōu)于隨機(jī)挑選Canopy策略?；谝陨涎芯浚R勝宇、王靜宇等[18]提出了一種新的改進(jìn)方式，針對(duì)K-means算法選擇初始聚類中心的盲目性使用余弦相似度度量及Canopy算法進(jìn)行改善，并通過(guò)并行計(jì)算框架實(shí)現(xiàn)并行擴(kuò)展。Canopy算法的過(guò)程首先是進(jìn)行閾值tl、t2的設(shè)定，并且t1要大于t2；然后在數(shù)據(jù)集里隨機(jī)選取中心點(diǎn)并且將與之距離不大于t1的數(shù)據(jù)點(diǎn)放入聚類中心是剛才選取的點(diǎn)的聚簇。之后剔除數(shù)據(jù)集中與中心點(diǎn)距離不大于t2的點(diǎn)，循環(huán)至數(shù)據(jù)集為空。通過(guò)優(yōu)化之后，在Hadoop平臺(tái)下通過(guò)Map及Reduce階段獲得全局Canopy中心集合，并使用其進(jìn)行粗糙聚類之后得到數(shù)個(gè)相互重疊的Canopy聚類集合，將其作為下一步K-means初始聚類中心。所有對(duì)象到簇類中心距離是K-means算法每次迭代都必須計(jì)算的。優(yōu)化之后通過(guò)實(shí)驗(yàn)證明，其在處理海量數(shù)據(jù)時(shí)具有較好的聚類質(zhì)量、加速比及擴(kuò)展性。

4.3 Hash算法引入

通過(guò)散列函數(shù)將任意長(zhǎng)度輸入轉(zhuǎn)化為固定長(zhǎng)度輸出即為Hash算法，也稱為散列算法[19]。對(duì)于海量高維數(shù)據(jù)在Hadoop平臺(tái)下使用K-means算法存在聚類效果不好的問(wèn)題，張波，徐蔚鴻等[20]提出了基于Hash改進(jìn)的并行化并在算法整體并行化時(shí)通過(guò)Combine等機(jī)制改善執(zhí)行效率及并行化程度的優(yōu)化方案。通過(guò)Hash改進(jìn)的并行化方案的原理是將高維數(shù)據(jù)映射至壓縮標(biāo)識(shí)空間，進(jìn)而實(shí)現(xiàn)聚類關(guān)系的挖掘以及初始聚類中心的選取。用Hash算法進(jìn)行初始聚類中心選取就是將不同相似度數(shù)據(jù)散列至不同的地址空間。對(duì)應(yīng)地將相似度大的數(shù)據(jù)散列到同一地址空間。初始聚類中心就是選自最多同義詞的K個(gè)地址空間。在實(shí)現(xiàn)并行化時(shí)，設(shè)計(jì)了3個(gè)獨(dú)立運(yùn)行的Job作業(yè)鏈工作且上一Job輸出為下一輸入。其中第1個(gè)Job用于構(gòu)造散列表，第2個(gè)則是計(jì)算初始聚類中心，第3個(gè)用于完成對(duì)全部數(shù)據(jù)的K-means聚類。最后通過(guò)實(shí)驗(yàn)證明，這種優(yōu)化對(duì)聚類穩(wěn)定性及準(zhǔn)確率都有很好的改善作用。

4.4 遺傳算法與K-means算法相結(jié)合

與K-means算法一樣，遺傳算法也是廣為人知的算法之一[21]。因此將K-means算法與遺傳算法相結(jié)合的研究也吸引著許多研究者。戴文華、焦翠珍[22]等將K-means聚類算法與并行遺傳算法相結(jié)合，對(duì)聚類的結(jié)果及K值進(jìn)行優(yōu)化。之后，賈瑞玉、管玉勇等[23]提出了基于MapReduce模型的并行遺傳K-means算法，實(shí)驗(yàn)證明其優(yōu)化效果良好。實(shí)質(zhì)上，遺傳K-means算法就是把每個(gè)聚類中心坐標(biāo)當(dāng)成染色體基因。聚類中心個(gè)數(shù)就是染色體長(zhǎng)度，對(duì)若干相異染色體進(jìn)行初始化操作并將其當(dāng)成一個(gè)種群進(jìn)行遺傳操作，最終獲得適應(yīng)度最大染色體，而最優(yōu)聚類中心坐標(biāo)就是解析出的各中心點(diǎn)坐標(biāo)。該算法第一步是初始化聚類個(gè)數(shù)K和最大遺傳代數(shù)以及種群個(gè)數(shù)P；第二步是初始化種群也即隨機(jī)產(chǎn)生種群個(gè)數(shù)且每個(gè)都表示一個(gè)聚類結(jié)果的染色體；第三步是對(duì)染色體進(jìn)行K-means操作并評(píng)價(jià)適應(yīng)度和記錄；第四步是對(duì)結(jié)束條件進(jìn)行判斷看是否達(dá)到，若未滿足則進(jìn)行選擇、交叉和變異操作；第五步轉(zhuǎn)到步驟三。在Map和Reduce設(shè)計(jì)過(guò)程中，在Map階段進(jìn)行個(gè)體初始化和適應(yīng)度評(píng)價(jià)以及K-means操作。在Reduce過(guò)程中，針對(duì)相同鍵，滿足停機(jī)條件則輸出各子種群中最優(yōu)個(gè)體后選出最終的最優(yōu)個(gè)體。依據(jù)是染色體末位適應(yīng)度值，若否，則需要完成一個(gè)子種群的遺傳操作。

4.5 人工魚(yú)群算法與K-means算法相結(jié)合

將人工魚(yú)群算法與K-means算法相結(jié)合也是一種優(yōu)化思路[24]。陳書(shū)會(huì)、周蓮英[25]利用人工魚(yú)群算法對(duì)K-means算法進(jìn)行優(yōu)化，并通過(guò)MapReduce并行處理框架進(jìn)行并行處理。通過(guò)afsa全局尋優(yōu)特點(diǎn)在數(shù)據(jù)集中靠魚(yú)群行為搜索最優(yōu)解或與之相近解并將其作為K-means初始值。并行人工魚(yú)群算法思想就是對(duì)魚(yú)群進(jìn)行劃分，劃分之后的各子魚(yú)群在所給數(shù)據(jù)集中獲得此次過(guò)程局部最優(yōu)解。本次運(yùn)行的全局最優(yōu)解通過(guò)對(duì)子魚(yú)群最優(yōu)解進(jìn)行匯總之后獲得。用人工魚(yú)群算法優(yōu)化K-means算法后在執(zhí)行速度和加速比以及準(zhǔn)確度等方面都有很大改善。

4.6 對(duì)數(shù)據(jù)多次采樣并引入密度法

李歡、劉峰等[26]提出了一種優(yōu)化思路，即對(duì)海量數(shù)據(jù)通過(guò)多次采樣的方式進(jìn)行聚類個(gè)數(shù)的確定，再加上用密度法來(lái)確定采樣數(shù)據(jù)聚類中心，原始數(shù)據(jù)聚類中心通過(guò)歸并各樣本中心點(diǎn)的方式得到。在數(shù)據(jù)集合中，一個(gè)數(shù)據(jù)對(duì)象鄰域內(nèi)其它數(shù)據(jù)對(duì)象越多，距離它的路徑越小，就證明密度越大，則以該數(shù)據(jù)對(duì)象作為聚類中心能很好地反映出數(shù)據(jù)分布特征[27]。正是由于這一優(yōu)異特性，因此采用密度法來(lái)選擇初始聚類中心。李歡，劉峰等[26]在Hadoop平臺(tái)下實(shí)施了改進(jìn)后的算法，通過(guò)實(shí)驗(yàn)的方式證明優(yōu)化后的算法在聚類精度和聚類性能上有了明顯提高。

5 結(jié)語(yǔ)

Hadoop和K-means算法都經(jīng)歷了很長(zhǎng)的一段發(fā)展時(shí)間，它們所具有的獨(dú)特優(yōu)勢(shì)使得其被廣大研究者不斷地優(yōu)化和使用。在互聯(lián)網(wǎng)高速發(fā)展的今天，將Hadoop與K-means算法相結(jié)合，并不斷地對(duì)其加以優(yōu)化是處理當(dāng)前海量數(shù)據(jù)的有效途徑。本文介紹的幾種基于Hadoop平臺(tái)的K-means算法優(yōu)化大多是通過(guò)引入其它算法對(duì)K-means算法的初始聚類中心選取及K值進(jìn)行改善來(lái)實(shí)現(xiàn)。將一些能夠彌補(bǔ)K-means算法本身缺點(diǎn)的、高效的算法與K-means算法相結(jié)合，并在Hadoop平臺(tái)下實(shí)現(xiàn)是下一步重點(diǎn)研究方向。

參考文獻(xiàn)：

[1]張石磊，武裝.一種基于Hadoop云計(jì)算平臺(tái)的聚類算法優(yōu)化的研究[J].計(jì)算機(jī)科學(xué)，2012，39（s2）：115-118.

[2]孫玉強(qiáng)，李媛媛，陸勇.基于MapReduce的K-means聚類算法的優(yōu)化[J].計(jì)算機(jī)測(cè)量與控制，2016，24（7）：272-275.

[3]吳夙慧，成穎，鄭彥寧，等.K-means算法研究綜述[J].現(xiàn)代圖書(shū)情報(bào)技術(shù)，2011（5）：28-35.

[4]唐世慶，李云龍，田鳳明，等.基于Hadoop的云計(jì)算與存儲(chǔ)平臺(tái)研究與實(shí)現(xiàn)[J].四川兵工學(xué)報(bào)，2014（8）：97-100.

[5]王宏宇.Hadoop平臺(tái)在云計(jì)算中的應(yīng)用[J].軟件，2011，32（4）：36-38.

[6]王鑫.基于Hadoop平臺(tái)的MapReduce的技術(shù)研究[J].信息通信，2015（6）：5-6.

[7]向小軍，高陽(yáng)，商琳，等.基于Hadoop平臺(tái)的海量文本分類的并行化[J].計(jì)算機(jī)科學(xué)，2011，38（10）：184-188.

[8]謝桂蘭，羅省賢.基于Hadoop MapReduce模型的應(yīng)用研究[J].微型機(jī)與應(yīng)用，2010，29（8）：4-7.

[9]MACQUEEN J.Some methods for classification and analysis of multivariate observations[C].Proc.of Berkeley Symposium on Mathematical Statistics and Probability，1967：281-297.

[10]周愛(ài)武，于亞飛.K-Means聚類算法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（2）：62-65.

[11]洪月華.蜂群K-means聚類算法改進(jìn)研究[J].科技通報(bào)，2016，32（4）：170-173.

[12]李建江，崔健，王聃，等.MapReduce并行編程模型研究綜述[J].電子學(xué)報(bào)，2011，39（11）：2635-2642.

[13]周婷，張君瑛，羅成.基于Hadoop的K-means聚類算法的實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（7）：18-21.

[14]WANG J，YUAN D，JIANG M.Parallel K-PSO based on MapReduce[C].International Conference on Communication Technology，2012：1203-1208.

[15]馬漢達(dá)，楊麗娜.基于Hadoop的PSO-KM聚類算法的并行實(shí)現(xiàn)[J].信息技術(shù)，2015（7）：90-94.

[16]朱薔薔，張桂蕓，劉文龍.基于Hadoop平臺(tái)上面向電影數(shù)據(jù)集Kmeans算法的改進(jìn)[J].哈爾濱師范大學(xué)：自然科學(xué)學(xué)報(bào)，2012，28（1）：32-36.

[17]毛典輝.基于MapReduce的Canopy-Kmeans改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（27）：22-26.

[18]盧勝宇，王靜宇，張曉琳，等.基于Hadoop平臺(tái)的K-means聚類算法優(yōu)化研究[J].內(nèi)蒙古科技大學(xué)學(xué)報(bào)，2016，35（3）：264-268.

[19]KASSELMAN P R.A fast attack on the MD4 hash function[C].COMSIG '97.Proceedings of the 1997 South African Symposium on Communications and Signal Processing，1997：147-150.

[20]張波，徐蔚鴻，陳沅濤，等.基于Hash改進(jìn)的K-means算法并行化設(shè)計(jì)[J].計(jì)算機(jī)工程與科學(xué)，2016，38（10）：1980-1985.

[21]李紅梅.遺傳算法概述[J].軟件導(dǎo)刊，2009（1）：67-68.

[22]戴文華，焦翠珍，何婷婷.基于并行遺傳算法的K-means聚類研究[J].計(jì)算機(jī)科學(xué)，2008，35（6）：171-174.

[23]賈瑞玉，管玉勇，李亞龍.基于MapReduce模型的并行遺傳K-means聚類算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2014，35（2）：657-660.

[24]鄒康，劉婷，鮑韋韋，等.人工魚(yú)群算法研究綜述[J].山西電子技術(shù)，2012（2）：92-93.

[25]陳書(shū)會(huì)，周蓮英.基于 MapReduce的afsa-km聚類算法并行實(shí)現(xiàn)[J].軟件導(dǎo)刊，2016，15（7）：51-54.

[26]李歡，劉鋒，朱二周.基于改進(jìn)K-means算法的海量數(shù)據(jù)分析技術(shù)研究[J].微電子學(xué)與計(jì)算機(jī)，2016，33（5）：52-57.

[27]ERISOGLU M，CALIS N，SAKALLIOGLU S.A new algorithm for initial cluster centers in K-means algorithm[J].Pattern Recognition Letters，2011，32（14）：1701-1705.

（責(zé)任編輯：孫 娟）

英文摘要Abstract：Today， with the rapid development of science and technology， more and more people pay attention to the problem of massive data processing.The combination of K-means clustering algorithm and Hadoop platform is a reliable way to deal with massive data problems.In this paper， we do a brief introduction about Hadoop and K-means algorithm and parallel implementation of K-means clustering algorithm based on MapReduce.At the same time， we do a introduction and elaboration about several optimization methods of K-means algorithm based on Hadoop platform .Finally， the future research directions are discussed.

英文關(guān)鍵詞Key Words： Mass Data Processing；Hadoop；K-means；MapReduce