入侵檢測中常用數(shù)據(jù)挖掘算法的分析與研究

楊銘

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

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)分析；序列分析；算法

1 引言

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

2 關(guān)聯(lián)分析算法

關(guān)聯(lián)規(guī)則挖掘技術(shù)用于發(fā)現(xiàn)數(shù)據(jù)庫中屬性之間的有趣關(guān)聯(lián)，和傳統(tǒng)的產(chǎn)生式規(guī)則不同，關(guān)聯(lián)規(guī)則可以有一個或者多個關(guān)聯(lián)屬性。同時一個規(guī)則的輸出屬性可以是另外一個的輸入屬性。

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

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

定義3：數(shù)據(jù)集D中包含項目集X的事務(wù)數(shù)稱為項目集X的支持?jǐn)?shù)，記為σx。項目集X的支持度記為support（x）：

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

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

3 序列分析算法

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

⑴排序階段。利用客戶標(biāo)識字作為主關(guān)鍵字及事務(wù)發(fā)生的時間做為次關(guān)鍵字將數(shù)據(jù)庫進(jìn)行排序，該步驟也將原始的事務(wù)數(shù)據(jù)庫轉(zhuǎn)換成客戶序列的數(shù)據(jù)庫。

⑵大項目集階段。在該階段發(fā)現(xiàn)所有的大項目集L，同時發(fā)現(xiàn)了所有的大1序列的集合，并把大數(shù)據(jù)項集映射為一組相鄰的整數(shù)，每個大數(shù)據(jù)項對應(yīng)一個整數(shù)。

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

⑷序列階段。利用大項目集，發(fā)現(xiàn)所期望的序列。

⑸最大階段。在大序列中發(fā)現(xiàn)最大的序列。

4 在入侵檢測中應(yīng)用數(shù)據(jù)挖掘技術(shù)的優(yōu)點

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

[參考文獻(xiàn)]

[1]李志云，周國祥，張麗萍.一種挖掘大型數(shù)據(jù)庫的關(guān)聯(lián)規(guī)則新算法[J]. 合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版）.2010（02）.

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

[3]李學(xué)明.計算機數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘理論和算法研究[D].重慶大學(xué).