基于混合多樣性生成與修剪的集成單類分類算法

劉家辰 苗啟廣曹 瑩 宋建鋒 權(quán)義寧

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院 西安 710071)

基于混合多樣性生成與修剪的集成單類分類算法

劉家辰 苗啟廣*曹 瑩 宋建鋒 權(quán)義寧

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院 西安 710071)

針對(duì)傳統(tǒng)集成學(xué)習(xí)方法直接應(yīng)用于單類分類器效果不理想的問題，該文首先證明了集成學(xué)習(xí)方法能夠提升單類分類器的性能，同時(shí)證明了若基分類器集不經(jīng)選擇會(huì)導(dǎo)致集成后性能下降；接著指出了經(jīng)典集成方法直接應(yīng)用于單類分類器集成時(shí)存在基分類器多樣性嚴(yán)重不足的問題，并提出了一種能夠提高多樣性的基單類分類器混合生成策略；最后從集成損失構(gòu)成的角度拆分集成單類分類器的損失函數(shù)，針對(duì)性地構(gòu)造了集成單類分類器修剪策略并提出一種基于混合多樣性生成和修剪的單類分類器集成算法，簡(jiǎn)稱為PHD-EOC。在UCI標(biāo)準(zhǔn)數(shù)據(jù)集和惡意程序行為檢測(cè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，PHD-EOC算法兼顧多樣性與單類分類性能，在各種單類分類器評(píng)價(jià)指標(biāo)上均較經(jīng)典集成學(xué)習(xí)方法有更好的表現(xiàn)，并降低了決策階段的時(shí)間復(fù)雜度。

機(jī)器學(xué)習(xí)；單類分類；集成單類分類；分類器多樣性；集成修剪；集成學(xué)習(xí)

1 引言

單類分類[1](One-class classification)是僅使用一類訓(xùn)練樣本建立分類模型的機(jī)器學(xué)習(xí)問題。單類分類僅要求一類樣本被有效采樣，稱為目標(biāo)類(簡(jiǎn)稱為正類)；其它類由于獲取代價(jià)過高、無法枚舉、采樣不充分等原因無法得到有效采樣，極端情況下甚至無法獲取樣本，統(tǒng)稱為異常類(簡(jiǎn)稱為負(fù)類)。例如，故障診斷中的故障類和人臉檢測(cè)中的非人臉類等，都是典型的單類分類問題中的負(fù)類。單類分類算法通過構(gòu)建正類的數(shù)據(jù)描述模型，將其與負(fù)類區(qū)分，在故障檢測(cè)[2]、入侵檢測(cè)[3]、異常檢測(cè)[4]等應(yīng)用中取得了良好的效果。

迄今為止，研究者已提出多種單類分類算法，其中支持向量數(shù)據(jù)描述[5](Support Vector Data Description, SVDD)和單類支持向量機(jī)[6](One Class Support Vector Machine, OCSVM)是最流行的兩種。單類分類器集成是提升單類分類器性能的有效途徑，最初由文獻(xiàn)[7]提出，之后的研究者相繼將裝袋(Bootstrap Aggregation, Bagging)、隨機(jī)子空間(Random Subspace Method, RSM)和Boosting等集成學(xué)習(xí)方法用于單類分類算法[810]-。然而以上文獻(xiàn)同時(shí)指出，傳統(tǒng)的集成學(xué)習(xí)方法應(yīng)用于單類分類器的表現(xiàn)并不理想，在一些數(shù)據(jù)集上，集成單類分類器的性能甚至低于單個(gè)單類分類器(以下稱為基單類分類器)，但造成該問題的原因在現(xiàn)有文獻(xiàn)中并沒有得到深入分析。

本文首先以概率密度水平集估計(jì)模型為基礎(chǔ)，推導(dǎo)出集成單類分類器的風(fēng)險(xiǎn)上下界，說明集成單類分類器性能的提升不僅需要基單類分類器集合具有足夠的多樣性，而且需要精心選擇參與集成的基分類器。第二，由于單類分類器集成的多樣性問題尚未得到充分研究[11]，本文分析了傳統(tǒng)集成方法用于單類分類器集成時(shí)存在的多樣性不足的問題，并提出了一種混合多樣性生成方法提高基單類分類器集合多樣性。第三，拆解集成單類分類器的損失函數(shù)并分析其構(gòu)成，提出了一種尋找最優(yōu)基單類分類器集成順序的方法?；谝陨戏治?、證明和實(shí)驗(yàn)，提出了修剪混合多樣性集成單類分類器(Pruned Hybrid Diverse Ensemble One-class Classifier, PHD-EOC)，并通過實(shí)驗(yàn)說明PHD-EOC算法能夠更有效地提升集成單類分類器的性能。

2 集成單類分類多樣性的理論分析

首先給出單類分類問題的形式化描述：

其中X={x|x∈?N,i=1,2,…,n}從固定但未

Posii知的分布Q中獨(dú)立同分布地產(chǎn)生，sign(·)是符號(hào)函數(shù)，d(x|XPos)是x到目標(biāo)類XPos的距離度量，d(x | XPos)與閾值θ的差值被用于判定樣本x是否屬于正類。僅基于該形式化描述并不能有效開展理論分析，這是由于單類分類器必須對(duì)負(fù)類樣本的分布做某種先驗(yàn)假設(shè)，否則單類分類問題不可解[12]。常用的假設(shè)是負(fù)類樣本分布的集中程度低于正類樣本，故可將單類分類等價(jià)于概率密度水平集估計(jì)(Density Level Set Estimation, DLSE)，即設(shè)在可測(cè)空間X中，有已知分布μ(負(fù)類樣本的分布)和未知分布Q(正類樣本的分布)及Q的概率密度h，在給定ρ∈(0,1)時(shí)，得到密度函數(shù)h上ρ水平集{ρ＜h}的估計(jì)。采用文獻(xiàn)[12]提出的與以上兩種評(píng)價(jià)具有一致性的概率測(cè)度評(píng)價(jià)指標(biāo)：

其中s是分布Q和分布μ的平衡參數(shù)，()·E表示期望，I(·)是指示函數(shù)，指示函數(shù)在括號(hào)內(nèi)邏輯表達(dá)式成立時(shí)取值為1，否則取值為0。對(duì)于訓(xùn)練數(shù)據(jù)集={|∈,i=1,2,…,n}，單類分類的經(jīng)驗(yàn)風(fēng)險(xiǎn)可以定義為

其中ρ是在DLSE中定義的參數(shù)，在單類分類問題中ρ=1-ε,ε是正類拒絕率，即ρ代表正類的接受率。

在式(3)的基礎(chǔ)上，假設(shè)各基分類器對(duì)訓(xùn)練集的n個(gè)正類樣本均有k個(gè)分類錯(cuò)誤，對(duì)負(fù)類樣本的分類錯(cuò)誤率均為p。記基分類器集合中基分類器個(gè)數(shù)為T，不失一般性，假設(shè)T為奇數(shù)。多數(shù)投票可能導(dǎo)致的最大風(fēng)險(xiǎn)在每一個(gè)錯(cuò)誤的集成決策均只由個(gè)錯(cuò)誤的基分類器決策投票得到，由此得到集成風(fēng)險(xiǎn)的上界為

同理，多數(shù)投票的最小風(fēng)險(xiǎn)是盡量多的錯(cuò)誤投票被包含在正確的集成決策中，因此集成風(fēng)險(xiǎn)的下界為

為直觀顯示集成風(fēng)險(xiǎn)的上下界，令T=5, ρ=0.9并遍歷k和p的可能取值，得到結(jié)果如圖1所示。

圖1中R(H)Upper和R(H)Lower分別表示集成風(fēng)險(xiǎn)的上界和下界，R(H)Mean是基分類器的平均損失?？梢婋m然集成單類分類器的風(fēng)險(xiǎn)下界隨著k和p的降低而降低，但其上界甚至比基單類分類器的平均損失更高。這說明合適的基分類器生成與選取可以降低集成單類分類器的損失，但不合適的基分類器生成與選取可能反而提高單類分類器的損失，因此有必要深入研究基單類分類器的生成與選擇方法。

3 PHD-EOC算法

3.1 提升基分類器集合的多樣性

以文獻(xiàn)[13]為代表的研究者提出了一種混合多樣性生成策略，即首先混合使用多種基分類器生成方法生成基分類器集合，再將這些基分類器集成以提高基分類器集合的多樣性。本文將該方法引入單類分類器集成，原因如下：第一，單類分類器的原理導(dǎo)致很多原本適用于二分類器的多樣性生成方法無法使用，例如糾錯(cuò)輸出編碼(Error Correcting Output Codes, ECOC)和輸出反轉(zhuǎn)(flipping output)等，而混合使用多種多樣性生成方法是提升基單類分類器多樣性的可行途徑；第二，單一集成方法構(gòu)成集成單類分類器的假設(shè)空間受限于具體的基分類器生成方法，而混合使用多種基分類器生成方法可以擴(kuò)大假設(shè)空間；第三，單一集成方法的集成分類器性能提升的大部分由前幾個(gè)基分類器完成[14]，因此混合使用多種基分類器生成方法能夠充分利用每一種集成方法的提升效果。

以下實(shí)驗(yàn)使用分類器投影通過將Bagging, RSM和Boosting方法生成的基單類分類器映射到分類器投影空間[15](Classifier Project Space, CPS)中來驗(yàn)證混合多樣性生成方法的效果。CPS建立在分類器距離度量，故根據(jù)單類分類器的特性，以不一致性度量為基礎(chǔ)定義單類分類器ih和jh在數(shù)據(jù)集X上距離的指標(biāo)。

UCI數(shù)據(jù)集①UCI Repository of Machine Learning Databases, http://archive. ics.uci.edu/ml/，訪問時(shí)間2014年5月10日中Sonar數(shù)據(jù)上以“Rock”為正類的實(shí)驗(yàn)結(jié)果如圖2所示，其中“TRUE”標(biāo)記了正確決策參考點(diǎn)的位置，其余各形狀的標(biāo)記表示對(duì)應(yīng)方法生成的基分類器。以“TRUE”標(biāo)記為圓心繪制圓形參考線，若兩個(gè)基分類器位于同一參考線上，認(rèn)為它們性能近似相等?；诸惼髟贑PS空間上歐氏距離小則多樣性低，反之多樣性高，即基分類器在CPS空間中分布的集中程度越高則多樣性越低。從圖2(a)，圖2(b)和圖2(c)中基分類器分布情況可以看出：?jiǎn)我环椒ㄉ傻幕诸惼鞣植技?，多樣性較低。而如圖2(d)所示，使用不同方法生成的基分類器投影到同一個(gè)CPS空間時(shí)，生成的基分類器之間明顯具有較高的多樣性。在多個(gè)UCI數(shù)據(jù)集(參見4.1節(jié)列出的UCI數(shù)據(jù)集)上均可得出類似的實(shí)驗(yàn)結(jié)果，這些實(shí)驗(yàn)說明單一集成方法生成的基分類器集合多樣性不足，使用混合多樣性生成方法可以有效提高基單類分類器集合的多樣性。

圖2 幾種方法生成基分類器的CPS空間分布圖

3.2 修剪集成單類分類器

混合使用多種基分類器生成方法可以提高基分類器的多樣性，但單純提升多樣性并不能保證集成單類分類器性能的提升。一種建立在足夠多樣性基分類器集合基礎(chǔ)上的方法是以最終集成分類器的性能為目標(biāo)選擇部分基分類器，即對(duì)集成單類分類器進(jìn)行修剪(Ensemble Pruning，也被稱為選擇性集成)。修剪步驟不僅能確保單類分類器集成的性能提升效果，有效平衡多樣性與性能，也能降低集成分類器的計(jì)算復(fù)雜度。雖然集成分類器修剪在二分類器上已經(jīng)取得了一些研究成果[16,17]，但集成單類分類器修剪的研究還是空白。

為此，下面從集成單類分類器損失的角度出發(fā)，進(jìn)一步分析選擇基單類分類器的方法。受試者工作特征[18](Receiver-Operating Characteristics, ROC)曲線下包圍的面積(Area Under the Curve, AUC)是單類分類研究中最常用的評(píng)價(jià)指標(biāo)[1]。從統(tǒng)計(jì)特性上講，AUC與排序問題中的Wilcoxon排序檢驗(yàn)等價(jià)[18]，因此可定義集成單類分類器的損失函數(shù)如下，為書寫簡(jiǎn)便起見以下推導(dǎo)中字面上省略PosX這一符號(hào)。

其中x+與x-分別是從正類、負(fù)類中隨機(jī)抽取的樣本，函數(shù)D是集成單類分類器對(duì)樣本與目標(biāo)類之間的距離度量，在采用多數(shù)投票時(shí)D(x)=(1/T)I(d(x)＞θ)，在此基礎(chǔ)上，定義所有基單類i i分類器的平均損失為

為度量集成單類分類器相對(duì)于基分類器平均性能的提升程度，計(jì)算其損失之差為

修剪集成單類分類器的目標(biāo)是選擇合適的基單類分類器集合{di}使μ最小化，將式(7)，式(8)代入式(9)并整理，可以得到μ的表達(dá)式。

為建立多樣性與集成單類分類器修剪的關(guān)系，定義某一個(gè)基單類分類器與集成分類器的不一致性為

將式(10)依集成分類器決策正確與否的概率展開，同時(shí)代入式(11)，可以得到μ與多樣性的關(guān)系為其中P表示集成分類器決策正確與否的事件概率。式(12)共有4項(xiàng)，其中第3項(xiàng)和第4項(xiàng)出現(xiàn)的概率很低，可以忽略。第1項(xiàng)說明在在集成分類器分類正確時(shí)，基分類器的不一致性會(huì)增大損失L；第2項(xiàng)說明在集成分類器分類錯(cuò)誤時(shí)，基分類器的不一致性會(huì)減小損失L。據(jù)此，可以得到集成單類分類器修剪策略：即盡可能提升集成分類器分類錯(cuò)誤時(shí)基分類器的多樣性，同時(shí)避免集成分類器分類正確時(shí)基分類器的多樣性過高。

從基分類器集合中選擇最優(yōu)基分類器子集是一個(gè)NP完全問題[17]，因此假設(shè)大小為t的最優(yōu)基分類器子集總是包含于大小為t+1的最優(yōu)基分類器子集，從而將該問題轉(zhuǎn)化為尋找最優(yōu)的基分類器集成順序[17,19]。根據(jù)對(duì)式(12)的分析，首先需要得到含有正負(fù)類樣本的驗(yàn)證樣本集，訓(xùn)練數(shù)據(jù)中缺乏的負(fù)類樣本可通過人工生成的方法得到[20]，從而得到驗(yàn)證樣本集XVal={(xi,yi)|xi∈,i=1,2,…,l,yi∈{-1, 1}}。將驗(yàn)證樣本集ValX拆分為被集成分類器正確分類的和被錯(cuò)誤分類的。根據(jù)對(duì)集成分類器分類正確和錯(cuò)誤樣本多樣性的不同要求，從基分類器集合H中選擇第k個(gè)參與集成的基單類分類器hk的方法為

式(13)中的函數(shù)eX(hi,hj)如式(6)所定義，該基分類器選擇方法能夠以式(12)的分析為基礎(chǔ)尋找損失最小的基分類器組合。

綜合以上分析得到基于多樣性的選擇性集成單類分類算法PHD-EOC，其流程為：

訓(xùn)練階段：

(1)采用均勻生成負(fù)類樣本的方法[21]，得到驗(yàn)證樣本集

(2)分別使用M中的各多樣性生成方法訓(xùn)練基分類器，得到基分類器集合。

(3)使用H對(duì)驗(yàn)證樣本集分類，并以分類正確與否為依據(jù)將驗(yàn)證樣本集拆分為和，即

輸出：基分類器集合HSel={h1,h2,…,ht}

測(cè)試階段：

分別使用HSel中的基分類器對(duì)樣本分類，再采用使用多數(shù)投票策略即得到PHD-EOC算法的最終決策。

3.3 PHD-ECO算法的時(shí)間復(fù)雜度分析

記訓(xùn)練樣本數(shù)為M，假設(shè)集成過程中用到的單類分類算法為OCSVM，其訓(xùn)練時(shí)間復(fù)雜度是O(M3)，決策時(shí)間復(fù)雜度是O(M)，生成T個(gè)基單類分類模型的時(shí)間復(fù)雜度為T·O(M3)，這是使用Bagging, RSM和Boosting方法集成單類分類算法的訓(xùn)練時(shí)間復(fù)雜度。與傳統(tǒng)集成方法相比，PHD-EOC算法的額外時(shí)間消耗是對(duì)基分類器的多樣性分析和排序過程，其中多樣性分析的時(shí)間復(fù)雜度是T·O(M)，使用快速選擇算法選出前γ·T個(gè)基分類器的時(shí)間復(fù)雜度為O(T)。因此PHD-EOC訓(xùn)練階段的時(shí)間復(fù)雜度為T·O(M3)+T·O(M)+O(T)≈T·O(M3)，即絕大多數(shù)時(shí)間復(fù)雜度源自基單類分類器的訓(xùn)練時(shí)間，因此PHD-EOC相對(duì)于傳統(tǒng)集成方法的訓(xùn)練階段時(shí)間復(fù)雜度提升很小。

在決策階段，全部基分類器參與集成的決策時(shí)間復(fù)雜度是T·O(M)，而PHD-EOC算法的決策時(shí)間復(fù)雜度是γ·T·O(M)，決策階段時(shí)間復(fù)雜度有較大降低，降低的程度取決于基分類器選擇比率γ。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 標(biāo)準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn)

為驗(yàn)證PHD-EOC算法的有效性，將其與選擇傳統(tǒng)集成學(xué)習(xí)方法進(jìn)行對(duì)比。實(shí)驗(yàn)程序使用MATLAB r2012b編寫，基分類器中OCSVM使用LIBSVM[22]提供的算法實(shí)現(xiàn)，NegSVDD算法通過修改LIBSVM實(shí)現(xiàn)。

實(shí)驗(yàn)中選擇Bagging, RSM方法和Boosting這3種最常用的集成學(xué)習(xí)方法作為對(duì)比算法。由于并沒有廣泛認(rèn)可地特別針對(duì)單類分類問題的標(biāo)準(zhǔn)數(shù)據(jù)集，單類分類研究通常使用UCI數(shù)據(jù)集的二分類數(shù)據(jù)集，并指定兩類中樣本較多的一類為正類[1]。實(shí)驗(yàn)從UCI數(shù)據(jù)集中選擇了單類分類研究常用的Biomed, Breast, Diabetes, Ecoli, Heart, Hepatitis, Imports, Sonar, Spectf和Wine等10個(gè)數(shù)據(jù)集構(gòu)成11個(gè)單類分類數(shù)據(jù)集，其中Sonar數(shù)據(jù)集在使用傳統(tǒng)集成單類分類器時(shí)效果較差[8,9]，故以其兩類分別為正負(fù)類形成了兩個(gè)單類分類數(shù)據(jù)集。

實(shí)驗(yàn)采用二迭交叉驗(yàn)證重復(fù)10次取平均值，使用OCSVM算法作為基分類器生成算法，其中正類拒絕率設(shè)置為0.1。OCSVM使用常用的RBF核函數(shù)，核函數(shù)中關(guān)鍵的參數(shù)核帶寬使用二迭交叉驗(yàn)證的網(wǎng)格搜索得到，搜索范圍是{2k}，其中k取[-10,10]內(nèi)的整數(shù)，實(shí)驗(yàn)過程為：

步驟1 分別按照Bagging, RSM和Boosting各自的基分類器生成方法，各得到90個(gè)基單類分類器并按照各自的集成方式集成，分別記為“Bagging”,“RSM”和“Boosting”。同時(shí)，從3種方法的基分類器集合中各抽取前30個(gè)基分類器，這些基分類器多數(shù)投票得到的集成單類分類器記為“ALL”。

步驟.2 使用PHD-EOC算法，分別取選擇率γ為0.2, 0.4和0.6，修剪步驟3得到的集成單類分類器，將得到的集成單類分類器模型分別記為“PHDEOC(γ=0.2)”,“PHD-EOC (γ=0.4)”和“PHDEOC (γ=0.6)”。

步驟3 評(píng)估前兩個(gè)步驟得到的7個(gè)集成單類分類器，分別比較它們的AUC, F指標(biāo)(F-measure，取1α=，記為F1)和G指標(biāo)(G-measure，取1α=，記為G1)，完整的對(duì)比實(shí)驗(yàn)結(jié)果如表1所示。

從表1給出的實(shí)驗(yàn)結(jié)果中可以看出：

(1)在基分類器個(gè)數(shù)相等的前提下，混合使用多種方法生成基分類器集合也可以有效地提高集成基單類分類器的性能。但在一些數(shù)據(jù)集上“ALL”和RSM等單一方法的性能并無明顯差距，這說明了單獨(dú)使用混合多樣性生成策略提高多樣性是不夠的，需要通過PHD-EOC算法的修剪步驟提高集成單類分類器性能。

(2)PHD-EOC算法的AUC, F-measure和G-means指標(biāo)明顯優(yōu)于Bagging, RSM, Boosting和“ALL”算法，說明選擇性集成確實(shí)能夠在降低參與集成基分類器個(gè)數(shù)的同時(shí)，提高集成單類分類器的性能。

(3)修剪步驟的最優(yōu)選擇率γ因數(shù)據(jù)集而異，但實(shí)驗(yàn)結(jié)果表明在基分類器個(gè)數(shù)相同的情況下，經(jīng)過PHD-EOC排序后的集成分類器性能幾乎總是優(yōu)于隨機(jī)順序集成。

為說明基分類器集成順序?qū)煞诸惼餍阅艿挠绊?，將PHD-EOC算法和隨機(jī)順序集成的“ALL”算法的迭代性能曲線對(duì)比如圖3所示。在迭代過程中，PHD-EOC算法的迭代AUC指標(biāo)幾乎始終優(yōu)于隨機(jī)集成順序的“ALL”集成分類器，說明依照多樣性分析得到的集成順序能夠有效提升集成單類分類器的性能。

表1 UCI數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)結(jié)果

4.2 惡意程序檢測(cè)實(shí)驗(yàn)

本節(jié)通過將PHD-EOC算法用于計(jì)算機(jī)安全領(lǐng)域中惡意程序行為檢測(cè)來進(jìn)一步評(píng)估其在實(shí)際應(yīng)用問題中的表現(xiàn)。在惡意程序檢測(cè)問題中，正常程序種類繁多，功能各異，收集樣本的難度很大，而惡意程序行為具有普遍的相似性，并且可以從一些專門的網(wǎng)站批量獲取，容易得到數(shù)量較大的惡意程序樣本集。因此正常程序類樣本很難被視為整個(gè)正常程序類別的充分采樣。單類分類模型不對(duì)負(fù)類樣本的采樣情況做任何要求，因此將正常程序類作為負(fù)類更符合樣本特性，并有效降低誤檢率。實(shí)驗(yàn)采用實(shí)驗(yàn)室自主開發(fā)的Osiris系統(tǒng)[23]捕獲到的程序行為數(shù)據(jù)，每個(gè)惡意程序樣本以2488維的離散值特征表示。數(shù)據(jù)集包含3155個(gè)正常程序樣本和15263個(gè)惡意程序樣本。其中正常程序樣本采用惡意程序分析研究中通行的做法收集自全新安裝的Windows 7操作系統(tǒng)，惡意程序從VX-Heaven②VX-Heaven, http://vxheaven.org，訪問時(shí)間2014年5月10日公開的惡意程序數(shù)據(jù)庫以及MLSEC③Machine Learning for Computer Security, http://www.mlsec.org，訪問時(shí)間2014年5月10日研究組提供的樣本中收集整理，包含后門、蠕蟲、Rootkit、木馬和病毒等常見類別的65個(gè)重要惡意程序家族，包含了主要惡意程序類別和各類別中典型的惡意程序家族，具有較充足的覆蓋能力，能夠代表絕大多數(shù)惡意程序。

圖3 PHD-EOC算法和隨機(jī)集成順序的集成單類分類器迭代AUC變化曲線

從表2中的實(shí)驗(yàn)結(jié)果可以看出：首先，3種經(jīng)典集成方法中RSM方法和Bagging方法效果較Boosting方法效果略好，這是因?yàn)閻阂獬绦蛐袨閿?shù)據(jù)中存在較多難以手工去除的噪聲，對(duì)噪聲敏感的Boosting方法性能造成了一定影響。其次，混合多樣性生成的“ALL”算法較Bagging, RSM和Boosting等單一集成算法性能更優(yōu)，該結(jié)果與之前分析和實(shí)驗(yàn)的結(jié)果一致，進(jìn)一步驗(yàn)證了提升基分類器集多樣性能夠提高集成單類分類器的性能。最后，PHD-EOC算法在多數(shù)情況下取得了比“ALL”更優(yōu)的性能，這驗(yàn)證了經(jīng)過修剪的集成單類分類器的性能優(yōu)勢(shì)。此外，選擇適中的選擇率γ能夠取得較好的集成單類分類器修剪結(jié)果。

表2 PHD-EOC算法在惡意程序行為檢測(cè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

由以上實(shí)驗(yàn)分析可知，PHD-EOC算法的性能普遍優(yōu)于其他集成單類分類算法，進(jìn)一步驗(yàn)證了PHD-EOC算法在較復(fù)雜的實(shí)際問題中的有效性，說明PHD-EOC算法具有較大的推廣應(yīng)用價(jià)值。

5 結(jié)束語

本文首先證明了單類分類器集成的性能提升效果，也指出不經(jīng)選擇的集成可能帶來的風(fēng)險(xiǎn)。通過實(shí)驗(yàn)分析了傳統(tǒng)集成方法在單類分類器集成中存在的多樣性不足是制約其性能的主要原因，證明了修剪步驟對(duì)集成單類分類器的作用，同時(shí)通過拆解集成損失得到了具體的修剪策略。在以上證明和分析的基礎(chǔ)上提出了PHD-EOC算法，該算法通過混合多樣性生成方法得到多樣性強(qiáng)的基單類分類器集合，之后通過分析基分類器多樣性與集成性能提升之間的關(guān)系，選擇一部分基分類器參與集成，在標(biāo)準(zhǔn)數(shù)據(jù)集和實(shí)際惡意程序檢測(cè)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果表明，PHD-EOC算法能夠得到性能優(yōu)于將全部基分類器集成的集成單類分類器。

[1] Tax D. One-class classification[D]. [Ph.D. dissertation]. Delft University of Technology, 2001.

[2] Xiao Ying-chao, Wang Huan-gang, Zhang Lin, et al.. Two methods of selecting Gaussian kernel parameters for one-class SVM and their application to fault detection[J]. Knowledge-Based Systems, 2014, 59(1): 75-84.

[3] Mennatallah A, Markus G, and Slim A. Enhancing one-class support vector machines for unsupervised anomaly detection[C]. Proceedings of the ACM SIGKDD Workshop on Outlier Detection and Description, Chicago, USA, 2013: 8-15.

[4] Shahid N, Naqvi I, and Qaisar S. One-class support vector machines: analysis of outlier detection for wireless sensor networks in harsh environments[J]. Artificial Intelligence Review, 2013, 39(1): 1-49.

[5] Tax D and Duin R. Support vector data description[J]. Machine Learning, 2004, 54(1): 45-66.

[6] Sch?lkopf B, Platt J, Shawe-Taylor J, et al.. Estimating the support of a high-dimensional distribution[J]. Neural Computation, 2001, 13(7): 1443-1471.

[7] Tax D and Duin R. Combining one-class classifiers[C]. Proceedings of 2nd International Workshop on Multiple Classifier Systems, Cambridge, UK, 2001: 299-308.

[8] Segui S, Igual L, and Vitria J. Bagged one-class classifiers in the presence of outliers[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2013, 27(5): 1-21. [9] Cheplygina V and Tax D. Pruned random subspace method for one-class classifiers[C]. Proceedings of the 10th International Conference on Multiple Classifier Systems, Naples, Italy, 2011: 96-105.

[10] Ratsch G, Mika S, Scholkopf B, et al.. Constructing boosting algorithms from SVMs: an application to one-class classification[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(9): 1184-1199.

[11] Aggarwal C. Outlier ensembles: position paper[J]. ACM Special Interest Group on Knowledge Discovery and Data Mining (SIGKDD) Explorations Newsletter, 2013, 14(2): 49-58.

[12] Steinwart I, Hush D, and Scovel C. A classification framework for anomaly detection[J]. Journal of Machine Learning Research, 2006, 6(1): 211-232.

[13] Caruana R, Niculescu-Mizil A, Crew G, et al.. Ensemble selection from libraries of models[C]. Proceedings of 21st International Conference on Machine Learning, Banff, Canada, 2004: 137-144.

[14] Kotsiantis S. Combining bagging, boosting, rotation forest and random subspace methods[J]. Artificial Intelligence Review, 2011, 35(3): 223-240.

[15] P kalska E, Duin R, and Skurichina M. A discussion on the classifier projection space for classifier combining[C]. Proceedings of 3rd International Workshop on Multiple Classifier Systems, Cagliari, Italy, 2002: 137-148.

[16] Guo L and Boukir S. Margin-based ordered aggregation for ensemble pruning[J]. Pattern Recognition Letters, 2013, 34(6): 603-609.

[17] Martinez-Muoz G, Hernández-Lobato D, and Suárez A. An analysis of ensemble pruning techniques based on ordered aggregation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 245-259.

[18] Fawcett T. An introduction to ROC analysis[J]. Pattern Recognition Letters, 2006, 27(8): 861-874.

[19] Tamon C and Xiang J. On the boosting pruning problem[C]. Proceedings of 11th European Conference on Machine Learning, Catalonia, Spain, 2000: 404-412.

[20] Désir C, Bernard S, Petitjean C, et al.. One class random forests[J]. Pattern Recognition, 2013, 46(12): 3490-3506.

[21] Tax D and Duin R. Uniform object generation for optimizing one-class classifiers[J]. The Journal of Machine Learning Research, 2001, 2(1): 155-173.

[22] Chang C and Lin C. LIBSVM: a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3): 1-27.

[23] Cao Ying, Liu Jia-chen, Miao Qi-guang, et al.. Osiris: a malware behavior capturing system implemented at virtual machine manage layer[C]. Proceedings of 8th International Conference on Computational Intelligence and Security, Guangzhou, China, 2012: 534-538.

劉家辰： 男，1988年生，博士生，研究方向?yàn)闄C(jī)器學(xué)習(xí)與計(jì)算機(jī)安全.

苗啟廣： 男，1972年生，教授，博士生導(dǎo)師，研究方向?yàn)橹悄軋D像處理與機(jī)器學(xué)習(xí).

曹 瑩： 女，1987年生，博士生，研究方向?yàn)闄C(jī)器學(xué)習(xí).

宋建鋒： 男，1978年生，講師，研究方向?yàn)橛?jì)算機(jī)安全與機(jī)器學(xué)習(xí).

權(quán)義寧： 男，1968年生，副教授，研究方向?yàn)榫W(wǎng)絡(luò)計(jì)算與網(wǎng)絡(luò)安全.

Ensemble One-class Classifiers Based on Hybrid Diversity Generation and Pruning

Liu Jia-chen Miao Qi-guang Cao Ying Song Jian-feng Quan Yi-ning
(School of Computer Science and Technology, Xidian University, Xi’an 710071, China)

Combining one-class classifiers using the classical ensemble methods is not satisfactory. To address this problem, this paper first proves that though one-class classification performance can be improved by a classifier ensemble, it can also degrade if the set of base classifiers are not selected carefully. On this basis, this study further analyzes that the lacking of diversity heavily accounts for performance degradation. Therefore, a hybrid method for generating diverse base classifiers is proposed. Secondly, in the combining phase, to find the most useful diversity, the one-class ensemble loss is split and analyzed theoretically to propose a diversity based pruning method. Finally, by combining these two steps, a novel ensemble one-class classifier named Pruned Hybrid Diverse Ensemble One-class Classifier (PHD-EOC) is proposed. The experimental results on the UCI datasets and a malicious software detection dataset show that the PHD-EOC strikes a better balance between the diverse base classifiers and classification performance. It also outperforms other classical ensemble methods for a faster decision speed. Key words: Machine learning; One-class classifier; Ensemble One-class Classifier (EOC); Classifier diversity; Ensemble pruning; Ensemble learning

TP181

A

1009-5896(2015)02-0386-08

10.11999/JEIT140161

2014-01-24收到，2014-06-03改回

國(guó)家自然科學(xué)基金(61272280, 41271447, 61272195)，教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃(NCET-12-0919)，中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金(K5051203020, K5051303016, K5051303018, BDY081422, K50513100006)和西安市科技局項(xiàng)目(CXY1341(6))資助課題

*通信作者：苗啟廣 qgmiao@gmail.com