覃 俊，許 斐

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

支持向量機(jī)(SVM,Support Vector Machine)自Vapnik提出即成為機(jī)器學(xué)習(xí)和模式識(shí)別領(lǐng)域的研究熱點(diǎn)，但其自身方法的復(fù)雜性成為處理較大規(guī)模數(shù)據(jù)時(shí)的瓶頸.在模式識(shí)別的實(shí)際應(yīng)用中，很難在訓(xùn)練初期就收集得到一個(gè)完整的訓(xùn)練數(shù)據(jù)集，則希望機(jī)器學(xué)習(xí)的能力能隨著訓(xùn)練過(guò)程中樣本集的不斷積累而逐步提高.因此，具有增量學(xué)習(xí)能力的信息分類(lèi)技術(shù)，已漸漸成為信息智能化領(lǐng)域中的關(guān)鍵技術(shù)之一.

目前常用的、具有代表性的SVM增量學(xué)習(xí)算法有基于錯(cuò)誤率最小的增量學(xué)習(xí)策略[1]、基于KKT(Karush-Kuhn-Tucker)條件的增量學(xué)習(xí)策略[2]等.但是，這2種方法并沒(méi)有把部分普通樣本包含進(jìn)來(lái)，這部分樣本盡管不屬于支持向量集但距離最優(yōu)分類(lèi)面較近，可能轉(zhuǎn)變?yōu)橹С窒蛄炕虿荒鼙徽_分類(lèi)，但是直接舍棄不考慮，可能會(huì)導(dǎo)致分類(lèi)精度下降.

本文在分析了這些代表性算法的基礎(chǔ)上提出了一種基于殼向量的支持向量機(jī)漸進(jìn)增量學(xué)習(xí)算法，該算法以求取殼向量來(lái)降低SVM訓(xùn)練過(guò)程中二次尋優(yōu)的運(yùn)算時(shí)間[3]，且更加完善了增量學(xué)習(xí)過(guò)程中的選擇淘汰機(jī)制[4]，大大提高了SVM增量學(xué)習(xí)的訓(xùn)練速度；同時(shí)還利用由初始分類(lèi)器確定的KKT條件來(lái)選擇一部分增量樣本進(jìn)行訓(xùn)練，舍棄無(wú)用樣本以減少其中噪點(diǎn)帶來(lái)的干擾.二者結(jié)合構(gòu)成了基于殼向量的SVM漸進(jìn)增量學(xué)習(xí)算法能有效地提高增量學(xué)習(xí)的效率，尤其是在規(guī)模較大的樣本數(shù)據(jù)集中，分類(lèi)性能總體上優(yōu)于其他算法.

1 殼向量

包含某一類(lèi)訓(xùn)練樣本集在內(nèi)的最小凸集(特征空間中是一個(gè)多面體)稱為訓(xùn)練集的凸殼，簡(jiǎn)稱為凸殼.

殼向量(HV,Hull Vector)的思想[5,6]來(lái)自支持向量機(jī)中最優(yōu)分類(lèi)超平面的幾何意義，即保證兩類(lèi)樣本之間的最小間隔最大化，則支持向量一定只會(huì)在樣本集合的最邊緣位置上出現(xiàn).如圖1所示，A、B為分屬兩個(gè)不同類(lèi)別的訓(xùn)練樣本集，要使得二者最小間距最大化，支持向量是在圖中標(biāo)識(shí)的樣本集的凸殼上產(chǎn)生，而不可能是凸殼內(nèi)部的點(diǎn).

■表示訓(xùn)練集A的殼向量 ●表示訓(xùn)練集B的殼向量

1.1 支持向量與殼向量

圖1中，{A1,A2,A3,B1,B2,B3}為支持向量，令H(A)表示對(duì)訓(xùn)練樣本集A求殼向量集的算子，HVA則表示對(duì)應(yīng)求得的殼向量集，S(A)表示對(duì)訓(xùn)練樣本集A求支持向量集的算子，SVA則表示對(duì)應(yīng)求得的支持向量，即HVA=H(A)，SVA=S(A)，可得出如下結(jié)論[5]：

1)SVA?HVA;

2)如果有A+表示A的同類(lèi)增量樣本集，且滿足A∩A+=?，則有：

S(SVA∪A+)≠S(A∪A+);

3)S(HVA∪A+)=S(A∪A+).

也就是說(shuō)，殼向量集可以更好地表示原訓(xùn)練集中所包含的分類(lèi)信息，因此與其它使用支持向量集代替原訓(xùn)練集的常用SVM增量學(xué)習(xí)策略相比，使用殼向量可大大提高訓(xùn)練速度.

1.2 殼向量的求解算法

1)初始化V0為包含給定訓(xùn)練集X在內(nèi)的最小超球面上的點(diǎn)集，即V0={Sphere(X)}，且使V=?；

2)對(duì)訓(xùn)練集X按照到超球中心的距離進(jìn)行降序排列得：X*={SphereSort(X)}-V0；

3)whileX*≠? do,

有x∈X*，更新X*=X*-{x},

if (F(x,V)= = false)，則使V0=V0∪{x}；

4)whileV0≠? do,

取x∈V0；

if(F(x,V0-{x})= = false)，則使V=V∪{x}.

由上述步驟得到如圖2所示的凸殼.

圖2 基于超球面的凸殼示意圖

2 支持向量機(jī)增量學(xué)習(xí)算法

2.1 算法思想

1)在增量學(xué)習(xí)之前，建立對(duì)初始樣本有選擇的淘汰機(jī)制[6].在初始樣本集中選取一部分最有可能屬于學(xué)習(xí)后所得支持向量集的樣本集(即殼向量集)作為訓(xùn)練集，從而遺忘或丟棄對(duì)支持向量集沒(méi)有影響的樣本.再針對(duì)殼向量集進(jìn)行SVM訓(xùn)練，求得支持向量集.

2)在利用先前得到的知識(shí)來(lái)對(duì)新增樣本進(jìn)行訓(xùn)練時(shí)，根據(jù)KKT條件，淘汰已被原分類(lèi)器所識(shí)別的樣本，保留違背KKT條件的新增樣本，并上原殼向量集求取新的殼向量集并進(jìn)行SVM訓(xùn)練，得到新的分類(lèi)決策函數(shù).重復(fù)上述步驟，即可連續(xù)對(duì)多批新增樣本進(jìn)行增量學(xué)習(xí).

2.2 算法流程與算法描述

對(duì)于初始訓(xùn)練數(shù)據(jù)集A，可分為A+和A-兩類(lèi)待訓(xùn)練樣本，每一類(lèi)樣本所對(duì)應(yīng)的分類(lèi)器和支持向量集分別為φA和SVA，增量學(xué)習(xí)的目的在于，在處理增量樣本集B之后得到A∪B上的支持向量機(jī)φ和支持向量集SV.主要過(guò)程描述見(jiàn)圖3.

圖3 增量學(xué)習(xí)流程圖

算法描述及運(yùn)行步驟如下：

(1)分別針對(duì)數(shù)據(jù)集A+和A-求殼向量集HVA+和HVA-，令HVA=HVA+∪HVA-；

(2)將(1)所求得的殼向量集HVA作為新的訓(xùn)練數(shù)據(jù)集，運(yùn)用SVM算法得到一個(gè)分類(lèi)器φA和對(duì)應(yīng)的支持向量集SVA，以及由φA決定的KKT條件；

(3)構(gòu)造工作集B′，B′為新增訓(xùn)練樣本集B中所有違反φA定義的KKT條件的樣本；

(4)如果B′=?，則轉(zhuǎn)至步驟(7)；

(5)如果B≠?，則令HVA=HVA∪B′，作為新訓(xùn)練樣本集，重新得到A+和A-，再針對(duì)A+和A-求新的殼向量集HVA=HVA+∪HVA-；

(6)返回步驟(2)，重復(fù)執(zhí)行；

(7)輸出更新后的φA和SVA；

(8)得到最終的支持向量機(jī)φ和支持向量集SV，算法結(jié)束.

3 數(shù)據(jù)仿真

為了驗(yàn)證該算法的有效性，這一部分將對(duì)實(shí)際數(shù)據(jù)進(jìn)行仿真.其實(shí)驗(yàn)數(shù)據(jù)集Haberman來(lái)自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)，具體情況如表1所示.

表1 仿真所采用的樣本數(shù)據(jù)集

仿真實(shí)驗(yàn)中支持向量機(jī)的訓(xùn)練是采用Matlab下的SVM工具箱，求取樣本集的殼向量是采用Matlab下的Qhull工具箱(如圖4所示).為了驗(yàn)證所提出的增量學(xué)習(xí)算法的有效性，本實(shí)驗(yàn)在Haberman數(shù)據(jù)集上，對(duì)4種不同的增量學(xué)習(xí)方法(算法)進(jìn)行了比較分析，算法1為標(biāo)準(zhǔn)支持向量機(jī)算法，即每次增量學(xué)習(xí)都對(duì)全體樣本求解分類(lèi)器的方法；算法2是常用的以支持向量集(SVs)代替原始樣本的方法進(jìn)行增量學(xué)習(xí)；算法3是基于KKT條件的增量學(xué)習(xí)；算法4為本文所提出的基于殼向量和KKT條件的漸進(jìn)式增量學(xué)習(xí)算法.

圖4 對(duì)Haberman數(shù)據(jù)集所求得的凸包

先從數(shù)據(jù)集中隨機(jī)抽取70%的樣本作為初始樣本集，然后分別進(jìn)行3次增量學(xué)習(xí)，每次增加剩余樣本的1/3，在增量學(xué)習(xí)完成后用全部樣本來(lái)檢驗(yàn)分類(lèi)的效果.在Haberman數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如表2～表5所示，SV表示支持向量，HV表示殼向量，t(s)表示訓(xùn)練時(shí)間，P表示訓(xùn)練精度.

表2 初始學(xué)習(xí)的仿真結(jié)果

表3 第1次增量學(xué)習(xí)后的結(jié)果

表4 第2次增量學(xué)習(xí)后的結(jié)果

表5 第3次增量學(xué)習(xí)后的結(jié)果

從上述表和圖的結(jié)果可以得出：基于支持向量的增量學(xué)習(xí)算法和本文所提出增量學(xué)習(xí)算法的訓(xùn)練時(shí)間差不多，甚至還略少一點(diǎn)，但訓(xùn)練精度低于本文所提出的增量學(xué)習(xí)算法；基于KKT條件的增量學(xué)習(xí)算法訓(xùn)練時(shí)間長(zhǎng)，且在訓(xùn)練精度方面略低于本文所提出的增量學(xué)習(xí)算法.雖然算法3和本算法都利用了KKT條件來(lái)選取樣本，但是本算法卻沒(méi)用KKT條件對(duì)初始樣本集進(jìn)行操作，而是利用幾何意義上的殼向量集來(lái)代表原始訓(xùn)練集，這一策略使得待訓(xùn)練樣本中包含了一些普通樣本，還結(jié)合了經(jīng)過(guò)KKT條件檢驗(yàn)后的新增樣本一起再進(jìn)行訓(xùn)練，不僅保證了更高的分類(lèi)精度，也提高了學(xué)習(xí)效率，所以本算法是可行有效的.

4 結(jié)語(yǔ)

本文在分析比較了幾種具有代表性SVM增量學(xué)習(xí)算法的基礎(chǔ)上，提出了一種基于殼向量的支持向量機(jī)漸進(jìn)式增量學(xué)習(xí)算法，該算法在訓(xùn)練過(guò)程中對(duì)歷史樣本以及新增樣本較好地實(shí)現(xiàn)了有選擇性的遺忘淘汰機(jī)制，同時(shí)保證了良好的分類(lèi)精度，最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性.下一步的工作是將其擴(kuò)展到手寫(xiě)體數(shù)字、少數(shù)民族文字識(shí)別等更廣泛的實(shí)際應(yīng)用中去.

[1] 蕭 嶸，王繼成，孫正興，等.一種SVM增量學(xué)習(xí)算法a-ISVM[J].軟件學(xué)報(bào),2001,12(12): 1818-1824.

[2] 周偉達(dá),張 莉,焦李成.支撐矢量機(jī)推廣能力分析[J].電子學(xué)報(bào)，2001,29(5): 590-594.

[3] 李紅蓮，王春花，袁保宗，等.針對(duì)大規(guī)模訓(xùn)練集的支持向量機(jī)的學(xué)習(xí)策略[J].計(jì)算機(jī)學(xué)報(bào),2004,27(5):715-719.

[4] Dong J X,Krzyzak A,Suen C Y.Fast SVM training algorithm with decomposition on very large data sets[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(4): 603-618.

[5] Osuna E,Castro O D.Convex hull in feature space for support vector machines[C]//Francisco J G.Proceedings of 8th lbero-American Conference on Artificial Intelligence.Madrid: Springer,2002: 411-419.

[6] 白冬嬰，王曉丹，張宏達(dá)，等.對(duì)求殼向量算法的分析與實(shí)驗(yàn)[C]//李 映.第六屆全國(guó)信號(hào)與信息處理聯(lián)合學(xué)術(shù)會(huì)議.西安：陜西省信號(hào)處理學(xué)會(huì)，2007.