基于最大頻繁項的數據流異常檢測

史曉晨

(太原科技大學計算機科學與技術學院，山西 太原 030000)

隨著大數據時代的到來，大數據挖掘技術應運而生，數據流的高效處理成為數據庫領域的研究熱點。數據流是一種大規模、連續到達、高速、不可預測的數據序列，廣泛應用于通信、金融、互聯網信息安全等現實生活和工業數據領域[1]。與傳統數據不同，數據流的數據實時到達，每條數據只能訪問一次，數據到達順序獨立，不受系統控制，這些特點給數據處理帶來了新的挑戰。作為數據挖掘研究領域的一個重要分支，異常檢測技術受到了學術界的廣泛關注[2]。

異常是指數據集中存在獨特的數據，而數據流的異常檢測就是找出這些明顯遠離其他數據點的數據。欺詐檢查、醫療處理、圖像處理等多方面使用異常檢測的算法。傳統的異常檢測算法主要分為基于統計學、基于聚類、基于分類以及基于近鄰性[3]。現在隨著對數據流分析處理研究的深入，數據流異常檢測算法也在不斷更新和完善。一般來說，數據流的異常檢測可以分為兩種類型，即檢測數據對象的行為變化和發展趨勢的變化[4]。數據流異常檢測已應用于各個領域，如網絡入侵檢測、異常天氣檢測、金融分析檢測等。為了研究異常檢測技術，一些研究利用領域知識來提高異常檢測模型的準確性，一些學者將模糊理論與關聯挖掘技術相結合，提出了網絡用戶挖掘模型。這些技術極大地改進了異常數據的檢查技術[5-6]。然而，由于其自身具有不確定性和數據量大等特點，數據流面臨著許多挑戰。例如，數據流不能存儲在有限的內存中，隨機訪問數據流中的數據對象的機會很小[7]。最大頻繁挖掘是對數據進行分類和壓縮，可以更好地節省數據的存儲空間[8]。因此，研究基于MFI的數據異常檢測具有重要意義。

綜上所述，本研究采用MFI算法對數據流進行異常檢測。本文首先構建了基于數據挖掘的異常數據入侵檢測模型，設計了一種基于MFI的多維頻率模式挖掘算法，并對MFI算法的更新方法進行了說明，最后對異常數據的檢測率、異常數據的處理時間、異常數據的節點維護結果進行分析。本研究旨在為利用挖掘數據技術構建網絡異常入侵數據檢測模型提供良好的理論依據。

1 基于數據挖掘的異常入侵檢測模型的建立

數據流是一個動態的數據序列，具有持久性和快速形成的特點，常用來表征動態網絡的訪問量。本研究探索的數據集是：收集一段時間內的網絡訪問量，將其定義為一個數據流，分析其特征，找出異常數據和正常數據的特征，從而構建相應的網絡訪問數據模型庫。算法基于數據集進行分析，實現對未來網絡訪問數據的異常檢測和分析。

傳統的異常檢測方法可以快速識別未知攻擊訪問，但誤報率較高。本研究設計的異常檢測模型將誤用檢測和異常檢測相結合，強化優勢，改善劣勢。圖1顯示了基本架構。

圖1 異常數據入侵檢測模型

圖1中的模型由兩個主要模塊組成，即前端檢測模塊和后端學習模塊。檢測模塊主要在異常檢測模型的基礎上結合誤用檢測；學習模塊用于生成知識模式的特征，包括正常規則和異常規則的學習模塊。異常檢測模塊將網絡范圍的訪問數據與正常模式和已知異常模式庫進行匹配。前者通過檢查是否完美匹配來判斷是否為正常數據，后者通過與已知異常數據庫的匹配來判斷是否為異常數據，否則將轉移到普通正常訓練集和異常訓練集。后端學習模塊包括正常規則學習模塊和異常規則學習模塊，旨在增量學習新增的正常訓練集和異常訓練集，更新正常和異常模式庫。

2 基于MFI的數據流最大頻繁模式挖掘算法設計

2.1 相關定義

最大頻繁模式是本研究中要解決的一個場景。該場景是指由許多屬性組成的網絡訪問。本研究將公共數據集KDD99中的一個數據段按照連接類型、服務類型、連接標識、連接時長和字節數列出，如表1所示，選擇屬性作為問題的焦點來挖掘最大頻繁模式。定義1：頻繁模式。假設數據集為M，維度屬性集為B，則可以得到B={B1,B2,…,Bm}。假設離散化屬性B1的值為A，可以得到，M中基于B的n維項集用L表示，可以得到，其中amn∈Ai(i=1,2,…,m;pn=1,2,…,m)。因此，項集在數據集M中所占的百分比可以稱為它的支持度；通常如果項集的支持度不小于用戶定義的最小支持度，則可以稱為頻繁模式。

表1 KDD99的數據屬性

定義2：超集(頻繁模式的包含關系)。假設有給定的數據集M和給定的維度屬性集B={B1,B2,…,Bm}，對應的取值范圍可以表示為A={ai1,ai2,…,anpn}。對于任意兩個基于B(L={ai1,ai2,…,amn}和Q={Qi1,Qi2,…,Qmn})的n維項集，如果ai1=Qi1(i=1,2,…,m)中所有維屬性都為真，則可以稱為L?Q。如果L?Q,并且其中一個維度屬性j符合Qmn≠*而不是anpn≠*，則L真正包含在Q中，可以表示為L?Q。

定義3：最大頻繁模式。頻繁模式L的所有超集都是非頻繁項集,那么稱L為最大頻繁模式,記為MFI(Maximal Frequent Itemset)。

定 義4：遍 歷 第 一 個 根。 在 樹PC={R,P1,…,Pi,…Pv}中，C表示樹的根節點，PC表示以節點i(1≤i≤c)為根的子樹。遍歷時，應遵循“根優先遍歷”的原則。得到節點順序后，對節點進行編號并遞歸生成。

本研究利用最大頻繁模式(MFI)對數據流進行高效挖掘，設計了MFI的模式樹。首先根據表1設計內存中的Max FP-Tree。Max FP-Tree樹具有三個特點：父節點必須包含子節點；子節點的支持數必須小于父節點的支持數；存儲過程中只存儲最大頻繁項集。

2.2 最大頻繁模式數的更新方法

隨著數據流的變化，每條新生成的訓練記錄都需要相應地修改。現有的Max P-tree及其對應的支持度被計入Max FP-Tree的更新。

算法1的流程如下：使用Max FP-Tree進行更新，更新后的算法記為Update-MaxFP-tree。輸入當前處理的多維數據流記錄i，當前節點“node”被更新，最后輸出更新后的Max FP-Tree。

為了減少使用數據流解決網絡入侵異常檢測時的窗口模型問題，基于衰減窗口機制設計了一種網絡訪問數據流最大頻繁模式的挖掘算法，稱為Max FPTree NDS算法。算法過程如下：輸入網絡數據流M、衰減率、最小支持minSupport、MaxFP-Tree，然后輸出入侵異常數據ID-Pattern的檢測模式。

上述兩種算法的運行過程必須在數據流每次到達一次訪問時記錄下來?？偣灿兴膫€步驟：記錄評估、窗口估計、最大FP-Tree維護和模式輸出。

3 結果與討論

本研究使用的實驗數據來源于KDD99數據集。該數據集有41個基本屬性。根據本研究的實驗環境條件，僅選取21個關鍵屬性進行實驗。訓練集中有520,000條記錄，測試集中有10,000條記錄。在測試集中，正常數據占72.9%，異常入侵數據占16.76%，未知類型異常入侵數據占10.34%。

3.1 異常數據檢出率結果分析

本研究算法的目標是優化數據流中異常檢測的準確率。比較模型基于異常檢測算法和本研究提出的Max FP-Tree NDS算法，將誤用檢測和異常檢測相結合。設計的評價指標包括未知異常預警率，即現有數據集中無法驗證的異常數據占所有數據集的比例；異常誤報率，即系統誤判為異常數據的記錄在總數據集中的比例.

本研究分析了不同數據集下的異常數據檢測結果，兩組算法模型的未知異常預警率和異常誤報率隨著數據容量的增加而變化，如圖2所示。本研究的Max FP-Tree NDS算法融合了誤用檢測的思想，因此檢測更加準確，減少了非完全匹配數據集的比例。結果表明，無論數據集大小，優化后的算法在未知異常預警率和異常誤報率方面均具有優勢。Max FP-Tree算法的未知異常預警率和異常誤報率均低于基本異常檢測算法，并且隨著數據集的增加，優越性越來越高，說明改進算法后異常檢測準確率提升。

圖2 不同數據集下異常數據檢測結果分析

3.2 異常數據處理時間結果分析

圖3給出了數據集增加時檢測算法總處理時間的變化。由此可以看出，本實驗的衰減率為0.994。在不同程度的支持下，隨著數據流容量的增加，Max FPTree NDS算法的處理時間增加，但是這兩者的增加并沒有呈現出線性變化。當數據量超過90,000條記錄時，處理時間增長緩慢，說明處理用戶在正常行為模式下逐漸完善。

圖3 數據集增加時檢測算法的總處理時間

3.3 Max FP-Tree NDS算法節點維護結果分析

如圖4所示是Max FP-Tree算法維護的節點數隨數據集節點增加的變化情況。本研究實驗中的衰減率為0.994。從圖4中可以看出，在學習階段初期，系統模型庫存在一定缺陷，Max FP-Tree NDS算法會進入并移動大量節點。經過一段時間后，被維護的節點會達到最高峰。后來隨著數據集節點的增加，模式庫和用戶行為逐漸趨于穩定，Max FP-Tree NDS維護的節點數逐漸減少，穩定在80,000左右的合理范圍內。

圖4 Max FP-Tree算法維護的節點數隨數據集節點增加的變化

4 總結

針對網絡數據流中無法構建異常數據檢測模型的問題，本研究提出了一種基于最大頻繁項(MFI)的數據流異常檢測算法，即Max FP-Tree NDS算法，并對其進行了改進，使Max FP-Tree NDS算法實現多維條件下異常數據的檢測。根據實驗結果發現，在異常入侵數據的檢測中，Max FP-Tree NDS算法能夠很好地提高異常數據的預警率和誤報率。此外，Max FPTree NDS算法在總處理時間上表現出明顯的優勢。本研究為多維頻繁模式下的異常入侵數據檢測提供了良好的理論基礎，但也存在一定的局限性。本研究僅選擇了兩種支持模式，后續研究可以在更豐富的支持基礎上進行。