粒子群優化的半監督入侵檢測算法

賈志偉, 關忠仁, 趙建芳

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

0 引言

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

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

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

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

對于must-link中的數據集也滿足傳遞的規律,即:

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

當兩數據點 xi,xj滿足cannot-link,xi,xk滿足must-link約束,則

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

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

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

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

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

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

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

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

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

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

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

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

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

2 粒子群優化算法

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

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

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

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

3 粒子群優化的半監督入侵檢測算法(PSO-scid)

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

PSO-scid算法描述:

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

輸出:數據 x∈Xu的數據類型(正常或者異常)

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

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

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

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

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

4 實驗及分析

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

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

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

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

4.1 KDDcup99樣本數據的選取

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

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

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

其中,

4.2 測試結果及分析

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

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

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

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

在實驗中用到的有關參數如表1。

表1 實驗參數表

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

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

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

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

5 結束語

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

[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] 張亮,李敏強.半監督聚類中基于密度的約束擴展方法[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] 宋凌,李枚毅,李孝源.基于粒群優化的K均值算法及其應用[J].計算機工程,2008,34(16):0201-0204.

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