基于支持向量數(shù)據(jù)描述的閉合超球面機

梁錦錦

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

0 引 言

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

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

1 閉合超球面機

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

1.2 閉合超球面分類機SHM

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

(6)

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

(7)

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

(8)

化簡整理得到

(9)

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

(10)

(11)

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

(12)

1.3 算法復雜度分析

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

2 仿真實驗

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

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

表1 SHM的分類精度

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

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

如果定義正負兩類樣本的數(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ōu)參數(shù)，懲罰參數(shù)和徑向基核參數(shù)的取值區(qū)域為lgC=[-2,-1,-0.5,0，0.5，1，2]和σ=[0.01,0.03,0.1,0.3,0.5,0.8,1]。支持向量機SVM和SSVM隨機抽取總樣本的50%參與訓練，其余參與測試；支持向量數(shù)據(jù)描述算法SVDC和SHM將正類樣本作為目標類進行訓練，代入數(shù)目較多的負類樣本進行測試。表3列出不同算法在最優(yōu)參數(shù)下的分類性能。

表3 不同算法的分類性能

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

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

數(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在分類精度和運行時間上具有良好表現(xiàn)：其分類精度與SVM相當，略高于SSVM和SVDC；其分類時間遠遠低于SVM，略低于SSVM而略高于SVDC?？紤]到SHM可以提高SVDC的分類精度，增加的分類時間是值得的。

最后，闡明SHM的魯棒性，也即分類精度隨核參數(shù)變化而變化趨勢。選取UCI中的Image數(shù)據(jù)集進行實驗。該數(shù)據(jù)集規(guī)模較大，共含有2310個樣本，其中正類樣本1310個，負類樣本1000個，故而在此數(shù)據(jù)集上的分類表現(xiàn)，可以視為算法的實際性能。實驗中發(fā)現(xiàn)，不同算法隨懲罰參數(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的分類精度相當，兩者均比SSVM的分類精度要高，且遠遠高于SVDC的分類精度。這驗證了采用負類樣本修正描述邊界，可以顯著提高SVDC的分類精度。

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

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

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

觀察圖2曲線可以看出：SHM的分類時間要遠遠低于SVM的分類時間，顯著低于SSVM的分類時間。這是因為利用一類樣本所需的計算和存儲成本較低。SHM的分類時間略高于SVDC的分類時間?？紤]到SHM提高了SVDC的分類精度，增加的分類時間是值得的。

3 結束語

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