魏明軍，田 昆

(華北理工大學(xué)，河北 唐山 063000)

改進(jìn)K中心點(diǎn)算法在入侵檢測(cè)的應(yīng)用

魏明軍，田 昆

(華北理工大學(xué)，河北 唐山 063000)

傳統(tǒng)K中心點(diǎn)算法雖然改進(jìn)了K均值算法對(duì)噪聲和孤立點(diǎn)數(shù)據(jù)敏感的不足，但是仍存在著初始聚類(lèi)中心和聚類(lèi)個(gè)數(shù)k難以確定的問(wèn)題，因此，針對(duì)算法存在的問(wèn)題，提出一種基于密度的改進(jìn)K中心點(diǎn)算法。該算法會(huì)根據(jù)數(shù)據(jù)集數(shù)據(jù)的分布情況自主確定聚類(lèi)個(gè)數(shù)k和k個(gè)聚類(lèi)中心點(diǎn)。最后，通過(guò)在入侵檢測(cè)領(lǐng)域KDD Cup99數(shù)據(jù)集上實(shí)驗(yàn)測(cè)試表明，改進(jìn)K中心點(diǎn)算法不僅能夠自動(dòng)形成k個(gè)聚類(lèi)，而且具有較高的入侵檢測(cè)率和較低的漏報(bào)率，聚類(lèi)和入侵檢測(cè)的效果均優(yōu)于傳統(tǒng)的K中心點(diǎn)算法。

入侵檢測(cè)；K中心點(diǎn)算法；改進(jìn)K中心點(diǎn)算法；聚類(lèi)分析

入侵檢測(cè)作為一種有別于防火墻的安全技術(shù)，能夠提供對(duì)來(lái)自外部和內(nèi)部攻擊的實(shí)時(shí)監(jiān)控。然而，傳統(tǒng)的兩種入侵檢測(cè)技術(shù)誤用檢測(cè)和異常檢測(cè)，在入侵檢測(cè)性能的兩個(gè)評(píng)價(jià)指標(biāo)誤檢率和檢測(cè)率上各有長(zhǎng)短，前者的特點(diǎn)是誤檢率低但檢測(cè)率低，不能檢測(cè)新型的未知攻擊，后者正好相反，特點(diǎn)是檢測(cè)率高但誤檢率高，它能夠檢測(cè)出新型的攻擊，適應(yīng)性好，但是存在高誤檢率問(wèn)題。

聚類(lèi)分析是數(shù)據(jù)挖掘中常用的一種無(wú)監(jiān)督的學(xué)習(xí)方法，它依據(jù)數(shù)據(jù)內(nèi)部的潛在關(guān)聯(lián)將數(shù)據(jù)集中的數(shù)據(jù)依據(jù)相似性劃分成不同的分類(lèi)，同一分類(lèi)中的數(shù)據(jù)之間具有較高的相似度，不同分類(lèi)的數(shù)據(jù)之間有較大的差異性，這一點(diǎn)正滿(mǎn)足了入侵檢測(cè)中異常檢測(cè)的需要。異常檢測(cè)需要建立正常行為庫(kù)和異常行為庫(kù)來(lái)區(qū)分正常行為和攻擊行為，而且要求兩個(gè)行為庫(kù)各自?xún)?nèi)部的數(shù)據(jù)越相似越好，兩個(gè)行為庫(kù)之間數(shù)據(jù)差異性越大越好。因此，可以將聚類(lèi)分析應(yīng)用于入侵檢測(cè)來(lái)提高入侵檢測(cè)的檢測(cè)率和降低漏報(bào)率。

1.K中心點(diǎn)算法

1.1 基本思想

K中心點(diǎn)算法與K均值算法是數(shù)據(jù)挖掘聚類(lèi)分析中基于劃分的算法中比較經(jīng)典的兩個(gè)算法，應(yīng)用較為廣泛?；趧澐值木垲?lèi)方法的思想是首先創(chuàng)建一個(gè)數(shù)據(jù)集的初始劃分，然后采用迭代重定位技術(shù)，使樣本在劃分塊間移動(dòng)，提高聚類(lèi)的相似度，最終得到一個(gè)較為完善的數(shù)據(jù)劃分。K均值算法簡(jiǎn)單易實(shí)現(xiàn)，但是對(duì)噪聲和孤立點(diǎn)數(shù)據(jù)敏感；K中心點(diǎn)算法改進(jìn)了K均值算法的不足，具有較高的穩(wěn)定性。

K中心點(diǎn)算法的基本思想：首先為每個(gè)分類(lèi)隨機(jī)選擇一個(gè)中心點(diǎn)，然后計(jì)算剩余的數(shù)據(jù)對(duì)象與各分類(lèi)中心之間的距離，根據(jù)距離的遠(yuǎn)近將數(shù)據(jù)對(duì)象分配給最近的一個(gè)分類(lèi)；然后，計(jì)算每個(gè)簇中所有點(diǎn)的平均值，選用離平均值最近的點(diǎn)作為新的簇中心，再次對(duì)數(shù)據(jù)點(diǎn)進(jìn)行劃分，該過(guò)程不斷循環(huán)直到類(lèi)簇的中心不再發(fā)生變化(類(lèi)簇的絕對(duì)誤差之和收斂)為止。類(lèi)簇的絕對(duì)誤差之和直接反應(yīng)了聚類(lèi)的質(zhì)量，它的值越小，表示類(lèi)簇越緊湊，那么聚類(lèi)效果就越好。

1.2 聚類(lèi)步驟

輸入：包含n個(gè)樣本的數(shù)據(jù)集和簇?cái)?shù)目k。

輸出：k個(gè)類(lèi)簇。

流程：

1) 隨機(jī)選擇k個(gè)樣本點(diǎn)作為初始的簇中心；

2) 重復(fù)下列(1)(2)(3)(4)步驟直到k個(gè)中心點(diǎn)不再發(fā)生變化：

(1) 指派每個(gè)剩余樣本給離它最近的中心點(diǎn)所代表的簇；

(2) 計(jì)算每個(gè)簇中所有點(diǎn)的均值作為候選簇中心點(diǎn)c；

(3) 隨機(jī)地選擇一個(gè)非中心點(diǎn)x；

(4) 如果用x代替候選中心點(diǎn)c后得到的聚類(lèi)絕對(duì)誤差和減小，則用x代替c形成新的中心點(diǎn)；

3) 輸出k個(gè)類(lèi)簇。

1.3 算法不足

K中心點(diǎn)聚類(lèi)算法的優(yōu)點(diǎn)是算法思想較簡(jiǎn)單，容易實(shí)現(xiàn)，同時(shí)能夠有效降低噪聲和孤立點(diǎn)的影響，但是該算法仍存在一些不足之處：

1)K中心點(diǎn)算法在聚類(lèi)之初就需要輸入聚類(lèi)數(shù)目k，這樣要想達(dá)到一個(gè)好的聚類(lèi)效果往往要嘗試很多次才可能找到一個(gè)比較合適的k值，所以存在著聚類(lèi)數(shù)據(jù)k難以確定的問(wèn)題。

2)K中心點(diǎn)算法存在因初始點(diǎn)的選取問(wèn)題而導(dǎo)致不穩(wěn)定的聚類(lèi)結(jié)果的缺陷，容易使算法陷入局部最優(yōu)解，不同的初始點(diǎn)不僅會(huì)導(dǎo)致不同的運(yùn)行效率，更可能會(huì)產(chǎn)生不同的聚類(lèi)結(jié)果，直接影響算法的實(shí)際應(yīng)用效率。

2.改進(jìn)K中心點(diǎn)算法

2.1 基本思想

改進(jìn)K中心點(diǎn)算法的基本思想：聚類(lèi)簇的中心點(diǎn)應(yīng)該是鄰域范圍內(nèi)密度最高且鄰域平均距離最短的點(diǎn)，而且趨向于更高密度、更短平均距離的樣本點(diǎn)移動(dòng)。具體做法：采用定寬的聚類(lèi)方法，預(yù)先設(shè)定聚類(lèi)半徑R，同時(shí)將數(shù)據(jù)點(diǎn)周?chē)徲虬霃絉范圍內(nèi)包含的其他數(shù)據(jù)點(diǎn)的個(gè)數(shù)定義為該數(shù)據(jù)點(diǎn)的密度，將R范圍內(nèi)包含的其他數(shù)據(jù)點(diǎn)到該數(shù)據(jù)點(diǎn)的平均距離定義為該點(diǎn)的鄰域平均距離，在聚類(lèi)過(guò)程中調(diào)整各個(gè)類(lèi)簇的聚類(lèi)中心時(shí)，用各類(lèi)簇中密度最高、鄰域平均距離最短的數(shù)據(jù)點(diǎn)作為新的聚類(lèi)中心，再次對(duì)數(shù)據(jù)點(diǎn)進(jìn)行劃分，直到各類(lèi)簇中心不再發(fā)生變化時(shí)聚類(lèi)終止。

2.2 相關(guān)概念

定義1 任意兩個(gè)數(shù)據(jù)對(duì)象之間的歐幾里得距離定義為：

(1)

式中：xi=(xi1,xi2,…,xim)，yj=(yj1,yj2,…,yjm)都是m維的數(shù)據(jù)對(duì)象。

定義2 訓(xùn)練數(shù)據(jù)集平均距離定義為：

(2)

定義3 數(shù)據(jù)對(duì)象的鄰域半徑R定義為：

(3)

式中：m為正整數(shù)，通常取值為2。

定義4 數(shù)據(jù)對(duì)象密度函數(shù)定義為：

Density(xi)={p|d(p,xi)πR,p∈X,xi∈X}

(4)

式中：X是數(shù)據(jù)對(duì)象集合，d(p,xi)為數(shù)據(jù)對(duì)象p到數(shù)據(jù)對(duì)象xi的距離，R代表鄰域半徑，采用歐幾里得距離計(jì)算。

定義5R鄰域平均距離定義為：

(5)

式中：NR是數(shù)據(jù)對(duì)象xi鄰域半徑R內(nèi)的點(diǎn)數(shù)即Density(xi)。

數(shù)據(jù)集中的每個(gè)對(duì)象可以根據(jù)以上5個(gè)定義的計(jì)算方法計(jì)算出對(duì)應(yīng)的數(shù)據(jù)對(duì)象的密度值及鄰域平均距離，這兩個(gè)值將會(huì)被用作聚類(lèi)中選擇聚類(lèi)中心對(duì)象的依據(jù)。

2.3 算法描述

改進(jìn)K中心點(diǎn)算法的整個(gè)算法描述如下：

輸入：X={x1,x2,…,xn}是包含n個(gè)對(duì)象的數(shù)據(jù)集合，鄰域半徑R，閾值θ。

輸出：k個(gè)數(shù)據(jù)分類(lèi)。

過(guò)程：

1) 根據(jù)輸入的數(shù)據(jù)對(duì)象，計(jì)算出R、每個(gè)對(duì)象的數(shù)據(jù)對(duì)象密度及鄰域平均距離；

2) 將第一個(gè)數(shù)據(jù)對(duì)象x1作為類(lèi)簇C1的中心點(diǎn)oc1：

Do

(1) 計(jì)算數(shù)據(jù)對(duì)象xi到每個(gè)聚類(lèi)Cj聚類(lèi)中心的距離d(xi,oj)；

(2) 比較d(xi,oj)與鄰域半徑R大小，若d(xi,oj)≤R，比較數(shù)據(jù)對(duì)象xi與聚類(lèi)中心點(diǎn)oj的數(shù)據(jù)對(duì)象密度和鄰域平均距離，如果Density(xi)R，則建立新的類(lèi)簇Ck，并將數(shù)據(jù)對(duì)象xi作為它的聚類(lèi)中心點(diǎn)；

Until所有類(lèi)簇的聚類(lèi)中心不再發(fā)生變化。

3.測(cè)試實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)集選擇

KDDCup99 數(shù)據(jù)集是入侵檢測(cè)領(lǐng)域比較權(quán)威的測(cè)試數(shù)據(jù)，測(cè)試用的數(shù)據(jù)選自數(shù)據(jù)集中的10%數(shù)據(jù)集“kddcup.data_10.percent”，該數(shù)據(jù)集共有494021個(gè)記錄，正常網(wǎng)絡(luò)數(shù)據(jù)的數(shù)目為97278，剩下全部為攻擊行為數(shù)據(jù)。其中，攻擊行為數(shù)據(jù)可以分為四個(gè)類(lèi)別，分別是Dos攻擊、U2R攻擊、R2L攻擊和Probe攻擊。

聚類(lèi)分析算法能夠應(yīng)用在入侵檢測(cè)中是基于以下兩個(gè)基本的假設(shè)：

(1)正常數(shù)據(jù)的數(shù)量遠(yuǎn)遠(yuǎn)大于攻擊數(shù)據(jù)的數(shù)量；

(2)攻擊數(shù)據(jù)在某些屬性的取值上明顯偏離正常的取值范圍。

因此，在該數(shù)據(jù)集中選擇2000條數(shù)據(jù)作為測(cè)試數(shù)據(jù)集，其中正常數(shù)據(jù)1960，異常數(shù)據(jù)40條，異常數(shù)據(jù)占比為2%，滿(mǎn)足以上兩個(gè)假設(shè)。

3.2 評(píng)價(jià)指標(biāo)

對(duì)于入侵檢測(cè)系統(tǒng)，評(píng)價(jià)其性能的最重要的兩個(gè)指標(biāo)是檢測(cè)率和漏報(bào)率，二者的具體定義如下：

誤報(bào)率=被誤判為入侵的正常記錄數(shù)/總測(cè)試記錄中的正常記錄數(shù)。

檢測(cè)率=檢測(cè)出來(lái)的入侵記錄數(shù)/總測(cè)試中的入侵記錄數(shù)。

3.3 性能實(shí)驗(yàn)

將數(shù)據(jù)集分別在K中心點(diǎn)算法和改進(jìn)的K中心點(diǎn)算法上進(jìn)行實(shí)驗(yàn)，最后比較算法性能。由于K中心點(diǎn)算法需要在聚類(lèi)之初便確定聚類(lèi)個(gè)數(shù)，而且聚類(lèi)個(gè)數(shù)的不同選擇將會(huì)對(duì)聚類(lèi)算法的最終結(jié)果產(chǎn)生非常大的影響，因此在設(shè)置不同聚類(lèi)個(gè)數(shù)的條件下得出的K中心點(diǎn)算法聚類(lèi)效果如表1所示。

改進(jìn)K中心點(diǎn)算法不需要在聚類(lèi)之初便確定聚類(lèi)的數(shù)目，它可以根據(jù)數(shù)據(jù)集中數(shù)據(jù)的特征自主確定產(chǎn)生聚類(lèi)的數(shù)目。改進(jìn)K中心點(diǎn)算法性能如表2。

表1 K中心點(diǎn)算法性能

表2 改進(jìn)K中心點(diǎn)算法性能

從表1和表2可以看出，和K中心點(diǎn)算法比較，改進(jìn)K中心點(diǎn)算法在不需要輸入聚類(lèi)個(gè)數(shù)的前提下，能夠根據(jù)數(shù)據(jù)特點(diǎn)找出比較適當(dāng)?shù)木垲?lèi)數(shù)量，且有一個(gè)較好的誤報(bào)率和檢測(cè)率。

4. 結(jié)論

本文提出了基于密度的改進(jìn)K中心點(diǎn)算法，解決了傳統(tǒng)K中心點(diǎn)算法初始聚類(lèi)中心和聚類(lèi)個(gè)數(shù)k難以確定的問(wèn)題。由實(shí)驗(yàn)結(jié)果可知，將改進(jìn)算法應(yīng)用在入侵檢測(cè)的異常檢測(cè)中，改進(jìn)算法的聚類(lèi)性能和入侵檢測(cè)的檢測(cè)性能均優(yōu)于傳統(tǒng)K中心點(diǎn)算法，因此將改進(jìn)K中心點(diǎn)算法應(yīng)用在入侵檢測(cè)中可以提高入侵檢測(cè)率，同時(shí)降低漏報(bào)率，有效提高入侵檢測(cè)的性能。

[1]MohammadrezaEktefa,SaraMemar,FatimahSidi,LillySurianiAffendeyIntrusiondetectionusingdataminingtechniques[C]//In:Internationalconferenceoninformationretrievalandknowledgemanagement, 2010，200-204.

[2]蘇家洪.入侵檢測(cè)系統(tǒng)新技術(shù)介紹[J].中國(guó)新技術(shù)新產(chǎn)品，2012,0(3) ：43-43.

[3]劉向旗. 基于數(shù)據(jù)挖掘的入侵檢測(cè)系統(tǒng)研究[J]. 信息系統(tǒng)工程，2013,0(4)：44-45.

[4]李賀玲. 數(shù)據(jù)挖掘在網(wǎng)絡(luò)入侵檢測(cè)中的應(yīng)用研究[D]. 吉林：吉林大學(xué)，2013.

ApplicationofImprovedK-MedoidsAlgorithminIntrusionDetection

WEI Ming-jun, TIAN Kun
(North China University of Science and Technology, Tangshan 063000, China)

The k-means algorithm has the problem which is sensitive to noise and outlier data. Though the traditional k-medoids algorithm overcomes the problem, it still has another two problems. One is determining the initial cluster centers, and the other is determining the cluster number k. In order to solve the problems, an improved k-medoids algorithm based on density is proposed. It can determine the cluster number k and cluster centers independently according to the distribution of the data set. Experimental test on the KDD Cup99 data set in the intrusion detection field shows that the improved k-medoids can not only automatically form the center of the k cluster, but also has high detection rate and low false negative rate. The effect of clustering and intrusion detection is better than that of the traditional k-medoids algorithm.

intrusion detection; k-medoids algorithm; improved k-medoids algorithm; cluster analysis

TP393

A

1671-3974(2017)04-0057-03

2017-09-02

魏明軍(1969- )，男，碩士，華北理工大學(xué)信息工程學(xué)院教授，研究方向：入侵檢測(cè)，數(shù)據(jù)挖掘。