并行支持向量機(jī)

摘 要：支持向量機(jī)算法是一種基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則上，盡量提高學(xué)習(xí)機(jī)的泛化能力，在處理小樣本、非線性及高維模式識(shí)別問(wèn)題有許多優(yōu)勢(shì)，但在解決大規(guī)模數(shù)據(jù)時(shí)，訓(xùn)練速度會(huì)變得緩慢，影響訓(xùn)練的效果。所以，本文在原有支持向量機(jī)實(shí)現(xiàn)方式上，利用類(lèi)似級(jí)聯(lián)方式，增加算法處理的數(shù)據(jù)規(guī)模，并且基于云計(jì)算平臺(tái)，利用Map/Reduce機(jī)制實(shí)現(xiàn)算法過(guò)程，加快算法的訓(xùn)練速度。

關(guān)鍵詞：支持向量機(jī)；并行實(shí)現(xiàn)；Hadoop；Map/Reduce

中圖分類(lèi)號(hào)：TP18

在統(tǒng)計(jì)學(xué)理論的基礎(chǔ)上，發(fā)展出來(lái)的機(jī)器學(xué)習(xí)方法——支持向量機(jī)（Support Vector Machine，SVM）。支持向量機(jī)算法是基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則上，盡量提高學(xué)習(xí)機(jī)的泛化能力，具有良好的推廣性能和較好的分類(lèi)精確性。

近年來(lái)，人們?cè)絹?lái)越多的將目光集中在支持向量機(jī)的可擴(kuò)展性上，也提出了很多關(guān)于支持向量機(jī)的并行算法，主要是通過(guò)將數(shù)據(jù)集分割為小的數(shù)據(jù)模塊，對(duì)每個(gè)小的數(shù)據(jù)模塊進(jìn)行支持向量機(jī)訓(xùn)練，通過(guò)多次迭代形式，形成級(jí)聯(lián)式SVM實(shí)現(xiàn)并行處理樣本數(shù)據(jù)，或者是通過(guò)多線程處理，得到訓(xùn)練模型。這些方法充分利用現(xiàn)階段硬件的一些新特性，在不同程度上提高了支持向量機(jī)的性能。但是，通過(guò)這種方式并行處理數(shù)據(jù)來(lái)提高訓(xùn)練速度，由于計(jì)算步驟地設(shè)計(jì)和在每個(gè)小的數(shù)據(jù)子集訓(xùn)練狀態(tài)的不同，導(dǎo)致再想進(jìn)一步提高算法效率明顯是比較難的。解決這一問(wèn)題，一種有效的方式，就是利用云計(jì)算平臺(tái)集群的優(yōu)勢(shì)，提高算法運(yùn)算效率，加快算法運(yùn)算時(shí)間。

1 PSVM算法

1.1 SVM簡(jiǎn)介

支持向量機(jī)是一種二類(lèi)分類(lèi)模型。SVM學(xué)習(xí)的基本思想是求解能夠正確劃分訓(xùn)練數(shù)據(jù)集并且?guī)缀伍g隔最大的分離超平面，等價(jià)于構(gòu)造并求解最優(yōu)化問(wèn)題求得最優(yōu)解，由此得到分離超平面。在線性可分的情況下，訓(xùn)練數(shù)據(jù)集的樣本點(diǎn)中與分離超平面距離最近的樣本點(diǎn)的實(shí)例稱(chēng)為支持向量（support vector）。支持向量是約束條件式成立的點(diǎn)，即：對(duì)的正例點(diǎn)，支持向量在超平面上，對(duì)的負(fù)例點(diǎn)，支持向量機(jī)在超平面上。

1.2 SMO

快速學(xué)習(xí)算法-序列最小最優(yōu)化算法（sequential minimal optimization， SMO），是一種啟發(fā)式算法，其基本思想是，如果所有變量的解都滿足此最優(yōu)化問(wèn)題的KKT條件，那么這個(gè)最優(yōu)化問(wèn)題的解就得到了。否則，選擇兩個(gè)變量，固定其他變量，針對(duì)這兩個(gè)變量構(gòu)建一個(gè)二次規(guī)劃的問(wèn)題。SMO算法將原問(wèn)題不斷分解為子問(wèn)題并對(duì)子問(wèn)題求解，進(jìn)而達(dá)到求解原問(wèn)題的目的。

2 PSVM實(shí)現(xiàn)過(guò)程

2.1 PSVM方法

本文中并行支持向量機(jī)算法是基于云計(jì)算平臺(tái)實(shí)現(xiàn)的。根據(jù)Hadoop平臺(tái)Map/Reduce實(shí)現(xiàn)機(jī)制的特點(diǎn)，采用類(lèi)似級(jí)聯(lián)SVM的方法對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行處理。PSVM實(shí)現(xiàn)方式是：（1）首先將訓(xùn)練數(shù)據(jù)分割成子集（依照級(jí)聯(lián)方式逐次減少），對(duì)每個(gè)子集分別進(jìn)行獨(dú)立訓(xùn)練，得到支持向量。（2）對(duì)運(yùn)行過(guò)程進(jìn)行判斷，如果沒(méi)有結(jié)束，則對(duì)得到的支持向量結(jié)合后，再進(jìn)行分塊處理，進(jìn)行操作（1）；否則，訓(xùn)練結(jié)束，則進(jìn)行操作（3）。（3）訓(xùn)練結(jié)束，將訓(xùn)練得到的訓(xùn)練模型輸出。在訓(xùn)練過(guò)程中，盡可能早地消除非支持向量來(lái)加速支持向量機(jī)過(guò)程。

下圖以三層級(jí)聯(lián)支持向量機(jī)訓(xùn)練過(guò)程為例，說(shuō)明算法的實(shí)現(xiàn)過(guò)程。

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

3.2 實(shí)驗(yàn)數(shù)據(jù)

3.3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)使用的數(shù)據(jù)是libsvm的自帶數(shù)據(jù)集，heart_scale數(shù)據(jù)集。

4 結(jié)束語(yǔ)

針對(duì)SVM對(duì)大規(guī)模訓(xùn)練樣本存在的訓(xùn)練速度緩慢的問(wèn)題，提出了基于Hadoop的Map reduce機(jī)制進(jìn)行SVM訓(xùn)練，通過(guò)Map將訓(xùn)練樣本分塊，再在Reduce中進(jìn)行SVM訓(xùn)練，輸出支持向量，通過(guò)迭代的過(guò)程完成SVM訓(xùn)練過(guò)程。并行支持向量機(jī)增加了訓(xùn)練樣本的大小，以及加快了訓(xùn)練時(shí)間，對(duì)于大數(shù)據(jù)的處理有很好的效果。

參考文獻(xiàn)：

[1]NelloCristianini，JohnShawe Taylor，著.李國(guó)正，王猛，曾華軍，譯.支持向量機(jī)導(dǎo)論[M].北京：電子上業(yè)出版社，2004.

[2]Tomwhite，著，曾大耽，周傲英，譯.Hadoop權(quán)威指南[M].北京：清華大學(xué)出版社，2010.

[3]鄧乃楊，田英杰，著.數(shù)據(jù)挖掘中的新方法——支持向量機(jī)[M].北京：科學(xué)出版社，2004.

[4]Hans Peter Graf，Eric Cosatto，Leon Bottou. Parallel Support Vector Machines：The Cascade SVM，2005.

作者單位：北京郵電大學(xué)計(jì)算機(jī)學(xué)院，北京 100876