面向大規模數據集的單類支持向量機

肖志博 王煥鋼 肖英超 徐文立

(清華大學自動化系，北京 100084)

在很多實際應用中通常存在這樣一種特殊情況，即只有唯一類別的訓練數據，或者其他類別的訓練數據極為稀少.例如復雜系統的故障檢測，往往只能獲取到大量的正常運行數據.這類問題通常被稱為單類樣本分類問題(one-class classification，OCC).現有的處理OCC問題的方法有很多種，主要有主成分分析(principal component analysis，PCA)、k近鄰(k-nearest neighbor，k-NN)、單類支持向量機(one-class support vector machine，OCSVM)等，其中OCSVM 在解決非線性、高維度、小樣本數據上表現突出，應用廣泛.OCSVM的訓練過程需要求解一個二次規劃(quadratic programming，QP)問題［1-2］，因此在面向大規模數據集時，訓練耗時過長，參數優化困難，而且訓練后的支持向量數目也過多，預測效率較低.對于很多實時性要求較高的實際應用，直接在大數據集上訓練得到的模型通常無法使用.

應對大規模數據訓練問題的一種行之有效的方法是先對訓練樣本集合進行壓縮，然后在壓縮后的集合上訓練分類器［3］.目前基于k-NN的訓練樣本壓縮方法已有很多學者進行了討論［4］，也得出了較多有效算法，如基于區域描述的數據集壓縮算法(condensed prototype-based domain description，CPDD)［5］.但是，針對 OCSVM 的訓練樣本壓縮問題還沒有完善的解決方法，因此本文將基于k-NN的數據壓縮方法直接應用于OVSVM訓練時會出現分類面過緊的問題，因為壓縮集合中的點往往屬于原始樣本集合的內部點，缺少集合邊緣樣本點.因此為了使壓縮集合更好適用于OCSVM，本文改進了現有CPDD方法，在內部點提取的基礎上向外擴充再生邊緣點，從而得到在改進的壓縮集合上訓練OCSVM的新方法，簡稱CD-OCSVM(condensed data-based OCSVM).

1 CPDD算法

Angiulli［5］在 2012 年提出的 CPDD 算法［3］壓縮效率理想，下面簡述其基本思想.首先對訓練數據集合D進行處理，得到原型集合P，原型集合P由以下數據對組成:

其中，每個Xi(1≤i≤m)代表訓練樣本D中的一個點，也被稱為原型;每個Ri是一個正實數，也被稱為原型半徑，Ri代表Xi到其在集合D中第k個近鄰的距離.對于給定的正實數θ，原型集合中每個數據對滿足Ri≤θ.給定原型Xi，其對應的原型半徑也可以表示為R(Xi).與CPDD算法對應的分類標準如下:

文獻［5］指出，存在一個原型集合P的子集S，在CPDD算法對應的分類標準下S與P等價，即用S對原訓練集合D預測與用P預測得到的結果一致.同時還給出了一個可以對原型集合進行有效壓縮，計算近似最小子集S的壓縮算法.該算法采用迭代的方式，核心思想是刪除那些可以用某些原型正確分類的點，詳細算法請參考文獻［5］.

實驗證明，CPDD算法可以有效地壓縮訓練集合，減少存儲，提高預測效率.但是在壓縮率較高時所得分類面過松，異常樣本被錯分的可能性增大.如圖1所示，實心小圓點代表原始訓練樣本點，2組樣本點數均為5000，“+”點代表壓縮后的集合，實線代表CPDD分類面.

圖1 CPDD算法高壓縮率下的實驗結果

2 CD-OCSVM算法

2.1 OCSVM原理

設訓練集合 χ={X1，X2，…，XN}?Rn，N 為訓練集合中的樣本數量.若令φ(Xi)代表原始空間樣本點Xi到特征空間F的映射，則OCSVM就是在特征空間F中尋找一個能將訓練樣本與原點以最大間隔分離的超平面，即求解如下二次規劃問題:

其中，松弛變量 ξi，i=1，2，…，N 的引入是為了允許少量的訓練樣本被錯誤分類.在引入拉格朗日乘子［α1，α2，…，αN］T之后，問題(3)的對偶問題可以表述如下:

其中核函數 K(Xi，Xj)=〈φ(Xi)，φ(Xj)〉.求解對偶問題(4)，可以得到分類決策函數:

其中偏置量ρ可以通過下面公式確定:

式中，Xk可以為任意對應0＜＜1/(vN)的邊界點，f(X)=0即為分類面方程.由于絕大部分樣本點分布在邊界內部，其對應的αi=0，不會影響最終的分類決策函數.只有那些對應的αi＞0的樣本才會影響分類邊界，這些樣本就被稱為支持向量.

2.2 CD-OCSVM算法

本文試圖將CPDD壓縮后的子集用于OCSVM訓練，來得到更好的分類邊界.但是，CPDD算法得到的壓縮原型集合屬于原始集合的內部點，如果直接用于OCSVM訓練得到的分類邊界將會過緊，大量正類樣本會被錯分在分類面外部.因此必須提取訓練樣本中的邊緣信息，再結合壓縮后的原型集合才能得到適合于OCSVM訓練的壓縮集合.對于OCSVM訓練樣本的邊緣信息提取，文獻［6］已經給出了比較好的方法，但是在一個大數據集上同時運行CPDD和邊緣提取2個算法，將導致運算復雜度過大.因此本文考慮在CPDD算法得到的原形集合上重新構造出邊緣點的信息，這樣既減小了復雜度，也改善了壓縮集合.

要在壓縮后的原形集合上重構出邊緣點，需要檢測出壓縮原型的邊緣，并確定合理的方向再生邊緣點.在文獻［6］的基礎上，本文給出了檢測原形子集邊緣并重構原始訓練樣本邊緣的算法:首先檢測出原形子集的邊緣，再沿著估算出的壓縮原形邊緣切平面的法方向生成邊緣點.如圖2所示，實心小圓點代表原始訓練樣本，“+”和“⊕”代表原形子集，⊕代表檢測出的原形子集邊界，×代表生成的邊緣點，實線代表近似的原形子集的分布邊界線.

下面給出CD-OCSVM算法的詳細步驟:

圖2 基于OCSVM數據壓縮算法原理圖

2.3 算法復雜度簡析

假設原始數據集合點數為N.經過本文算法壓縮后點數為n(n?N).則CD-OCSVM 算法的計算復雜度為:O(N2+(n)3)［6-10］，近似 O(N2).相比之下，直接在原始數據集合上進行OCSVM訓練的計算復雜度為O(N3)［10］.因此在數據集合較大時，本算法的復雜度低于直接在原始數據集合上進行OCSVM訓練.而且CD-OCSVM所得模型的支持向量數目也會明顯少于直接在原始數據集上進行OCSVM訓練，因此預測速率也更快.

3 實驗

本文實驗所用的數據集為人工生成的單類樣本，有香蕉形分布和環形分布，每個數據集所含點數為5000.本文所有實驗均是用 LIBSVM的OCSVM實現，核函數選擇的是高斯核:k(x，y)=e－γ||x－y||2.具體結果見表 1.

表1 CD-OCSVM結果及參數選擇

圖3 CD-OCSVM結果

圖3中，實心小圓點代表原始訓練集合的樣本點，+代表CPDD壓縮后的點，×代表重構的邊緣點，實線邊界為在壓縮后的集合上訓練得到的OCSVM分類面.根據表1和圖3可以看出本文所提算法在CPDD原形子集基礎上進一步壓縮了數據，支持向量數極大降低，加速了預測速率，而且所得邊界光滑，很好地描述了原始樣本的分布情況.以香蕉形數據集合結果為例，原始訓練樣本點數為5000，經過CPDD壓縮后的點數為64，在壓縮后的集合基礎上再生的邊界點數為41(共計105點)，經過OCSVM訓練后的模型支持向量數僅為17，所得分類面合理地描述了香蕉形分布，且分類面光滑.

4 結語

本文針對OCSVM在大規模數據集上訓練時間過長等問題，提出了一種有效壓縮原始數據集合的方法，從而加速OCSVM訓練過程.所提算法可以在保證壓縮率的情況下不丟失原始數據的邊緣信息，并最終得到存儲量低、預測速率快的OCSVM模型.在人造數據集合上進行的實驗，驗證了本文算法的有效性.

References)

［1］Tax D M J，Duin R P W.Support vector data description［J］.Machine Learning，2004，54(1):45-66.

［2］Scholkopf B，Platt J C，Taylor J S，et al.Estimating the support of a high-dimensional distribution［J］.Neural Computation，2001，13(7):1443-1471.

［3］Bicego M，Figueiredo M A.Soft clustering using weighted one-class support vector machines［J］.Pattern Recognition，2009，42(1):27-32.

［4］Garcia E K，Feldman S，Gupta M R，et al.Completely lazy learning［J］.IEEE Transactions on Knowledge and Data Engineering，2010，22(9):1274-1285.

［5］Angiulli F.Prototype-based domain description for oneclass classification［J］.Pattern Analysis and Machine Intelligence，2012，34(6):1131-1144.

［6］Li Y.Selecting training points for one-class support vector machines［J］. Pattern Recognition Letters，2011，32(11):1517-1522.

［7］Park C，Huang J Z，Ding Y.A computable plug-in estimator of minimum volume sets for novelty detection［J］.Operations Research，2010，58(5):1469-1480.

［8］Li Y，Maguire L.Selecting critical patterns based on local geometrical and statistical information［J］.Pattern Analysis and Machine Intelligence，2011，33(6):1189-1201.

［9］Maji S，Berg A C，Malik J.Efficient classification for additive Kernel SVMs［J］.Pattern Analysis and Machine Intelligence，2013，35(1):66-77.

［10］Angiulli F，Astorino A.Scaling up support vector machines using nearest neighbor condensation［J］.Neural Networks，2010，21(2):351-357.