白玉辛，劉曉燕

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明 650500)

1 引 言

大數(shù)據(jù)時(shí)代背景下，信用卡交易、傳感器測(cè)量、機(jī)器日志、網(wǎng)站或移動(dòng)應(yīng)用程序上的用戶交互等各種類型的數(shù)據(jù)都是作為事件流產(chǎn)生的，傳統(tǒng)數(shù)據(jù)挖掘算法處理這些大規(guī)模數(shù)據(jù)集的能力出現(xiàn)瓶頸，因此需要將傳統(tǒng)數(shù)據(jù)挖掘算法和現(xiàn)有大數(shù)據(jù)框架進(jìn)行結(jié)合，改變傳統(tǒng)數(shù)據(jù)挖掘算法無(wú)法高效處理大規(guī)模數(shù)據(jù)集的現(xiàn)狀.支持向量機(jī)[1](Support Vector Machine,SVM)基于統(tǒng)計(jì)學(xué)習(xí)理論，在模式識(shí)別、文本分類和圖像識(shí)別等眾多領(lǐng)域表現(xiàn)出優(yōu)異實(shí)踐性能的機(jī)器學(xué)習(xí)算法.SVM相比較其他常用的數(shù)據(jù)挖掘算法而言，在算法訓(xùn)練過(guò)程中很少會(huì)出現(xiàn)過(guò)度擬合、屬性特征過(guò)多造成的維數(shù)災(zāi)難對(duì)算法性能影響微乎其微、對(duì)核函數(shù)運(yùn)用巧妙，可以讓算法處理數(shù)據(jù)集線性不可分的情況.但是，當(dāng)傳統(tǒng)SVM算法處理大規(guī)模數(shù)據(jù)集時(shí)，會(huì)出現(xiàn)訓(xùn)練速度慢，內(nèi)存溢出，運(yùn)行崩潰等性能低下問(wèn)題[2-4].

針對(duì)傳統(tǒng)單機(jī)SVM算法面對(duì)大規(guī)模數(shù)據(jù)集處理效率低下等問(wèn)題，最近幾年數(shù)據(jù)挖掘領(lǐng)域的專家主要使用兩種方法改進(jìn)傳統(tǒng)支持向量機(jī)算法：1)采用“分而治之”的思想處理大規(guī)模數(shù)據(jù)集，該思想是將一個(gè)完整的數(shù)據(jù)集切分成若干訓(xùn)練子集，在每一個(gè)訓(xùn)練子集上訓(xùn)練局部支持向量并剔除大量非樣本邊界樣本點(diǎn)，使其并行訓(xùn)練，達(dá)到算法并行化訓(xùn)練的目的；2)利用GPU或FPGA強(qiáng)大的矩陣運(yùn)算能力來(lái)提高收斂速度.如Li等人[5]基于GPU設(shè)備設(shè)計(jì)實(shí)現(xiàn)了一個(gè)并行SVM智能分類系統(tǒng)，提高SVM預(yù)測(cè)及訓(xùn)練階段算法執(zhí)行的效率.胡福平等人[6]使用FPGA實(shí)現(xiàn)SVM并行計(jì)算結(jié)構(gòu),借助Verilog HDL程序設(shè)計(jì)語(yǔ)言完成了各模塊的結(jié)構(gòu)設(shè)計(jì)，該結(jié)構(gòu)實(shí)現(xiàn)的SVM的分類性能要略優(yōu)于Libsvm.丁宣宣等人[7]利用MapReduce和Bagging的并行組合支持向量機(jī)訓(xùn)練算法，采用Bagging集成算法的思想,結(jié)合隨機(jī)次梯度SVM算法對(duì)剩余的支持向量訓(xùn)練,以提高算法的分類精度.劉澤燊[8]等人使用基于內(nèi)存計(jì)算的分布式處理框架—Spark，實(shí)現(xiàn)基于Spark的并行SVM算法，克服了并行SVM算法在MapReduce模型中迭代計(jì)算的不足.李坤等人[9]和何經(jīng)緯等人[10]則研究如何在Spark框架提高SVM參數(shù)尋優(yōu)的時(shí)間.通過(guò)這些研究一定程度上可以解決傳統(tǒng)支持向量機(jī)訓(xùn)練效率低下等問(wèn)題，但隨著電子商務(wù)的高速發(fā)展，互聯(lián)網(wǎng)電商平臺(tái)的數(shù)據(jù)呈指數(shù)級(jí)別的增長(zhǎng)，鑒于實(shí)時(shí)機(jī)器學(xué)習(xí)的思想提出，因此，需要使用實(shí)時(shí)處理框架來(lái)對(duì)傳統(tǒng)SVM算法做出改進(jìn)，使其能夠適應(yīng)框架，最終達(dá)到線下訓(xùn)練，線上實(shí)時(shí)預(yù)測(cè)的目的.

2008年，柏林理工大學(xué)研發(fā)出一個(gè)大數(shù)據(jù)處理平臺(tái)，此為Flink[11]的前身，隨后在2014年成為了ASF(Apache Software Foundation)的頂級(jí)項(xiàng)目之一.Apache Flink是一個(gè)框架和分布式處理引擎，用于對(duì)無(wú)邊界和有邊界數(shù)據(jù)流上進(jìn)行有狀態(tài)的計(jì)算，并且它可以用于Google數(shù)據(jù)流模型[12]，同時(shí)Flink能在所有常見(jiàn)集群環(huán)境中運(yùn)行，以內(nèi)存速度和任意規(guī)模進(jìn)行計(jì)算.目前互聯(lián)網(wǎng)領(lǐng)域的實(shí)時(shí)搜索、數(shù)據(jù)分析和機(jī)器學(xué)習(xí)等任務(wù)都可以在Flink平臺(tái)上運(yùn)行.

本文對(duì)Cascade SVM算法和Flink計(jì)算框架進(jìn)行了深入研究分析，采用數(shù)據(jù)切分的思想，實(shí)現(xiàn)了基于Flink平臺(tái)并行SVM算法，有助于向線下訓(xùn)練，線上實(shí)時(shí)預(yù)測(cè)模型準(zhǔn)確度.具體工作主要有：1)深入研究CascadeSVM算法的訓(xùn)練結(jié)構(gòu)及合并策略，設(shè)計(jì)基于Flink計(jì)算框架的并行SVM算法；2)對(duì)部分并行操作算子進(jìn)行優(yōu)化，通過(guò)廣播變量的方式將訓(xùn)練過(guò)程中的局部支持向量發(fā)送給下一級(jí)算子，優(yōu)化了原本中間結(jié)果需要寫到本地磁盤的過(guò)程.實(shí)驗(yàn)對(duì)比表明，該算法能夠加快模型訓(xùn)練的速度，保證精度損失較小的前提下，提高了算法執(zhí)行效率.

2 Apache Flink 技術(shù)

Apache Flink(1)http://flink.apache.org一款能夠同時(shí)支持高吞吐、低延遲、高性能的分布式處理框架，在2010年-2014年間，由柏林工業(yè)大學(xué)、柏林洪堡大學(xué)和哈索普拉特納研究所聯(lián)合發(fā)起名為“Stratosphere:Information Management on the Cloud”研究項(xiàng)目，并于2014年4月，貢獻(xiàn)給Apache基金會(huì)孵化器項(xiàng)目，期間改名Flink.自2015年9月發(fā)布第一個(gè)穩(wěn)定版本到現(xiàn)在為止，更多的社區(qū)開發(fā)成員逐步加入，現(xiàn)在Flink在全球范圍內(nèi)擁有350多位開發(fā)人員，在國(guó)內(nèi)比較出名的互聯(lián)網(wǎng)公司如阿里巴巴，滴滴等都在大規(guī)模使用Flink作為企業(yè)的分布式大數(shù)據(jù)處理引擎.在不久的將來(lái)，F(xiàn)link也將成為企業(yè)內(nèi)部主流的數(shù)據(jù)處理框架，最終成為下一代大數(shù)據(jù)處理的標(biāo)準(zhǔn).

Apache Flink是一個(gè)集眾多具有競(jìng)爭(zhēng)力的特性于一身的第3代流處理引擎.它支持精確的流處理，能同時(shí)滿足各種規(guī)模下對(duì)高吞吐和低延遲的要求，尤其是以下功能使其在同類系統(tǒng)中脫穎而出：1)同時(shí)支持事件時(shí)間和處理時(shí)間語(yǔ)義.事件時(shí)間語(yǔ)義能夠針對(duì)無(wú)序事件提供一致、精確的結(jié)果.處理時(shí)間語(yǔ)義能夠用在具有極低延遲需求的應(yīng)用中；2)提供精確一次(exactly-once)的狀態(tài)一致性保障；3)在每秒處理數(shù)百萬(wàn)條事件的同時(shí)保持毫秒級(jí)延遲，同時(shí)基于Flink的應(yīng)用可以擴(kuò)展到數(shù)千核心之上；4)層次化的API在表達(dá)能力和易用性方面各有權(quán)衡；5)支持高可用性配置(無(wú)單點(diǎn)失效)，如Apache Kafka、Apache Cassandra、JDBC、Elasticsearch以及分布式文件系統(tǒng)(HDFS和S3)等.

現(xiàn)實(shí)世界中，所有的數(shù)據(jù)都是以流式的形態(tài)產(chǎn)生的，根據(jù)現(xiàn)實(shí)的數(shù)據(jù)產(chǎn)生方式和數(shù)據(jù)產(chǎn)生是否含有邊界(具有起始點(diǎn)和終止點(diǎn))角度，將數(shù)據(jù)分為兩種類型的數(shù)據(jù)集，一種是有界數(shù)據(jù)集，另一種是無(wú)界數(shù)據(jù)集.Flink正是用于這兩種數(shù)據(jù)集上進(jìn)行有狀態(tài)計(jì)算，其核心模塊是一個(gè)數(shù)據(jù)流執(zhí)行引擎，主要是通過(guò)Java代碼實(shí)現(xiàn)的.其中有界數(shù)據(jù)集具有時(shí)間邊界，在處理過(guò)程中數(shù)據(jù)一定會(huì)在某個(gè)時(shí)間范圍內(nèi)起始或結(jié)束，對(duì)有界數(shù)據(jù)集的數(shù)據(jù)處理方式被稱為批處理(Batch Process)；對(duì)于無(wú)界數(shù)據(jù)集，數(shù)據(jù)從一開始生成就持續(xù)不斷地產(chǎn)生新的數(shù)據(jù)，因此數(shù)據(jù)是沒(méi)有邊界的，對(duì)無(wú)界數(shù)據(jù)集的數(shù)據(jù)處理方式被稱為流處理(Streaming Process).Flink最近提出了本地閉環(huán)迭代操作符[13]和基于成本的自動(dòng)優(yōu)化器，它能夠重新排序操作符，并更好地支持流，所以Flink 在處理迭代和實(shí)時(shí)數(shù)據(jù)處理問(wèn)題時(shí)，能夠在保證穩(wěn)定性和狀態(tài)一致性的同時(shí)提高系統(tǒng)的運(yùn)行速度，支持?jǐn)?shù)據(jù)高吞吐和低延遲等優(yōu)點(diǎn).

3 相關(guān)概念和原理介紹

3.1 支持向量機(jī)

支持向量機(jī)SVM算法是建立在統(tǒng)計(jì)學(xué)習(xí)理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理基礎(chǔ)上，其基本模型是在特征空間上尋找具有最大邊緣距離(Maximum Marginal)分類超平面的線性分類器，有效克服了傳統(tǒng)機(jī)器學(xué)習(xí)算法中出現(xiàn)維數(shù)災(zāi)難、過(guò)度擬合和局部最小值等缺點(diǎn).算法描述如下：給定線性可分訓(xùn)練集T={(x1,y1),(x2,y2),…,(xN,yN)}，其中xi∈X=Rn,yi∈Y={+1,-1},i=1,2,…,M；對(duì)于給定的訓(xùn)練集，構(gòu)造并求解約束最優(yōu)化問(wèn)題，然后引入拉格朗日乘子，對(duì)其參數(shù)求偏導(dǎo)，得到與原問(wèn)題對(duì)應(yīng)的對(duì)偶問(wèn)題，如式(1)所示：

αi≥0,i=1,2,…,N

(1)

對(duì)于訓(xùn)練樣本集線性不可分的情況，設(shè)置懲罰函數(shù)C，使分類器模型容忍部分噪聲點(diǎn)的同時(shí)避免了過(guò)擬合學(xué)習(xí)的情況，求解線性分類問(wèn)題，線性分類支持向量機(jī)是一種非常有效的方法，但如果訓(xùn)練數(shù)據(jù)線性不可分時(shí)，對(duì)偶問(wèn)題和決策函數(shù)中有樣本點(diǎn)的內(nèi)積計(jì)算，通過(guò)引入核函數(shù)將樣本從低維空間映射到高維空間，等價(jià)于隱式地在高維空間中學(xué)習(xí)非線性支持向量機(jī)，這樣的方法稱為核技巧，優(yōu)點(diǎn)是實(shí)質(zhì)的分類效果表現(xiàn)在高維空間上，使原問(wèn)題變成線性可分，通過(guò)使用核技巧(knernel trick)及軟間隔最大化，學(xué)習(xí)非線性支持向量機(jī).核函數(shù)包括多項(xiàng)式核、高斯核和線性核，一般的核函數(shù)表達(dá)式為：

K(x,z)=<σ(x)·σ(z)>

(2)

3.2 層疊分組并行SVM算法

Deng Kun等人和Grafs等人提出了分組訓(xùn)練和層疊訓(xùn)練算法，目的是為了解決單機(jī)SVM處理大規(guī)模數(shù)據(jù)集出現(xiàn)訓(xùn)練速度慢，內(nèi)存溢出，運(yùn)行崩潰等性能低下問(wèn)題，但文獻(xiàn)[14]指出分組訓(xùn)練SVM模型在分組數(shù)目分配過(guò)多的情況下，會(huì)導(dǎo)致訓(xùn)練子集中的局部支持分布與原樣本集的分布差別過(guò)大，導(dǎo)致準(zhǔn)確率下降；層疊訓(xùn)練SVM模型在第一層訓(xùn)練過(guò)程中剔除大部分非支持向量，隨后層級(jí)訓(xùn)練過(guò)程中消耗大量的時(shí)間，且過(guò)濾的非支持向量較少，效率低，所以將這兩種算法結(jié)合使用訓(xùn)練模型.算法基本思路是采用3層固定串聯(lián)訓(xùn)練結(jié)構(gòu)，層與層之間采用隨機(jī)合并的方式，首先將訓(xùn)練樣本集隨機(jī)劃分成大小相等的樣本子集(TD1-TD8)，在樣本子集上并行訓(xùn)練SVM，將得到的支持向量合并再隨機(jī)劃分成大小相等新的樣本子集(TD9-TD12)，同樣進(jìn)行并行訓(xùn)練，最后一次迭代將這4個(gè)訓(xùn)練子集合并進(jìn)行全局訓(xùn)練得到全局支持向量機(jī)模型.算法的詳細(xì)流程圖如圖1所示，TDi表示第i個(gè)樣本子集，SVi表示在TDi樣本子集上訓(xùn)練得到SVM模型.

圖1 層疊分組并行SVM訓(xùn)練算法流程

第1層：根據(jù)大數(shù)據(jù)“分而治之”的思想，將樣本隨機(jī)劃分成大小相等的樣本子集(TD1-TD8)，在各個(gè)訓(xùn)練子集上并行訓(xùn)練SVM模型，本層將濾掉大量非支持向量，同時(shí)剔除非邊界樣本.

第2層：將上層得到的局部支持向量先合并，然后再隨機(jī)劃分成大小相等新的訓(xùn)練子集(TD9-TD12)，并在各自樣本子集上并行訓(xùn)練SVM模型.

第3層：將第2層得到4個(gè)訓(xùn)練樣本子集合并，得到一個(gè)訓(xùn)練集(TD13)，然后進(jìn)行全局支持向量的訓(xùn)練，得到全局支持向量機(jī)模型，同時(shí)判斷是否滿足迭代停止條件.如果不滿足，將結(jié)果送回反饋，重復(fù)以上步驟，直到滿足收斂條件.

4 基于Flink的并行SVM算法的設(shè)計(jì)與實(shí)現(xiàn)

4.1 基于Flink框架并行SVM算法實(shí)現(xiàn)

深入研究層疊分組SVM算法訓(xùn)練策略，結(jié)合Flink計(jì)算框架的優(yōu)勢(shì)，設(shè)計(jì)基于Flink的并行SVM算法.算法的訓(xùn)練流程如圖2所示，在訓(xùn)練模型之前需將訓(xùn)練集樣本及測(cè)試集樣本上傳到Flink集群上，F(xiàn)link設(shè)置批處理執(zhí)行環(huán)境ExecutionEnvironment,通過(guò)readTextFile()方法讀取文件，F(xiàn)link中的JobManager在集群中創(chuàng)建任務(wù)同時(shí)負(fù)責(zé)集群任務(wù)的調(diào)度以及資源管理.算法在Flink集群上進(jìn)行分層的并行SVM訓(xùn)練將局部支持向量進(jìn)行合并，直至最后訓(xùn)練完成，得到全局支持向量模型輸出到本地文件系統(tǒng).

圖2 基于Flink的并行SVM的訓(xùn)練流程

算法在Flink分布式框架上的并行實(shí)現(xiàn)首先搭建Flink集群，設(shè)置集群模式為standalone，上傳訓(xùn)練數(shù)據(jù)集到集群，通過(guò)readTextFile()方法讀取訓(xùn)練集并轉(zhuǎn)換成DataSet[String]數(shù)據(jù)模型，同時(shí)設(shè)置任務(wù)并行度setParalleism(int)，代表將大規(guī)模數(shù)據(jù)集隨機(jī)切分成大小適中的獨(dú)立數(shù)據(jù)塊并分區(qū).然后使用mapPartition()方法并行SVM模型訓(xùn)練，過(guò)濾掉樣本子集中大量非邊界樣本同時(shí)保留局部支持向量SVi，大幅度減少后續(xù)訓(xùn)練樣本數(shù)據(jù)的大小，加快了算法的訓(xùn)練速度，同時(shí)第一層訓(xùn)練完以后將局部支持向量合并再隨機(jī)劃分為大小相同的數(shù)據(jù)塊TDi，同時(shí)以廣播變量的方式發(fā)送給下次迭代，作為下一次迭代的輸入，最后得到一個(gè)數(shù)據(jù)集GTDi，在GTDi上訓(xùn)練SVM，得到全局支持向量模型GModel.基于Flink的并行SVM算法的描述如算法1所示.

算法1.基于Flink的并行SVM算法

輸入:Training Datasets,FilePath

輸出:SVi,GModel

1.val env = ExecutionEnvironment.getExecutionEnvironment

2.val env.setParalleism(8)

3.val DataSet[String]←env.readTextFile(FilePath)

4.Do i=1,…,L

5.val SVi←DataSet.mapPartition(Train_SVM).setBroadcast()

6.val TDi←SVi.rebalence()

7.val SVi←TDi.mapPartition(Train_SVM).setBroadcast()

8.val GTDi←SVi.rebalence()

9.val GModel←GTDi.mapPartition(Train_SVM)

10.Until滿足收斂條件Return GModel

4.2 算法調(diào)優(yōu)

Flink有3種數(shù)據(jù)分區(qū)模式：Rebalance，Hash-Partition和Range-Partition并行操作算子.其中Rebalance根據(jù)輪詢調(diào)度算法，將數(shù)據(jù)均勻地分發(fā)給下一級(jí)節(jié)點(diǎn)，平衡了有些節(jié)點(diǎn)局部支持向量較少，有些節(jié)點(diǎn)局部支持向量過(guò)多的情況，有效利用集群資源，達(dá)到均衡負(fù)載的目的.其次Flink中廣播變量(Broadcast Variable)是算子的多個(gè)并行實(shí)例間共享數(shù)據(jù)的一類方法.廣播變量以集合的方式定義在某個(gè)需要共享的算子上，算子的每一個(gè)實(shí)例可以通過(guò)集合訪問(wèn)共享變量，將局部支持向量以廣播變量的方式發(fā)送給下一級(jí)算子，減少兩個(gè)算子的網(wǎng)絡(luò)通信消耗，提高了算法訓(xùn)練速度，但廣播變量存儲(chǔ)在TaskManager的內(nèi)存里，其大小不易過(guò)大，所以需要通過(guò)第一層剔除大量非邊界樣本點(diǎn)后得到部分支持向量，才能將其以廣播變量的方式發(fā)送給下一級(jí)算子.

5 實(shí)驗(yàn)過(guò)程與結(jié)果分析

5.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

實(shí)驗(yàn)使用LibSVM3.24工具，利用5臺(tái)PC機(jī)構(gòu)建Flink集群，包括1臺(tái)Master節(jié)點(diǎn)和5個(gè)Slave節(jié)點(diǎn)(其中一臺(tái)機(jī)器即是Master節(jié)點(diǎn)又是Slave節(jié)點(diǎn))，集群的任務(wù)調(diào)度模式為standalone.硬件配置：CPU雙核，內(nèi)存4GB，硬盤20G.軟件配置：集群搭建使用Flink-1.7.2-bin-scala_2.11，Scala選用Scala2.11，Java選用JDK1.8(Linux版本)，操作系統(tǒng)選擇CentOS7.訓(xùn)練集采用a9a，covtype.Binary兩個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集(2)https://www.csie.ntu.edu.tw/～ cjlin/libsvmtools/datasets.a9a數(shù)據(jù)集是用來(lái)預(yù)測(cè)一個(gè)成年人的年收入，該數(shù)據(jù)集是一個(gè)二分類問(wèn)題，類標(biāo)號(hào)分別是-1和+1，該數(shù)據(jù)集擁有123個(gè)屬性、32562個(gè)訓(xùn)練樣本和16281個(gè)測(cè)試樣例；covtype.binary數(shù)據(jù)集原始為森林覆蓋率數(shù)據(jù)，有581912個(gè)樣本，每個(gè)樣本具有54維特征.

5.2 實(shí)驗(yàn)結(jié)果及性能評(píng)估

5.2.1 使用廣播變量性能分析

首先使用covtype.binary數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，將數(shù)據(jù)集切分成8個(gè)大小相同的數(shù)據(jù)塊，然后再相同條件下使用廣播變量和不使用廣播變量的情況下，訓(xùn)練不同規(guī)模的樣本集，相關(guān)結(jié)果展示在圖3中，可以看出，隨著樣本數(shù)量的增加，兩者的訓(xùn)練時(shí)間都在增大，但是當(dāng)樣本數(shù)量超過(guò)20萬(wàn)時(shí)，使用廣播變量將局部支持向量轉(zhuǎn)發(fā)給下一級(jí)算子的訓(xùn)練時(shí)間明顯少于不使用廣播變量，這是因?yàn)閷⒕植恐С窒蛄勘４鏋閺V播變量是存儲(chǔ)在內(nèi)存中，不用寫到本地磁盤，下一級(jí)算子直接從內(nèi)存中讀取上一層局部支持向量繼續(xù)計(jì)算，減少了中間結(jié)果寫到本地磁盤和從本地磁盤讀取中間結(jié)果的時(shí)間，算法整體效率更高，極大地減少了合并的時(shí)間.因此最后采用廣播變量的方式將局部支持向量發(fā)送給下一級(jí)算子.

圖3 使用廣播變量

5.2.2 訓(xùn)練結(jié)果與計(jì)算節(jié)點(diǎn)數(shù)量的關(guān)系

為了評(píng)估算法在不同計(jì)算節(jié)點(diǎn)數(shù)量下訓(xùn)練時(shí)間和準(zhǔn)確率的變化情況下，選用了a9a數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，不同規(guī)模的集群(集群中Slave節(jié)點(diǎn)的數(shù)量)在訓(xùn)練時(shí)間取3次訓(xùn)練的平均時(shí)間，準(zhǔn)確率是通過(guò)訓(xùn)練出的SVM模型對(duì)相應(yīng)測(cè)試集進(jìn)行預(yù)測(cè).最終結(jié)果如圖4所示.

從圖4可以看出，隨著計(jì)算節(jié)點(diǎn)數(shù)目的增加，算法的訓(xùn)練時(shí)間逐步下降，這是由于多個(gè)taskManager同時(shí)對(duì)算法并行訓(xùn)練，雖然有效的降低模型訓(xùn)練時(shí)間，但是同時(shí)增加了分區(qū)數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)開銷.開始時(shí)，可以看見(jiàn)算法訓(xùn)練時(shí)間急劇下降，這是單機(jī)與并行訓(xùn)練最大的不同，當(dāng)計(jì)算節(jié)點(diǎn)達(dá)到一定數(shù)量后，集群中每個(gè)taskManager計(jì)算時(shí)間趨于平穩(wěn)，所以整個(gè)訓(xùn)練時(shí)間下降會(huì)變得平緩；算法的測(cè)試準(zhǔn)確率隨著計(jì)算節(jié)點(diǎn)數(shù)量的增加而降低，這是因?yàn)閷?shù)據(jù)集切分過(guò)多的數(shù)據(jù)塊，每個(gè)小數(shù)據(jù)塊與原始數(shù)據(jù)集的支持向量分布差別過(guò)大，所以導(dǎo)致訓(xùn)練出來(lái)的全局支持向量與單機(jī)SVM訓(xùn)練的結(jié)果不一致.平衡集群的計(jì)算能力與數(shù)據(jù)集切分大小的關(guān)系是至關(guān)重要的，我們不能一味追求計(jì)算速度的提升而忽略算法的準(zhǔn)確率.

圖4 計(jì)算節(jié)點(diǎn)對(duì)測(cè)試精度和訓(xùn)練時(shí)間的影響

5.2.3 算法運(yùn)行時(shí)間對(duì)比

算法運(yùn)行時(shí)間對(duì)比實(shí)驗(yàn)采用covtype.binary數(shù)據(jù)集，因?yàn)榇藬?shù)據(jù)集數(shù)據(jù)量大，可以有效看出單機(jī)SVM算法、Cascade SVM算法和FL-SVM算法訓(xùn)練的模型所需時(shí)間的差異，圖5展示了3種算法在不同規(guī)模的數(shù)據(jù)集上訓(xùn)練所耗費(fèi)的時(shí)間.當(dāng)數(shù)據(jù)集較小時(shí)，3種算法訓(xùn)練時(shí)間差別不是很大.隨著樣本規(guī)模增大，并行算法在集群上運(yùn)行的優(yōu)勢(shì)也就明顯，說(shuō)明在大規(guī)模數(shù)據(jù)集下訓(xùn)練支持向量的任務(wù)初始化和網(wǎng)絡(luò)開銷占整個(gè)作業(yè)運(yùn)行時(shí)間的比重小，同時(shí)并行SVM算法會(huì)將樣本隨機(jī)均勻劃分，同時(shí)分發(fā)給集群中的計(jì)算節(jié)點(diǎn)上，從而節(jié)省大量的訓(xùn)練時(shí)間.Flink的任務(wù)調(diào)度方式以及作業(yè)“流水線”的執(zhí)行等等，使得FL-SVM算法在效率上要明顯優(yōu)于Cascade SVM算法，能夠有效在大規(guī)模數(shù)據(jù)集上訓(xùn)練中減少訓(xùn)練時(shí)間并提高分類效率.

圖5 算法運(yùn)行時(shí)間對(duì)比

5.2.4 算法準(zhǔn)確率對(duì)比

為了驗(yàn)證改進(jìn)后的FL-SVM算法模型的準(zhǔn)確率，本次實(shí)驗(yàn)采用a9a和covtype.binary數(shù)據(jù)集進(jìn)行驗(yàn)證實(shí)驗(yàn)，使用單機(jī)SVM算法、Cascade SVM算法和Fl-SVM算法對(duì)這兩個(gè)數(shù)據(jù)集進(jìn)行訓(xùn)練，并得到支持向量機(jī)模型，然后使用測(cè)試數(shù)據(jù)集對(duì)模型進(jìn)行評(píng)測(cè)，得到測(cè)試準(zhǔn)確率如圖6所示，從中可以看出FL-SVM算法在2個(gè)數(shù)據(jù)集的準(zhǔn)確明顯高于Cascade SVM算法但略低于單機(jī)SVM算法，且誤差范圍不超過(guò)0.01.總體而言，F(xiàn)L-SVM算法的精度損失在我們能忍受的范圍內(nèi)，同時(shí)其能有效減少訓(xùn)練時(shí)間，避免內(nèi)存溢出的等情況，所以采用FL-SVM算法處理大規(guī)模數(shù)據(jù)集是可行的.

圖6 算法的測(cè)試精確度對(duì)比

6 結(jié) 語(yǔ)

支持向量機(jī)算法從問(wèn)世至今已有20年的歷史，在大數(shù)據(jù)時(shí)代背景下的今天，傳統(tǒng)的支持向量機(jī)算法已無(wú)法高效處理大規(guī)模數(shù)據(jù)集.本文對(duì)分組層疊SVM算法的并行訓(xùn)練策略深入的研究，結(jié)合Flink計(jì)算框架，實(shí)現(xiàn)了一種基于Flink的并行SVM訓(xùn)練算法，有效克服單機(jī)SVM算法在處理大規(guī)模數(shù)據(jù)集出現(xiàn)內(nèi)存溢出，訓(xùn)練效率低，訓(xùn)練時(shí)間慢等問(wèn)題.實(shí)驗(yàn)結(jié)果表明FL-SVM算法在保證一定的準(zhǔn)確率的情況下，能大幅度提高訓(xùn)練速度，是SVM算法解決大規(guī)模數(shù)據(jù)集的一種有效的解決方案.

以后的工作中重點(diǎn)著手于Flink平臺(tái)的性能優(yōu)化，以及實(shí)時(shí)機(jī)器學(xué)習(xí)等方面，將支持向量機(jī)算法結(jié)合Flink實(shí)時(shí)計(jì)算的低延遲、高吞吐、高性能的優(yōu)勢(shì)，達(dá)到線下訓(xùn)練模型，線上實(shí)時(shí)預(yù)測(cè)模型.同時(shí)，也會(huì)深入研究Flink平臺(tái)的參數(shù)調(diào)優(yōu)，以達(dá)到更好的訓(xùn)練效果目的.