云計算平臺上的Canopy-Kmeans并行聚類算法研究

孫秀娟

摘 ?要： 針對大數(shù)據(jù)的高維特性及海量性，提出云計算平臺中的Canopy?Kmeans并行聚類算法，通過三角不等式原理，能夠使計算冗余降低，使算法執(zhí)行速度得到提高。對Canopy?Kmeans并行聚類算法進行深入的研究，并且在大量不同大小數(shù)據(jù)集中的實驗結(jié)果表明，所設(shè)計的并行聚類算法具有良好的加速比、數(shù)據(jù)伸縮率及擴展率等特點，能夠在海量數(shù)據(jù)挖掘及分析中使用。

關(guān)鍵詞： 云計算平臺; Canopy?Kmeans算法; 并行聚類算法; 大數(shù)據(jù)挖掘; 集群數(shù)據(jù); 數(shù)據(jù)分析

中圖分類號： TN911.1?34 ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）19?0078?04

Abstract： The Canopy?Kmeans parallel clustering algorithm in cloud computing platform is proposed for the high?dimensional feature and massive nature of big dat. The computational redundancy of the algorithm can be reduced and its execution speed can be improved according to the principle of triangular inequality. Canopy?Kmeans parallel clustering algorithm is studied in depth. The results from experiments of a large number of data sets show that the designed parallel clustering algorithm has the characteristics of high acceleration ratio， and data scalability and expansion rate， and can be used in massive data mining and analysis.

Keywords： cloud computing platform; Canopy?Kmeans algorithm; parallel clustering algorithm; big data mining; clustering data; data analysis

0 ?引 ?言

目前，在大數(shù)據(jù)處理過程中大部分都是使用分布式或者并行架構(gòu)，使系統(tǒng)擴展性得到提高，并且通過多線程并行式結(jié)構(gòu)、基于Apache的開源云計算Hadoop平臺進行實現(xiàn)，其中，使用最為廣泛的就是K?means算法。相關(guān)研究人員提出將MPI作為基礎(chǔ)的分布式聚類，其雖然能夠通過集中式存儲，使算法時效性得到提高，但是此算法在進行計算的過程中為單節(jié)點運行，在大數(shù)據(jù)處理聚類分析任務(wù)過程中的算法效率并不快[1]。所以，又提出Canopy?Kmeans改進算法，對于傳統(tǒng)算法的問題，使用最小最大的原則，通過云計算平臺集群計算及存儲能力，使此算法的有效性及時效性得到提高。本文基于K?means算法，使用三角不等式原理，提出Canopy?Kmeans并行聚類算法[2]。通過開源云計算平臺及分布式框架，結(jié)合三角不等式定理，并且在大數(shù)據(jù)預處理過程中實現(xiàn)原始大數(shù)據(jù)預處理，實現(xiàn)算法的改進。

1 ?算法實現(xiàn)

在實現(xiàn)數(shù)據(jù)挖掘的過程中，主要特點就是從海量數(shù)據(jù)中將有價值的信息及時提取出來。在網(wǎng)絡(luò)時代到來之后，現(xiàn)代數(shù)據(jù)種類及數(shù)據(jù)量也都在不斷的提高，傳統(tǒng)數(shù)據(jù)挖掘技術(shù)已經(jīng)無法使數(shù)據(jù)挖掘需求得到滿足。在云計算時代中，海量數(shù)據(jù)在不同計算機中分布，目前聚類算法在時間及空間復雜性方面都無法使此問題得到解決。那么本文的主要研究思路就是在目前聚類算法中使用并行處理技術(shù)，使聚類算法時間及空間的復雜度得到降低，以此使聚類時間得到縮短。

1.1 ?編程的思想

MapReduce屬于海量數(shù)據(jù)處理的并行編程模式及計算框架，其在大規(guī)模數(shù)據(jù)集并行計算中使用。簡單來說，MapReduce為任務(wù)分解及結(jié)果匯總[3]。首先，就要得到聚類數(shù)據(jù)[N]個樣本對象，將其定義為：[N]指的是樣本總數(shù)量，也就是每個樣本都是通過[m]個屬性共同特征所構(gòu)成。初始數(shù)據(jù)以數(shù)據(jù)存儲節(jié)點和Mapper個數(shù)量劃分成為相應(yīng)數(shù)據(jù)集數(shù)量，能夠為Mapper節(jié)點分配數(shù)據(jù)集實現(xiàn)獨立執(zhí)行，之后利用相應(yīng)的Reducer處理結(jié)果，并且對下一輪迭代進行判斷[4]。

1.2 ?基于距離三角不等式的聚類算法

在云計算平臺中的MapReduce框架中，通過傳統(tǒng)K?means算法和距離三角不等式定理相互結(jié)合，從而提出基于距離三角不等式聚類算法。此算法使用三角不等式定理，任何一個三角形的兩邊之和都比第三邊要大，兩邊之差要比第三邊小。使其擴充到歐幾里得空間，因為歐氏距離能夠使三角不等式原理得到滿足，從而能夠降低聚類算法計算過程中的復雜度，使大數(shù)據(jù)聚類分析效率得到提高。

假設(shè)在歐幾里得空間中有[X]，[C1]，[C2]三個任意數(shù)據(jù)點，數(shù)據(jù)點之間的距離能夠滿足三角不等式原理：[d（X，C1）+d（C1，C2）≥d（X，C2）]，[d（C1，C2）-d（X，C1）≤][d（X，C2）]。如果[X]指的是數(shù)據(jù)空間中的任何數(shù)據(jù)點，[C1]和[C2]都是兩個簇中心點。假如[2d（X，C1）≤d（C1，C2）]，并且在兩邊減去[d（X，C1）]，那么就有[2d（X，C1）-d（X，C1）≤d（C1，C2）-d（X，C1）]。所以，假如[2d（X，C1）≤][d（C1，C2）]，那么則有[d（X，C1）

由上述原理可知，K?means的算法思想就是通過預處理之后的初始中心點對不同中心點彼此最短距離進行計算，之后以三角不等式原理對集合中的數(shù)據(jù)點到第一個數(shù)據(jù)中心點距離進行計算。假如數(shù)據(jù)點到中心點的距離的兩倍小于或者等于第一個數(shù)據(jù)中心點到其他數(shù)據(jù)中心點的最短距離，那么此數(shù)據(jù)點就為第一個數(shù)據(jù)中心點，將其標記為第一類。以此類推，實現(xiàn)全部數(shù)據(jù)點標記。

1.3 ?Map函數(shù)的設(shè)計

Map函數(shù)輸入指的是MapReduce框架默認的格式，也就是key指的是目前樣本相對輸入數(shù)據(jù)文件起始點偏移量，ualue指的是目前樣本各維坐標值構(gòu)成字符串。首先，通過ualue實現(xiàn)目前樣本各維值的解析;然后，對其和[k]個中心點距離進行計算，尋找距離最近聚簇下標;最后，實現(xiàn)的輸出，key1指的是距離最近聚簇下標，ualue1指的是目前樣本各維坐標所構(gòu)成的字符串[5]。

為了能夠降低算法在迭代過程中傳輸數(shù)據(jù)量及通信代價，在操作Map以后，PKMeans算法中實現(xiàn)Combine操作的設(shè)計，使每個Map函數(shù)處理之后輸出數(shù)據(jù)實現(xiàn)本地合并。由于每個Map操作之后輸出函數(shù)都是在本地節(jié)點中存儲，所以所有Combine操作都是通過本地進行執(zhí)行，通信代價比較小[6]。

1.4 ?Combine函數(shù)的設(shè)計

Combine函數(shù)在對對輸入的過程中，key屬于聚簇下標，[V]指的是為下標分類的聚簇所有樣本各維坐標值構(gòu)成的字符串鏈表。首先，基于字符串鏈表實現(xiàn)所有樣本各維坐標值的依次解析，并且使全部相應(yīng)坐標值都相加，記錄下鏈表樣本的總數(shù)量。輸出中的key1指的是聚簇下標，ualue1指的是字符串，其中主要包括各維的坐標值及樣本總數(shù)量和、構(gòu)成字符串等信息[7]。

1.5 ?K?means算法的設(shè)計

K?means算法的執(zhí)行過程為：

1） 使數(shù)據(jù)集上傳到HDFS中，實現(xiàn)數(shù)據(jù)分片，并且使所有分片都在DataNodes中存儲，實現(xiàn)初始中心點集合[U]的輸出，將其作為全局變量;

2） 在所有計算節(jié)點中，對每個中心點到其他中心點最短距離[D]集合進行計算[8];

3） 以距離三角不等式的原理，使?jié)M足條件需求數(shù)據(jù)點到中心點簇進行劃分，并且將數(shù)據(jù)集[V]中已經(jīng)劃分的數(shù)據(jù)點刪除。假如數(shù)據(jù)集[V]中存在不滿足條件的數(shù)據(jù)點，以計算過程中的數(shù)據(jù)點到不同中心點距離對相應(yīng)簇進行分配，并且將數(shù)據(jù)集[V]中的相應(yīng)數(shù)據(jù)點進行刪除;

4） 實現(xiàn)全新中心點的生成;

5） 返回到步驟2）對數(shù)據(jù)中心點重新進行計算，直到數(shù)據(jù)中心點沒有變化，結(jié)束算法;

6） 對子節(jié)點進行規(guī)約，實現(xiàn)聚類結(jié)果的輸出。

K?means算法的實現(xiàn)流程如圖1所示。

Setup函數(shù)：

輸入：初始簇中心點集合表示為[U={C，C1}]，[K]值;

1. 對全部中心點[C]與[C1]實現(xiàn)[d（C，C1）]的計算;對全部中心點[C]，[S（C）=]min[（d（C，C1））（C≠C1）];

2. 對全部中心點[C]與[C1]進行計算，得到彼此最短距離，并且在相應(yīng)數(shù)組中進行保存;

3. 假如中心點出現(xiàn)變化，那么重復以上步驟。

Map函數(shù)：

輸入：實現(xiàn)簇中心集合[U]的輸入，并且實現(xiàn)數(shù)據(jù)集[V（v1，v2，…，vn）]的輸入;

輸出：[K]中心點的集合[U]。

1. [U=U];

2. while（true）

3. 對[V]中數(shù)據(jù)點到中心點[C]距離[d1]進行計算;

4. If（[2d1≤S]），其中數(shù)據(jù)點的標記為第一個中心點簇，同時從[V]中將此數(shù)據(jù)點刪除，并且將不符合條件的數(shù)據(jù)點到此中心點的距離保存到數(shù)組[D]中。以此類推，直到對[V]中全部聚類進行計算，并且對簇進行標記;

5. ?If（[V！=]Null），以上個中心點距離[D]，對[C]最短距離進行計算，選擇距離中心點最近的簇實現(xiàn)標記，并且從[V]中將此數(shù)據(jù)點進行刪除;

6. 對已經(jīng)標記點簇全新的[C]進行計算;

7. 對上一個中心與最新中心點之間的距離進行計算;

8. ?If（Distance==0）;

Break

Else;

9. 返回到步驟3）重新計算;

10. End while

為了使大數(shù)據(jù)在主節(jié)點和子節(jié)點通信時間得到縮短，此算法在MAP函數(shù)以后實現(xiàn)Combine操作的設(shè)計，其主要功能就是合并本地節(jié)點數(shù)據(jù)文件，降低大數(shù)據(jù)I/O傳輸。圖2為MAP并行化的過程。

2 ?實 ?驗

2.1 ?實驗平臺

云計算的平臺結(jié)構(gòu)如圖3所示，在進行實驗的過程中，將一臺機器作為數(shù)據(jù)JobTracker及NameNode服務(wù)節(jié)點，另外的三臺為TaskTracker及DataNode服務(wù)節(jié)點，每臺計算機都能夠?qū)?個MAP數(shù)據(jù)任務(wù)進行處理。

2.2 ?單機處理實驗對比

信息數(shù)據(jù)處理的實驗內(nèi)容比較集中，都是在某個群數(shù)據(jù)節(jié)點中，和串行聚類K?means算法處理相同規(guī)模數(shù)據(jù)中消耗的時間如表1所示。[T1]的設(shè)置數(shù)值指的是串行算法計算，[T2]數(shù)值指的是通過MAP模型實現(xiàn)的計算時間。

通過表1可知，在目前小數(shù)據(jù)中，串行算法效率要比MAP模型中的計算效率高。出現(xiàn)此種結(jié)果的主要原因就是基于MAP計算模型中，聚類K?means算法在每次迭代計算過程中都要重新進行設(shè)置，以此能夠形成全新的工作任務(wù)，但是在完成工作的過程中要消耗一定計算資源。在計算機數(shù)據(jù)信息量規(guī)模達到一定程度時，單機處理算法就會使計算機在計算的過程中出現(xiàn)內(nèi)存不足的情況。以此表示，Map模型的可靠性比較強，充分展現(xiàn)了云計算平臺數(shù)據(jù)處理能力。

2.3 ?集群數(shù)據(jù)的計算實驗

在本次實驗內(nèi)容中，如果增加目前計算機硬件資源，計算機系統(tǒng)中的計算數(shù)據(jù)規(guī)模相同，表2為實驗數(shù)據(jù)。通過表2可以看出，每條計算得到的數(shù)據(jù)都是通過四維狀態(tài)下數(shù)值類型組合構(gòu)成，計算模型的計算程序也通過既定標準生成5種計算類型。對比規(guī)模大小完全相同的計算數(shù)據(jù)，在計算過程中如果出現(xiàn)增加節(jié)點的情況，系統(tǒng)完成計算任務(wù)所消耗時間會減少，以此實現(xiàn)計算大規(guī)模數(shù)據(jù)實效性。由此可知，在大規(guī)模數(shù)據(jù)計算的過程中，利用節(jié)點的增加能夠提高系統(tǒng)的計算成效。

3 ?結(jié) ?語

總之，目前網(wǎng)絡(luò)技術(shù)在不斷的發(fā)展，尤其是云計算技術(shù)和網(wǎng)絡(luò)技術(shù)的廣泛使用，海量數(shù)據(jù)處理的過程也越來越復雜，以此對于空間及時間復雜度的需求也在不斷的提高。那么，就要利用數(shù)據(jù)處理模式，使聚類時間及對于海量數(shù)據(jù)延展能力降低。本文所設(shè)計的并行聚類算法通過實驗表明其能夠滿足實際需求。

參考文獻

[1] 孟海東，任敬佩.基于云計算平臺的聚類算法[J].計算機工程與設(shè)計，2015，11（11）：2990?2994.

MENG Haidong， REN Jingpei. Clustering algorithms based on cloud computing platform [J]. Computer engineering and design， 2015， 11（11）： 2990?2994.

[2] 霍可棟.基于Hadoop平臺下的Canopy?Kmeans算法實現(xiàn)[J].科技展望，2015，25（33）：87?88.

HUO Kedong. Implementation of Canopy?Kmeans algorithm based on Hadoop platform [J]. Prospects for science and technology， 2015， 25（33）： 87?88.

[3] 牛怡晗，海沫.Hadoop平臺下Mahout聚類算法的比較研究[J].計算機科學，2015，42（z1）：465?469.

NIU Yihan， HAI Mo. Comparison research on Mahout cluste?ring algorithms under Hadoop platform [J]. Computer science， 2015， 42（S1）： ?465?469.

[4] 崔莉霞.基于Hadoop的并行聚類算法的研究[J].計算機光盤軟件與應(yīng)，2014，12（23）：141?142.

CUI Lixia. Research on parallel clustering algorithm based on Hadoop [J]. Computer CD software and application， 2014， 12 （23）： 141?142.

[5] 高見文，薛行貴，羅杰，等.基于迭代式MapReducede的海量數(shù)據(jù)并行聚類算法研究[J].中國科技論文，2016，11（14）：1626?1631.

GAO Jianwen， XUE Xinggui， LUO Jie， et al. Research on parallel clustering algorithm for massive data based on iterative MapReducede [J]. Chinese science and technology paper， 2016， 11（14）： 1626?1631.

[6] 李琪，張欣，張平康，等.基于密度峰值優(yōu)化的Canopy?Kmeans并行算法[J].通信技術(shù)，2018，51（2）：85?86.

LI Qi， ZHANG Xin， ZHANG Pingkang， et al. Canopy?Kmeans parallel algorithm based on density peak optimization [J]. Communication technology， 2018， 51（2）： 85?86.

[7] 肖雪平，倪建成，曹博.基于Map?Reduce模型的BCkmeans并行聚類算法[J].電子技術(shù)，2016，11（5）：78?79.

XIAO Xueping， NI Jiancheng， CAO Bo. BCkmeans parallel clustering algorithm based on Map?Reduce model [J]. Electronic technology， 2016， 11（5）： 78?79.

[8] 張友海，李鋒剛.基于MapReduce的Canopy?Kmeans算法的并行化[J].遼寧科技學院學報，2017，19（1）：4?5.

ZHANG Youhai， LI Fenggang. Parallelization of Canopy?Kmeans algorithm based on MapReduce [J]. Journal of Liaoning University of Science and Technology， 2017， 19（1）： 4?5.