入侵檢測中常用數據挖掘算法的分析與研究

楊銘

摘 要：數據挖掘算法是一個定義完備的過程，它以數據作為輸入并產生模型或模式形式的輸出。本文介紹了2種入侵檢測中常用的數據挖掘算法，并說明了在入侵檢測中應用數據挖掘技術的優點。

關鍵詞：數據挖掘；關聯分析；序列分析；算法

1 引言

數據挖掘（Data Mining，DM），又稱為數據捕撈、知識挖掘、知識發現、模式分析等，是從大量的、不完全、包含噪聲數據的、模糊的、隨機的數據中發現知識（模式）的非平凡過程。該定義包含以下幾層含義：數據是指一個有關事實的集合，記錄了事務有關方面的原始信息，數據源必須是真實的、大量的、包含噪聲的；模式給出了數據的特性或數據之間的關系，是對數據包含的信息的更抽象描述，發現的知識是可理解的、新穎的、潛在有用的、可解釋的：不是要發現所有的知識，通常是針對特定的需求來發現滿足需要的知識。數據挖掘系統具有以下主要成分：數據庫、數據倉庫或其它信息庫、數據庫或數據倉庫服務器、知識庫、數據挖掘引擎、模式評估模塊和圖形用戶界面。

2 關聯分析算法

關聯規則挖掘技術用于發現數據庫中屬性之間的有趣關聯，和傳統的產生式規則不同，關聯規則可以有一個或者多個關聯屬性。同時一個規則的輸出屬性可以是另外一個的輸入屬性。

定義1：關聯規則挖掘的數據集記為D（一般為事務數據庫），D={t1，t2，…tk…，tm，}，tk={i1，i2，…im，…iP}，tk（k=1，2，…n）稱為事務。im={1，2，…p}，稱為項目。

定義2：設I={il，i2，…im}是D中全體項目的集合，I中的任何子集X稱為D中的項目集，x=k稱為集合X為K項目集。設tk和X分別為D中的事務和項目集，如果x tk，稱事務tk包含項目集X。每一個事務都由一個唯一的標識符，稱為TID。

定義3：數據集D中包含項目集X的事務數稱為項目集X的支持數，記為σx。項目集X的支持度記為support（x）：

其中|D|是數據集D的事務數，若support（x）不小于用戶支持的最小度（minspport），則稱X為頻繁項目集，簡稱頻集，否則稱X為非頻繁項目集，簡稱非頻集。

定義4：若X、Y為項目集，且X∩Y≠Φ，蘊涵式X Y稱為關聯規則，X、Y分別稱為關聯規則X Y的前提和結論。項目集X∪Y的支持度稱為關聯規則X Y的支持度，記作：support（X Y），support（X Y）=support（X∪Y），關聯規則X Y的置信度，記作：confidence（X Y）：

3 序列分析算法

序列模式與關聯模式相仿，不同的是它處理不同記錄之間屬性集的關聯關系，把數據之間的關聯性與時間聯系起來。為了發現序列模式，不僅需要知道事件是否發生，而且需要確定事件發生的時間。序列模式分析的側重點在于分析數據間的前后序列關系。序列分析描述的問題是：在給定交易序列數據庫中，每個序列按照交易時間排列成一組交易集，挖掘序列函數作用在這個交易序列數據庫上，返回出現的高頻序列。將序列模式發現的問題分解成以下幾個階段：

⑴排序階段。利用客戶標識字作為主關鍵字及事務發生的時間做為次關鍵字將數據庫進行排序，該步驟也將原始的事務數據庫轉換成客戶序列的數據庫。

⑵大項目集階段。在該階段發現所有的大項目集L，同時發現了所有的大1序列的集合，并把大數據項集映射為一組相鄰的整數，每個大數據項對應一個整數。

⑶轉換階段。需要重復確定哪一個給定的大序列集被包含于顧客序列中，要快速完成這種測試，需要將每一個顧客序列轉換成一個替換的代表。在一個已轉換的客戶序列中，每一個事務被包含于該事務中的所有大項目集來替換。如果一個事務不包含任何大項目集，在已轉換的序列中就不應保留該事務。如果一個客戶序列不包含任何大項目集，則從已轉換的數據庫中去掉該序列，但是，總客戶數的計數仍要對它計數。這個已轉換的數據庫稱為Dt，根據磁盤空間的大小，可以生成這個己轉換的數據庫，或者當在一個遍歷期間讀每一個客戶序列時通過快速查找完成這個轉換。

⑷序列階段。利用大項目集，發現所期望的序列。

⑸最大階段。在大序列中發現最大的序列。

4 在入侵檢測中應用數據挖掘技術的優點

數據挖掘技術能夠從大量的審計數據和網絡數據中抽取出能充分描述網絡連接和主機會話特征的屬性，利用數據挖掘技術產生能夠精確描述入侵行為和系統正常行為模式的規則，并自動產生精確適用的檢測模型。同時應用數據挖掘方法的檢測系統不是基于預定義的檢測模型，自適應能力強，可以有效地檢測新型攻擊以及己知攻擊的變種，也可以有效地剔除重復的攻擊數據，因而具有較低的虛警率，減少漏報的發生。

[參考文獻]

[1]李志云，周國祥，張麗萍.一種挖掘大型數據庫的關聯規則新算法[J]. 合肥工業大學學報（自然科學版）.2010（02）.

[2]Armananzas R，IInza，R.Santana，et al.A review of estimation of distribution algorithms in bioinformatics.BioData Min. 2008.

[3]李學明.計算機數據的關聯規則挖掘理論和算法研究[D].重慶大學.