基于云模型和粗糙集的特征選擇算法

黃巧云

(福州大學至誠學院 計算機工程系，福建福州 350002)

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

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

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

1 理論研究

1.1 云模型

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

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

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

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

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

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

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

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

1.2 屬性約簡

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

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

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

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

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

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

其中［ck］={mij|mij=ck，mij以序列SO為標準排序，mij∈M}。

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

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

2 Cloud-Rough算法研究

本文提出的Cloud_Rough特征選擇算法，通過云模型對日志屬性進行排序，解決了由專家給定屬性序的主觀偏好的問題，然后再利用粗糙集進行基于屬性序的特征選擇，刪除冗余的屬性，以實現(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維屬性，對每類對象Xi∈U/ind(D)的重心點Exij進行升序排列，得到Ex1j?Ex2j?…?Exmj，其中1≤j≤|C|;

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實驗

3.1 實驗數(shù)據(jù)

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

3.2 實驗分析

為了驗證提出的特征選擇算法的有效性，本文主要進行以下三組實驗。

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

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

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

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

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

［8］劉常昱，李德毅，潘莉莉．基于云模型的不確定性知識表示［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．