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

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

中圖分類號：TP18

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

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

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

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

1 支持向量機(jī)分類方法

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

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

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

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

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

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

2 基于并行計(jì)算的支持向量機(jī)加速算法

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

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

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

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

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

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

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

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

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

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

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

Step5：采用Step4得到的最優(yōu)核函數(shù)及懲罰參數(shù)在每個(gè)工作子集Xi上進(jìn)行訓(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 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

[2]苗奪謙，王國胤，劉清等.粒計(jì)算：過去、現(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ī)算法研究[J].計(jì)算機(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]陳國良.并行計(jì)算——結(jié)構(gòu)、算法、編程（第二版）[M].北京：高等教育出版社，2003.

[10]金瀟明，文益民.基于支持向量機(jī)的并行學(xué)習(xí)方法研究[J].湖南大學(xué)學(xué)報(bào)：自然科學(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.