基于Relief和BFO的并行支持向量機算法

摘 要： "針對大數據環境下并行支持向量機（SVM）算法存在冗余數據敏感、參數選取困難、并行化效率低等問題，提出了一種基于Relief和BFO算法的并行SVM 算法RBFO-PSVM。首先，基于互信息和Relief算法設計了一種特征權值計算策略MI-Relief，剔除數據集中的冗余特征，有效地降低了冗余數據對并行SVM分類的干擾；接著，提出了基于MapReduce的MR-HBFO算法，并行選取SVM的最優參數，提高SVM的參數尋優能力；最后，提出核聚類策略KCS，減小參與并行化訓練的數據集規模，并提出改進CSVM反饋機制的交叉融合級聯式并行支持向量機CFCPSVM，結合MapReduce編程框架并行訓練SVM，提高了并行SVM的并行化效率。實驗表明， RBFO-PSVM算法對大型數據集的分類效果更佳，更適用于大數據環境。

關鍵詞： "SVM算法； MapReduce； CFCPSVM模型； MI-Relief策略； MR-HBFO算法

中圖分類號： "TP311 """文獻標志碼： A

文章編號： "1001-3695（2022）02-021-0447-09

doi：10.19734/j.issn.1001-3695.2021.08.0314

Parallel SVM algorithm based on Relief and "bacterial foraging optimization algorithm

Hu Jian1，2， Wang Xiangtai1， Mao Yimin1， Liu Wei2

（1.School of Information Engineering， Jiangxi University of Science amp; Technology， Ganzhou Jiangxi 341000， China； 2.Dept. of Information Engineering， Gannan University of Science amp; Technology， Ganzhou Jiangxi 341000， China）

Abstract： "Aiming at the problems of parallel support vector machine（SVM） algorithm in big data environment such as redundant data sensitivity，difficulty in parameter selection，and low parallelization efficiency，this paper proposed a parallel SVM algorithm using Relief and bacterial foraging optimization（BFO） algorithm based on MapReduce（RBFO-PSVM）.Firstly，the algorithm designed a feature weight calculation strategy（MI-Relief），which used mutual information to improve the weight calculation function of Relief algorithm to eliminate redundant features in the data set and effectively reduce redundant data to support parallelism.Secondly，this paper proposed a hybrid BFO algorithm based on MapReduce（MR-HBFO），which selected the optimal parameters of SVM in parallel，and solved the problem of difficult selection of SVM parameters.Finally，it proposed the kernel clustering strategy（KCS） to reduce the size of the data set involved in parallel training，and proposed a cross-fusion cascaded parallel SVM（CFCPSVM） to improve the cascade SVM（CSVM） feedback mechanism.

It

trained SVM by combining with the MapReduce programming framework，and this improved the parallelization efficiency of parallel SVM.Experiments show that the RBFO-PSVM algorithm has a better classification effect on large data sets and is more suitable for large data environments.

Key words： "SVM algorithm； MapReduce； CFCPSVM model； MI-Relief strategy； MR-HBFO algorithm

0 引言

隨著信息技術的迅速發展，大數據在互聯網、社交網絡以及物聯網等領域得到了廣泛的應用。相較于傳統數據，大數據具有類型多樣、數據規模大、流速快和價值密度低等特征，使得傳統的分類算法難以處理。近年來，并行化技術的發展為大數據的處理提供了一個新的視野，而SVM作為一種基于結構風險最小化實現的分類算法，具有強大的泛化能力和較好的魯棒性［1］，被廣泛應用于圖像識別［2］、文本分類［3］、生物醫學［4］、人臉識別［5］、股票預測［6］等領域。因此，基于大數據的并行SVM算法已經成為當前并行分類算法的研究熱點。

MapReduce是Google公司提出的一種處理海量數據的分布式并行運算框架［7］，具有操作簡單、成本低廉、負載均衡以及系統擴展性強等優點，目前已被廣泛應用于大數據分析和處理領域。基于此，研究人員設計將SVM遷移到MapReduce框架［8］，開發出適用于大數據環境下的并行SVM。例如文獻［9，10］提出的基于MapReduce的并行SVM模型，都在一定程度上提高了并行SVM處理大型數據集的能力。然而隨著數據復雜性和多樣性的增加，不相關的冗余數據會嚴重影響并行SVM的分類準確度。為了有效地識別并刪除數據集中的冗余數據，Cao等人［11］提出了基于MapReduce和自適應特征權值更新的SVM算法（PAFWU-SVM），該算法每次從初始特征空間中選擇多個特征，并隨機自適應融合，融合后的特征在一定程度上減小了冗余數據對SVM分類的影響；然而該算法改變了初始特征空間分布，忽略了弱相關特征對分類的影響。為了從原始特征空間中更加準確地識別冗余數據，Zhang等人［12］提出了基于Relief和混合核函數的SVM算法，利用Relief進行特征選擇，通過計算每個特征的相關統計量之和來評估特征子集的重要性，根據特征權值來衡量特征區分類別的能力。該算法有效地降低了冗余數據對SVM性能的干擾，但在計算特征權值時沒有考慮特征之間的冗余性對分類的不利影響，導致算法的分類準確度降低。

雖然降低冗余數據的干擾能夠有效地提高并行SVM算法的分類準確率， 但是參數的選取對并行SVM的影響同樣不容忽視。近年來，群智能算法憑借著尋優速度快、并行處理能力強和全局尋優等優勢［13］，被眾多研究者應用于并行SVM的參數尋優問題中。Hu等人［9］提出了基于杜鵑搜索（cuckoo search，CS）的并行SVM算法，CS算法設置了萊維隨機搜索路徑和基于萊維分布的搜索步長，再利用CS和十折交叉驗證來選取SVM的最優參數。滿蔚仕等人［14］提出了基于MapReduce和NPP-PSO的分布式SVM算法，在Hadoop平臺上實現了NPP-PSO，將數據集劃分成多個子集，并在map端對每個子集使用粒子群優化算法并行尋優，在reduce端提取子集中的最佳適應度粒子，從而得到適用于整個數據集的SVM最優參數。以上算法都在一定程度上提高了并行SVM選取最優參數的能力，但也存在尋優過程復雜、易陷入局部最優等問題。

在處理大型數據集時參數的選取嚴重影響并行SVM的分類性能，然而并行化效率的提高對并行SVM性能的影響同樣巨大。為了提高并行SVM對大型數據集的并行處理能力，Jadhav等人［15］提出了基于MapReduce框架的級聯式并行SVM（MR-PSVM）算法，將級聯式SVM遷移到MapReduce框架上，使用map函數分層訓練SVM，在reduce函數中將SVM訓練得到的子集兩兩合并輸入下一層，在最后一層得到全局SVM模型。該算法充分利用MapReduce框架的并行優勢，有效地提高了SVM的并行化效率，然而這種并行化結構的反饋機制耗時較長，不利于二次迭代訓練。為了改進耗時的反饋機制，Zhang等人［16］提出了一種改進的級聯式并行SVM模型，該模型通過比較第二層訓練得到的支持向量集的變化來判斷并行SVM是否收斂到全局最優，減少了反饋機制的耗時，有效地提高了并行SVM的并行化效率，然而模型中反饋的數據融合過程計算量較大，所需內存較多。

盡管上述算法取得了一定成就，但也暴露了算法在其他方面的不足。因此，如何設計有效且合理的冗余數據刪減策略，如何簡化尋優過程、提高并行SVM的參數尋優能力，如何合理地利用計算機資源提高并行SVM的并行化效率仍是亟待解決的問題。針對以上三個問題，本文提出了基于Relief和BFO的并行SVM算法RBFO-PSVM。該算法的主要思想包括：a）提出了基于互信息和Relief算法的特征權值計算策略MI-Relief，刪減冗余數據，降低冗余數據對并行SVM的干擾；b）提出了基于MapReduce的MR-HBFO算法，實現并行參數尋優，提高了并行SVM的參數尋優能力；c）提出了縮減數據集和改進CSVM反饋機制的CFCPSVM，并基于MapReduce構建CFCPSVM模型，提高了算法的并行化效率。

1 相關概念及算法介紹

1.1 相關概念

定義1 "互信息。互信息［17］用于計算一個隨機變量中包含的關于另一個隨機變量的信息量。假設兩個隨機變量 X和Y，p（x）和p（y） 分別是 X 和 Y 的概率密度， p（x，y） 為聯合概率密度，則互信息MI （X；Y） 可以定義為

MI （X；Y）=∑ x∈X ∑ y∈Y p（x，y） log "2 p（x，y） p（x）p（y） """（1）

定義2 "核平方歐氏距離。核平方歐氏距離［18］用于計算兩個向量在再生希爾伯特空間中的歐氏距離。假設 Φ 是一個從低維的輸入空間 X 到高維的空間的 "Euclid Math OneHAp

映射且存在核函數 K（x i，x j） ，對于任意 x i，x j∈X ，都有 K（x i，x j）=Φ（x i）·Φ（x j） ，則核平方歐氏距離可以定義為

‖Φ（x i）-Φ（x j）‖2=K（x i，x i）-2K（x i，x j）+K（x j，x j） ""（2）

1.2 相關算法

1.2.1 Relief算法

Relief算法是一種基于樣本學習的多變量過濾式特征選擇算法［19］。設有訓練數據集 D={x i，y i}N i=1 ，樣本 i 為 x i={x i1，x i2，…，x iF} ， y i∈{+1，-1} 。兩個樣本在第 i 維上的差異可用絕對誤差距離表示，算法每次從樣本集合中隨機選取樣本 x n（1≤n≤N） ；從 C={c 1，c 2} 中各選擇一個距離 x n 最近的同類樣本NH （x n） 和異類樣本NM （x n） ，則特征 t∈F 的權值更新公式為

w t=w t+ 1 r "diff （xt n ，NM t（x n））- 1 r "diff （xt n ，NH t（x n） ""（3）

其中： rgt;1 表示上述過程的迭代次數。可知，無論特征是何種類型，diff （x 1，x 2）都屬于［0，1］，式（5）迭代r次后0≤w t≤1 。

1.2.2 細菌覓食優化算法

細菌覓食優化算法（bacterial foraging optimization，BFO）［20］是通過模擬細菌覓食行為而提出的一種仿生類優化算法，該算法主要模擬細菌的趨化操作、復制操作和遷徙操作來進行尋優。設細菌初始種群大小為 S ，細菌 i表示為θi={θi 1，θi 2，…，θi D} ，其中D 表示參數維數， θi（j，k，l） 表示細菌 i 完成第 j 次趨化、第 k 次復制和第 l 次遷徙操作后的位置，細菌的尋優操作如下：

a）趨化操作，包括翻轉和游動兩個基本動作。設 C（i） 為細菌 i 的游動步長， Δ （i） 表示隨機方向上的單位向量。細菌 i 的趨化操作可以表示為

θi（j+1，k，l）=θi（j，k，l）+C（i） "Δ （i） ""Δ T （i） Δ （i） """"（4）

b）復制操作。將細菌按照適應度均值降序排序，淘汰后半部分細菌，復制前半部分細菌，新復制的細菌將繼承母體細菌的位置和步長。

c）遷徙操作。設細菌遷徙操作的執行概率為 p ed ， r∈［0，1］ ，細菌 i 執行遷徙操作的公式為

P i（j，k，l）= "P i（j，k，l） "r gt; p ed

（m′ 1，m′ 2，…，m′ D） "r lt; p ed """"（5）

1.2.3 級聯式支持向量機

級聯式支持向量機（CSVM）［21］將原問題分解成多個相互獨立的子問題，分層優化子問題，直到最后一層融合成原問題的最優解。具體操作步驟如下：a）將原數據集劃分成多個相互獨立的子集；b）使用SMO（sequential minimal optimization）算法［22］并行訓練各子集；c）將上層訓練得到的支持向量兩兩融合輸入下一層，重復步驟b）c）直到只剩下一個數據集；d）構造SVM分類器并反饋到第一層；e）將第一層各子集中不滿足KKT條件的樣本與最后一層的數據集合并用于下次迭代，直到模型滿足精度要求，迭代停止。CSVM的結構如圖1所示。

2 RBFO-PSVM算法

2.1 算法思想

本文提出的RBFO-MRSVM算法主要包含三個階段：a）冗余數據刪減，提出MI-Relief策略改進Relief算法的權重判定函數，降低冗余數據對并行SVM的干擾；b）并行SVM參數尋優，基于MapReduce框架并行訓練局部SVM，并提出自適應翻轉方向和游動步長的MR-HBFO算法，利用MR-HBFO算法對SVM進行參數尋優，提高SVM的參數尋優能力；c）并行SVM模型構建，提出基于簡化核空間距離的KCS策略以減小參與訓練的數據集規模，通過改進CSVM的反饋機制得到CFCPSVM模型，并基于MapReduce構建CFCPSVM模型，得到全局并行SVM模型。

2.2 冗余數據刪減

當前大數據環境下的并行SVM算法存在冗余數據干擾算法決策面構造的問題，如果讓冗余數據參與訓練，將會使得決策面偏離最大間隔平面中心，從而降低算法的分類準確度。為了解決此問題，本文提出了MI-Relief策略來識別并刪除冗余數據，MI-Relief策略的主要實現過程如下：

a）數據集劃分。使用MapReduce自帶的數據集劃分策略對原數據集進行劃分，得到數據塊 chunk 1，chunk 2，…，chunk h 。

b）特征權值計算。利用Relief算法從特征中選擇一個樣本，根據樣本與同類、異類近鄰樣本的絕對誤差距離計算特征權值，迭代 r 次后得到該特征的初始權值。全部特征計算完初始權值后得到按權值降序排序的特征集合 M={m 1，m 2，…，m n} ，權值降序排序為 w 1m 1gt;w 2m 2gt;…gt;w nm n 。

c）特征冗余度計算。Relief計算得到的特征權值只能度量特征區分類別的能力，未考慮特征之間的冗余度對分類的影響。為了降低高冗余度特征的權值，提出基于互信息的特征冗余度度量公式FMI將特征按權值降序排序，從初始權值最大的特征開始，依次計算特征冗余度，并將計算完冗余度的特征加入到特征集合 S 中。

定理1 "特征冗余度度量［23］公式FMI。假設計算完冗余度的特征為 m′ j∈S ，初始化 S={m 1} ，則未計算冗余度的特征集合 S′=M-S ，特征 m i∈S′ 關于特征子集 S 的冗余度可以表示為

R i=∑ m′ j∈S "MI （m i;m′ j） ""（6）

d）特征權值更新。通過Relief算法計算特征的初始權值，接著使用特征冗余度度量公式FMI計算特征冗余度，為了降低冗余度高的特征的初始權值，提出特征權值更新公式FWU重新計算特征權值。將計算好權值的特征降序排序，取前 k 個特征 F′ 組成的數據集用于后續工作。

定理2 "特征權值更新公式FWU。已知Relief算法計算得到特征 m i 的權值大小為 w im i ， R i 表示特征 m i 的冗余度，令 w′ i 表示特征 m i 更新之后的權值，則使用特征權值更新公式FWU重新定義的特征權值可以表示為

w′ i=w im i-R i/ ∑ n t=1 R2 t """（7）

證明 "根據式（5）權值的計算公式可知0≤［diff （xt n， NM t（x n）） -diff （xt n， NH t（x n））］≤1，迭代r次后∑ r i = 1 "1 r ［ diff （xt n， NM t（x n））- diff （xt n ，NH t（x n））］≤1，即初始權重w t∈［0，1］。特征的冗余度R i，利用歸一化思想轉換為R i/ ∑ n t=1 R2 t ，因為 ∑ n t=1 R2 t ≥R i，所以R i/ ∑ n t=1 R2 t ∈［0，1］，又因為歸一化后與w im i 具有相同的值域，即特征之間的冗余度會對特征的初始權值產生顯著影響，所以可以利用式（9）來重新度量特征的重要性。證畢。

使用MI-Relief策略刪減冗余數據的偽代碼如算法1所示。

算法1 冗余數據刪減

輸入：原始數據集標簽 C={c 1，c 2} ；原始數據集特征集合為 F={f 1，f 2，…，f n} 。

輸出：去除噪聲后的特征集合為 F′={f′ 1，f′ 2，…，f′ n} 。

split（）； //數據集劃分

for each data chunk

map（）；

for each "f i∈F "do

calculate "w t "by Eq（3）； //計算初始特征權值

sort feature by "w t "descending order；

end for

for each "m i∈M "do

calculate "R i "by Eq（6）； //計算特征冗余度

calculate "w′ i "by Eq（7）； //更新特征權值

sort feature by "w′ i "descending order；

end for

return the first "k "features to get "F′

2.3 并行SVM參數尋優

目前，基于群智能優化的并行SVM算法在模型訓練的過程中使用群智能算法選取合適的參數，能夠明顯提高并行SVM算法的分類性能。BFO算法作為群智能算法的一員， 具有并行搜索和易跳出局部最優的特點，然而在大型數據集的尋優過程中，BFO算法存在后期收斂乏力、尋優精度不高、多樣性不足和尋優效率低等問題。為了解決這些問題，提高并行SVM算法的參數尋優能力，本文提出了基于MapReduce的MR-HBFO算法進行并行參數尋優，MR-HBFO算法具體過程如下：

a）參數更新。在參數更新模塊中，啟動MapReduce作業更新參數值，map函數接收帶有標志的細菌，此時形成的鍵值對為 〈bacterialID，bacterial〉，其中，bacterialID表示細菌ID；bacterial表示細菌個體包含的參數信息，包括參數向量 B =（C，γ）（C表示懲罰系數，γ表示RBF核函數參數），趨化次數N c，復制次數N re，遷徙次數N ed，游動步長ss，翻轉方向Φ（j），遷徙概率p ed，個體最優參數P local，全局最優參數P global。其他系數如c 1、c 2和r 1、r 2 等，由用戶自行配置。在map函數中，為了解決尋優算法后期收斂乏力的問題，提出了自適應步長公式ASS更新細菌的尋優步長。

定理3 "自適應步長［24］公式ASS。已知 N re 是最大復制迭代次數， SS max 和 SS min 分別是細菌的最大和最小游動步長， n re 為細菌 i 當前復制操作的迭代次數，則MR-HBFO算法中自適應步長公式ASS可表示為

SS′ i=（SS max-SS min）× N re-n re N re +SS min ""（8）

同時為了解決尋優算法尋優精度不高的問題，提出了交互式翻轉公式IF更新細菌的尋優方向。

定理4 "交互式翻轉公式IF。假設 Δ "rand 表示任意翻轉方向， c 1 是細菌 i 趨向個體最優解的速率， c 2 是細菌 i 趨向全體最優解的調整率， r 1 和 r 2 是0～1的隨機數， θ pbest 是個體最優解， θ gbest 是全局最優值， N c 為最大趨化次數， n c 為當前趨化次數， θ i 表示細菌當前位置，則翻轉公式AT可表示為

Δ "t+1（i）=α Δ "rand+（1-α）［c 1r 1（θ pbest-θ i）+c 2r 2（θ gbest-θ i）］

α=（N c-n c）/N c

θi（j+1，k，l）=θi（j，k，l）+SS′ i× "Δ （i） ""Δ T（ i） Δ （i） """"（9）

證明 "由于 Δ （i）方向向量受 Δ "rand 和 c 1r 1（θ pbest-θ i）+c 2r 2（θ gbest-θ i） 兩部分控制，所以 Δ （i） 表示的方向是隨 α 的減小而變化的， α 控制細菌在尋優初期的翻轉方向以隨機產生為主，隨著趨化次數的增加 α 逐漸減小，細菌的翻轉方向主要由自我認知部分 c 1r 1（θ pbest-θ i） 和群體交互部分 c 2r 2（θ gbest-θ i） 決定，利用 Δ （i）/ "Δ T （i） Δ （i） "將翻轉方向歸一化成單位向量，控制細菌的趨化方向。證畢。

參數更新之后，map函數將參數更新后的細菌輸出到reduce函數。第一個模塊中的reduce函數用于對map的輸出進行排序，并將所有結果合并到一個輸出文件中；此外，將菌群保存在分布式文件系統中，以供其他兩個模塊調用。

細菌參數更新的map和reduce函數的偽代碼如算法2所示。

算法2 細菌參數更新

輸入： N c，N re，N ed，ss，p ed，P local，P global 。

輸出： newΦ，newss，newb 。

function map（key： bacterialID ，value： bacterial ）

initialization：

bacterialID=key ；

bacterial=value ；

//extract the information from the bacterial

extract_Info（ n c，n re，n ed，ss，p ed，P local，P global ）；

generate random number "r 1 "and "r 2 ；

for each "b i "in "B "do

//update bacterial swimming step and flip direction

for each "j "in "Dimension "do

calculate "newΦ（j） "by Eq（9）

calculate "newss j "by Eq（8）

end for

update（ bacterial ， newΦ（i） ， newss i ）；

end for

emit（ bacterialID，bacterial ）；

end function

function reduce（ key：bacterialID，ValList：bacterial ）

for each "Value "in "ValList nbsp;do

emit（ key，value ）；

end for

end function

b）并行尋優。在并行尋優模塊中啟動MapReduce作業，map函數先從分布式緩存中取得菌群數據，提取每個細菌的參數向量；接著細菌執行趨化、復制和遷徙操作，為了更準確地篩選精英細菌，提出方差復制公式FVV度量細菌的尋優能力，解決了尋優算法多樣性不足的問題。

定理5 "方差復制［25］公式FVV。已知尋優參數的維度為 d ，令 X（i，j，m） 表示細菌 i 在第 j 次趨化操作后第 m 維適應度的值， ""m 表示當前趨化次數中第 m 維的平均值，則細菌個體 i 的適應度值方差可以表示為

FVV（i）=∑ N c j=1 ""1 d ×∑ d m=1 ［X（i，j，m）- "m］2 """（10）

隨后計算更新后的菌群的適應度。在計算細菌適應度的過程中，使用當前參數訓練SVM分類器，并為每個樣本添加一個標記屬性，用于標記該樣本是否是候選SV（support vector）或非支持向量；再用測試集測試分類器得到正確分類的樣本數。為了更加準確地度量細菌適應度、加快算法收斂速度，提出了適應度度量公式ASV。

定理6 "適應度度量［24］公式ASV。假設使用當前參數構建SVM分類器訓練得到正確分類的樣本數 S R ，支持向量個數 S sv 。若訓練集樣本數為 S ，權衡系數為 λ ，則細菌當前的適應度可表示為

fitness=λ× S R S +（1-λ）×（1- S sv S ） ""（11）

最后，輸出鍵值對 〈fitnessID，pfValue〉 ，其中， fitnessID 表示參數對應的適應度， pfValue 表示參數值和樣本的標記屬性。map函數將新的鍵值對發送給reduce函數；reduce函數整理相同 fitnessID 的 pfvalue 值，按照適應度大小在分布式文件系統中降序排序。

并行參數尋優的map和reduce函數的偽代碼如算法3所示。

算法3 并行參數尋優

輸入：path of HDFS。

輸出：鍵值對 ［fitnessID，pfValue］ 。

function map（key： fitnessID ，value： pfValue ）

initialization：

fitnessID=key ；

pfValue=value ；

//read the bacterial swarm from distributed cache

read（ Swarm ）;

for each "bacterial "in "swarm "do

for （ n ed=1 ; n ed≤N ed ; n ed+ + ） //遷徙循環

for （ n re=1 ; n re≤N re ; n re+ + ） //復制循環

for （ n c=1 ; n c≤N c；n c+ + ） //趨化循環

chemotaxis（ bacterial ）； //執行趨化操作

end for

train SVM classifier；

calculate_fitness（ f C，γ ） by Eq（11）； //計算適應度

mark candidate support vector and non-support vector； /*標記候選SV和非支持向量*/

end for

descending_sort（ swarm ）； //按適應度方差降序排序

reproduction（ swarm ） by Eq（10）； //執行復制操作

end for

elimination_dispersion（ swarm ）； //執行遷徙操作

newKey=fitnessID ；

newValue=pfValue ；

end for

end function

function reduce（ key：fitnessID ， ValList：pfValue ）

initialization：

for each "value "in "ValList

maxFitness=extractmaxFitness ；

count=count+1 ；

end for

emit（ key，（optimalParameter，MarkingF） ）；

//輸出各數據塊的最優參數和標記屬性

c）數據合并。MR-HBFO算法在參數更新模塊初始化菌群和更新參數并將參數提供給并行尋優模塊；并行尋優模塊負責算法的尋優操作，控制細菌依次執行趨化循環、復制循環和遷徙循環，并在每次跳出趨化循環時計算細菌的適應度值。數據合并模塊的主要任務是整理參數更新模塊和并行尋優模塊的輸出，通過比較適應度值得到最大適應度值對應的最優參數。新的適應度函數值由并行尋優模塊計算得到，并與個體最優適應度值比較，若大于個體最優，則更新個體最優；若有個體最優適應度大于全局最優，則更新全局最優適應度值。最后，更新參數信息并保存在分布式文件系統中，用于下次迭代尋優。尋優達到最大迭代次數時尋優算法終止，輸出SVM的最優參數和標記屬性。

2.4 并行SVM模型構建

當前大數據環境下基于并行SVM的分類算法中，大多是將原始數據集分割成多個小數據集，然后在各個小數據集上并行訓練SVM，層層迭代之后形成級聯式并行SVM結構，這種結構在一定程度上提高了SVM處理大型數據集的能力。然而，級聯式并行SVM結構的反饋機制耗時較長，且節點個數會隨著數據集規模的增加而增加，造成分類準確度的損失。為了提高并行SVM的并行化效率和減小參與訓練的數據規模，提出了基于MapReduce的CFCPSVM模型。該模型的構建過程如下所示，并在圖2中給出了總體的運行流程。

a）數據集縮減。SVM模型的構建依賴于被稱為支持向量的部分訓練數據集，為了減小算法訓練非支持向量耗費的時間，在并行化訓練之前使用KCS策略刪除大部分非支持向量、獲取候選SV，KCS策略具體過程描述如下：

（a）刪除部分非支持向量。并行參數尋優階段，計算細菌適應度時需要訓練多個局部SVM分類器，由于非支持向量都是距離決策平面較遠的向量，能夠被多個局部SVM分類器正確分類。因此，將尋優期間被 g 個及以上分類器標記為非支持向量的數據刪除。

（b）獲取候選SV集。并行參數尋優期間使用的支持向量都是距離決策平面較近的向量，盡管此時的決策平面不是最優決策平面，但是支持向量都是距離最優決策平面較近的向量。因此，選擇尋優期間得到的支持向量為候選SV。

（c）計算高維空間向量距離。每個候選SV作為一個質心，將候選SV按照類別分成正反兩類，分別使用核空間距離簡化度量公式KSD計算所有正類樣本到正類質心和負類樣本到負類質心的簡化核空間距離。

定理7 "核空間距離簡化度量公式KSD。假設兩個向量間的簡化核空間距離為 d ksd ，原特征空間為 Rn ，則對于向量 x "i和 x "j ，使用映射函數 Φ 變換后的向量為 Φ（x "i）和 Φ（x "j） ，兩向量在高維空間中的距離可利用RBF核函數度量，于是核空間距離簡化度量公式可表示為

‖ Φ（x "i）- Φ（x "j）‖2d ksd=‖ x "i- x "j‖ ""（12）

證明 "由式（2）可知‖ Φ（x "i）- Φ（x "j）‖2=K（ x "i， x "i）-2K（ x "i， x "j）+K（ x "j， x "j）=2（1-K（ x "i， x "j）） ，式中 K（ x "i， x "j）= exp （-β‖ x "i- x "j‖2） ，代入得‖ Φ（x "i）- Φ（x "j）‖2=2（1- "exp （-β‖ x "i- x "j‖2）） ，可知‖ Φ（x "i）- Φ（x "j）‖2 與 ‖x i-x j‖ 成正比，考慮到計算向量核空間距離的目的是為了比較各向量到候選SV的距離大小，而不是計算具體的值，所以用簡化核空間距離 d ksd 代替核平方歐氏距離‖ Φ（x "i）- Φ（x "j）‖2 比較大小。兩向量間 d ksd 越大，核平方歐氏距離 ‖Φ（x i）-Φ（x j）‖2 越大。證畢。

（d）獲取訓練數據集。設置合適的聚類半徑 r ，若向量到質心的簡化核空間距離小于 r ，則將該向量標記為候選向量。合并候選SV集和候選向量集構成并行SVM模型的訓練數據集，經過數據集縮減得到規模減小的訓練數據集。

b）CFCPSVM模型構建。標準級聯式SVM的反饋機制是利用最后一層得到的SVM模型對第一層中各子集進行KKT條件判斷，這是相當耗時的一個過程，而CFCPSVM模型的反饋機制是通過比較第二層的支持向量集的差異來判斷訓練效果。這里將候選SV集劃分成四個數據塊 CSV 1、CSV 2、CSV 3、CSV 4 ，則CFCPSVM模型的運行過程如下，圖3給出了CFCPSVM的結構。

（a）使用SMO算法并行訓練數據集 CSV 1、CSV 2、CSV 3、CSV 4 ，輸出第一層的支持向量集 SV 1、SV 2、SV 3、SV 4 ；

（b）分別融合 SV 1 和 SV 2 、 SV 3 和 SV 4 作為第二層的輸入；

（c）訓練上一層輸出的兩個數據集，得到支持向量集 SV 5、SV 6 ；

（d）將 SV 1 分別與 CSV 3 、 CSV 4 融合， SV 2 分別與 CSV 3 、 CSV 4 融合， SV 3 分別與 CSV 1 、 CSV 2 融合， SV 4 分別與 CSV 1 、 CSV 2 融合，作為第一層下一次訓練的輸入；

（e）重復步驟（a）～（c）得到第二層第二次輸出的支持向量集 SV′ 5、SV′ 6 ；

（f）如果滿足以下三個條件之一： SV 5-SV′ 5=和SV 6-SV′ 6=；多次迭代發現SV 5-SV′ 5和SV 6-SV′ 6是兩個不變的集合；SV 5-SV′ 5和SV 6-SV′ 6 兩個集合中的樣本數小于某個特定的值 e 。則停止迭代過程，并融合 SV′ 5、SV′ 6 作為最后一層的輸入，訓練最后一層得到 SV 7 ，用 SV 7 構造SVM決策函數，如果不滿足上述三個條件，則返回步驟a）。

c）CFCPSVM模型并行化。在并行SVM模型構建過程中，首先提出了KCS策略預處理數據集，得到規模減小的訓練數據集；接著提出了改進反饋機制的CFCPSVM模型，減小了反饋的耗時；為了進一步提高CFCPSVM的并行化效率，將CFCPSVM模型的運行過程布置在MapReduce編程模型上。基于MapReduce的CFCPSVM模型的具體操作步驟如下：將數據集 D 劃分成 n 個數據塊，數據塊保存在計算單元中； Map-ReduceDriver在每個節點上啟動MapReduce作業，在每個計算單元中執行map操作，將每個mapper訓練得到的支持向量發送到reducer執行reduce操作；在reduce階段，所有map操作得到的支持向量都被分組發送給用戶，重復訓練過程，直到所有子SVM合并到一個SVM中為止。map和reduce階段執行的操作如下所示。

a）map階段。在不滿足迭代終止條件時，mapper在其對應的數據集塊中使用SMO算法過濾非支持向量，得到的支持向量與其他數據塊合并，map函數的輸出是局部空間數據塊的支持向量數量。

b）reduce階段。在不滿足迭代終止條件時，將局部支持向量兩兩合并作為下一層訓練的輸入，節點支持向量與全局支持向量合并來計算全局權重支持向量。

基于MapReduce的CFCPSVM并行化訓練的偽代碼如算法4所示。

算法4 并行化訓練

輸入：path of datasets。

輸出：global support vector。

initialize data blocks；//劃分數據集

map（ key ， value ）

SVglobal= ；

while "hi≠hi-1 "do //第 i 次迭代不滿足迭代終止條件

for each node "nc i "in "NC "do /* NC 是Hadoop集群中總的節點個數 NC=nc 1，nc 2，…，nc n */

Di nc←Di nc∪SV nc； /*將節點nc 的子集與節點 nc 中的支持向量合并*/

end for

end while

reduce（ key ， value ）

while "hi≠hi-1 "do

for each node "nc i "in "NC "do

SV nc=binary "sum （D nc） ； //兩個節點的子集合并

end for

for each node "nc i "in "NC "do

SV global=SV global∪SV nc ； //節點支持向量與全局支持向量合并

end for

end while

return "SV global

2.5 算法時間復雜度分析

本文RBFO-PSVM算法的時間復雜度主要由冗余數據刪減、并行SVM參數尋優以及并行SVM模型構建三部分組成，各階段的時間復雜度是：

冗余數據刪減階段的時間復雜度包括計算每個特征的絕對誤差距離和利用互信息計算冗余度的時間。令原始數據集中的樣本數為 n ，特征數為 d ，則該階段的時間復雜度為

T 1=O（nd+d） ""（13）

并行SVM參數尋優階段，令MapReduce分布式集群的mapper節點個數為 M ，細菌個數為 b ，每次迭代進行并行參數尋優時要對所有數據塊進行處理，則該階段的時間復雜度為

T 2=O（（ n M ）2+b） ""（14）

并行SVM構建階段主要由數據集縮減以及使用SMO算法并行訓練SVM的時間組成，令支持向量的個數為 N sv ，MapReduce分布式集群的mapper節點數為 L ，且 N sv/nlt; lt;1 ，則該階段的時間復雜度為

T 3=O（（ N sv L ）2+ N svdn L +N sv） ""（15）

綜上可知，對于RBFO-PSVM算法，其總的時間復雜度為 T=（n×d+d+（ n M ）2+b+（ N sv L ）2+ N sv×d×n L +N sv），其中（ N sv L ）2lt; lt;（ n M ）2，T≤3 ， dlt; lt;nd且N svlt; lt;nd ， Llt; lt;N sv ，所以最終的時間復雜度近似為

T RBFO-PSVM=O（（ n M ）2+ N sv×n×d L ） ""（16）

對于PAFWU-SVM［11］算法，先進行特征提取、特征歸一化和自適應融合特征處理，該階段的時間復雜度為 O（nd2） ；接著訓練并行SVM，將數據集劃分成多個訓練集和測試集，map階段用訓練集訓練支持向量機，然后用測試集得到每個SVM模型的準確率；reduce階段把SVM模型按其準確率排序，得到最優SVM模型，令mapper節點數為 K ，測試集樣本數為 S ，該部分的時間復雜度為 O（（n/K）2+S） ，則PAFWU-SVM的時間復雜度為 O（nd2+（n/K）2+S） 。

對于MR-PSVM［15］算法，首先將數據集劃分成多個子數據集，在子數據集上并行訓練支持向量機，將第一層訓練得到的支持向量與其他子數據集合并，通過比較第二層訓練得到的支持向量集的變化判斷是否收斂到全局最優。令劃分后子數據集的個數為 H ，則MR-PSVM的時間復雜度為 O（（n/H）2+nN svd） 。

對于RBFO-PSVM算法，由于 N sv≤dL ，所以 N svnd/Llt;Lnd2+SL/L ，于是有 T RBFO-PSVMlt;O（（n/K）2+nd2+S） ，而且 T RBFO-PSVMlt;O（（n/H）2+N svnd） 。因此相較于PAFWU-SVM、MR-PSVM，RBFO-PSVM算法有著更為理想的時間復雜度。

3 實驗結果及比較

3.1 實驗環境

為了驗證RBFO-PSVM算法的性能，本文設計了相關實驗。實驗硬件配置為主從結構的分布式集群，包含一個master節點，四個slaver節點。所有節點的硬件配置均為Intel Core i9-9900K八核處理器、16 GB內存、2 TB固態硬盤，節點間通過500 Mbps的以太網連接。軟件配置則統一安裝Ubuntu 16操作系統、2.7.5版本的Hadoop計算平臺以及JDK 1.8版本的Java環境。各個節點的具體配置如表1所示。

3.2 實驗數據

本文實驗部分所用數據為四個真實的數據集，分別是Bitcoin-Heist［26］、Covertype［26］、Census-Income［26］和GitHub MUSAE［26］。 BitcoinHeist是一個記錄比特幣勒索軟件地址的數據庫，該數據集包含2 916 697條樣本，共有10種屬性，具有樣本量較大，屬性較少的特點；Covertype是一個森林覆蓋類型的數據庫，該數據集包含581 012條樣本， 共有54種屬性，具有樣本量適中，屬性適中的特點；Census-Income是從美國當前人口調查中提取的加權人口普查數據，數據集包含299 285條樣本，共有40種屬性，具有樣本量適中，屬性適中的特點；GitHub MUSAE是從GitHub用戶的社交網絡中收集到的數據庫，該數據集包含37 700條樣本，共有4 906種屬性，具有樣本量較少，屬性較多的特點。這些數據集的詳細信息如表2所示。

4 906 2 2 2 2

3.3 評價指標

1）加速比 為了確定并行SVM并行處理數據的效率，本文選用加速比作為評價算法并行化效率的指標，加速比用來衡量算法通過并行計算降低總體運行時間而獲得的性能提升，其定義為

S n=T 1/T n ""（17）

其中： T 1 表示算法在單個節點上的運行時間； T n 表示算法在 n 個節點上的運行時間； S n 表示最終加速比， S n 越大說明算法的并行化效率越高。

2） F -measure "F -measure是衡量算法分類準確率的一種評價指標，該指標利用準確率（precision）和召回率（recall）來評價分類結果，其定義為

F-measure= （β2+1）precision×recall β2precision+recall """（18）

其中：參數 β 設置為1。 F -measure的值越高，表示分類效果越好。

3）馬修斯相關系數 馬修斯相關系數（Matthews correlation coefficient，MCC）是一個能夠均衡測量二分類的分類性能的指標，即使兩類別的樣本數量差別很大，也可以用它描述實際分類與測試分類之間的相關系數，設正真例、假正例、真反例和假反例分別為 TP 、 FP 、 TN 、 FN ，MCC定義為

MCC= TP×TN-FP×FN "（TP+FP）（TP+FN）（TN+FP）（TN+FN） """"（19）

3.4 算法可行性分析

3.4.1 MR-HBFO算法可行性分析

為了驗證MR-HBFO算法的可行性，本文使用五個經典基準測試函數，對MR-HBFO、BFO［20］、粒子群優化（particle swarm optimization，PSO）算法［14］和遺傳算法（genetic algorithm，GA）［27］進行仿真對比實驗，通過測試函數的收斂情況評價MR-HBFO算法的參數尋優能力。測試函數包含連續單峰函數和非線性多峰函數，單峰函數 f 1 、 f 2 用于測試算法的精度和收斂速度，多峰函數 f 3、f 4、f 5 用于測試算法的搜索能力和跳出局部最優的能力，測試函數如表3所示。

實驗中的參數設置為：最大迭代次數 maxiter=2 000 ，種群數 S=100 ，函數維度 d=30 ， N c=100 ， N re=5N ed=4 ， p ed=0.25 ， ss=4 ， C∈［2-8，20］ ， γ∈［2-8，20］ ， c 1=1.2 ， c 2=0.5 。將四種尋優算法在五個測試函數上獨立運行50次，計算得到算法在每個函數上的最優值、平均值和標準差，其中平均值反映算法的最大精度，標準差反映算法的穩定性。表4為四種尋優算法在測試函數上的運行結果。

由表4可知，相比BFO和PSO算法，MR-HBFO算法在五種函數上的收斂精度更高且穩定性更好。在Rosenbrock函數上，BFO算法的平均值和標準差分別是2.53E+03、1.05E+04，而MR-HBFO算法運行的結果是0.21和0.13，顯然MR-HBFO算法的平均值和標準差遠小于BFO算法；在Ackley函數上，PSO算法的最優值和平均值都是3.66E-14，而MR-HBFO算法的最優值和標準差是5.37E-68。可知相比于BFO算法，MR-HBFO算法收斂更快、更準確，相比于PSO算法，MR-HBFO算法的收斂精度更高。特別是在Rastrigin函數上，相較于BFO和PSO算法，MR-HBFO算法的收斂精度有了明顯的提升，足以證明MR-HBFO算法具有更強的跳出局部最優和全局搜索的能力。這是因為MR-HBFO算法提出交互式翻轉操作，提高了收斂速度，還提出了自適應游動步長和方差復制，有效地提高了算法的穩定性。實驗表明，在全局尋優能力和算法穩定性方面，MR-HBFO算法比BFO、PSO和GA算法表現更佳。

3.4.2 RBFO-PSVM算法可行性分析

為驗證RBFO-PSVM算法在大數據環境下并行訓練SVM的可行性，將RBFO-PSVM算法分別在BitcoinHeist、Covertype、Census-Income和GitHub MUSAE數據集上獨立運行10次，取運行時間的平均值計算加速比，通過對算法加速比的分析，實現對RBFO-PSVM算法性能的總體評估。圖4為RBFO-PSVM算法在四個數據集上的運行結果。

從圖4可以看出，RBFO-PSVM算法在四種數據集上的加速比隨著節點數的增加而不斷提升。RBFO-PSVM算法在BitcoinHeist數據集上運行的加速比分別增長了0.9、1.6、2.2、3.1；在Covertype數據集上運行的加速比分別增長了0.8、1.2、1.6、2.4；在Census-Income數據集上運行的加速比分別增長了0.6、1.4、2.0、2.6；在GitHub MUSAE數據集上運行的加速比分別增長了0.4、1.0、1.3、2.1。從圖4中的數據可知，RBFO-PSVM算法在各數據集上的加速比顯著增加，即使在維度較高的GitHub MUSAE數據集上，算法的上升趨勢依然顯著，在包含噪聲數據的Census-Income數據集上，加速比的上升趨勢最好，在數據規模較大的BitcoinHeist數據集上，算法表現出了較好的伸縮性。主要是由于RBFO-PSVM算法使用MI-Relief策略，提高了Relief算法的降噪能力，利用改進CSVM的反饋機制的CFCPSVM模型，進一步提高了并行SVM的并行化效率，故該算法在大數據集下也有良好的處理性能。

3.5 算法性能比較分析

3.5.1 算法時間復雜度比較分析

為驗證RBFO-PSVM算法的時間復雜度，本文基于BitcoinHeist、Covertype、Census-Income和GitHub MUSAE四種數據集進行對比實驗，根據算法的運行時間，與MR-PSVM［15］、MR-CSSVM［9］和PAFWU-SVM［11］算法進行綜合比較，實驗結果如圖5所示。

從圖5可以看出，RBFO-PSVM算法在四種數據集上的運行時間小于其他三種算法，且隨著樣本數目的增加，RBFO-PSVM相較于其他三種算法在運行時間上的增幅最小。在大小適中的Census-Income數據集上，相較于MR-PSVM、MR-CSSVM和PAFWU-SVM算法，RBFO-PSVM算法的運行時間分別降低了48.1%、51.9%、42.1%；在特征數目較多的GitHub MUSAE數據集上，RBFO-PSVM算法的運行時間與MR-PSVM、MR-CSSVM和PAFWU-SVM算法相比，分別降低了41.5%、46.1%和18.2%；隨著數據規模的增長，在樣本數目較多的BitcoinHeist數據集上，RBFO-PSVM的運行時間相較于MR-PSVM、MR-CSSVM和PAFWU-SVM算法，分別降低了27.9%、37.5%和19.8%。RBFO-PSVM算法的時間復雜度小于其他三種算法的主要原因是：a）使用MI-Relief策略刪減冗余數據，減少了算法處理冗余數據的時間；b）使用基于MapReduce的MR-HBFO算法實現并行參數尋優，提高了并行SVM的尋優速度；c）構建了基于MapReduce的CFCPSVM模型，該模型通過縮減數據集和改進CSVM的反饋機制有效地提高了并行SVM的并行化效率。以上三個方面的改進使得RBFO-PSVM算法更能適應于大數據環境，具有更好的魯棒性。

3.5.2 算法加速比較分析

為了評估RBFO-PSVM算法的并行性能，本文基于BitcoinHeist、Covertype、Census-Income和GitHub MUSAE四個數據集進行實驗，根據實驗得到的加速比比較分析RBFO-PSVM算法與MR-PSVM［15］、MR-CSSVM［9］和PAFWU-SVM［11］算法的差異，實驗結果如圖6所示。

從圖6可以看出，在各數據集上隨著節點數的增加，RBFO-PSVM算法始終擁有最高的加速比。在樣本數目較多的BitcoinHeist數據集上，RBFO-PSVM算法的加速比，在節點數為5時，比PAFWU-SVM、MR-PSVM和MR-CSSVM算法分別提升了0.6、0.8和1.2；在Covertype數據集上分別提升了0.2、0.4和0.7；在Census-Income數據集上分別提升了0.3、0.4和0.9；在特征數目較多的GitHub MUSAE數據集上分別提升了0.2、0.5和0.8。這是因為RBFO-PSVM算法使用了基于MapReduce的CFCPSVM模型，該模型會在并行化訓練之前使用KCS策略縮減數據集，大大減小了參與訓練的數據集規模，其并行化效率遠高于單純使用MapReduce框架的MR-PSVM算法，且模型減少了反饋融合的次數，使得反饋效率高于MR-CSSVM算法。其次RBFO-PSVM還使用了MI-Relief策略刪減冗余數據，提高了算法對多屬性數據集的處理能力，其刪減效率遠高于采用特征融合的PAFWU-SVM算法。故相較于另外三種算法，RBFO-PSVM算法在大數據集上的并行性能和魯棒性更佳。

3.5.3 算法分類準確度比較分析

為了評估RBFO-PSVM算法的并行化性能，將RBFOA-PSVM算法分別與MR-PSVM［15］、MR-CSSVM［9］和PAFWU-SVM［11］算法在BitcoinHeist、Covertype、Census-Income和GitHub MUSAE數據集上進行對比實驗，在實驗中分別比較了各算法的分類準確度 F -measure，實驗結果如圖7所示。

從圖7可以看出，在各數據集上，RBFO-PSVM算法的分類準確度始終高于其他三種算法的分類準確度，在各種不同特征的數據集上，RBFO-PSVM都具有較好的魯棒性。在Bitcoin-Heist數據集上，RBFO-PSVM算法的準確度比MR-CSSVM、MR-PSVM和PAFWU-SVM算法分別高出8.7%、7.5%、2.6%；在Covertype數據集上，RBFO-PSVM算法的準確度比MR-CSSVM、MR-PSVM和PAFWU-SVM算法分別高出5.1%、4.9%、2.3%；在Census-Income數據集上，RBFO-PSVM算法的準確度比MR-PSVM、MR-CSSVM和PAFWU-SVM算法分別高出了4.5%、2.8%、2.4%；在GitHub MUSAE數據集上，RBFO-PSVM算法的準確度比MR-PSVM、MR-CSSVM和PAFWU-SVM算法分別高出8.5%、7.4%、2.9%。從實驗結果可以看出，RBFO-PSVM算法在處理維度較低的BitcoinHeist、Covertype和Census-Income數據集時，準確度沒有明顯的提升，而在處理維度較高的GitHub MUSAE數據集時，準確度遠高于另外三種算法。這是因為RBFO-PSVM算法使用MI-Relief策略降低了數據維度，有效地減小了數據復雜度，使得冗余數據對并行SVM的干擾顯著降低，并且RBFO-PSVM還使用了MR-HBFO算法進行參數尋優，同時，采用CFCPSVM模型重復訓練SVM，有效地提高了算法的分類準確度和并行性能。故由以上實驗結果可知，面對大多數數據集RBFO-PSVM算法的準確度都高于MR-PSVM、MR-CSSVM和PAFWU-SVM算法，且在處理高維數據時，RBFO-SVM算法的優勢更加明顯。

為了評估RBFO-PSVM算法在不同計算節點下的分類性能，通過自助采樣的方式從BitcoinHeist數據集中得到四組不同大小的數據集，比較算法在不同數據集上的MCC。實驗結果如圖8所示。

從圖8可以看出，隨著節點數和樣本數的增加，RBFO-PSVM算法的MCC越來越接近單機時的MCC，表明RBFO-PSVM算法的分類性能不會因節點數的增加而出現損失較大的狀況。樣本數為30 000時，單機狀況下的MCC比節點數為4、5時分別高出0.3和0.024；樣本數為60 000時，單機狀況下的MCC比節點數為4、5時分別高出0.015和0.006；樣本數為70 000時，單機狀況下的MCC比節點數為4、5時分別高出0.01和0.005。從實驗結果可以看出，隨著樣本數的增加，RBFO-PSVM算法表現出更好的分類性能。這是因為RBFO-PSVM算法使用基于MapReduce的MRHBFO算法提高了并行SVM的并行尋優能力，為分類器選取了合適的參數。在并行SVM模型構造階段，使用KCS策略縮減數據集并改進了CSVM的反饋機制，加強了數據塊間的數據交互，進而提高了算法在多個節點時的MCC。由以上實驗結果可知，在節點數適當時，RBFO-PSVM有較高的MCC，且隨著樣本數的增加RBFO-PSVM算法依然擁有較好的分類性能，在面對不平衡數據集時，RBFO-PSVM算法有較好的擴展性。

4 結束語

為解決大數據環境下并行SVM算法處理高維數據時存在噪聲數據敏感、參數選取困難以及并行化效率低等問題進行研究，提出了一種基于Relief和BFO算法的交叉融合級聯式并行SVM算法RBFO-PSVM。該算法為了解決并行SVM噪聲數據敏感問題，使用MI-Relief策略刪減冗余數據，利用互信息計算特征之間的冗余度，并結合Relief算法計算特征區分類別的能力，準確地識別特征是否為冗余數據；提出了基于Map-Reduce的MR-HBFO算法，通過自適應游動步長、自適應翻轉方向和方差復制有效地提高了并行SVM的參數尋優能力，解決了并行SVM參數選取困難的問題；提出了基于MapReduce的CFCPSVM模型，該模型通過KCS策略縮減數據集并改進了CSVM的反饋機制，提高了RBFO-PSVM算法的并行化效率。同時，為了驗證RBFO-PSVM算法的分類性能，在BitcoinHeist、Covertype、Census-Income和GitHub MUSAE數據集上對RBFO-PSVM、MR-PSVM、MR-CSSVM和PAFWU-SVM算法進行綜合性能對比分析，實驗結果表明，在較大數量的數據集和高維數據集中，RBFO-PSVM算法能夠更高效地完成分類過程，其時間開銷最少，執行效果最佳。

雖然RBFO-PSVM算法在并行SVM分類效果方面取得了一定的進步，但依然還有很大的提升空間。要提出一個更加健壯的并行SVM算法，在時間上，需要更加高效的并行尋優算法，考慮選取部分具有代表性的樣本進行尋優，并在并行SVM模型構建中加入負載均衡策略以減少等待時間，還可以將CSVM結構與增量學習結合起來，提高CSVM的并行化效率；在空間上，需要加入更加高效的緩存策略以減少矩陣計算的空間占用；在準確率方面，需要更加精準和高效的數據集縮減策略，減小非支持向量在訓練數據集中所占的比例。以上將是今后的重點研究內容。

參考文獻：

［1］ ""Cervantes J，Garcia-Lamont F，Rodríguez-Mazahua L， et al .A comprehensive survey on support vector machine classification：applications，challenges and trends［J］. Neurocomputing ，2020， 408 （9）：189-215.

［2］ Chaa M，Akhtar Z，Attla A.3D palmprint recognition using unsupervised convolutional deep learning network and SVM classifier［J］. IET Image Processing ，2019， 13 （5）：736-745.

［3］ 葛曉偉，李凱霞，程銘.基于CNN-SVM的護理不良事件文本分類研究［J］.計算機工程與科學，2020， 42 （1）：161-166. （Ge Xiaowei，Li Kaixia，Cheng Ming.Research on text classification of adverse nursing events based on CNN-SVM［J］. Computer Engineering amp; Science ，2020， 42 （1）：161-166.

［4］ Huang Shujun，Cai Nianguang，Pacheco P P， et al .Applications of support vector machine learning in cancer genomics［J］. Cancer Genomics amp; Proteomics ，2018， 15 （1）：41-51.

［5］ Patro K K，Reddi S P R，Khalelulla S K E， et al .ECG data optimization for biometric human recognition using statistical distributed machine learning algorithm［J］. Journal of Supercomputing ，2020， 76 （2）：858-875.

［6］ Xiao Chenglin，Xia Weili，Jiang Jijiao.Stock price forecast based on combined model of ARI-MA-LS-SVM［J］. Neural Computing and Applications ，2020， 32 （1）：5379-5388.

［7］ Shah J S.A survey on Hadoop MapReduce framework［J］. International Journal of Innovative Research in Computer and Communication Engineering ，2019， 7 （4）：2209-2217.

［8］ Satti I，Elkarim A，Agbinya J， et al .Parallel SVM based classification technique on big data：HPC center in Sudan［J］. Australian Journal of Basic and Applied Sciences ，2020， 14 （4）：1-14.

［9］ Hu Jingjing，Ma Dongyan，Liu Chen， et al. Network security situation prediction based on MR-SVM［J］. IEEE Access ，2019， 7 ：130937-130945.

［10］ Magoules F，Zhao Haixiang.Parallel computing for support vector machines［M］//

Data Mining and Machine Learning in Building Energy Analysis.[S.l.]：Wiley，2016：121-144.

［11］ Cao Jianfang，Wang Min，Li Yanfei， et al .Improved support vector machine classification algorithm based on adaptive feature weight updating in the Hadoop cluster environment［J］. PLoS One ，2019， 14 （4）：e0215136.

［12］ Zhang Wei.Relief feature selection and parameter optimization for support vector machine based on mixed kernel function［J］. International Journal of Performability Engineering ，2018， 14 （2）：280-289.

［13］ 李素，袁志高，王聰，等.群智能算法優化支持向量機參數綜述［J］.智能系統學報，2018， 13 （1）：70-84. （Li Su，Yuan Zhigao，Wang Cong， et al. Optimization of support vector machine parameters based on group intelligence algorithm［J］. CAAI Trans on Intelligent Systems ，2018， 13 （1）：70-84.）

［14］ 滿蔚仕，吉元元.Hadoop平臺分布式SVM算法分類研究［J］.計算機系統應用，2017， 26 （8）：141-146. （Man Weishi，Ji Yuanyuan.Research on distributed SVM classification based on Hadoop platform［J］. Computer Systems amp; Applications ，2017， 26 （8）：141-146.）

［15］ Jadhav N，Bhavani C.Parallel support vector machines on a Hadoop framework［J］. International Journal of Research ，2018， 7 （9）：60-66.

［16］ Zhang Jianpei，Li Zhongwei，Yang Jing.A parallel SVM training algorithm on large-scale classification problems［C］//Proc of International Conference on Machine Learning and Cybernetics.Piscataway，NJ：IEEE Press，2005：1637-1641.

［17］ Cover T M，Thomas J A.Elements of information theory［M］.New Jersey：Wiley-Blackwell，2003.

［18］ Wang Tongbo.A novel kernel clustering method for SVM training sample reduction［C］//Proc of International Conference on Algorithms and Architectures for Parallel Processing.Cham：Springer，2018：51-58.

［19］ Urbanowicz R J，Meeker M，La Cava W， et al .Relief-based feature selection：introduction and review［J］. Journal of Biomedical Informatics ，2018， 85 （9）：189-203.

［20］ "Ye Fulan，Lee C Y，Lee Z J， et al. Incorporating particle swarm optimization into improved bacterial foraging optimization algorithm applied to classify imbalanced data［J］. Symmetry ，2020， 12 （2）：

article No.29.

［21］ Graf H P，Cosatto E，Bottou L， et al. Parallel support vector machines：the cascade SVM［C］//Proc of the 17th International Conference on Neural Information Processing Systems.Cambridge，MA：MIT Press，2004：521-528.

［22］ Tian Liyan，Hu Xiaoguang.Method of parallel sequential minimal optimization for fast training support vector machine［J］. Applied Mechanics amp; Materials ，2010， 29-32 （8）：947-951.

［23］ Gao Wanfu，Hu Liang，Zhang Ping.Feature redundancy term variation for mutual information-based feature selection［J］. Applied Intelligence ，2020， 50 （4）：1272-1288.

［24］ Chen Huiling，Bo Yang，Wang Sujing， et al .Towards an optimal support vector machine classifier using a parallel particle swarm optimization strategy［J］. Applied Mathematics and Computation ，2014， 239 （8）：180-197.

［25］ Chen Hanning，Zhu Yunlong，Hu Kunyuan.Adaptive bacterial foraging optimization［J］. Abstract and Applied Analysis ，2014， 2011 ：article ID 108269.

［26］ Aha D，Murphy P，Merz C， et al. UCI machine learning repository[DB/OL].http：//archive.ics.uci.edu/ml/index.php.

［27］ Namdeo A，SINGH D.Challenges in evolutionary algorithm to find optimal parameters of SVM：a review［J/OL］. Materials Today：Proceedings .（2021-04-08）.http：//doi.org/10.1016/j.matpr.2021.03.288.