MK-LSSVM與AdaBoost-SVM在分類中的比較和研究

劉衛(wèi)華

(蘭州交通大學(xué)自動化與電氣工程學(xué)院，甘肅 蘭州 730070)

0 引言

支持向量機(jī)(support vector machine，SVM)作為一種新的數(shù)據(jù)分類和函數(shù)估計(jì)方法［1］，越來越受到人們的重視。近幾年出現(xiàn)了許多對標(biāo)準(zhǔn)支持向量機(jī)的改進(jìn)方法，最小二乘支持向量機(jī)(least squares support vector machines，LS-SVM)［2］就是其中的一種。該方法采用等式約束代替了標(biāo)準(zhǔn)支持向量機(jī)的不等式約束，其實(shí)質(zhì)是求解線性方程組，這極大地簡化了計(jì)算的復(fù)雜性，提高了訓(xùn)練速度和測試速度。

集成分類方法是將多個弱分類器通過一定的策略組裝，充分利用多個弱分類器的特性，達(dá)到提高總的分類精度的目的。AdaBoost是集成分類方法中具有代表性的算法，將支持向量機(jī)(SVM)作為弱分類器的一種新的集成分類算法［3］(AdaBoost-SVM)已經(jīng)得到了廣泛應(yīng)用。

本文分別將改進(jìn)的多核LS-SVM算法和AdaBoost-SVM算法應(yīng)用于心臟單光子發(fā)射計(jì)算機(jī)化斷層顯像(single photon emission computerized tomography，SPECT)圖像數(shù)據(jù)和iris數(shù)據(jù)的分類問題，并且給出分類的可視化效果圖。試驗(yàn)結(jié)果表明，改進(jìn)的多核LS-SVM算法和AdaBoost-SVM算法都能取得較好的分類精度，且多核LS-SVM算法耗時(shí)較短。

1 最小二乘支持向量機(jī)

1.1 最小二乘支持向量機(jī)分類

LS-SVM算法的數(shù)學(xué)表達(dá)式如下:設(shè)訓(xùn)練樣本集D= { (xi，yi)}(i=1，…，N，xi∈Rn，yi∈R)，其中 xi表示輸入數(shù)據(jù)，yi表示輸出類別。LS-SVM的原始分類問題可以表述為:

構(gòu)造拉格朗日函數(shù)，可表示為:

式中:拉格朗日乘子αi∈R。

對式(3)進(jìn)行優(yōu)化，可表示為:

忽略w、ξ，由式(4)可以得到線性方程組，其表達(dá)式為:

將Mercer條件應(yīng)用到矩陣Ω=ZZT中，得到:

因此，式(1)的原始分類問題通過求解式(5)的線性方程可以獲得，于是可以得到?jīng)Q策函數(shù)為:

式中:sign為符號函數(shù);b為分類閾值;αi為拉格朗日乘子。

1.2 多核最小二乘支持向量機(jī)

基于多核核函數(shù)［4-5］的最小二乘支持向量機(jī)(multiple kernel least squares support vector machine，MK-LSSVM)算法是將不同類型的核函數(shù)進(jìn)行凸組合，得到新的等價(jià)核函數(shù)，其表達(dá)式為:

式中:λk為不同核函數(shù)的加權(quán)系數(shù)［6］。

由核函數(shù)的性質(zhì)可知，等價(jià)核函數(shù)滿足Mercer條件。

MK-LSSVM的原始問題變?yōu)?

2 AdaBoost-SVM算法

AdaBoost分類算法是以尋求高分類精度為目標(biāo)的一種迭代的訓(xùn)練算法，它是將多個弱分類器經(jīng)過一定的策略組合，最終求得一個強(qiáng)分類器的過程［7］。在這個過程中，主要是通過改變樣本的權(quán)重系數(shù)來改變樣本分布，對于錯誤分類的樣本增大其相應(yīng)的權(quán)重系數(shù)，同時(shí)降低正確分類樣本的權(quán)重系數(shù)。經(jīng)過T次迭代循環(huán)，得到了T個基分類器和T個與其對應(yīng)的權(quán)重系數(shù)，最后把這T個基分類器按權(quán)重系數(shù)疊加，從而得到最終的強(qiáng)分類器［8］。

算法過程示意圖如圖1所示。

圖1 算法過程示意圖Fig.1 Schematic diagram of the algorithm process

目前，神經(jīng)網(wǎng)絡(luò)、決策樹等方法已經(jīng)被用來作為AdaBoost的弱分類器，但都存在弱分類器本身的參數(shù)以及訓(xùn)練次數(shù)T選取難的問題。將SVM作為弱分類器很好地解決了以上問題［9］。當(dāng)SVM采用徑向基核函數(shù)時(shí)，它的分類性能只受高斯寬度σ和懲罰因子C的影響。只要給定一個適當(dāng)?shù)腃值，SVM的性能就會很大程度上依賴σ的取值。

AdaBoost-SVM算法的訓(xùn)練步驟［10］如下。

① 給定含有標(biāo)簽的訓(xùn)練樣本集S={(x1，y1)，…，(xN，yN)}，事先設(shè)定循環(huán)迭代次數(shù)為 T、誤差ε*、線性SVM 參數(shù) δ1={C1，C2，C3，…}與采用 RBF 核的非線性 SVM 參數(shù) δ2={(C1，σ1)，(C2，σ2)，...}，并且令δ = δ1∪δ2。

② 采用AdaBoost求出各個基分類器h1，h2，…，hT及其權(quán)重α1，α2，…，αT。假設(shè) ψ(x)=［α1h1(x)，α2h2(x)，…，αThT(x)］，則 訓(xùn) 練 集 S={［ψ (x1)，y1］，…，［ψ(xN)，yN］}。

③ 由以下步驟獲得SVM的參數(shù)δi∈δ。

對訓(xùn)練樣本集S做訓(xùn)練，并利用交叉驗(yàn)證優(yōu)化方法確定其誤差 ε。若 ε ＜ ε*，則設(shè) ε*=ε、δ*=δi。

④設(shè)定SVM的參數(shù)為δ*，并輸出訓(xùn)練后的強(qiáng)分類器。

3 試驗(yàn)及結(jié)果分析

本試驗(yàn)在一臺2.13 GHz、內(nèi)存2 GB的DELL個人計(jì)算機(jī)上運(yùn)行，在Matlab R2007b環(huán)境下實(shí)現(xiàn)。

將LS-SVM算法和AdaBoost-SVM算法分別應(yīng)用于二分類問題和多分類問題，所用的數(shù)據(jù)樣本有心臟單光子發(fā)射計(jì)算機(jī)化斷層顯像(SPECT)圖像數(shù)據(jù)、Iris數(shù)據(jù)集。由于數(shù)據(jù)都是具有多個屬性的高維數(shù)據(jù)集，文中采用Sammon算法將高維輸入空間的數(shù)據(jù)映射到二維輸出空間中予以顯示，從而使分類結(jié)果可視化。

①SPECT圖像數(shù)據(jù)試驗(yàn)

SPECT數(shù)據(jù)集包含兩個數(shù)據(jù)集:SPECT Heart數(shù)據(jù)集和SPECTF Heart數(shù)據(jù)集，這些數(shù)據(jù)描述了心臟診斷的單質(zhì)子發(fā)射計(jì)算機(jī)斷層攝影圖像。數(shù)據(jù)集共包含267個樣本，SPECT Heart數(shù)據(jù)集共有 22個屬性，SPECTF Heart數(shù)據(jù)集共有44個屬性。

試驗(yàn)過程中，SPECT數(shù)據(jù)取80個樣本為訓(xùn)練數(shù)據(jù)，剩下的作為測試數(shù)據(jù);迭代次數(shù)T取3，懲罰參數(shù)C以及核參數(shù)由交叉驗(yàn)證優(yōu)化方法尋優(yōu)得到。采用LSSVM、AdaBoost-SVM和MK-LSSVM這3種方法得到的數(shù)據(jù)分類試驗(yàn)結(jié)果如表1所示。

表1 數(shù)據(jù)分類試驗(yàn)結(jié)果Tab.1 Classification test results of heart data

由表1可以看出，3種方法都能達(dá)到較好的分類效果。從分類精度來看，MK-LSSVM算法略優(yōu)于普通LS-SVM算法和AdaBoost-SVM算法;從平均訓(xùn)練時(shí)間來看，由于在選型階段多核比普通RBF核需要更多的搜索時(shí)間，所以MK-LSSVM算法的訓(xùn)練與測試耗時(shí)都比普通的LS-SVM算法稍長些，但與AdaBoost-SVM算法相比較，MK-LSSVM算法明顯提高了訓(xùn)練速度。

②Iris數(shù)據(jù)試驗(yàn)

Iris鳶尾花數(shù)據(jù)集選自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫。該數(shù)據(jù)集包含150個樣本，分為3類，每類含50個樣本。樣本共有4種屬性:萼片寬度、萼片長度、花瓣寬度和花瓣長度。該數(shù)據(jù)集被認(rèn)為是目前模式識別中最好的測試數(shù)據(jù)集。

Iris數(shù)據(jù)分別選取的訓(xùn)練樣本數(shù)為40、60、80、100、120、140，隨機(jī)抽取80個數(shù)據(jù)作為測試樣本。采用LSSVM、AdaBoost-SVM和MK-LSSVM這3種算法分別對選取不同訓(xùn)練樣本數(shù)目時(shí)的Iris數(shù)據(jù)集進(jìn)行試驗(yàn)，迭代次數(shù)T取10，懲罰參數(shù)C以及核參數(shù)由交叉驗(yàn)證優(yōu)化方法尋優(yōu)得到。在樣本數(shù)目大小不同的情況下，3種方法的分類性能如圖2所示。

圖2 3種算法分類性能曲線比較Fig.2 Classification performance curves of three kinds of algorithms

由圖2可以看出，對多分類問題中的Iris數(shù)據(jù)集進(jìn)行性能測試時(shí)，這3種算法的分類精度都相應(yīng)地隨著訓(xùn)練樣本數(shù)目的增加而不斷提高。當(dāng)訓(xùn)練樣本較少時(shí)，MK-LSSVM算法的分類精度高于其他兩種算法，并且當(dāng)訓(xùn)練樣本數(shù)增加到一定數(shù)目時(shí)，MK-LSSVM算法的分類精度可以達(dá)到100%。

Iris數(shù)據(jù)經(jīng)過MK-LSSVM分類器分類并通過Sammon映射后在二維平面的分類可視化圖如圖3所示。

圖3 Iris數(shù)據(jù)集分類可視化圖Fig.3 Visualized diagram of Iris data classification

4 結(jié)束語

本文比較研究了MK-LSSVM和AdaBoost-SVM這兩種分類器方法。MK-LSSVM算法是最小二乘支持向量機(jī)的一種改進(jìn)算法，它將多核學(xué)習(xí)的理念與最小二乘支持向量機(jī)相融合，降低了分類精度對核函數(shù)選擇的依賴性。AdaBoost-SVM算法是通過選擇合適參數(shù)，將支持向量機(jī)作為一種弱分類器，通過循環(huán)迭代而最終得到強(qiáng)分類器。

將MK-LSSVM和AdaBoost-SVM這兩種方法應(yīng)用于二分類問題和多分類問題中，通過試驗(yàn)數(shù)據(jù)結(jié)果可知，這兩種方法都能獲得較好的分類精度，但AdaBoost-SVM算法耗時(shí)較長;從經(jīng)Sammon映射的分類可視化圖可以看出，在Iris數(shù)據(jù)分類中，MK-LSSVM算法的分類精度可達(dá)到100%，而AdaBoost-SVM算法的平均耗時(shí)要比MK-LSSVM算法長。

［1］Cristianini N，Shawe-Taylor J.支持向量機(jī)導(dǎo)論［M］.李國正，王猛，曾華軍，譯.北京:電子工業(yè)出版社，2004.

［2］Suykens J A K，Vandewalle J.Least squares support vector machine classifiers［J］.Neural Processing Letters，1999，9(3):293-300.

［3］閻威武，邵惠鶴.支持向量機(jī)和最小二乘支持向量機(jī)的比較及應(yīng)用研究［J］.控制與決策，2003，18(3):358-360.

［4］Taylor J S，Cristianini N.Kernel methods for pattern analysis［D］.Cambridge:Cambridge University，2004.

［5］汪洪橋，孫富春，蔡艷寧，等.多核學(xué)習(xí)方法［J］.自動化學(xué)報(bào)，2010，36(8):1037-1050.

［6］陳強(qiáng)，任雪梅.基于多核最小二乘支持向量機(jī)的永磁同步電機(jī)混沌建模及其實(shí)時(shí)在線預(yù)測［J］.物理學(xué)報(bào)，2010，54(4):2310-2318.

［7］朱樹先，張仁杰，鄭剛.混合核函數(shù)對支持向量機(jī)分類性能的改進(jìn)［J］.上海理工大學(xué)學(xué)報(bào):自然科學(xué)版，2009，31(2):173-176.

［8］Li Xuchun，Wang Lei，Sung Eric.AdaBoost with SVM-based component classi fi ers［J］.Engineering Applications of Arti fi cial Intelligence，2008(21):785-795.

［9］胡金海，謝壽生，楊帆，等.基于支持向量機(jī)的組合分類方法及應(yīng)用［J］.推進(jìn)技術(shù)，2007，28(6):669-673.

［10］張曉龍，任芳.支持向量機(jī)與AdaBoost的結(jié)合算法研究［J］.計(jì)算機(jī)應(yīng)用研究，2009，26(1):77-78，110.