黃巧云

(福州大學(xué)至誠學(xué)院 計(jì)算機(jī)工程系，福建福州 350002)

入侵檢測系統(tǒng)是通過收集和分析系統(tǒng)日志，從而對(duì)網(wǎng)絡(luò)狀態(tài)做出正確的判斷［1］。但由于其日志中含有大量的冗余數(shù)據(jù)，因此如何快速、有效地從數(shù)據(jù)中獲取安全威脅信息，成為當(dāng)前的研究熱點(diǎn)。目前，人們主要通過特征選擇來消除冗余數(shù)據(jù)，在保證分類精度的前提下，通過降低特征空間的維度，從而快速、有效地提取網(wǎng)絡(luò)安全信息［1］。

粗糙集理論中的屬性約簡在特征選擇上具有天然的優(yōu)勢，它能夠在保持信息系統(tǒng)的分類精度的條件下，刪除冗余的屬性［2］。然而，基于粗糙集的屬性約簡大多是基于啟發(fā)式信息的算法，而這些算法的計(jì)算結(jié)果都是唯一的。但對(duì)于同一張數(shù)據(jù)表，不同屬性數(shù)據(jù)的提取難易程度不一樣，而且不同的人所關(guān)注的屬性也可能不同。因此若屬性約簡的結(jié)果是較難提取的數(shù)據(jù)屬性，或者是人們所不關(guān)注的，那么屬性約簡的意義就大打折扣。文獻(xiàn)［3］提出了一種基于屬性序的約簡算法，它能根據(jù)不同的屬性序，得到不同的約簡結(jié)果。然而，基于屬性序的約簡方法一般都是根據(jù)專家的意見或是操作者的經(jīng)驗(yàn)給出，主觀性比較大，不能很好地根據(jù)數(shù)據(jù)的實(shí)際分布情況給出屬性序［4］。

因此，本文在此提出一種基于云模型和粗糙集的特征選擇算法Cloud_Rough，通過云模型對(duì)入侵檢測系統(tǒng)日志屬性進(jìn)行排序，解決了由專家給定屬性序的主觀偏好的問題，在此基礎(chǔ)上，利用粗糙集進(jìn)行基于屬性序的約簡。在實(shí)際應(yīng)用中，利用基于云模型的屬性序算法得到的權(quán)重排序后，還可以根據(jù)專家的意見對(duì)屬性序進(jìn)行適當(dāng)?shù)恼{(diào)整，從而保證了屬性序的給定既符合數(shù)據(jù)的實(shí)際分布，又能滿足對(duì)屬性偏好的需求。

1 理論研究

1.1 云模型

設(shè)論域U={x1，x2，…，xm}，A是關(guān)于U上的定性概念，若論域中的元素xi對(duì)A的隸屬確定度CA(xi)∈［0，1］是一個(gè)有穩(wěn)定傾向隨機(jī)數(shù)，則確定度CA(xi)在論域上的分布稱為云模型，簡稱云［5］。

云的數(shù)字特征可以用期望值Ex，熵En和超熵He三個(gè)數(shù)值來表示，其中，期望值Ex反映模糊概念的信息中心;熵En指云的期望曲線的帶寬，是概念模糊度的度量;超熵He反映云的離散程度［5］。如式 (1)所示:

定義1 U是n維空間的論域，U={x1，x2，…，xm}，xi表示U中的第i類對(duì)象，xij則表示xi在第j維屬性空間的取值［6］，根據(jù)云模型的定義，可對(duì)其建模如下:

其中，Exij表示xij的重心點(diǎn)，即該云模型范圍內(nèi)的高頻率元素;Enij來描述云模型覆蓋的數(shù)值范圍;Xminij表示該維屬性空間的最小值點(diǎn);Xmaxij表示該維屬性空間的最大值點(diǎn);Xij表示在云模型的范圍內(nèi)任意一屬性值所對(duì)應(yīng)的隸屬度。

定義2 U是n維空間的論域，兩個(gè)對(duì)象xi，xj∈U，d(xik，xjk)表示兩個(gè)對(duì)象在第k維屬性空間的距離［7］。

根據(jù)云的3En規(guī)則［8］，當(dāng)d(Hik，Hjk)≥1時(shí)，說明兩個(gè)對(duì)象空間是相離的，第k維屬性可區(qū)分度高;當(dāng)d(Hik，Hjk)=0時(shí)，說明兩個(gè)對(duì)象空間完全重全，第k維屬性可區(qū)分度低。

定義3 U是n維空間的論域，U={x1，x2，…，xm}，根據(jù)定義2，第k維屬性的類別間距離可以定義如下:

定義4 U是n維空間的論域，任意兩個(gè)對(duì)象xi，xj∈U，當(dāng)d(xik，xjk)越大，則第k維屬性的可區(qū)分度越大，該屬性在分類的作用中越大，因此第k維屬性權(quán)重可以定義如下:

1.2 屬性約簡

屬性約簡［2］作為粗糙集理論的一個(gè)重要組成部分，能夠在保持信息系統(tǒng)的分類精度的前提下，刪除冗余的屬性，快速獲取有效數(shù)據(jù)。

定義5 設(shè)決策屬性集D，條件屬性集U/ind(D)={Y1，Y2，…，Yt}的正區(qū)域［2］可計(jì)算如下:

定義6 設(shè)M是決策表S的可辨識(shí)矩陣，?mij∈M，mij中的屬性從左到右繼承著序列SO，在序SO下mij中的第一個(gè)屬性稱為標(biāo)簽屬性［9］。

定義7 令M是決策表S=＜U，C∪D，V，f＞的可辨識(shí)矩陣。R(R?C且R≠Φ)是一個(gè)約簡，當(dāng)且僅當(dāng)?α∈M(α≠Φ→α∩R≠Φ)［9］。

定義8 指定標(biāo)簽屬性ck∈C，是C的一個(gè)屬性子集，集合L(SO)計(jì)算如下［9］:

定義9 可辨識(shí)矩陣M關(guān)于L(SO)的劃分［9］:

其中［ck］={mij|mij=ck，mij以序列SO為標(biāo)準(zhǔn)排序，mij∈M}。

定義10 假設(shè)可辨識(shí)矩陣M的一個(gè)等價(jià)類{［c1］，［c2］，…，［c|C|］}，則最大標(biāo)簽屬性的定義［10］:

綜合上述定義，基于屬性序的約簡算法是在給定屬性序的基礎(chǔ)上，按照屬性的重要性，將屬性逐個(gè)加入集合，直到計(jì)算出一個(gè)滿足的子集，再刪去當(dāng)中不必要的屬性［9］。然而，該算法是通過遍歷可辨識(shí)矩陣M來尋找非空標(biāo)簽屬性的，這樣不可避免地會(huì)帶來時(shí)間和空間上較大的開銷［9］。而文獻(xiàn) ［3］則通過引入分治法的思想，提出了一種快速計(jì)算標(biāo)簽屬性的算法，大大降低了算法的時(shí)間和空間復(fù)雜性。

2 Cloud-Rough算法研究

本文提出的Cloud_Rough特征選擇算法，通過云模型對(duì)日志屬性進(jìn)行排序，解決了由專家給定屬性序的主觀偏好的問題，然后再利用粗糙集進(jìn)行基于屬性序的特征選擇，刪除冗余的屬性，以實(shí)現(xiàn)在海量的數(shù)據(jù)中快速提取有效的信息。

輸入:決策表S=(U，R，V，f)，U為論域，R=C∪D為屬性集合。

輸出:特征選擇子集T。

Step1:?cj∈C，?Xi∈U/ind(D)，根據(jù)定義1建模，分別求出云模型的期望值Exij和熵Enij;

Step2:按照第j維屬性，對(duì)每類對(duì)象Xi∈U/ind(D)的重心點(diǎn)Exij進(jìn)行升序排列，得到Ex1j?Ex2j?…?Exmj，其中1≤j≤|C|;

Step3:對(duì)每一維屬性，根據(jù)式 (4)計(jì)算排序后的兩兩對(duì)象間的距離;

Step4:根據(jù)式 (5)分別計(jì)算每維屬性的類別間距;

Step5:根據(jù)式 (6)分別計(jì)算每維屬性的權(quán)重，并按升序排列，從而得到屬性序SO;

Step6:設(shè)C={c1，c2，…c|c|}，按照屬性序SO:c1＜c2＜… ＜c|c|，r=1，T=φ;

Step7:根據(jù)式 (7)，計(jì)算正區(qū)域POSC(D);

Step8:根據(jù)文獻(xiàn) ［3］所提的算法，計(jì)算決策表的非空標(biāo)簽屬性集合F;

Step9:設(shè)CN是F中標(biāo)號(hào)最大的標(biāo)簽屬性，如果CN∈T，轉(zhuǎn)到Step14;

Step10:令T=T∪{CN}且CN放在T的最后一位;同時(shí)令F=F－{CN};

Step11:令C`=φ，ti為T的標(biāo)簽屬性，按照i從大到小排列，并依次加入C'中;

Step12:令fi為F的標(biāo)簽屬性，按照i從小到大排列，再依次加入到C'中;

Step13:令C=φ，C=C`。根據(jù)新屬性序，計(jì)算非空標(biāo)簽屬性集合F，轉(zhuǎn)至Step9;

Step14:輸出特征選擇子集T。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文的實(shí)驗(yàn)數(shù)據(jù)采用標(biāo)準(zhǔn)數(shù)據(jù)集UCI的Heart數(shù)據(jù)源和Segmentation數(shù)據(jù)源，以及從KDD Cup 1999 Data的入侵檢測系統(tǒng)數(shù)據(jù)庫中隨機(jī)抽取的10 000條記錄作為測試數(shù)據(jù)。

3.2 實(shí)驗(yàn)分析

為了驗(yàn)證提出的特征選擇算法的有效性，本文主要進(jìn)行以下三組實(shí)驗(yàn)。

1)利用標(biāo)準(zhǔn)數(shù)據(jù)集UCI的Heart數(shù)據(jù)源和Segmentation數(shù)據(jù)源，屬性名用Ai表示(i=0，1，2，…，n－1)，其中n為屬性個(gè)數(shù)，進(jìn)行云模型 (Cloud model)的屬性重要性排序測試，并根據(jù)排序結(jié)果的前50%的屬性，與Weka［10］數(shù)據(jù)挖掘工具里提供的Genetic Search特征選擇算法選出的特征子集，以及全部屬性集，利用J-48分類器進(jìn)行分類，來驗(yàn)證該重要性排序的有效性。

表1是利用Weka數(shù)據(jù)挖掘工具所提供的J-48分類器分別對(duì)三類屬性集合進(jìn)行分類的結(jié)果。從表中可以看出，由云模型所選擇的屬性子集，分類效果與另兩種方式相差不多，說明該算法選擇出的50%屬性的重要性。實(shí)驗(yàn)證明基于云模型的屬性重要性排序的有效性。

表1 不同屬性子集的分類結(jié)果

2)利用Cloud_Rough算法與Weka數(shù)據(jù)挖掘工具提供的Generic Search、貪心式前向搜索和貪心式反向搜索三種算法［10］對(duì)KDD的測試數(shù)據(jù)集進(jìn)行特征選擇，再利用J-48分類器對(duì)約簡后的特征子集進(jìn)行分類，最后對(duì)測試結(jié)果進(jìn)行比較。

表2為不同特征選擇算法得到的屬性子集，而這當(dāng)中比如:服務(wù)類型 (service)、連接服務(wù)的次數(shù)(service_count)、登錄狀態(tài) (logged_in)等對(duì)于分類具有較為重要意義的特征屬性都包含在內(nèi)。

表3是在表2的基礎(chǔ)上，使用分類器對(duì)不同的特征子集進(jìn)行分類的結(jié)果。從表中可以看出，與其它的特征選擇方法相比，基于Cloud_Rough的算法，雖然約簡出的特征數(shù)較多，但是分類器構(gòu)建時(shí)間卻不長，而且識(shí)別率最高。

表2 不同特征選擇算法的特征子集

表3 不同特征子集的分類結(jié)果

3)利用Weka數(shù)據(jù)挖掘工具提供的J_48分類器與BayesNet分類器，分別對(duì)未進(jìn)行特征選擇的屬性集和經(jīng)由Cloud_Rough算法選擇的屬性子集進(jìn)行分類。

從表4中可以看出，經(jīng)過Cloud_Rough算法特征選擇后，在不同的分類器下分類正確率都有所提高，而且分類器的構(gòu)建時(shí)間減少。實(shí)驗(yàn)結(jié)果表明，本文提出的Cloud_Rough特征選擇算法不僅可以適用不同的分類器，而且可以改善分類器的性能，具有較高的效率。

表4 不同分類器的分類結(jié)果

4 結(jié)語

本文將云模型與粗糙集相結(jié)合，通過云模型對(duì)入侵檢測系統(tǒng)日志屬性進(jìn)行重要性排序，解決了由專家給定屬性序的主觀偏好的問題，在此基礎(chǔ)上進(jìn)行基于屬性序的快速約簡。實(shí)驗(yàn)的結(jié)果證明，該算法在大數(shù)據(jù)量下，仍能快速得到特征選擇的結(jié)果，并且達(dá)到較高水平的分類效果。

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

［2］陳昊，楊俊安，莊鎮(zhèn)泉．變精度粗糙集的屬性核和最小屬性約簡算法［J］．計(jì)算機(jī)學(xué)報(bào)，2012，35(5):1011－1017．

［3］胡峰，王國胤．屬性序下的快速約簡算法［J］．計(jì)算機(jī)學(xué)報(bào)，2007，30(8):1429－1434．

［4］關(guān)素潔．基于Rough集的屬性與屬性值約簡方法研究［D］．江西:南昌大學(xué)，2011．

［5］李德毅．知識(shí)表示中的不確定性［J］．中國工程科學(xué)，2000，2(10):73－79．

［6］劉延華，周柳鴻，陳國龍．基于云模型的入侵檢測日志數(shù)據(jù)特征選擇算法［J］．福州大學(xué)學(xué)報(bào):自然科學(xué)版，2011，39(6):812－818．

［7］張國英，沙云，劉旭紅，等．高維云模型及其在多屬性評(píng)價(jià)中的應(yīng)用［J］．北京理工大學(xué)學(xué)報(bào)，2004，24(12):1065－1069．

［8］劉常昱，李德毅，潘莉莉．基于云模型的不確定性知識(shí)表示［J］．計(jì)算機(jī)工程與應(yīng)用，2004，40(2):32－35．

［9］HU Xiao-hua，Cercone Nick．Learning in Relational Databases:A Rough Set Approach［J］．Computational Intelligence，1995，11(2):323 －338．

［10］Witten Lan H，F(xiàn)rank Eibe，Hall Mark A．Data Mining:Practical Machine Learning Tools and Techniques［M］．San Francisco:Morgan Kaufmann Publishers，2011．