基于超平面的增強(qiáng)型單類支持向量機(jī)

單類問(wèn)題意味著只有一個(gè)目標(biāo)數(shù)據(jù)，而不是其他目標(biāo)數(shù)據(jù)。由于收獲成本高（如故障診斷，無(wú)法獲得大量非目標(biāo)數(shù)據(jù)而破壞機(jī)器）以及數(shù)據(jù)過(guò)于寬泛，現(xiàn)有數(shù)據(jù)的代表性無(wú)法得到（例如，皮膚檢測(cè)和其他非表面數(shù)據(jù)等）。因此，需要放棄獲取，導(dǎo)致樣本不足。為了識(shí)別和識(shí)別個(gè)別問(wèn)題設(shè)計(jì)的個(gè)別分發(fā)，可以用于文本檢測(cè)、圖像提取和異常檢測(cè)。典型的研究方法包括密度和邊界法?；诿芏鹊姆椒ㄍㄟ^(guò)參數(shù)化或非參數(shù)化方法來(lái)估計(jì)樣本數(shù)據(jù)的概率密度,而后設(shè)置閾值以判定測(cè)試數(shù)據(jù)是否屬于正常數(shù)據(jù).現(xiàn)實(shí)中有限的目標(biāo)數(shù)據(jù)反映的常常是數(shù)據(jù)所處的區(qū)域而非密度信息,因此采用密度估計(jì)很可能把正常數(shù)據(jù)的稀疏區(qū)域作為低密度區(qū)而誤判,并且由于維數(shù)災(zāi)難,該方法更適合低維數(shù)據(jù).基于邊界的方法是通過(guò)幾何形狀如超平面、超(橢)球等,將目標(biāo)數(shù)據(jù)中的高密度區(qū)映射到一個(gè)正半空間或者封閉的超(橢)球里,從而在盡可能包含大部分目標(biāo)數(shù)據(jù)的前提下,最小化上述幾何形狀的體積,以達(dá)到錯(cuò)誤率最小的目的.由于該方法的目標(biāo)是尋找數(shù)據(jù)的支持域而非密度,從而適合處理高維、有噪和有限樣本的單類問(wèn)題,成為單類分類器研究的熱點(diǎn).單類支持向量機(jī)(one-classSVM,OCSVM)作為超平面模型的代表,由于采用的歐氏度量無(wú)法考慮數(shù)據(jù)結(jié)構(gòu)分布,導(dǎo)致所獲得的超平面很可能是次優(yōu)解.單類最小化最大概率機(jī)one-classMPM雖然利用了樣本分布的先驗(yàn)信息,但因?yàn)樗捎玫母怕誓Ｐ捅仨毻ㄟ^(guò)二次錐規(guī)劃求解,且因無(wú)法采用對(duì)偶理論而喪失了解的稀疏性.Tsang等人直接將馬氏距離引入到OCSVM(MOCSVM),避免二次錐規(guī)劃求解的同時(shí),一定程度上克服了原算法采用歐氏距離的不足.支持向量數(shù)據(jù)描述(supportvectordatadescription,SVDD)作為超球模型典型算法,當(dāng)目標(biāo)數(shù)據(jù)在各方向呈現(xiàn)不同的分布趨勢(shì)或數(shù)據(jù)并非球狀分布時(shí),SVDD所找到的超球會(huì)因包含過(guò)多的非目標(biāo)區(qū)域而不夠緊湊,Wei等人利用超橢球代替了SVDD中的超球以考慮數(shù)據(jù)的結(jié)構(gòu)信息,類似的橢球模型還有最小體積包含橢球(minimumvolumeenclosingellipsoid,MVEE)以及核最小體積覆蓋橢球(kernelminimumvolumecoveringellipsoid,KMVCE),它們均是通過(guò)優(yōu)化橢球體積來(lái)尋找最小超橢球.上述基于邊界的算法由于沒(méi)有考慮數(shù)據(jù)分布(如OCSVM或SVDD)或結(jié)構(gòu)信息粒度過(guò)粗(如MOCSVM或MVEE,KMVCE),因而更適合解決數(shù)據(jù)呈單簇分布的情形.然而現(xiàn)實(shí)中越來(lái)越多的單類應(yīng)用如網(wǎng)絡(luò)入侵檢測(cè)、手寫體識(shí)別、人臉檢測(cè)等,目標(biāo)數(shù)據(jù)均呈多簇分布,如圖1即為UCI標(biāo)準(zhǔn)數(shù)據(jù)集Sonar部分?jǐn)?shù)據(jù)經(jīng)KPCA降維取最大三維主分量后的可視化分布,圖1(a)(b)分別為正負(fù)類相應(yīng)的簇分布,分別對(duì)應(yīng)著實(shí)驗(yàn)部分Sonar1和Sonar2.盡管低維空間中的分布并不能完全表示高維空間的情形,但從實(shí)驗(yàn)部分的結(jié)果可充分說(shuō)明圖1可視化的代表性.因此,設(shè)計(jì)可用于多(單)簇?cái)?shù)據(jù)分布的單類分類器已成為應(yīng)用驅(qū)動(dòng)的必然.結(jié)構(gòu)化單類分類器(structureone-classclassification,TOCC)作為首次提出的針對(duì)數(shù)據(jù)呈多簇分布的單類分類器,首先通過(guò)聚類找到數(shù)據(jù)的簇分布,而后借助超橢球模型即若干個(gè)馬氏距離SVDD來(lái)尋找各簇?cái)?shù)據(jù)的超橢球,橢球數(shù)目等于聚類個(gè)數(shù),其推廣性能較其他算法有顯著提高.然而,TOCC為得到好的推廣性能設(shè)計(jì)了多個(gè)橢球并依次采用二次錐規(guī)劃優(yōu)化求解,且受樣本數(shù)目和聚類算法的影響,所尋找的橢球有相當(dāng)?shù)牟淮_定性,該不確定性會(huì)在一定程度上影響算法的性能.本文所提出的增強(qiáng)型單類支持向量機(jī)(enhancedone-classSVM,EnOCSVM)旨將超平面模型應(yīng)用于多簇?cái)?shù)據(jù),為此算法也分為兩個(gè)階段:首先如TOCC那樣通過(guò)聚類得到數(shù)據(jù)的內(nèi)在分布簇以獲得各簇結(jié)構(gòu)信息;而后在分類階段,EnOCSVM并未像TOCC那樣完全根據(jù)聚類的結(jié)果來(lái)設(shè)計(jì)各橢球,而是在現(xiàn)有OCSVM框架下構(gòu)建出新的目標(biāo)函數(shù),最大化間隔的同時(shí),通過(guò)嵌入各簇結(jié)構(gòu)信息組成的總體協(xié)方差矩陣以反映數(shù)據(jù)的先驗(yàn)信息,不僅保留了原算法的諸多優(yōu)點(diǎn)如全局最優(yōu)性、對(duì)偶稀疏性、可二次規(guī)劃求解以及易核化等,并且由于結(jié)合了數(shù)據(jù)的結(jié)構(gòu)信息,帶有更多的先驗(yàn)知識(shí),因此,與基于超平面的同類算法相比,理論上具有更好的推廣性.1確定+an給定數(shù)據(jù)集X={x1,x2,…,xn},n為樣本個(gè)數(shù),單類支持向量機(jī)OCSVM通過(guò)最大化原點(diǎn)和目標(biāo)數(shù)據(jù)之間的最小歐氏距離ρwΤw來(lái)尋找最優(yōu)超平面,其中w是超平面的法向量,ρ是超平面截距.目標(biāo)函數(shù)中引入松弛因子ξ=[ξ1,…,ξn]T使算法具有一定的魯棒性,具體刻畫如下:minw,ξ,ρ12wΤw-ρ+1vnn∑i=1ξis.t.wΤxi≥ρ-ξi,ξi≥0,i=1,?,n,(1)其中,v∈[0,1)是所謂的百分比估計(jì),和支持向量的數(shù)目有密切聯(lián)系,即v是邊界支持向量的上界,是全部支持向量的下界,稱為v屬性.引入向量α=[α1,…,αv]T,1n=[1,…,1]T,式(1)的對(duì)偶形式以矩陣表示為minα=12αΤXΤXαs.t.αΤ1n=1,0≤α≤1vn1n.(2)這是一個(gè)二次規(guī)劃(quadraticprogramming,QP)問(wèn)題,可采用經(jīng)典的QP軟件包或者序列最小優(yōu)化(sequentialminimaloptimization,SMO)算法來(lái)優(yōu)化.對(duì)于新來(lái)的測(cè)試樣本z,判別函數(shù)如下:f(x)=sgn[αΤXΤz-ρ]={1,target.-1,outlier.(3)2應(yīng)用程序模塊上述OCSVM在計(jì)算間隔時(shí)并未考慮數(shù)據(jù)的結(jié)構(gòu)信息,因而所尋找的超平面很可能是次優(yōu)解.針對(duì)此不足且考慮到算法要同時(shí)應(yīng)用于多(單)簇?cái)?shù)據(jù)分布,增強(qiáng)型單類支持向量機(jī)EnOCSVM亦分為兩個(gè)階段:首先借助聚類算法獲取數(shù)據(jù)的內(nèi)在分布簇;而后將各簇結(jié)構(gòu)信息嵌入到OCSVM框架下構(gòu)建出包含數(shù)據(jù)先驗(yàn)信息的目標(biāo)函數(shù),詳細(xì)過(guò)程如下.2.1聚類個(gè)數(shù)的確定為使分布簇能用協(xié)方差矩陣表示數(shù)據(jù)分布信息,要求所采用的聚類算法所得到的子簇需是球形緊湊聚類,凝聚型層次聚類Ward算法因?yàn)闈M足此要求亦在本文采用.通過(guò)重復(fù)計(jì)算當(dāng)前各聚類中心點(diǎn)之間的距離且合并最近一對(duì)聚類這一過(guò)程,所有數(shù)據(jù)點(diǎn)最終可成為一類.在整個(gè)聚類過(guò)程中,隨著聚類數(shù)目的減少,每次所合并的兩個(gè)聚類中心之間的距離(稱為合并距離)逐漸增大,將上述聚類數(shù)目和合并距離之間的變化匯成曲線,其中曲率變化最大的點(diǎn)(拐點(diǎn))所對(duì)應(yīng)的聚類數(shù)目即為聚類個(gè)數(shù).為找到該拐點(diǎn),本文采用文獻(xiàn)所使用的貪婪法來(lái)遍歷任一點(diǎn)作為拐點(diǎn)時(shí)所擬合曲線的誤差,其中,誤差最小即為拐點(diǎn).由于凝聚型層次聚類的樹(shù)型結(jié)構(gòu),因此可在任意深度確定各聚類所包含的樣本點(diǎn),于是,根據(jù)拐點(diǎn)所確定的聚類個(gè)數(shù)將各樣本點(diǎn)劃分到各自獨(dú)立的子類,自此,聚類階段完成.2.2enocsvm的建立上述聚類過(guò)程將目標(biāo)數(shù)據(jù)分成若干個(gè)簇,記為S1,…,Si,…,SM,并分別以協(xié)方差矩陣ΣS1,…,ΣSi,…,ΣSM表示各簇結(jié)構(gòu)信息.為將此聚類結(jié)果加入到基于超平面的分類器設(shè)計(jì)中,現(xiàn)將上述各協(xié)方差整體求和后組成新的總體協(xié)方差矩陣Σ,且Σ=ΣS1+…+ΣSi+…+ΣSM.考慮到OCSVM所優(yōu)化的目標(biāo)函數(shù)可看作類間(目標(biāo)數(shù)據(jù)和原點(diǎn)之間)距離,而協(xié)方差矩陣所揭示的結(jié)構(gòu)信息恰好指示目標(biāo)數(shù)據(jù)的類內(nèi)緊性,因此受LDA類間盡量分開(kāi)且類內(nèi)盡量緊湊思想的啟發(fā),EnOCSVM在現(xiàn)有OCSVM框架下嵌入分布簇結(jié)構(gòu)信息Σ,相應(yīng)目標(biāo)函數(shù)如下:minw,ξ,ρ12wΤw+λ2wΤΣw-ρ+1vnn∑i=1ξis.t.wΤxi≥ρ-ξi,ξi≥0,i=1,?,n,(4)其中參數(shù)λ用于類內(nèi)緊性和類間的平衡,且λ≥0.從式(4)可看出,λ較大則更強(qiáng)調(diào)目標(biāo)數(shù)據(jù)的結(jié)構(gòu)分布信息,而λ較小則更強(qiáng)調(diào)目標(biāo)數(shù)據(jù)與原點(diǎn)之間的可分性,λ=0退化為OCSVM算法,即不考慮數(shù)據(jù)的類內(nèi)結(jié)構(gòu)信息而只關(guān)注數(shù)據(jù)間的可分性.由此可見(jiàn),EnOCSVM是原算法的推廣,它通過(guò)在原算法的基礎(chǔ)上加入結(jié)構(gòu)信息充分考慮數(shù)據(jù)的先驗(yàn)知識(shí),而加入先驗(yàn)正是提高分類器精度的有效途徑.EnOCSVM實(shí)現(xiàn)了最大化類間間隔ρwΤw的同時(shí)最小化類內(nèi)散度wTΣw,當(dāng)進(jìn)一步整理式(4)并調(diào)整參數(shù)λ的位置,可得12wΤΣrw-ρ+1vnn∑i=1ξi,(5)其中,Σr=1λΙ+Σ,表示總體協(xié)方差矩陣Σ估計(jì)值的不確定性,而ρwΤΣrw表示所尋找的超平面與原點(diǎn)之間的馬氏距離,即整理后的EnOCSVM目標(biāo)函數(shù)可看作加入簇結(jié)構(gòu)信息的馬氏距離MOCSVM,或者說(shuō)MOCSVM是EnOCSVM將全部數(shù)據(jù)樣本聚為一類的特殊情形,一致起見(jiàn),下文稱MOCSVM為全局EnOCSVM,簡(jiǎn)稱gEnOCSVM.將式(4)變換得到相應(yīng)的對(duì)偶形式:minα12αΤXΤ(Ι+λΣ)-1Xαs.t.αΤ1n=1,0≤α≤1vn1n.(6)和OCSVM的對(duì)偶形式(2)比較不難看出,式(6)所在的對(duì)偶空間已不再是樣本內(nèi)積XTX作用的輸入空間,而是XT(Ι+λΣ)-1X所在的輸出空間,它相當(dāng)于把樣本通過(guò)(Ι+λΣ)-12映射到輸出空間中尋找最優(yōu)超平面,該超平面相對(duì)于原空間來(lái)說(shuō)是非線性的,因此不難理解,理論上EnOCSVM優(yōu)于OCSVM.盡管該結(jié)論對(duì)于gEnOCSVM也同樣成立,但由于其并未如EnOCSVM那樣考慮數(shù)據(jù)分布簇而丟失了一部分先驗(yàn)信息,因而從理論上分析其性能不會(huì)超過(guò)后者,這點(diǎn)可從后續(xù)實(shí)驗(yàn)部分進(jìn)一步說(shuō)明.值得指出,由于協(xié)方差矩陣可事先計(jì)算及存儲(chǔ),因此上述對(duì)偶形式在計(jì)算復(fù)雜度上并未帶來(lái)額外計(jì)算量,并且由于同樣是QP問(wèn)題,因此優(yōu)化可直接采用OCSVM的方法.對(duì)于待測(cè)樣本z,可通過(guò)如下判別函數(shù)決定是否屬于異常類:f(x)=sgn[αXΤ(Ι+λΣ)-1z-ρ].(7)2.3高維特征空間的聚類分布這里僅指分類階段的核化,簡(jiǎn)單起見(jiàn),省略了核化空間的目標(biāo)函數(shù),而直接采用線性空間中的對(duì)偶式(6)引入核技巧,為此,需求所有簇的總體協(xié)方差矩陣Σ,首先某簇結(jié)構(gòu)信息表示為ΣSi=1|Si|～XSi～XΤSi-1|Si|2～XSi1Si1ΤSi～XΤSi=～XSiΗSi～XΤSi,(8)其中,Ηsi=(1|Si|ΙSi-ESiEΤSi),|Si|表示某簇的樣本個(gè)數(shù),i=1,?,Μ?～XSi=[x1,?,x|Si|]表示該簇的樣本,1Si表示|Si|維數(shù)的1向量,ESi=1|Si|1Si.因此,總體協(xié)方差矩陣Σ可整理為:Σ=～XΗ～XΤ,(9)其中～X=[～XS1,?,～XSΜ],表示按簇分布重新排序的樣本數(shù)據(jù),H表示各簇的結(jié)構(gòu)分布信息.為求式(6)中的(Ι+λΣ)-1,此處需借助Woodbury公式:(A+UBV)-1=A-1-A-1UB(B+BVA-1UB)-1BVA-1,得(Ι+λΣ)-1=Ι-λ～XΗ(Η+λΗ～XΤ～XΗ)-1Η～XΤ.(10)將上述結(jié)果代入矩陣表示的對(duì)偶式(6),并將樣本數(shù)據(jù)之間的內(nèi)積用核函數(shù)來(lái)替代,化簡(jiǎn)如下:min12αΤ(Κ-λ～ΚΗ(Η+λΗ?ΚΗ)-1Η～ΚΤ)α,(11)其中K=XTX表示輸入樣本數(shù)據(jù)的核矩陣,～Κ=XΤ～X表示樣本數(shù)據(jù)和聚類后重新排序數(shù)據(jù)的核矩陣,～ΚΤ是其相應(yīng)轉(zhuǎn)置,?Κ=～XΤ～X是聚類后重新排序數(shù)據(jù)之間的核矩陣,原有約束條件不變.同樣,該核化目標(biāo)函數(shù)仍屬二次規(guī)劃,優(yōu)化方法可參照QP求解.對(duì)于新來(lái)的樣本矩陣Z,將式(10)帶入式(7),可得到高維特征空間的判別函數(shù)矩陣:f=sgn[αΤ(?Κ-λ～ΚΗ(Η+λΗ?ΚΗ)-1ΗΚ-ρ],(12)這里?Κ表示訓(xùn)練樣本和測(cè)試樣本的核矩陣,Κ表示分簇排序后的訓(xùn)練樣本和測(cè)試數(shù)據(jù)之間的核矩陣,而超平面的偏移向量ρ=ρ1T,向量1的意義同前,f和sgn分別對(duì)應(yīng)式(7)中f(x)和sgn(·)的向量形式.3在單類數(shù)據(jù)集中的應(yīng)用由于單類少有專用數(shù)據(jù)集,因此實(shí)驗(yàn)中采用了UCI的5個(gè)兩類數(shù)據(jù)集分別產(chǎn)生10個(gè)單類數(shù)據(jù),分別稱為DataSet1,DataSet2,其中DataSet1是指將數(shù)據(jù)集中較多的一類作為目標(biāo)類,而數(shù)據(jù)較少的一類作為異常類,DataSet2則相反.這里比較了EnOCSVM與OCSVM以及gEnOCSVM算法,后者是省略了聚類過(guò)程的EnOCSVM算法,即將數(shù)據(jù)看成一個(gè)簇或者說(shuō)省略聚類過(guò)程而直接考慮數(shù)據(jù)的整體結(jié)構(gòu)信息,粒度與MOCSVM相當(dāng).實(shí)驗(yàn)中采用了高斯核函數(shù)Κ(x,y)=e-∥x-y∥2/σ2.核帶寬σ和λ采用網(wǎng)格式搜索,5-fold交叉驗(yàn)證,隨機(jī)選擇80%的目標(biāo)數(shù)據(jù)作為訓(xùn)練樣本,剩余20%的目標(biāo)數(shù)據(jù)和異常類分別作為正類和異常類的測(cè)試數(shù)據(jù),重復(fù)10輪.單類問(wèn)題根據(jù)測(cè)試樣本的真實(shí)類別和分類結(jié)果構(gòu)成了表1的混淆矩陣:Tabel1ConfusionMatrixofOne-ClassClassification從表1可看出單類有兩類錯(cuò)誤,即目標(biāo)類被錯(cuò)分為異常類FN和異常類被錯(cuò)分為目標(biāo)類FP,實(shí)驗(yàn)中即采用了FP/FN評(píng)價(jià)指標(biāo),顯然,這兩個(gè)結(jié)果越小越好.表2列出了上述5個(gè)數(shù)據(jù)集的10組結(jié)果,其中黑體表示每組3個(gè)算法中(FΡ+FΝ)2的最小結(jié)果,稱為BalanceLoss(BL).數(shù)據(jù)集括號(hào)內(nèi)Tr:TeT:TeO依次表示該數(shù)據(jù)集的訓(xùn)練樣本、目標(biāo)類和異常類測(cè)試樣本.3個(gè)算法的v均取0.1,即在訓(xùn)練樣本上,最多允許10%的數(shù)據(jù)落在邊界或分類面之外而成為支持向量,根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論,該值不可能為零,也就是說(shuō),單類必然存在訓(xùn)練誤差.表中FN括號(hào)中列出了相應(yīng)的訓(xùn)練誤差.優(yōu)化方法采用單類SMO算法.分析表2可看出:1)考慮數(shù)據(jù)類內(nèi)結(jié)構(gòu)信息的gEnOCSVM和EnOCSVM所對(duì)應(yīng)的BL均一致優(yōu)于僅考慮數(shù)據(jù)類間信息的OCSVM,尤其對(duì)于Heart和Sonar數(shù)據(jù)集,EnOCSVM的BL較OCSVM降低了7%～11%,gEnOCSVM在Import1上也降低了5%,驗(yàn)證了考慮數(shù)據(jù)結(jié)構(gòu)信息的有效性.2)進(jìn)一步比較結(jié)構(gòu)信息的粒度,EnOCSVM除在Breast1上和gEnOCSVM結(jié)果相當(dāng),在Import1上BL差于gEnOCSVM外,其他8組結(jié)果均優(yōu)于gEnOCSVM,最高達(dá)6%～8%(見(jiàn)Heart2和Sonar數(shù)據(jù)集),說(shuō)明對(duì)于大部分?jǐn)?shù)據(jù),內(nèi)部的確呈簇分布,EnOCSVM因?yàn)楹侠砜紤]了該簇信息因此性能更優(yōu);相反,若數(shù)據(jù)內(nèi)部沒(méi)有明顯的分簇,EnOCSVM性能只與gEnOCSVM相當(dāng)甚至出現(xiàn)降低.3)分析上述結(jié)果不難發(fā)現(xiàn),考慮結(jié)構(gòu)化信息的算法相對(duì)于OCSVM性能提高的主要原因是FN降低:從表2看,除gEnOCSVM在Heart1上和EnOCSVM在Import2上FN增大之外,其他9組數(shù)據(jù)集上兩算法的FN均一致減小,這是因?yàn)榭紤]了數(shù)據(jù)的結(jié)構(gòu)信息可以更準(zhǔn)確地把握數(shù)據(jù)的分布趨勢(shì),因而可使更多的正類落在目標(biāo)區(qū)域內(nèi).當(dāng)然,兩者降幅不同,如Heart2和Sonar1,EnOCSVM的FN降幅高達(dá)28%,而gEnOCSVM只降低了11%～17%,總的來(lái)說(shuō),多數(shù)情況下EnOCSVM降幅要高于gEnO