基于Hadoop平臺的K—means算法優(yōu)化綜述
2017-07-12 13:46:51孟佳偉孫紅
軟件導(dǎo)刊 2017年6期
孟佳偉+孫紅
摘要：在科技高速發(fā)展的今天，海量數(shù)據(jù)處理問題受到人們廣泛關(guān)注。將K-means聚類算法與Hadoop平臺相結(jié)合是處理海量數(shù)據(jù)問題的一條可靠途徑。簡單介紹Hadoop和K-means算法以及K-means聚類算法MapReduce并行化實現(xiàn)，并闡述目前Hadoop平臺下K-means算法的幾種優(yōu)化方式，最后提出研究展望。
關(guān)鍵詞：海量數(shù)據(jù)處理；Hadoop；K-means；MapReduce
DOIDOI：10.11907/rjdk.171405
中圖分類號：TP301
文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2017）006-0208-04
0 引言
隨著科學(xué)技術(shù)的飛速發(fā)展，互聯(lián)網(wǎng)技術(shù)已經(jīng)深入到社會的各個領(lǐng)域，由此，數(shù)據(jù)量呈現(xiàn)出一種指數(shù)級增長[1]。如何高效地對這些海量數(shù)據(jù)進(jìn)行處理和分析已成為當(dāng)前研究熱點。隨著數(shù)據(jù)規(guī)模越來越大，在面對海量數(shù)據(jù)時，傳統(tǒng)的數(shù)據(jù)挖掘工作會出現(xiàn)儲存量不足、用時過長等缺點[2]。而云計算的出現(xiàn)則為解決這些問題提供了新思路，將云計算與傳統(tǒng)數(shù)據(jù)挖掘方法相結(jié)合并對其進(jìn)行優(yōu)化是科學(xué)工作者們不斷研究的方向。
聚類分析是數(shù)據(jù)挖掘方法中的常用方法。1975年，Hartigan對聚類算法提出了系統(tǒng)論述[3]。在眾多聚類算法中，K-means算法是被應(yīng)用與研究最廣泛的算法。如今，云計算已經(jīng)得到了人們的廣泛關(guān)注，而Hadoop平臺是一個可以開發(fā)和并行處理大數(shù)據(jù)的云計算平臺。作為一種由分布式技術(shù)、網(wǎng)絡(luò)計算機(jī)技術(shù)及并行技術(shù)發(fā)展而來的產(chǎn)物，Hadoop可以說是一種為了適應(yīng)大規(guī)模數(shù)據(jù)存儲以及計算而衍生出的模型構(gòu)架[4]。本文將對當(dāng)前基于Hadoop平臺的K-means算法的各種優(yōu)化方法進(jìn)行綜述，并提出展望。
1 Hadoop
從最初版本HDFS和MapReduce于2004年開始實施，到2011年1.0.0版本釋出標(biāo)志Hadoop已初具生產(chǎn)規(guī)模，經(jīng)歷了短短不到十年的時間。作為一種開源云計算模型，Hadoop模仿并實現(xiàn)了Google云計算的主要技術(shù)，不但可移植性強(qiáng)，而且使用Java語言進(jìn)行編寫[5]。其最早是來自于Google的一款名為MapReduce的編程模型包。MapReduce最早是由Google公司在2004年提出的一種可伸縮并且是線性的用于處理海量數(shù)據(jù)的并行編程模型[6]。Hadoop平臺的出現(xiàn)極大地便利了對于處理海量數(shù)據(jù)和應(yīng)用程序的算法研究。Hadoop框架中最核心的部分是MapReduce和HDFS。分布式文件系統(tǒng)Hadoop Distributed File System的縮寫即HDFS，其具有極高的容錯性并且對機(jī)器要求不高，適合部署在廉價的機(jī)器上，為分布式計算存儲提供底層支持。其能夠提供高吞吐的數(shù)據(jù)訪問，因而適合于大規(guī)模數(shù)據(jù)集上的應(yīng)用。
MapReduce可以使程序自動分布到一個超大集群上并發(fā)執(zhí)行，并且這個超大集群可以由普通機(jī)器組成[7]。其中，Map將一個任務(wù)分解為多個任務(wù)。而Reduce則是將分解之后的多任務(wù)的處理結(jié)果進(jìn)行匯總并且得出分析結(jié)果。由大量機(jī)器組成的機(jī)器集群可以被視作分布式系統(tǒng)的資源池，通過對并行任務(wù)進(jìn)行拆分并且交給空閑機(jī)器資源處理這種方式提高了計算效率。對MapReduce的工作流程進(jìn)行展示如圖1所示，Map對任務(wù)進(jìn)行分解，Reduce則負(fù)責(zé)合并。通過Map函數(shù)及Reduce函數(shù)對一組輸入鍵值對（Key/Value）的計算，得到一組輸出鍵值對。一個Mapper類、Reducer類和一個創(chuàng)建JobConf的驅(qū)動函數(shù)組成了運(yùn)行于Hadoop平臺下的MapReduce應(yīng)用程序。另外若有需要，還可以有一個Combiner類，實際上該類也是Reducer的一種實現(xiàn)。基本計算流程首先將輸入數(shù)據(jù)劃分為數(shù)據(jù)塊，之后處理數(shù)據(jù)塊得到
2 K-means算法
追根溯源，K-means算法是由MacQueen[9]于1967年提出，并且用數(shù)學(xué)方法對算法進(jìn)行了證明。K-means算法由于其簡單、高效、易實施等特性受到科學(xué)工作者的青睞，被不斷改進(jìn)優(yōu)化并應(yīng)用于實踐，目前被廣泛應(yīng)用于文本聚類、考古和自然語言處理等諸多領(lǐng)域。K-means算法的第一步工作是初始聚類中心的選取，然后對數(shù)據(jù)點進(jìn)行分類后通過對每個聚類平均值的計算來調(diào)整聚類中心并且不斷迭代循環(huán)，最終達(dá)到使得類間對象相似性最小，而類內(nèi)對象相似性最大的目的。算法步驟：首先是自樣本隨機(jī)選取K個對象作為初始聚類中心，然后計算其它數(shù)據(jù)對象到聚類中心距離并將其分配到相應(yīng)類，接著計算每一類中所有對象平均值作為新聚類中心，循環(huán)上一步與此步驟直至目標(biāo)函數(shù)不再變化[10]。K-means算法本身存在全局搜索能力差、對初始聚類中心依賴性大、聚類效率和精度都不高，而且容易陷入局部最優(yōu)解等缺點[11]。因此，這些都是科學(xué)工作者們不斷優(yōu)化和改進(jìn)K-means算法的方向。
3 K-means算法MapReduce并行化實現(xiàn)
通過MapReduce模型實現(xiàn)K-means算法并行化的基本思路實際上就是每一次迭代都啟動一個MapReduce過程。根據(jù)計算需求，對數(shù)據(jù)做按行存儲的安排同時可按行分片且片間數(shù)據(jù)無相關(guān)性[12]。具體流程如圖2所示，通過Map函數(shù)從HDFS的文件中讀取數(shù)據(jù)并通過每條記錄得到其與各質(zhì)心距離，Map函數(shù)的輸入為原始文件和聚類質(zhì)心，通過比較得到各記錄到質(zhì)心的距離，對每個記錄進(jìn)行分類，將其歸到距離最近質(zhì)心所屬類，最后將記錄以及記錄所屬類寫入中間文件，因此Map函數(shù)輸出為中間結(jié)果。在執(zhí)行Map函數(shù)之后，MapReduce首先會對輸出結(jié)果進(jìn)行合并，之后再執(zhí)行Reduce函數(shù)，根據(jù)Map函數(shù)的輸出通過Reduce函數(shù)進(jìn)行聚類中心的更新；同時對標(biāo)準(zhǔn)測度函數(shù)值進(jìn)行計算，為主函數(shù)是否結(jié)束迭代提供判斷依據(jù)。如果未結(jié)束則繼續(xù)進(jìn)行循環(huán)并且得到的新聚類中心將由下一輪Map函數(shù)使用。在主函數(shù)中調(diào)用MapReduce過程，每次迭代申請一個新Job。迭代結(jié)束的判斷標(biāo)準(zhǔn)就是兩次得到平方誤差和差值小于給定閾值，則最后結(jié)果就是Map函數(shù)最后一次中間結(jié)果[13]。
4 Hadoop平臺下的K-means算法優(yōu)化
4.1 粒子群算法引入
有研究者[14]提出了一種并行基于MapReduce的K-PSO算法。馬漢達(dá)，楊麗娜[15]進(jìn)一步將PSO-KM全部并行運(yùn)行，提出了一種用粒子群算法對K-means算法的初始聚類中心進(jìn)行優(yōu)化的在Hadoop平臺上加以實現(xiàn)的改進(jìn)方法，這種改進(jìn)使得K-means算法和PSO算法都可以用MapReduce模型處理。引入PSO算法在一定程度上克服了K-means算法對初始聚類中心敏感的問題。在Map階段，更新和移動并且評估粒子，之后判斷更新單個粒子最優(yōu)解，如果粒子有更新則進(jìn)行粒子群最優(yōu)解的更新；然后進(jìn)入Reduce階段，接收更新后粒子并對粒子信息進(jìn)行合并，且更新粒子群最優(yōu)解。
其中，進(jìn)行PSO算法處理操作的第一步是初始化和構(gòu)建初始粒子群，再以每個粒子為每個Map接收新位置、速度、價值以及單個粒子最優(yōu)適應(yīng)度，最終的Key為粒子id。Value屬性則是更新后粒子屬性字符串，接收Key和List（Value）的為PSO-Reduce函數(shù)。特定粒子的id即為這個Key，最新更新的粒子屬性信息包含于Value列表。通過Reduce函數(shù)實現(xiàn)信息合并，全局更新粒子群最優(yōu)位置以及粒子群最優(yōu)適應(yīng)度并輸出粒子群最優(yōu)粒子。
4.2 Canopy算法與K-means算法相結(jié)合
朱薔薔、張桂蕓等[16]提出了一種在Hadoop平臺下將Canopy算法與K-means算法結(jié)合使用的優(yōu)化思想，使用Canopy算法對數(shù)據(jù)經(jīng)行預(yù)處理，得到K-means算法的K值，并且K值由得到的Canopy個數(shù)決定。實驗證明，這種優(yōu)化方式具有良好的加速比及可擴(kuò)展性。毛典輝[17]針對Canopy-Kmeans算法中的Canopy選擇具有隨意性和盲目性的問題，提出一種使用“最大最小原則”對算法進(jìn)行改進(jìn)，并通過MapReduce并行框架進(jìn)行并行擴(kuò)展的優(yōu)化思想。改進(jìn)后的算法在抗噪能力和分類準(zhǔn)確率上明顯優(yōu)于隨機(jī)挑選Canopy策略?；谝陨涎芯?，盧勝宇、王靜宇等[18]提出了一種新的改進(jìn)方式，針對K-means算法選擇初始聚類中心的盲目性使用余弦相似度度量及Canopy算法進(jìn)行改善，并通過并行計算框架實現(xiàn)并行擴(kuò)展。Canopy算法的過程首先是進(jìn)行閾值tl、t2的設(shè)定，并且t1要大于t2；然后在數(shù)據(jù)集里隨機(jī)選取中心點并且將與之距離不大于t1的數(shù)據(jù)點放入聚類中心是剛才選取的點的聚簇。之后剔除數(shù)據(jù)集中與中心點距離不大于t2的點，循環(huán)至數(shù)據(jù)集為空。通過優(yōu)化之后，在Hadoop平臺下通過Map及Reduce階段獲得全局Canopy中心集合，并使用其進(jìn)行粗糙聚類之后得到數(shù)個相互重疊的Canopy聚類集合，將其作為下一步K-means初始聚類中心。所有對象到簇類中心距離是K-means算法每次迭代都必須計算的。優(yōu)化之后通過實驗證明，其在處理海量數(shù)據(jù)時具有較好的聚類質(zhì)量、加速比及擴(kuò)展性。
4.3 Hash算法引入
通過散列函數(shù)將任意長度輸入轉(zhuǎn)化為固定長度輸出即為Hash算法，也稱為散列算法[19]。對于海量高維數(shù)據(jù)在Hadoop平臺下使用K-means算法存在聚類效果不好的問題，張波，徐蔚鴻等[20]提出了基于Hash改進(jìn)的并行化并在算法整體并行化時通過Combine等機(jī)制改善執(zhí)行效率及并行化程度的優(yōu)化方案。通過Hash改進(jìn)的并行化方案的原理是將高維數(shù)據(jù)映射至壓縮標(biāo)識空間，進(jìn)而實現(xiàn)聚類關(guān)系的挖掘以及初始聚類中心的選取。用Hash算法進(jìn)行初始聚類中心選取就是將不同相似度數(shù)據(jù)散列至不同的地址空間。對應(yīng)地將相似度大的數(shù)據(jù)散列到同一地址空間。初始聚類中心就是選自最多同義詞的K個地址空間。在實現(xiàn)并行化時，設(shè)計了3個獨立運(yùn)行的Job作業(yè)鏈工作且上一Job輸出為下一輸入。其中第1個Job用于構(gòu)造散列表，第2個則是計算初始聚類中心，第3個用于完成對全部數(shù)據(jù)的K-means聚類。最后通過實驗證明，這種優(yōu)化對聚類穩(wěn)定性及準(zhǔn)確率都有很好的改善作用。
4.4 遺傳算法與K-means算法相結(jié)合
與K-means算法一樣，遺傳算法也是廣為人知的算法之一[21]。因此將K-means算法與遺傳算法相結(jié)合的研究也吸引著許多研究者。戴文華、焦翠珍[22]等將K-means聚類算法與并行遺傳算法相結(jié)合，對聚類的結(jié)果及K值進(jìn)行優(yōu)化。之后，賈瑞玉、管玉勇等[23]提出了基于MapReduce模型的并行遺傳K-means算法，實驗證明其優(yōu)化效果良好。實質(zhì)上，遺傳K-means算法就是把每個聚類中心坐標(biāo)當(dāng)成染色體基因。聚類中心個數(shù)就是染色體長度，對若干相異染色體進(jìn)行初始化操作并將其當(dāng)成一個種群進(jìn)行遺傳操作，最終獲得適應(yīng)度最大染色體，而最優(yōu)聚類中心坐標(biāo)就是解析出的各中心點坐標(biāo)。該算法第一步是初始化聚類個數(shù)K和最大遺傳代數(shù)以及種群個數(shù)P；第二步是初始化種群也即隨機(jī)產(chǎn)生種群個數(shù)且每個都表示一個聚類結(jié)果的染色體；第三步是對染色體進(jìn)行K-means操作并評價適應(yīng)度和記錄；第四步是對結(jié)束條件進(jìn)行判斷看是否達(dá)到，若未滿足則進(jìn)行選擇、交叉和變異操作；第五步轉(zhuǎn)到步驟三。在Map和Reduce設(shè)計過程中，在Map階段進(jìn)行個體初始化和適應(yīng)度評價以及K-means操作。在Reduce過程中，針對相同鍵，滿足停機(jī)條件則輸出各子種群中最優(yōu)個體后選出最終的最優(yōu)個體。依據(jù)是染色體末位適應(yīng)度值，若否，則需要完成一個子種群的遺傳操作。
4.5 人工魚群算法與K-means算法相結(jié)合
將人工魚群算法與K-means算法相結(jié)合也是一種優(yōu)化思路[24]。陳書會、周蓮英[25]利用人工魚群算法對K-means算法進(jìn)行優(yōu)化，并通過MapReduce并行處理框架進(jìn)行并行處理。通過afsa全局尋優(yōu)特點在數(shù)據(jù)集中靠魚群行為搜索最優(yōu)解或與之相近解并將其作為K-means初始值。并行人工魚群算法思想就是對魚群進(jìn)行劃分，劃分之后的各子魚群在所給數(shù)據(jù)集中獲得此次過程局部最優(yōu)解。本次運(yùn)行的全局最優(yōu)解通過對子魚群最優(yōu)解進(jìn)行匯總之后獲得。用人工魚群算法優(yōu)化K-means算法后在執(zhí)行速度和加速比以及準(zhǔn)確度等方面都有很大改善。
4.6 對數(shù)據(jù)多次采樣并引入密度法
李歡、劉峰等[26]提出了一種優(yōu)化思路，即對海量數(shù)據(jù)通過多次采樣的方式進(jìn)行聚類個數(shù)的確定，再加上用密度法來確定采樣數(shù)據(jù)聚類中心，原始數(shù)據(jù)聚類中心通過歸并各樣本中心點的方式得到。在數(shù)據(jù)集合中，一個數(shù)據(jù)對象鄰域內(nèi)其它數(shù)據(jù)對象越多，距離它的路徑越小，就證明密度越大，則以該數(shù)據(jù)對象作為聚類中心能很好地反映出數(shù)據(jù)分布特征[27]。正是由于這一優(yōu)異特性，因此采用密度法來選擇初始聚類中心。李歡，劉峰等[26]在Hadoop平臺下實施了改進(jìn)后的算法，通過實驗的方式證明優(yōu)化后的算法在聚類精度和聚類性能上有了明顯提高。
5 結(jié)語
Hadoop和K-means算法都經(jīng)歷了很長的一段發(fā)展時間，它們所具有的獨特優(yōu)勢使得其被廣大研究者不斷地優(yōu)化和使用。在互聯(lián)網(wǎng)高速發(fā)展的今天，將Hadoop與K-means算法相結(jié)合，并不斷地對其加以優(yōu)化是處理當(dāng)前海量數(shù)據(jù)的有效途徑。本文介紹的幾種基于Hadoop平臺的K-means算法優(yōu)化大多是通過引入其它算法對K-means算法的初始聚類中心選取及K值進(jìn)行改善來實現(xiàn)。將一些能夠彌補(bǔ)K-means算法本身缺點的、高效的算法與K-means算法相結(jié)合，并在Hadoop平臺下實現(xiàn)是下一步重點研究方向。
參考文獻(xiàn)：
[1]張石磊，武裝.一種基于Hadoop云計算平臺的聚類算法優(yōu)化的研究[J].計算機(jī)科學(xué)，2012，39（s2）：115-118.
[2]孫玉強(qiáng)，李媛媛，陸勇.基于MapReduce的K-means聚類算法的優(yōu)化[J].計算機(jī)測量與控制，2016，24（7）：272-275.
[3]吳夙慧，成穎，鄭彥寧，等.K-means算法研究綜述[J].現(xiàn)代圖書情報技術(shù)，2011（5）：28-35.
[4]唐世慶，李云龍，田鳳明，等.基于Hadoop的云計算與存儲平臺研究與實現(xiàn)[J].四川兵工學(xué)報，2014（8）：97-100.
[5]王宏宇.Hadoop平臺在云計算中的應(yīng)用[J].軟件，2011，32（4）：36-38.
[6]王鑫.基于Hadoop平臺的MapReduce的技術(shù)研究[J].信息通信，2015（6）：5-6.
[7]向小軍，高陽，商琳，等.基于Hadoop平臺的海量文本分類的并行化[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]周愛武，于亞飛.K-Means聚類算法的研究[J].計算機(jī)技術(shù)與發(fā)展，2011，21（2）：62-65.
[11]洪月華.蜂群K-means聚類算法改進(jìn)研究[J].科技通報，2016，32（4）：170-173.
[12]李建江，崔健，王聃，等.MapReduce并行編程模型研究綜述[J].電子學(xué)報，2011，39（11）：2635-2642.
[13]周婷，張君瑛，羅成.基于Hadoop的K-means聚類算法的實現(xiàn)[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聚類算法的并行實現(xiàn)[J].信息技術(shù)，2015（7）：90-94.
[16]朱薔薔，張桂蕓，劉文龍.基于Hadoop平臺上面向電影數(shù)據(jù)集Kmeans算法的改進(jìn)[J].哈爾濱師范大學(xué)：自然科學(xué)學(xué)報，2012，28（1）：32-36.
[17]毛典輝.基于MapReduce的Canopy-Kmeans改進(jìn)算法[J].計算機(jī)工程與應(yīng)用，2012，48（27）：22-26.
[18]盧勝宇，王靜宇，張曉琳，等.基于Hadoop平臺的K-means聚類算法優(yōu)化研究[J].內(nèi)蒙古科技大學(xué)學(xué)報，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ī)工程與科學(xué)，2016，38（10）：1980-1985.
[21]李紅梅.遺傳算法概述[J].軟件導(dǎo)刊，2009（1）：67-68.
[22]戴文華，焦翠珍，何婷婷.基于并行遺傳算法的K-means聚類研究[J].計算機(jī)科學(xué)，2008，35（6）：171-174.
[23]賈瑞玉，管玉勇，李亞龍.基于MapReduce模型的并行遺傳K-means聚類算法[J].計算機(jī)工程與設(shè)計，2014，35（2）：657-660.
[24]鄒康，劉婷，鮑韋韋，等.人工魚群算法研究綜述[J].山西電子技術(shù)，2012（2）：92-93.
[25]陳書會，周蓮英.基于 MapReduce的afsa-km聚類算法并行實現(xiàn)[J].軟件導(dǎo)刊，2016，15（7）：51-54.
[26]李歡，劉鋒，朱二周.基于改進(jìn)K-means算法的海量數(shù)據(jù)分析技術(shù)研究[J].微電子學(xué)與計算機(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
