基于近似約簡(jiǎn)的集成學(xué)習(xí)算法及其在入侵檢測(cè)中的應(yīng)用

江　峰，張友強(qiáng)，杜軍威，劉國柱，眭躍飛

基于近似約簡(jiǎn)的集成學(xué)習(xí)算法及其在入侵檢測(cè)中的應(yīng)用

江峰1，張友強(qiáng)1，杜軍威1，劉國柱1，眭躍飛2

（1.青島科技大學(xué)信息科學(xué)與技術(shù)學(xué)院，青島266061；2.中國科學(xué)院計(jì)算技術(shù)研究所，北京100190）

為了獲得較大差異性的基學(xué)習(xí)器來構(gòu)建集成學(xué)習(xí)器，從屬性空間劃分的角度來考慮集成學(xué)習(xí)問題，通過粗糙集理論定義了近似約簡(jiǎn)的概念，進(jìn)一步提出了基于近似約簡(jiǎn)的集成學(xué)習(xí)算法；本方法將數(shù)據(jù)集的屬性空間劃分為多個(gè)子空間，基于不同子空間對(duì)應(yīng)的數(shù)據(jù)集訓(xùn)練得到的基學(xué)習(xí)器具有較大的差異性，從而保證了集成學(xué)習(xí)器具有較強(qiáng)的泛化性能.為了驗(yàn)證本算法的有效性，本算法被應(yīng)用于網(wǎng)絡(luò)入侵檢測(cè)中.在KDD CUP 99數(shù)據(jù)集上的實(shí)驗(yàn)表明，與傳統(tǒng)的集成學(xué)習(xí)算法相比，本文所提出的算法具有更高的檢測(cè)率和更低的計(jì)算開銷，更適合于從海量高維的網(wǎng)絡(luò)數(shù)據(jù)中檢測(cè)入侵.

近似約簡(jiǎn)；集成學(xué)習(xí)；入侵檢測(cè)

由于具有良好的泛化性能，近年來集成學(xué)習(xí)在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域得到了廣泛關(guān)注［1］.Dietterich［2］更是將集成學(xué)習(xí)列為機(jī)器學(xué)習(xí)領(lǐng)域的四大研究方向之首.在集成學(xué)習(xí)中，主要有2種方法來產(chǎn)生基學(xué)習(xí)器:基于訓(xùn)練樣本擾動(dòng)的方法和基于屬性空間擾動(dòng)的方法.對(duì)于前者，代表性算法包括: Bagging和Boosting［3-4］.這些算法都是通過對(duì)訓(xùn)練樣本進(jìn)行重采樣來產(chǎn)生基學(xué)習(xí)器，其中，Bagging采用等概率方式對(duì)實(shí)例重采樣并訓(xùn)練基學(xué)習(xí)器；與Bagging方法不同，Boosting在產(chǎn)生后一個(gè)基學(xué)習(xí)器時(shí)，總是根據(jù)前一個(gè)基學(xué)習(xí)器的分類錯(cuò)誤率來改變實(shí)例抽樣的權(quán)重比，從而使得后一個(gè)基學(xué)習(xí)器具有較好的性能.對(duì)于后者，代表性算法主要是隨機(jī)子空間法（random subspace method RSM）［5-7］，該方法將訓(xùn)練集的屬性空間隨機(jī)劃分成不同的屬性子集，并基于多個(gè)屬性子集來構(gòu)建不同的基學(xué)習(xí)器.

目前的集成學(xué)習(xí)算法大多采用基于訓(xùn)練樣本擾動(dòng)的方法來產(chǎn)生基學(xué)習(xí)器，采用基于屬性空間擾動(dòng)的方法還比較少，相關(guān)研究主要集中在對(duì)RSM的一些改進(jìn)和擴(kuò)展［6-11］.例如，Ho［6］將RSM應(yīng)用于決策樹學(xué)習(xí)，從而得到了決策森林算法.該算法采用RSM將數(shù)據(jù)集的屬性空間隨機(jī)劃分為多個(gè)屬性子集，然后基于每個(gè)屬性子集對(duì)應(yīng)的數(shù)據(jù)集來構(gòu)建決策樹，最后將這些決策樹集成在一起來構(gòu)成決策森林.在此基礎(chǔ)上，Breiman［7］進(jìn)一步將Bagging方法和RSM相結(jié)合并用于決策樹學(xué)習(xí)，從而得到了隨機(jī)森林算法，該算法在建立每棵決策樹時(shí)，同時(shí)對(duì)數(shù)據(jù)集的實(shí)例空間和屬性空間進(jìn)行擾動(dòng).實(shí)驗(yàn)表明，隨機(jī)森林算法的性能要好于決策森林.Bryll等［8］提出了一種稱之為“屬性Bagging”的集成學(xué)習(xí)方法，該方法首先確定一個(gè)合適的特征子集大小，然后隨機(jī)選擇一組固定大小的特征子集來構(gòu)建集成學(xué)習(xí)器.姚旭等［9］提出了一種基于RSM和AdaBoost的自適應(yīng)集成學(xué)習(xí)方法.該方法利用粒子群算法尋找使得AdaBoost依樣本權(quán)重抽取的數(shù)據(jù)集分類錯(cuò)誤率最小化的最優(yōu)特征權(quán)重分布，然后根據(jù)最優(yōu)特征權(quán)重分布產(chǎn)生隨機(jī)子空間，最后用于Adaboost的訓(xùn)練過程中，實(shí)驗(yàn)結(jié)果表明該方法具有較好的性能.上述方法都是采用隨機(jī)策略來擾動(dòng)屬性空間，從而得到不同的基學(xué)習(xí)器.然而，僅僅采用隨機(jī)策略進(jìn)行屬性空間的劃分可能是不恰當(dāng)?shù)?，因?yàn)殡S機(jī)劃分屬性空間具有一定的盲目性，在很多時(shí)候，由RSM所產(chǎn)生的集成學(xué)習(xí)器的性能難以得到保證.對(duì)此，Guo等［11］提出了一種基于動(dòng)態(tài)粗糙子空間的選擇性集成學(xué)習(xí)算法DRSSE.在該算法中，使用屬性的最大依賴度來減少約簡(jiǎn)的搜索空間，同時(shí)增強(qiáng)被選擇的約簡(jiǎn)之間的差異性，DRSSE使用一個(gè)評(píng)價(jià)函數(shù)來動(dòng)態(tài)平衡多個(gè)約簡(jiǎn)的學(xué)習(xí)精度和約簡(jiǎn)之間的多樣性.實(shí)驗(yàn)結(jié)果證實(shí)了DRSSE算法比其他集成學(xué)習(xí)算法具有更好的性能.此外，胡清華等提出了一種基于粗糙子空間的集成學(xué)習(xí)算法 FS-PPEROS［12］，該算法將粗糙集的屬性約簡(jiǎn)技術(shù)引入到屬性空間的劃分中［13-14］，使用多個(gè)約簡(jiǎn)來劃分屬性空間，從而構(gòu)建不同的基學(xué)習(xí)器.為了得到足夠多的約簡(jiǎn)，Hu等［12］放寬了粗糙集中屬性重要性的選擇標(biāo)準(zhǔn)，他們認(rèn)為可以選擇重要性排在第2或第3的屬性作為目標(biāo)屬性，從而在生成約簡(jiǎn)的過程中對(duì)屬性的選擇進(jìn)行擾動(dòng)，以獲得多個(gè)約簡(jiǎn).實(shí)驗(yàn)表明，與RSM相比，F(xiàn)S-PP-EROS具有更好的泛化性能.

近年來，機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘技術(shù)在入侵檢測(cè)領(lǐng)域的廣泛應(yīng)用，極大地提升了入侵檢測(cè)系統(tǒng)的準(zhǔn)確率，降低了其誤警率.作為機(jī)器學(xué)習(xí)的一個(gè)重要研究方向，集成學(xué)習(xí)在入侵檢測(cè)領(lǐng)域也得到了廣泛應(yīng)用.當(dāng)前已有許多集成學(xué)習(xí)算法被應(yīng)用于入侵檢測(cè)系統(tǒng)中［15-19］，例如，譚愛平等［15］提出了一種基于SVM的入侵檢測(cè)集成學(xué)習(xí)算法，該算法采用SVM來訓(xùn)練基學(xué)習(xí)器，并利用Boosting來進(jìn)行基學(xué)習(xí)器的集成.徐沖等［16］分別利用改進(jìn)的BP神經(jīng)網(wǎng)絡(luò)算法和支持向量機(jī)算法來訓(xùn)練基學(xué)習(xí)器，并利用相應(yīng)的集成學(xué)習(xí)器來檢測(cè)入侵.Abdulla等［17］設(shè)計(jì)了基于粒子群優(yōu)化的集成網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)，該集成方法使用粒子群算法產(chǎn)生權(quán)重來建立基學(xué)習(xí)器，使得基學(xué)習(xí)器對(duì)于入侵檢測(cè)具有較高的檢測(cè)率，從而使得集成學(xué)習(xí)器具有較高的檢測(cè)率.Kavitha等［18］提出了基于中智邏輯分類器的集成學(xué)習(xí)入侵檢測(cè)模型，由于該模型采用了中智邏輯分類器，它能夠處理模糊的、不確定的、不完整的和不一致的信息，再加上使用了集成學(xué)習(xí)技術(shù)，因此該模型能夠處理復(fù)雜、不確定的網(wǎng)絡(luò)數(shù)據(jù)，實(shí)驗(yàn)結(jié)果證實(shí)了該模型的有效性.

集成學(xué)習(xí)能夠有效提升學(xué)習(xí)系統(tǒng)的泛化能力，并保持較小的誤差.在入侵檢測(cè)中引入集成學(xué)習(xí)方法，可以在先驗(yàn)知識(shí)不足的情況下仍保證有較好的檢測(cè)性能.然而，在面對(duì)海量、高維的網(wǎng)絡(luò)數(shù)據(jù)時(shí)，現(xiàn)有的集成學(xué)習(xí)算法將面臨一個(gè)挑戰(zhàn)，即入侵檢測(cè)系統(tǒng)的實(shí)時(shí)性難以保證，在入侵行為被系統(tǒng)檢測(cè)出來之前，可能入侵行為就已經(jīng)發(fā)生.當(dāng)前的集成學(xué)習(xí)算法大多采用基于訓(xùn)練樣本擾動(dòng)的方法來產(chǎn)生基學(xué)習(xí)器，在處理高維數(shù)據(jù)時(shí)，這些算法將面臨非常大的計(jì)算開銷.因此，要想從海量、高維的網(wǎng)絡(luò)數(shù)據(jù)中實(shí)時(shí)地檢測(cè)出入侵，有必要對(duì)現(xiàn)有的集成學(xué)習(xí)算法進(jìn)行改進(jìn)［19］.

針對(duì)現(xiàn)有的集成學(xué)習(xí)算法所存在的問題，本文提出了一種基于近似約簡(jiǎn)的集成學(xué)習(xí)算法ELAR，并利用該算法來檢測(cè)入侵.ELAR算法首先利用粗糙集的屬性約簡(jiǎn)技術(shù)對(duì)高維的屬性空間進(jìn)行降維處理，即生成多個(gè)近似約簡(jiǎn)；然后，在每個(gè)近似約簡(jiǎn)所對(duì)應(yīng)的低維子空間上構(gòu)建一個(gè)基學(xué)習(xí)器；最后，通過對(duì)這些基學(xué)習(xí)器進(jìn)行集成，從而得到集成學(xué)習(xí)器.在低維的屬性子空間上構(gòu)建基學(xué)習(xí)器可以有效降低入侵檢測(cè)系統(tǒng)的計(jì)算開銷，從而保證系統(tǒng)的實(shí)時(shí)性.另外，本文在生成近似約簡(jiǎn)時(shí)，首先采用隨機(jī)抽取的方式選擇一個(gè)屬性到核中，然后再通過啟發(fā)式方式來選擇剩余的屬性，這樣就可以保證不同的近似約簡(jiǎn)之間的多樣性，從而使得相應(yīng)的基學(xué)習(xí)器之間也具有多樣性.

作為一種基于屬性空間擾動(dòng)的集成學(xué)習(xí)方法，ELAR與傳統(tǒng)的RSM存在著明顯的不同.RSM采用隨機(jī)策略對(duì)屬性空間進(jìn)行劃分，而ELAR則采用屬性約簡(jiǎn)技術(shù)來對(duì)屬性空間進(jìn)行劃分.雖然ELAR在確定貪心搜索的起點(diǎn)時(shí)也采用了隨機(jī)策略，但在選擇剩余的屬性時(shí)都采用了貪心策略.因此，由ELAR所生成的近似約簡(jiǎn)與初始屬性集具有相同或相近的分類能力，而由RSM所生成的屬性子集則有可能具有非常低的分類能力，從而影響到基學(xué)習(xí)器的性能.相對(duì)于RSM，ELAR不僅可以保證基學(xué)習(xí)器的多樣性，而且還可以保證每個(gè)基學(xué)習(xí)器都具有較好的性能.另外，ELAR與Hu等［12］所提出的FSPP-EROS算法也存在明顯的不同.在ELAR中，本文對(duì)傳統(tǒng)的約簡(jiǎn)定義進(jìn)行了擴(kuò)展，提出了近似約簡(jiǎn)的概念，并由此提出了一種近似約簡(jiǎn)算法，該算法能夠產(chǎn)生足夠多差異性大的近似約簡(jiǎn).在FS-PPEROS中Hu等并沒有對(duì)約簡(jiǎn)概念本身進(jìn)行修改，而只是對(duì)屬性重要性的選擇標(biāo)準(zhǔn)進(jìn)行了修改.另外，F(xiàn)S-PP-EROS中也沒有引入隨機(jī)策略，例如，隨機(jī)選擇一個(gè)屬性到核中作為貪心搜索的起點(diǎn)，因此，該算法所生成的基學(xué)習(xí)器的多樣性不一定能夠得到保證.

為了驗(yàn)證ELAR在入侵檢測(cè)中的效果，本研究利用KNN算法來訓(xùn)練基學(xué)習(xí)器，并在KDD Cup 99數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)［20］.在KDD Cup 99數(shù)據(jù)集上利用ELAR來檢測(cè)入侵主要包括以下4個(gè)步驟:1）在訓(xùn)練集上采用近似約簡(jiǎn)算法生成多個(gè)近似約簡(jiǎn)；2）在每個(gè)近似約簡(jiǎn)所對(duì)應(yīng)的屬性子空間上訓(xùn)練一個(gè)基學(xué)習(xí)器；3）將多個(gè)基學(xué)習(xí)器通過多數(shù)投票的方式集成在一起，從而得到集成學(xué)習(xí)器；4）在待檢測(cè)的數(shù)據(jù)上，利用集成學(xué)習(xí)器進(jìn)行入侵檢測(cè)，并返回入侵檢測(cè)結(jié)果.實(shí)驗(yàn)結(jié)果表明:與現(xiàn)有的集成學(xué)習(xí)算法Bagging、Adaboost和RSM相比，ELAR具有更好的性能.

1　相關(guān)概念介紹

在粗糙集中，信息表是一個(gè)四元組IS=（U，A，V，f）.式中:U和A分別為對(duì)象集和屬性集；V為所有屬性論域的并，即，其中Va為屬性a的值域；f:U×A→V為一個(gè)信息函數(shù)，使得對(duì)任意a∈A以及x∈U，f（x，a）∈Va［13-14］.

進(jìn)一步，A又可以劃分為2個(gè)不相交的子集——條件屬性集C和決策屬性集D.這種特殊的信息表被稱為決策表，簡(jiǎn)記DT=（U，C，D，V，f）.

給定決策表DT=（U，C，D，V，f），對(duì)于任意B?C∪D，定義由B所決定的一個(gè)不可分辨關(guān)系IND（B）為:IND（B）=｛（x，y）∈U×U:?a∈B（f（x，a）=f（y，a））｝.可以證明，IND（B）是U上的一個(gè)等價(jià)關(guān)系.IND（B）將U劃分成多個(gè)等價(jià)類，所有這些等價(jià)類的集合就構(gòu)成U的一個(gè)劃分，記為U/IND（B）.

定義1［13-14］（上、下近似）給定決策表DT=（U，C，D，V，f），對(duì)任意B?C∪D和X?U，X的B-上近似和B-下近似分別定義為

定義2［13-14］（正區(qū)域）給定決策表DT=（U，C，D，V，f），對(duì)任意B?C，定義D的B-正區(qū)域POSB（D）為

定義3［13-14］（核屬性）給定決策表DT=（U，C，D，V，f），對(duì)任意屬性 b∈C，如果POSC-｛b｝（D）≠POSC（D），那么稱b為C中相對(duì)于D的一個(gè)核屬性.所有的核屬性所組成的集合CoreD（C）被稱為C相對(duì)于D的核.

定義4［13-14］（屬性重要性）給定決策表DT=（U，C，D，V，f），對(duì)任意B?C和c∈C-B，屬性c相對(duì)于B和D的重要性定義為

2　近似約簡(jiǎn)與基于近似約簡(jiǎn)的集成學(xué)習(xí)

在粗糙集中，一個(gè)約簡(jiǎn)就是能夠分辨出對(duì)象屬于不同決策值的最小屬性子集.理論上來說，在一個(gè)約簡(jiǎn)后的數(shù)據(jù)集上所訓(xùn)練的基學(xué)習(xí)器與在初始數(shù)據(jù)集上訓(xùn)練的基學(xué)習(xí)器具有相同的性能.

對(duì)于一個(gè)給定的決策表，由于約簡(jiǎn)屬性集和初始屬性集具有相同的分類能力，因此可以在每個(gè)約簡(jiǎn)所對(duì)應(yīng)的屬性子空間上來訓(xùn)練基學(xué)習(xí)器，這樣不僅可以降低基學(xué)習(xí)器的訓(xùn)練時(shí)間，而且還可以保證每個(gè)基學(xué)習(xí)器的性能.換句話說，可以通過粗糙集中的屬性約簡(jiǎn)技術(shù)來擾動(dòng)訓(xùn)練集的屬性空間，從而構(gòu)建一個(gè)集成學(xué)習(xí)器.當(dāng)采用屬性約簡(jiǎn)技術(shù)來擾動(dòng)訓(xùn)練集的屬性空間時(shí)，首先要解決的一個(gè)問題就是約簡(jiǎn)的數(shù)量可能不足.眾所周知，不同數(shù)據(jù)集上的約簡(jiǎn)數(shù)量是不一樣的.對(duì)于很多數(shù)據(jù)集而言，約簡(jiǎn)的數(shù)量非常少，最壞的情況下可能沒有任何約簡(jiǎn).當(dāng)約簡(jiǎn)的數(shù)量不夠時(shí)，就不能獲得足夠多的基學(xué)習(xí)器，從而影響到集成學(xué)習(xí)器的構(gòu)建.針對(duì)上述問題，本文對(duì)傳統(tǒng)的約簡(jiǎn)定義進(jìn)行擴(kuò)展，提出一種近似約簡(jiǎn)的概念，并由此提出一種近似約簡(jiǎn)算法.采用近似約簡(jiǎn)對(duì)訓(xùn)練集的屬性空間進(jìn)行擾動(dòng)，可以保證約簡(jiǎn)的數(shù)量足夠多，從而獲得足夠多的基學(xué)習(xí)器.

在傳統(tǒng)的粗糙集約簡(jiǎn)定義中，給定一個(gè)決策表DT=（U，C，D，V，f），如果R是初始屬性集C的一個(gè)約簡(jiǎn)，那么R必須與C具有完全相同的分類能力，即 |POSR（D）|=|POSC（D）|.上述關(guān)于約簡(jiǎn)的要求過于嚴(yán)格，從而導(dǎo)致很多數(shù)據(jù)集上的約簡(jiǎn)數(shù)量非常少.為了保證在每個(gè)數(shù)據(jù)集上約簡(jiǎn)的數(shù)量都足夠多，有必要對(duì)上述要求進(jìn)行適當(dāng)?shù)姆潘?，?如果R是C的一個(gè)約簡(jiǎn)，那么R與C具有相同或者相近的分類能力.通過上述修改，就得到了近似約簡(jiǎn)的概念，具體定義如下.

定義5（近似約簡(jiǎn)）給定決策表DT=（U，C，D，V，f），對(duì)任意AR?C，如果滿足|POSC（D）|≥|POSAR（D）|≥δ×|POSC（D）|，那么稱AR為C相對(duì)于D的一個(gè)近似約簡(jiǎn)，其中，δ∈（0，1］是一個(gè)給定的閾值，稱δ為近似度.

從定義5可以看出，雖然近似約簡(jiǎn)AR的分類能力可能要低于初始屬性集C，但是它們的分類能力是近似相等的.AR與C的分類能力的近似程度可以通過閾值δ來控制.若δ越大，則AR的分類能力就越接近于C，特別是，當(dāng) δ=1時(shí)，AR的分類能力等于C，這時(shí)AR就演變成傳統(tǒng)的約簡(jiǎn)了.

為了獲得足夠多的約簡(jiǎn)來構(gòu)建基學(xué)習(xí)器，本文適當(dāng)放松了傳統(tǒng)方法對(duì)約簡(jiǎn)的嚴(yán)格要求，雖然這種放松可能會(huì)導(dǎo)致AR的分類能力比C要低，從而影響到由AR所構(gòu)建的基學(xué)習(xí)器的精度，但這種犧牲是值得的.因?yàn)锳R的分類能力與C之間的差距可以通過閾值δ來控制，通過合理地設(shè)置δ的取值，既可以保證由AR所構(gòu)建的基學(xué)習(xí)器具有較好的性能，同時(shí)又可以獲得足夠多的近似約簡(jiǎn).另外，集成學(xué)習(xí)不僅僅只關(guān)注每個(gè)基學(xué)習(xí)器的性能，基學(xué)習(xí)器的多樣性也是集成學(xué)習(xí)成功的一個(gè)關(guān)鍵因素.正如文獻(xiàn)［21］所指出的，當(dāng)基學(xué)習(xí)器達(dá)到最高的精度時(shí)，多樣性必然會(huì)降低，就需要在基學(xué)習(xí)器的精度與多樣性之間進(jìn)行折衷，找到精度與多樣性之間的平衡點(diǎn).因此，適當(dāng)?shù)亟档突鶎W(xué)習(xí)器的精度，實(shí)際上是為了提升基學(xué)習(xí)器的多樣性，通過獲得精度與多樣性之間的平衡來提高集成學(xué)習(xí)器的整體性能.

算法1給出了計(jì)算近似約簡(jiǎn)的詳細(xì)步驟.

算法1計(jì)算近似約簡(jiǎn)

輸入:決策表DT=（U，C，D，V，f），其中U=｛x1，…，xn｝，C=｛a1，…，am｝，近似約簡(jiǎn)的個(gè)數(shù)S，近似度δ.

輸出:S個(gè)近似約簡(jiǎn)的集合Set_AR.

2）采用計(jì)數(shù)排序的方法來計(jì)算正區(qū)域POSC（D）.

3）對(duì)任意a∈C，反復(fù)執(zhí)行:

①采用計(jì)數(shù)排序的方法來計(jì)算正區(qū)域POSC-｛a｝（D）；

②如果 POSC-｛a｝（D）≠POSC（D），則令CoreD（C）=CoreD（C）∪｛a｝.

4）令Rem=C-CoreD（C）表示從C中除去核之后的剩余屬性集.

5）當(dāng)|Set_AR|＜S時(shí)，反復(fù)執(zhí)行以下語句:

①令A(yù)R=CoreD（C）表示當(dāng)前的近似約簡(jiǎn).

②隨機(jī)從Rem中選擇一個(gè)屬性r，并且令A(yù)R= AR∪｛r｝，Rem=Rem-｛r｝.

③當(dāng) |POSAR（D）|＜δ×|POSC（D）|時(shí)，循環(huán)執(zhí)行以下操作:

（Ⅰ）對(duì)任意c∈Rem，計(jì)算屬性c相對(duì)于AR和D的重要性SGF（c，AR，D）；

（Ⅱ）從Rem中找出重要性最大的屬性m；

（芋）令A(yù)R=AR∪｛m｝，Rem=Rem-｛m｝.

④如果 AR?Set_AR，則令 Set_AR=Set_AR∪｛AR｝.

6）返回S個(gè)不重復(fù)的近似約簡(jiǎn)集合Set_AR.

在算法1中，要多次計(jì)算正區(qū)域POSB（D），其中B?C.而為了得到POSB（D），就需要先計(jì)算出劃分U/IND（B）.通常，計(jì)算U/IND（B）的時(shí)間復(fù)雜度為O（|U|2|）.為了降低計(jì)算U/IND（B）的時(shí)間開銷，本文先采用計(jì)數(shù)排序方法對(duì)論域U進(jìn)行排序，然后再計(jì)算 U/IND（B）［22］，從而使得計(jì)算 U/ IND（B）的時(shí)間復(fù)雜度僅為O（|B|×|U|）.

保證基學(xué)習(xí)器的多樣性是集成學(xué)習(xí)的一個(gè)主要目標(biāo).為了實(shí)現(xiàn)這一目標(biāo)，算法1將隨機(jī)策略與貪心策略結(jié)合在一起來生成近似約簡(jiǎn).在算法1的第②步中，從剩余屬性集Rem中隨機(jī)選擇一個(gè)屬性 r到當(dāng)前的近似約簡(jiǎn)AR中，然后再在第③步中通過貪心策略來選擇其他的屬性（即每次都選擇當(dāng)前最重要的屬性）到AR中，直到 |POSAR（D）|≥δ× |POSC（D）|.由于算法1每次貪心搜索當(dāng)前近似約簡(jiǎn)的起點(diǎn)（即CoreD（C）∪｛r｝）可能是不一樣的（每次貪心搜索的起點(diǎn)都是由隨機(jī)策略來決定的），因此可以有效增加不同近似約簡(jiǎn)之間的多樣性，這可以保證相應(yīng)的基學(xué)習(xí)器之間也具有多樣性.

在算法1的基礎(chǔ)上，本文進(jìn)一步提出了基于近似約簡(jiǎn)的集成學(xué)習(xí)算法ELAR.ELAR的詳細(xì)描述如算法2所示.

算法2ELAR

輸入:訓(xùn)練集T，近似約簡(jiǎn)的個(gè)數(shù)S，近似度δ.

輸出:集成學(xué)習(xí)器EL.

1）初始化:令集合E=芰.

2）在訓(xùn)練集T上，根據(jù)給定的近似約簡(jiǎn)個(gè)數(shù)S以及近似度δ，采用算法1計(jì)算出S個(gè)近似約簡(jiǎn)的集合Set_AR.

3）對(duì)每一個(gè)近似約簡(jiǎn)AR∈Set_AR，循環(huán)執(zhí)行:

①利用AR對(duì)訓(xùn)練集T的屬性空間進(jìn)行降維，從而得到約簡(jiǎn)之后的訓(xùn)練集TAR；

②采用給定的學(xué)習(xí)算法在約簡(jiǎn)后的訓(xùn)練集TAR上進(jìn)行訓(xùn)練，從而得到一個(gè)基學(xué)習(xí)器bAR；

③令E=E∪｛bAR｝.

4）通過多數(shù)投票的方式對(duì)集合E中的所有基學(xué)習(xí)器進(jìn)行集成，從而得到集成學(xué)習(xí)器EL.

5）返回集成學(xué)習(xí)器EL.

3　基于近似約簡(jiǎn)的集成學(xué)習(xí)流程與實(shí)例

考慮到傳統(tǒng)的基于RSM的集成學(xué)習(xí)所存在的不足，如基學(xué)習(xí)器分類精度低、生成的集成學(xué)習(xí)器不穩(wěn)定等，本文從粗糙集的屬性約簡(jiǎn)出發(fā)，定義了近似約簡(jiǎn)的概念，從而將數(shù)據(jù)集的屬性空間劃分為多個(gè)屬性子集；然后基于每一個(gè)屬性子集建立基學(xué)習(xí)器；最后通過投票的方式將這些基學(xué)習(xí)器集成起來.基于近似約簡(jiǎn)的集成學(xué)習(xí)的基本流程如圖1所示.

從圖1可以看出，基于近似約簡(jiǎn)的集成學(xué)習(xí)關(guān)鍵在于如何定義近似約簡(jiǎn)以及設(shè)計(jì)一種求解近似約簡(jiǎn)的算法，使得約簡(jiǎn)后的數(shù)據(jù)集和原始數(shù)據(jù)集具有相同或近似的分辨能力.本文采用隨機(jī)策略和貪心策略相結(jié)合的方式實(shí)現(xiàn)了近似約簡(jiǎn)算法.上一節(jié)詳細(xì)闡述了近似約簡(jiǎn)的定義、近似約簡(jiǎn)算法以及基于近似約簡(jiǎn)的集成學(xué)習(xí)算法ELAR.下面，舉例說明ELAR算法的具體實(shí)現(xiàn)過程.

例1以UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的trains數(shù)據(jù)集為例來說明ELAR算法的具體實(shí)現(xiàn)過程［23］.該數(shù)據(jù)集有10個(gè)實(shí)例和32個(gè)屬性，其中，決策屬性集D=｛dec｝，條件屬性集C=｛a1，a2，…，a31｝.將trains數(shù)據(jù)集中的10個(gè)實(shí)例劃分為2個(gè)部分，其中，前7個(gè)實(shí)例作為訓(xùn)練集，后3個(gè)實(shí)例作為測(cè)試集.表1給出了trains數(shù)據(jù)集的詳細(xì)信息.

假設(shè)近似約簡(jiǎn)的個(gè)數(shù)S=10，近似度δ=0.9.在trains數(shù)據(jù)集上采用ELAR算法進(jìn)行集成學(xué)習(xí)時(shí)，主要包括以下5個(gè)步驟:

第1步，計(jì)算核屬性.首先，利用訓(xùn)練集來構(gòu)建一個(gè)決策表DT=（U，C，D，V，f），并采用計(jì)數(shù)排序的方法計(jì)算出正區(qū)域POSC（D）；然后，對(duì)于任意屬性 a∈C，計(jì)算正區(qū)域 POSC-｛a｝（D），如果POSC（D）≠POSC-｛a｝（D），則將屬性a作為核屬性加入到集合Core中；最終，得到核屬性集Core=.因此，非核屬性集Rem=C-Core=C.

表1　Trains數(shù)據(jù)集Table 1　Trains data set

第2步，計(jì)算近似約簡(jiǎn).令當(dāng)前近似約簡(jiǎn)AR= Core，隨機(jī)從Rem中選擇一個(gè)屬性（這里，屬性a25被選中）加入到AR中.然后，貪心選擇剩余的屬性到AR中.對(duì)于任意c∈Rem，計(jì)算c相對(duì)于AR和D的重要性SGF（c，AR，D），并找出重要性最大的屬性.由于當(dāng)前屬性a2的重要性最大，因此，將a2加入到AR中.反復(fù)執(zhí)行上述過程，直到|POSAR（D）|≥0.9×|POSC（D）|.最終，得到一個(gè)近似約簡(jiǎn)AR=｛a2，a10，a13，a19，a25｝.由于之前AR沒有出現(xiàn)在約簡(jiǎn)集Set_AR中，因此，將AR加入到Set_AR中.

第3步，將第2步重復(fù)執(zhí)行多次，直到得到全部的10個(gè)近似約簡(jiǎn).通過多次迭代，最終Set_AR=｛AR1，AR2，…，AR10｝=｛｛a2，a10，a13，a19，a25｝，｛a2，a6，a13，a19，a29｝，…，｛a4，a10，a13，a20，a29｝｝.

第4步，通過每個(gè)近似約簡(jiǎn)生成一個(gè)基學(xué)習(xí)器，從而構(gòu)建一個(gè)集成學(xué)習(xí)器.在訓(xùn)練集｛x1，x2，…，x7｝上，分別根據(jù)Set_AR中的10個(gè)不同的近似約簡(jiǎn)來進(jìn)行訓(xùn)練，從而得到10個(gè)基學(xué)習(xí)器的集合E=｛b1，b2，…，b10｝.對(duì)E中的所有基學(xué)習(xí)器進(jìn)行集成，就可以得到集成學(xué)習(xí)器EL.

第5步，在測(cè)試集｛x8，x9，x10｝上來測(cè)試集成學(xué)習(xí)器EL的分類性能.對(duì)于測(cè)試實(shí)例x8，集合E中的10個(gè)基學(xué)習(xí)器所給出的分類結(jié)果有3個(gè)為“east”，有7個(gè)為“west”，因此，根據(jù)多數(shù)投票原則，集成學(xué)習(xí)器EL所給出的分類結(jié)果為“west”，這與x8的實(shí)際類別“west”是一致的.對(duì)于剩余的2個(gè)測(cè)試實(shí)例x9和x10，采用同樣的方法進(jìn)行測(cè)試，EL所給出的分類結(jié)果與它們的實(shí)際類別也是一致的.

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

4.1實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)

下面，通過實(shí)驗(yàn)來驗(yàn)證ELAR對(duì)于入侵行為的檢測(cè)能力.實(shí)驗(yàn)采用著名的 KDD Cup 99數(shù)據(jù)集［20］，該數(shù)據(jù)集包含了約49萬條連接記錄，總共有24種攻擊類型，這些攻擊類型又進(jìn)一步被分為DOS、R2L、U2R和Probe四大類［20］.實(shí)驗(yàn)采用KNN算法來訓(xùn)練基學(xué)習(xí)器，并將ELAR與傳統(tǒng)的集成學(xué)習(xí)算法Bagging［3］、Adaboost［4］以及RSM［5］進(jìn)行了比較，其中Bagging和Adaboost是2個(gè)具有代表性的基于訓(xùn)練樣本擾動(dòng)的集成學(xué)習(xí)方法，而RSM則是具有代表性的基于屬性空間擾動(dòng)的集成學(xué)習(xí)方法.

實(shí)驗(yàn)的硬件環(huán)境為:Intel處理器2.0 GHz，2 GB內(nèi)存.本研究采用Java語言實(shí)現(xiàn)了ELAR和KNN算法.對(duì)于RSM、Bagging和Adaboost這3種算法，則直接使用Weka中提供的算法進(jìn)行實(shí)驗(yàn)［24］.

由于KDD Cup 99過于龐大，并且包含了太多冗余的信息，因此，仿照陳仕濤等［25］的實(shí)驗(yàn)方法，從KDD Cup 99的一個(gè)10%子集“10%-KDD”中隨機(jī)抽取出一定比例的數(shù)據(jù)來進(jìn)行實(shí)驗(yàn)［20］.具體的抽取策略如下:1）對(duì)于10%-KDD中樣本數(shù)比較少的類別，所有樣本都被抽??；2）對(duì)于10%-KDD中樣本數(shù)比較多的類別，隨機(jī)抽取其中10%的樣本；3）對(duì)于10%-KDD中樣本數(shù)最多的幾個(gè)類別，只抽取其中1%的樣本.根據(jù)上述抽取策略，最終得到了一個(gè)包含6 338條記錄的數(shù)據(jù)集“Sample-KDD”.

表2分別給出了10%-KDD和Sample-KDD中各種攻擊類型以及正常連接的記錄數(shù).

Sample-KDD數(shù)據(jù)集總共有41個(gè)條件屬性，其中34個(gè)是連續(xù)型屬性，只有7個(gè)是離散型屬性［20］.由于粗糙集更適合于處理離散型數(shù)據(jù)，因此，在計(jì)算近似約簡(jiǎn)之前，本文預(yù)先對(duì)Sample-KDD中的連續(xù)型屬性進(jìn)行了離散化處理，離散化算法主要采用等寬區(qū)間 （equal width binning，EW）和等頻區(qū)間（equal frequency binning，EF）這 2種常用的算法［24］.

4.2實(shí)驗(yàn)步驟與設(shè)置

1）離散化與數(shù)據(jù)準(zhǔn)備.本文分別采用Weka中提供的EW和EF算法來離散化Sample-KDD中的連續(xù)型屬性.對(duì)于EW和EF，它們的區(qū)間數(shù)都設(shè)置為3［24］.

表2　各種攻擊類型以及正常連接的記錄數(shù)Table 2　Number of records for various attack categories and normal connections

需要指出的是，雖然Sample-KDD中包含了34個(gè)連續(xù)型屬性，但是其中有8個(gè)屬性的取值個(gè)數(shù)非常有限，沒有必要對(duì)它們進(jìn)行離散化［20］.因此，本文只針對(duì)其中26個(gè)連續(xù)型屬性進(jìn)行了離散化.對(duì)于每個(gè)經(jīng)過EW或EF離散化之后的Sample-KDD數(shù)據(jù)集，隨機(jī)選擇其中60%的數(shù)據(jù)作為訓(xùn)練集，并將剩余40%的數(shù)據(jù)作為測(cè)試集.

2）基學(xué)習(xí)器的生成.對(duì)于ELAR算法，首先在訓(xùn)練集上計(jì)算出S個(gè)近似約簡(jiǎn)，其中S被設(shè)定為10.然后，針對(duì)每個(gè)近似約簡(jiǎn)AR，利用AR對(duì)訓(xùn)練集的屬性空間進(jìn)行降維，并采用KNN算法在約簡(jiǎn)后的訓(xùn)練集上進(jìn)行訓(xùn)練，從而得到S個(gè)基學(xué)習(xí)器.

對(duì)于RSM、Bagging和Adaboost這3種算法，直接使用Weka中所提供的算法來生成基學(xué)習(xí)器，其中RSM的子空間維數(shù)設(shè)為21（即每個(gè)隨機(jī)子空間包含21個(gè)屬性）.這3種算法的集成規(guī)模（即基學(xué)習(xí)器的個(gè)數(shù)）均設(shè)為10，而其他參數(shù)的設(shè)置則使用Weka中的默認(rèn)值.

由于KNN算法的性能依賴于參數(shù)k的取值，因此，針對(duì)k=1，3，5分別做了3組不同的實(shí)驗(yàn).

3）集成學(xué)習(xí)器的生成與入侵檢測(cè).將前面所生成的10個(gè)基學(xué)習(xí)器集成在一起，從而得到一個(gè)集成學(xué)習(xí)器.最后，在測(cè)試集上利用該集成學(xué)習(xí)器來檢測(cè)入侵.

對(duì)于ELAR算法，本文采用多數(shù)投票的方式將所有的基學(xué)習(xí)器集成在一起，并由此來檢測(cè)入侵.對(duì)于RSM、Bagging和Adaboost這3種算法，仍然使用Weka中所提供的算法來構(gòu)建集成學(xué)習(xí)器以及在測(cè)試數(shù)據(jù)上來檢測(cè)入侵，相關(guān)參數(shù)的設(shè)置均采用Weka中的默認(rèn)值.

為了更準(zhǔn)確地評(píng)估每個(gè)算法的入侵檢測(cè)性能，本文將每個(gè)算法都重復(fù)執(zhí)行10次，并取這10次檢測(cè)結(jié)果的平均值作為最終的入侵檢測(cè)結(jié)果.

4.3實(shí)驗(yàn)結(jié)果

表3～5分別列出了當(dāng)k取1、3和5時(shí)各個(gè)集成學(xué)習(xí)算法在Sample-KDD上的入侵檢測(cè)結(jié)果，其中，EW算法被用來對(duì)Sample-KDD進(jìn)行離散化.

表3　Sample-KDD上的結(jié)果（k=1，采用EW進(jìn)行離散化）Table 3　Results on Sample-KDD（k=1 and using EW for discretization）

表4　Sample-KDD上的結(jié)果（k=3，采用EW進(jìn)行離散化）Table 4　Results on Sample-KDD（k=3 and using EW for discretization）

表5　Sample-KDD上的結(jié)果（k=5，采用EW進(jìn)行離散化）Table 5　Results on Sample-KDD（k=5 and using EW for discretization）

從表3～5可以看出，在由EW所離散化的Sample-KDD數(shù)據(jù)集上，相對(duì)于不同k的取值，ELAR的性能總是要好于Bagging、Adaboost和RSM，其中，ELAR的檢測(cè)率約為99%，其他幾種算法的檢測(cè)率約為95%，因此，可以計(jì)算得出，ELAR算法的檢測(cè)率要比其他算法高4%左右.另外，在4種集成學(xué)習(xí)算法當(dāng)中，ELAR的建模時(shí)間最短，而Adaboost的建模時(shí)間最長(zhǎng).Adaboost算法在建立后一個(gè)基學(xué)習(xí)器的時(shí)候需要根據(jù)前一個(gè)基學(xué)習(xí)器的學(xué)習(xí)錯(cuò)誤率來改變樣本重采樣的權(quán)重比，屬于迭代算法，因此其建模時(shí)間相對(duì)比較長(zhǎng).

表6～8分別給出了當(dāng)k取1、3和5時(shí)各個(gè)集成學(xué)習(xí)算法在Sample-KDD上的入侵檢測(cè)結(jié)果，其中，EF算法被用來對(duì)Sample-KDD進(jìn)行離散化.

表6　Sample-KDD上的結(jié)果（k=1，采用EF進(jìn)行離散化）Table 6　Results on Sample-KDD（k=1 and using EF for discretization）

表7　Sample-KDD上的結(jié)果（k=3，采用EF進(jìn)行離散化）Table 7　Results on Sample-KDD（k=3 and using EF for discretization）

表8　Sample-KDD上的結(jié)果（k=5，采用EF進(jìn)行離散化）Table 8　Results on Sample-KDD（k=5 and using EF for discretization）

從表6～8可以看出，在由EF所離散化的Sample-KDD數(shù)據(jù)集上，相對(duì)于不同的 k的取值，ELAR的檢測(cè)率也總是要高于其他3種集成學(xué)習(xí)算法，另外，ELAR的建模時(shí)間均少于其他算法.因此，上述實(shí)驗(yàn)結(jié)果同樣證明了ELAR算法具有較好的入侵檢測(cè)性能.

5　結(jié)論

1）定義了近似約簡(jiǎn)的概念，采用隨機(jī)策略和貪心策略相結(jié)合的方式實(shí)現(xiàn)了近似約簡(jiǎn)算法.

2）近似約簡(jiǎn)算法能夠?qū)?shù)據(jù)集的屬性空間劃分為多個(gè)與原始屬性集具有相同或近似分辨能力的屬性子集.

3）將基于近似約簡(jiǎn)的集成學(xué)習(xí)算法ELAR用于網(wǎng)絡(luò)入侵檢測(cè)，實(shí)驗(yàn)結(jié)果表明:與其他算法相比，ELAR具有更高的檢測(cè)率和更低的計(jì)算開銷.

［1］李文斌，劉椿年，鐘寧.基于兩階段集成學(xué)習(xí)的分類器集成［J］.北京工業(yè)大學(xué)學(xué)報(bào)，2010，36（3）:410-419.

LI W B，LIU C N，ZHONG N.Combining classifiers based on two-phase ensemble learning［J］.Journal of Beijing University of Technology，2010，36（3）:410-419.（in Chinese）

［2］DIETTERICH T G.Machine learning research:four current directions［J］.AI Magazine，1997，18（4）:97-136.

［3］BUHLMANN P，YU B.Analyzing bagging［J］.Annals of Statistics，2002，30（4）:927-961.

［4］SCHAPIRE R E.The boosting approach to machine learning:an overview［C］∥MSRI Workshop on Nonlinear Estimation and Classification.New York:Springer，2002: 149-171.

［5］HO T K.Nearest neighbors in random subspaces［C］∥Proceedingsofthe2ndInternationalWorkshoponStatistical Techniques in Pattern Recognition.Heidelberg: Springer，1998:640-648.

［6］HO T K.The random subspace method for constructing decision forests［J］.IEEETransactionsonPattern Analysis and Machine Intelligence，1998，20（8）:832-844.

［7］BREIMAN L.Random forests［J］.Machine Learning，2001，45（1）:5-32.

［8］BRYLL R，GUTIERREZ-OSUNA R，QUEK F.Attribute bagging:improving accuracy of classifier ensembles by using random feature subsets［J］.Pattern Recognition，2003，36（6）:1291-1302.

［9］姚旭，王曉丹，張玉璽，等.基于隨機(jī)子空間和AdaBoost的自適應(yīng)集成方法［J］.電子學(xué)報(bào)，2013，41（4）:810-814.

YAO X，WANG X D，ZHANG Y X，et al.A selfadaption ensemble algorithm based on random subspace and AdaBoost［J］.Acta Electronica Sinica，2013，41（4）:810-814.（in Chinese）

［10］蔣宗禮，徐學(xué)可.一種基于集成學(xué)習(xí)與類指示器的文本分類方法［J］.北京工業(yè)大學(xué)學(xué)報(bào)，2010，36（4）: 546-553.

JIANG Z L，XU X K.An ensemble learning and category indicator based text categorizing method［J］.Journal of Beijing University of Technology，2010，36（4）:546-553.（in Chinese）

［11］GUO Y，JIAO L，WANG S，et al.A novel dynamic rough subspace based selective ensemble［J］.Pattern Recognition，2015，48（5）:1638-1652.

［12］HU Q H，YU D R，XIE Z X，et al.EROS:ensemble rough subspaces［J］.Pattern Recognition，2007，40（12）:3728-3739.

［13］PAWLAK Z.Rough sets［J］.International Journal of Computer and Information Sciences，1982，11（5）:341-356.

［14］PAWLAK Z.Rough sets:theoretical aspects of reasoning aboutdata［M］.Dordrecht:KluwerAcademic Publishing，1991:23-65.

［15］譚愛平，陳浩，吳伯橋.基于SVM的網(wǎng)絡(luò)入侵檢測(cè)集成學(xué)習(xí)算法［J］.計(jì)算機(jī)科學(xué)，2014，41（2）:197-200.

TAN A P，CHEN H，WU B Q.Network intrusion intelligent detection algorithm based on AdaBoost［J］. Computer Science，2014，41（2）:197-200.（in Chinese）

［16］徐沖，王汝傳，任勛益.基于集成學(xué)習(xí)的入侵檢測(cè)方法［J］.計(jì)算機(jī)科學(xué)，2010，37（7）:217-219.

XU C，WANG R C，REN X Y.Ensemble learning based intrusion detection method［J］.Computer Science，2010，37（7）:217-219.（in Chinese）

［17］ABDULLA A A，MAMUN B I R.A novel SVM-kNNPSO ensemble method for intrusion［J］.Applied Soft Computing，2016，38:360-372.

［18］KAVITHA B，KARTHIKEYAN S，MAYBELL P S.An ensemble design of intrusion detection system for handling uncertainty usingneutrosophiclogicclassifier［J］. Knowledge-Based Systems，2012，28（2）:88-96.

［19］陳友，程學(xué)旗，李洋，等.基于特征選擇的輕量級(jí)入侵檢測(cè)系統(tǒng)［J］.軟件學(xué)報(bào)，2007，18（7）:1639-1651.

CHEN Y，CHENG X Q，LI Y，et al.Lightweight intrusion setection system based on feature selection［J］. Journal of Software，2007，18（7）:1639-1651.（in Chinese）

［20］ACM SIGKDD.The KDD Cup 99 dataset［DB/OL］.（1999-10-28）［2015-03-15］.http:∥kdd.ics.uci. edu/databases/kddcup99/kddcup99.html.

［21］KUNCHEVA L I，SKURICHINA M，DUIN R P W.An experimental study on diversity for bagging and boosting with linear classifiers［J］.Information Fusion，2002，3（4）:245-258.

［22］徐章艷，劉作鵬，楊炳儒，等.一個(gè)復(fù)雜度為max（O（|C||U|），O（|C|2|U/C|））的快速屬性約簡(jiǎn)算法［J］.計(jì)算機(jī)學(xué)報(bào)，2006，29（3）:391-399.

XU Z Y，LIU Z P，YANG B R，et al.A quick attribute reduction algorithm with complexity of max（O（|C||U|），O（|C|2|U/C|））［J］.Chinese Journal of Computers，2006，29（3）:391-399.（in Chinese）

［23］University of California Irvine.UCI machine learning repository［DB/OL］.［2015-03-15］.http:∥archive. ics.uci.edu/ml/.

［24］WITTEN I H，F(xiàn)RANK E，HALL M A.Data mining: practical machine learning tools and techniques［M］.3rd ed.Burlington:Morgan Kaufmann Publishers，2011: 79-112.

［25］陳仕濤，陳國龍，郭文忠，等.基于粒子群優(yōu)化和鄰域約簡(jiǎn)的入侵檢測(cè)日志數(shù)據(jù)特征選擇［J］.計(jì)算機(jī)研究與發(fā)展，2010，47（7）:1261-1267.

CHEN S T，CHEN G L，GUO W Z，et al.Feature selection of the intrusion detection data based on particle swarm optimization and neighborhood reduction［J］. Journal of Computer Research and Development，2010，47（7）:1261-1267.（in Chinese）

（責(zé)任編輯呂小紅）

Approximate Reducts-based Ensemble Learning Algorithm and Its Application in Intrusion Detection

JIANG Feng1，ZHANG Youqiang1，DU Junwei1，LIU Guozhu1，SUI Yuefei2
（1.College of Information Science&Technology，Qingdao University of Science and Technology，Qingdao 266061，China；2.Institute of Computing Technology，Chinese Academy of Sciences，Beijing 100190，China）

To obtain diverse base learners for construct ensemble learner，the issue of ensemble learning was considered from the perspective of partitioning the attribute space.Through rough set theory，the concept of approximate reduct was defined，and further an approximate reducts-based ensemble learning algorithm was proposed.The method could partition the attribute space of data set into multiple subspaces，and the base learners trained on data sets corresponding to different subspaces had large diversity，which guarantee that the ensemble learner has strong generalization performance.To verify the effectiveness of the algorithm，it was applied to network intrusion detection.Experimental results on the KDD CUP 99 data set demonstrate that compared with the traditional ensemble learning algorithms，the proposed method has higher detection rate and lower computational cost，which is more suitable for the detection of intrusions from the massive and high-dimensional network data.

approximate reducts；ensemble learning；intrusion detection

TP 181

A

0254-0037（2016）06-0877-09

10.11936/bjutxb2015100008

2015-10-07

國家自然科學(xué)基金資助項(xiàng)目（61303193）；山東省自然科學(xué)基金資助項(xiàng)目（ZR2014FM015）；山東省高等學(xué)校科技計(jì)劃資助項(xiàng)目（J11LG05）

江峰（1978—），男，副教授，主要從事數(shù)據(jù)挖掘、粗糙集方面的研究，E-mail:jiangkong@163.net