數(shù)據(jù)點位置并行FP-Growth挖掘算法仿真

喬陽陽,王麗娟

(1. 鄭州工商學院信息工程學院,河南 鄭州 451400;2. 華北水利水電大學電力學院,河南 鄭州 450046)

1 引言

數(shù)據(jù)挖掘(Data Mining,DM)又稱數(shù)據(jù)庫中的知識發(fā)現(xiàn),是目前人工智能和數(shù)據(jù)庫領域研究的熱點問題,是指從數(shù)據(jù)庫的大量數(shù)據(jù)中揭示出隱含的、先前未知的并有潛在價值的信息的非平凡過程。網(wǎng)絡海量數(shù)據(jù)[1]中存在大量有價值信息,一旦發(fā)生入侵會造成信息丟失、網(wǎng)絡環(huán)境不穩(wěn)定等問題,當前已經(jīng)成為網(wǎng)絡安全的極大隱患。木馬、惡意程序、僵尸網(wǎng)絡、拒絕服務攻擊以及個人信息泄露等問題難以預防[2],因此亟需挖掘入侵數(shù)據(jù)點位置,及時發(fā)現(xiàn)入侵數(shù)據(jù)并加以防御,為提高網(wǎng)絡安全性奠定基礎。

針對此問題,孫子文等人[3]構建了基于深度自編碼網(wǎng)絡的集成學習入侵檢測模型,完成入侵數(shù)據(jù)點位置挖掘。將若干正則降噪自編碼網(wǎng)絡棧式疊加,生成深度自編碼網(wǎng)絡,采用非線性方式將原始數(shù)據(jù)降維處理,通過多個深度信念網(wǎng)絡投票實現(xiàn)入侵數(shù)據(jù)點位置挖掘。金志剛等人[4]提出了一種基于特征選取與樹狀Parzen估計的入侵檢測方法。采用相關性分析降維數(shù)據(jù)特征,選取特征后構建新特征子集,引入樹狀Parzen估計算法優(yōu)化隨機森林算法模型,通過優(yōu)化后模型實現(xiàn)入侵數(shù)據(jù)點位置挖掘。陳虹等人[5]構建了基于改進ADASYN-SDA的入侵檢測模型,以挖掘入侵數(shù)據(jù)點位置。通過自適應過采樣算法對原始數(shù)據(jù)過采樣處理,融合Adam算法和隨機失活正則化算法優(yōu)化堆疊式降噪自編碼器深度學習模型,在softmax分類器中實現(xiàn)去入侵數(shù)據(jù)點位置挖掘。

現(xiàn)階段提出的數(shù)據(jù)挖掘方法均忽略了在入侵異常數(shù)據(jù)點位置挖掘前濾除正常數(shù)據(jù),導致入侵數(shù)據(jù)挖掘的誤報率較高,入侵數(shù)據(jù)定位準確率還有待進一步優(yōu)化?；诖?本研究提出基于并行FP-Growth算法的數(shù)據(jù)點位置智能挖掘方法。

2 數(shù)據(jù)降維

網(wǎng)絡節(jié)點采集到的數(shù)據(jù)屬性較多,在眾多屬性中存在大量無意義和冗余屬性,高維數(shù)帶來數(shù)據(jù)維數(shù)災難問題,使入侵數(shù)據(jù)點檢測和定位復雜性增加,不但會造成系統(tǒng)資源的浪費還會降低數(shù)據(jù)點位置挖掘的準確度。因此所提方法在入侵數(shù)據(jù)點位置挖掘前采用融合信息熵和主成分分析法的E-PCA算法降維大數(shù)據(jù)[6,7]。

2.1 信息熵

(1)

信息熵是表現(xiàn)系統(tǒng)有序化程度的指標,將其用于特征選擇中時,若某個特征的信息熵越大,則說明該特征所蘊含信息量越高,即能夠提供更多有意義的信息,降維數(shù)據(jù)時應盡量保留該類特征,反之將特征剔除。保留或剔除特征的依據(jù)為信息熵閾值ψ,ψ取值需要結合實際情況和特征在原始數(shù)據(jù)中比重共同決定。

2.2 E-PCA算法

引入信息熵的E-PCA算法與主成分分析法原理相同,差異僅為在執(zhí)行主成分分析法前采用信息熵對數(shù)據(jù)特征預篩選,減少特征數(shù)量,彌補主成分分析法效率低、內存消耗大等缺點。用Wm×n表示原始數(shù)據(jù)矩陣,其中n表示樣本總數(shù),m表示特征總數(shù)。

①計算全部數(shù)據(jù)特征b1,b2,…,bn對應的信息熵H(bi),若H(bi)>ψ,則將該屬性加入樣本集合B中;

②將樣本集合對應矩陣B中心化處理,得到中心化矩陣Xm×n如下所示:

Xm×n=B-repmat[mean(B,2),1,m]

(2)

③計算不同特征維度之間協(xié)方差,構建協(xié)方差矩陣C如下所示[8]:

(3)

④計算協(xié)方差矩陣C中的特征值λi和特征向量zi;

⑤選取k個最大特征值對應特征向量構建矩陣Um×k,根據(jù)貢獻率η確定k的取值,η計算公式如下所示

(4)

⑥得到降維結果Yk×n=Um×kXm×n,實現(xiàn)數(shù)據(jù)降維。

3 入侵數(shù)據(jù)點位置智能挖掘

基于數(shù)據(jù)的降維操作,將數(shù)據(jù)挖掘引入入侵檢測系統(tǒng)IDS中能夠在入侵數(shù)據(jù)點位置挖掘前提取海量網(wǎng)絡數(shù)據(jù)中的異常數(shù)據(jù)[9],降低后續(xù)數(shù)據(jù)處理復雜度,為數(shù)據(jù)點位置智能挖掘奠定基礎。

3.1 入侵數(shù)據(jù)點智能識別

3.1.1 IDS K-means算法

對不適用于入侵智能檢測的K-means算法加以改進,構建用于入侵檢測系統(tǒng)的IDS K-means算法[10]。針對標準K-means算法獲取聚類個數(shù)K困難的問題,采用預定距離改進K-means算法。假設存在數(shù)據(jù)集X={x1,x2,…,xn},預先設置聚類半徑r,首先以x1為中心設置第一個聚類C1的聚類中心c1,然后計算x2與c1的距離dx2,c1,若dx2,c1

結合實際情況設定智能閾值θ,若某類中數(shù)據(jù)總數(shù)m與全部數(shù)據(jù)總數(shù)n的比例m/n≥θ,則說明該類為正常數(shù)據(jù)類,將其加入正常聚類表,建立正常行為模式庫;若m/n<θ,則說明該類為入侵數(shù)據(jù)類,將其加入異常聚類表,建立異常行為模式庫。在網(wǎng)絡數(shù)據(jù)中,正常數(shù)據(jù)總數(shù)遠遠多于入侵數(shù)量總數(shù),因此濾除正常數(shù)據(jù),僅對可能為入侵數(shù)據(jù)的聚類進一步檢測,能夠有效提升檢測效率。

3.1.2 并行FP-Growth算法

針對Apriori算法在計算過程中會產生大量候選集且每次計算均需要重新掃描數(shù)據(jù)集造成的算法復雜度較高、效率較低的問題[11],FP-growth算法應運而生,該算法是用于頻繁項集和數(shù)據(jù)強關聯(lián)規(guī)則挖掘的算法[12],通過該算法獲取頻繁項集的過程主要分為以下兩個部分:

1)建立事件FP-tree

①第一次遍歷

用G=(G1,G2,…,Gn)表示事務數(shù)據(jù)集,在第一次遍歷G時,計算頻繁項大于1的項目集支持度數(shù),設定最小支持度數(shù)和置信度數(shù),分別記作supmin和confmin,刪除小于supmin和confmin的頻繁項,其余頻繁項數(shù)據(jù)集由大到小排列。

②第二次遍歷

建立FP-tree根結點null,對G執(zhí)行第二次遍歷,依據(jù)次序處理全部項集的項,為全部項集創(chuàng)立各自分支,完成FP-tree構建。

2)在事件FP-tree樹中挖掘頻繁項集

在各個項集中獲取對應條件模式基,遞歸調用樹形結構,剔除全部小于最小支持度的項,若已經(jīng)生成單一路徑樹形結構,則列舉全部組合;反之繼續(xù)遞歸調用樹形結構,直到生成單一路徑樹形結構。

為了減少網(wǎng)絡通信量,提升傳輸效率,所提方法將MapReduce引入FP-Growth算法構建并行FP-Growth算法[13],并行FP-Growth算法主要流程如下所示:

①計算事務數(shù)據(jù)集中頻繁項大于1的支持度數(shù),采用一個MapReduce job統(tǒng)計頻繁項大于1的頻繁集,存儲結果于分布式緩存中;

③采用一個MapReduce job統(tǒng)計存儲于Hadoop中的項目集支持度數(shù),將滿足最小支持度的頻繁項目集添加至全局頻繁目集中。

④融合步驟②和步驟③結果即可生成完整的全局頻繁項目集。

3.1.3 KMFP算法

將單一的K-Means算法用于入侵數(shù)據(jù)檢測中易出現(xiàn)陷入局部收斂的情況,因此將改進的K-Means算法與并行FP-Growth算法相結合,建立KMFP算法,用于提升入侵檢測效果。

KMFP算法首先利用改進的K-Means算法劃分網(wǎng)絡大數(shù)據(jù)為正常數(shù)據(jù)和異常數(shù)據(jù)兩類,然后通過FP-Growth算法挖掘異常數(shù)據(jù)中的關聯(lián)規(guī)則,從而將生成的規(guī)則用于入侵檢測之中,提升算法的檢測準確率,降低誤報率。改進的K-Means算法預先劃分數(shù)據(jù)為正常數(shù)據(jù)聚類和數(shù)據(jù)聚類兩種,在執(zhí)行入侵檢測前濾除正常數(shù)據(jù)聚類,使待檢測數(shù)據(jù)量大大降低,在提升算法效率中具有明顯效果。

3.2 入侵數(shù)據(jù)點位置智能挖掘

通過KMFP算法實現(xiàn)入侵數(shù)據(jù)檢測后需要對入侵數(shù)據(jù)點位置進一步挖掘。引入鄰居節(jié)點數(shù)據(jù)投票方式判別包含入侵數(shù)據(jù)的節(jié)點,依據(jù)節(jié)點和鄰居節(jié)點之間的位置關系完成入侵數(shù)據(jù)點位置智能挖掘。

(5)

依據(jù)式(5)計算節(jié)點i和節(jié)點j的屬性相關系數(shù),設定閾值β,若sim(i,j)>β,則將節(jié)點i和節(jié)點j視為空間相關。

Cor(i,j,k,t)=

(6)

若Cor(i,j,k,t)>β,則視為鄰居節(jié)點k對入侵數(shù)據(jù)有所感知,將投票記作1,反之記作-1,完成全部投票后,大部分投票結果為1的節(jié)點即為入侵數(shù)據(jù)節(jié)點,由此實現(xiàn)入侵數(shù)據(jù)點位置智能挖掘。

4 實驗與結果

為了驗證基于并行FP-Growth算法的數(shù)據(jù)點位置智能挖掘仿真整體有效性,將所提方法與文獻[3]提出的深度自編碼網(wǎng)絡方法和文獻[4]提出的樹狀Parzen估計方法做實驗對比。

采用KDD CUP99數(shù)據(jù)集作為實驗數(shù)據(jù)集,數(shù)據(jù)集中包括正常網(wǎng)絡連接數(shù)據(jù)、拒絕服務攻擊數(shù)據(jù)、遠程權限獲取數(shù)據(jù)、PROBE攻擊數(shù)據(jù)和各種權限提升數(shù)據(jù),其中有20%左右數(shù)據(jù)為正常數(shù)據(jù),80%左右為拒絕服務攻擊數(shù)據(jù),而遠程權限獲取數(shù)據(jù)、PROBE攻擊數(shù)據(jù)和各種權限提升數(shù)據(jù)出現(xiàn)概率極小。為了模擬真實數(shù)據(jù)環(huán)境,異常數(shù)據(jù)數(shù)量遠遠小于正常數(shù)據(jù)數(shù)量,因此在實驗前需要調整數(shù)據(jù)比例,控制正常數(shù)據(jù)數(shù)量和異常數(shù)據(jù)數(shù)量在合適的范圍內。KDDCUP99原始數(shù)據(jù)集中包含數(shù)據(jù)超過500萬條,數(shù)據(jù)過多不利于實驗分析,因此選取其中具有代表性的4820條數(shù)據(jù)用于后續(xù)實驗,每條數(shù)據(jù)具有45維屬性,其中正常數(shù)據(jù)有4628條,異常數(shù)據(jù)192條,異常數(shù)據(jù)包括4大類中共計36種攻擊形式。

以DDCUP99原始數(shù)據(jù)集中的4820條數(shù)據(jù)為樣本,利用不同方法對數(shù)據(jù)集中國異常數(shù)據(jù)點位置完成挖掘,統(tǒng)計不同方法的平均誤報率,測試結果如圖1所示。

圖1 誤報率檢驗結果

由圖1可以看出,所提方法的平均誤報率最低,深度自編碼網(wǎng)絡方法和樹狀Parzen估計方法在挖掘數(shù)據(jù)點位置時,平均誤報率明顯高于研究方法由此可知,所提方法的入侵數(shù)據(jù)檢測性能好。

以相同數(shù)據(jù)集為樣本,不同數(shù)據(jù)點位置挖掘方法的平均準確率測試結果如圖2所示:

圖2 入侵數(shù)據(jù)點位置挖掘準確率

由圖2可以看出,所提方法在入侵數(shù)據(jù)點位置挖掘中的平均定位準確率可達到98%,說明所提方法的入侵數(shù)據(jù)點位置挖掘能力強。因為所提方法將改進的K-Means算法和并行FP-Growth算法相結合,在入侵數(shù)據(jù)檢測前濾除正常數(shù)據(jù),降低了數(shù)據(jù)處理的復雜性。為進一步驗證所提方法的有效性,將所提方法與深度自編碼網(wǎng)絡方法和特征選取與樹狀Parzen估計方法進行實驗對比。驗證在不同方法下數(shù)據(jù)的聚類效果,實驗結果如圖3所示。

圖3 不同方法下的數(shù)據(jù)聚類效果

從圖3的實驗結果可以看出,所提方法能夠將正常數(shù)據(jù)點集合與異常數(shù)據(jù)點集合精準分離,完成相同屬性數(shù)據(jù)的聚類。深度自編碼網(wǎng)絡方法與特征選取與樹狀Parzen估計方法應用下,數(shù)據(jù)聚類的效果不夠理想,在分類出的異常數(shù)據(jù)中,仍然摻雜著少量正常數(shù)據(jù)。此實驗結果證明了研究方法具有更好的數(shù)據(jù)聚類效果,從而更好地完成了數(shù)據(jù)入侵檢測,得到數(shù)據(jù)更精確的位置信息。

5 結束語

入侵數(shù)據(jù)的位置檢測可判定網(wǎng)絡是否受到非法攻擊等威脅,對網(wǎng)絡中入侵數(shù)據(jù)實時檢測與定位能夠為網(wǎng)絡抵抗內外部攻擊提供數(shù)據(jù)基礎,提高網(wǎng)絡運行的安全性。本研究提出基于并行FP-Growth算法的數(shù)據(jù)點位置智能挖掘方法,通過E-PCA算法降維網(wǎng)絡大數(shù)據(jù),采用KMFP算法檢測入侵數(shù)據(jù),利用鄰居節(jié)點數(shù)據(jù)投票的方式完成入侵數(shù)據(jù)點位置智能挖掘。該方法能夠有效地降低誤報率,提高入侵數(shù)據(jù)定位中的準確率,為網(wǎng)絡安全運行提供思路。