李慧敏

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

2 Canopy 算法

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

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

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

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

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

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

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

3 基于Hadoop平臺(tái)的并行化Canopy算法設(shè)計(jì)

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

3.1 Map Reduce實(shí)現(xiàn)

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

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

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

Mapper：

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

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

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

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

Reducer：

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

輸出：全局canopy中心列表

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

3.2 性能測(cè)試與分析

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

在實(shí)驗(yàn)中，采用加速比和聚類精確度作為評(píng)價(jià)指標(biāo)。

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

[3] 牛怡晗，海沫. Hadoop平臺(tái)下Mahout聚類算法的比較研究[J]. 計(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ì)算機(jī)工程與應(yīng)用， 2015， 51（16）：47-54.

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

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

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

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