Fp樹算法的研究以及在入侵檢測(cè)中的應(yīng)用.pdf

1、關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的一個(gè)重要研究方向，旨在挖掘項(xiàng)集之間的內(nèi)在聯(lián)系。Fp樹算法是關(guān)聯(lián)規(guī)則的一種基于深度的典型算法，具有良好的性能和可擴(kuò)展性。Fp樹通過自頂向下構(gòu)造頻繁樹和自底向上挖掘頻繁項(xiàng)集，只需掃描事務(wù)數(shù)據(jù)庫兩次便可以有效的挖掘出頻繁項(xiàng)集，因而比基于寬度的Apriori算法快一個(gè)數(shù)量級(jí)。但是，F(xiàn)p樹采用遞歸的方法，同一條路徑需要多次遍歷，這成為制約Fp樹算法效率的瓶頸。改進(jìn)后的算法采用空間換時(shí)間的方法在每個(gè)節(jié)點(diǎn)上添加一個(gè)標(biāo)記位來標(biāo)識(shí)該節(jié)

2、點(diǎn)是否被遍歷，首先通過遍歷Fp樹找到所有葉子節(jié)點(diǎn)，然后從頭表找出樹中的葉子節(jié)點(diǎn)，從葉子節(jié)點(diǎn)開始回溯樹中的路徑，將同一條路徑存儲(chǔ)在一個(gè)線性鏈表中，從而減少同一條路徑的遍歷次數(shù)。實(shí)驗(yàn)顯示：改進(jìn)后的算法對(duì)于稀疏事務(wù)數(shù)據(jù)和稠密事務(wù)數(shù)據(jù)都能有效的提高挖掘效率，雖然增加了標(biāo)記位的空間消耗，但是同時(shí)減少了條件Fp樹的生成，因而空間性能也有所提高。 入侵檢測(cè)是數(shù)據(jù)挖掘的一個(gè)重要應(yīng)用方向，而挖掘算法效率的提高則是其中的一個(gè)研究熱點(diǎn)。本文分析了當(dāng)前

3、入侵檢測(cè)的研究進(jìn)展，采用Jpcap開源庫設(shè)計(jì)了入侵檢測(cè)的數(shù)據(jù)采集模塊。將改進(jìn)后的Fp算法應(yīng)用于入侵檢測(cè)中的關(guān)聯(lián)規(guī)則挖掘中，采用主軸因子和參考因子有效地過濾頻繁項(xiàng)集來獲得規(guī)則集，通過模式比較來獲得入侵行為。采用林肯實(shí)驗(yàn)室的1998年的網(wǎng)絡(luò)實(shí)時(shí)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，將改進(jìn)后的Fp樹算法應(yīng)用到關(guān)聯(lián)規(guī)則的模式庫挖掘中，采用不同的支持度來挖掘訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集。實(shí)驗(yàn)結(jié)果顯示，對(duì)于入侵?jǐn)?shù)據(jù)，改進(jìn)后的Fp樹算法比原Fp樹算法挖掘效率更高。檢測(cè)結(jié)果顯示，改