梁錦錦

(1.西安石油大學(xué) 理學(xué)院，陜西 西安 710065；2.陜西師范大學(xué) 教育學(xué)院，陜西 西安 710062)

0 引 言

支持向量數(shù)據(jù)描述(support vector data description, SVDD)被廣泛用于單值分類和奇異值檢測[1,2]。文獻(xiàn)[3]利用模糊C均值找到關(guān)鍵特征進(jìn)而構(gòu)造一種高效SVDD算法；文獻(xiàn)[4]將SVDD應(yīng)用于無線傳感器網(wǎng)絡(luò)；文獻(xiàn)[5]對癌癥多分類基因數(shù)據(jù)集，利用SVDD設(shè)計遞歸策略消去冗余特征；文獻(xiàn)[6]對特征進(jìn)行排序，構(gòu)造多個支持向量數(shù)據(jù)描述模型；文獻(xiàn)[7]對雷達(dá)目標(biāo)識別問題，構(gòu)造一種最小二乘SVDD模型，降低了計算復(fù)雜度且保證了檢測精度；文獻(xiàn)[8]修改SVDD的目標(biāo)函數(shù)，并利用啟發(fā)式策略解決參數(shù)選擇問題，提高求解線性方程組的訓(xùn)練速度；文獻(xiàn)[9]利用支持向量數(shù)據(jù)描述構(gòu)造一種分類器SVDC，利用一類樣本的球形描述邊界對數(shù)據(jù)進(jìn)行分類；文獻(xiàn)[10]針對多源樣本，利用支持向量數(shù)據(jù)描述構(gòu)造一種多分類器；文獻(xiàn)[11]融合支持向量數(shù)據(jù)描述和二叉樹結(jié)合構(gòu)造了一種多分類器，取得了良好的分類結(jié)果；文獻(xiàn)[12]利用SVDD構(gòu)造兩個支持向量超球，避免了矩陣求逆的運(yùn)算，提高了傳統(tǒng)SVDD的分類器。這些研究或拓寬SVDD的應(yīng)用領(lǐng)域，或構(gòu)造快速訓(xùn)練算法，但由于訓(xùn)練僅利用目標(biāo)類樣本而不考慮非目標(biāo)類樣本，故而分類精度并不高。

從提高分類精度角度，筆者利用SVDD構(gòu)造閉合超球面機(jī)(sealed hypersphere machine，SHM)，在SVDD的目標(biāo)函數(shù)和約束條件中加入對非目標(biāo)類樣本的錯分懲罰和限制條件，修正最小包圍超球的描述邊界，以更加準(zhǔn)確地貼近實(shí)際的分類曲面，判斷待測樣本的類別。

1 閉合超球面機(jī)

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

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

(1)

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

(2)

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

(3)

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

(4)

給定測試樣本z，采用下列規(guī)則判斷是否接受該樣本

(5)

如果待測樣本z到最小包圍超球球心的距離平方小于超球半徑R2，接受該測試樣本為目標(biāo)類；否則，拒絕該樣本，將其作為非目標(biāo)類。需要指出，這里距離的計算是在非線性空間中進(jìn)行。

1.2 閉合超球面分類機(jī)SHM

以非線性空間為例，記Φ:x→Φ(x)為非線性映射，i,j≥0為松弛變量，C1,C2>0為懲罰參數(shù)，訓(xùn)練SHM等價于求解如下凸二次規(guī)劃

(6)

采用Lagrange乘子法推導(dǎo)上述問題的最優(yōu)解，依次對規(guī)劃(6)中的4個不等式約束引入Lagrange乘子αi≥0,βj≥0,γi≥0和ηj≥0，構(gòu)造如下Lagrange函數(shù)

(7)

對Lagrange函數(shù)L(R,a,αi,βj)關(guān)于變量R，a，i和j求偏導(dǎo)，并置偏導(dǎo)的值為零，則有

(8)

化簡整理得到

(9)

將所得關(guān)系式帶入原規(guī)劃，可得原問題的對偶規(guī)劃

(10)

(11)

給定測試樣本z，SHM采用如下符號函數(shù)來判斷樣本的類別

(12)

1.3 算法復(fù)雜度分析

選取經(jīng)典的SVM和SVDC算法，對比分析SHM算法的復(fù)雜度。不妨假設(shè)訓(xùn)練樣本個數(shù)為l。SVM在訓(xùn)練時需要輸入兩類樣本，所需時間和空間復(fù)雜度分為o(l2)和o(l3)。SVDC僅采集一類目標(biāo)類樣本信息，求取這類樣本的最小包圍超球，將落入描述邊界內(nèi)部和外部的樣本分別定義為正類和負(fù)類。為了方便分析，不妨假定正負(fù)類樣本個數(shù)相同，則參與訓(xùn)練的目標(biāo)樣本個數(shù)為l/2，SVDC需要的時間和空間復(fù)雜度分別為o(l2/4)和o(l3/8)。SHM采集目標(biāo)類樣本構(gòu)造一個超球面分類機(jī)，時間和空間復(fù)雜度與SVDC相當(dāng)；但是在約束條件中加入對非目標(biāo)類樣本的限制條件，從而超球半徑的計算式(11)和決策準(zhǔn)則(12)，完全不同于SVDC的計算式(4)和決策準(zhǔn)則(5)。由于SVDC和SHM需要采集的數(shù)據(jù)數(shù)目較少，從而大大降低了存儲空間；同時這兩類算法具有較少的支持向量數(shù)目，從而降低了測試階段所需的計算量和運(yùn)算時間。

2 仿真實(shí)驗(yàn)

為驗(yàn)證SHM的算法性能，生成正態(tài)分布數(shù)據(jù)集，并選取部分規(guī)模不同的UCI數(shù)據(jù)集展開實(shí)驗(yàn)。所有算法采用MATLAB7.01編寫程序，并在P4CPU，3.06 GHz，1 GB的PC機(jī)上模擬實(shí)現(xiàn)。

首先，對正態(tài)分布數(shù)據(jù)集驗(yàn)證SHM的有效性。產(chǎn)生正負(fù)類數(shù)目均等的樣本集，并依次增加樣本規(guī)模。隨機(jī)互換3%的類別指標(biāo)，選取80%的樣本參與訓(xùn)練，其余參與測試。SHM將正類樣本當(dāng)作目標(biāo)類，采用線性核函數(shù)，并取10次隨機(jī)抽取實(shí)驗(yàn)的平均結(jié)果。為方便計算，SHM取C1=C2=C，表1列出在不同懲罰參數(shù)下的分類精度。

表1 SHM的分類精度

表1數(shù)據(jù)驗(yàn)證了SHM是一種有效的分類算法。SHM的分類精度較高，且隨著懲罰參數(shù)和樣本規(guī)模的變化而呈現(xiàn)一定規(guī)律性。SHM的分類精度先隨懲罰參數(shù)的增加而增加，繼續(xù)增加反而有小幅下降；SHM的分類精度隨樣本規(guī)模的增加先增加然后幾乎保持不變。

其次，對比SHM與已有算法的分類表現(xiàn)。選取部分UCI數(shù)據(jù)，列出基本特征于表2；其中，正類指代數(shù)目較少的樣本，負(fù)類指代數(shù)目較多的樣本，比例是正類樣本和負(fù)類樣本的數(shù)目之比。

如果定義正負(fù)兩類樣本的數(shù)目之比為不平衡度，則表2中數(shù)據(jù)可以分為兩部分：不平衡度較低的數(shù)據(jù)集，如Pima、Iris和Indian數(shù)據(jù)集；不平衡度較高的數(shù)據(jù)集，如Glass Ⅱ和Balance Ⅱ。

表2 數(shù)據(jù)集的基本特征

選取SVM、SSVM和SVDC作為比較對象，對比SHM的分類表現(xiàn)。所有算法采用十重交叉驗(yàn)證法選取最優(yōu)參數(shù)，懲罰參數(shù)和徑向基核參數(shù)的取值區(qū)域?yàn)閘gC=[-2,-1,-0.5,0，0.5，1，2]和σ=[0.01,0.03,0.1,0.3,0.5,0.8,1]。支持向量機(jī)SVM和SSVM隨機(jī)抽取總樣本的50%參與訓(xùn)練，其余參與測試；支持向量數(shù)據(jù)描述算法SVDC和SHM將正類樣本作為目標(biāo)類進(jìn)行訓(xùn)練，代入數(shù)目較多的負(fù)類樣本進(jìn)行測試。表3列出不同算法在最優(yōu)參數(shù)下的分類性能。

表3 不同算法的分類性能

在上述表3中，精度是訓(xùn)練集和測試集上的分類精度的平均值，時間是訓(xùn)練集和測試集上的運(yùn)行時間的平均值。

觀察表3數(shù)據(jù)得出結(jié)論：SHM在處理不平衡度較高的數(shù)據(jù)集時，能夠顯著提高SVM和SSVM的分類精度且縮減分類時間。SHM在處理任意不平衡度的數(shù)據(jù)集上，均能顯著提高SVDC的分類精度，同時略微增加運(yùn)行時間。

數(shù)據(jù)集Iris的不平衡度較低而Balance Ⅱ的不平衡度較高。在Iris數(shù)據(jù)集上，SHM將SVM和SSVM的分類精度分別提高1.14%和1.72%，而分類時間依次是兩者的42.32%和67.26%。SHM將SVDC的分類精度提高4.25%，而分類時間僅多0.11 s。在數(shù)據(jù)集Balance Ⅱ上，SHM的有效性和優(yōu)越性體現(xiàn)地更為明顯，其分類精度分別比SVM和SSVM高5.85%和8.58%；而分類時間依次是兩者的17.17%和29.06%。SHM將SVDC分類精度提高12.98%，而分類時間僅多0.37 s。

整體而言，SHM在分類精度和運(yùn)行時間上具有良好表現(xiàn)：其分類精度與SVM相當(dāng)，略高于SSVM和SVDC；其分類時間遠(yuǎn)遠(yuǎn)低于SVM，略低于SSVM而略高于SVDC。考慮到SHM可以提高SVDC的分類精度，增加的分類時間是值得的。

最后，闡明SHM的魯棒性，也即分類精度隨核參數(shù)變化而變化趨勢。選取UCI中的Image數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)集規(guī)模較大，共含有2310個樣本，其中正類樣本1310個，負(fù)類樣本1000個，故而在此數(shù)據(jù)集上的分類表現(xiàn)，可以視為算法的實(shí)際性能。實(shí)驗(yàn)中發(fā)現(xiàn)，不同算法隨懲罰參數(shù)的變化趨勢類似，故著重列出算法隨徑向基核參數(shù)的變化趨勢。設(shè)定懲罰參數(shù)C=1，4種算法SHM、SVM、SSVM和SVDC的分類精度隨徑向基核參數(shù)σ的變化曲線列于圖1。

圖1 分類精度隨徑向基核參數(shù)的變化曲線

觀察圖1曲線可以看出：SHM、SVM、SSVM和SVDC的分類精度均隨徑向基核參數(shù)的增加，出現(xiàn)先增加而后減少的變化趨勢；但是4種算法的變化幅度并不相同。

整體而言，SHM和SVM的分類精度相當(dāng)，兩者均比SSVM的分類精度要高，且遠(yuǎn)遠(yuǎn)高于SVDC的分類精度。這驗(yàn)證了采用負(fù)類樣本修正描述邊界，可以顯著提高SVDC的分類精度。

當(dāng)核參數(shù)較小時，4種算法的分類精度并不高，這是因?yàn)椤斑^擬合”造成對訓(xùn)練集過度學(xué)習(xí)，而一定程度降低了測試集上的分類性能；增大核參數(shù)，4種算法的分類精度先隨之增加，進(jìn)一步增大反而導(dǎo)致分類精度有一定程度的下降。其中，SHM、SVM和SSVM由于用到了兩類樣本的信息，分類精度隨核參數(shù)變化的幅度并不明顯；而SVDC僅利用一類樣本的信息，分類精度隨核參數(shù)變化增幅顯著，也即算法的魯棒性不高。

取訓(xùn)練集和測試集上運(yùn)行時間的平均值作為分類時間，進(jìn)一步驗(yàn)證SHM算法對比已有算法的優(yōu)勢。對上述徑向基核參數(shù)的取值，給出取懲罰參數(shù)C=1時，不同算法的分類時間隨徑向基核參數(shù)的變化趨勢，列出相應(yīng)結(jié)果于圖2。

圖2 分類時間隨徑向基核參數(shù)的變化曲線

觀察圖2曲線可以看出：SHM的分類時間要遠(yuǎn)遠(yuǎn)低于SVM的分類時間，顯著低于SSVM的分類時間。這是因?yàn)槔靡活悩颖舅璧挠嬎愫痛鎯Τ杀据^低。SHM的分類時間略高于SVDC的分類時間?？紤]到SHM提高了SVDC的分類精度，增加的分類時間是值得的。

3 結(jié)束語

閉合超球面機(jī)(sealed hyperplane machine，SHM)利用非目標(biāo)類修正傳統(tǒng)SVDD的超球形描述邊界，并設(shè)計符號函數(shù)展開分類判別。SHM在不同規(guī)模的正態(tài)分布數(shù)據(jù)集上均保持了良好的分類精度；相較于已有算法，在UCI數(shù)據(jù)集上具有分類精度和分類時間上的顯著優(yōu)勢，且這種優(yōu)勢在不平衡度較高的數(shù)據(jù)集上體現(xiàn)得更加明顯。SHM具有較好的魯棒性，大規(guī)模Image數(shù)據(jù)集上分類精度和分類時間隨徑向基核參數(shù)的變化曲線驗(yàn)證了這一點(diǎn)。本文的閉合超球面機(jī)針對二分類問題提出，如何拓寬SHM將其應(yīng)用于多分類問題是進(jìn)一步的研究方向。