茅嫣蕾,魏　赟,賈　佳

(1.上海理工大學 光電信息與計算機工程學院,上?！?00093;2.上海生物信息技術研究中心,上?！?01202)

?

一種基于KKT條件和殼向量的SVM增量學習算法

茅嫣蕾1,2,魏赟1,賈佳2

(1.上海理工大學 光電信息與計算機工程學院,上海200093;2.上海生物信息技術研究中心,上海201202)

摘要針對傳統(tǒng)支持向量機(SVM)增量算法,在學習過程中因基于局部最優(yōu)解而可能舍棄含隱性信息的非支持向量樣本,以及對于新增樣本需全部進行訓練的缺點,文中提出一種基于KKT條件和殼向量的SVM增量學習算法。該方法利用殼向量的特性保留了訓練樣本集中可能含隱性信息的非支持向量,并只將違反KKT條件的增量樣本加入新的訓練集,從而提高運算效率。通過對公共數(shù)據(jù)集Abalone和 Balance Scale的實驗表明,新算法在屬性列數(shù)較多的數(shù)據(jù)集上分類效果更明顯。

關鍵詞SVM;增量學習;KKT條件;殼向量

支持向量機(Support Vector Machines,SVM)是由Vapnik等人提出的一種有監(jiān)督的機器學習算法。其基于結(jié)構(gòu)風險最小化原則和統(tǒng)計學中的VC維理論,在解決非線性和高維問題時表現(xiàn)出良好的特性。近年來在文本分類[1]、目標識別[2]、時間序列的預測[3]等領域得到廣泛應用。與傳統(tǒng)的學習相比,增量學習在加入增量樣本進行新的訓練過程中充分利用歷史訓練結(jié)果,減少了訓練時間同時又降低了存儲空間[4]。

基于SVM的增量學習概念最早是由Syed提出的,在文獻[5]中提出了一種分塊增量學習SVM算法,該算法的基本思想是在每次增量學習后保留支持向量(Support Vector,SV),舍棄非支持向量,并將本次支持向量集與新增樣本作為下一次學習的訓練樣本。其在算法求解上仍使用標準的SVM,并未進行改進。每次訓練求得的支持向量集是局部最優(yōu)解,而每次將可能包含隱性信息的非支持向量集全部舍棄,會導致分類精度的下降。針對以上問題,已有一些研究者提出了一些改進方法。文獻[6～7]通過引入KKT條件,在新增樣本中篩選最有可能成為支持向量的樣本加入到新的訓練集中。文獻[8]通過兩次求解殼向量來提高SVM增量學習的分類精度。文獻[9]在簡單SVM增量學習的基礎上,提出一種基于遺忘因子T的SVM增量學習算法,對樣本有選擇的進行遺忘,從而提高訓練速度,降低存儲空間的占用。本算法利用KKT條件篩選新增樣本加入新的訓練集,以提高運算效率,利用殼向量的特點保留了非支持向量集中可能在下一次訓練中成為支持向量的殼向量,從而提高分類精確度。

1SVM理論

SVM的基本思想是通過用內(nèi)積函數(shù)定義的非線性變換將數(shù)據(jù)輸入空間變換到一個高維空間,然后在這個空間中求最優(yōu)線性分類面。假設存在樣本(x1,y1),…,(xl,yl),xi∈Rn,yi∈{+1,-1}為類別標號,l為樣本數(shù),n為輸入維數(shù),支持向量機要尋找一個最優(yōu)超平面f(x)=(w,x)+b,使得測試數(shù)據(jù)盡可能正確地分類。最優(yōu)超平面即在正確分類兩類樣本的同時,使得分類間隔margin最大,如圖1所示。

圖1　最優(yōu)超平面

對于線性可分的情況,可轉(zhuǎn)化成如下二次優(yōu)化問題,將其轉(zhuǎn)化為Lagrange函數(shù)并根據(jù)Wolfe對偶定義,得到最優(yōu)決策函數(shù)

(1)

對于非線性可分的情況,引入核函數(shù)K(xi,yi),將訓練樣本映射到一個高維線性特征空間。通過引入一個非負的松弛變量ξ,將最優(yōu)問題轉(zhuǎn)化為

(2)

s.t.yi((ω·xi)+b)+ξi≥1,i=1,2,…,l

ξ≥0,i=1,2,…,l

(3)

通過轉(zhuǎn)化為Lagrange函數(shù)并根據(jù)Wolfe對偶定義,最終得到?jīng)Q策函數(shù)

(4)

其中,K(xi,yi)為核函數(shù),通過非線性映射得到。

2改進的SVM增量學習

增量學習的過程中,其主要任務是利用歷史結(jié)果避免重復訓練,并得到了較高精確度的分類結(jié)果。傳統(tǒng)的SVM在增量學習的過程中主要是尋找支持向量集SV,用于下一次訓練。其在每次的增量訓練中得到的支持向量集SV是基于局部最優(yōu)解,從而導致可能將含有隱性信息的非支持向量全部舍棄。本文通過結(jié)合KKT條件和殼向量的特點來改進傳統(tǒng)的SVM增量學習,從而提高分類器的準確率。

2.1KKT條件

對于上述對偶問題中的最優(yōu)解α=[α1,α2,…,αl],使得每個樣本x滿足優(yōu)化問題的KKT條件為

K1+160—K1+310邊坡總長150 m，由于是開挖階段故以施工便道通行的工程車輛為主，平均車速約為Vv=20 km/h，日通過車次約Nv=360輛/日。計算得到人員時空概率PS∶T=0.1125。

(5)

定理1SVM中,α=0的樣本分布于分類間隔之外;0<α

由此可將上述KKT條件轉(zhuǎn)化為

(6)

定理2若新增樣本中存在某些違反KKT條件的樣本,則這些違反KKT條件的樣本中肯定存在新的支持向量;若新增樣本中不存在違背KKT條件的樣本,則新增樣本中肯定不存在新的支持向量。

定理3若新增樣本中存在違反KKT條件的樣本,則上次訓練結(jié)果中的非支持向量有可能轉(zhuǎn)化為支持向量。

由上述定理知,可根據(jù)KKT條件對新增樣本集進行篩選。對于新增樣本中違反KKT條件的樣本,說明原支持向量中不包含這部分信息,需將其與原非支持向量一同加入進行訓練。而對于新增樣本集中沒有違反原支持向量的KKT條件,說明已包含這部分信息,即為對分類無用的樣本,可進行舍棄。通過該種方式大幅減少了對新增樣本的學習,同時又不影響原支持向量所含的信息。

2.2殼向量

由前文對SVM機理的介紹可知,SVM在訓練的過程中尋找的是對分類起決定作用的支持向量的樣本。在對樣本訓練的過程中只有類邊界附近樣本有可能成為支持向量[10]。定義殼向量為所有位于訓練集中類邊界的樣本,即殼向量是樣本集凸頂點。求殼向量集合S的方法:首先求出給定樣本集中各類的最小超球體,然后以超球面上的點作為初始的殼向量,通過迭代方法求出其極點集合S0,最后從S0中逐步舍棄一些多余的內(nèi)點從而求出凸殼的殼向量集合[11]。

3算法設計與實驗分析

由于傳統(tǒng)的SVM增量學習每次通過訓練求得的支持向量集是局部最優(yōu)解,故每次舍棄的非支持向量中可能包含隱性信息,從而導致分類精度下降。本文針對這一問題本文在改進傳統(tǒng)SVM增量學習時利用KKT條件篩選新增樣本加入新的訓練集,利用殼向量可能成為支持向量的特性,保留了非支持向量中的殼向量部分,即可能含隱性信息的非支持向量,將其加入下一次訓練。

3.1算法的設計

設T0為初始樣本集,B為新增樣本集B={B1,B2,…,Bn},且T0∩B1∩B2∩…∩Bn=Φ。算法:

(1)使用標準的SVM對初始樣本集T0進行訓練,得到初始向量集SV0和決策函數(shù)f0;

(2)加入新增樣本集Bi,若i>n,算法終止,否則轉(zhuǎn)(3);

3.2實驗分析

為驗證本文算法的有效性,采用本文提出的基于KKT條件和殼向量的增量學習算法與傳統(tǒng)的SVM增量學習進行比較。實驗數(shù)據(jù)使用UCI數(shù)據(jù)庫中的Abalone數(shù)據(jù)集和BalanceScale數(shù)據(jù)集。實驗過程中核函數(shù)均選用徑向基函數(shù)(RadialBasisFunction,RBF)。訓練樣本數(shù)與測試樣本數(shù)比為3:1,如表1所示。在數(shù)據(jù)集Abalone上的每次增量學習樣本數(shù)為500,在數(shù)據(jù)集BalanceScale上每次增量學習樣本數(shù)為100,實驗結(jié)果如表2所示。

表1　實驗數(shù)據(jù)集

表2　實驗結(jié)果

由上述實驗可知,本文算法與傳統(tǒng)SVM增量學習算法相比,在數(shù)據(jù)集的屬性列數(shù)較少的Balance Scale數(shù)據(jù)集上都顯示出良好的分類特性。在數(shù)據(jù)集的屬性列數(shù)較多的Abalone數(shù)據(jù)集上,本文算法的分類精確度要高于傳統(tǒng)SVM增量學習算法,以上結(jié)果驗證了本文算法的有效性。

4結(jié)束語

本文分析了SVM的特性,探討了傳統(tǒng)SVM增量學習的不足之處。在此基礎上利用KKT條件以及殼向量的特性提出一種新的SVM增量學習算法。并在UCI數(shù)據(jù)庫中的Abalone數(shù)據(jù)集和Balance Scale數(shù)據(jù)集上驗證了本文算法的有效性。

參考文獻

[1]崔建明,劉建明,廖周宇.基于SVM算法的文本分類技術研究[J].計算機仿真,2013,30(2):299-302.

[2]David A,Lerner B.Support vector machine-based image classification for genetic syndrome diagnosis[J].Pattern Recognition Letters,2005,26(8):1029-1038.

[3]尹華,吳虹.最小二乘支持向量機在混沌時間序列中的應用[J].計算機仿真,2011,28(2):225-227.

[4]王元卓,靳小龍,程學旗.網(wǎng)絡大數(shù)據(jù):現(xiàn)狀與展望[J].計算機學報,2013,36(6):1125-1138.

[5]Ruping S.Incremental learning with support vector machines[C].DA USA:Proceedings IEEE International Conference on Data Mining,2001.

[6]Wu C,Wang X,Bai D,et al.Fast incremental learning algorithm of SVM on KKT conditions[C].SA USA:Proceedings of the 6th International Conference on Fuzzy Systems and Knowledge Discovery,IEEE Press,2009.

[7]吳崇明,王曉丹,白冬嬰,等.利用KKT條件與類邊界包向量的SVM增量學習算法[J].計算機工程與設計,2010,31(8):1792-1794.

[8]王一,楊俊安,劉輝,等.一種基于內(nèi)殼向量的SVM增量式學習算法[J].電路與系統(tǒng)學報,2011,16(6):109-113.

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

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

[11]薛貞霞.支持向量機及半監(jiān)督學習中若干問題的研究[D].西安:西安電子科技大學,2009.

A New Incremental SVM Learning Algorithm Based on KKT Conditions and Hull Vectors

MAO Yanlei1,2,WEI Yun1,JIA Jia2

(1.School of Optical-electrical and Computer Engineering,University of Shanghai for Science and Technology,

Shanghai 200093,China;2.Shanghai Center for Bioinformation Technology,Shanghai 201202,China)

AbstractThe traditional support vector machine (SVM) incremental algorithm in the learning process may give up the non-support vectors with implicit information,and requires the training of all the incremental samples.This paper presents a new incremental SVM learning algorithm based on KKT conditions and hull vectors.The algorithm makes use of the characteristics of hull vectors to retrain non-support vectors with implicit information,and it only add the samples violating the KKT conditions to the new training set.The experimental results from Abalone dataset and Balance Scale dataset show this algorithm has better classification effect in the datasets with more columns of properties.

KeywordsSVM;incremental learning;KKT conditions;hull vectors

中圖分類號SVM

文獻標識碼A

文章編號1007-7820(2016)02-038-04

doi:10.16180/j.cnki.issn1007-7820.2016.02.010

作者簡介:茅嫣蕾(1991—),女,碩士研究生。研究方向:機器學習等。

基金項目:國家自然科學基金資助項目(61170277);上海市教委科研創(chuàng)新基金資助項目(12YZ094)

收稿日期:2015- 06- 09