孟海東，任敬佩

（內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭014010）

0 引 言

目前，針對(duì)于大數(shù)據(jù)［1－3］的處理，多采用并行或分布式架構(gòu)來(lái)提高系統(tǒng)的擴(kuò)展性，并利用多線程的并行式結(jié)構(gòu)，或者是基于Apache推出的開源云計(jì)算Hadoop［4，5］平臺(tái)實(shí)現(xiàn)，其中K－means算法的應(yīng)用最為廣泛。文獻(xiàn) ［6］提出了基于MPI的分布式聚類，它雖然從某種程度上利用集中式存儲(chǔ)提高了算法的時(shí)效性，但是，由于該算法在計(jì)算過(guò)程當(dāng)中是單節(jié)點(diǎn)運(yùn)行的，所以在處理大數(shù)據(jù)進(jìn)行聚類分析任務(wù)時(shí)，該算法的效率還不夠快；文獻(xiàn) ［7，8］提出了在Hadoop平臺(tái)下，利用MapReduce 模型框架，實(shí)現(xiàn)了Kmeans［9－11］分布式聚類，提高了聚類算法的加速比；文獻(xiàn)［12］利用Spark （Pregel和HaLoop［13］）模型框架，實(shí)現(xiàn)了迭代式的分布式聚類，提高算法的可擴(kuò)展性；文獻(xiàn) ［14］中為了進(jìn)一步提高聚類算法的效率，解決初始中心點(diǎn)的隨機(jī)性和盲目性，在該算法在基于MapReduce分布式框架的聚類中，加入了Canopy算法對(duì)原數(shù)據(jù)的預(yù)處理，初步的解決了該算法選取初始中心點(diǎn)的隨機(jī)性與初始確定聚類個(gè)數(shù)的問(wèn)題；文獻(xiàn) ［15］中提出基于MapReduce 的Canopy－Kmeans改進(jìn)算法，針對(duì)于Canopy算法的缺點(diǎn)采用了 “最小最大原則”，利用云計(jì)算平臺(tái)的集群計(jì)算和存儲(chǔ)能力，更進(jìn)一步提高該算法的時(shí)效性和有效性。

鑒于以上改進(jìn)后的K－means聚類算法的優(yōu)點(diǎn)，利用文獻(xiàn) ［16］在K－means算法引進(jìn)了三角不等式原理的基礎(chǔ)上，提出一種改進(jìn)的BRTI－K－means（MapReduce based triangle inequality Canopy K－means，BRTI－K－means）算法。主要通過(guò)基于開源云計(jì)算平臺(tái)，利用MapReduce分布式框架，融合了距離三角不等式定理，同時(shí)在大數(shù)據(jù)的預(yù)處理過(guò)程當(dāng)中，使用Canopy算法對(duì)原始的大數(shù)據(jù)進(jìn)行了預(yù)處理，進(jìn)一步實(shí)現(xiàn)了K－means算法在聚類分析過(guò)程中的改進(jìn)；為了進(jìn)一步驗(yàn)證BRTI－K－means算法的優(yōu)越性，將該算法與Kmeans和Canopy－Kmeans算法進(jìn)行了算法比較。

1 BRTI－K－means算法

1.1 基于距離三角不等式聚類算法

基于云計(jì)算平臺(tái)下的MapReduce框架下，利用傳統(tǒng)的K－means算法與距離三角不等式定理相結(jié)合，提出了基于距離三角不等式聚類算法。該算法利用三角不等式定理：任一個(gè)三角形兩邊和大于第三邊，兩邊之差小于第三邊；將其擴(kuò)展到歐幾里得空間，由于歐式距離滿足三角不等式原理，進(jìn)一步減少了聚類算法的計(jì)算復(fù)雜度，提高了大數(shù)據(jù)的聚類分析效率。

假設(shè)在歐幾里得空間內(nèi)有任意3個(gè)數(shù)據(jù)點(diǎn)X、C1、C2，數(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ù)空間中任意一個(gè)數(shù)據(jù)點(diǎn)，C1和C2為兩個(gè)簇中心點(diǎn)。如果2＊d（X，C1）＜＝d（C1，C2），同時(shí)在兩邊減去d（X，C1），則有：2＊d（X，C1）－d（X，C1）＜＝d（C1，C2）－d（X，C1），即有d（X，C1）＜＝d（C1，C2）－d（X，C1）；由于d（C1，C2）－d（X，C1）＜＝d（X，C2），因此，d（X，C1）＜d（X，C2）；所以，如果2＊d（X，C1）＜＝d（C1，C2），則d（X，C1）＜d（X，C2），即數(shù)據(jù)點(diǎn)X 屬于簇中心點(diǎn)C1。

根據(jù)上述原理，BRTI－K－means算法的設(shè)計(jì)思想為：利用預(yù)處理過(guò)后的初始中心點(diǎn)，計(jì)算各個(gè)中心點(diǎn)彼此最短距離；然后，根據(jù)三角不等式原理，計(jì)算集合中的每個(gè)數(shù)據(jù)點(diǎn)到第一個(gè)數(shù)據(jù)中心點(diǎn)之間的距離。如果數(shù)據(jù)點(diǎn)到中心點(diǎn)之間的距離的2倍小于或等于第一個(gè)數(shù)據(jù)中心點(diǎn)到其它數(shù)據(jù)中心點(diǎn)的最短距離，那么，這個(gè)數(shù)據(jù)點(diǎn)就屬于第一個(gè)數(shù)據(jù)中心點(diǎn)，標(biāo)記為第一類，同時(shí)從數(shù)據(jù)集中刪除數(shù)據(jù)這個(gè)數(shù)據(jù)點(diǎn)；根據(jù)上述的步驟，依次類推，對(duì)集合中的數(shù)據(jù)點(diǎn)進(jìn)行標(biāo)記，同時(shí)從數(shù)據(jù)集中刪除標(biāo)記過(guò)的數(shù)據(jù)點(diǎn)，直到?jīng)]有符合條件的數(shù)據(jù)點(diǎn)為止；如果集合中還存在不符合條件的數(shù)據(jù)點(diǎn)，則根據(jù)上述過(guò)程中已經(jīng)求得的不符合條件的數(shù)據(jù)點(diǎn)到每個(gè)中心點(diǎn)距離，把集合V 中沒(méi)有被標(biāo)記的數(shù)據(jù)點(diǎn)，根據(jù)歐氏距離分配到相應(yīng)的簇。當(dāng)集合中所有數(shù)據(jù)點(diǎn)都被標(biāo)識(shí)后，更新新的中心點(diǎn)與初始中心點(diǎn)相比較，如果前后變化在一定閾值內(nèi)或者不變，即達(dá)到一種穩(wěn)定分類狀態(tài)，則聚類完成。

基于MapReduce框架，BRTI－K－means可以分解為以下幾步，具體流程如圖1所示，其中每個(gè)方框內(nèi)的過(guò)程都是一個(gè)獨(dú)立的過(guò)程。

1.2 BRTI－K－means算法設(shè)計(jì)

BRTI－K－means算法執(zhí)行過(guò)程如下：

（1）將數(shù)據(jù)集上傳到HDFS，數(shù)據(jù)分片，并將每一分片存儲(chǔ)到若干臺(tái)DataNodes，輸入初始中心點(diǎn)的集合U （作為全局變量）；

（2）在每個(gè)計(jì)算節(jié)點(diǎn)，計(jì)算每個(gè)中心點(diǎn)到其它中心點(diǎn)的最短距離D 集合；

（3）根據(jù)距離三角不等式原理，將滿足條件的數(shù)據(jù)點(diǎn)劃分到各個(gè)中心點(diǎn)所在的簇，同時(shí)把已劃分的數(shù)據(jù)點(diǎn)從數(shù)據(jù)集V 中刪除；如果在數(shù)據(jù)集V 中還有不符合條件的數(shù)據(jù)點(diǎn)，則根據(jù)已經(jīng)計(jì)算得到的數(shù)據(jù)點(diǎn)到各個(gè)中心點(diǎn)的距離分配給相應(yīng)的簇，并把相應(yīng)的數(shù)據(jù)點(diǎn)從V 中刪除；

圖1 BRTI－K－means算法實(shí)現(xiàn)流程

（4）生成新的中心點(diǎn)；

（5）返回到 （2）重新計(jì)算數(shù)據(jù)中心點(diǎn)，直到數(shù)據(jù)中心點(diǎn)不在發(fā)生變化為止，算法結(jié)束；

（6）實(shí)現(xiàn)子節(jié)點(diǎn)的歸約，輸出聚類結(jié)果。

具體實(shí)現(xiàn)BRTI－K－means算法的偽代碼如下：

Setup函數(shù)

輸入：初始簇中心點(diǎn)的集合U＝ ｛C，C’｝，K 值；

（1）對(duì)所有的中心點(diǎn)C 和C’，計(jì)算d（C，C’）；對(duì)所有的中心點(diǎn)C，S（C）＝min（d（C，C’））（C≠C’）；

（2）計(jì)算所有中心點(diǎn)C 和C’，求出彼此最短距離并保存到相應(yīng)的數(shù)組中；

（3）如果中心點(diǎn)發(fā)生改變，則重復(fù)步驟 （1）與 （2）。

Map函數(shù)

輸入：簇中心點(diǎn)的集合U，數(shù)據(jù)集V（v1，v2，…，vn）；

輸出：K 中心點(diǎn)集合U’；

（1）U’＝U；

（2）While（true）

（3）計(jì)算出V 中數(shù)據(jù)點(diǎn)到中心點(diǎn)C 的距離d1；

（4）If（2＊d1＜＝S）標(biāo)記數(shù)據(jù)點(diǎn)屬于第一個(gè)中心點(diǎn)的簇；同時(shí)從V 中刪除這個(gè)數(shù)據(jù)點(diǎn)，并保存不符合條件的數(shù)據(jù)點(diǎn)到該中心點(diǎn)的距離到數(shù)組D；依次類推，直到計(jì)算出V 中所有點(diǎn)的聚類，并標(biāo)記出其所屬簇；

（5）End If

（6）If（V?。絅ull）

（7）根據(jù)上述中心點(diǎn)的距離D，計(jì)算到C 的最短距離，選取到中心點(diǎn)最近的簇，并進(jìn)行標(biāo)記，同時(shí)從V 中刪除該數(shù)據(jù)點(diǎn)；

（8）End If

（9）計(jì)算已被標(biāo)記點(diǎn)所屬簇的新的C；

（10）對(duì)比上一個(gè)中心與新中心點(diǎn)之間的距離 （Distance＝＝0）；

（11）If（Distance＝＝0）

（12）Break

（13）Else

（14）返回 （3）重新計(jì)算；

（15）End while

Combine函數(shù)

為了減少大數(shù)據(jù)在主節(jié)點(diǎn)與子節(jié)點(diǎn)之間的通訊時(shí)間，該算法在Map函數(shù)之后設(shè)計(jì)了一個(gè)Combine操作；它的主要功能為：對(duì)于本地節(jié)點(diǎn)的數(shù)據(jù)文件進(jìn)行合并，減少大數(shù)據(jù)的I／O 傳輸。

輸入：V 中數(shù)據(jù)點(diǎn)所屬簇下標(biāo) （Key），Key對(duì)應(yīng)鍵值對(duì)列表；

輸出：V 中數(shù)據(jù)點(diǎn)所屬簇下標(biāo) （Key），各個(gè)簇內(nèi)被標(biāo)記數(shù)據(jù)點(diǎn)的各維累加值，以及Key對(duì)應(yīng)鍵值對(duì)列表；

（1）定義一個(gè)列表，用于存儲(chǔ)各個(gè)簇內(nèi)被標(biāo)記數(shù)據(jù)點(diǎn)的各維累加值；

（2）初始化一個(gè)變量Num＝0，記錄所屬簇內(nèi)點(diǎn)的個(gè)數(shù)；

（3）While（V.hasNext（））

（4）在V.next（）中，解析出各維坐標(biāo)值；

（5）計(jì)算上步過(guò)程中各維累加值和，并存儲(chǔ)到定義的列表當(dāng)中；

（6）Num＋＋；

（7）End While

Reduce函數(shù)設(shè)計(jì)

輸入：V 中數(shù)據(jù)點(diǎn)所屬簇下標(biāo) （Key），Key對(duì)應(yīng)的鍵值對(duì)列表；

輸出：V 中數(shù)據(jù)點(diǎn)所屬簇下標(biāo) （Key），以及新的中心點(diǎn)；

（1）定義一個(gè)列表，保存所屬簇的各維累加值；

（2）初始化一個(gè)變量NUM＝0，記錄所屬簇內(nèi)標(biāo)記點(diǎn)的個(gè)數(shù)；

（3）While（V.hasNext（））

（4）在V.next（）中，解析出坐標(biāo)值，計(jì)算出樣本個(gè)數(shù)Num；

（5）計(jì)算上步解析出v 的各維坐標(biāo)值的累加和，并存儲(chǔ)到相應(yīng)的列表中；

（6）NUM＋＝Num；

（7）End While

（8）將數(shù)組的分量除以NUM；得到新的中心點(diǎn)坐標(biāo)。

根據(jù)上述規(guī)約得到的聚類結(jié)果，得到新的中心點(diǎn)，更新HDFS中的中心文件，利用Setup 函數(shù)，進(jìn)行初始化，進(jìn)行下一輪Job，直到算法收斂。

2 BRTI－K－means實(shí)驗(yàn)結(jié)果分析

2.1 實(shí)驗(yàn)平臺(tái)、測(cè)試數(shù)據(jù)集和評(píng)價(jià)指標(biāo)

本文所有實(shí)驗(yàn)環(huán)境搭建的平臺(tái)的組成為：2 臺(tái)2GHZ Inter Xeon CPU、2G 內(nèi)存和4臺(tái)2GHZ Inter Xeon CPU、1G 內(nèi)存的PC 構(gòu)成的，操作系統(tǒng)均為Ubuntu Linux 10.10，Hadoop版本選用1.1.2；Java開發(fā)包為JDK1.7版本，程序開發(fā)工具為Eclipse－standard－kepler－SR1－linux，算法使用Java實(shí)現(xiàn)。

實(shí)驗(yàn)數(shù)據(jù)集采用了UCI數(shù)據(jù)集下Synthetic＿Control，分別構(gòu)造了100 M，200 M，300 M，400 M，500 M，1G的60維不同大小的數(shù)據(jù)集來(lái)驗(yàn)證算法的時(shí)效性；同時(shí)，為了驗(yàn)證算法的有效性，利用了Wine（數(shù)據(jù)對(duì)象178，屬性13）數(shù)據(jù)集，Iris數(shù)據(jù)集 （數(shù)據(jù)對(duì)象150，屬性4），Libras數(shù)據(jù)集 （數(shù)據(jù)對(duì)象360，屬性90）進(jìn)行了實(shí)驗(yàn)。同時(shí)，利用節(jié)點(diǎn)個(gè)數(shù)的不同驗(yàn)證了算法的擴(kuò)展性的效率。

在實(shí)驗(yàn)中，為了測(cè)試BRTI－K－means算法的性能，本文采用了以下評(píng)價(jià)指標(biāo)：加速比 （speedup）、時(shí)效性、數(shù)據(jù)伸縮率和有效性 （采用正確率 （正確的個(gè)數(shù)／總個(gè)數(shù)%）表達(dá)算法的有效性）。

2.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中，由于算法初始中心隨機(jī)選擇，因而對(duì)初始中心點(diǎn)進(jìn)行了10次隨機(jī)選擇，同時(shí)進(jìn)行了10 次運(yùn)算，最終的結(jié)果利用10次實(shí)驗(yàn)結(jié)果的平均值來(lái)獲得。

為了驗(yàn)證該算法的有效性，該算法采用了不同大小的數(shù)據(jù)集進(jìn)行測(cè)試，同時(shí)獲得了BRTI－K－means算法的加速比，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 BRTI－K－means算法加速比結(jié)果的測(cè)試

從圖2可以發(fā)現(xiàn)，BRTI－K－means算法在處理少量數(shù)據(jù)時(shí)加速比的變化是接近線性的；然而，當(dāng)數(shù)據(jù)集的規(guī)模越來(lái)越大時(shí)，該算法的加速比的變化會(huì)變大，效果越明顯。其主要的原因是：①在主節(jié)點(diǎn)計(jì)算出了K 個(gè)中心彼此最短距離，并把結(jié)果作為全局變量分配到各個(gè)子節(jié)點(diǎn)；因而，隨著數(shù)據(jù)集的增大，在主節(jié)點(diǎn)所耗費(fèi)時(shí)間所占的比重越來(lái)越少；②在該算法中加入了Combine操作，減少了大數(shù)據(jù)的通訊代價(jià)，并且隨著數(shù)據(jù)的增長(zhǎng)，效果會(huì)更加明顯；③由于該算法減少了每個(gè)數(shù)據(jù)點(diǎn)到中心點(diǎn)的計(jì)算次數(shù)，從而減少了算法的運(yùn)行時(shí)間；因此，當(dāng)數(shù)據(jù)規(guī)模越大時(shí)，算法加速比性能越好，適合用于大數(shù)據(jù)的聚類分析研究。

為了進(jìn)一步證明BRTI－K－means算法的優(yōu)越性，本文通過(guò)利用6 個(gè)有效節(jié)點(diǎn)，把不同的大小的數(shù)據(jù)集與Kmeans和Canopy－Kmeans聚類算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 3種算法時(shí)效性的對(duì)比

從圖3可以看出，3種算法在不同大小的數(shù)據(jù)集上執(zhí)行的時(shí)間是不同的，基于MapReduce的距離三角不等式Kmeans算法 （BRTI－K－means）在執(zhí)行時(shí)間上有了明顯的改善；同時(shí)可以看出，伴隨著數(shù)據(jù)集的增長(zhǎng)，BRTI－K－means算法更進(jìn)一步提高了聚類算法的時(shí)效性。

圖4 給出了BRTI－K－means算法數(shù)據(jù)伸縮率的測(cè)試結(jié)果。在實(shí)驗(yàn)中，分別測(cè)試了不同節(jié)點(diǎn)下不同大小數(shù)據(jù)集BRTI－K－means算法的運(yùn)行時(shí)間。

從圖4可以發(fā)現(xiàn)，算法的時(shí)效性不僅與數(shù)據(jù)集的大小有關(guān)，而且還與實(shí)驗(yàn)平臺(tái)的數(shù)據(jù)節(jié)點(diǎn)密切相關(guān)；當(dāng)數(shù)據(jù)節(jié)點(diǎn)較少時(shí)，時(shí)效性呈現(xiàn)出線性變化的特點(diǎn)；當(dāng)隨著數(shù)據(jù)節(jié)點(diǎn)的不斷增多，算法的執(zhí)行效率變化越快。

為了進(jìn)一步驗(yàn)證算法的有效性，在實(shí)驗(yàn)中，使用平臺(tái)下的3個(gè)節(jié)點(diǎn)，利用UCI數(shù)據(jù)集，針對(duì)于BRTI－K－means算法與K－means和Canopy－Kmeans算法的有效性進(jìn)行了比較，實(shí)驗(yàn)結(jié)果如表1所示。

圖4 BRTI－K－means算法的伸縮性

表1 不同算法對(duì)UCI數(shù)據(jù)集的測(cè)試結(jié)果

通過(guò)上述表1 的實(shí)驗(yàn)結(jié)果表明：Canopy－Kmeans算法與BRTI－K－means算法都從一定的程度上提高了K－means算法的有效性；其主要原因?yàn)椋涸陬A(yù)處理過(guò)程中都用Canopy算法對(duì)原始數(shù)據(jù)進(jìn)行了預(yù)處理。

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

本文通過(guò)把距離三角不等式原理與K－means算法的性相結(jié)合，在基于云計(jì)算平臺(tái)環(huán)境下針對(duì)于傳統(tǒng)的K－means算法進(jìn)行了改進(jìn)，提出了一種改進(jìn)BRTI－K－means算法，提高原算法的執(zhí)行速度。實(shí)驗(yàn)結(jié)果表明：算法具有良好的時(shí)效性、加速比、伸縮性和有效性等性能，適合用于大數(shù)據(jù)的聚類分析。這些算法均以K－means算法為原型，具有K－means的特性，對(duì)于非等軸狀分布、具有噪聲或孤立點(diǎn)的數(shù)據(jù)對(duì)象分布，3 種聚類算法的有效性必然會(huì)降低。因此，對(duì)于K－means的改進(jìn)需要在云計(jì)算平臺(tái)下更進(jìn)一步的研究。

［1］Anand Rajira Man，Jeffrey David Ullman.Mining of massive datasets［M］.WANG Bin，transl.Beijing：The People’s Posts and Telecommunicati Ons Press，2013：176－205 （in Chinese）.［Anand Rajira man，Jeffrey David Ullman.互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘與分布式處理 ［M］.王斌，譯.北京：人民出版社，2013：176－205.］

［2］BAO Xiaodi，ZHANG Fangfang.Reaserchon the key technologies of big data ［J］.Information Construction，2013 （10）：49－54 （in Chinese）.［鮑曉地，張芳芳.大數(shù)據(jù)處理的關(guān)鍵技術(shù)研究 ［J］.信息化建設(shè)，2013 （10）：49－54.］

［3］Ciprian Dobre，F(xiàn)atos Xhafa.Parallel programming paradigms and frameworks in big data era ［J］.International Journal of Parallel Programming，2014，42 （5）：710－738.

［4］LIU Gang，HOU Bing，ZHAI Zhouwei.Open source cloud computing platform for Hadoop ［M］.Beijing：Beijing University of Post and Telecommunications Press，2011：35－72 （in Chinese）. ［劉剛，侯賓，翟周偉.Hadoop開源云計(jì)算平臺(tái)［M］.北京：北京郵電大學(xué)出版社，2011：35－72.］

［5］Hadoop ［EB／OL］.http：／／hadoop.apache，2014.

［6］QIAN Yanjiang.Research and implementation on the technologies of mining of massive datasets［D］.Chengdu：University of Electronic Science and Technology of China，2009：27－55（in Chinese）. ［錢彥江.大規(guī)模數(shù)據(jù)聚類技術(shù)研究與實(shí)現(xiàn)［D］.成都：電子科技大學(xué)，2009：27－55.］

［7］QIU Rongtai.Research on Map－Reduce application based on Hadoop ［D］.Jiaozuo：Henan Polytechnic University，2009：17－32 （in Chinese）.［邱榮太.基于Hadoop平臺(tái)的Map－Reduce應(yīng)用研究 ［D］.焦作：河南理工大學(xué)，2009：17－32.］

［8］WEN Cheng.Parallel clustering algorithm based on MapRedcuce ［D］.Hangzhou：Zhjiang University，2011 （in Chinese）. ［溫程.并行聚類算法在MapReduce上的實(shí)現(xiàn) ［D］.杭州：浙江大學(xué)，2011.］

［9］ZHAO Weizhong，MA Huifang，F(xiàn)U Yanxiang.Research on parallel K－means algorithm design based on Hadoop platform ［J］.Computing Science，2011，38 （10）：166－178 （in Chinese）. ［趙衛(wèi)中，馬慧芳，傅燕翔.基于云計(jì)算平臺(tái)的并行K－means聚類算法設(shè)計(jì)研究［J］.計(jì)算機(jī)科學(xué)，2011，38 （10）：166－178.］

［10］ZHOU Lijuan， WANG Hui， WANG Wenbo.Parallel Kmeans algorithm for massive data ［J］.Journal Huazhong University of Science and Technology （Natural Science Edition），2012 （S1）：150－152 （in Chinese）. ［周麗娟，王慧，王文伯.面向海量數(shù)據(jù)的并行K－means算法 ［J］.華中科技大學(xué)學(xué)報(bào) （自然科學(xué)版），2012 （S1）：150－152.］

［11］Cui Xiaoli，Zhu Pingfei，Yang Xin，et al.Optimized big data K－means clustering using MapReduce［J］.The Journal of Supercomputing，2014，70 （3）：1249－1259.

［12］TANG Zhenkun.Based on the Spark machine learning platform design and implementation ［D］.Xiamen：Amoy University，2014 （in Chinese）.［唐振坤.基于Spark的機(jī)器學(xué)習(xí)平臺(tái)設(shè)計(jì)與實(shí)現(xiàn) ［D］.廈門：廈門大學(xué)，2014.］

［13］Bu Yingyi，Bill Howe，Magdalena Balazinska，et al.Ha－Loop：Efficient iterative data processing on large clusters［C］／／36th International Conference on Very Large Data Bases，2010：1－12.

［14］ZHAO Qing.Efficient algorithm of Canopy－K－means based on Hadoop platform ［J］.University of Electronic Science and Technology of China，2014，27 （2）：29－32 （in Chinese）.［趙慶.基于Hadoop 平臺(tái)下的Canopy－K－means 高效算法［J］.電子科技大學(xué)，2014，27 （2）：29－32.］

［15］MAO Dianhui.Improved Canopy－Kmeans algorithm based on MapReduce ［J］.Computer Engineering and Applications，2012，48 （27）：22－26 （in Chinese）. ［毛典輝.基于MapReduce的Canopy－K－means改進(jìn)算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48 （27）：22－26.］

［16］SHAN Yushuang，XING Changzheng.Amore effective Kmeans clustering algorithm ［J］.Computer Systems ＆ Applications，2009 （8）：96－99 （in Chinese）. ［單玉雙，邢長(zhǎng)征.一種更有效的K－means聚類算法 ［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2009 （8）：96－99.］