楊銘

摘 要：數(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ù)都由一個唯一的標識符，稱為TID。

定義3：數(shù)據(jù)集D中包含項目集X的事務(wù)數(shù)稱為項目集X的支持數(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)的問題分解成以下幾個階段：

⑴排序階段。利用客戶標識字作為主關(guān)鍵字及事務(wù)發(fā)生的時間做為次關(guān)鍵字將數(shù)據(jù)庫進行排序，該步驟也將原始的事務(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ù)庫，或者當在一個遍歷期間讀每一個客戶序列時通過快速查找完成這個轉(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ā)生。

[參考文獻]

[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é).