云計(jì)算平臺(tái)上的Canopy-Kmeans并行聚類算法研究

孫秀娟

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

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

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

1 ?算法實(shí)現(xiàn)

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

1.1 ?編程的思想

MapReduce屬于海量數(shù)據(jù)處理的并行編程模式及計(jì)算框架，其在大規(guī)模數(shù)據(jù)集并行計(jì)算中使用。簡(jiǎn)單來(lái)說(shuō)，MapReduce為任務(wù)分解及結(jié)果匯總[3]。首先，就要得到聚類數(shù)據(jù)[N]個(gè)樣本對(duì)象，將其定義為：[N]指的是樣本總數(shù)量，也就是每個(gè)樣本都是通過(guò)[m]個(gè)屬性共同特征所構(gòu)成。初始數(shù)據(jù)以數(shù)據(jù)存儲(chǔ)節(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é)果，并且對(duì)下一輪迭代進(jìn)行判斷[4]。

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

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

假設(shè)在歐幾里得空間中有[X]，[C1]，[C2]三個(gè)任意數(shù)據(jù)點(diǎn)，數(shù)據(jù)點(diǎn)之間的距離能夠滿足三角不等式原理：[d（X，C1）+d（C1，C2）≥d（X，C2）]，[d（C1，C2）-d（X，C1）≤][d（X，C2）]。如果[X]指的是數(shù)據(jù)空間中的任何數(shù)據(jù)點(diǎn)，[C1]和[C2]都是兩個(gè)簇中心點(diǎn)。假如[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的算法思想就是通過(guò)預(yù)處理之后的初始中心點(diǎn)對(duì)不同中心點(diǎn)彼此最短距離進(jìn)行計(jì)算，之后以三角不等式原理對(duì)集合中的數(shù)據(jù)點(diǎn)到第一個(gè)數(shù)據(jù)中心點(diǎn)距離進(jìn)行計(jì)算。假如數(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.3 ?Map函數(shù)的設(shè)計(jì)

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

為了能夠降低算法在迭代過(guò)程中傳輸數(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)中存儲(chǔ)，所以所有Combine操作都是通過(guò)本地進(jìn)行執(zhí)行，通信代價(jià)比較小[6]。

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

Combine函數(shù)在對(duì)對(duì)輸入的過(guò)程中，key屬于聚簇下標(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.5 ?K?means算法的設(shè)計(jì)

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

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

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

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

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

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

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

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

Setup函數(shù)：

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

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

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

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

Map函數(shù)：

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

輸出：[K]中心點(diǎn)的集合[U]。

1. [U=U];

2. while（true）

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

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

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

6. 對(duì)已經(jīng)標(biāo)記點(diǎn)簇全新的[C]進(jìn)行計(jì)算;

7. 對(duì)上一個(gè)中心與最新中心點(diǎn)之間的距離進(jìn)行計(jì)算;

8. ?If（Distance==0）;

Break

Else;

9. 返回到步驟3）重新計(jì)算;

10. End while

為了使大數(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并行化的過(guò)程。

2 ?實(shí) ?驗(yàn)

2.1 ?實(shí)驗(yàn)平臺(tái)

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

2.2 ?單機(jī)處理實(shí)驗(yàn)對(duì)比

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

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

2.3 ?集群數(shù)據(jù)的計(jì)算實(shí)驗(yàn)

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

3 ?結(jié) ?語(yǔ)

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

參考文獻(xiàn)

[1] 孟海東，任敬佩.基于云計(jì)算平臺(tái)的聚類算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，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平臺(tái)下的Canopy?Kmeans算法實(shí)現(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平臺(tái)下Mahout聚類算法的比較研究[J].計(jì)算機(jī)科學(xué)，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].計(jì)算機(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] 高見(jiàn)文，薛行貴，羅杰，等.基于迭代式MapReducede的海量數(shù)據(jù)并行聚類算法研究[J].中國(guó)科技論文，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].遼寧科技學(xué)院學(xué)報(bào)，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.