支持向量機與ＡｄａＢｏｏｓｔ的結合算法研究
2009-01-01 00:00:00張曉龍任芳
計算機應用研究 2009年1期
（武漢科技大學 計算機科學與技術學院， 武漢 430081）
摘 要：將支持向量機與AdaBoost算法相結合，稱其為BoostSVM。從提升泛化性能和預測精度等方面對支持向量機的學習算法進行了研究與比較。BoostSVM實驗結果表明，該算法提高了支持向量機的預測精度并優化了學習機的性能。
關鍵詞：支持向量機； 增強法； 自適應增強算法； 算法優化
中圖分類號：TP301.6 文獻標志碼：A
文章編號：10013695(2009)01007702
Study on combinability of SVM and AdaBoost algorithm
ZHANG Xiaolong， REN Fang
(School of Computer Science Technology， Wuhan University of Science Technology， Wuhan 430081， China）
Abstract:This paper described an algorithm——BoostSVM， which put SVM into AdaBoost framework， trying to improve the learning accuracy of the SVM algorithm. The experimental results show that the proposed method has a competitive learning ability and acquires better accuracy than SVM.
Key words：SVM; Boosting algorithm; AdaBoost algorithm; algorithm optimization
支持向量機是建立在統計學習理論的VC維(VapnikChervonenkis dimension)理論和結構風險最小化原則基礎上的新型機器學習方法。最初于20世紀90年代由Vapnik[1]提出，近年來在其理論研究和算法實現方面都取得了突破性進展。與傳統統計學的經驗風險最小化（ERM）不同，支持向量機基于結構風險最小化（SRM）原理[2]，從而表現出優于已有方法的性能，成為克服維數災難和過學習等傳統困難的有力手段，并且迅速引起各領域的注意和研究興趣，取得了大量的應用研究成果，推動了各領域的發展。但是，在實際應用支持向量機方法時，經常會遇到不平衡數據集或高精度要求等問題。為保證穩定的學習性能，本文引入了模式識別中分類器設計的重采樣技術——Boosting方法（增強法）。Boosting是一種試圖提升任意給定學習算法精度的普遍方法，可以集成任何分類算法的算法框架，有比較完整的數學理論基礎。與其他算法相比，Boosting具有適應性強、精度高的優點。AdaBoost（adaptive boosting，自適應增強）算法是Freund等人[3]提出的Boosting算法的一種變形，它有效地解決了早期Boosting算法在實際應用中的困難，其最終判別準則的精確度是依賴所有學習過程得出的假設，因而更能全面地挖掘學習算法的能力。本文將SVM作為AdaBoost集成學習框架的學習器，結合UCI數據進行實驗和比較。
1 支持向量機
SVM的基本思想是在二維兩類現行可分情況下，有很多可能的線性分類器可以把這組數據分開，但是只有一個使兩類的分類間隔（margin）最大，這個分類器就是最優分類超平面。假設該分類超平面表示為wTx+b=0，x∈Rd，它對樣本集中任意樣本點都滿足式（1）:
wTxi+b≥+1 當yi=+1時wTxi+b≤-1 當yi=-1時
(1)
這樣，任意樣本點到分類超平面的距離margin=2/‖w‖。因此使margin最大的超平面就是最優分類超平面，要使分類間隔2/‖w‖最大，就等價于使‖w‖/2最小。因此可將構造最優超平面的問題轉換為拉格朗日函數：
L(w，b，α)=wTw/2-∑li=1αi[yi(wTxi+b)-1](2)
yi(wTx+b)≥1；i=1，2，…，l(3)
對式（2）求其偏導可得其相應的對偶形式：
L(w，b，α)=∑li=1αi-（1/2）∑yiyjαiαj(xi×xj)(4)
其中：αi≥0，∑αiyi=0。
于是，最優分類問題就轉換為對αi求解式（4）的最大值問題。其中αi是與每個樣本對應的拉格朗日乘子。這是一個不等式約束下二次函數尋優問題，存在惟一解，且其最優解滿足條件αi(yi(wTx+b)-1)=0，i。顯然，只有支持向量的系數αi才可能為非零值，即只有支持向量影響最終的劃分結果。
當訓練樣本為非線性可分時，可以通過一個非線性函數φ(#8226;)將訓練樣本集x映射到一個高維線性特征空間，在這個維數可能無窮大的線性空間中構造最優分類超平面，并得到分類判別函數。因此，在非線性情況下，分類超平面為w×φ(x)+b=0。
最優分類面問題可描述為
minw，b，ξ ‖w‖2/2+c∑li=1ξi
(5)
其中:ξ為線性不可分問題的松弛變量；c為懲罰參數，使得
yi(w×φ(xi)+b)≥1-ξi； ξi≥0；i=1，2，…，l(6)
進而可得到其對偶形式為
L(w，b，ξ，α)=∑li=1αi-（1/2）∑li=1∑lj=1αiαjyiyjφ(xi)φ(xj)=
∑li=1αi-（1/2）∑li=1∑lj=1αiαjyiyjK(xi，xj)(7)
使得0≤αi≤c，∑li=1αiyi=0。
上式中的K(xi，xj)=φ(xi)×φ(xj)稱為核函數。在SVM中，不同的內積核函數將形成不同的算法。常用的核函數主要有以下幾種：
a)線性核函數，K(x，xi)=x×xi；
b)多項式核函數，K(x，xi)=[(x×xi)+1]q；
c)徑向基核函數，K(x，xi)=exp(-｜x-xi｜2)/σ2)；
d)Sigmoid核函數，K(x，xi)=tahn(v(x×xi)+c)。
核函數的作用是可以將數據特征映射到高維的特征空間。本文選擇的核函數為徑向基核函數。徑向基核函數有兩個優點：a)它可以將數據特征映射到更高維的特征空間，而并不增加計算復雜度；b)徑向基核函數只有一個參數，也降低了計算復雜度。
2 AdaBoost算法原理
2.1 Boosting算法
Boosting算法[4]的目標是提高任何給定的學習算法的分類準確率。在Boosting算法中，首先根據已有的訓練樣本集設計一個分類器，要求該分類器的準確率比平均性能要好；然后依次順序地加入多個分量分類器系統；最后形成一個總體分類器，它對訓練樣本集的準確率能夠任意高。在這種情況下，分類準確率被增強了。概括地說，此方法依次訓練一組分量分類器，其中每個分量分類器的訓練集都選擇自己已有的其他各個分類器所給出的最富信息（most information）的樣本點組成。而最終的判決結果則是根據這些分量分類器的結果共同決定。
2.2 AdaBoost算法
基本Boosting方法有許多不同的變形，其中最流行的一種就是AdaBoost方法。這個方法允許設計者不斷地加入新的分類器，直到達到某個預定的足夠小的誤差率。在AdaBoost方法中，每個訓練樣本都被賦予一個權重，表明它被某個分量分類器選入訓練集的概率。如果某個樣本點已經被準確地分類，那么在構造下一個訓練集中，它被選中的概率就被降低；相反，如果某個樣本點沒有被正確分類，那么它的權重就得到提高。通過這樣的方式，AdaBoost方法能夠聚焦于那些較困難（更富信息）的樣本上。在其具體實現上，最初令每個樣本的權重都相等。對于第k次迭代操作，根據這些權重來選取樣本點，進而訓練分類器Ck；然后根據這個分類器來提高被它錯分的那些樣本點的權重，并降低可以被正確分類的樣本權。權重更新過的樣本集被用來訓練下一個分類器Ck+1，整個訓練過程如此進行下去。
當改變樣本點權重后，必須考慮到分類器Ck的誤差率βk。βk對最終形成的各分量分類器的決策權有很大的影響，本文定義βk=（1/2） ln[(1-Ek)/Ek]，hk(xi)為分量分類器Ck給出的對任意樣本點xi的標記（+1或1）。最后總體分類的判決可以使用各個分量分類器加權平均來得到：
g(x)=∑kmaxk=1βkhk(x)(8)
這樣，最后的判定規則簡單形式就是sgn[g(x)]。
在大多數情況下，如果kmax足夠大，總體分類器的訓練誤差概率就能夠任意小。但是在實際應用中，通常令kmax比達到零誤差率所需要的值要小一些，這樣做的好處是增強分類器的推廣能力。雖然在原理上比較大的kmax值可能導致過擬合，但是仿真實驗卻表明，甚至當kmax非常大時，過擬合現象也很少發生。
3 BoostSVM算法設計
SVM算法與AdaBoost算法有一個共同點，即在學習過程中都是不斷地迭代訓練最富信息的樣本點。本文的BoostSVM算法結合了兩種算法的優點，在學習過程中重點訓練錯分的樣本點，即支持向量，試圖通過結合這一特點提高算法的分類性能。
本算法是以LIBSVM[5]為基礎平臺的，LIBSVM軟件包是由臺灣大學林智仁教授等人開發完成的。本文所采用的訓練算法是由LIBSVM[6]軟件包中提供的SMO[7]算法。其中，訓練算法所用到的參數C、γ（γ即為RBF核函數中σ的倒數）的選擇是由LIBSVM軟件包中的grid.py運用網格法實現的。
輸入數據集的格式為(yi，xi1，…，xin)。其中：n為樣本點的特征個數；yi為表示正負樣本的標志。為了得到每次迭代學習的最富信息，本文對各樣本點添加了一個屬性Di，用于表示訓練樣本的權重。在迭代學習前對其進行初始化，隨后在每次迭代學習后，根據分量學習器對其進行的分類正確與否更新樣本點的權重。這樣，在下一次迭代學習時就可以根據最新的權重選擇待訓練m個樣本點構成新的訓練集。具體的BoostSVM算法設計流程如下所示：
輸入：(x1，y1)，…，(xl，yl)，其中xi∈X，yi∈{-1，+1}
初始化：D1(i)=1/l
for t=1，…，T:
通過權重Dk選取含有m個樣本點的訓練集進行SVM訓練；
得到分類器hk:X→{-1，+1}；
用分類器對輸入數據進行預測；
根據預測精度計算分類器hk的權重βk；
更新各樣本點權重Dk+1(i)=Dk(i)exp(-yiβkhk(xi))/Zk，其中Zk為一個歸一化變量；
結束for循環
輸出最終的學習器：用迭代K次得到的分類器分別對樣本點進行分類，最終的分類結果由投票的方式得到，公式表示為H(x)=sign(∑Kk=1βkhk(x))。
4 BoostSVM算法的實驗過程及結果
4.1 BoostSVM算法的實驗過程
本文以breastcancer數據集為例介紹BoostSVM算法的實驗過程。
利用LIBSVM提供的grid.py文件對breastcancer數據集進行參數選擇，得到的參數值為C=0.5，γ=0.125。在以后的迭代學習中，將其作為分量學習器SVM的學習參數。對數據集中所有樣本點的權重進行初始化，將各權重值初始為Di=1/l=1/532，每個權重值與樣本點一一對應，并且時刻與樣本點相關聯。在每次迭代學習后根據式（9）更改每個樣本點的權重。當yi與hk(xi)相等時，說明分量分類器對第i個樣本分類正確，Dt+1(i)值較小；當yi與ht(xi)不相等時，說明分類錯誤，Dk+1(i)的值較大。
Dk+1(i)=Dk(i)exp(-yiβkhk(xi))/Zk(9)
根據Boosting算法的特點，當迭代足夠大時，分類誤差會盡可能小。為了明顯地提高分類效果，本文設置迭代次數為20，選取的訓練子集大小為40。接下來的迭代過程中，得到了20個分量分類器，分別存儲于20個以“.model”為后綴名的文件中。最后，執行數據集分類預測，即由這20個分量分類器分別對各樣本點進行預測，并根據類別投票的多少來決定樣本點最終的分類類別，將投票數目多的分類作為該樣本點的類別。
4.2 BoostSVM算法的實驗結果
本文的樣本訓練集采用UCI[8]的五組數據，對其進行了訓練和測試，并與LIBSVM的學習性能進行了比較，如表1所示。
表1 BoostSVM算法與LIBSVM性能比較
UCI datasetsLIBSVM/%BoostSVM/%
diabetes78.125 078.515 6
liverdisorders77.391 393.333 3
breastcancer97.744 497.932 3
Australian85.797 187.681 1
German78.900 079.600 0
表1中列出了將五個UCI數據集用于LIBSVM以及BoostSVM算法所得到的分類精度。本文將訓練這五組數據集時所使用的迭代次數都設定為20次。通過與LIBSVM學習精度相比，五組數據集的學習精度后者均高于前者。從以上實驗可以看出，BoostSVM算法的學習精度與LIBSVM相比，具有更好的學習性能。
5 結束語
本文提出了BoostSVM學習算法，將支持向量機作為基礎學習器應用于AdaBoost的迭代學習框架中。實驗結果表明，此算法將支持向量機和AdaBoost算法的優點很好地集于一身，改進了學習性能，提高了學習精度。另外，文獻[9]提出了一種σAdaBoostRBFSVM算法，通過使用變化著的參數σ試圖更好地適應每次迭代學習的SVM學習器，同樣達到了提高分類器的分類精度和泛化性的目的。由于缺乏該算法的實現程序，本文并未與σAdaBoostRBFSVM進行比較研究。現階段BoostSVM算法還僅局限于解決兩類分類問題，筆者將來的工作是解決多類問題以及回歸問題，并且將其應用于大規模數據學習問題中。
參考文獻：
［1］VAPNIK V N. The nature of statical learning theory[M]. London: SpringerVerlag， 1995.
[2]VAPNIK V N. Principles of risk minimization for learning theory[C]//Advances in Neural Information Processing Systems 4. San Francisco: Morgan Kaufmann Publishers，1992:831838.
[3]FREUND Y， SCHAPIRE R E. A decisiontheretic generalization of online learning and an application to boosting[J]. Journal of Computer and System Sciences， 1997，55(1) : 119139.
[4]DUDA R O， HART P E. 模式分類[M].李宏東，等譯. 北京：電子工業出版社， 2001.
[5]CHANG C C， LIN C J. LIB SVM:a library for support vector machines[EB/OL].(20020310). http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf.
[6]LIN C J. LIBSVM[EB/OL].(20030623). http://www.csie.ntu.edu.tw/~cjlin/.
[7]CHEN P H， FAN Rongen， LIN C J. A study on SMOtype decomposition methods for support vector machine[J]. IEEE Trans on Neural Networks， 2006，17(4):893908.
[8]Machine learning repository[EB/OL].(20020413). http://archive.ics.uci.edu/ml/.
[9]王曉丹， 孫東延. 一種基于AdaBoost的SVM分類器[J].空軍工程大學學報， 2006，7(6):5457.
