基于Hadoop平臺的并行化Canopy聚類算法

李慧敏

摘要：在大數(shù)據(jù)時代，傳統(tǒng)聚類算法已無法滿足各領(lǐng)域的應(yīng)用需求，如何改造使之適應(yīng)大數(shù)據(jù)，是當(dāng)前的研究熱點(diǎn)。因此，提出基于Hadoop平臺的并行化Canopy聚類算法，采用Map Reduce來實現(xiàn)并進(jìn)行仿真實驗驗證，以加速比和聚類精確度作為評價指標(biāo)，證明該算法在保證精確度的同時大幅提高運(yùn)算速度。

關(guān)鍵詞：Hadoop；Canopy；并行化；聚類算法；大數(shù)據(jù)

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）29-0018-02

Abstract： In the era of big data， the traditional clustering algorithms have been unable to meet the application needs of various fields. So how to transform it to adapt to big data， is the current research hotspot. Therefore， a parallel Canopy clustering algorithm based on Hadoop platform is proposed， which is implemented by Map Reduce and validated by simulation experiments. The acceleration ratio and clustering accuracy are taken as evaluation indicators to prove that the algorithm can greatly improve the operation speed while ensuring the accuracy.

Key words： Hadoop； Canopy； Parallel； clustering algorithm； big data

1 引言

在生活中，我們可以使用聚類解決很多問題，傳統(tǒng)的聚類算法已經(jīng)應(yīng)用到很多生活領(lǐng)域。但是隨著時代發(fā)展，海量數(shù)據(jù)的出現(xiàn)，傳統(tǒng)聚類算法就已無法滿足應(yīng)用需求了。Canopy算法[1]就是聚類算法發(fā)展到一定階段，Andrew McCallum等提出的一種改進(jìn)算法。但隨著大數(shù)據(jù)時代的到來，原有算法已無法滿足應(yīng)用需求，采用Hadoop平臺的Map Reduce對算法進(jìn)行并行化優(yōu)化是應(yīng)對急劇增長的大數(shù)據(jù)的有效方法。

2 Canopy 算法

Canopy算法是一種簡單快速的聚類技術(shù)，采用簡單的間距度量方式計算數(shù)據(jù)點(diǎn)之間的距離，然后跟預(yù)定義的距離閾值T1、T2進(jìn)行比較，通過多次迭代，得到聚類結(jié)果。它最大的特點(diǎn)是不用預(yù)先指定聚類個數(shù)，因此具有很大的實際應(yīng)用價值，可以用在預(yù)處理階段，對數(shù)據(jù)進(jìn)行粗聚類。

Canopy算法基本流程[2]如下：

1）設(shè)置閾值T1、T2，T1>T2（關(guān)于閾值的選取可通過交叉驗證得到）；

2）從數(shù)據(jù)集中任取一點(diǎn)P，將P作為第一個Canopy，并將它從數(shù)據(jù)集中刪除；

3）繼續(xù)從集合中取點(diǎn)，計算其到已經(jīng)產(chǎn)生的所有Canopy的距離，如果到某個Canopy的距離小于T2，則將其加入該Canopy，如果它到所有Canopy中心的距離都大于T1，則將其作為一個新Canopy，如果該點(diǎn)到某個Canopy距離小于T1，并在其與所有Canopy距離計算完成后仍未加入任何Canopy，則將它作為一個新的Canopy；

4）重復(fù)第3）步，直至數(shù)據(jù)集為空。

根據(jù)上面描述，最后每個canopy中至少含有一個數(shù)據(jù)點(diǎn)，一般來說會含有多個數(shù)據(jù)點(diǎn)，另外一個數(shù)據(jù)點(diǎn)可能出現(xiàn)在多個canopy中。

3 基于Hadoop平臺的并行化Canopy算法設(shè)計

Canopy算法的提出，就是為解決數(shù)據(jù)規(guī)模變大的問題。但當(dāng)海量數(shù)據(jù)涌現(xiàn)，Canopy算法也力不從心。所以就需要對其進(jìn)行并行化優(yōu)化以適應(yīng)大數(shù)據(jù)。Hadoop的Map Reduce是一個軟件框架，應(yīng)用該框架可以改寫原算法，使之能夠運(yùn)行在集群上，還提供了相應(yīng)的機(jī)制保障并行處理海量數(shù)據(jù)的可靠性。所以采用Map Reduce來實現(xiàn)Canopy算法的并行化。

3.1 Map Reduce實現(xiàn)

本文提出了基于Map Reduce的并行化Canopy算法的實現(xiàn)框架。并行化Canopy算法[3]首先將輸入數(shù)據(jù)集分成數(shù)據(jù)塊，分發(fā)到Datanode上，在各個Datanode上用map操作并發(fā)地進(jìn)行Canopy聚類，接著在Namenode上采用reduce操作歸并各Datanode上的聚類結(jié)果，得到全局Canopy中心，最后再用map操作得到完整的聚類結(jié)果。實現(xiàn)框架如圖1所示。

其中，mapper是對數(shù)據(jù)集進(jìn)行Canopy聚類得到多個群組，而reducer則是對生成的群組進(jìn)行篩選得到全局Canopy中心，篩選依據(jù)是以設(shè)定好的數(shù)據(jù)點(diǎn)數(shù)量為閾值，當(dāng)某個群組中數(shù)據(jù)點(diǎn)小于閾值時，則判定該群組中的數(shù)據(jù)點(diǎn)多為孤立點(diǎn)，則刪除該群組。

具體實現(xiàn)過程如下所示：

Mapper：

輸入：分解好的數(shù)據(jù)塊X={x1， x2， … ， xn}，其中xi為一個多維向量；距離閾值T1和T2，T1>T2。輸出：canopy中心列表。

步驟1 從數(shù)據(jù)集中任取一點(diǎn)P，將P作為第一個Canopy，并將它從數(shù)據(jù)集中刪除；

步驟2 繼續(xù)從集合中取點(diǎn)，計算其到已經(jīng)產(chǎn)生的所有Canopy的距離，如果到某個Canopy的距離小于T2，則將其加入該Canopy，如果它到所有Canopy中心的距離都大于T1，則將其作為一個新Canopy，如果該點(diǎn)到某個Canopy距離小于T1，并在其與所有Canopy距離計算完成后仍未加入任何Canopy，則將它作為一個新的Canopy；

步驟3 重復(fù)步驟2，直至數(shù)據(jù)集為空。

Reducer：

輸入：各Datanode上生成的canopy中心列表

輸出：全局canopy中心列表

步驟 對各Datanode上生成的canopy中心值進(jìn)行歸并，以設(shè)定好的數(shù)據(jù)點(diǎn)數(shù)量為閾值，當(dāng)某個canopy中數(shù)據(jù)點(diǎn)小于閾值時，則判定該canopy中的數(shù)據(jù)點(diǎn)多為孤立點(diǎn)，則刪除該canopy。

3.2 性能測試與分析

仿真環(huán)境：在Linux 環(huán)境下搭建Hadoop集群，共5臺計算機(jī)，其中一臺作為NameNode，其他4臺作為DataNode。實驗所使用的數(shù)據(jù)是基于UCI的Iris數(shù)據(jù)集隨機(jī)生成 106、107、4*107條記錄的數(shù)據(jù)集，它們所占空間大小分別為30MB、300MB、1.2GB，將它們標(biāo)識為數(shù)據(jù)集Iris-1、Iris-2和Iris-3。由于數(shù)據(jù)集不相同，因此Canopy算法得到的初始聚類中心不盡相同，各不相同的初始化質(zhì)心將會對作業(yè)的循環(huán)次數(shù)造成一定程度的干擾，進(jìn)而對完成作業(yè)所消耗的總時間形成比較大的影響。

在實驗中，采用加速比和聚類精確度作為評價指標(biāo)。

從表1可以看出Canopy聚類算法的加速比近似線性。這表明在數(shù)據(jù)量大時，隨著節(jié)點(diǎn)數(shù)的增加，優(yōu)化后的算法運(yùn)行速度得到了大幅提高。但在數(shù)據(jù)大規(guī)模增長后，節(jié)點(diǎn)增加，加速比增長變慢，這是因為隨著節(jié)點(diǎn)增加，主從節(jié)點(diǎn)之間的通信代價也隨著增加，對算法性能產(chǎn)生了影響。

從表2可以看出Canopy算法的聚類精確度并不高，所以Canopy經(jīng)常應(yīng)用在預(yù)處理階段，對數(shù)據(jù)進(jìn)行粗聚類。而并行化后聚類精確度并沒有受到很大影響，所以采用并行化在保證精確度的同時大副提高了運(yùn)算速度。

4 結(jié)論

并行化Canopy算法的聚類精確度并沒有受到很大影響，運(yùn)算速度卻得到了大幅提升，證明了并行化算法的可行性。但Canopy算法是一種快速近似的聚類技術(shù)，從實驗結(jié)果可以發(fā)現(xiàn)它的聚類精確度并不高，在實際應(yīng)用中經(jīng)常用在預(yù)處理階段對數(shù)據(jù)進(jìn)行粗聚類。針對Canopy算法的低精確度，可以增加后續(xù)處理，如應(yīng)用其他精確聚類算法（K-means、K-Medoids等）在粗聚類的基礎(chǔ)上再次進(jìn)行精準(zhǔn)聚類。因為通過粗聚類大量減少了數(shù)據(jù)量，后續(xù)處理保證了精確度，所以聚類算法的一個優(yōu)化方向[4]就是針對各個應(yīng)用領(lǐng)域中數(shù)據(jù)的特點(diǎn)，結(jié)合多種傳統(tǒng)聚類算法，并進(jìn)行并行化處理，來獲得性能好、高效率的大數(shù)據(jù)聚類算法。

參考文獻(xiàn)：

[1] 萬旭.基于Hadoop平臺的聚類算法研究[D].西安：西安電子科技大學(xué)，2016.

[2] 陳笑.基于Mahout的并行化K-means聚類算法優(yōu)化研究[D].武漢：華中科技大學(xué)，2016.

[3] 牛怡晗，海沫. Hadoop平臺下Mahout聚類算法的比較研究[J]. 計算機(jī)科學(xué)，2015，42（6）：465-469.

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

[5] 王永貴，戴偉，武超.一種基于Hadoop 的高效K -Medoids 并行算法[J]. 計算機(jī)工程與應(yīng)用， 2015， 51（16）：47-54.

[6] 劉建紅.基于Hadoop 平臺的聚類算法并行化研究[D]. 吉林：吉林大學(xué)， 2017.

[7] 施亮，錢雪忠. 基于Hadoop的并行FP-Growth算法的研究與實現(xiàn)[J]. 微電子學(xué)與計算機(jī)信，2015， 32（4）：150-154.

[8] 呂婉琪，鐘誠，唐印滸，等. Hadoop 分布式架構(gòu)下大數(shù)據(jù)集的并行挖掘[J]. 計算機(jī)技術(shù)與發(fā)展， 2014， 24（1）：22-25，30.

【通聯(lián)編輯：王力】