基于數(shù)據(jù)挖掘的入侵檢測系統(tǒng)的改進與實現(xiàn)
從Apriori算法執(zhí)行過程可以了解到Apriori算法的缺點:一方面,在每一次產(chǎn)生候選項集時循環(huán)產(chǎn)生的組合過多,沒有具體考慮不符合閾值的組合;另一方面,對每個項集計算支持度時要對整個數(shù)據(jù)庫掃描一遍,對于分析網(wǎng)絡(luò)數(shù)據(jù)包這樣大型的數(shù)據(jù)庫會增加I/O開銷。這種開銷是隨著數(shù)據(jù)庫的記錄的增加呈幾何級數(shù)的增長?,F(xiàn)階段人們開始探索一種能減少系統(tǒng)I/O開銷的更為快捷的算法,相繼提出了許多改進的算法。主要有Park等人提出的基于哈希技術(shù)的DHP算法,Savasere等人提出的基于劃分技術(shù)的Partition算法,Toivonen提出的抽樣算法,Sampling、Zaki等人提出的基于等價類和圖論的MaxCique系列算法,S.Agarwal等人提出的采用有序樹數(shù)據(jù)結(jié)構(gòu)的TreeP-rojection算法以及Orlando等人提出的Apriori增強版的DCP算法等。而對于挖掘數(shù)據(jù)包是網(wǎng)絡(luò)數(shù)據(jù)包時,數(shù)據(jù)源的特征屬性較多而且數(shù)據(jù)包的記錄數(shù)較大,這就需要必須選擇合理的算法才能發(fā)現(xiàn)能描述用戶特征的規(guī)則。
1 引用作用度的Apriori_lift算法
1.1 作用度
作用度是采用相關(guān)分析描述規(guī)則內(nèi)在價值的度量,它描述的是項集X對Y的影響力的大小。作用度越高表示X的出現(xiàn)對Y出現(xiàn)的可能性影響越大,作用度度量的是X與Y之間蘊涵的實際強度。
作用度表示為:
1.2 Aprior=>lift算法的描述
第一步:大項集的生成;
第二步:采用作用度找出強關(guān)聯(lián)規(guī)則。
使用第一步找到的所有頻繁項集產(chǎn)生期望的規(guī)則。為了獲取強有效關(guān)聯(lián)規(guī)則,在使用信任度的基礎(chǔ)上增加作用度計算來度量規(guī)則的有效性。具體描述過程如下:
(1)對于每個頻繁K(K≥2)項集L,產(chǎn)生L的所有非空子集S;
(2)對于項集L的每個非空子集S,規(guī)則:
如果lift[S=>(L-S)]>1,則規(guī)則“S=>(L-S)”是強有效關(guān)聯(lián)規(guī)則,輸出。
2 算法性能比較
在局域網(wǎng)環(huán)境中(如圖1所示)捕獲網(wǎng)絡(luò)數(shù)據(jù)包2 000個,分別采用Apriori,Apriori_lift算法挖掘,其挖掘過程及結(jié)果如下:
表3是實驗采用的兩個數(shù)據(jù)集Tcppro,Udppro。
表4是二種算法在不同支持度(Supp)信任度(Conf)下的挖掘結(jié)果統(tǒng)計。
由表4可知,在相同的作用度與支持度的情況下,Apriori,Apriori_lift算法挖掘得到的規(guī)則逐漸遞減;在不同的作用度與支持度情況下,參數(shù)值越低挖掘出的規(guī)則越多,這主要體現(xiàn)在Apriori算法的挖掘上,而對于Apriori_lift算法當參數(shù)值達到一定閾值時,改變參數(shù)值對其挖掘結(jié)果影響不大,改善了挖掘規(guī)則遺漏的情況。
由表4可以看出,Apriori算法和Apriori_lift算法的運行時間隨挖掘規(guī)則變化的比較情況。Apriori算法隨著挖掘結(jié)果中規(guī)則數(shù)的增長,時間上有數(shù)量級的提高,而Apriori_lift隨著時間的增長,其挖掘出的規(guī)則數(shù)量增幅不大。而Apriori_lift存在額外的作用度比較的開銷,在高支持度時,由于要處理的頻繁項目及模式數(shù)目都較少,此時從挖掘結(jié)果上看Apriori_lift表現(xiàn)了比Apriori更好的性能。
評論