數(shù)據(jù)挖掘中聚類算法比較及在武警網(wǎng)絡(luò)中的應(yīng)用研究

摘 要：聚類算法是數(shù)據(jù)挖掘的核心技術(shù)，根據(jù)評(píng)價(jià)聚類算法優(yōu)劣的幾個(gè)標(biāo)準(zhǔn)，對(duì)數(shù)據(jù)挖掘中常用聚類算法做了比較分析，根據(jù)各自特點(diǎn)，加以改進(jìn)，并應(yīng)用于武警部隊(duì)數(shù)據(jù)挖掘項(xiàng)目中。通過(guò)運(yùn)用改進(jìn)型Kmeans算法，取得了較好的挖掘結(jié)果，為進(jìn)一步信息的智能化檢索、信息的過(guò)濾、分揀提供依據(jù)。

關(guān)鍵詞：數(shù)據(jù)挖掘;代表點(diǎn)聚類算法;基于密度的聚類算法;Kmeans聚類算法;指揮自動(dòng)化

中圖分類號(hào)：TP274文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1004-373X(2008)08-115-03

Comparison of Clustering Method in Data Mining and Application of Armed Police Force Network

TIAN Jie，ZHOU Xiaojuan，LV Jianxin

(Engineering College of Armed Police Force，Xi′an，710086，China)

Abstract：Clustering method is the core of data mining technology.In this paper，several standards are used to evaluate these clustering methods.Finally the author elicits an advanced Kmeans clustering algorithms to the armed police actual network，obtaining good result，which will provide basis for further information on intelligent retrieval，information filtering，sorting，and so on.

Keywords：data mining;DBSCAN;CURE;Kmeans;command automation

1 引 言

數(shù)據(jù)挖掘的歷史雖然較短，但從20世紀(jì)90年代以來(lái)，他的發(fā)展速度很快，是多學(xué)科綜合的產(chǎn)物。雖然目前還沒(méi)有一個(gè)完整的定義，但這里認(rèn)為：數(shù)據(jù)挖掘就是從海量的數(shù)據(jù)中挖掘出可能有潛在價(jià)值的信息的技術(shù)。這些信息是可能有潛在價(jià)值的，支持決策，可以有效利用指揮自動(dòng)化網(wǎng)，為進(jìn)一步研究尋找突破口。

數(shù)據(jù)挖掘綜合了各個(gè)學(xué)科技術(shù)，其任務(wù)一般可分為2類：描述和預(yù)測(cè)。描述性挖掘任務(wù)刻劃數(shù)據(jù)庫(kù)中數(shù)據(jù)的一般特性。預(yù)測(cè)性挖掘任務(wù)在當(dāng)前數(shù)據(jù)上進(jìn)行推斷，以進(jìn)行預(yù)測(cè)\\[1\\]。主要功能有分類和預(yù)測(cè)、聚類分析、關(guān)聯(lián)規(guī)則和序列模式的發(fā)現(xiàn)、偏差的檢測(cè)等。

把數(shù)據(jù)庫(kù)中的對(duì)象分類是數(shù)據(jù)挖掘的基本操作，根據(jù)最大化類內(nèi)的相似性、最小化類間的相似性的原則進(jìn)行聚類或分組，從而使屬于同一類的個(gè)體間距離盡可能小，而不同類個(gè)體間距離盡可能大，為了找到效率高、通用性強(qiáng)的聚類方法人們從不同角度提出近百種聚類方法，典型的有Kmeans方法、Kmedoids方法、CLARANS方法，BIRCH方法等，這些算法適用于特定的問(wèn)題及用戶。

聚類算法一般分為分割和分層2種。分割聚類算法通過(guò)優(yōu)化評(píng)價(jià)函數(shù)把數(shù)據(jù)集分割為K個(gè)部分，他需要K作為輸人參數(shù)。典型的分割聚類算法有Kmeans算法：Kmedoids算法、CLARANS算法。分層聚類由不同層次的分割聚類組成，層次之間的分割具有嵌套的關(guān)系。他不需要輸入?yún)?shù)，這是他優(yōu)于分割聚類算法的一個(gè)明顯的優(yōu)點(diǎn)，其缺點(diǎn)是終止條件必須具體指定。典型的分層聚類算法有BIRCH算法、DBSCAN算法和CURE算法等。根據(jù)評(píng)價(jià)聚類算法優(yōu)劣的幾個(gè)標(biāo)準(zhǔn)\\[2\\]，對(duì)常用的聚類算法進(jìn)行比較分析。

(1) 是否適用于大數(shù)據(jù)量，算法的效率是否滿足大數(shù)據(jù)量高復(fù)雜性的要求;

(2) 是否能應(yīng)付不同的數(shù)據(jù)類型，能否處理符號(hào)屬性;

(3) 是否能發(fā)現(xiàn)不同類型的聚類;

(4) 是否能應(yīng)付噪聲數(shù)據(jù)或異常數(shù)據(jù);

(5) 是否對(duì)數(shù)據(jù)的輸入順序不敏感。

2 數(shù)據(jù)挖掘常用聚類算法比較分析

2.1 BIRCH算法

BIRCH算法即平衡迭代削減聚類法，其核心是用一個(gè)聚類特征3元組表示一個(gè)簇的有關(guān)信息，從而使一簇點(diǎn)的表示可用對(duì)應(yīng)的聚類特征，而不必用具體的一組點(diǎn)來(lái)表示。他通過(guò)構(gòu)造滿足分支因子和簇直徑限制的聚類特征樹(shù)來(lái)求聚類。BIRCH算法通過(guò)聚類特征可以方便地進(jìn)行中心、半徑、直徑及類內(nèi)、類間距離的運(yùn)算。算法的聚類特征樹(shù)是一個(gè)具有2個(gè)參數(shù)分枝因子B和類直徑T的高度平衡樹(shù)。分枝因子規(guī)定了樹(shù)的每個(gè)節(jié)點(diǎn)子女的最多個(gè)數(shù)，而類直徑體現(xiàn)了對(duì)一類點(diǎn)的直徑大小的限制即這些點(diǎn)在多大范圍內(nèi)可以聚為一類，非葉子結(jié)點(diǎn)為他的子女的最大關(guān)鍵字，可以根據(jù)這些關(guān)鍵字進(jìn)行插人索引，他總結(jié)了其子女的信息。

聚類特征樹(shù)可以動(dòng)態(tài)構(gòu)造，因此不要求所有數(shù)據(jù)讀人內(nèi)存，而可以在外存上逐個(gè)讀人。新的數(shù)據(jù)項(xiàng)總是插人到樹(shù)中與該數(shù)據(jù)距離最近的葉子中。如果插人后使得該葉子的直徑大于類直徑T，則把該葉子節(jié)點(diǎn)分裂。其他葉子結(jié)點(diǎn)也需要檢查是否超過(guò)分枝因子來(lái)判斷其分裂與否，直至該數(shù)據(jù)插入到葉子中，并且滿足不超過(guò)類直徑，而每個(gè)非葉子節(jié)點(diǎn)的子女個(gè)數(shù)不大于分枝因子。算法還可以通過(guò)改變類直徑修改特征樹(shù)大小，控制其占內(nèi)存容量。

BIRCH算法通過(guò)一次掃描就可以進(jìn)行較好的聚類，由此可見(jiàn)，該算法適合于大數(shù)據(jù)量。BIRCH算法只適用于類的分布呈凸形及球形的情況，并且由于BIRCH算法需提供正確的聚類個(gè)數(shù)和簇直徑限制，對(duì)不可視的高維數(shù)據(jù)不可行。

2.2 CURE算法

CURE算法即使用代表點(diǎn)的聚類方法。該算法先把每個(gè)數(shù)據(jù)點(diǎn)看成一類，然后合并距離最近的類直至類個(gè)數(shù)為所要求的個(gè)數(shù)為止。CURE算法將傳統(tǒng)對(duì)類的表示方法進(jìn)行改進(jìn)，回避用所有點(diǎn)或用中心和半徑來(lái)表示一個(gè)類；而是從每一個(gè)類中抽取固定數(shù)量、分布較好的點(diǎn)作為描述此類的代表點(diǎn)，并將這些點(diǎn)乘以一個(gè)適當(dāng)?shù)氖湛s因子，使他們更靠近類的中心點(diǎn)。將一個(gè)類用代表點(diǎn)表示，使得類的外延可以向非球形的形狀擴(kuò)展，從而可調(diào)整類的形狀以表達(dá)那些非球形的類。另外，收縮因子的使用減小嗓音對(duì)聚類的影響。CURE算法采用隨機(jī)抽樣與分割相結(jié)合的辦法提高算法的空間和時(shí)間效率，并且在算法中用堆和Kd樹(shù)結(jié)構(gòu)來(lái)提高算法效率。

2.3 DBSCAN算法

DBSCAN算法即基于密度的聚類算法。該算法利用類的密度連通性可以快速發(fā)現(xiàn)任意形狀的類。其基本思想是：對(duì)于一個(gè)類中的每個(gè)對(duì)象，在其給定半徑的領(lǐng)域中包含的對(duì)象不能少于某一給定的最小數(shù)目。在DBSCAN算法中，發(fā)現(xiàn)一個(gè)類的過(guò)程是基于這樣的事實(shí)：一個(gè)類能夠被其中的任意一個(gè)核心對(duì)象所確定。為了發(fā)現(xiàn)一個(gè)類，DBSCAN先從對(duì)象集D中找到任意對(duì)象P，并查找D中關(guān)于關(guān)徑Eps和最小對(duì)象數(shù)Minpts的從P密度可達(dá)的所有對(duì)象。如果P是核心對(duì)象，即半徑為Eps的P的鄰域中包含的對(duì)象不少于Minpts，則根據(jù)算法，可以找到一個(gè)關(guān)于參數(shù)Eps和Minpts的類。如果P是一個(gè)邊界點(diǎn)，則半徑為Eps的P鄰域包含的對(duì)象少于Minpts，P被暫時(shí)標(biāo)注為噪聲點(diǎn)。然后，DBSCAN處理D中的下一個(gè)對(duì)象。

密度可達(dá)對(duì)象的獲取是通過(guò)不斷執(zhí)行區(qū)域查詢來(lái)實(shí)現(xiàn)的。一個(gè)區(qū)域查詢返回指定區(qū)域中的所有對(duì)象。為了有效地執(zhí)行區(qū)域查詢，DBSCAN算法使用空間查詢R-樹(shù)結(jié)構(gòu)。在進(jìn)行聚類前，必須建立針對(duì)所有數(shù)據(jù)的R*-樹(shù)。另外，DBSCAN要求用戶指定一個(gè)全局參數(shù)Eps(為了減少計(jì)算量，預(yù)先確定參數(shù)Minpts)。為了確定取值，DBSCAN計(jì)算任意對(duì)象與他的第K個(gè)最臨近的對(duì)象之間的距離。然后，根據(jù)求得的距離由小到大排序，并繪出排序后的圖，稱Kdist圖。Kdist圖中的橫坐標(biāo)表示數(shù)據(jù)對(duì)象與他的第K個(gè)最近的對(duì)象間的距離;縱坐標(biāo)為對(duì)應(yīng)于某一Kdist距離值的數(shù)據(jù)對(duì)象的個(gè)數(shù)。R*-樹(shù)的建立和Kdist圖的繪制非常消耗時(shí)間。此外，為了得到較好的聚類結(jié)果，用戶必須根據(jù)Kdist圖，通過(guò)試探選定一個(gè)比較合適的Eps值。DBSCAN算法不進(jìn)行任何的預(yù)處理而直接對(duì)整個(gè)數(shù)據(jù)集進(jìn)行聚類操作。當(dāng)數(shù)據(jù)量非常大時(shí)，就必須有大內(nèi)存量支持，I/O消耗也非常大。其時(shí)間復(fù)雜度為O(nlog n)(n為數(shù)據(jù)量)，聚類過(guò)程的大部分時(shí)間用在區(qū)域查詢操作上。

2.4 Kpototypes算法

Kpototypes算法結(jié)合Kmeans方法和根據(jù)Kmeans方法改進(jìn)的能夠處理符號(hào)屬性的Kmodes方法，同Kmeans方法相比，Kpototypes 算法能夠處理符號(hào)屬性。

2.5 CLARANS算法

CLARANS算法即隨機(jī)搜索聚類算法，是一種分割聚類方法。他首先隨機(jī)選擇一個(gè)點(diǎn)作為當(dāng)前點(diǎn)，然后隨機(jī)檢查他周圍不超過(guò)參數(shù)Maxneighbor個(gè)的一些鄰接點(diǎn)，假如找到一個(gè)比他更好的鄰接點(diǎn)，則把他移人該鄰接點(diǎn)，否則把該點(diǎn)作為局部最小量。然后再隨機(jī)選擇一個(gè)點(diǎn)來(lái)尋找另一個(gè)局部最小量，直到所找到的局部最小量數(shù)目達(dá)到用戶要求為止。該算法要求聚類的對(duì)象必須都預(yù)先調(diào)人內(nèi)存，并且需多次掃描數(shù)據(jù)集，這對(duì)大數(shù)據(jù)量而言，無(wú)論時(shí)間復(fù)雜度還是空間復(fù)雜度都相當(dāng)大。雖通過(guò)引人R樹(shù)結(jié)構(gòu)對(duì)其性能進(jìn)行改善，使之能夠處理基于磁盤(pán)的大型數(shù)據(jù)庫(kù)，但R*樹(shù)的構(gòu)造和維護(hù)代價(jià)太大。該算法對(duì)臟數(shù)據(jù)和異常數(shù)據(jù)不敏感，但對(duì)數(shù)據(jù)物人順序異常敏感，且只能處理凸形或球形邊界聚類。

2.6 CLIQUE算法

CLIQUE 9法即自動(dòng)子空間聚類算法。該算法利用自頂向上方法求出各個(gè)子空間的聚類單元。CUQUE算法主要用于找出在高維數(shù)據(jù)空間中存在的低維聚類。為了求出d維空間聚類，必須組合給出所有d-1維子空間的聚類，導(dǎo)致其算法的空間和時(shí)間效率都較低，而且要求用戶輸入2個(gè)參數(shù)：數(shù)據(jù)取值空間等間隔距離和密度闊值。這2個(gè)參數(shù)與樣木數(shù)據(jù)緊密相關(guān)，用戶一般難以確定。CLIQUE算法對(duì)數(shù)據(jù)輸人順序不敏感。

由于每個(gè)方法都有其特點(diǎn)和不同的適用領(lǐng)域，在數(shù)據(jù)挖掘中，用戶應(yīng)該根據(jù)實(shí)際需要選擇恰當(dāng)?shù)木垲愃惴ā＊?/p>

3 武警網(wǎng)絡(luò)據(jù)挖掘技術(shù)中Kmeans算法的應(yīng)用

根據(jù)武警網(wǎng)絡(luò)實(shí)際，項(xiàng)目主要圍繞基于DM技術(shù)的武警網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的構(gòu)建(屬于網(wǎng)絡(luò)用法挖掘范疇)和基于DM技術(shù)的武警網(wǎng)絡(luò)輔助決策系統(tǒng)的構(gòu)建(屬于網(wǎng)絡(luò)內(nèi)容挖掘范疇)。在武警網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的檢測(cè)挖掘算法方面采用廣域網(wǎng)上的kddcup data網(wǎng)絡(luò)數(shù)據(jù)流數(shù)據(jù)包作為挖掘?qū)嶒?yàn)數(shù)據(jù)，提出一種改進(jìn)的Kmeans算法，將傳統(tǒng)算法任意選取初始聚類中心變?yōu)檫x取出現(xiàn)頻率最高的一組數(shù)據(jù)作為初始聚類中心，從而極大地提高Kmeans的速度，取得較好的挖掘?qū)嶒?yàn)結(jié)果。

整體思想是先用模式匹配的算法檢測(cè)出主要的和已知的入侵行為，然后針對(duì)剩余的和未知的新的入侵方式用聚類方式進(jìn)行檢測(cè)。具體步驟如圖1所示。

首先對(duì)數(shù)據(jù)分析其屬性，選取特征向量，并對(duì)各條記錄的特征項(xiàng)數(shù)據(jù)標(biāo)準(zhǔn)化，然后對(duì)標(biāo)準(zhǔn)化后的數(shù)據(jù)用Kmeans聚類，通過(guò)調(diào)整輸入?yún)?shù)得到較好的結(jié)果，并根據(jù)設(shè)定的類的大小劃分出異常類，最后將需要判斷的數(shù)據(jù)與已得到的類的質(zhì)心進(jìn)行距離比較，從而判斷是否屬于異常類，是否為異常數(shù)據(jù)。目前得到的是實(shí)驗(yàn)數(shù)據(jù)上的統(tǒng)計(jì)結(jié)果，在實(shí)際檢測(cè)中還需要對(duì)一些參數(shù)進(jìn)行自適應(yīng)的調(diào)整。該過(guò)程是用matlab仿真，主要模塊為std_data.m，cluster_size.m，result_show.m及運(yùn)行結(jié)果如圖1所示：

圖1表示程序運(yùn)行結(jié)果聚類一共分為9類，各類中的記錄數(shù)目如圖1所示，其中第8類為229條記錄。第8個(gè)類中各條記錄的編號(hào)以及該記錄的異常類型為6，即neptune攻擊。第8個(gè)類中正常數(shù)據(jù)的個(gè)數(shù)為8個(gè)。

目前已知的網(wǎng)絡(luò)攻擊可以歸納為4個(gè)類型：dos為拒絕服務(wù);u2r為特權(quán)用戶濫用;r2l為遠(yuǎn)程登陸;probe為探測(cè)（或掃描）。上面檢測(cè)出的neptune屬dos類攻擊。通過(guò)以上模擬可以計(jì)算出參數(shù)輸入為9時(shí)的檢測(cè)率和誤檢率。[LL]經(jīng)調(diào)整參數(shù)，可得趨勢(shì)圖如圖2所示：

圖2中上面的曲線為檢測(cè)率，下面的為誤檢率，由圖可推斷聚類數(shù)目為10，異常類大小為1 000時(shí)，效果相對(duì)較好，但這種算法存在異常類大小的硬劃分，對(duì)于實(shí)時(shí)檢測(cè)下一步仍需要改進(jìn)。

4 結(jié) 語(yǔ)

本文創(chuàng)新點(diǎn)為針對(duì)數(shù)據(jù)挖掘中的聚類算法，根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行比較分析，有利于人們更容易、更快捷地找到一種適用于特定問(wèn)題及用戶的聚類算法。根據(jù)武警網(wǎng)絡(luò)實(shí)際，結(jié)合項(xiàng)目，提出改進(jìn)型Kmeans算法，取得較好的挖掘?qū)嶒?yàn)結(jié)果。

參 考 文 獻(xiàn)

［1］Han Jiawei，Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)\\[M\\].北京：機(jī)械工業(yè)出版社，2001.

［2］張紅云，劉向東，段曉東，等.數(shù)據(jù)挖掘中聚類算法比較研究\\[J\\].計(jì)算機(jī)應(yīng)用與軟件，2003，20(2):56.

［3］賀玲，吳玲達(dá)，蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述\\[J\\].計(jì)算機(jī)應(yīng)用研究，2007，24(1):1013.

［4］蘇輝貴，傅秀芬，李志清，等.基于數(shù)據(jù)挖掘技術(shù)的智能入侵檢測(cè)模型\\[J\\].微計(jì)算機(jī)信息，2007，23(6)：7476.

［5］徐興元，傅和平，熊中朝.基于數(shù)據(jù)挖掘的入侵檢測(cè)技術(shù)研究\\[J\\].微計(jì)算機(jī)信息，2007，23(9)：7475，122.

［6］張昕，彭宏，鄭啟倫.基于微粒群算法的聚類分析\\[J\\].微電子學(xué)與計(jì)算機(jī)，2006，23(9)：9495.

［7］陳京民.數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘技術(shù)\\[M\\].北京：電子工業(yè)出版社，2002.

［8］Olivia Parr Rud.Data Mining Cookbook:Modeling Data for Marketing，Risk，and Customer Relationship Management\\[M\\].John Wiley Sons，INC.2003.

［9］陳莉平，屈百達(dá).基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法的研究與應(yīng)用\\[J\\].現(xiàn)代電子技術(shù)，2007，30(20):7174.

作者簡(jiǎn)介 田 杰 女，1970年出生，武警工程學(xué)院通信工程系副教授，碩士。研究方向?yàn)橛?jì)算機(jī)應(yīng)用。