穩(wěn)健最小二乘單類支持向量機及其稀疏化方法

王瑞平，方云錄，何洪輝

(1.安陽工學(xué)院 計算機科學(xué)與信息工程學(xué)院，河南 安陽 455000；2.河南大學(xué) 民生學(xué)院，河南 開封 475001；3.河南大學(xué) 軟件學(xué)院，河南 開封475001)

0 引 言

單分類支持向量機(one class support vector machine，OCSVM)需要求解一個帶不等式約束的二次規(guī)劃問題，計算復(fù)雜度較高。針對此問題，有學(xué)者提出了最小二乘單類支持向量機[1,2](least square one class support vector machine，LS-OCSVM)，其基本思想與最小二乘支持向量機(least square support vector machine，LS-SVM)類似[3,4]，通過引入等式約束和最小二乘損失函數(shù)，將其轉(zhuǎn)化為一線性方程組的求解問題，大大提高了計算效率。

與LS-SVM類似，LS-OCSVM存在易受噪聲樣本影響、稀疏性差的問題。針對此問題，常采用普通LS-SVM方法對目標(biāo)樣本進行分類，然后根據(jù)第一步求得的樣本誤差值確定對應(yīng)樣本的權(quán)值，最后采用加權(quán)的LS-SVM方法對樣本進行再次分類。模型稀疏化采用迭代訓(xùn)練策略，當(dāng)模型的測試誤差不超過給定閾值時，對每個樣本的拉格朗日乘子的絕對值|αi|進行升序排序，在每次迭代計算中，去掉前5%個乘子所對應(yīng)的樣本，然后繼續(xù)在新的樣本集上進行訓(xùn)練并估計測試誤差，直至滿足稀疏化要求。余正濤等[5]提出一種基于主動學(xué)習(xí)的LSSVM稀疏化方法，首先采用核聚類選取初始樣本，建立一個LSSVM最小分類器，然后求解樣本在分類器作用下的分布，選擇最接近分類面的樣本并將其加入訓(xùn)練集建立新的分類器，重復(fù)上述過程直到模型精度滿足要求，以此建立部分樣本的LSSVM稀疏化模型。文獻[6]采用獨立成分分析(ICA)對語音特征降維，對降維后的語音樣本采用LSSVM構(gòu)建建模，實現(xiàn)基于ICA的快速剪枝方法，完成支持向量篩選。文獻[7-9]采用在線稀疏化策略，實現(xiàn)LSSVM的快速稀疏化。此外，Carvalho等[10]提出一種針對LS-SVM的兩步稀疏化方法，該方法是根據(jù)樣本到超平面的距離確定是否對樣本進行保留。本文提出一種穩(wěn)健加權(quán)的最小二乘單類支持向量機(robust LS-OCSVM，RLS-OCSVM)，采用普通最小二乘單類支持向量機獲取樣本訓(xùn)練誤差，并選用不同的權(quán)函數(shù)對樣本進行加權(quán)分類，最后通過迭代計算實現(xiàn)樣本分類。同時，提出一種模型的稀疏化方法(RLS-OCSVM-GA)，以訓(xùn)練精度最大化和支持向量最小化為目標(biāo)，采用多目標(biāo)遺傳算法實現(xiàn)模型的稀疏化。

1 穩(wěn)健最小二乘單類支持向量機

最小二乘單類支持向量機采用二次損失函數(shù)和等式約束，以訓(xùn)練樣本到超平面的距離最小化求解超平面，因此，大多數(shù)訓(xùn)練樣本將位于超平面附近，從而可以根據(jù)樣本到超平面的距離表示樣本與訓(xùn)練樣本的接近程度。

1.1 最小二乘單類支持向量機

最小二乘單類支持向量機是單類支持向量機的一種擴展，其目標(biāo)函數(shù)為

(1)

與OCSVM相比，不再具有ξi≥0約束，且松弛因子變?yōu)槠椒巾棥Ｒ肜窭嗜粘俗应羒，分別對w、ξ、ρ、αi求導(dǎo)并令其為0，則

(2)

上式可化簡為

(3)

其中,1=[1,1,…,1]T，α=[α1,α2,…,αn]T，Ω為核函數(shù)矩陣，Ωi,j=K(xi,xj)=φ(xi)Tφ(xj)。上式為線性方程組，計算速度較二次優(yōu)化問題大大提高。

求得的超平面為

(4)

1.2 穩(wěn)健最小二乘單類支持向量機

為得到穩(wěn)健的分類模型，基于LS-OCSVM的解，可以得到一個誤差變量ξi=αivn/2，則目標(biāo)函數(shù)可表示為

(5)

同樣對w、ξ、ρ、αi求導(dǎo)并令其為0，并化簡，則

(6)

為敘述方便，將上式改寫為

(7)

權(quán)值μi可由(非加權(quán))LS-OCSVM誤差項ξi得到，權(quán)函數(shù)可以采用Hampel等穩(wěn)健權(quán)函數(shù)

(8)

2 基于GA的最小二乘單類支持向量機稀疏化

標(biāo)準(zhǔn)的單類支持向量機所求得的拉格朗日系數(shù)αi中有較多0值，具有稀疏性，但是在LS-OCSVM中，由于最優(yōu)條件中含有αi=2μiξi/vn，因此不具有稀疏性。在非稀疏條件下，幾乎所有的訓(xùn)練樣本都被用于最終的決策函數(shù)，當(dāng)訓(xùn)練樣本較大時，將嚴(yán)重影響預(yù)測速度，所以稀疏化是LS-OCSVM的一項重要研究內(nèi)容。

稀疏化最理想的情況是在保持精度不降低的前提下盡量減小支持向量數(shù)，可以將其視為一個多目標(biāo)規(guī)劃問題，本文嘗試采用遺傳算法進行稀疏化。

對每個樣本值采用二進制編碼，“1”代表支持向量，“0”代表非支持向量。由式(7)可知，與稀疏化直接相關(guān)的是矩陣A，一般的剪枝方法是將非支持樣本在矩陣A中所對應(yīng)的行和列刪除，保留支持向量對應(yīng)的行和列，然后再求解拉格朗日系數(shù)，這種方法雖易于實現(xiàn)，但會導(dǎo)致樣本信息的丟失。本文根據(jù)染色體編碼，只將編碼“0”在矩陣A中所對應(yīng)的列刪除，保留其所在的行，從而最大限度地保留樣本信息。

稀疏化過程中，應(yīng)盡量滿足分類精度最大化和支持向量數(shù)最小化，遺傳算法的適應(yīng)度函數(shù)為

(9)

其中，σi為訓(xùn)練精度，ri為稀疏化比例，即非支持向量數(shù)與總樣本數(shù)之比，λ∈[0,1]為調(diào)節(jié)系數(shù)，用于調(diào)節(jié)訓(xùn)練精度與稀疏化在適應(yīng)度函數(shù)中所占的比例。

為使迭代過程快速收斂，采用啟發(fā)式設(shè)計，基于遺傳算法的穩(wěn)健最小二乘單類支持向量機稀疏化方法具體步驟如下：

(1)采用普通最小二乘單類支持向量機對樣本進行訓(xùn)練，得到初始樣本誤差；

(2)根據(jù)初始樣本誤差，計算樣本權(quán)值，由式(8)計算系數(shù)矩陣和樣本誤差；

(3)重復(fù)步驟(2)直至兩次迭代誤差小于閾值，得到系數(shù)矩陣A和初始分類精度σ；

(4)設(shè)置進化代數(shù)T，初始化代數(shù)t=0；

(5)產(chǎn)生初始種群P(t)，對每個樣本進行染色體編碼；

(6)根據(jù)染色體編碼，當(dāng)編碼為“0”時，刪除系數(shù)矩陣A中的對應(yīng)列，并由式(7)求解最小二乘支持向量機模型；

(7)計算每個個體的分類精度σi,t、稀疏化程度ri,t以及適應(yīng)度函數(shù)值fi,t；

(8)當(dāng)t

1)根據(jù)適應(yīng)度值選擇下一代個體；

2)按交叉概率進行交叉操作；

3)按變異概率進行變異操作；

4)令t=t+1，生成下一代種群P(t+1)并按步驟(6)、步驟(7)計算分類精度ai,t+1、稀疏化程度ri,t+1和適應(yīng)度函數(shù)值fi,t+1；

(9)選擇適應(yīng)度值最大的個體，其對應(yīng)的模型解即為需要求解的稀疏化模型參數(shù)。

需要特別指出的是，在染色體編碼時，第一個編碼應(yīng)始終為“1”，因為系數(shù)矩陣A中的第一行和第一列均為常數(shù)，不是樣本所對應(yīng)的行和列，因此不應(yīng)該被刪除。

3 實驗與分析

為驗證本文算法的有效性，采用一組UCI數(shù)據(jù)集作為分類對象，將數(shù)量較多的一類作為目標(biāo)類，另一類作為異常類，采用的數(shù)據(jù)見表1，括號中的數(shù)字為數(shù)量較少類的樣本數(shù)。為保證目標(biāo)數(shù)據(jù)的代表性，隨機選取80%目標(biāo)類樣本作為訓(xùn)練樣本，剩余的20%目標(biāo)樣本和全部異常樣本作為測試樣本。

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

將提出的算法與典型稀疏化方法進行對比分析，用于對比分析的典型稀疏化方法有文獻[10]的剪枝方法、Silva等[11]提出的GAS-LSSVM和MOGAS-LSSVM方法，但這3種稀疏化方法都是針對LSSVM模型提出的，而本文研究對象為單類支持向量機，為便于比較，將3種方法目標(biāo)函數(shù)改為對應(yīng)的單類支持向量機形式，其余稀疏化步驟不變，所得到的模型分別簡稱為P-LSOCSVM、GAS-LSOCSVM、MOGA-LSOCSVM。這些改進易于理解且較為簡單，故本文不再贅述。

RLS-OCSVM-GA稀疏化模型中取λ為1，因為當(dāng)λ在區(qū)間[0,1]之間變化時精度變化不大，但是稀疏化程度將隨著λ的增大而提高，而我們的目標(biāo)是在保證精度的前提下盡量得到稀疏化模型。遺傳算法均采用二進制編碼，進化代數(shù)為50，種群大小為20，每個變量的二進制長度為系數(shù)矩陣列數(shù)。每個實驗進行10次并取其精度和稀疏化的均值，各模型的超參數(shù)采用5-fold交叉驗證進行確定，實驗結(jié)果見表2，其中最優(yōu)結(jié)果用粗體標(biāo)識

(10)

由表2可知，在分類精度方面，P-LSOCSVM與RLS-OCSVM-GA的分類精度基本相當(dāng)，均優(yōu)于OCSVM、LS-OCSVM、GAS-LSOCSVM和MOGA-LSOCSVM，表明提出方法的分類性能具有較強的穩(wěn)健性。由于采用相似的權(quán)函數(shù)確定方法，因此P-LSOCSVM與RLS-OCSVM-GA的分類精度較為接近，但總體而言提出的方法在穩(wěn)健性方面優(yōu)于P-LSOCSVM，這是因為提出的方法在稀疏化過程中考慮了分類精度，在采用遺傳算法進行稀疏化的過程中通過不斷迭代保持甚至略微提高了分類精度。

在稀疏性方面，提出的RLS-OCSVM-GA方法略優(yōu)于MOGA-LSOCSVM，明顯優(yōu)于OCSVM、P-LSOCSVM、GAS-LSOCSVM，這是因為前兩種方法以分類精度最高和稀疏性最大為目標(biāo)，從而保證了種群在迭代的過程中模型向的稀疏化高的方向發(fā)展，而其余方法由于在目標(biāo)函數(shù)未考慮模型的稀疏性，導(dǎo)致其稀疏性不及前兩種方法，但是P-LSOCSVM、GAS-LSOCSVM在通過不斷迭代提高模型的分類精度的同時也剔除了系數(shù)矩陣的部分列向量，從而也在一定程度上保證了模型的稀疏性。

表2 分類精度與稀疏化程度

在方法的復(fù)雜度方面，LSOCSVM由于不需要迭代進行稀疏化，因此其復(fù)雜度最低，提出的方法采用迭代方式對稀疏化模型進行求解，其復(fù)雜度略高于OCSVM，但與其余的稀疏化方法相當(dāng)。

由以上分析可知，提出的RLS-OCSVM-GA方法在保持分類精度的同時，具有較好的稀疏性。

4 結(jié)束語

本文以提高最小二乘單類支持向量機的穩(wěn)健性與稀疏性為目標(biāo)，提出了基于迭代加權(quán)的最小二乘單類支持向量機，并給出了基于遺傳算法的稀疏化方法，與傳統(tǒng)方法相比，提出的方法具有以下優(yōu)勢：①通過權(quán)函數(shù)的不斷迭代保證了模型的穩(wěn)健性；②基于遺傳算法的稀疏化方法以分類精度最高和稀疏性最大為目標(biāo)，在稀疏化的過程中只刪除系數(shù)矩陣所對應(yīng)的列，最大限度地保持了樣本信息。實驗結(jié)果表明，本文提出的RLS-OCSVM-GA模型在穩(wěn)健性及稀疏性方面均優(yōu)于傳統(tǒng)方法。

參考文獻：

[1]Wang T,Chen J,Zhou Y,et al.Online least squares one-class support vector machines-based abnormal visual event detection[J].Sensors,2013,13(12):17130-17155.

[2]Uddin M S,Kuh A.Online least-squares one-class support vector machine for outlier detection in power grid data[C]//IEEE International Conference on Acoustics,Speech and Signal Processing.IEEE,2016:2628-2632.

[3]Huang X,Shi L,Suykens J A K.Asymmetric least squares support vector machine classifiers[J].Computational Statistics & Data Analysis,2014,70:395-405.

[4]Rebentrost P,Mohseni M,Lloyd S.Quantum support vector machine for big data classification[J].Physical Review Letters,2014,113(13):130503.

[5]YU Zhengtao,ZOU Junjie,ZHAO Xing,et al.Sparseness of least squares support vector machines based on active learning[J].Journal of Nanjing University of Science and Technology,2012,36(1):12-17(in Chinese).[余正濤,鄒俊杰,趙興,等.基于主動學(xué)習(xí)的最小二乘支持向量機稀疏化[J].南京理工大學(xué)學(xué)報(自然科學(xué)版),2012,36(1):12-17.]

[6]WANG Zhenzhen,ZHANG Xueying,LIU Xiaofeng.Sparse LSSVM and application in speech recognition[J].Computer Engineering and Design,2014,35(4):1303-1307(in Chinese).[王真真,張雪英,劉曉峰.稀疏LSSVM及其在語音識別中的應(yīng)用[J].計算機工程與設(shè)計,2014,35(4):1303-1307.]

[7]Cheng R,Song Y,Chen D,et al.Intelligent localization of a high-speed train using LSSVM and the online sparse optimization approach[J].IEEE Transactions on Intelligent Transportation Systems,2017,99:1-14.

[8]Gao Y,Shan X,Hu Z,et al.Extended compressed tracking via random projection based on MSERs and online LS-SVM learning[J].Pattern Recognition,2016,59(C):245-254.

[9]Wang B,Shi Q,Mei Q.Improvement of LS-SVM for time series prediction[C]//11th International Conference on Service Systems and Service Management.IEEE,2014:1-5.

[10]Carvalho B P R,Braga A P.IP-LSSVM:A two-step sparse classifier[J].Pattern Recognition Letters,2009,30(16):1507-1515.

[11]Silva D A,Silva J P,Neto A R R.Novel approaches using evolutionary computation for sparse least square support vector machines[J].Neurocomputing,2015,168:908-916.