雙最小二乘支持向量數據描述

張仙偉，邢佳瑤

(西安石油大學 計算機學院，陜西 西安 710065)

0 引 言

TAX提出支持向量數據描述(support vector data description，SVDD)[1]算法，在單值分類領域得到了廣泛應用。陸從德將SVDD推廣至分類領域，根據數據的描述邊界進行分類并采用乘性規則求解[2]。從提高SVDD求解速度入手，ZHAO F等構造一種簡化算法，尋求特征空間中支持向量的基函數以提高測試速度[3]。LAN J C將SVDD算法拓寬應用于在模擬電路，并通過獨立成分分析進行特征選擇以提高訓練速度[4]。NIAZMARDI S等利用SVDD改進模糊C均值聚類算法，并用于無監督高光譜數據分類[5]。PENG X J等設計避免矩陣求逆的運算方法，提高傳統SVDD的分類精度[6]。劉富等從提高分類精度角度，設計根據位置分布構造可變懲罰參數的方法[7]。CAO J等拓寬SVDD用于癌癥多分類的快速基因選擇方法[8]。REKHA A G等根據SVDD目標函數的梯度下降方向找到球心的近似原像，避免了拉格朗日乘子的計算問題并降低了復雜度[9]。陶新民等設計密度敏感最大間隔SVDD算法，根據樣本在空間的分布，解決不均衡的數據分類問題[10]。GUO Y等將SVDD與多核學習結合構造多分類器[11]。引入集成學習理念，Pranjal利用斜二叉樹和SVDD構造改進的多分類算法[12]。GORNITZ N進一步應用集成學習思想[13]，利用SVDD和K均值聚類構造單值分類算法。YIN L L等將SVDD應用于奇異值檢測，構造具有較好魯棒性的積極學習算法[14]。在無線傳感器網絡領域，HUAN Z等設計SVDD算法進行奇異值檢測[15]，而SHI P等在此基礎上設計改進的SVDD算法[16]。陶新民等針對故障檢測設計一種不均衡的最大間隔SVDD模型[17]。WANG K Z等設計針對污染數據的魯棒支持向量域描述算法[18]。為了進一步提高SVDD的訓練速度和降低計算復雜度，ZHANG L等利用超球球心和半徑之比選擇特征[19]。ZHENG S F修改SVDD模型的拉格朗日函數為可微凸函數，并設計一種迭代算法求解，更加快速有效且分類精度較高[20]。高羅瑩等在室內無線局域網中引入SVDD算法[21]，解決了已有檢測技術的適應性較差和檢測性能較低的問題。呂國俊等學者結合蟻群優化算法進行相似重復記錄檢測[22]。這些研究取得了一定的進展，拓寬了SVDD的應用領域，或提高SVDD的分類精度，或降低SVDD的復雜度，或增加SVDD的魯棒性。然而，設計過程中往往需要借助其余算法，例如獨立成分分析、多核學習、K均值聚類、粒子群優化等，計算較為復雜。

如果構造出既能夠縮短運行時間、提高可處理問題的規模，又能夠保證較高的分類精度的分類算法，則能有效提高算法在各個領域的運算效率。最小二乘支持向量機將標準算法的不等式約束改為等式約束，具有計算簡單、分類精度高的優點[23]；對SVDD進行分片[24]和對SVM進行分區域處理[25]的思想，有效提高了相應算法的分類精度。筆者受最小二乘思想和分塊處理思想的啟發，構造雙最小二乘支持向量數據描述DLSSVDD；將支持向量數據描述中的不等式約束修改為等式約束，同時結合樣本到2個最小包圍超球的距離設計分區域的分類準則。DLSSVDD僅需求解一個線性方程組而非凸二次規劃，訓練僅對一類樣本進行且考慮樣本在空間的位置分布；預計DLSSVDD具有較低復雜度、較短的分類時間、較高的分類精度。

1 雙最小二乘支持向量數據描述

簡要給出最小二乘支持向量機和支持向量數據描述的工作原理。

1.1 最小二乘支持向量機

s.t.yi[w·φ(xi)+b]=1-ξi,i=1,…,l

(1)

以拉格朗日乘子αi≥0乘以每個等式約束，加入優化目標得到拉格朗日函數L。

(2)

根據KKT最優解條件，置L對變量w,ξi,b,αi的偏導為零，得到的最優解條件可以表述為如下線性方程組

(3)

這里Ωij=yiyjk(xi,xj)，I為單位矩陣；k(xi,xj)=φ(xi)Tφ(xj)為核函數，y=[y1,…,yl]T,e=[1,…,1]T。

根據線性方程組(3)的解α和b，構造分類判別函數

(4)

1.2 支持向量數據描述

記{xi}(i=1,…,N)為n維空間Rn中的目標類樣本，SVDD求取一個半徑最小的超球來覆蓋全體目標類樣本。由于樣本并非總是球形分布，SVDD通過非線性映射φ∶x→φ(x)將樣本投影到一個高維的特征空間。SVDD對樣本xi引入松弛變量ξi>0以放松約束條件，并引入正比于違反約束總量的懲罰參數C>0。記最小包圍超球的半徑和球心分別為R和a，SVDD在非線性空間中求解如下凸二次規劃

s.t.(φ(xi)-a)T(φ(xi)-a)≤R2+ξi,

ξi≥0,i=1,…,N

(5)

SVDD采用Lagrange乘子法，求解(5)的對偶規劃得到原問題的解

(6)

最小包圍超球的球心按照下式進行計算

(7)

最小包圍超球半徑根據下式計算

(8)

如果待測樣本z到最小包圍超球球心的距離平方小于超球半徑R2，接受該測試樣本為目標類；否則，拒絕該樣本，將其作為非目標類。

‖φ(z)-a‖2≤R2?

(9)

1.3 雙最小二乘支持向量數據描述

s.t.[φ(xi)-a+]T[φ(xi)-a+]=[R+]2+ξi,ξi≥0,i=1,…,N

(10)

這里R+(R-)和a+(a-)為正(負)類樣本最小包圍超球S1(S2)的半徑和球心；ξi為樣本xi的松弛。

構造上述規劃的拉格朗日函數

(11)

這里R+和a+為正類樣本最小包圍超球S1的半徑和球心；ξi為樣本xi的松弛。

對上述拉格朗日函數關于所含變量求導，并置變量的偏導數為零，得到

(12)

將所得等式帶入目標函數，得到如下問題

(13)

這里α=[α1,α2,L,αN]T，IN是N×N階的單位陣;K=[k(x1,x1),k(x1,x2),…,k(xN,xN)]為核矩陣，K(xp，xq)=φ(xp)·φ(xq)為核函數。

KKT最優性條件整理為

(14)

式中Φ為對核矩陣K進行正交分解所得矩陣，也即非線性映射矩陣。

根據式(14)求得的最優解，得到正類樣本的最小包圍超球半徑的計算公式

(15)

給定測試樣本z，其與超球球心的距離按照如下2式計算。

d1=D(z,S1)=‖φ(z)-a+‖2

(16)

d2=D(z,S2)=‖φ(z)-a-‖2

(17)

給定待測樣本z，雙最小二乘支持向量數據描述以如下函數作為分類決策函數

(18)

式中R1=R+，R2=R-,S1=(R+,a+)為正類樣本的最小包圍超球；S2=(R-,a-)為負類樣本的最小包圍超球。

2 數值試驗

為驗證DLSSVDD的性能，選取不同規模的基準數據集和正態分布數據集進行實驗。所有實驗均在P4CPU，3.06 GHz，內存為0.99 GB的PC機上進行；所有程序均采用Matlab 7.01編寫。

例1 正態分布數據集

在二維空間中，調用Matlab中的mvnrnd 函數生成滿足正態分布的正類和負類樣本各250個。正負類樣本的均值分別取為μ1=[0.4,0.8]和μ2=[0.8,0.4]，協方差矩陣均取為單位矩陣；數據集利用r=mvnrnd(mu，SIGMA，250)生成，其中mu為均值，SIGMA為協方差矩陣，250為樣本總數。

為了驗證DLSSVDD的分類精度，選取徑向基核函數K(x,y)=exp(-‖x-y‖2/σ2)進行數值實驗，取徑向基核參數σ=0.5，并取懲罰參數為C=1。視正類樣本作為目標類(Target)，其余樣本作為奇異值類(Outlier)。圖1給出了樣本集的分布，以及算法DLSSVDD對目標類和奇異值類的分類精度。

圖1 DLSSVDD的分類精度

例2 Diabetics數據集

Diabetics為含有768個樣本的8維數據集。隨機選取468個樣本參與訓練，其余300個參與測試。為避免隨機性，進行10次隨機抽取實驗，并列出訓練集和測試集上的平均結果。

實驗選取徑向基核函數，懲罰參數取為C=1；隨著徑向基核參數的變化，以分類精度和運行時間作為評價指標，對比DLSSVDD和SVDD的分類表現，并列出相應結果見表1。

從表1可以看出，對于不同的核參數取值，DLSSVDD的分類精度和分類時間均比SVDD要低。同時可以看到，當核寬參數從σ=0.1增加到σ=0.5時，2種算法的分類精度均隨核參數的增加而降低，只是變化幅度不同；SVDD分類精度的變化幅度約為5.6%；而DLSSVDD分類精度的變化幅度約為2.3%。

表1 DLSSVDD和SVDD的比較

例2 Breast Cancer和Banana數據集

另取UCI數據集中的Breast Cancer和Banana數據集進行測試。前者為包含277個樣本的9維數據集，隨機選取200個參與訓練，其余77個參與測試。后者為包含5 300個樣本的2維數據集，隨機抽取400個樣本參與訓練，其余參與測試。

為便于比較，對不同算法設置相同的參數，均取徑向基核函數，取懲罰參數為C=1，核寬參數為σ=0.1；列出不同算法在訓練集和測試集上的平均分類精度和分類時間見表2，并將最優分類結果加黑表出。

表2 不同算法的表現

由表2看出，DLSSVDD在不同的數據集上均具有最高的分類精度和最短的分類時間。由于Banana數據集的測試集規模較大，在其上的分類精度可以代表算法的泛化能力；不妨以Banana數據集為例展開分析。DLSSVDD的分類精度分別比SVM、LSSVM和SVDD高1.76%，2.64%和0.22%；而分類時間依次是三者的16.51%，49.30%和77.43%。顯見，DLSSVDD對訓練精度提高的幅度較低，在分類時間上具有著優勢。

例3 大規模數據集

本例依舊調用Matlab中的Mvnrnd 函數生成滿足正態分布的二維空間數據集，并保持正類和負類樣本的的數據均等。為了驗證算法在大規模數據集上的分類表現，依次增加正類和負類樣本的數目，并隨機交換部分樣本的正負號，使得有5%的重合。正類和負類樣本的均值分別取為μ1=[0.2,0.6]和μ2=[0.6,0.2]，協方差矩陣依舊取單位矩陣，正態分布數據集的規模為2 000，4 000，8 000和10 000。

隨機選取50%的樣本參與訓練，其余參與測試；取10次隨機抽取實驗的平均結果。設置懲罰參數C=1，取徑向基核函數并取核寬參數σ=1；表2對比給出不同算法的分類性能。

由表3顯見：DLSSVDD的分類精度與SVDD的相當，而分類時間遠遠低于SVDD的分類時間；同時這種分類精度和分類時間上的優勢在樣本規模較大時，也即參與訓練的樣本集數目較多時，體現的更為明顯。

表3 SVDD與DLSSVDD的分類性能

以2 000個數據集為例，DLSSVDD的分類時間9.57 s是SVDD分類時間12.26 s的78.06%；當樣本數目增加到10 000時，DLSSVDD的分類時間60.08 s是后者12.26 s的18.69%。

3 結 論

1)DLSSVDD具有比SVDD更短的分類時間。DLSSVDD在分類時間上具有明顯優勢，一方面是因為DLSSVDD減少了參與訓練的樣本規模，僅需帶入單一類別的樣本進行訓練，而不需要像SVDD那樣帶入全體樣本參與訓練；另一方面是因為DLSSVDD將支持向量數據描述中的不等式約束改為等式約束，采用類似最小二乘支持向量機的思想，通過求解一個線性方程組得到最優解。

2)DLSSVDD具有比SVDD略高的分類精度。這是因為DLSSVDD同時考慮了正類樣本和負類樣本，根據待測樣本與2個最小包圍超球修心的距離，通過一個分段函數來判斷類別標簽。這樣更符合樣本的空間分布。

3)與SVDD相比，DLSSVDD分類時間方面的優勢在大規模樣本集上體現的更為明顯。以正態分布數據集上的數值實驗為例，DLSSVDD保持了較高的分類精度，而分類時間隨樣本規模的變化而增加的幅度并不明顯。這得益于DLSSVDD僅通過求解一個線性方程組得到最優解，而避免了傳統SVDD算法對凸二次規劃的求解。鑒于DLSSVDD在這3個方面的優勢，下一步研究方向將拓寬DLSSVDD在大規模樣本集的分類問題以及奇異值檢測等實際問題中的應用。