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

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