王瑞平，方云錄，何洪輝

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

0 引 言

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

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

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

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

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

最小二乘單類支持向量機是單類支持向量機的一種擴展，其目標函數為

(1)

與OCSVM相比，不再具有ξi≥0約束，且松弛因子變?yōu)槠椒巾?。引入拉格朗日乘子αi，分別對w、ξ、ρ、αi求導并令其為0，則

(2)

上式可化簡為

(3)

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

求得的超平面為

(4)

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

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

(5)

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

(6)

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

(7)

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

(8)

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

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

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

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

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

(9)

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

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

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

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

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

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

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

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

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

(8)當t

1)根據適應度值選擇下一代個體；

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

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

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

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

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

3 實驗與分析

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

表1 實驗數據集

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

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

(10)

由表2可知，在分類精度方面，P-LSOCSVM與RLS-OCSVM-GA的分類精度基本相當，均優(yōu)于OCSVM、LS-OCSVM、GAS-LSOCSVM和MOGA-LSOCSVM，表明提出方法的分類性能具有較強的穩(wěn)健性。由于采用相似的權函數確定方法，因此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，這是因為前兩種方法以分類精度最高和稀疏性最大為目標，從而保證了種群在迭代的過程中模型向的稀疏化高的方向發(fā)展，而其余方法由于在目標函數未考慮模型的稀疏性，導致其稀疏性不及前兩種方法，但是P-LSOCSVM、GAS-LSOCSVM在通過不斷迭代提高模型的分類精度的同時也剔除了系數矩陣的部分列向量，從而也在一定程度上保證了模型的稀疏性。

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

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

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

4 結束語

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

參考文獻：

[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).[余正濤,鄒俊杰,趙興,等.基于主動學習的最小二乘支持向量機稀疏化[J].南京理工大學學報(自然科學版),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及其在語音識別中的應用[J].計算機工程與設計,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.