基于改進模糊FP-Growth的異常檢測算法

杜嘉偉，余 粟

（上海工程技術大學 機械與汽車工程學院，上海 201620）

0 引 言

隨著大數據時代的來臨，數據挖掘對于研究事務之間的關聯規律模式有著重要的意義。目前，異常檢測被廣泛應用于工業控制系統、網絡入侵檢測、醫療異常檢測等領域。異常檢測是基于當前數據模式檢測出其中的異常點，即檢測出不符合預期模式的數據。相比較于正常數據簇，異常值數據有著與數據集中正常數據并不相同的數據特征的數據模式。

近年來，國內外學者對于異常檢測的研究已取得顯著成果。其算法主要可以分類4類：基于模式預測的算法模型、基于機器學習的算法模型、基于統計的算法模型、基于貝葉斯網絡的算法模型。

文獻［6］提出一種基于模糊孤立森林算法的多維數據異常值檢測算法。該算法通過挑選一些有價值的屬性建立異常檢測模型，再通過隸屬度判斷得到評價結果，但選取的屬性只能為類別型特征。文獻［7］基于模糊理論，提出一種挖掘連續型數值數據的關聯規則，但該算法基于正常模式的數據，無法處理黑盒數據。由此可見，上述方法大多都基于正常模式下的數據挖掘，在建立模型時要求其數據全為正常模式數據，并且要包含絕大多數的正常模式行為。在異常檢測中，將沒有標簽標識的元數據稱為黑箱狀態的數據。在面對數據黑箱場景下，降低算法的誤報率和漏檢率，以及提高算法模型的泛化能力就成為了當下研究的熱點與難點。

綜上所述，本文提出一種基于改進FP-Growth算法的異常檢測算法-RFPG算法（Random Frequency Pattern Growth）。對于傳統數據挖掘方法中以閾值對數值型特征數據進行劃分遇到的尖銳邊界問題，本文提出一種基于模糊集理論的異常檢測方法；對于數據黑箱問題，算法中基于baggging思想對數據隨機采樣，生成FP-Tree集合，挖掘出模式長頻繁項集合，并通過將長頻繁項集合作為輸入生成新FP-Tree，挖掘模式強關聯規則集，使算法對于黑箱數據有著更好的尋優與泛化能力。

1 基本概念

1.1 模糊集和隸屬度

模糊集是用來描述具有模糊語義集合概念。如果存在論域，而且其中任何一個元素與（）∈［0，1］存在對應關系，則稱為上的模糊集，（）稱為對的隸屬度。

1.2 頻繁項集

采用向量和矩陣的概念，建立頻繁項集（Frequent itemsets）的 挖 掘 模 型。令｛，，，item｝為個 數 據 項 的 集 合。其 中，item（1≤≤）稱為項｛，，，t｝，是個事務組成的數據集，t（1≤≤）表示一條事務，且t是的子集。

項的集合稱為項集（），包含個項的項集稱為項集。當一個項集計算所得的支持度滿足設定的支持度閾值時，則定義該項集為頻繁項集。

支持度（）描述了多個項集在所有事務中同時出現的概率。事務數據集中的支持度用（）表示，支持度閾值用_表示。在挖掘頻繁項集的過程中，_能夠篩選并枚舉出所有重要的項集。基于以上描述可推得如下定義：

給定_，若（）_，則項目集是頻繁項目集。

存在項目集、，而且?，則（）≥（）。

1.3 FP-Growth算法

FP-Growth算法是一種頻繁項集挖掘算法，該算法中使用一種FP樹的數據結構作為存儲結構。在面對大量輸入的情況下，樹存儲結構可以應對復雜的數據存儲問題。算法通過以頻繁一項集的支持度，倒序讀取事務，并將其映射到FP樹中。考慮到選用的存儲結構，當大量讀取相同事務的情況下，已構造的重疊路徑能大大減少存儲時間，并減少了空間上的開銷。

FP-Tree的存儲結構避免了如Apriori算法那樣頻繁掃描數據庫的I／O瓶頸，減少了I／O損耗，有著更優的時間與空間復雜度。FP-Growth算法的主要任務是找出數據集中的頻繁項集，算法的主要實現步驟可依次表述為：數據采樣；構建FP-Tree；基于FP-Tree挖掘長頻繁項集；生成模式關聯規則集；模式匹配。FP-Growth算法偽代碼詳述如下。

網路流量數據集，_

輸出異常檢測分類結果

／／對流量特征進行標準化

1：D＝（）

／／對數值特征進行模糊化處理

2：_（__（））

3：while_

／／為采樣百分比

4：__（，_）

／／構建

5：__（_）

／／生成長頻繁項集

6：_（_）

7：End while

／／生成關聯規則集

8：____（）

／／計算數據與關聯規則集相似度

9：__（，__）

／／相似度匹配

10：_（_）

11：return

2 RFPG算法

在傳統FP-growth基礎上，基于模糊理論的RFPG算法根據頻繁項集的隸屬度，以降序方式生成條件模式基。每個條件模式基在經過剪枝后，獲得候選1項集，滿足支持度要求的候選1項集即為頻繁項集。于是提出如下定義：

若條件模式基中存在個滿足_的元素，則該條件模式集基中存在最長候選1項集。

2.1 數據模糊化處理

基于模糊數學理論的綜合評價方法，針對連續型數據特征進行數據模糊化處理。具體來說，模糊綜合評判就是將數據模糊關系與模糊數學相關聯，將難以確定邊界的特征因素以隸屬度的形式進行描述。

在挖掘包含大量連續數值型特征數據的關聯規則時，由于傳統FP-Growth算法只能處理二值化特征，無法處理連續數值型特征，因此引入數據模糊化處理改進FP-Growth算法，使算法的泛化能力更好，并能避免傳統基于閾值劃分時數據分類帶來的尖銳邊界問題。本文使用Fuzzy-C-Means算法對連續數值型數據進行模糊聚類，使用隸屬度描述聚類程度。目標函數定義為：

通過公式（2）計算得到聚類中心點和目標函數值，并由公式（3）重新計算權重矩陣，當目標函數值小于誤差閾值結束迭代。這里用到的公式為：

將元數據集轉化為模糊數據集，見表1。表1中，d表示FCM聚類后結果。

表1 模糊數據集DTab.1 Fuzzy dataset D

模糊集的隸屬度使用模糊集各屬性的支持度計數所得，對此可表示為：

計算得出各個項集的支持度后，對候選項集進行剪枝操作，得到頻繁項集。其中，剪枝包含2個步驟，可做闡釋分述如下：

（1）刪除不滿足_閾值的候選項，得到頻繁項集。

（2）刪除包含非頻繁（1）項集的候選項集，得到頻繁項集。

2.2 異常檢測

在進行異常檢測之前，通常先挖掘出數據正常模式下的關聯規則，但處于數據黑盒狀態下的數據由于異常數據擾動，會使挖掘出的關聯規則支持度與置信度會降低。因此，使用RFPG算法挖掘生成FP-Tree時，可以設置稍低的最小支持度與最小置信度閾值，以獲得盡可能多的關聯規則集；將各個FP-Tree集合挖掘出的關聯規則集作為第二層輸入，生成新的FP-Tree，由此得到接近正常模式的關聯規則集。

在數據中，由于異常數據簇與正常數據簇分布不同，RFPG算法使用背離度這一概念來描述異常狀態。通過規則集與單時間段數據的相似度，量化當前數據集與數據正常模式的背離度，以此建立異常檢測系統的檢測機制。算法中將模糊化處理后的單時間段數據與挖掘出的正常模式關聯規則的交集作為單條數據的長頻繁項集。對于關聯規則相似度的計算，設存在關聯規則與某一時間段數據，這里的支持度為，置信度為，則其關聯規則的相似度可由式（5）計算求出：

對于關聯規則集相似度的計算，設存在關聯規則集與某一時間段數據。其中，規則集包含若干關聯規則R，為關聯規則集規則數量，為某一時間段數據元素與關聯規則集元素交集個數。關聯規則集的相似度的計算可寫為式（6）：

3 實驗結果及分析

實驗使用NSL-KDD網絡流量數據，以評價RFPG算法異常檢測的性能。實驗環境為：64位的Win10操作系統，IntelCoreTM i7-9700kf CPU，主頻3.6 GHz、內存32 GB；仿真編程語言為Python3.8。

3.1 數據集介紹

NSL-KDD數據集是改進KDD-CUP99的網絡流量數據集，優化了數據集冗余和重復數據多的不足。數據為9個星期的網絡連接數據，采集于模擬的某國空軍局域網。

數據集有41個特征，包含網絡連接特征和網絡流量特征。標簽列分為了2類：正常模式的標識類型（normal）和異常模式的標識類型（abnormal）。數據集共125 972條數據，樣本分布見表2。

表2 NSL-KDD數據集樣本分布Tab.2 Samples distribution of NSL-KDD dataset

3.2 評價指標

在異常檢測中，誤報率（）與漏檢率（）通常是衡量異常檢測算法的指標，而誤報率與檢測率是基于混淆矩陣的概念實現。混淆矩陣見表3。對此擬做探討闡述如下。

表3 混淆矩陣Tab.3 Confusion matrix

（1）誤報率。是指正常而被誤判為入侵樣本數占正常樣本數的百分比，數學定義公式如下：

（2）檢測率。是指異常而被誤判為正常的樣本數占異常樣本數的百分比，數學定義公式如下：

3.3 實驗過程

為了模擬真實網絡攻擊狀況、并檢驗RFPG算法異常檢測效果，實驗分別準備了3組不同數據量的數據，分別為：5 000條數據、10 000條數據、15 000條數據。每組中使用3類數據，分別是：包含5%異常樣本數據的數據集；包含10%異常樣本數據的數據集；包含15%異常樣本數據的數據集。

實驗中，RFPG算法使用前文求得的模糊聚類中心模糊化網絡流量數據，按照先驗知識將流量特征等數值特征_分為低、中、高三個模糊分區，并將連接特征等類別特征_按照其類型數量進行編碼，研究獲得（*_*_）個特征。其中，為模糊分區數，為類別特征包含的類別數。在挖掘模式強關聯規則時，設最小支持度_08，最小置信度_08。

數據量為5 000、10 000、15 000時RFPG算法的評分結果曲線如圖1～3所示。由圖1～3可見，RFPG算法整體異常檢測效果良好，并且隨著數據量的提高，包含不同比例的異常樣本數據的分類評分越穩定。由此證明：數據量越大，數據中包含的正常行為模式越完整，在挖掘關聯規則時，實際為正常樣本被預測為異常樣本的概率降低，分類效果更好。由圖3還可見到，RFPG算法實驗結果中，包含不同比例異常數據的分類結果評分相近，證明該算法抗噪聲干擾能力強，對于黑盒數據的模型泛化能力也很強。

圖1 5 000數據量RFPG算法AUC評分Fig.1 AUC score of RFPG algorithm when the amount of data is 5 000

圖3 15 000數據量RFPG算法AUC評分Fig.3 AUC score of RFPG algorithm when the amount of data is 15 000

3.4 對比試驗

實驗使用基于K-means異常檢測算法、基于KL距離的異常檢測算法、Fuzzy-Apriori算法以及RFPG算法進行結果對比。

圖2 10 000數據量RFPG算法AUC評分Fig.2 AUC score of RFPG algorithm when the amount of data is 10 000

對比實驗選取同一包含15 000數據量以及10%異常樣本的數據集，對RFPG算法的可用性進行驗證，見表4。結果表明，在實驗數據相同的情況下，RFPG異常檢測算法相比其它算法，在誤報率與檢測率上都有著更好的檢測表現。基于K-means的異常檢測算法，對于數據特征變化偏移較小的異常數據容易產生漏檢的情況；基于KL距離的異常檢測算法，結合了EWMA預測模型刻畫出了數據整體變化趨勢，敏感性較高，有著較好的檢測率，同時誤報率也有所提升；Fuzzy-Apriori算法基于模糊理論，根據數據分布進行隸屬度函數的建立，對于有標簽的數據有著較好的表現，但是對于黑箱數據檢測率與誤報率表現欠佳，并且時間復雜度較高。RFPG算法基于bagging隨機采樣數據生成FP-Tree集合，得到長頻繁項集合，并將其作為第二層的輸入，生成近似正常模式的關聯規則集，使算法面對黑盒數據依然有較為良好的表現，更符合異常檢測的現實需求。同時，RFPG算法基于FP-Tree結構，使算法相較于Fuzzy-Apriori算法有著較優時間復雜度。實驗結果顯示，較高的檢測率與較低的誤報率也驗證了RFPG異常檢測算法的可用性。

表4 多算法對比試驗Tab.4 Algorithms comparison experiment %

4 結束語

本文提出的基于改進模糊FP-Growth異常檢測算法RFPG，經實驗表明，在大數據體量下，其異常檢測能力更優，并且由于RFPG基于樹的存儲結構更適用于大數據集體量的場景，減少了提取關聯規則集的運行時間和內存消耗。但基于先驗知識，在對數值型特征進行模糊化處理時，會增加數據集的維度。因此，需要對自適應隸屬度函數的建立，以及在算法過程中動態削減數據集維度與優化搜索空間進入深入探討，以達到進一步優化整體異常檢測質量與效率的研究目的。