基于中心凸包算法與增量學(xué)習(xí)的SVM算法研究*

白東穎，王 剛，張 泚

（1.第二炮兵工程大學(xué)，西安 710025；2.空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安 710051；3.解放軍94402部隊，濟(jì)南 250002）

基于中心凸包算法與增量學(xué)習(xí)的SVM算法研究*

白東穎1，2，王 剛2，張 泚3

（1.第二炮兵工程大學(xué)，西安 710025；2.空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安 710051；3.解放軍94402部隊，濟(jì)南 250002）

基于計算幾何理論，在分析支持向量與凸包向量關(guān)系的基礎(chǔ)上，提出了一種基于中心凸包算法與增量學(xué)習(xí)的SVM學(xué)習(xí)算法。在確保分類器達(dá)到可靠精度的前提下，為解決學(xué)習(xí)中時耗過長的問題，在對當(dāng)前訓(xùn)練集計算凸包的基礎(chǔ)上采用歐式中心距離淘汰法對訓(xùn)練樣本進(jìn)一步精簡，并且每次進(jìn)行增量學(xué)習(xí)的樣本都包含前次訓(xùn)練樣本集中違背KKT條件的樣本，在UCI數(shù)據(jù)庫上進(jìn)行算法對比實驗，結(jié)果表明算法的可行性和有效性。

凸包，增量支持向量機(jī)，中心距離，KKT

0 引言

支持向量機(jī)［1］（Support Vector Machine，SVM）是一種以統(tǒng)計學(xué)習(xí)理論為基礎(chǔ)的機(jī)器學(xué)習(xí)技術(shù)，主要應(yīng)用于求解監(jiān)督學(xué)習(xí)［2］問題。在實際應(yīng)用中，訓(xùn)練樣本常常具有在線式增加的特點，這就要求分類器不斷地對新樣本重新訓(xùn)練，使得分類效率大大降低，而增量學(xué)習(xí)旨在獲得原訓(xùn)練樣本與新增樣本并集的最優(yōu)解，因此，對于不斷增長的數(shù)據(jù)集來說，支持向量機(jī)增量學(xué)習(xí)具有其獨特的優(yōu)勢。

當(dāng)前，對增量SVM算法的研究主要集中在如何保證分類精度與提高學(xué)習(xí)速度兩個方面。見文獻(xiàn)［3-12］。

由以上分析可知，如何對訓(xùn)練樣本有效淘汰在一定程度上影響了SVM分類精度與學(xué)習(xí)速度。本文分析了計算幾何［13］中構(gòu)成凸包的向量與支持向量之間的關(guān)系，采用了凸包算法與樣本的歐氏中心距離［14］概念結(jié)合進(jìn)行樣本篩選，依據(jù)KKT條件更新增量訓(xùn)練樣本，提出了一種利用中心凸包算法與增量學(xué)習(xí)的SVM快速學(xué)習(xí)算法，簡稱CQSVM。

1 SVM分類原理及支持向量與凸包向量的幾何關(guān)系

1.1 SVM分類原理

SVM是從線性最優(yōu)分類超平面發(fā)展而來，最優(yōu)分類面問題可以表示成如下的約束優(yōu)化問題［1］：

定義Lagrange函數(shù)為：

則原問題在原約束條件下可以轉(zhuǎn)化為如下凸二次規(guī)劃的對偶問題：

上述方程其實質(zhì)是一個不等式約束下的二次函數(shù)機(jī)制問題，存在唯一最優(yōu)解αi*，則：

αi*不為零時，所得到的樣本為支持向量。因此，最優(yōu)分類面中所采用的權(quán)系數(shù)向量是支持向量的線性組合，b*可通過約束條件求解，由此得到的最優(yōu)分類函數(shù)是：

1.2 支持向量和凸包向量的幾何關(guān)系

文獻(xiàn)［15］指出：尋找使2類間的分類邊界最大的最優(yōu)超平面等同于在2類數(shù)據(jù)相應(yīng)的凸包上尋找2個最近鄰點。2類線性可分樣本最優(yōu)分類面的幾何意義見圖1所示。

在線性可分的情況下，是由SV來確定SVM最優(yōu)分類面的位置。為確保最優(yōu)分類面能夠最大化2類樣本間的最小間隙，SV只可能在位于2類樣本集合邊界位置的樣本向量中產(chǎn)生。

凸包是指每一類訓(xùn)練集幾何意義上最邊緣的樣本［13］。SVM算法旨在尋求兩個凸集之間的最小距離最大化，SV一定出現(xiàn)在樣本集合的最邊緣位置。可以說，SV產(chǎn)生于樣本集的凸包上以及凸包周圍。當(dāng)SV確定后，最優(yōu)分類面的位置也就得到了確定。

第三，完善資本市場機(jī)制。完善綠色金融市場相關(guān)規(guī)定，優(yōu)化證券發(fā)行和準(zhǔn)入機(jī)制，降低綠色債券發(fā)行成本、拓寬發(fā)行渠道，擴(kuò)大綠色債券發(fā)行對生態(tài)產(chǎn)業(yè)的正效益，使企業(yè)直接融資更加容易，最終做到提高綠色金融支持效率。

2 KKT條件及支持向量變化情況分析

KKT條件（Karush-Kuhn-Tucher condition）［1］在約束優(yōu)化中具有重要作用。根據(jù)KKT條件，在最優(yōu)點，拉格朗日乘子與約束的積為0。取線性判別函數(shù)：

則對偶問題的最優(yōu)解α=［α1，α2，…，αl］使得每個樣本x滿足優(yōu)化問題的KKT條件為：

式中，非零的αi為SV?？紤]函數(shù)系g（x）=h，可知g（x）=0為分類面，g（x）=±1為分類間隔的邊界，其上的樣本即為SV。

定理1新增樣本加入后，一部分與KKT條件相違背的新增樣本將轉(zhuǎn)化為滿足KKT條件的樣本甚至SV；部分滿足KKT條件的新增樣本將轉(zhuǎn)化為SV；部分滿足KKT條件的原樣本集的非SV將轉(zhuǎn)化為SV；部分原SV將轉(zhuǎn)化為非SV。這就意味著，標(biāo)準(zhǔn)增量訓(xùn)練過程中，僅考慮新增樣本和原樣本集的SV集，而忽略原樣本集中的非SV集可能造成重要信息的丟失。因此，每次進(jìn)行增量訓(xùn)練時，訓(xùn)練樣本還應(yīng)包含上次訓(xùn)練樣本集中違背KKT條件的樣本。

3 基于中心凸包與增量學(xué)習(xí)的SVM算法

3.1 算法原理

為保證包含分類信息的訓(xùn)練樣本在篩選時被有效保留，同時考慮到原SV集可能受到新增樣本集的影響，在進(jìn)行新的增量學(xué)習(xí)過程中，將前次訓(xùn)練過程中與KKT條件相違背的樣本同本次新增樣本點一起作為當(dāng)前訓(xùn)練樣本集。同時，在對當(dāng)前訓(xùn)練集計算凸包的基礎(chǔ)上進(jìn)行訓(xùn)練樣本集篩選，采用歐式中心距離淘汰法將邊界凸包向量提取出來，作為增量SVM訓(xùn)練的訓(xùn)練集。

3.2 算法描述

3.2.1 符號說明

3.2.2 算法步驟

（1）對Qhull{X0}訓(xùn)練得到分類器Ω0。

（2）第k次增量學(xué)習(xí)（k=1，2，…，n）時，算法描述為：步驟1檢驗增量過程是否繼續(xù)，如果不繼續(xù)，轉(zhuǎn)步驟3，否則，執(zhí)行步驟2；步驟2求Xk-1的中心凸包向量CQhull{Xk-1}；步驟3計算Xk-1中違背KKT條件的樣本；步驟4令Xk=Ik+CQhull{Xk-1}+；步驟5用Xk訓(xùn)練獲得分類器Ωk。

（3）終止，輸出Ωk。

4 實驗分析

4.1 實驗數(shù)據(jù)及參數(shù)設(shè)置

實驗環(huán)境為Intel酷睿2.50 GHz，內(nèi)存2 GB的PC機(jī)，Matlab7.0平臺，采用libsvm-mat-2.91-1的工具包。為驗證算法的有效性，選取UCI數(shù)據(jù)庫中2類不同的數(shù)據(jù)進(jìn)行學(xué)習(xí)：①Breast-cancer數(shù)據(jù)集，選取訓(xùn)練樣本為300，測試樣本為300；②Artificial數(shù)據(jù)集，取訓(xùn)練樣本為600，測試樣本數(shù)為300，樣本類別數(shù)為2，2類中心歐式距離為3。

4.2 相關(guān)對比算法

方法1：IncHulSVM0（）。只采用凸包算法進(jìn)行訓(xùn)練集約簡；每次增量學(xué)習(xí)過程中，用本次計算的凸包向量與新增樣本一起求解分類器。

方法2：IncHulSVM1（）。只采用凸包算法進(jìn)行訓(xùn)練集約簡；每次增量學(xué)習(xí)過程中，用本次計算的凸包向量和前次訓(xùn)練樣本集中違背廣義KKT條件的樣本以及新增樣本點一起進(jìn)行分類器的求解。

方法3：IncHulCntr0（）。采用中心凸包算子進(jìn)行樣本約簡；每次進(jìn)行增量學(xué)習(xí)時，僅用本次計算的中心凸包向量與新增樣本點求解分類器。

方法4：標(biāo)準(zhǔn)增量SVM，記為SISVM。

4.3 實驗結(jié)果與分析

圖2和圖3是在Breast-cancer數(shù)據(jù)集上的實驗結(jié)果。圖4和圖5是基于Aritificial數(shù)據(jù)集的測試結(jié)果。實驗選用RBF核函數(shù)來確定訓(xùn)練時間，而分類精度是在不同核函數(shù)（Linear、Rbf）下求得的分類精度的平均值。

圖2 Breast-cancer數(shù)據(jù)集下本文算法與對比算法訓(xùn)練時間比較圖

圖3 Breast-cancer數(shù)據(jù)集下本文算法與對比算法學(xué)習(xí)精度比較圖

圖4 Artificial數(shù)據(jù)集下本文算法與對比算法訓(xùn)練時間比較圖

圖5 Artificial數(shù)據(jù)集下本文算法與對比算法學(xué)習(xí)精度比較圖

對以上實驗結(jié)果分析：①從訓(xùn)練時間上來說，對于Breast-cancer數(shù)據(jù)集，訓(xùn)練樣本數(shù)為300。由圖2可見，IncHulSVM0、IncHulCntr0與CQSVM訓(xùn)練時間較短，SISVM及IncHulSVM1耗時較長，由于選取的訓(xùn)練樣本集規(guī)模不大，因此，上述幾種方法在訓(xùn)練時間上都有不同程度的重疊，不能確定何種方式的訓(xùn)練速度最快。而對于Artificial數(shù)據(jù)集，訓(xùn)練樣本數(shù)為600，規(guī)模較大。由圖4可見，這些方法中，按時耗由小到大排序分別是：IncHulSVM0、IncHulCntr0、CQSVM、IncHulSVM1、SISVM；②從分類精度上來說，圖3與圖5表明，不管采用Artificial或者Breast-cancer數(shù)據(jù)集，CQSVM與SISVM的分類精度是最高的，并且兩者的分類精度近似。方法IncHulSVM0雖然耗時最短，但其分類精度也最低。方法IncHulCntr0與IncHulSVM1體現(xiàn)出近似性能，均高于方法 IncHulSVM0，但低于 CQSVM與SISVM。

CQSVM算法核心思想是提高SVM增量學(xué)習(xí)速度的同時盡量不降低分類精度。從訓(xùn)練時間的角度分析，在采用了凸包算法對訓(xùn)練樣本約簡后進(jìn)一步用中心距離比值來簡化訓(xùn)練樣本，提高訓(xùn)練速度；從分類精度方面來說，每次進(jìn)行增量訓(xùn)練的樣本都包含了前次訓(xùn)練樣本集中與廣義KKT條件相違背的樣本，體現(xiàn)了對新增樣本的合理利用，使得分類精度盡量不降低。

5 結(jié)束語

利用KKT條件，著重對SV集受到新增樣本的影響進(jìn)行了分析；從計算幾何角度指出尋找使2類間的分類邊際最大的最優(yōu)超平面等同于在兩類數(shù)據(jù)相應(yīng)的的凸包上尋找2個最近鄰點。提出了基于中心凸包算法與增量學(xué)習(xí)的SVM算法，該方法結(jié)合了凸包算法與中心距離淘汰法，同時每次進(jìn)行增量學(xué)習(xí)的樣本中都包含了前次訓(xùn)練樣本集中與KKT條件相違背的樣本。實驗表明，該算法能夠在保持較高分類精度的同時大大提高SVM增量學(xué)習(xí)的速度。

［1］Vapnik V.The Nature of Statistical Learning Theory［M］.New York：Springer Verlag，1995.

［2］王玨，周志華，周傲英.機(jī)器學(xué)習(xí)及其應(yīng)用［M］.北京:清華大學(xué)出版社，2006.

［3］Syed N，Liu H，Sung K.Incremental Learning with Support Vector Machines.［C］//Proceedings of the Workshop on SupportVector Machines atthe InternationalJoint Conference on Artificial Intelligence.Stockholm ，Sweden: Morgan Kaufmann，1999.

［4］文波，單甘霖，段修生.基于驅(qū)動錯誤準(zhǔn)則的SVM增量學(xué)習(xí)研究［J］.計算機(jī)技術(shù)與自動化，2012，31（3）:100-103.

［5］吳崇明，王曉丹，白冬嬰.基于類邊界殼向量的快速SVM增量學(xué)習(xí)算法［J］.計算機(jī)工程與應(yīng)用，2010，46（23）: 185-187.

［6］ RalaivolaL，dAlch-BucF.IncrementalSupportVector Machine Learning:A Local Approach［C］//Proc.of ICANN，01.Vienna，Austria:Springer，2001.

［7］牟琦，陳藝?yán)ぃ呅⑷?一種基于快速增量SVM的入侵檢測方法［J］.計算機(jī)工程，2012，38（12）:92-94.

［8］毛建洋，黃道.一種新的支持向量機(jī)增量算法［J］.華東理工大學(xué)學(xué)報（自然科學(xué)版），2006（8）:989-991.

［9］李忠偉，張健沛，楊靜.基于支持向量機(jī)的增量學(xué)習(xí)算法研究［J］.哈爾濱工程大學(xué)學(xué)報，2005，26（5）:643-646.

［10］王一，楊俊安，劉輝.一種基于內(nèi)殼向量的SVM增量式學(xué)習(xí)算法［J］.電路與系統(tǒng)學(xué)報，2011，16（6）:109-113.

［11］ Gert C，Tomaso P.Incremental and Decremental Support VectorMachine Learning ［C］//Adancesin Neural Information Processing Systems（NIPS*2000）.Cambridge，MA:MIT Press，2001.

［12］申豐山，張軍英，王開軍.使用模擬切削算法的SVM增量學(xué)習(xí)機(jī)制［J］.模式識別與人工智能，2010，23（4）: 491-500.

［13］周培德.計算幾何—算法分析與設(shè)計［M］.北京:清華大學(xué)出版社，2003.

［14］Zhang L，Zhou W D，Jiao L C.Pre-extracting Support Vectors for Support Vector Machine［C］//Proceeding of ICSP2000.Beijing:IEEE Press，2000.

［15］Theodorids S，Koutroumbas K.Pattern Recognition，Third Edition［M］.Beijing:China Machine Press，2006.

Study on SVM Algorithm using Center Convex Vector and Incremental Learning

BAI Dong-ying1，2，WANG Gang2，ZHANG Ci3
（1.The Second Artillery Engineering University，Xi’an 710025，China；
2.Air and Missile Defense College，Air Force Engineering University，Xi’an 710051，China；
3.Unit 94402 of PLA，Jinan 250002，China）

Based on analysis of the support vector geometry significance and convex vector relationship，a learning algorithm of fast incremental convex vector algorithm based on SVM is proposed.In order to enhance training speed while SVM incremental learning accuracy is ensured，the training set is acquired based on computing the convex vector of the center distance method in the training sample set，and each incremental training sample contains the last training sample set against the KKT conditions of the sample，various algorithms then are used for comparison experiment under the UCI standard database，the result shows the feasibility and validity of this algorithm.

convex hull，incremental support vector machine，center distance，Karush-Kuhn-Tucher

TP18

A

1002-0640（2015）03-0020-04

2014-01-15

2014-03-27

國家自然科學(xué)基金資助項目（61102109）

白東穎（1982- ），女，陜西寶雞人，博士。研究方向：智能信息處理。