譚躍生，楊寶光，王靜宇，張亞楠

（1.內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭014010；2.內(nèi)蒙古科技大學(xué) 網(wǎng)絡(luò)中心，內(nèi)蒙古 包頭014010）

0 引 言

現(xiàn)如今隨著網(wǎng)絡(luò)應(yīng)用的興起，網(wǎng)絡(luò)數(shù)據(jù)量極具增加，當(dāng)大規(guī)模數(shù)據(jù)利用機(jī)器學(xué)習(xí)算法進(jìn)行分析處理時(shí)，很難在有限的時(shí)間內(nèi)完成要解決的任務(wù)，為了加快處理分析數(shù)據(jù)，分布式處理和云計(jì)算平臺(tái)被提到日程上來。

機(jī)器學(xué)習(xí)算法并行化研究現(xiàn)在有多種方法，目前的方法主要有MPI并行、PVM并行，但是MPI并行主要用于科學(xué)計(jì)算，算法編寫比較復(fù)雜，PVM并行計(jì)算對(duì)于硬件要求比較高，需要高性能計(jì)算機(jī)，故這兩種方法不適合大規(guī)模推廣。MapReduce編程框架的提出彌補(bǔ)了此兩種方法的不足。

機(jī)器學(xué)習(xí)算法已經(jīng)開始應(yīng)用于處理分析數(shù)據(jù)，機(jī)器學(xué)習(xí)算法也有很多種，經(jīng)典的有k－means算法、SVM （support vector machine）、Apriori算法和譜聚類算法等［1］。譜聚類算法作為一種新型的機(jī)器學(xué)習(xí)算法，具有明顯的優(yōu)勢(shì)，該算法不僅思想簡(jiǎn)單，易于實(shí)現(xiàn)，不易陷入局部最優(yōu)解，而且具有識(shí)別非凸分布聚類的能力，能夠?qū)θ我庑螤畹臉颖究臻g進(jìn)行聚類，非常適合于解決許多實(shí)際應(yīng)用問題［2］，但是在面對(duì)大數(shù)據(jù)集時(shí)該算法也顯得無力，故本文是針對(duì)此算法的分布式研究。

1 相關(guān)理論

云計(jì)算是一種新的計(jì)算模式，其特征在于能夠處理大量分布式數(shù)據(jù)集，而不是簡(jiǎn)單的計(jì)算。與網(wǎng)格計(jì)算側(cè)重于科學(xué)計(jì)算不同的是，云計(jì)算更加關(guān)注商業(yè)數(shù)據(jù)處理［3］。Hadoop是Apache組織下的一個(gè)開源項(xiàng)目，它可以非常輕松地部署云計(jì)算系統(tǒng)。它支持在商業(yè)硬件級(jí)構(gòu)成的大型集群上部署數(shù)據(jù)密集型分布式應(yīng)用。這個(gè)框架是可擴(kuò)展的，它允許用戶按照應(yīng)用要求添加更多的節(jié)點(diǎn)。Hadoop使用的文件系統(tǒng)稱為 HDFS （Hadoop distributed file system），這種文件系統(tǒng)可以創(chuàng)建數(shù)據(jù)塊的多個(gè)副本，并將它們分配到整個(gè)集群中計(jì)算機(jī)節(jié)點(diǎn)，以實(shí)現(xiàn)可靠的、快速的計(jì)算。Hadoop是使用MapReduce的分布式計(jì)算模型，MapReduce編程模型最早由Google公司提出，并廣泛的應(yīng)用在其內(nèi)部許多領(lǐng)域。Hadoop開源實(shí)現(xiàn)了該模型，MapReduce由兩個(gè)用戶自定義函數(shù)：Map函數(shù)和Reduce函數(shù)。

Map階段，這階段主要是將輸入數(shù)據(jù) （任務(wù)）分割成固定大小任務(wù)塊，之后該框架將每個(gè)任務(wù)塊進(jìn)一步分解成鍵值對(duì)＜Key1，Value1＞ （以后簡(jiǎn)稱＜K1，V1＞）的形式。而每一個(gè)數(shù)據(jù)塊都會(huì)創(chuàng)建一個(gè)Map任務(wù)，每個(gè)Map任務(wù)是由map函數(shù)來執(zhí)行的，并將對(duì)應(yīng)數(shù)據(jù)塊中的鍵值對(duì)＜K1，V1＞作為輸入，經(jīng)過計(jì)算得到一個(gè)中間結(jié)果＜K2，V2＞，得到中間結(jié)果之后會(huì)進(jìn)行從新排序，將key值相同的value放在一起形成一個(gè)新的列表＜K2，list（V2）＞形式，最后再根據(jù)key值的范圍將其進(jìn)行分組［4］。

Reduce階段，Reduce階段主要工作是接收不同Map任務(wù)中的數(shù)據(jù)，并將其整合在一起進(jìn)行排序，然后調(diào)用reduce函數(shù)，對(duì)輸入的＜K2，list（V2）＞進(jìn)行處理，得到最后的鍵值對(duì)＜K3，V3＞并最后輸出在HDFS上。

Map和Reduce處理模型如圖1所示。

圖1 Map和Reduce處理模型

2 Normalized譜聚類算法

譜聚類算法思想是將樣本數(shù)據(jù)看作為一個(gè)個(gè)頂點(diǎn)，這些頂點(diǎn)根據(jù)它們之間的相似度用直線連結(jié)起來，這些數(shù)據(jù)樣本間相似度看作是帶權(quán)的邊，用G＝ （V，E）表示無向圖，其中V和E分別為其頂點(diǎn)集和邊集，從而將聚類問題轉(zhuǎn)為圖分割問題，這就是要找到一種圖分割的方法使得連接不同組邊的權(quán)重盡可能低，組內(nèi)邊的權(quán)重盡可能高，最后進(jìn)行分割，分割后還連在一起的頂點(diǎn)就是同一類。

譜聚類算法是建立在譜圖理論基礎(chǔ)上，其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的最優(yōu)劃分問題，是一種點(diǎn)對(duì)聚類算法。劃分準(zhǔn)則直接影響了聚類結(jié)果的好壞，所以選擇一種最優(yōu)的劃分準(zhǔn)則是至關(guān)重要的。最常用的劃分準(zhǔn)則有以下幾種方法，Minimum Cut方法、Ratio Cut方法、Normalized Cut方法等［5］，由于Normalized Cut方法迭代次數(shù)相對(duì)其它幾種方法來說是比較少的，故本文提出基于Normalized Cut分割方法的譜聚類算法研究。Normalized Cut方法是由Shi和 Malik提出的，并給出了Normalized Cut方法的目標(biāo)函數(shù)［6］

式中：Cut（A，B）——A，B 二 個(gè) 子 圖 的 相 似 程 度，sumA——A圖中所以點(diǎn)的權(quán)值之和。根據(jù)Normalized Cut劃分方法得出譜聚類的具體實(shí)習(xí)步驟如下：

（1）根據(jù)輸入數(shù)據(jù)構(gòu)建相似矩陣W；

（2）利用相似矩陣W計(jì)算出對(duì)角矩陣D；

（3）計(jì)算出規(guī)范化Laplacian矩陣L；

（4）計(jì)算出矩陣L前K個(gè)最小特征值及其對(duì)應(yīng)的特征向量；

（5）利用這個(gè)K組特征向量組成新的矩陣，矩陣的行數(shù)為樣本數(shù)N，列數(shù)為K；

（6）最后用K－means算法進(jìn)行聚類，得到最后結(jié)果［7］。

之所以稱為Normalized譜聚類，是因?yàn)樵诘谌接?jì)算得到的Laplacian矩陣是規(guī)范化的

式中：Lsym——是規(guī)范化Laplacian矩陣，L——非規(guī)范化，D——對(duì)角矩陣，W——相似矩陣。

3 譜聚類并行化設(shè)計(jì)

3.1 構(gòu)建相似矩陣

首先要對(duì)原始數(shù)據(jù)進(jìn)行處理，構(gòu)建文本向量，在構(gòu)建文本向量時(shí)要計(jì)算每個(gè)詞在文本中出現(xiàn)的次數(shù)，這就要用到 TF－IDF （term frequency－inverse document frequency）算法。如果某一特征項(xiàng)t在文檔d中的權(quán)重為w，公式如下

式中：tft，d——局部參數(shù)，idft——全局參數(shù)，分子 nt，d是特征項(xiàng)t在文檔d中的出現(xiàn)次數(shù)，分母則是在文件d中所有特征項(xiàng)的出現(xiàn)次數(shù)之和。｜D｜是文件集中的文件總數(shù)，是含有特征項(xiàng)t的文件數(shù)。文檔d的權(quán)重向量為

文本d1和文本d2之間的相似度可以采用向量間內(nèi)積來度量。如下所示

計(jì)算出的相似矩陣W是對(duì)稱矩陣并且其對(duì)角元素為0，假設(shè)相似值用Wij來表示，有Wij＝Wji且Wii＝0。

3.2 構(gòu)建對(duì)角矩陣

3.3 并行規(guī)范化矩陣Laplacian

這一步只要工作是并行計(jì)算規(guī)范化Laplacian矩陣和Laplacian矩陣的前k個(gè)最小特征值及特征向量。非規(guī)范化矩陣Laplacian表示為L(zhǎng)＝D－W，規(guī)范化Laplacian矩陣為

式中：L——非規(guī)范化矩陣，Lsym——規(guī)范化矩陣［8］，由于D是對(duì)角矩陣，也就是也是對(duì)角矩陣，因此在計(jì)算Laplacian矩陣時(shí)就是簡(jiǎn)單的矩陣相乘。偽代碼如下：

今天是竹韻到威力裝飾工程有限公司上班以來的第一次領(lǐng)工資，連工資加獎(jiǎng)金領(lǐng)了2000多元，比下崗前的工資高得多，特別高興，馬上給龍斌的姐姐打了電話，要請(qǐng)她一家夜晚去她家吃飯，好好慶賀慶賀。這時(shí)，海力的電話又打了過來，要她馬上去他辦公室打一轉(zhuǎn)，有重要事情要跟她談。

計(jì)算Laplacian矩陣的最小特征值及特征向量有很多方法，比如說雅克比算法，雅克比算法在求解特征值和特征向量時(shí)用的是一種迭代的思想，迭代次數(shù)隨著數(shù)據(jù)量的增大而增多，但MapReduce編程模式不適合反復(fù)迭代的算法，反復(fù)迭代會(huì)降低效率。為了更好的適應(yīng)MapReduce編程框架，本文選用Lanczos算法，Lanczos算法是將對(duì)稱矩陣通過正交相似變換變成對(duì)稱三對(duì)角矩陣的算法［9］。得到的三對(duì)角矩陣和原來的矩陣是相似的，也就是說求出這個(gè)三對(duì)角矩陣的前k個(gè)最小特征向量就是求出L的前k個(gè)最小特征向量，求出三對(duì)角矩陣的前k個(gè)最小特征向量只需簡(jiǎn)單的將矩陣L和向量v相乘。

3.4 并行Canopy算法

選用kmeans算法對(duì)數(shù)據(jù)進(jìn)行最后的聚類，由于kmeans算法適合處理維度較低的數(shù)據(jù)，故先選用Canopy算法對(duì)數(shù)據(jù)進(jìn)行降維再處理。Canopy算法思想非常簡(jiǎn)單，它適合應(yīng)對(duì)海量數(shù)據(jù)、多維數(shù)據(jù)，所用的聚類時(shí)間短，但是聚類效果不是很準(zhǔn)確。Canopy算法是由McCallum提出來的，Canopy算法主要的過程，該算法在處理數(shù)據(jù)時(shí)會(huì)自動(dòng)采用復(fù)雜度最低的算法來計(jì)算樣本之間的距離并且在處理樣本數(shù)據(jù)集時(shí)會(huì)把該數(shù)據(jù)劃分成多個(gè)子集，這些子集是重疊的，這種子集稱之為華蓋 （canopies）［10］。Canopy算法的流程如圖2所示。

圖2 Canopy算法流程

并行處理Canopy算法：

第一階段，各個(gè)slave節(jié)點(diǎn)可以依據(jù)存儲(chǔ)在本地的數(shù)據(jù)，各自在本地用上述算法生成若干Canopy，最后在master節(jié)點(diǎn)將這些Canopy用相同算法匯總后得到最終的Cano－py集合，第二階段聚類操作就利用最終的Canopy集合進(jìn)行。用了兩個(gè)map操作和一個(gè)reduce操作，首先用一個(gè)map和一個(gè)reduce生成全局Canopy集合，最后用一個(gè)map操作進(jìn)行聚類。算法并行化流程如圖3所示。

圖3 算法并行化流程

選用kmeans算法對(duì)數(shù)據(jù)進(jìn)行最后的聚類，并行kmeans算法的思想就是將每個(gè)樣本分配給其選定的中心點(diǎn)，重復(fù)迭代，這個(gè)過程是可以在hadoop平臺(tái)上并行執(zhí)行的，kmeans算法并行化主要工作是Map階段的設(shè)計(jì)、Combiner函數(shù)的設(shè)計(jì)、Reduce函數(shù)的設(shè)計(jì)，其具體的方法已有相應(yīng)的實(shí)現(xiàn)［11］。

3.5 時(shí)間復(fù)雜度分析

構(gòu)建相似矩陣時(shí)由算法可知其時(shí)間復(fù)雜度為O（n2），如果采用m臺(tái)機(jī)器進(jìn)行并行計(jì)算，那么理論上時(shí)間復(fù)雜度會(huì)降為O（n2／m）。

并行對(duì)角矩陣時(shí)，假設(shè)計(jì)算每一行的時(shí)間復(fù)雜度為O（m），那么計(jì)算對(duì)角矩陣總時(shí)間復(fù)雜度變?yōu)镺（m＋m＋…＋m）＝O（nm），如果采用p臺(tái)計(jì)算機(jī)并行執(zhí)行，理想情況下時(shí)間復(fù)雜度降為O（nm／p）。

同樣當(dāng)計(jì)算Laplacian矩陣和Laplacian矩陣前k個(gè)最小特征值時(shí)相應(yīng)的時(shí)間復(fù)雜度理論上也會(huì)降低到原來的1／k（k為實(shí)驗(yàn)的計(jì)算機(jī)臺(tái)數(shù)）。

Hadoop平臺(tái)是由多處理機(jī)同時(shí)進(jìn)行數(shù)據(jù)處理的，主節(jié)點(diǎn)和從節(jié)點(diǎn)之間需要進(jìn)行通訊，假設(shè)實(shí)驗(yàn)有m臺(tái)處理機(jī)，主節(jié)點(diǎn)和從節(jié)點(diǎn)之間通訊一次的時(shí)間復(fù)雜度為O（n），Hadoop平臺(tái)處理數(shù)據(jù)時(shí)，主節(jié)點(diǎn)是隨機(jī)分配任務(wù)，假設(shè)m－1臺(tái)從節(jié)點(diǎn)與主節(jié)點(diǎn)共通訊k次就完成了處理任務(wù)，那么總的通訊復(fù)雜度理論上為O（kn）。處理機(jī)通訊時(shí)由于網(wǎng)絡(luò)原因會(huì)導(dǎo)致通訊延遲，會(huì)影響到最后計(jì)算的精度，一次通訊延遲為C，通訊了k次，理論上總通訊延遲時(shí)間為kC，但由于Hadoop平臺(tái)處理的對(duì)象為海量數(shù)據(jù)，處理數(shù)據(jù)的時(shí)間會(huì)遠(yuǎn)遠(yuǎn)大于通訊延遲時(shí)間，所以實(shí)際上通訊延遲時(shí)間是可以大致忽略的。

4 實(shí)驗(yàn)及性能分析

實(shí)驗(yàn)采用VMware＿ESXi＿5.0.0虛擬化平臺(tái)。在該平臺(tái)上安裝6臺(tái)虛擬機(jī)，在6臺(tái)虛擬機(jī)上搭建Hadoop集群環(huán)境，其中一臺(tái)作為NameNode和JobTracker節(jié)點(diǎn)其余的5臺(tái)部署DataNode和TaskTracker。實(shí)驗(yàn)采用的6臺(tái)虛擬機(jī)硬件與軟件配置見表1。

表1 配置

實(shí)驗(yàn)數(shù)據(jù)采用Reuters－21578文本分類測(cè)試集和dbpedia真實(shí)數(shù)據(jù)分別在集群中進(jìn)行數(shù)據(jù)伸縮率和加速比實(shí)驗(yàn)分析。

文本分類測(cè)試集：數(shù)據(jù)伸縮率采用Reuters－21578文本分類測(cè)試集，分別取數(shù)據(jù)集的1／8，1／4，1／2還有全部數(shù)據(jù)在5臺(tái)機(jī)器上進(jìn)行加速比測(cè)試。加速比為Sp＝T1／Tp。其中Sp是加速比，T1是單處理器下的運(yùn)行時(shí)間，Tp是在有P個(gè)處理器并行系統(tǒng)中的運(yùn)行時(shí)間。當(dāng)Sp＝P時(shí)，此加速比被稱為線性加速比。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 Reuters－21578

從實(shí)驗(yàn)結(jié)果中能看出，隨著數(shù)據(jù)集的不斷增大加速比有增大的趨勢(shì)，HDFS文件系統(tǒng)最小的默認(rèn)存儲(chǔ)塊為64M，這就注定了該平臺(tái)是為處理大數(shù)據(jù)集而設(shè)計(jì)的，如果數(shù)據(jù)集比較小，集群之間的通信開銷會(huì)占用只要時(shí)間，加速比反而會(huì)下降，考慮到Reuters－21578數(shù)據(jù)集自身比較小，故選用5臺(tái)集群進(jìn)行實(shí)驗(yàn)。

Dbpedia真實(shí)數(shù)據(jù)：選取Dbpedia真實(shí)數(shù)據(jù)進(jìn)行不同節(jié)點(diǎn)加速比實(shí)驗(yàn)，實(shí)驗(yàn)采用的Dbpedia數(shù)據(jù)是取自Dbpedia的web文檔，一共4192499篇文檔，包含了51246種類別，數(shù)據(jù)內(nèi)容包括人物、地點(diǎn)、歌曲、電影、游戲、組織、體育、科技、飲食等。實(shí)驗(yàn)分別取2、3、4、5、6個(gè)節(jié)點(diǎn)分別就行試驗(yàn)，對(duì)比在同一數(shù)據(jù)集下隨著節(jié)點(diǎn)數(shù)的增加集群加速比會(huì)有什么變化。

從圖5中可以看出隨著節(jié)點(diǎn)數(shù)的增加，集群加速比也在增大，但是當(dāng)節(jié)點(diǎn)數(shù)繼續(xù)增大時(shí)，加速比增大的就不是很明顯了，這主要因?yàn)镠adoop平臺(tái)適合處理大規(guī)模數(shù)據(jù)，當(dāng)數(shù)據(jù)非常大時(shí)，集群處理數(shù)據(jù)的速度會(huì)有明顯的提高，各個(gè)節(jié)點(diǎn)之間通信所花費(fèi)的時(shí)間會(huì)占很小一部分，相反，如果處理的數(shù)據(jù)相對(duì)較小，當(dāng)集群節(jié)點(diǎn)數(shù)增加時(shí)，往往各個(gè)節(jié)點(diǎn)之間的通信時(shí)間會(huì)占很大一部分，這就導(dǎo)致了加速比變小。

圖5 集群加速比

5 結(jié)束語

本文提出了在大數(shù)據(jù)集下一種機(jī)器學(xué)習(xí)算法的并行化改進(jìn)。改進(jìn)之后的算法可以在HDFS文件系統(tǒng)下進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)部分分別測(cè)試了數(shù)據(jù)的伸縮率和不同節(jié)點(diǎn)下集群加速比。從實(shí)驗(yàn)結(jié)果上可以看出并行之后的譜聚類算法在集群加速比有明顯加快，也可以看出Hadoop平臺(tái)適合處理大數(shù)據(jù)集，數(shù)據(jù)集越大加速比越明顯，但由于實(shí)驗(yàn)用的環(huán)境和數(shù)據(jù)集大小有限，影響了實(shí)驗(yàn)的對(duì)比，接下來的主要工作是增大節(jié)點(diǎn)數(shù)和增大數(shù)據(jù)集從中找出最優(yōu)聚類的節(jié)點(diǎn)數(shù)和數(shù)據(jù)集大小并且采用源自信息論的規(guī)范化互信息 （normalized mutual information，NMI）來 量 化 聚類結(jié)果。

［1］Han J，Kamber M，Pei J.Data mining：Concepts and techniques［M］.3rd ed.Burlington：Morgan Kaufmann，2011：5－6.

［2］SUN Yuxia.Reseach on spectral clustering algorithm in data mining ［D］.Qingdao：Ocean University of China，2010 （in Chinese）.［孫玉俠.數(shù)據(jù)挖掘中的譜聚類算法研究 ［D］.青島：中國(guó)海洋大學(xué)，2010.］

［3］LIU Peng.Cloud computing ［M］.2nd ed.Beijing：Publishing House of Electronics Industry，2011 （in Chinese）. ［劉鵬.云計(jì)算 ［M］.2版.北京：電子工業(yè)出版社，2011.］

［4］Shvachko K，Hairong Kuang.The hadoop distributed file system ［C］／／IEEE 26th Symposium.Incline Village， Mass Storage Systems and Technologies，2010：1－10.

［5］Ulrike von Luxburg.A tutorial on spectral clustering ［J］.Statistics and Computing，2007，17 （4）：395－416.

［6］HUANG Yicen，SHEN Yifan.Improved image segmentation algorithm based on Normalized Cut ［J］.Computer Engineering and Applications，2008，44 （34）：179－181 （in Chinese）.［黃一岑，沈一帆.基于Normalized Cut的圖像分割改進(jìn)算法［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44 （34）：179－181.］

［7］Chen Wenyen，Song Yangqiu，Bai Hongjie.Parallel spectral clustering in distributed systems ［C］／／IEEE Transactions on Pattern A－nalysis and Machine Intelligence，2011，33 （3）：568－586.

［8］Ulrike von Luxburg.Mikhail belkin and olivier bousquet ［J］.Annals of Statistics，Institute of Mathematical Statistice，2008，36 （2）：555－586.

［9］Cullum，Willoughby.Lanczos algorithms for large symmetric eigenvalue computations：Pro－grams Vol.II ［M］.Birkhauser Boston Inc，2012：6－10

［10］McCallum A，Nigam K，Ungar L H.Efficient clustering of high－dimensional data sets with application to reference matching ［C］／／ProceedIngs of the sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.USA：ACM，2000：169－178.

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