基于支持向量數據描述的閉合超球面機

梁錦錦

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

0 引 言

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

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

1 閉合超球面機

1.1 支持向量數據描述SVDD

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

1.2 閉合超球面分類機SHM

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

(6)

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

(7)

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

(8)

化簡整理得到

(9)

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

(10)

(11)

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

(12)

1.3 算法復雜度分析

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

2 仿真實驗

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

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

表1 SHM的分類精度

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

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

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

表2 數據集的基本特征

選取SVM、SSVM和SVDC作為比較對象，對比SHM的分類表現。所有算法采用十重交叉驗證法選取最優參數，懲罰參數和徑向基核參數的取值區域為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%參與訓練，其余參與測試；支持向量數據描述算法SVDC和SHM將正類樣本作為目標類進行訓練，代入數目較多的負類樣本進行測試。表3列出不同算法在最優參數下的分類性能。

表3 不同算法的分類性能

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

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

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

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

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

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

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

整體而言，SHM和SVM的分類精度相當，兩者均比SSVM的分類精度要高，且遠遠高于SVDC的分類精度。這驗證了采用負類樣本修正描述邊界，可以顯著提高SVDC的分類精度。

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

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

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

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

3 結束語

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