云計(jì)算平臺上的Canopy

1、云計(jì)算平臺上的Canopy摘要：針對大數(shù)據(jù)的高維特性及海量性，提出云計(jì)算平臺中的CanopyKmeans并行聚類算法，通過三角不等式原理，能夠使計(jì)算冗余降低，使算法執(zhí)行速度得到提高。對CanopyKmeans并行聚類算法進(jìn)行深入的研究，并且在大量不同大小數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果說明，所設(shè)計(jì)的并行聚類算法具有良好的加速比、數(shù)據(jù)伸縮率及擴(kuò)展率等特點(diǎn)，能夠在海量數(shù)據(jù)挖掘及分析中使用。關(guān)鍵詞：云計(jì)算平臺;CanopyKmeans算法;并行聚類算法;大數(shù)據(jù)挖掘;集群數(shù)據(jù);數(shù)據(jù)分析中圖分類號：TN911.134文獻(xiàn)標(biāo)識碼：A文章編號：1004373X202119007804Abstract：TheCanopyK

2、meansparallelclusteringalgorithmincloudcomputingplatformisproposedforthehighdimensionalfeatureandmassivenatureofbigdat.Thecomputationalredundancyofthealgorithmcanbereducedanditsexecutionspeedcanbeimprovedaccordingtotheprincipleoftriangularinequality.CanopyKmeansparallelclusteringalgorithmisstudiedin

3、depth.Theresultsfromexperimentsofalargenumberofdatasetsshowthatthedesignedparallelclusteringalgorithmhasthecharacteristicsofhighaccelerationratio，anddatascalabilityandexpansionrate，andcanbeusedinmassivedataminingandanalysis.Keywords：cloudcomputingplatform;CanopyKmeansalgorithm;parallelclusteringalgo

4、rithm;bigdatamining;clusteringdata;dataanalysis目前，在大數(shù)據(jù)處理過程中大局部都是使用分布式或者并行架構(gòu)，使系統(tǒng)擴(kuò)展性得到提高，并且通過多線程并行式結(jié)構(gòu)、基于Apache的開源云計(jì)算Hadoop平臺進(jìn)行實(shí)現(xiàn)，其中，使用最為廣泛的就是Kmeans算法。相關(guān)研究人員提出將MPI作為根底的分布式聚類，其雖然能夠通過集中式存儲，使算法時(shí)效性得到提高，但是此算法在進(jìn)行計(jì)算的過程中為單節(jié)點(diǎn)運(yùn)行，在大數(shù)據(jù)處理聚類分析任務(wù)過程中的算法效率并不快【1】。所以，又提出CanopyKmeans改進(jìn)算法，對于傳統(tǒng)算法的問題，使用最小最大的原那么，通過云計(jì)算平臺集群計(jì)算及存

5、儲能力，使此算法的有效性及時(shí)效性得到提高。本文基于Kmeans算法，使用三角不等式原理，提出CanopyKmeans并行聚類算法【2】。通過開源云計(jì)算平臺及分布式框架，結(jié)合三角不等式定理，并且在大數(shù)據(jù)預(yù)處理過程中實(shí)現(xiàn)原始大數(shù)據(jù)預(yù)處理，實(shí)現(xiàn)算法的改進(jìn)。在實(shí)現(xiàn)數(shù)據(jù)挖掘的過程中，主要特點(diǎn)就是從海量數(shù)據(jù)中將有價(jià)值的信息及時(shí)提取出來。在網(wǎng)絡(luò)時(shí)代到來之后，現(xiàn)代數(shù)據(jù)種類及數(shù)據(jù)量也都在不斷的提高，傳統(tǒng)數(shù)據(jù)挖掘技術(shù)已經(jīng)無法使數(shù)據(jù)挖掘需求得到滿足。在云計(jì)算時(shí)代中，海量數(shù)據(jù)在不同計(jì)算機(jī)中分布，目前聚類算法在時(shí)間及空間復(fù)雜性方面都無法使此問題得到解決。那么本文的主要研究思路就是在目前聚類算法中使用并行處理技術(shù)，使聚類

6、算法時(shí)間及空間的復(fù)雜度得到降低，以此使聚類時(shí)間得到縮短。1.1編程的思想MapReduce屬于海量數(shù)據(jù)處理的并行編程模式及計(jì)算框架，其在大規(guī)模數(shù)據(jù)集并行計(jì)算中使用。簡單來說，MapReduce為任務(wù)分解及結(jié)果匯總【3】。首先，就要得到聚類數(shù)據(jù)N個(gè)樣本對象，將其定義為：N指的是樣本總數(shù)量，也就是每個(gè)樣本都是通過m個(gè)屬性共同特征所構(gòu)成。初始數(shù)據(jù)以數(shù)據(jù)存儲節(jié)點(diǎn)和Mapper個(gè)數(shù)量劃分成為相應(yīng)數(shù)據(jù)集數(shù)量，能夠?yàn)镸apper節(jié)點(diǎn)分配數(shù)據(jù)集實(shí)現(xiàn)獨(dú)立執(zhí)行，之后利用相應(yīng)的Reducer處理結(jié)果，并且對下一輪迭代進(jìn)行判斷【4】。1.2基于距離三角不等式的聚類算法在云計(jì)算平臺中的MapReduce框架中，通過傳統(tǒng)

7、Kmeans算法和距離三角不等式定理相互結(jié)合，從而提出基于距離三角不等式聚類算法。此算法使用三角不等式定理，任何一個(gè)三角形的兩邊之和都比第三邊要大，兩邊之差要比第三邊小。使其擴(kuò)充到歐幾里得空間，因?yàn)闅W氏距離能夠使三角不等式原理得到滿足，從而能夠降低聚類算法計(jì)算過程中的復(fù)雜度，使大數(shù)據(jù)聚類分析效率得到提高。假設(shè)在歐幾里得空間中有X，C1，C2三個(gè)任意數(shù)據(jù)點(diǎn)，數(shù)據(jù)點(diǎn)之間的距離能夠滿足三角不等式原理：dX，C1+dC1，C2dX，C2，dC1，C2-dX，C1dX，C2。如果X指的是數(shù)據(jù)空間中的任何數(shù)據(jù)點(diǎn)，C1和C2都是兩個(gè)簇中心點(diǎn)。假設(shè)2dX，C1dC1，C2，并且在兩邊減去dX，C1，那么就有2

8、dX，C1-dX，C1dC1，C2-dX，C1。所以，假設(shè)2dX，C1dC1，C2，那么那么有dX，C1由上述原理可知，Kmeans的算法思想就是通過預(yù)處理之后的初始中心點(diǎn)對不同中心點(diǎn)彼此最短距離進(jìn)行計(jì)算，之后以三角不等式原理對集合中的數(shù)據(jù)點(diǎn)到第一個(gè)數(shù)據(jù)中心點(diǎn)距離進(jìn)行計(jì)算。假設(shè)數(shù)據(jù)點(diǎn)到中心點(diǎn)的距離的兩倍小于或者等于第一個(gè)數(shù)據(jù)中心點(diǎn)到其他數(shù)據(jù)中心點(diǎn)的最短距離，那么此數(shù)據(jù)點(diǎn)就為第一個(gè)數(shù)據(jù)中心點(diǎn)，將其標(biāo)記為第一類。以此類推，實(shí)現(xiàn)全部數(shù)據(jù)點(diǎn)標(biāo)記。1.3Map函數(shù)的設(shè)計(jì)Map函數(shù)輸入指的是MapReduce框架默認(rèn)的格式，也就是key指的是目前樣本相對輸入數(shù)據(jù)文件起始點(diǎn)偏移量，ualue指的是目前樣本各

9、維坐標(biāo)值構(gòu)成字符串。首先，通過ualue實(shí)現(xiàn)目前樣本各維值的解析;然后，對其和k個(gè)中心點(diǎn)距離進(jìn)行計(jì)算，尋找距離最近聚簇下標(biāo);最后，實(shí)現(xiàn)的輸出，key1指的是距離最近聚簇下標(biāo)，ualue1指的是目前樣本各維坐標(biāo)所構(gòu)成的字符串【5】。為了能夠降低算法在迭代過程中傳輸數(shù)據(jù)量及通信代價(jià)，在操作Map以后，PKMeans算法中實(shí)現(xiàn)Combine操作的設(shè)計(jì)，使每個(gè)Map函數(shù)處理之后輸出數(shù)據(jù)實(shí)現(xiàn)本地合并。由于每個(gè)Map操作之后輸出函數(shù)都是在本地節(jié)點(diǎn)中存儲，所以所有Combine操作都是通過本地進(jìn)行執(zhí)行，通信代價(jià)比較小【6】。1.4Combine函數(shù)的設(shè)計(jì)Combine函數(shù)在對對輸入的過程中，key屬于聚簇下

10、標(biāo)，V指的是為下標(biāo)分類的聚簇所有樣本各維坐標(biāo)值構(gòu)成的字符串鏈表。首先，基于字符串鏈表實(shí)現(xiàn)所有樣本各維坐標(biāo)值的依次解析，并且使全部相應(yīng)坐標(biāo)值都相加，記錄下鏈表樣本的總數(shù)量。輸出中的key1指的是聚簇下標(biāo)，ualue1指的是字符串，其中主要包括各維的坐標(biāo)值及樣本總數(shù)量和、構(gòu)成字符串等信息【7】。1.5Kmeans算法的設(shè)計(jì)Kmeans算法的執(zhí)行過程為：1使數(shù)據(jù)集上傳到HDFS中，實(shí)現(xiàn)數(shù)據(jù)分片，并且使所有分片都在DataNodes中存儲，實(shí)現(xiàn)初始中心點(diǎn)集合U的輸出，將其作為全局變量;2在所有計(jì)算節(jié)點(diǎn)中，對每個(gè)中心點(diǎn)到其他中心點(diǎn)最短距離D集合進(jìn)行計(jì)算8;3以距離三角不等式的原理，使?jié)M足條件需求數(shù)據(jù)點(diǎn)到

11、中心點(diǎn)簇進(jìn)行劃分，并且將數(shù)據(jù)集V中已經(jīng)劃分的數(shù)據(jù)點(diǎn)刪除。假設(shè)數(shù)據(jù)集V中存在不滿足條件的數(shù)據(jù)點(diǎn)，以計(jì)算過程中的數(shù)據(jù)點(diǎn)到不同中心點(diǎn)距離對相應(yīng)簇進(jìn)行分配，并且將數(shù)據(jù)集V中的相應(yīng)數(shù)據(jù)點(diǎn)進(jìn)行刪除;4實(shí)現(xiàn)全新中心點(diǎn)的生成;5返回到步驟2對數(shù)據(jù)中心點(diǎn)重新進(jìn)行計(jì)算，直到數(shù)據(jù)中心點(diǎn)沒有變化，結(jié)束算法;6對子節(jié)點(diǎn)進(jìn)行規(guī)約，實(shí)現(xiàn)聚類結(jié)果的輸出。Kmeans算法的實(shí)現(xiàn)流程如圖1所示。Setup函數(shù)：輸入：初始簇中心點(diǎn)集合表示為U=C，C1，K值;1.對全部中心點(diǎn)C與C1實(shí)現(xiàn)dC，C1的計(jì)算;對全部中心點(diǎn)C，SC=mindC，C1CC1;2.對全部中心點(diǎn)C與C1進(jìn)行計(jì)算，得到彼此最短距離，并且在相應(yīng)數(shù)組中進(jìn)行保存;3.

12、假設(shè)中心點(diǎn)出現(xiàn)變化，那么重復(fù)以上步驟。Map函數(shù)：輸入：實(shí)現(xiàn)簇中心集合U的輸入，并且實(shí)現(xiàn)數(shù)據(jù)集Vv1，v2，vn的輸入;輸出：K中心點(diǎn)的集合U。1.U=U;2.whiletrue3.對V中數(shù)據(jù)點(diǎn)到中心點(diǎn)C距離d1進(jìn)行計(jì)算;4.If2d1S，其中數(shù)據(jù)點(diǎn)的標(biāo)記為第一個(gè)中心點(diǎn)簇，同時(shí)從V中將此數(shù)據(jù)點(diǎn)刪除，并且將不符合條件的數(shù)據(jù)點(diǎn)到此中心點(diǎn)的距離保存到數(shù)組D中。以此類推，直到對V中全部聚類進(jìn)行計(jì)算，并且對簇進(jìn)行標(biāo)記;5.IfV！=Null，以上個(gè)中心點(diǎn)距離D，對C最短距離進(jìn)行計(jì)算，選擇距離中心點(diǎn)最近的簇實(shí)現(xiàn)標(biāo)記，并且從V中將此數(shù)據(jù)點(diǎn)進(jìn)行刪除;6.對已經(jīng)標(biāo)記點(diǎn)簇全新的C進(jìn)行計(jì)算;7.對上一個(gè)中心與最新中

13、心點(diǎn)之間的距離進(jìn)行計(jì)算;8.IfDistance=0;BreakElse;9.返回到步驟3重新計(jì)算;10.Endwhile為了使大數(shù)據(jù)在主節(jié)點(diǎn)和子節(jié)點(diǎn)通信時(shí)間得到縮短，此算法在MAP函數(shù)以后實(shí)現(xiàn)Combine操作的設(shè)計(jì)，其主要功能就是合并本地節(jié)點(diǎn)數(shù)據(jù)文件，降低大數(shù)據(jù)I/O傳輸。圖2為MAP并行化的過程。2.1實(shí)驗(yàn)平臺云計(jì)算的平臺結(jié)構(gòu)如圖3所示，在進(jìn)行實(shí)驗(yàn)的過程中，將一臺機(jī)器作為數(shù)據(jù)JobTracker及NameNode效勞節(jié)點(diǎn)，另外的三臺為TaskTracker及DataNode效勞節(jié)點(diǎn)，每臺計(jì)算機(jī)都能夠?qū)?個(gè)MAP數(shù)據(jù)任務(wù)進(jìn)行處理。2.2單機(jī)處理實(shí)驗(yàn)比照信息數(shù)據(jù)處理的實(shí)驗(yàn)內(nèi)容比較集中，都是在

14、某個(gè)群數(shù)據(jù)節(jié)點(diǎn)中，和串行聚類Kmeans算法處理相同規(guī)模數(shù)據(jù)中消耗的時(shí)間如表1所示。T1的設(shè)置數(shù)值指的是串行算法計(jì)算，T2數(shù)值指的是通過MAP模型實(shí)現(xiàn)的計(jì)算時(shí)間。通過表1可知，在目前小數(shù)據(jù)中，串行算法效率要比MAP模型中的計(jì)算效率高。出現(xiàn)此種結(jié)果的主要原因就是基于MAP計(jì)算模型中，聚類Kmeans算法在每次迭代計(jì)算過程中都要重新進(jìn)行設(shè)置，以此能夠形成全新的工作任務(wù)，但是在完成工作的過程中要消耗一定計(jì)算資源。在計(jì)算機(jī)數(shù)據(jù)信息量規(guī)模到達(dá)一定程度時(shí)，單機(jī)處理算法就會使計(jì)算機(jī)在計(jì)算的過程中出現(xiàn)內(nèi)存缺乏的情況。以此表示，Map模型的可靠性比較強(qiáng)，充分展現(xiàn)了云計(jì)算平臺數(shù)據(jù)處理能力。2.3集群數(shù)據(jù)的計(jì)算實(shí)驗(yàn)

15、在本次實(shí)驗(yàn)內(nèi)容中，如果增加目前計(jì)算機(jī)硬件資源，計(jì)算機(jī)系統(tǒng)中的計(jì)算數(shù)據(jù)規(guī)模相同，表2為實(shí)驗(yàn)數(shù)據(jù)。通過表2可以看出，每條計(jì)算得到的數(shù)據(jù)都是通過四維狀態(tài)下數(shù)值類型組合構(gòu)成，計(jì)算模型的計(jì)算程序也通過既定標(biāo)準(zhǔn)生成5種計(jì)算類型。比照規(guī)模大小完全相同的計(jì)算數(shù)據(jù)，在計(jì)算過程中如果出現(xiàn)增加節(jié)點(diǎn)的情況，系統(tǒng)完成計(jì)算任務(wù)所消耗時(shí)間會減少，以此實(shí)現(xiàn)計(jì)算大規(guī)模數(shù)據(jù)實(shí)效性。由此可知，在大規(guī)模數(shù)據(jù)計(jì)算的過程中，利用節(jié)點(diǎn)的增加能夠提高系統(tǒng)的計(jì)算成效。總之，目前網(wǎng)絡(luò)技術(shù)在不斷的開展，尤其是云計(jì)算技術(shù)和網(wǎng)絡(luò)技術(shù)的廣泛使用，海量數(shù)據(jù)處理的過程也越來越復(fù)雜，以此對于空間及時(shí)間復(fù)雜度的需求也在不斷的提高。那么，就要利用數(shù)據(jù)處理模式，使

16、聚類時(shí)間及對于海量數(shù)據(jù)延展能力降低。本文所設(shè)計(jì)的并行聚類算法通過實(shí)驗(yàn)說明其能夠滿足實(shí)際需求。參考文獻(xiàn)【1】孟海東，任敬佩.基于云計(jì)算平臺的聚類算法J.計(jì)算機(jī)工程與設(shè)計(jì)，2021，1111：29902994.MENGHaidong，RENJingpei.ClusteringalgorithmsbasedoncloudcomputingplatformJ.Computerengineeringanddesign，2021，1111：29902994.【2】霍可棟.基于Hadoop平臺下的CanopyKmeans算法實(shí)現(xiàn)J.科技展望，2021，2533：8788.HUOKedong.Implemen

17、tationofCanopyKmeansalgorithmbasedonHadoopplatformJ.Prospectsforscienceandtechnology，2021，2533：8788.【3】牛怡晗，海沫.Hadoop平臺下Mahout聚類算法的比較研究J.計(jì)算機(jī)科學(xué)，2021，42z1：465469.NIUYihan，HAIMo.ComparisonresearchonMahoutclusteringalgorithmsunderHadoopplatformJ.Computerscience，2021，42S1：465469.【4】崔莉霞.基于Hadoop的并行聚類算法的研究J

18、.計(jì)算機(jī)光盤軟件與應(yīng)，2021，1223：141142.CUILixia.ResearchonparallelclusteringalgorithmbasedonHadoopJ.ComputerCDsoftwareandapplication，2021，1223：141142.【5】高見文，薛行貴，羅杰，等.基于迭代式MapReducede的海量數(shù)據(jù)并行聚類算法研究J.中國科技論文，2021，1114：16261631.GAOJianwen，XUEXinggui，LUOJie，etal.ResearchonparallelclusteringalgorithmformassivedatabasedoniterativeMapReducedeJ.Chinesescienceandtechnologypa