基于超平面的增強型單類支持向量機

基于超平面的增強型單類支持向量機

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