基于云計算平臺的聚類算法

孟海東，任敬佩

（內蒙古科技大學 信息工程學院，內蒙古 包頭014010）

0 引 言

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

鑒于以上改進后的K－means聚類算法的優點，利用文獻 ［16］在K－means算法引進了三角不等式原理的基礎上，提出一種改進的BRTI－K－means（MapReduce based triangle inequality Canopy K－means，BRTI－K－means）算法。主要通過基于開源云計算平臺，利用MapReduce分布式框架，融合了距離三角不等式定理，同時在大數據的預處理過程當中，使用Canopy算法對原始的大數據進行了預處理，進一步實現了K－means算法在聚類分析過程中的改進；為了進一步驗證BRTI－K－means算法的優越性，將該算法與Kmeans和Canopy－Kmeans算法進行了算法比較。

1 BRTI－K－means算法

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

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

假設在歐幾里得空間內有任意3個數據點X、C1、C2，數據點間距離滿足三角不等式原理：d（X，C1）＋d（C1，C2）＞＝d（X，C2），d（C1，C2）－d（X，C1）＜＝d（X，C2）；若X 為數據空間中任意一個數據點，C1和C2為兩個簇中心點。如果2＊d（X，C1）＜＝d（C1，C2），同時在兩邊減去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），即數據點X 屬于簇中心點C1。

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

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

1.2 BRTI－K－means算法設計

BRTI－K－means算法執行過程如下：

（1）將數據集上傳到HDFS，數據分片，并將每一分片存儲到若干臺DataNodes，輸入初始中心點的集合U （作為全局變量）；

（2）在每個計算節點，計算每個中心點到其它中心點的最短距離D 集合；

（3）根據距離三角不等式原理，將滿足條件的數據點劃分到各個中心點所在的簇，同時把已劃分的數據點從數據集V 中刪除；如果在數據集V 中還有不符合條件的數據點，則根據已經計算得到的數據點到各個中心點的距離分配給相應的簇，并把相應的數據點從V 中刪除；

圖1 BRTI－K－means算法實現流程

（4）生成新的中心點；

（5）返回到 （2）重新計算數據中心點，直到數據中心點不在發生變化為止，算法結束；

（6）實現子節點的歸約，輸出聚類結果。

具體實現BRTI－K－means算法的偽代碼如下：

Setup函數

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

（1）對所有的中心點C 和C’，計算d（C，C’）；對所有的中心點C，S（C）＝min（d（C，C’））（C≠C’）；

（2）計算所有中心點C 和C’，求出彼此最短距離并保存到相應的數組中；

（3）如果中心點發生改變，則重復步驟 （1）與 （2）。

Map函數

輸入：簇中心點的集合U，數據集V（v1，v2，…，vn）；

輸出：K 中心點集合U’；

（1）U’＝U；

（2）While（true）

（3）計算出V 中數據點到中心點C 的距離d1；

（4）If（2＊d1＜＝S）標記數據點屬于第一個中心點的簇；同時從V 中刪除這個數據點，并保存不符合條件的數據點到該中心點的距離到數組D；依次類推，直到計算出V 中所有點的聚類，并標記出其所屬簇；

（5）End If

（6）If（V！＝Null）

（7）根據上述中心點的距離D，計算到C 的最短距離，選取到中心點最近的簇，并進行標記，同時從V 中刪除該數據點；

（8）End If

（9）計算已被標記點所屬簇的新的C；

（10）對比上一個中心與新中心點之間的距離 （Distance＝＝0）；

（11）If（Distance＝＝0）

（12）Break

（13）Else

（14）返回 （3）重新計算；

（15）End while

Combine函數

為了減少大數據在主節點與子節點之間的通訊時間，該算法在Map函數之后設計了一個Combine操作；它的主要功能為：對于本地節點的數據文件進行合并，減少大數據的I／O 傳輸。

輸入：V 中數據點所屬簇下標 （Key），Key對應鍵值對列表；

輸出：V 中數據點所屬簇下標 （Key），各個簇內被標記數據點的各維累加值，以及Key對應鍵值對列表；

（1）定義一個列表，用于存儲各個簇內被標記數據點的各維累加值；

（2）初始化一個變量Num＝0，記錄所屬簇內點的個數；

（3）While（V.hasNext（））

（4）在V.next（）中，解析出各維坐標值；

（5）計算上步過程中各維累加值和，并存儲到定義的列表當中；

（6）Num＋＋；

（7）End While

Reduce函數設計

輸入：V 中數據點所屬簇下標 （Key），Key對應的鍵值對列表；

輸出：V 中數據點所屬簇下標 （Key），以及新的中心點；

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

（2）初始化一個變量NUM＝0，記錄所屬簇內標記點的個數；

（3）While（V.hasNext（））

（4）在V.next（）中，解析出坐標值，計算出樣本個數Num；

（5）計算上步解析出v 的各維坐標值的累加和，并存儲到相應的列表中；

（6）NUM＋＝Num；

（7）End While

（8）將數組的分量除以NUM；得到新的中心點坐標。

根據上述規約得到的聚類結果，得到新的中心點，更新HDFS中的中心文件，利用Setup 函數，進行初始化，進行下一輪Job，直到算法收斂。

2 BRTI－K－means實驗結果分析

2.1 實驗平臺、測試數據集和評價指標

本文所有實驗環境搭建的平臺的組成為：2 臺2GHZ Inter Xeon CPU、2G 內存和4臺2GHZ Inter Xeon CPU、1G 內存的PC 構成的，操作系統均為Ubuntu Linux 10.10，Hadoop版本選用1.1.2；Java開發包為JDK1.7版本，程序開發工具為Eclipse－standard－kepler－SR1－linux，算法使用Java實現。

實驗數據集采用了UCI數據集下Synthetic＿Control，分別構造了100 M，200 M，300 M，400 M，500 M，1G的60維不同大小的數據集來驗證算法的時效性；同時，為了驗證算法的有效性，利用了Wine（數據對象178，屬性13）數據集，Iris數據集 （數據對象150，屬性4），Libras數據集 （數據對象360，屬性90）進行了實驗。同時，利用節點個數的不同驗證了算法的擴展性的效率。

在實驗中，為了測試BRTI－K－means算法的性能，本文采用了以下評價指標：加速比 （speedup）、時效性、數據伸縮率和有效性 （采用正確率 （正確的個數／總個數%）表達算法的有效性）。

2.2 實驗結果

實驗中，由于算法初始中心隨機選擇，因而對初始中心點進行了10次隨機選擇，同時進行了10 次運算，最終的結果利用10次實驗結果的平均值來獲得。

為了驗證該算法的有效性，該算法采用了不同大小的數據集進行測試，同時獲得了BRTI－K－means算法的加速比，實驗結果如圖2所示。

圖2 BRTI－K－means算法加速比結果的測試

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

為了進一步證明BRTI－K－means算法的優越性，本文通過利用6 個有效節點，把不同的大小的數據集與Kmeans和Canopy－Kmeans聚類算法進行比較，實驗結果如圖3所示。

圖3 3種算法時效性的對比

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

圖4 給出了BRTI－K－means算法數據伸縮率的測試結果。在實驗中，分別測試了不同節點下不同大小數據集BRTI－K－means算法的運行時間。

從圖4可以發現，算法的時效性不僅與數據集的大小有關，而且還與實驗平臺的數據節點密切相關；當數據節點較少時，時效性呈現出線性變化的特點；當隨著數據節點的不斷增多，算法的執行效率變化越快。

為了進一步驗證算法的有效性，在實驗中，使用平臺下的3個節點，利用UCI數據集，針對于BRTI－K－means算法與K－means和Canopy－Kmeans算法的有效性進行了比較，實驗結果如表1所示。

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

表1 不同算法對UCI數據集的測試結果

通過上述表1 的實驗結果表明：Canopy－Kmeans算法與BRTI－K－means算法都從一定的程度上提高了K－means算法的有效性；其主要原因為：在預處理過程中都用Canopy算法對原始數據進行了預處理。

3 結束語

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

［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.互聯網大規模數據挖掘與分布式處理 ［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）.［鮑曉地，張芳芳.大數據處理的關鍵技術研究 ［J］.信息化建設，2013 （10）：49－54.］

［3］Ciprian Dobre，Fatos 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開源云計算平臺［M］.北京：北京郵電大學出版社，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）. ［錢彥江.大規模數據聚類技術研究與實現［D］.成都：電子科技大學，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平臺的Map－Reduce應用研究 ［D］.焦作：河南理工大學，2009：17－32.］

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

［9］ZHAO Weizhong，MA Huifang，FU Yanxiang.Research on parallel K－means algorithm design based on Hadoop platform ［J］.Computing Science，2011，38 （10）：166－178 （in Chinese）. ［趙衛中，馬慧芳，傅燕翔.基于云計算平臺的并行K－means聚類算法設計研究［J］.計算機科學，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）. ［周麗娟，王慧，王文伯.面向海量數據的并行K－means算法 ［J］.華中科技大學學報 （自然科學版），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的機器學習平臺設計與實現 ［D］.廈門：廈門大學，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 平臺下的Canopy－K－means 高效算法［J］.電子科技大學，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］.計算機工程與應用，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）. ［單玉雙，邢長征.一種更有效的K－means聚類算法 ［J］.計算機系統應用，2009 （8）：96－99.］