覃 俊，許 斐

(中南民族大學 計算機科學學院，武漢 430074)

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

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

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

1 殼向量

包含某一類訓練樣本集在內的最小凸集(特征空間中是一個多面體)稱為訓練集的凸殼，簡稱為凸殼.

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

■表示訓練集A的殼向量 ●表示訓練集B的殼向量

1.1 支持向量與殼向量

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

1)SVA?HVA;

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

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

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

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

1.2 殼向量的求解算法

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

2)對訓練集X按照到超球中心的距離進行降序排列得：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 支持向量機增量學習算法

2.1 算法思想

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

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

2.2 算法流程與算法描述

對于初始訓練數據集A，可分為A+和A-兩類待訓練樣本，每一類樣本所對應的分類器和支持向量集分別為φA和SVA，增量學習的目的在于，在處理增量樣本集B之后得到A∪B上的支持向量機φ和支持向量集SV.主要過程描述見圖3.

圖3 增量學習流程圖

算法描述及運行步驟如下：

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

(2)將(1)所求得的殼向量集HVA作為新的訓練數據集，運用SVM算法得到一個分類器φA和對應的支持向量集SVA，以及由φA決定的KKT條件；

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

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

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

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

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

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

3 數據仿真

為了驗證該算法的有效性，這一部分將對實際數據進行仿真.其實驗數據集Haberman來自UCI機器學習數據庫，具體情況如表1所示.

表1 仿真所采用的樣本數據集

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

圖4 對Haberman數據集所求得的凸包

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

表2 初始學習的仿真結果

表3 第1次增量學習后的結果

表4 第2次增量學習后的結果

表5 第3次增量學習后的結果

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

4 結語

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

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

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

[3] 李紅蓮，王春花，袁保宗，等.針對大規(guī)模訓練集的支持向量機的學習策略[J].計算機學報,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] 白冬嬰，王曉丹，張宏達，等.對求殼向量算法的分析與實驗[C]//李 映.第六屆全國信號與信息處理聯合學術會議.西安：陜西省信號處理學會，2007.