劉黎志，楊 敏

智能機器人湖北省重點實驗室（武漢工程大學），湖北 武漢430205

支持向量機（support vector machine，SVM）分類模型的建立需要經(jīng)過大量的計算，隨著訓練樣本集規(guī)模的增長，不僅會大量消耗主機的CPU及內(nèi)存資源，而且訓練模型所需要時間也會急劇增加，從而使得在單機環(huán)境下得到模型變得十分困難，因此如何針對大規(guī)模數(shù)據(jù)集，使用并行化方式獲得最優(yōu)支持向量機分類模型，一直是研究的熱點問題［1-3］?；贖adoop平臺的分布式計算框架MapReduce及Spark為并行化訓練大規(guī)模數(shù)據(jù)集提供了新的方法和手段［4-7］，在分布式計算框架的支持下，SVM分類模型的訓練過程可以并行化，從而顯著縮短了得到模型所需要的時間［8-10］，層疊化SVM就是基于MapReduce框架并行獲取支持向量的典型應用［11-12］。為了讓SVM分類模型能夠更魯棒地用于實際數(shù)據(jù)的預測及解決線性不可分問題，在模型的訓練過程中，需要對模型的參數(shù)進行選擇，從而得到最優(yōu)的模型［13-14］。相關(guān)研究運用MapReduce框架建立分布式參數(shù)尋優(yōu)模型，完成了模型訓練、預測和參數(shù)選擇優(yōu)化。吳云蔚等［15］針對使用網(wǎng)格搜索對SVM參數(shù)進行全局尋優(yōu)時存在的尋優(yōu)時間長的問題，提出了一種基于Hadoop分布式文件系統(tǒng)（hadoop distributed file system，HDFS）平臺的分布式參數(shù)尋優(yōu)方法，提高了尋優(yōu)效率。白玉辛［16］基于Flink并行網(wǎng)格搜索算法對SVM參數(shù)進行尋優(yōu)，將全局參數(shù)對文件切分成若干小塊交給各個計算節(jié)點并行尋優(yōu)，最后匯總尋優(yōu)結(jié)果，減少了尋優(yōu)時間。李坤等［17］基于Spark集群實現(xiàn)了libsvm參數(shù)優(yōu)選的并行化，提出了并行粗粒度網(wǎng)格搜索參數(shù)優(yōu)選算法，相比傳統(tǒng)算法運行速度提升了近7倍，且隨著集群規(guī)模的擴大而進一步加大。

但當前的這些研究都缺少在訓練過程對集群內(nèi)存資源消耗情況的論述。因此本文提出一種在MapReduce框架下進行最優(yōu)模型參數(shù)選擇的新算法，該算法能夠在合理利用集群內(nèi)存資源及保證進行交叉驗證的Reduce任務(wù)充分并行執(zhí)行的前提下，顯著減少最優(yōu)模型參數(shù)的獲取時間。

1 SVM分類最優(yōu)模型參數(shù)選擇

對于給定的訓練數(shù)據(jù)集：D={(xi,yi)|xi∈Rn,yi∈(-1,1)}mi=1，求解SVM最優(yōu)超平面的對偶問題描述為：

其中m為支持向量的個數(shù)，ɑi為支持向量對應的拉格朗日算子。

c為懲罰參數(shù)，控制SVM模型如何處理錯誤，對于線性可分問題，合適的c值可以使得超平面間距最大，同時出現(xiàn)的分類錯誤最少。沒有一個特定的c值可以解決所有的線性可分問題，對于具體的問題，最優(yōu)的c值只能通過實驗的方法得到。

對于線性不可分問題，可以通過核函數(shù)將數(shù)據(jù)映射到多維空間，使其線性可分。核函數(shù)K的返回值是數(shù)據(jù)點在轉(zhuǎn)換為多維空間向量后的內(nèi)積值，核函數(shù)K的形式化定義為：給定一個映射函數(shù)φ:x→ν，函數(shù)K:x→R，定義為：

其中，＜φ(x),φ(x')＞ν表示x,x'在轉(zhuǎn)換為φ(x),φ(x')后在ν中的內(nèi)積。核函數(shù)的類型有線性核函數(shù)、多項式核函數(shù)、高斯核函數(shù)等。實踐證明，使用高斯核函數(shù)對線性不可分問題進行分類，一般可以取得較好的效果，故在選擇核函數(shù)時，高斯核函數(shù)一般是首選。高斯核函數(shù)的描述為：

γ和c值一樣需要通過實驗得到其最優(yōu)值，取得最優(yōu)值的實驗為采用交叉驗證的網(wǎng)格搜索方法（grid search）。對于第i組給定的(ci,γi)，交叉驗證的過程為將訓練集劃分為大小相同的n個等份，依次取其中的第j份為測試集Tj,j=(1,2,…,n)，剩下的n-1份為訓練集，使用根據(jù)訓練集得到的分類模型預測Pj，得到預測準確率Aj，整個交叉驗證的準確率Ai為：

上述的過程稱為n重交叉驗證（n-fold cross validation）。n重交叉驗證使得整個訓練集中的數(shù)據(jù)均被預測，其準確率為整個訓練集中的數(shù)據(jù)被正確分類的百分比，故n重交叉驗證能有效的避免模型的過擬合問題。最優(yōu)模型參數(shù)的選擇就是在集合p={(ci,γi)|ci,γi∈R}mi=1中，使用交叉驗證得到每組參數(shù)的Ai，取準確率最高的參數(shù)(ci,γi)為最優(yōu)模型參數(shù)。使用網(wǎng)格搜索得到最優(yōu)模型是個非常耗時的過程，假設(shè)參數(shù)集合p的參數(shù)組數(shù)為m，每組參數(shù)進行n重交叉驗證，每一次交叉驗證的平均時間為w，若為串行執(zhí)行，網(wǎng)格搜索的總時間t為：

由此可見網(wǎng)格搜索的時間隨著參數(shù)組數(shù)m及交叉驗證的重數(shù)n而線性增長。在網(wǎng)格搜索的過程中，由于對某組參數(shù)進行交叉驗證的過程與其它參數(shù)組無關(guān)，故多組參數(shù)的交叉驗證過程可以并行執(zhí)行，從而縮短網(wǎng)格搜索得到最優(yōu)模型所需要的時間。

2 分布式集群環(huán)境下的最優(yōu)模型參數(shù)選擇

2.1 最優(yōu)模型參數(shù)的選擇過程

在分布式集群環(huán)境下，MapReduce框架負責處理并行計算中的分布式存儲、工作調(diào)度、負載均衡、容錯均衡、容錯處理以及網(wǎng)絡(luò)通信等復雜問題。MapReduce框架采用“分而治之”的策略，其核心步驟主要分兩部分：Map和Reduce。在向MapReduce框架提交一個計算作業(yè)后，MapReduce會首先把作業(yè)拆分成若干個Map任務(wù)，然后這些Map任務(wù)被分配到不同的機器上執(zhí)行，這些Map任務(wù)完成后會產(chǎn)生一些鍵值對構(gòu)成的中間文件，它們將會作為Reduce任務(wù)的輸入數(shù)據(jù)。Reduce任務(wù)的主要目標就是把前面若干個Map的輸出進行處理并給出結(jié)果。MapReduce框架的作業(yè)配置非常靈活，可以指定只單獨運行Map或者Reduce任務(wù)；指定完成具體任務(wù)的Reduce的個數(shù)；通過key值指定Map任務(wù)與Reduce任務(wù)的對應關(guān)系等。本文提出的最優(yōu)模型參數(shù)選擇方法首先在Map任務(wù)中讀取存儲在HDFS文件系統(tǒng)中的參數(shù)文件，然后在Reduce任務(wù)中進行模型的訓練及交叉驗證，得到模型的準確率。基于MapReduce的SVM最優(yōu)分類模型參數(shù)選擇的過程如圖1所示。

圖1 基于MapReduce的最優(yōu)模型參數(shù)選擇過程Fig.1 Optimal model parameter selection processbased on MapReduce

分布式集群環(huán)境下的最優(yōu)模型選擇的核心思想就是讓多組參數(shù)可以同時訓練，以縮短得到最優(yōu)模型參數(shù)的時間。將需要訓練的參數(shù)集合參數(shù)p={(c i,γi)|c i,γi∈R}m i=1中的每組參數(shù)(c i,γi)以一個文件的方式寫入到HDFS文件系統(tǒng)，當文件的個數(shù)達到指定的閾值n(n≤m)時，啟動MapReduce作業(yè)，通過重載Map任務(wù)讀取文件的模式，使得每個Map任務(wù)讀取輸入?yún)?shù)文件的所有內(nèi)容，在確保key唯一后，將＜key,參數(shù)＞寫入到中間結(jié)果。由于每組參數(shù)的key值不同，且Reduce的個數(shù)設(shè)置為n，所以JobTrack可以保證每個Reduce任務(wù)只訓練一組參數(shù)。每個Reduce任務(wù)讀取緩存在集群內(nèi)存中的訓練數(shù)據(jù)集文件及調(diào)用緩存在集群中的libsvm包中的方法訓練模型并進行交叉驗證，模型訓練的結(jié)果寫入HBase數(shù)據(jù)庫，以便對訓練過程進行統(tǒng)計分析。

2.2 最優(yōu)模型選擇算法設(shè)計

由于每組參數(shù)的交叉驗證過程要在Reduce任務(wù)中完成，增加Reduce的任務(wù)并發(fā)數(shù)顯然可以加快獲得最優(yōu)模型參數(shù)的速度。但是，當并發(fā)執(zhí)行的Reduce任務(wù)個數(shù)到達一定閾值后，集群的內(nèi)存資源將被全部占用，從而導致其它的MapReduce作業(yè)由于缺少內(nèi)存資源而無法執(zhí)行。因此，必須限制并發(fā)執(zhí)行的Reduce的任務(wù)個數(shù)。一種限制Reduce任務(wù)個數(shù)的方式為：將需要選擇的m個參數(shù)劃分為n個MapReduce作業(yè)(J1,J2,…,Jn-1,Jn),n≥1，其中（J1,J2,…,Jn-1)執(zhí)行mn個參數(shù)的驗證，Jn執(zhí)行m%n個參數(shù)的驗證，（J1,J2,…,Jn-1)在JobTrack的控制下串行執(zhí)行，執(zhí)行過程如圖2所示。

圖2（a）中的每個Ji中并行執(zhí)行m n個或者m%n個Reduce任務(wù)，矩形條表示每個Reduce任務(wù)的完成時間。對于第i個作業(yè)Ji，執(zhí)行交叉驗證耗時最長的Reduce任務(wù)完成時間為Ri，由于Ji為串行執(zhí)行方式，所以使用該方式進行最優(yōu)參數(shù)選擇的總時間G為：

另一種方式為單個MapReduce作業(yè)方式，即只啟動MapReduce作業(yè)一次，讓m個Reduce任務(wù)全部處于就緒狀態(tài)，但限制能獲得資源并行執(zhí)行的Reduce的任務(wù)個數(shù)為k,k≤m。當某個Reduce任務(wù)執(zhí)行完成后，處于就緒等待隊列中的某個Reduce任務(wù)獲得資源開始執(zhí)行，直到就緒隊列中的所有Reduce任務(wù)執(zhí)行完成。單個MapReduce作業(yè)方式的執(zhí)行過程如圖2（b）所示。

圖2 （a）串行MapReduce作業(yè)方式；（b）單個MapReduce作業(yè)方式Fig.2（a）Serial MapReduce job mode；（b）Single MapReduce job mode

單個MapReduce作業(yè)方式只在執(zhí)行最后一批k個Reduce任務(wù)時，需要等待耗時其中最長的任務(wù)執(zhí)行完成，其它情況下，耗時長的任務(wù)將和其它任務(wù)一起并行執(zhí)行。

通過比較兩種MapReduce作業(yè)方式可以發(fā)現(xiàn)，串行MapReduce作業(yè)方式調(diào)度簡單，不需要維護額外的Reduce任務(wù)就緒隊列或者等待任務(wù)執(zhí)行，但當作業(yè)中存在耗時的Reduce任務(wù)時，會顯著增加整個作業(yè)的完成時間，因此串行MapReduce作業(yè)方式適合并行執(zhí)行的各個Reduce任務(wù)的完成時間差距不大的細粒度最優(yōu)參數(shù)搜索。單個MapReduce作業(yè)方式只向集群提交一次作業(yè)，如果運行失敗，整個參數(shù)選擇的過程必須重做。但當作業(yè)中包括耗時的Reduce任務(wù)時，該作業(yè)方式可以使得耗時的任務(wù)和其它任務(wù)同時執(zhí)行，從而加快最優(yōu)參數(shù)的獲取速度，因此單個MapReduce作業(yè)方式適合Reduce任務(wù)的完成時間差距較大的粗粒度最優(yōu)參數(shù)搜索。

SVM最優(yōu)模型參數(shù)選擇的算法流程如圖3所示，其中reduceNums參數(shù)用于控制作業(yè)中并發(fā)執(zhí)行的Reduce任務(wù)的個數(shù)，reduceNumsAllowed參數(shù)用于控制集群中允許執(zhí)行的Reduce任務(wù)的個數(shù)。當reduceNums＜=cnum*gnum，reduceNums-Allowed＜=reduceNums時為串行MapReduce作業(yè)方式。當reduceNums＜=cnum*gnum，reduceNums-Allowed＜=reduceNums時為單個MapReduce作業(yè)方式。

圖3 SVM最優(yōu)模型參數(shù)選擇算法流程圖Fig.3 Flow chart of SVM optimal model parameter selection algorithm

MapReduce作業(yè)中的Map任務(wù)讀取存儲在HDFS文件系統(tǒng)中的參數(shù)文件，并以＜key，value＞的形式寫成，交給Reduce處理，其算法描述如圖4和圖5所示，其中paramFile表示當前參數(shù)文件，context表示MapReduce作業(yè)上下文。

圖4 MapReduce作業(yè)中的Map任務(wù)流程圖Fig.4 Flow chart of Map task in MapReducejob

圖5 MapReduce作業(yè)中的Reduce任務(wù)流程圖Fig.5 Flow chart of Reduce task in MapReduce job

存儲在HDFS文件系統(tǒng)中的參數(shù)文件經(jīng)過Map任務(wù)處理后，由于各自的key值不同，所以MapReduce框架的JobTrack把每組參數(shù)交給一個Reduce任務(wù)來處理，從而使得模型的選擇過程并行化，在Reduce任務(wù)的算法描述中，paramStr表示參數(shù)字符串，context表示MapReduce作業(yè)上下文。

Reduce任務(wù)中的交叉驗證過程直接調(diào)用libsvm包中的方法完成，訓練數(shù)據(jù)集中的輸入特征需要按libsvm規(guī)定的稀疏矩陣格式進行壓縮，輸入特征值一般需要進行歸一化處理，避免特征值之間的數(shù)量級差距過大對訓練算法的影響。在每組參數(shù)對應的Reduce任務(wù)完成后，將其交叉驗證的結(jié)果寫入HBase表，以便對數(shù)據(jù)進行統(tǒng)計分析，得到最優(yōu)模型的參數(shù)及其它性能指標。HBase的表結(jié)構(gòu)如圖6所示。

圖6 實驗結(jié)果存儲HBase表結(jié)構(gòu)Fig.6 Structure of HBase table of storing experiment results

3 實驗部分

實驗用服務(wù)器為DELL PowerEdge R720，其配置為2個物理CPU（Intel Xeon E5-2620 V2 2.10 GHz，每個CPU含6個內(nèi)核，共12個內(nèi)核），32 GB內(nèi)存，8 TB硬盤，4個物理網(wǎng)卡。服務(wù)器安裝VMWare esxi6.0.0操作系統(tǒng)，虛擬化整個服務(wù)器環(huán)境?？蛻舳耸褂肰MWare VSphere client 6.0.0將服務(wù)器劃分為4個虛擬機，每個虛擬機的配置為3內(nèi)核CPU，8 GB內(nèi)存，2 TB硬盤，1個物理網(wǎng)卡。每個虛擬機安裝ubuntu-16.04.1-server-amd64操作系統(tǒng)，Hadoop 2.7.3分布式計算平臺，組成含1個主節(jié)點，4個數(shù)據(jù)節(jié)點（主節(jié)點也是數(shù)據(jù)節(jié)點）的集群。實驗選用https：//www.csie.ntu.edu.tw/～cjlin/libsvmtools/datasets/中的a8a二分類訓練數(shù)據(jù)集，a8a共包含22 696條數(shù)據(jù)，大小在1.6 MB左右。

進行粗粒度參數(shù)選擇，比較在Reduce任務(wù)完成時間差距較大時，串行MapReduce作業(yè)方式和單個MapReduce作業(yè)方式在最優(yōu)模型參數(shù)選擇時的時間性能和集群內(nèi)存消耗上的差別。設(shè)置參數(shù)nrFold=4，cnum=8，c初始值為0，遞增步長為1，搜索范圍為0～7。參數(shù)gnum=8，γ的初始值為0，遞增步長為10-1，搜索范圍為0～10-7。ci和γi的笛卡爾積為64，在這64組參數(shù)中進行粗粒度搜索。設(shè)置reduceNums/reduceNumsAllowed參數(shù)分別為4/4，8/8，16/16，32/32，64/64，即reduceNums＜=cnum*gnum，reduceNums=reduceNumsAllowed，進行串行MapReduce作業(yè)方式實驗，得到的實驗數(shù)據(jù)如表1所示。

表1中的Reduce任務(wù)的最快、最慢及平均完成時間，均通過查詢統(tǒng)計BMSResult表得到，具體過程在此不詳細描述。分析表1可以發(fā)現(xiàn)，1）集群內(nèi)存資源的消耗隨著并行執(zhí)行的Reduce的任務(wù)個數(shù)的增加而增加，當Reduce的任務(wù)數(shù)量達到32個時，內(nèi)存被100%全部占用，無法得到內(nèi)存資源的Reduce任務(wù)只能等待正在執(zhí)行的任務(wù)完成后，再由JobTrack調(diào)度執(zhí)行。2）Reduce任務(wù)的平均完成時間，隨著并行執(zhí)行的任務(wù)數(shù)的增加而增加，說明當集群并發(fā)任務(wù)數(shù)多時，CPU的調(diào)度和內(nèi)存資源的分配緊張，Reduce完成任務(wù)的時間增加。3）獲取最優(yōu)參數(shù)的總訓練時間，隨著并行執(zhí)行的Reduce的任務(wù)的個數(shù)的增加，MapReduce作業(yè)啟動的次數(shù)的減少而下降，說明雖然任務(wù)并發(fā)個數(shù)多時，完成每個Reduce任務(wù)的平均時間雖然增加，但由于Reduce任務(wù)的并發(fā)度增加，獲得最優(yōu)參數(shù)的總時間相反會下降。

設(shè)置reduceNums/reduceNumsAllowed參數(shù)分別為64/4，64/8，64/16，即reduceNums=cnum*gnum，reduceNumsAllowed＜reduceNums，進 行 單 個MapReduce作業(yè)方式實驗，得到的實驗數(shù)據(jù)如表2所示。

比較表1中的實驗1-實驗3及表2中的實驗1-實驗3，可發(fā)現(xiàn)在內(nèi)存消耗相等時，粗粒度參數(shù)選擇單個MapReduce作業(yè)方式獲取最優(yōu)參數(shù)的總時間均優(yōu)于串行MapReduce作業(yè)方式。比較表2中的實驗3和表1中的實驗3，在內(nèi)存消耗相等時，獲取最優(yōu)模型的時間性能提高（4 559-3 506）/3 506≈30%；比較表2中的實驗3和表1中的實驗4-實驗5，可以發(fā)現(xiàn)單個MapReduce作業(yè)方式在僅消耗集群56%的內(nèi)存時，獲取最優(yōu)參數(shù)的時間與串行MapReduce作業(yè)方式消耗100%內(nèi)存時相近；比較表2中的實驗3和表1中的實驗1，可以發(fā)現(xiàn)通過合理的選擇獲取最優(yōu)參數(shù)的方式及設(shè)置reduceNums/reduceNumsAllowed參數(shù)，在保證集群內(nèi)存的合理消耗下，獲取最優(yōu)參數(shù)的時間性能提高了（9 599-3 506）/3 506≈174%。

表1 粗粒度參數(shù)選擇串行MapReduce作業(yè)方式實驗數(shù)據(jù)表Tab.1 Experimental results of serial MapReduce job mode for coarse-grained parameter selection

表2 粗粒度參數(shù)選擇單個MapReduce作業(yè)方式實驗數(shù)據(jù)表Tab.2 Experimental results of single MapReduce job mode for coarse-grained parameter selection

其次，進行細粒度粒度參數(shù)選擇，比較在Reduce任務(wù)完成時間差距不大時，串行MapReduce作業(yè)方式和單個MapReduce作業(yè)方式在最優(yōu)模型參數(shù)選擇時的時間性能和集群內(nèi)存消耗上的差別。設(shè)置參數(shù)nrFold=4，cnum=8，c初始值為0.5，遞增步長為0.25，搜索范圍為0.5～2.25。參數(shù)gnum=8，γ的初始值為0.05，遞增步長為0.012 5，搜索范圍為0.05～0.137 5。設(shè)置reduceNums/reduce-NumsAllowed參數(shù)分別為4/4，8/8，16/16，64/4，64/8，64/16，得到的實驗結(jié)果如表3所示。

比較表3中的實驗1-實驗3和實驗4-實驗6，可以發(fā)現(xiàn)在進行細粒度參數(shù)選擇時，當Reduce任務(wù)的完成時間差距不大時，在同等內(nèi)存消耗的情況下，兩種MapReduce作業(yè)方式在獲取最優(yōu)模型參數(shù)的時間性能上差距不大。

表3 細粒度參數(shù)選擇串行/單個MapReduce作業(yè)方式對比實驗數(shù)據(jù)表Tab.3 Comparison of experimental results between serial and single MapReduce job mode for fine-grained parameter selection

4 結(jié) 論

SVM分類模型最優(yōu)參數(shù)的選擇是一個非常耗時的過程，本文提出的基于MapReduce框架的最優(yōu)分類模型參數(shù)選擇的算法，能夠在分布式集群環(huán)境下，讓模型參數(shù)的交叉驗證過程并行執(zhí)行，并通過選擇不同的MapReduce作業(yè)方式，配置集群中的并發(fā)任務(wù)數(shù)，可以在合理的集群內(nèi)存消耗的情況下，顯著縮短獲取最優(yōu)參數(shù)的時間。后續(xù)的研究方向設(shè)想為：（1）對于大規(guī)模的訓練數(shù)據(jù)集，可否首先按并行層疊的方式獲取支持向量集合，然后僅根據(jù)獲取到的支持向量集合進行最優(yōu)模型參數(shù)選擇，從而減少進行交叉驗證的數(shù)據(jù)規(guī)模，提高獲取最優(yōu)參數(shù)的速度。（2）研究在Spark分布式計算框架進行SVM最優(yōu)模型參數(shù)的選擇的具體方式。