◆李 莉
(金肯職業(yè)技術(shù)學(xué)院 江蘇 211156)
基于云計(jì)算平臺(tái)Hadoop的并行k-means聚類算法設(shè)計(jì)研究
◆李 莉
(金肯職業(yè)技術(shù)學(xué)院 江蘇 211156)
隨著信息化時(shí)代的到來(lái),也相應(yīng)提升了科技的發(fā)展?,F(xiàn)階段網(wǎng)絡(luò)技術(shù)的發(fā)展也不斷為數(shù)據(jù)庫(kù)的發(fā)展提供技術(shù)支持。在實(shí)際應(yīng)用網(wǎng)絡(luò)技術(shù)時(shí)常常會(huì)出現(xiàn)大量的數(shù)據(jù)需要處理,人們開始致力于探討致聚類研究課題,但是隨著不斷深入的鹽分分析也顯現(xiàn)出較多的問(wèn)題,例如出現(xiàn)了新的計(jì)算環(huán)境還有海量數(shù)據(jù)等。本文主要是探討分析了基于云計(jì)算平臺(tái)Hadoop的并行k-means聚類算法設(shè)計(jì)研究,并且在此基礎(chǔ)之上提供了新的設(shè)計(jì)算法方式以及應(yīng)對(duì)策略。根據(jù)大量的數(shù)據(jù)研究顯示,并行k-means聚類算法設(shè)計(jì)的加速比較為良好,并且具有優(yōu)質(zhì)的數(shù)據(jù)伸縮率性能以及擴(kuò)展率,有效作用于挖掘和分析海量數(shù)據(jù)。
云計(jì)算;平臺(tái)Hadoop;并行k-means;聚類算法設(shè)計(jì);研究探討
現(xiàn)階段,數(shù)據(jù)挖掘當(dāng)中比較重要的課題在于聚類算法設(shè)計(jì),該算法的主要內(nèi)容在于了集合組成抽象對(duì)象或者物理對(duì)象,并轉(zhuǎn)變?yōu)榕c其相類似的對(duì)象簇群的算法過(guò)程。由聚類形成的簇群主要會(huì)集合一組數(shù)據(jù)對(duì)象,并且該對(duì)象之間存在較高的相似度,但是不同簇群當(dāng)中的對(duì)象具有較大的差異性。當(dāng)前的社會(huì)企業(yè),科研組織,政府部門以及商業(yè)領(lǐng)域等都廣泛應(yīng)用數(shù)據(jù)庫(kù)技術(shù),并且在數(shù)據(jù)存儲(chǔ)方面都是通過(guò)不同形式實(shí)現(xiàn)的?,F(xiàn)階段需要亟待解決的問(wèn)題就是怎樣加工海量數(shù)據(jù)進(jìn)行處理和存儲(chǔ),在此基礎(chǔ)之上如何尋找有價(jià)值的數(shù)據(jù)信息,并且可以應(yīng)用在實(shí)際工作當(dāng)中。針對(duì)現(xiàn)在產(chǎn)生和存在的海量數(shù)據(jù),現(xiàn)有的聚類算法已經(jīng)不能滿足該數(shù)據(jù)的要求,尤其是在空間復(fù)雜性和時(shí)間復(fù)雜性上,這就需要聚類算法進(jìn)行全面深化地研究和解決。針對(duì)以上問(wèn)題的解決最重要的措施就是將并行 k-means處理方式應(yīng)用在聚類算法當(dāng)中,這樣可以創(chuàng)新并行聚類算法,顯著加強(qiáng)該算法處理數(shù)據(jù)的實(shí)效性以及功能。
云計(jì)算主要是當(dāng)前比較新穎的商業(yè)計(jì)算模型,Hadoop云計(jì)算平臺(tái)可以實(shí)現(xiàn)并行處理和開發(fā)海量數(shù)據(jù),該平臺(tái)最重要的優(yōu)勢(shì)在于具有較強(qiáng)的擴(kuò)容能力以及運(yùn)行效率,較低的成本,具有顯著的優(yōu)勢(shì)性能。Hadoop云計(jì)算平臺(tái)主要是由MapReduce計(jì)算模型以及HDFS兩部分組成。
MapReduce屬于分布式編程模型,具有較高的效率,主要是實(shí)現(xiàn)數(shù)據(jù)集的生成和處理,該計(jì)算模型主要是應(yīng)用Hadoop云計(jì)算平臺(tái)中的框架,并且需要Map函數(shù)以及Reduce函數(shù),并且可以將運(yùn)行參數(shù)的輸出位置以及輸入位置進(jìn)行明確,加工大數(shù)據(jù)文件切割為較多數(shù)據(jù)塊。其次就是該框架可以將輸入當(dāng)做一組鍵值對(duì),在該環(huán)節(jié),框架可以實(shí)現(xiàn)調(diào)用用戶自行設(shè)置的函數(shù),并且可以有效處理每一組鍵值對(duì)。其次就是為了確保Reduce可以實(shí)現(xiàn)有效輸入,在Shuffle環(huán)節(jié),MapReduce框架主要是利用Http為Reduce提供鍵值對(duì)。再者就是Reduce環(huán)節(jié),該環(huán)節(jié)就可以將所涉及到的所有數(shù)據(jù)進(jìn)行瀏覽,并且可以實(shí)現(xiàn)分別對(duì)應(yīng)不同的Key,對(duì)用戶自行設(shè)定的Reduce函數(shù)進(jìn)行有效執(zhí)行。最后就是輸出環(huán)節(jié),該環(huán)節(jié)主要會(huì)將Reduce輸出的結(jié)果對(duì)應(yīng)顯示在輸出目錄上,這樣就完后了整體MapReduce算法。
HDFS主要是應(yīng)用M/S結(jié)構(gòu),每一個(gè)集群主要的組成為數(shù)據(jù)節(jié)點(diǎn)以及管理節(jié)點(diǎn),每一個(gè)節(jié)點(diǎn)屬于獨(dú)立的PC端。在實(shí)際應(yīng)用時(shí),HDFS高度相似于單機(jī)上的文件系統(tǒng),其主要功能在于可以創(chuàng)建文件目錄,并且實(shí)現(xiàn)文件的復(fù)制,查看,新建以及刪除等。HDFS的底層主要是可以切割文件并且將其分為若干塊,之后在不同的數(shù)據(jù)節(jié)點(diǎn)之上將其分散儲(chǔ)存。需要注意的是,這些塊功能再次分為較多子項(xiàng),并且存儲(chǔ)在不同類型的數(shù)據(jù)節(jié)點(diǎn)之上,這樣就可以實(shí)現(xiàn)容錯(cuò)功能。中心服務(wù)器主要是負(fù)責(zé)數(shù)據(jù)節(jié)點(diǎn)的管理,對(duì)其客戶端訪問(wèn)權(quán)限以及文件的名字空間等。數(shù)據(jù)節(jié)點(diǎn)可以實(shí)現(xiàn)對(duì)節(jié)點(diǎn)存儲(chǔ)的管理和控制。HDSF的核心功能在于數(shù)據(jù)節(jié)點(diǎn)的管理,可以有效加工某一組數(shù)據(jù)結(jié)構(gòu)進(jìn)行維護(hù),還可以將每一個(gè)文件的切割情況,塊的來(lái)源以及狀態(tài)數(shù)據(jù)信息等進(jìn)行詳細(xì)記錄。
由前面的分析我們能夠得出,基于云計(jì)算平臺(tái)Hadoop的并行k-means聚類算法設(shè)計(jì),用戶最主要的工作就是將Reduce函數(shù)以及Map函數(shù)進(jìn)行設(shè)計(jì)和實(shí)現(xiàn),還附帶輸出鍵值對(duì)以及輸入鍵值對(duì),以及包括Reduce函數(shù)以及Map函數(shù)的具體邏輯算法等。
針對(duì)串行的k-means聚類算法設(shè)計(jì)主要的算法流程為:第一步,先隨意選擇K個(gè)樣本,并將其作為聚簇創(chuàng)始的中心點(diǎn),第二步,迭代,首先主要按照不同聚簇的中心點(diǎn)坐標(biāo),并且將上述選擇的樣本下發(fā)到較近距離的聚簇,其次就是將不同聚簇中包含的樣本的平均值進(jìn)行計(jì)算。第三步,收斂。
從上述k-means聚類算法設(shè)計(jì)的主要流程能夠得出,其中最重要的算法工作在于將選擇的樣本下發(fā)到較近距離的聚簇,這樣就可以實(shí)現(xiàn)相互獨(dú)立選擇的樣本,這時(shí)就可以將以上兩個(gè)步驟進(jìn)行并行處理和執(zhí)行。在進(jìn)行迭代時(shí),將相同的操作方式下發(fā)給實(shí)際的算法當(dāng)中,k-means聚類算法設(shè)計(jì)主要是在迭代期間實(shí)現(xiàn)Map與Reduce操作的統(tǒng)一執(zhí)行。
在選擇樣本時(shí)主要是隨機(jī)選擇若干樣本,并將其作為中心點(diǎn),之后將以上形成的中心點(diǎn)共同儲(chǔ)存在HDFS文件,將其當(dāng)做全局變量。以上操作所涉及的迭代主要是由 Map函數(shù),Reduce函數(shù)以及Combine函數(shù)組成的。
Map函數(shù)所以輸入的鍵值對(duì)主要是所處框架之內(nèi)預(yù)設(shè)的格式,其中鍵值對(duì)當(dāng)中的key就是當(dāng)前樣本主要是針對(duì)輸入數(shù)據(jù)文件起始點(diǎn)偏移量,value主要是樣本的各項(xiàng)坐標(biāo)值數(shù)所形成的字符串。第一步,在value當(dāng)中將樣本各個(gè)坐標(biāo)值數(shù)進(jìn)行解析,之后計(jì)算value與中心點(diǎn)之間的距離,并且尋找出最近距離中心點(diǎn)聚簇的下標(biāo),之后將再次生成的鍵值對(duì)輸出,其中所包含的key*是距離聚簇最近的下標(biāo),value*主要是樣本在各個(gè)坐標(biāo)產(chǎn)生的字符串。
為了降低在算法迭代期間產(chǎn)生的數(shù)據(jù)傳輸以及通訊代價(jià),在結(jié)束Map操作之后,在k-means聚類算法之外設(shè)計(jì)Combine操作,之后本地合并處理結(jié)束的Map函數(shù)的數(shù)據(jù)輸出。由于每一個(gè)Map函數(shù)出現(xiàn)的數(shù)據(jù)傳輸可以有線在本地節(jié)點(diǎn)里面進(jìn)行儲(chǔ)存,這就說(shuō)明所有的Combine操作就是在本地進(jìn)行執(zhí)行,這樣就會(huì)產(chǎn)生較小的通信代價(jià)。
Combine函數(shù)產(chǎn)生的輸入鍵值對(duì)中的key主要是聚簇中的下標(biāo),包含的v主要是聚簇分配給key聚簇的樣本之間的各個(gè)坐標(biāo)產(chǎn)生的字符串聯(lián)表。第一步,在字符串聯(lián)表當(dāng)中將各個(gè)樣本顯示在不同坐標(biāo)指數(shù)進(jìn)行解析,再將分別相加每一個(gè)坐標(biāo)軸上產(chǎn)生的坐標(biāo)值數(shù),之后將字符串聯(lián)表當(dāng)中產(chǎn)生的樣本總數(shù)進(jìn)行詳細(xì)記錄。之后產(chǎn)生的鍵值對(duì)當(dāng)中的key*是距離聚簇最近的下標(biāo),value*主要是樣本在各個(gè)坐標(biāo)的總數(shù)以及累加其在各個(gè)坐標(biāo)軸產(chǎn)生的坐標(biāo)值數(shù)。
Reduce函數(shù)產(chǎn)生的輸入鍵值對(duì)中的 key主要是聚簇中的下標(biāo),包含的v主要是由Combine函數(shù)在進(jìn)行數(shù)據(jù)傳輸時(shí)產(chǎn)生的中間結(jié)果。在Reduce函數(shù)當(dāng)中可以將Combine函數(shù)中處理的樣本個(gè)數(shù)以及相對(duì)應(yīng)數(shù)據(jù)節(jié)點(diǎn)在各個(gè)坐標(biāo)軸上的坐標(biāo)值數(shù)累加進(jìn)行優(yōu)先解析,之后在對(duì)應(yīng)相間Reduce函數(shù)在各個(gè)坐標(biāo)軸值數(shù)的累加值數(shù),之后在除以總的樣本數(shù)量,這樣就可以產(chǎn)生新的中心點(diǎn)坐標(biāo)。
按照Reduce函數(shù)所輸出的結(jié)果可以產(chǎn)生新的中心點(diǎn)坐標(biāo),并且可以將HDSF當(dāng)中的文件進(jìn)行實(shí)時(shí)更新,之后在進(jìn)行新的迭代,直至算法收斂。
此次研究所涉及的所有實(shí)驗(yàn)都是通過(guò)云計(jì)算平臺(tái)Hadoop實(shí)現(xiàn)和運(yùn)行的。該云計(jì)算平臺(tái)Hadoop主要是由32核,10臺(tái)設(shè)備組成的。其中雙核2.8G,內(nèi)存4GB的設(shè)備有4臺(tái),四核2.33G,內(nèi)存為8G的設(shè)備有6臺(tái)。云計(jì)算平臺(tái)Hadoop的版本為0.16.0,java的版本為1.4.0-13.不同設(shè)備之間的連接都是采用交換機(jī)實(shí)現(xiàn)的,并且都是應(yīng)用傳輸速率為1000MPa的以太網(wǎng)卡。
此次研究實(shí)驗(yàn)都是采用人工數(shù)據(jù)作為主要的數(shù)據(jù)研究,應(yīng)用48維度。針對(duì)算法性能的測(cè)試,在此次研究實(shí)驗(yàn)當(dāng)中涉及到的數(shù)據(jù)群主要是32G,16G,8G,4G,2G,1G等。
因?yàn)?k-means聚類算法的操作運(yùn)行當(dāng)中包含隨機(jī)初始化中心點(diǎn),所以在進(jìn)行數(shù)據(jù)計(jì)算時(shí)需要進(jìn)行20次的重復(fù)執(zhí)行,每一組數(shù)據(jù)的最終實(shí)驗(yàn)結(jié)果取自于此次計(jì)算重復(fù)執(zhí)行時(shí)間的平均值。
在此次研究實(shí)驗(yàn)當(dāng)中,主要對(duì)k-means聚類算法在進(jìn)行不同數(shù)據(jù)大小處理的加速比,其實(shí)驗(yàn)結(jié)果可以詳見圖1:
圖1 測(cè)試結(jié)果
在上圖能夠得出,k-means聚類算法的加速比無(wú)限接近于線性。隨著不斷增大的數(shù)據(jù)集規(guī)模,就會(huì)相應(yīng)提升k-means聚類算法的加速比性能。造成以上結(jié)果的原因在于k-means聚類算法的Map與Reduce中鍵值對(duì)的對(duì)比比較科學(xué),這樣可以提升算法的速率以及實(shí)效性,使其可以在較短時(shí)間內(nèi)執(zhí)行和實(shí)現(xiàn)。其次就是在并行k-means聚類算法都當(dāng)中,新添加了Combine函數(shù)的操作,這樣就會(huì)在加大程度上降低數(shù)據(jù)節(jié)點(diǎn)與對(duì)應(yīng)節(jié)點(diǎn)之間的通訊代價(jià),加強(qiáng)了數(shù)據(jù)集的規(guī)模,提升了通訊量的減少比例。所以,在增加數(shù)據(jù)集的規(guī)模時(shí),就會(huì)相應(yīng)提升k-means聚類算法的性能。
在此次研究分析當(dāng)中,還進(jìn)行了k-means聚類算法的擴(kuò)展率測(cè)試。首先就是測(cè)試在不同大小數(shù)據(jù)集1G,2G,4G,在數(shù)據(jù)節(jié)點(diǎn)1,數(shù)據(jù)節(jié)點(diǎn)2,數(shù)據(jù)節(jié)點(diǎn)4上的上的運(yùn)行效率,其次就是計(jì)算在不同大小2G,4G,8G,以及16G在數(shù)據(jù)節(jié)點(diǎn)2,數(shù)據(jù)節(jié)點(diǎn)4,數(shù)據(jù)節(jié)點(diǎn)8上以及數(shù)據(jù)節(jié)點(diǎn)16上的運(yùn)行效率,最后就是測(cè)試在不同大小數(shù)據(jù)集4G,8G,16G以及32G,在數(shù)據(jù)節(jié)點(diǎn)4,數(shù)據(jù)節(jié)點(diǎn)8,數(shù)據(jù)節(jié)點(diǎn)16以及數(shù)據(jù)節(jié)點(diǎn)32上的運(yùn)行效率,所得出的實(shí)驗(yàn)結(jié)果詳情見圖2。
圖2 測(cè)試不同數(shù)據(jù)節(jié)點(diǎn)擴(kuò)展性的實(shí)驗(yàn)結(jié)果
從上圖能夠得出,針對(duì)相同數(shù)據(jù)集,如果計(jì)算平臺(tái)上的數(shù)據(jù)節(jié)點(diǎn)的數(shù)量以及測(cè)試數(shù)據(jù)集大小呈現(xiàn)同比例上升時(shí),就會(huì)相應(yīng)降低k-means聚類算法的擴(kuò)展率。造成以上原因的主要因素在于,當(dāng)增加數(shù)據(jù)節(jié)點(diǎn)的數(shù)量時(shí),就會(huì)相應(yīng)增加各個(gè)數(shù)據(jù)節(jié)點(diǎn)之間的通訊代價(jià)。如果數(shù)據(jù)集的規(guī)模也在不斷擴(kuò)大,就會(huì)相應(yīng)提升算法執(zhí)行的時(shí)間。然而,從此次研究實(shí)驗(yàn)結(jié)果可以看出,隨著不斷增加的數(shù)據(jù)集國(guó)模,就會(huì)相應(yīng)提升k-means聚類算法的擴(kuò)展率性能。造成以上原因的主要因素在于,,如果提升數(shù)據(jù)集規(guī)模,就可以將每一個(gè)數(shù)據(jù)節(jié)點(diǎn)的計(jì)算能力進(jìn)行提升。在分析對(duì)比k-means聚類算法的加速比可以看住,在 k-means聚類算法當(dāng)中添加Combine時(shí),隨著不斷提升的數(shù)據(jù)集規(guī)模,就會(huì)相應(yīng)提升各個(gè)數(shù)據(jù)節(jié)點(diǎn)之間的通信代價(jià)減少比例。
現(xiàn)階段,各個(gè)行業(yè)領(lǐng)域都開始普遍使用云計(jì)算方式,并且借助于其所具有的數(shù)據(jù)挖掘優(yōu)勢(shì)以及聚類算法優(yōu)勢(shì)等實(shí)現(xiàn)企業(yè)的生產(chǎn)經(jīng)營(yíng)。以上兩個(gè)方面也已經(jīng)成為現(xiàn)階段國(guó)際上熱門課題研究。從云計(jì)算平臺(tái)Hadoop的并行k-means聚類算法設(shè)計(jì)研究現(xiàn)狀可以看出,其未來(lái)的主要研究方向在于:探討分析聚類算法并行化的一般規(guī)律,并且可以尋找出數(shù)據(jù)集大小,數(shù)據(jù)節(jié)點(diǎn)數(shù)量以及算法復(fù)雜性三者之間的關(guān)系。
[1]華志潔.基于 Hadoop云計(jì)算平臺(tái)仿百度智能輸入提示算法的研究與實(shí)現(xiàn)[J].天津科技,2015.
[2]陳靜.基于 Hadoop云計(jì)算平臺(tái)的文本處理算法的研究與改進(jìn)[J].天津科技,2016.
[3]張玉峰,曾奕棠.基于云聚類挖掘的物流信息智能分析方法研究[J].情報(bào)資料工作,2016.
[4]王鳳領(lǐng).基于 Hadoop高校教育資源云存儲(chǔ)平臺(tái)構(gòu)建研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2016.
[5]謝雪蓮,李蘭友.基于云計(jì)算的并行K-means聚類算法研究[J].計(jì)算機(jī)測(cè)量與控制,2015.
[6]段慶偉,鐵木巴干.基于 Hadoop云計(jì)算平臺(tái)的新浪微博數(shù)據(jù)聚類分析算法研究[J].遼寧科技學(xué)院學(xué)報(bào),2017.
[7]武森,馮小東,張曉楠.基于MapReduce的大規(guī)模文本聚類并行化[J].北京科技大學(xué)學(xué)報(bào),2015.
[8]趙衛(wèi)中,馬慧芳,傅燕翔.基于云計(jì)算平臺(tái) Hadoop的并行k-means聚類算法設(shè)計(jì)研究[J].計(jì)算機(jī)科學(xué),2016.