張仙偉，邢佳瑤

(西安石油大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710065)

0 引 言

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

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

1 雙最小二乘支持向量數(shù)據(jù)描述

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

1.1 最小二乘支持向量機(jī)

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

(1)

以拉格朗日乘子αi≥0乘以每個(gè)等式約束，加入優(yōu)化目標(biāo)得到拉格朗日函數(shù)L。

(2)

根據(jù)KKT最優(yōu)解條件，置L對變量w,ξi,b,αi的偏導(dǎo)為零，得到的最優(yōu)解條件可以表述為如下線性方程組

(3)

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

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

(4)

1.2 支持向量數(shù)據(jù)描述

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

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

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

(5)

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

(6)

最小包圍超球的球心按照下式進(jìn)行計(jì)算

(7)

最小包圍超球半徑根據(jù)下式計(jì)算

(8)

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

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

(9)

1.3 雙最小二乘支持向量數(shù)據(jù)描述

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

(10)

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

構(gòu)造上述規(guī)劃的拉格朗日函數(shù)

(11)

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

對上述拉格朗日函數(shù)關(guān)于所含變量求導(dǎo)，并置變量的偏導(dǎo)數(shù)為零，得到

(12)

將所得等式帶入目標(biāo)函數(shù)，得到如下問題

(13)

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

KKT最優(yōu)性條件整理為

(14)

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

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

(15)

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

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

(16)

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

(17)

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

(18)

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

2 數(shù)值試驗(yàn)

為驗(yàn)證DLSSVDD的性能，選取不同規(guī)模的基準(zhǔn)數(shù)據(jù)集和正態(tài)分布數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。所有實(shí)驗(yàn)均在P4CPU，3.06 GHz，內(nèi)存為0.99 GB的PC機(jī)上進(jìn)行；所有程序均采用Matlab 7.01編寫。

例1 正態(tài)分布數(shù)據(jù)集

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

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

圖1 DLSSVDD的分類精度

例2 Diabetics數(shù)據(jù)集

Diabetics為含有768個(gè)樣本的8維數(shù)據(jù)集。隨機(jī)選取468個(gè)樣本參與訓(xùn)練，其余300個(gè)參與測試。為避免隨機(jī)性，進(jìn)行10次隨機(jī)抽取實(shí)驗(yàn)，并列出訓(xùn)練集和測試集上的平均結(jié)果。

實(shí)驗(yàn)選取徑向基核函數(shù)，懲罰參數(shù)取為C=1；隨著徑向基核參數(shù)的變化，以分類精度和運(yùn)行時(shí)間作為評價(jià)指標(biāo)，對比DLSSVDD和SVDD的分類表現(xiàn)，并列出相應(yīng)結(jié)果見表1。

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

表1 DLSSVDD和SVDD的比較

例2 Breast Cancer和Banana數(shù)據(jù)集

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

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

表2 不同算法的表現(xiàn)

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

例3 大規(guī)模數(shù)據(jù)集

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

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

由表3顯見：DLSSVDD的分類精度與SVDD的相當(dāng)，而分類時(shí)間遠(yuǎn)遠(yuǎn)低于SVDD的分類時(shí)間；同時(shí)這種分類精度和分類時(shí)間上的優(yōu)勢在樣本規(guī)模較大時(shí)，也即參與訓(xùn)練的樣本集數(shù)目較多時(shí)，體現(xiàn)的更為明顯。

表3 SVDD與DLSSVDD的分類性能

以2 000個(gè)數(shù)據(jù)集為例，DLSSVDD的分類時(shí)間9.57 s是SVDD分類時(shí)間12.26 s的78.06%；當(dāng)樣本數(shù)目增加到10 000時(shí)，DLSSVDD的分類時(shí)間60.08 s是后者12.26 s的18.69%。

3 結(jié) 論

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

2)DLSSVDD具有比SVDD略高的分類精度。這是因?yàn)镈LSSVDD同時(shí)考慮了正類樣本和負(fù)類樣本，根據(jù)待測樣本與2個(gè)最小包圍超球修心的距離，通過一個(gè)分段函數(shù)來判斷類別標(biāo)簽。這樣更符合樣本的空間分布。

3)與SVDD相比，DLSSVDD分類時(shí)間方面的優(yōu)勢在大規(guī)模樣本集上體現(xiàn)的更為明顯。以正態(tài)分布數(shù)據(jù)集上的數(shù)值實(shí)驗(yàn)為例，DLSSVDD保持了較高的分類精度，而分類時(shí)間隨樣本規(guī)模的變化而增加的幅度并不明顯。這得益于DLSSVDD僅通過求解一個(gè)線性方程組得到最優(yōu)解，而避免了傳統(tǒng)SVDD算法對凸二次規(guī)劃的求解。鑒于DLSSVDD在這3個(gè)方面的優(yōu)勢，下一步研究方向?qū)⑼貙扗LSSVDD在大規(guī)模樣本集的分類問題以及奇異值檢測等實(shí)際問題中的應(yīng)用。