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

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

中圖分類號：TP274文獻(xiàn)標(biāo)識碼：A文章編號：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年代以來，他的發(fā)展速度很快，是多學(xué)科綜合的產(chǎn)物。雖然目前還沒有一個完整的定義，但這里認(rèn)為：數(shù)據(jù)挖掘就是從海量的數(shù)據(jù)中挖掘出可能有潛在價值的信息的技術(shù)。這些信息是可能有潛在價值的，支持決策，可以有效利用指揮自動化網(wǎng)，為進(jìn)一步研究尋找突破口。

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

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

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

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

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

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

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

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

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

2.1 BIRCH算法

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

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

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

2.2 CURE算法

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

2.3 DBSCAN算法

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

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

2.4 Kpototypes算法

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

2.5 CLARANS算法

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

2.6 CLIQUE算法

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

由于每個方法都有其特點(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ò)入侵檢測系統(tǒng)的構(gòu)建(屬于網(wǎng)絡(luò)用法挖掘范疇)和基于DM技術(shù)的武警網(wǎng)絡(luò)輔助決策系統(tǒng)的構(gòu)建(屬于網(wǎng)絡(luò)內(nèi)容挖掘范疇)。在武警網(wǎng)絡(luò)入侵檢測系統(tǒng)的檢測挖掘算法方面采用廣域網(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é)果。

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

首先對數(shù)據(jù)分析其屬性，選取特征向量，并對各條記錄的特征項(xiàng)數(shù)據(jù)標(biāo)準(zhǔn)化，然后對標(biāo)準(zhǔn)化后的數(shù)據(jù)用Kmeans聚類，通過調(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í)際檢測中還需要對一些參數(shù)進(jìn)行自適應(yīng)的調(diào)整。該過程是用matlab仿真，主要模塊為std_data.m，cluster_size.m，result_show.m及運(yùn)行結(jié)果如圖1所示：

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

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

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

4 結(jié) 語

本文創(chuàng)新點(diǎn)為針對數(shù)據(jù)挖掘中的聚類算法，根據(jù)評價標(biāo)準(zhǔn)進(jì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ù)的智能入侵檢測模型\\[J\\].微計(jì)算機(jī)信息，2007，23(6)：7476.

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

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

［7］陳京民.數(shù)據(jù)倉庫與數(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.

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