賈志偉, 關忠仁, 趙建芳

(1.成都信息工程學院計算機學院,四川成都610225;2.成都信息工程學院信息中心,四川成都610225;3.江南大學物聯(lián)網(wǎng)工程學院,江蘇無錫214000)

0 引言

聚類分析根據(jù)在數(shù)據(jù)中發(fā)現(xiàn)的描述對象及其關系的信息,將數(shù)據(jù)對象分組。傳統(tǒng)的聚類算法通常采用無監(jiān)督的學習方式,近年,隨著研究的深入,人們不斷認識到先驗信息的重要性。如何有效利用先驗信息改善無監(jiān)督聚類算法的性能,成為機器領域的一個研究熱點,所提出的算法稱為半監(jiān)督聚類?，F(xiàn)有的半監(jiān)督聚類算法大致可分為3類:(1)基于約束的方法(Constraint-based Semi-supervised Clustering Method,CBSSC)[1-2],CBSSC利用成對約束先驗信息來指導最優(yōu)聚類的搜索過程;(2)基于距離的方法(Distance Based Semi-supervised Clustering Method,DBSSC)[3-4],DBSSC首先利用先驗信息訓練相似性距離測度,使之盡量滿足所給的先驗信息,再使用基于距離的方法聚類;(3)同時集成約束和距離的方法(Constraint and Based Semi-supervised Method,CDBSSC)[5]。

入侵檢測[6]是一種主動的網(wǎng)絡安全技術,是繼傳統(tǒng)安全保護措施后一種新的安全技術。其目的是對保護的系統(tǒng)進行安全審計、監(jiān)控、識別攻擊以及及時采取措施。目前入侵檢測技術大多是基于監(jiān)督學習和無監(jiān)督學習的。基于無監(jiān)督學習的入侵檢測算法根據(jù)數(shù)據(jù)間的相似性進行分組,其檢測精度較低,不需要有標識數(shù)據(jù);基于有監(jiān)督學習的入侵檢測算法的檢測率高,但要求的有標識數(shù)據(jù)可能不能完全反應數(shù)據(jù)集的分布情況,因此不能有效的檢測出未知數(shù)據(jù)?，F(xiàn)實中,獲得少量的標記信息是可能的,如何利用這些少量的標記信息指導半監(jiān)督學習成為關注的熱點。由此引入了基于半監(jiān)督的學習入侵檢測算法[8]。

采用基于約束的半監(jiān)督聚類方法,利用用戶給出約束條件引導聚類過程以此得到優(yōu)化的聚類結(jié)果。文中,成對約束信息分為兩部分[9]:(1)must-link,滿足must-link的數(shù)據(jù)必須在一個簇中;(2)cannot-link,對滿足cannotlink約束的數(shù)據(jù)不能在同一個簇中,否則就違反約束。對應的集合為以及

在半監(jiān)督聚類中,通過對約束信息進行擴展可以很大程度提高算法的聚類效果。通過人為的標記或者搜索開銷很大,因此,對已有的成對約束信息進行擴展成為一個理想的方式。在成對約束中,數(shù)據(jù)是滿足對稱關系的,可以表述為:

對于must-link中的數(shù)據(jù)集也滿足傳遞的規(guī)律,即:

但是對于滿足cannot-link的約束不能使用傳遞的規(guī)律。

當兩數(shù)據(jù)點 xi,xj滿足cannot-link,xi,xk滿足must-link約束,則

利用上述法則對初始成對約束進行調(diào)整,可以一定程度增加約束的量。

1 對約束進行擴展改進的算法(DCEM)

當在約束條件很少的情況下,利用上述方式的擴展效果是非常有限的,為了能更多的挖掘潛在的約束,可以將數(shù)據(jù)集結(jié)構信息以某種形式引入基于約束的聚類方法中,取得更好的聚類效果,為此提出了一種新的約束擴展算法(Density-based Constraint Expansion Method)約束擴展的思想是:根據(jù)約束中兩個樣本點間的關系,計算與其他樣本點的基于密度的圖形相似度[10],尋找最相似的點(文中采用文獻[11]“連接核”方法),指定這些點之間的must-link和cannot-link關系,添加新的約束條件,擴展已有的約束集。擴展后將產(chǎn)生更多的約束條件,而新增的約束由基于密度的距離計算得到,可以將數(shù)據(jù)集空間分布信息引入聚類方法,可獲得更好的聚類效果。文獻[12]提出了各種基于密度的距離度量,用于半監(jiān)督和無監(jiān)督學習。

在“連接核”方法中,定義一種密度敏感的基于路徑的距離,p表示一條長度為路徑,路徑上各邊表示為為兩點間所有路徑的集合。

定義路徑p為兩點間基于路徑p的相似度為路徑上所有邊權重的最小值:

定義邊(i,j)基于路徑的距離權重為點i與點j之間所有路徑的基于路徑的相似度的最大值:

下面給出基于密度的約束擴展算法(DCEM)描述:

輸出:擴展的must-link約束集M+,擴展的cannot-link約束集 C+

步驟1:根據(jù)樣本構造各點的圖形G,有式(6)、(7)計算樣本點間基于密度的圖形相似度矩陣 W={wi,j},對約束集初始化為 M+=M,C+=C;

步驟2:對M+和C+中的約束點利用式(2)～(5)根據(jù)約束的傳遞規(guī)則進行傳遞擴展。

步驟3:對 M+中的任一個約束(xi,xj),求出 xi,xj的k最近鄰點記為

步驟4:對Xi中的任一點xd(d為其在數(shù)據(jù)集中的下標),如果 wd,j≤wi,j,則擴展 M+為 M+,同樣的擴展 Xj中的點。

步驟5:重復步驟2～4直至 M+和C+集合不在變化,算法結(jié)束,得最終擴展出的M+,C+。

2 粒子群優(yōu)化算法

粒子群優(yōu)化算法(PSO)[13]最早是由Kennedy和Eberhart等人于1995年提出的一種新的群體智能進化計算算法,算法源于對鳥群捕食的行為研究而提出的一種全局優(yōu)化搜索算法[14-15],根據(jù)對環(huán)境的適應度將群體中的個體移動到好的區(qū)域,然而不對個體使用演化算子,而是將每個個體看作D維搜索空間中的一個沒有體積的粒子,所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應值(fitness value)。在搜索空間中以一定的速度飛行。每個粒子按照下列公式調(diào)整:

式中 Vi={vi1,vi2,…,vid}表示微粒i的飛行速度,Pi={pi1,pi2,…,pid}表示微粒 i到達的最好的位置,Pg表示群體所有粒子到達的最好位置,w為慣性權重,通常取0.2到0.9,c1和c2為加速常數(shù),通常取2。

由于PSO算法類似其他的智能算法會出現(xiàn)收斂速度慢或“早熟”的現(xiàn)象,出現(xiàn)了很多改進的算法[16-17],其中全面學習粒子群算法(CLPSO)[18]通過對所有粒子的歷史最優(yōu)值以一種概率的形式進行更新,為此對式(8)進行修改為:

f(i)表示從所有粒子的歷史最優(yōu)值中依照一定的概率選中某個粒子的歷史最優(yōu)值,從而避免了出現(xiàn)早熟的的現(xiàn)象[19]。

3 粒子群優(yōu)化的半監(jiān)督入侵檢測算法(PSO-scid)

網(wǎng)絡環(huán)境中,可以獲得少量的監(jiān)督信息,大量存在的是無標識數(shù)據(jù),為了充分利用少量的監(jiān)督信息,提高算法的性能,提出了一種新的入侵檢測算法。算法的思想是:利用改進成對約束信息對數(shù)據(jù)集進行擴展獲得更多的約束信息,以此指導數(shù)據(jù)集進行初聚類,對初聚類后仍未識別的數(shù)據(jù)利用粒子群k均值算法進行聚類,檢測網(wǎng)絡數(shù)據(jù)中是否存在入侵行為。

PSO-scid算法描述:

輸入:未標示數(shù)據(jù)集 Xu={xi},must-link約束集 M,cannot-link約束集 C,數(shù)據(jù)集 X=Xu∪(M+C),閥值W=15,K=60;

輸出:數(shù)據(jù) x∈Xu的數(shù)據(jù)類型(正?；蛘弋惓?

步驟1:利用算法DCEM在數(shù)據(jù)集X上對已有的成對約束信息進行擴展得出擴展后的M+,C+點集,同時得出新的未標示數(shù)據(jù)集X′u。

步驟2:在得出的擴展約束集中對滿足cannot-link約束的 L個M集(簇),求出這 L個約束集的聚類中心uL,計算各簇的最大半徑RL。

步驟3:對于 x∈X′u計算x與各聚類中心uL的距離若R≥r,則將 x分配給聚類CL,否則將 x分配給Cu。

步驟4:對于聚類Cu中的數(shù)據(jù),將其均分為K個子集,然后對Cu中的數(shù)據(jù)使用粒子群優(yōu)化算法進行優(yōu)化,得出K個聚類中心Oj。

步驟5:對于Cu中的任一數(shù)據(jù)x將其分配到距離x最近的類中心Oj(j=1,2,…,k),直到Cu中未標記數(shù)據(jù)分配完,得到 k個簇Cj(j=1,2,…,k)對于聚類后的K 個簇Ci(i=1,2,…,k+L),若Ci.num ＜W,即小于閥值所在簇的數(shù)據(jù)為異常數(shù)據(jù),否則為正常,直到所有的數(shù)據(jù)標記完畢。

4 實驗及分析

半監(jiān)督聚類應用到入侵檢測技術上是基于兩個假設:

(1)數(shù)據(jù)集中正常數(shù)據(jù)的數(shù)目遠比異常數(shù)據(jù)的個數(shù)多;

(2)異常數(shù)據(jù)和正常數(shù)據(jù)本質(zhì)上是不同的,某些屬性的取值明顯偏離正常的取值范圍。

根據(jù)這兩個假設可以從聚類后簇的大小檢測異常,攻擊行為。一般認為大簇是正常的數(shù)據(jù)集,小簇為異常數(shù)據(jù)集。

4.1 KDDcup99樣本數(shù)據(jù)的選取

為了評價改進算法對異常數(shù)據(jù)檢測的效果,選擇KDDcup99數(shù)據(jù)集[20]作為訓練和檢驗數(shù)據(jù),KDDcup99數(shù)據(jù)集的原始數(shù)據(jù)來自DARPA入侵檢測評估項目,網(wǎng)絡中加了很多模擬的攻擊,該數(shù)據(jù)集是入侵檢測領域使用廣泛的數(shù)據(jù)集。

實驗數(shù)據(jù)中包含4種主要的攻擊類型:(1)DOS拒絕服務的攻擊;(2)U2R對本地超級用戶權限的未授權的訪問;(3)Probe各種端口掃描和漏洞掃描 ;(4)R2L遠程權限獲取。

因為數(shù)據(jù)集的記錄屬性間存在差異,且可能存在單位使用維度不同,為了消除這些差異對聚類效果的影響,必須對數(shù)據(jù)進行歸一出來,也就是將原來的數(shù)據(jù)從一個空間轉(zhuǎn)化為標準化的空間,對一個n×k矩陣,其標準化如下:

其中,

4.2 測試結(jié)果及分析

KDD原始數(shù)據(jù)集的記錄數(shù)目很大,為了進行驗證,取6組數(shù)據(jù)集樣本,每組有10000多條數(shù)據(jù),其中異常數(shù)據(jù)位565條,正常數(shù)據(jù)所占比例大于99%,前4組作為訓練樣本結(jié)果去均值,后2組作為測試樣本,測試時去1%的數(shù)據(jù)進行添加約束信息,添加后測試集中包含了20多種已知攻擊類型和4種未知攻擊類型。

入侵檢測算法通過檢測率(DR)和誤報率(FPR)檢測算法的性能,這兩個指標能夠很好的檢測算法的檢測效果,分別定義如下:

DR=檢測到的入侵記錄數(shù)/入侵樣本總數(shù);

FPR=被誤報為入侵的正常記錄數(shù)/正常樣本數(shù)

在實驗中用到的有關參數(shù)如表1。

表1 實驗參數(shù)表

聚類數(shù)K和閥值M 的大小和聚類效果直接相關,只能通過試探性的實驗獲得K,M 的取值,表2為選取不同K,M值時入侵檢測算法的檢測效果,通過實驗發(fā)現(xiàn)試探性的選擇,當K=60,M=15時算法的整體效果最好。

表2 不同K,M值時入侵檢測算法效果

表3 PSO-scid與其他檢測算法檢測效果比較

從表3可知PSO-scid算法在對已知攻擊的檢測上明顯優(yōu)于PSO-kmeans[21]和SAID[22],在未知攻擊的檢測上相對于其他算法有所的提高,同時在誤檢率上也有所改善,因此總體上文中的算法改進一定程度上提升了入侵檢測算法的檢測性能。

5 結(jié)束語

將約束信息引入到粒子群的K均值算法中,并將改進后的算法應用到入侵檢測中,提出了PSO-scid算法,實驗表明該算法在檢測率和誤檢率上相對于其他基于聚類的入侵檢測算法都有所提高,因此算法充分利用了監(jiān)督信息進行聚類,同時增加了粒子群算法的全局搜索能力,從而提升了算法的性能。

[1] Wagastaff K,cardie C,Roger S,Schoredl S.Consrtrained K-meansclustering with background knowledge.In:Brodley CE,Danyluk AP,eds.Proc.of the 18th Int'l Conf.On Machine learning[M].Williamstown:Morgan kaufman Publishers,2001:577-584.

[2] Basus,banerjee A,Mooney RJ.semi-Supervised clustering by seeding.In:Sammut C,Hoffman AG,eds.Proc.of the 19th Int'l conf.onMachine Learning[M].sydney:Morgan Publisgers,2002:19-26.

[3] Bar-Hillel A,Hertz T,Shental N,weinshall D.learning distance functions using equivalence relations.In:Fawcett T,Mishara N,eds,Proc.of the 20th Int'l Conf.on Machine learning[M].washington:Morgan kanfman Publishers,2003:11-18.

[4] Xing EP,Ng Ay,jordan MI,Russell S.Distance metric learning with application side-information.In:Becher S,Thrun S,obermayer K,eds,Proc,of the 16th annual Conf,On Neural Information Processing System[M].Cambridge:MTI Press,2003:505-512.

[5] Bilenko M,Basus S,Mooney RJ.Intergrating Constrains and metric learning in semi-supervised clustering.In:Brodley CE,ed.Proc.of the 21st Int'l conf on Machine learning[M].New York:ACM Press,2004:81-88.

[6] Denning D E.Anintrusiondeteetionmodel[J].IEEETrans.OnSoftwareEngineering,1987,13(2):222-232.

[7] PORTNOY L,ESKIN E,STOLFO S.Intrusion detectionwith unlabeled data using clustering[A].Proceedings of ACM CSS Workshop on Data Mining Applied to Security[C],2001.

[8] BASU S,BANERJEE A,MOONEY R.Semi-supervised clustering by seeding[A].Proceedings of the 19th International Conference on Machine Learning[C],2002:19-26.

[9] A Demiriz,KP Bennett,MJ Embrechts.Semi-supervised clustering using genetic algorithm[J].Artificial neural network in engineering.1999:809-814.

[10] 張亮,李敏強.半監(jiān)督聚類中基于密度的約束擴展方法[J].計算機工程,2008,34(10):0013-0015.

[11] Fischer B,Roth V,Buhmann J M.Clustering with the Connectivity Kernel[C]//Proceedings of the NIPS.Cambridge,MA,USA:MIT Press,2004.

[12] Chang Hong,Yeung D Y.Locally Linear Metric Adaptation withApplication to Semi-supervised Clustering and Image Retrieval[J].Pattern Recognition,2006,39(7):1253-1264.

[13] Kennedy J,Eberhart R C,Shi Y.Swarm Intelligence[M].SanFrancisco:Morga Kaufman Publisher,2001.

[14] Kennedy J,EberhartR C.Swam intelligence[M].San Francisca:Morgan Kaufmann Publishers,2000.

[15] ParsopoulosK E,VrahatisM N.Recent approach to global optimization problem through particle swarm optimization[J].Natural Computing,2002,1(2):235-25.

[16] Mendes R,Kennedy J,Neves J.The fully informed particle swarm:Simpler,maybe better[J].IEEE Trans Evol Comput,2004,8(6):204-210.

[17] 周龍甫,師奕兵,張偉.擁有領導機制的改進粒子群算法[J].控制與決策,2010,25(10):1463-1468.

[18] Liang J J,Qin A K,Suganthan P N,et al.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Trans Evol Comput,2006,10(3):281-294.

[19] Lin C,Feng Q Y.The Standard Particle Swarm Optimization Algorithm Convergence Analysis and Parame-ter Selection[C]//Proceedings of the 3th International Conference on Natural Computation.USA:IEEE Computer Society,2007:823-826.

[20] The UCIKDD Archive.KDD99 cup dataset[EB/OL].http://kdd.ics.uc.i edu/databases/kddcup99/kddcup99.htm.l.2007-10-10.

[21] 宋凌,李枚毅,李孝源.基于粒群優(yōu)化的K均值算法及其應用[J].計算機工程,2008,34(16):0201-0204.

[22] 俞研,黃皓.一種半聚類的異常入侵檢測算法[J].計算機應用,2006,26(7):1640-1642.