面向大規(guī)模數(shù)據(jù)集的單類支持向量機(jī)

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

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

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

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

1 CPDD算法

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

其中，每個(gè)Xi(1≤i≤m)代表訓(xùn)練樣本D中的一個(gè)點(diǎn)，也被稱為原型;每個(gè)Ri是一個(gè)正實(shí)數(shù)，也被稱為原型半徑，Ri代表Xi到其在集合D中第k個(gè)近鄰的距離.對于給定的正實(shí)數(shù)θ，原型集合中每個(gè)數(shù)據(jù)對滿足Ri≤θ.給定原型Xi，其對應(yīng)的原型半徑也可以表示為R(Xi).與CPDD算法對應(yīng)的分類標(biāo)準(zhǔn)如下:

文獻(xiàn)［5］指出，存在一個(gè)原型集合P的子集S，在CPDD算法對應(yīng)的分類標(biāo)準(zhǔn)下S與P等價(jià)，即用S對原訓(xùn)練集合D預(yù)測與用P預(yù)測得到的結(jié)果一致.同時(shí)還給出了一個(gè)可以對原型集合進(jìn)行有效壓縮，計(jì)算近似最小子集S的壓縮算法.該算法采用迭代的方式，核心思想是刪除那些可以用某些原型正確分類的點(diǎn)，詳細(xì)算法請參考文獻(xiàn)［5］.

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

圖1 CPDD算法高壓縮率下的實(shí)驗(yàn)結(jié)果

2 CD-OCSVM算法

2.1 OCSVM原理

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

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

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

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

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

2.2 CD-OCSVM算法

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

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

下面給出CD-OCSVM算法的詳細(xì)步驟:

圖2 基于OCSVM數(shù)據(jù)壓縮算法原理圖

2.3 算法復(fù)雜度簡析

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

3 實(shí)驗(yàn)

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

表1 CD-OCSVM結(jié)果及參數(shù)選擇

圖3 CD-OCSVM結(jié)果

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

4 結(jié)語

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

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，F(xiàn)igueiredo M A.Soft clustering using weighted one-class support vector machines［J］.Pattern Recognition，2009，42(1):27-32.

［4］Garcia E K，F(xiàn)eldman 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.