基于并行計算的支持向量機加速算法

摘 要：針對傳統(tǒng)支持向量機（Support Vector Machine，SVM）方法不能有效處理海量數(shù)據(jù)分類的問題，本文提出一種基于并行計算（Parallel Computing，PC）的支持向量機加速（Speeding support vector machine based on parallel computing，PC_SVM）方法。該方法首先將海量的訓(xùn)練樣本通過聚類方式劃分為多個獨立的工作子集，并在每個工作子集上并行進行SVM的自適應(yīng)訓(xùn)練，以得到適應(yīng)該訓(xùn)練子集的SVM學(xué)習(xí)模型，通過衡量不同子集訓(xùn)練結(jié)果的關(guān)系，對每個工作集中聚類得到的子類進行合并，從而有效處理海量數(shù)據(jù)的分類問題。實驗結(jié)果表明，PC_SVM方法在大規(guī)模數(shù)據(jù)集上在保持分類效果的同時大幅度提高了傳統(tǒng)SVM的分類效率。

關(guān)鍵詞：支持向量機；并行計算；并行支持向量機；工作子集；效率

中圖分類號：TP18

隨著科學(xué)技術(shù)的進步，以及人們管理和知識水平的提高，現(xiàn)實世界中需要處理的數(shù)據(jù)量越來越大。據(jù)互聯(lián)網(wǎng)數(shù)據(jù)中心發(fā)布的研究報告指出，2011年全球數(shù)據(jù)存儲量達到1.8ZB，預(yù)計2020年全球數(shù)據(jù)存儲量將為現(xiàn)在的50倍[1]。為了能夠從海量數(shù)據(jù)中提煉出有用知識，數(shù)據(jù)挖掘技術(shù)便應(yīng)用而生。數(shù)據(jù)挖掘[2]是指從大規(guī)模的、不完整的、有噪聲的、模糊的、隨機的復(fù)雜數(shù)據(jù)集中提取潛在有用的信息或知識。

支持向量機[3]（Support Vector Machine，SVM）是一種近年來受到廣泛關(guān)注的機器學(xué)習(xí)方法，它以統(tǒng)計學(xué)習(xí)理論（Statistical Learning Theory，SLT）為基礎(chǔ)，具有簡潔的數(shù)學(xué)表示、標準的訓(xùn)練算法和良好的泛化性能，目前在諸如模式識別[4]、函數(shù)估計[5]、圖像識別[6]、時間序列預(yù)測[7]和生物信息學(xué)[8]等諸多領(lǐng)域得到成功的應(yīng)用。然而，由于支持向量機的學(xué)習(xí)過程要構(gòu)建核矩陣，當數(shù)據(jù)規(guī)模比較大時，核矩陣的運算會非常繁瑣，學(xué)習(xí)的效率也會較低。迄今為止，對于大規(guī)模數(shù)據(jù)的處理，并沒有特別有效的方法，既能夠提高學(xué)習(xí)效率，又可以獲得較為滿意的泛化能力。因此，如何提高支持向量機對于大規(guī)模數(shù)據(jù)學(xué)習(xí)的效率已成為近年來機器學(xué)習(xí)領(lǐng)域的一個研究熱點。

隨著數(shù)據(jù)挖掘領(lǐng)域處理樣本規(guī)模的日趨增大，要求研究人員能夠提出高效的挖掘算法來處理海量數(shù)據(jù)問題。并行計算作為一種定量、精細、高效的方法在海量數(shù)據(jù)挖掘中得到了成功的應(yīng)用[9]。狹義上的并行計算是指在并行/分布式計算機上所做的計算，從廣義上講，將多個問題同時求解的過程都可以看作是并行計算的過程。盡管目前已經(jīng)有學(xué)者提出了一些基于并行計算思想的技術(shù)以加速傳統(tǒng)支持向量機訓(xùn)練方法[10-12]，但是，這些方法的效率還不足夠高，對于大規(guī)模分類問題的處理能力依然有限。因此，如何結(jié)合并行計算技術(shù)進一步提高支持向量機方法處理海量數(shù)據(jù)的能力依然是一個值得探討的問題。

針對傳統(tǒng)支持向量機方法不能有效處理海量數(shù)據(jù)分類的問題，本文提出一種基于并行計算的支持向量機加速方法。該方法首先將訓(xùn)練樣本通過聚類方法劃分為多個獨立的工作子集，并在每個工作集上進行自適應(yīng)的支持向量機訓(xùn)練，最后對不同工作集的訓(xùn)練結(jié)果進行快速合并，從而有效處理海量數(shù)據(jù)的分類問題。

1 支持向量機分類方法

支持向量機最早是面向分類問題提出的。就兩類問題而言，所謂最優(yōu)分類面就是要求分類面不但能將兩類示例無錯誤地分開，而且要使兩類示例的分類間隔最大。假設(shè)訓(xùn)練集為{（xi，yi）}li=1，xi∈Rd是輸入空間的向量，yi表示分類標識，yi∈{-1，1}。如果輸入向量集合是線性可分離的，則分類面方程為：

此時分類間隔等于2/‖w‖，使間隔最大化等價于使‖w‖2最小，滿足式（2）且使1/2‖w‖2最小的分類面叫做最優(yōu)分類面，落在分類間隔邊界上和邊界外的點就稱為支持向量。支持向量機求解的過程實質(zhì)上就是尋找支持向量的過程。

根據(jù)結(jié)構(gòu)風(fēng)險最小化（SRM）原理，即求解以下約束最優(yōu)化問題：

一般情況下，訓(xùn)練集不是完全線性可分的，此時分類器允許有一定的誤差，因此引入非負變量ξi≥0，構(gòu)造軟間隔最優(yōu)分類超平面，對應(yīng)最優(yōu)化問題變成如下形式：

其中C為軟間隔懲罰參數(shù)，用于調(diào)節(jié)分類超平面寬度與分類允許誤差的平衡。

對于復(fù)雜非線性可分問題，SVM通過引入核方法，將低維空間的訓(xùn)練數(shù)據(jù)通過映射函數(shù)Φ映射到高維空間，使其線性可分，但在實際問題中，顯示的映射函數(shù)Φ是很難得到的，因此這里采用核函數(shù)K（x，x，）來進行樣本的映射，使得K（x，x，）=Φ（x）·Φ（x，）。常見的核函數(shù)包含高斯核、多項式核和線性核等[13]。

2 基于并行計算的支持向量機加速算法

設(shè)數(shù)據(jù)集X={x1，…，xi，…xn}且xi∈Rd，其中n為樣本個數(shù)，d為樣本維度，假設(shè)k為指定的工作子集劃分參數(shù)。采用傳統(tǒng)k-均值聚類方法將樣本集X劃分為k個工作子集，即X→{X1，…，Xk}，并計算每個工作子集X1，…，Xk所對應(yīng)的中心c1，…，ck以及距離每個工作子集中心最近的樣本點x1，，…，xk，，構(gòu)成工作子集的類中心集X，→{x1，，…，xk，}。然后在每個工作子集上訓(xùn)練支持向量機學(xué)習(xí)器。這里每個工作子集上的支持向量機均采用高斯核，核參數(shù)P和懲罰參數(shù)C在每個工作子集上均采用網(wǎng)格搜索的方法確定。假設(shè)每個工作子集X1，…，Xk上得到的對應(yīng)支持向量子集分別為SV1，…，SVk，并構(gòu)成工作子集的支持向量集SV={SV1，…，SVk}。最后，合并工作子集中心集X，及工作子集的支持持向量集SV，構(gòu)成新的訓(xùn)練集來訓(xùn)練SVM，從而得到最終的分類器。

基于并行計算的支持向量機加速算法具體如下：

初始化：設(shè)初始訓(xùn)練數(shù)據(jù)集為X={x1，…，xi，…xn}且xi∈Rd，其中n為樣本個數(shù)，d為樣本維度，假設(shè)k為指定的工作子集劃分參數(shù)。

Step1：將訓(xùn)練集X通過k-均值聚類劃分為k個工作子集，即X→{X1，…，Xk}，具體方法如下：

Step1.1：在訓(xùn)練集X中隨機選擇k個樣本作為初始聚類中心C={c1，…，ck}；

Step1.2：根據(jù)式（6）計算每個樣本xi與不同類聚類中心之間的相似度，并將xi歸為與其相似度最高的類中心所屬的類；

其中，xjq∈Xj，nj為聚類子集Xj包含的樣本數(shù)；

Step1.4：若類中心有更新，則返回Step1.2繼續(xù)聚類，直到類中心不發(fā)生更新時迭代停止，得到訓(xùn)練集X的聚類結(jié)果X→{X1，…，Xk}及相應(yīng)的工作子集的中心集C={c1，…，ck}。

Step2：根據(jù)式（6）計算每個工作子集Xi中與其中心ci最相似的樣本點xi，，并構(gòu)成工作子集的類中心集X，={x1，，…，xk，}。

Step3：將測試集TX也采用Step1的聚類方法劃分為k個類別，即TX→{TX1，…，TXk}；

Step4：結(jié)合劃分后的每個訓(xùn)練工作子集Xi和與之對應(yīng)的測試工作子集TXi，采用網(wǎng)格搜索的方法選擇SVR訓(xùn)練所需要的最優(yōu)核參數(shù)Pi和懲罰參數(shù)ci；

Step5：采用Step4得到的最優(yōu)核函數(shù)及懲罰參數(shù)在每個工作子集Xi上進行訓(xùn)練，得到該工作子集的支持向量子集SVi，從而構(gòu)成全部的支持向量集SV={SV1，…，SVk}。

Step6：構(gòu)造最終的工作集T=X，USV，然后采用網(wǎng)格搜索的方法設(shè)置核函數(shù)參數(shù)及懲罰參數(shù)，得到最終的訓(xùn)練結(jié)果。

算法結(jié)束。

3 實驗結(jié)果及分析

為驗證基于并行計算的支持向量機加速算法的性能，本文在五個標準數(shù)據(jù)集[13]上進行了實驗，具體見表1。實驗全部采用高斯核，核參數(shù)及懲罰參數(shù)采用網(wǎng)格搜索的方式確定，核參數(shù)P的網(wǎng)格搜索范圍為0.8、0.9、1.0、1.1、1.2；懲罰參數(shù)的搜索范圍為10、100、1000、10000和100000，取每個工作子集上對應(yīng)精度最高的核函數(shù)參數(shù)P和懲罰參數(shù)C作為訓(xùn)練的最優(yōu)參數(shù)；初始聚類參數(shù)k分別取20、40、60、80、100。實驗在1臺PC機（2.66Ghz CPU， 1G內(nèi)存）上進行，實驗平臺是Matlab2008。

為檢驗本文所提的基于并行計算的PC_SVM方法的性能，本文與與標準SVM學(xué)習(xí)算法進行比較。表2為PC_SVM算法及標準SVM算法在各數(shù)據(jù)集上的訓(xùn)練和測試結(jié)果的對比。

從實驗中可以看出，采用本文提出的基于并行計算的PC_SVM方法在數(shù)據(jù)集Letter上得到的泛化能力與傳統(tǒng)標準SVM一樣，測試精度都為78%，在數(shù)據(jù)集Banana上，當初始工作子集劃分參數(shù) 取100時，PC_SVM方法的測試精度比標準SVM方法還要高出0.1個百分點，而在其他三個數(shù)據(jù)集上，PC_SVM的最優(yōu)測試精度都與標準SVM的測試精度非常接近，這可能是由于PC_SVM方法通過并行計算，提取了大多數(shù)的重要支持向量信息，而刪除了對于分類不起作用甚至起副作用的非支持向量信息，從而保證了學(xué)習(xí)器具有較好的泛化能力。其次，從運行效率看，在五個數(shù)據(jù)集上都提高了200-1000倍，這是由于PC_SVM方法只提取了原始訓(xùn)練集中的少量樣本進行訓(xùn)練，從而大大地壓縮了訓(xùn)練的時間，提高了模型的學(xué)習(xí)效率。

綜上可看出，由于本文提出的基于并行計算的PC_SVM方法采用了并行計算的模式，通過將整個樣本集劃分為多個工作子集進行并行的處理，并有效地提取了訓(xùn)練樣本中包含重要分類信息的潛在支持向量樣本，而刪除了大量冗余的對分類無作用甚至具有副作用的非支持向量信息，因此能夠以很高的學(xué)習(xí)效率處理支持向量機針對大規(guī)模數(shù)據(jù)的分類問題，同時保證了模型的泛化性能。

4 結(jié)論

支持向量機是目前機器學(xué)習(xí)領(lǐng)域具有扎實的理論基礎(chǔ)、良好的泛化能力、廣泛的應(yīng)用價值的一種學(xué)習(xí)機。本文針對標準支持向量機算法復(fù)雜度高、模型訓(xùn)練效率低的問題，結(jié)合并行計算的思想提出一種并行的支持向量機加速算法。該方法通過將訓(xùn)練集劃分為多個工作子集，并在各自的工作子集上訓(xùn)練適合于當前工作子集的學(xué)習(xí)器，最后通過一定的方式抽取各工作子集的重要信息，刪除各工作子集的非重要信息，從而在保證支持向量機泛化能力的同時大幅度提高了其學(xué)習(xí)效率，使其能夠方便地應(yīng)用于大規(guī)模數(shù)據(jù)的分類問題中。在未來的工作中，將進一步探索基于云計算的支持向量機處理模型，結(jié)合云計算思想來采用分布式的方法設(shè)計更為高效的并行支持向量機加速方法，進一步提高其處理海量、高維復(fù)雜數(shù)據(jù)的能力。

參考文獻：

[1]IDC研究報告[EB/OL].http：//storage.chinabyte.com/163/12110163.shtml，2011-06.

[2]苗奪謙，王國胤，劉清等.粒計算：過去、現(xiàn)在與展望[M].科學(xué)出版社，2007，299-303.

[3]V.Vapnik.StatisticalLearningTheory[M].NewYork：Wiley，1998.

[4]Y.L.Cunetal.Comparisonoflearningalgorithmsforhandwrittendigitrecognition[C].ProceedingsICANN95InternationalConferenceonArtificialNeuralNetworks.Vol.Ⅱ.EC2，1995：53-60.

[5]朱家元，陳開陶，張恒喜.最小二乘支持向量機算法研究[J].計算機科學(xué)，2003，30（7）：157-159.

[6]H.Berndeta1.Hierarchicalclassificationandfeaturereductionforfastfacedetectionwithsupportvectormachines[J].PatternRecognition，2003，36：2007-2017.

[7]S.Mukherjee，E.Osuna，F(xiàn).Girosi.Nonlinearpredictionofchaotictimeseriesusingasupportvectormachine[C].Proceedingsofthe1997IEEEWorkshoponNeuralNetworksforSignalProcessing，IEEEPress，1997：1125-1132.

[8]Y.C.Tang，B.Jin，Y.Q.Zhang.Granularsupportvectormachineswithassociationrulesminingforproteinhomologyprediction[J].ArtificialIntelligenceInMedicine，2005，35，121-134.

[9]陳國良.并行計算——結(jié)構(gòu)、算法、編程（第二版）[M].北京：高等教育出版社，2003.

[10]金瀟明，文益民.基于支持向量機的并行學(xué)習(xí)方法研究[J].湖南大學(xué)學(xué)報：自然科學(xué)版，2008，35（7）：74-79.

[11]B.Catanzaro，N.Sundaram，K.Keutzer.Fastsupportvectormachinetrainingandclassificationongraphicsprocessors[C].Proceedingsofthe25thInternationalConferenceonMachineLearning，Helsinki，F(xiàn)inland，2008，104-111.

[12]H.P.Graf，E.Cosatto，L.Bottou，etal.Parallelsupportvectormachines：ThecascadeSVM[C].ProceedingsofNIPS，2004，196-212.

[13]UCIMachineLearningRepository[DB/OL].http：//ww.ics.uci.edu/mleam/MLRepository.html，2010.