基于改進混沌粒子群的聚類檢測算法研究

吳有曉

(廣東省電信規劃設計院有限公司，廣東 廣州 510630)

基于改進混沌粒子群的聚類檢測算法研究

吳有曉

(廣東省電信規劃設計院有限公司，廣東 廣州 510630)

針對入侵檢測系統特征報警聚類質量低、冗余告警的不足，提出基于改進混沌自適應粒子群優化的IDS特征報警聚類方法。該方法結合混沌算法特性和改進粒子群算法自適應慣性權重系數以及對非線性動態學習因子進行改善，引導粒子群在混沌與穩定之間交替波動，保證粒子運動慣性，更利于趨近最優。本方法能夠克服PSO算法的過早收斂、“惰性”反應等缺點，利于聚類中心更能趨向全局最優。實驗結果表明，本文粒子群參數改進算法提高了特征報警聚類質量，具有較高的檢測率和較低的誤報率。

入侵檢測；粒子群優化；混沌；自適應慣性權重；非線性動態學習因子

1 引言

近年來，網絡安全成為人們日益關注的一個問題。就入侵檢測系統（IDS,Intrusion Detection System）而言,它作為當前保障網絡安全運行的有效檢測工具，得到了廣泛的重視及應用，它可以檢測網絡上的攻擊行為，并產生相應的告警信息，提示系統管理人員進行及時有效的處理，避免入侵造成的巨大損失[1,2]。

然而，鑒于網絡入侵檢測系統的技術不夠完善，加之其異構性和自治性的特點，使得產生的報警信息在準確度、詳略程度等方面存在較大的差異，進而致使系統產生大量冗余、可信度較低的報警數據，系統管理人員難以手動分析處理這些數據[3-5]。因此，對于告警數據集進行劃分、整合及精簡，從而提高報警數據的可信度以及降低數據冗余具有重要的意義。

因此，對于網絡中大量的告警不能準確反映網絡的攻擊情況，同時過多的網絡報警冗余致使淹沒有用信息，進而導致IDS效率低下。所以需要一種可靠的方法來降低其報警數據冗余，同時挖掘系統的有用告警信息，從而利于網絡安全管理人員對系統進行有效的維護。

2 相關工作

數據挖掘技術在IDS中受到越來越多的關注，是近年來學者在入侵檢測領域一個研究熱點。尤其在入侵特征報警方面，把數據挖掘、智能算法等相關知識運用到入侵特征分析上，在入侵報警信息的聚類及入侵數據特征的關聯性方面取得了較明顯的研究成果。因此，采用聚類技術處理入侵告警海量數據具有廣泛的研究和應用。

文獻[6]提出基于混沌粒子群優化的IDS告警聚類，文中利用混沌理論，動態更新種群粒子的位置移動，使得粒子群粒子在混沌與穩定之間交替運動，從而加速向最優值靠近，加快收斂過程，雖然混沌系統對粒子的位置產生明顯的影響，但動態學習因子的改變也可以加快收斂速度，跳出局部最優，從而提高全局尋優能力和局部尋優能力。在文獻[7]中，針對K均值算法對初始聚類中心、孤立點和噪聲敏感且容易陷入局部最優解的不足，提出基于PSO的K均值算法。在一定程度上對克服K均值的不足取得了明顯的效果。但只是運用了粒子群的基本固定參數公式，沒有考慮到參數的變化對粒子群的收斂以及跳出局部最優帶來的更高的效率。文獻[8]提出了一種非線性改變粒子群算法中的慣性權重，并將其用于SVM與KPCA中，其實驗表明在SVM參數選擇方面以及WPSO-SVM在入侵檢測系統中，提高了準確度。基于此思路，本文在慣性權重方面也進行了不同條件狀態處理，通過不同的，達到了理想的效果。文獻[9]針對粒子群算法中慣性權重對種群粒子的社會性和認知能力的重要影響，提出自適應慣性權重PSO策略，即SBCAW-PSO，基于正弦函數的混沌映射，并通過Ackley、Hyperellipsoid、Rastrigin等一系列函數來測試改進的PSO，驗證基于正弦的混沌映射在PSO搜索方面具有較高的效率。在文獻[10]中，針對現有大多數PSO算法在處理復雜的多峰函數優化時容易陷入局部最優，該文提出基于聚類的自適應PSO算法，通過K均值聚類操作，動態地把種群劃分構建成變化的子群聚類，同時采用聚類中心附近拓撲分享聚類信息，利用自適應機制來調整所有個體粒子慣性權重，重新評價種群聚類質量。最后通過實驗表明APSO-C在收斂速度方面具有較高的效率，較其它PSO算法有較高的準確率和可靠性。

Cheng等人在2012年提出改進的PSO與映射混沌搜索的方法結合的思想。文中提出了組合動態引導PSO和基于混沌搜索在全局最優（Gbest）與局部最優粒子之間進行搜索。邏輯混沌映射使新產生的種群具有更強的多樣性，通過一系列測試函數測試，該方法較傳統的PSO具有更好的收斂效果。Hu等人在2013年提出了針對時間窗的車輛路由問題的混合混沌粒子群算法，把DCh(tent map)用于改進的算法研究并降低種群的過早收斂，實驗表明改進的混合算法在質量與時間消耗上優于其它的PSO算法[11]。

粒子群算法（particle swarm optimization，PSO）是一種有效的全局尋優算法，最早由美國的Kenedy和Eberhart于1995年提出，與其他進化算法相比，PSO通過個體間的配合與競爭，實現復雜空間的尋優。由于采用“速度-位移”模型避免了繁瑣的遺傳操作，同時，其算法本身特有的記憶可以根據搜索情況動態調整搜索策略，粒子之間具有自我經驗與同伴經驗，極大降低了尋優的迭代次數。

根據Wolpert與Macready在1997年提出的No Free Lunch Theorems，文中將改進參數調整的混沌粒子群算法與K均值聚類算法結合，就調整的參數進行仿真，最后利用KDDCUP99數據集對入侵特征報警數據聚類仿真測試。實驗結果表明，本文提出改進算法在特征報警聚類方面獲得較理想的檢測率和誤報率，進而降低了報警冗余，提高了聚類質量。

3 混沌粒子群算法

本文的混沌粒子群算法采用文獻[6,12]中的實驗算法,它在文獻[12]對混沌蟻群（CAS）算法[13]進行分析改進，同時利用PSO固有的特性優勢，結合兩者的優勢并應用于入侵檢測特征聚類中，進而改善海量數據的聚類效果。其混沌粒子群算法數學模型：

3.1 速度

3.2 標準粒子群算法位置

3.3混沌粒子更新位置

3.4 混沌變量

其中，式（1）為種群中粒子的速度更新，vid(t+1)表示第i個粒子在t+1次迭代中第d維上的速度，為慣性權重，為學習因子。式（2）為粒子的位置更新。式（3）基于式（2）對粒子群中粒子位置更新引入混沌，t表示迭代次數，表示搜索測度，Mi表示粒子i的搜索空間向負方向移動的比例系數（如：ψd=100，Mi=0.4，則表示搜索空間為[-40,40]）。式（4）影響種群粒子的混沌程度，表示粒子混沌變量。rid為第i個粒子的第d維混沌因子（一個小于1的正常數）。

若種群粒子一直處于混沌狀態，使得粒子群處于多樣性，不利于粒子尋優；而長期處于穩定狀態，導致種群粒子陷于局部最優。所以只有在兩者之間交替才能不斷向最優靠近。混沌采用文獻[13]中的混沌算法（Sole等給出的混沌系統[14]），混沌迭代如式（5）。

x=x exp(μ(1-x)) （5）

該算法區別于已有的采用粒子序列替換來對種群粒子進行位置更新，將混沌理論融入PSO種群粒子的更新中。采用混沌的方法使得種群粒子位置更新在混沌與穩定之間交替進行，從而更加利于種群尋優。通過混沌因子調節混沌程度，使得粒子的運動更具合理性，具有較好的全局搜索能力。數據結果顯示在利用混沌理論在對函數尋優時，能夠有效克服種群粒子的過早收斂及早熟現象，及時跳出局部最優，使得函數在求解精度以及最優解的求解能力方面得到了極大的提高[6]。

4 優化混沌粒子群和K-means混合聚類算法設計

4.1 k-means報警聚類描述

報警特征聚類描述：將眾多的入侵報警特征數據進行分類整合，每個類群產生一個報警作為標志，表明網絡正在發生的攻擊行為。IDS特征報警聚類規定：給定一個報警數據集 D={xi，i=1,2,…,n}，將 其 劃 分 為 K 個 聚 類C={C1,C2,…,CK}，且滿足式(6)。

文中通過最小均方誤差（MSE）來劃分聚類（聚類劃分為同一類的限定是使得均方誤差達到最小），如式（7）所示。

其中zj為聚類中心。

4.2 非線性學習因子改善

由于學習因子對種群粒子的速度更新具有重要作用，其c1，c2的值代表了粒子的認知能力和社會性（粒子本身經驗和群體的經驗）。往常的線性調整學習因子取值容易出現粒子早熟的現象，過早收斂于局部極值。陳水利等人通過利用非線性策略來調整學習因子，利用其非線性變化來控制算法的局部和全局搜索并獲得了較理想的效果。在其非線性方法啟發下，結合PSO基本算法（通常c1，c2都設置為常數2，則反映種群粒子對自己和群體經驗信任度相同），本文利用三角函數的非線性動態調整學習因子來控制粒子的局部開拓能力和全局收斂能力。c1和c2的動態取值如下：

其中ρ=1.3為常數（經過測試，ρ的取值在1.0～1.5之間適合），t為當前迭代次數，MaxIter為最大迭代次數，rand()表示區間上均勻分布的隨機數，δ∈[2,10]用于控制隨機數的振幅，β取值為1或0用來表示c1和c2在動態更新是否加入隨機擾動rand()/δ。

由式（10）可知，0＜2β·rand()＜2，0＜2β·rand()/δ＜1，確保c1+c2基本穩定在（0，4）區間內。學習因子c1動態減少同時c2動態增加，對種群粒子速度的更新早期參照個體歷史信息，具有很強的空間開拓能力，到迭代后期則利于粒子相信群體決策，注重社會信息，從而避免陷入局部極值；利于種群最終收斂于一個全局最優解或次優解。

4.3 自適應慣性權重設計

慣性權重ω決定種群中粒子的先前飛行速度對當前速度的影響程度，慣性權重較大時，其全局搜索性強而局部搜索能力弱；反之，慣性權重較小時，則局部搜索能力強而全局搜索性弱。所以，合理地調整慣性權重可以權衡全局性與局部性之間的平衡。因此，動態調整ω值在提高種群尋優、減少迭代次數方面具有重要影響。

本文對數據集進行特征報警聚類時，每個聚類形成以后具有不同的粒子數目。由于粒子本身的能力，在搜索水平上聚類的效果大不相同。由于每個粒子聚類效果最好的粒子之間的平均距離不相同。所以可以通過距離來對聚類進行分類來改善粒子的搜索能力。給出兩個定義：

定義1：聚類種群j用 ||Cj表示；定義 fij為粒子i在聚類j中的適應度。聚類j的平均適應度為定義fi作為粒子i的適應度。則種群的平均適應度表示為,其中，N表示種群數目。

定義2：初始種群粒子的慣性權重的最大值、最小值分別由ωmax、ωmin表示。在達到第t代時，粒子i的慣性權重表示為，這個權重是基于ωmax，ωmin，三者來調整粒子的狀態。也就是說通過三者來產生新的慣性權重，從而調整粒子的速度狀態。

由于在搜索的過程中，處于不同位置的種群粒子具備不同的特征和能力。通過適應度來表示這些不同。這些粒子在不同的位置時，需要強化他們的能力，這種能力就是搜索整體空間的能力。例如，有些粒子處于不利的位置需要逃離這些位置并加速對其它區域的探索；而已經處于有利位置的粒子需要更進一步地深入探索空間來發現更具優勢的位置。本文通過調整慣性權重，基于聚類操作的算法來改善粒子的這種尋優能力。對于每個聚類，處于這個聚類中的粒子具有不同的優勢與劣勢。所以這些聚類的平均適應度不相同。這些不同可以用來評價這些聚類進而為個體粒子調整慣性權重ω。

目的是使得適應度最小。通過聚類的平均適應度與種群的平均適應度來調整慣性權重ω的值：

條件1：aj≥avg：如果滿足此條件說明子群處于不利的位置，處于這個位置的粒子距離最好的位置距離太遠。所以接下來的搜索應當設置并改善全局的搜索能力，避免陷入局部搜索。即增加慣性權重ω值來改善搜索的全局性。

條件2：aj＜avg，如果滿足此條件說明子群位于一個較好的區域。對于這種情況下的子群，通過調整慣性權重ω來減少搜索步長，避免全局的搜索，從而改善局部搜索的能力，防止忽略附近域的最優解。

通過以上分析得知，每個個體可以通過在不同的條件下自適應調整參數，來達到最佳的尋優狀態。

其中粒子i屬于聚類j。

由于慣性權重ω是粒子群算法中對算法效率具有重要影響的可調整參數，ω的值越大，可利用搜索的全局性；反之，可利用搜索的局部性，所以，改變ω為定值的單一模式，有效調整ω能權衡算法的全局與局部之間的搜索能力，有利于種群尋優。

4.4 報警空間定義

告警空間定義引申為實現對IDS報警的聚類，應將報警映射為N維空間上的點集。針對IDS研究中廣泛采用的開源軟件Snort，將其每條報警映射為（AID,Atime，Aproto，AsrcIP, AsrcPort,AdestIP,AdestPort,Amsg,Acontent,Aclasstype）[12]。

定義兩個報警之間的距離為式（13）：

其中，X，Y為報警，XAi為報警X的Ai屬性值。

屬性值取得實數值或字符串時，其距離定義分別如式（14）、式（15）：

其中，a，b為報警的屬性值。

4.5 聚類算法步驟

本文的報警聚類算法將混沌粒子群算法的參數進行改善，并在現存相關文獻在聚類方面研究的基礎上進行了設計，算法流程如圖1。

圖1 改進混沌粒子群報警聚類算法流程圖

本文的混沌粒子群算法是把種群聚類的聚類中心對應到單個粒子，進而利用混沌理論進行聚類中心的混沌操作，從而找到最優的聚類中心，得到最優特征分類結果。具體步驟如下：

a.首先對映射的種群進行初始化，在種群的搜索范圍內隨機生成N個粒子，同時每個粒子對應一組聚類中心。種群粒子的速度、位置初始隨機產生。

b.種群粒子根據隨機聚類中心，利用最近鄰法則分配到各個聚類中。通過式（13）～式（15）計算其SSE值，進而更新更新P_id(i)值與P_gd值。

c.根據式（1）,（8）,（9）或式（1）,（11）,（12），更新粒子的速度，式（3）更新粒子位置，進行混沌搜索，根據式（4）更新粒子群混沌變量。

d.判斷是否滿足終止條件，如果滿足，則記錄P_id和P_gd值并轉至步驟e，退出程序；否則轉至步驟b。

e.根據粒子的數目，聚類的個數k，利用聚類評判標準式（7），進行距離最小選擇，將選擇出的xi添加到相應的Cj中。

5 仿真實驗

5.1 自適應慣性權重仿真

在此本文利用Griewank函數進行測試，該函數是一種典型的多模態函數，具有大量的局部極值，可有效檢驗算法的全局搜索性能。參數設置：LIW,FIW,SINW三種方法中慣性權重的設置均為[0.9，0.4]，即ωstart=0.9，ωend=0.4，c1=c2=2.0。群體規模大小都為40，允許誤差為σ=e-80，優化變量的維數為20，最大迭代次數取1500，最大速度為600。實驗設置運行50次，取50次的平均值作為最終結果，并以函數平均最優值取對數（以10為底）為縱坐標。

通過圖2可知，利用自適應的慣性權重，在粒子的收斂方面明顯比LIW、FIW慣性權重調整方面具有更快的收斂速度，所需的迭代次數也相應有所減少。FIW由于其固定不變的慣性權重，不能較好地協調全局搜索能力和局部搜索能力[15]。本文的自適應慣性權重通過兩種不同的狀態，來調整慣性權重ω的值，且容易跳出局部最優，在收斂速度和求解精度上比另外兩種效果好。

圖2 Griewank函數

5.2 非線性動態學習因子擾動仿真

利用相關標準測試函數進行PSO算法測試，ω線性遞減，優化變量的維數為20，最大迭代次數為50。區分加擾動與未加擾動的學習因子的變化。

圖3 c1與c2隨進化代數動態變化軌跡

通過圖3非線性動態變化學習因子動態變化軌跡可以得到，加上隨機擾動的學習因子，具有較好的波動，對粒子群算法尋優以及跳出局部最優，較快達到收斂，并獲得較好的全局最優具有較大的影響。

5.3 報警聚類效果測試

文中攻擊場景采用文獻[12]所設計的攻擊環境，同時基于前文的告警聚類，利用“行為+位置+目的”模式攻擊行為的表述，構建攻擊場景。為驗證不同參數調整的聚類效果，文中采用通用的KDDCUP網絡數據集進行仿真實驗。混沌粒子群參數設置：ω=0.7298，c1=c2=1.4962，MaxIter=1500，r(i，d)=0.5+0.005rand()，N=20，Cid=0.999，ψd為各自搜索空間長度，Mi=0.5，粒子初始值為ψd·Mi·(2rand()-1)。本文首先通過混沌粒子群算法與非線性動態學習因子結合仿真測試，文中用CCPSO-KM表示，其參數設置：ω=0.7298，MaxIter= 1500，r(i，d)=0.5+0.005rand()，N=20，Cid=0.999，ψd為各自搜索空間長度，Mi=0.5，粒子初始值為ψd·Mi·(2rand()-1)，c1、c2的改變按式（8），式（9）。再者，與自適應慣性權重結合仿真測試，文中用ACPSO-KM表示，其參數設置：c1=c2=1.4962，MaxIter=1500，r(i，d)=0.5+0.005rand()，N=20,Cid=0.999,為各自搜索空間長度，Mi=0.5，粒子初始值為ψd·Mi·(2rand()-1)，ω慣性權重按式（11），式（12）不同條件更新其值。通過統計如表1所示。

表1 報警聚類算法結果比較

通過對比表1結果：本文在基于混沌粒子群對其粒子速度更新中參數調整的不同策略，其聚類效果明顯高于單一的混沌粒子群聚類。在對學習因子利用三角函數進行動態調整的CCPSO-KM算法中，其平均報警檢測率為83.34%，高于混沌聚類算法的80.36%，同時平均誤報率為1.04%，低于混沌聚類算法的誤報率。在自調整慣性權重的混沌聚類算法中，其平均報警檢測率為83.66%，高于CPSO-KM聚類算法檢測率，而平均誤報率為1.01%，低于混沌聚類算法的1.35%。總的來看，兩種參數改進，對提高檢測率，降低誤報率具有明顯的效果，同時對比發現，針對慣性權重的改進影響比學習因子的效果略明顯。

6 結束語

在網絡入侵檢測復雜環境中，對海量告警數據進行劃分、整合、精簡，以減少告警冗余，降低誤報率具有重要現實意義。為提高IDS的入侵特征的聚類質量，減少冗余，降低誤報率與虛報率，本文提出一種基于改進混沌粒子群優化的IDS特征報警聚類算法，利用混沌的遍歷性和粒子群收斂快的特性，同時結合非線性動態學習因子和自適應慣性權重動態更新粒子群參數，動態引導K均值算法的聚類中心更新迭代，從而獲得較好的聚類效果，避免聚類中心選擇對最終聚類結果的影響，與現存混沌粒子群算法相比，本文提出參數調整策略更好地跳出局部最優，提高了種群全局尋優能力。最后通過對多峰函數對非線性動態學習因子和自適應慣性權重進行仿真，利用KDDCUP99數據集進行實驗測試。實驗表明，非線性動態學習因子和自適應慣性權重在迭代擾動方面具有明顯效果，更容易跳出局部最優，對數據集進行聚類，具有更高的檢測率和較低的誤報率。

[1]龔儉，吳樺，楊望．計算機網絡安全導論[M]．南京：東南大學，200 7．

[2]DOROTHY E，DENNING．An intrusion detection model[J]．IEEE Transactions on Software Engineering，1987，13(2):222-232．

[3]李家春，李之棠．分布式入侵告警關聯分析[J]．計算機研究與發展，200 4，41(11):19 19-19 2 3．

[4]NINGP，CUI Y，REEVES D S，et al．Techniques and tools for analyzing intrusion alerts[J]．ACM Transactions on Information and System Security，2004，7(2):2 74-3 18．

[5]DEBAR H，WESPI A．Aggregation and correlation of intrusion

Detection alerts[A]．Proceedings of the 4th International Symposium on Recent Advances in Intrusion Detection[C]．Davis，CA，USA，2001．8 5-10 3．

[6]XU X B，ZHENG K F，LI D，et al．A new chaos-particle swarm optimization algorithm[J]．Journal on Communications，2012，3 3(1):2 4-3 0．

[7]傅濤，孫文靜．PSO-based K-means算法及其在網絡入侵檢測中的應用[J]．計算機科學，2013，40(11):13 7-13 9．

[8]Lia L，Liub K．An Intrusion Detection Method Based on WPSOSVM and KPCA[J]．Journal of Information&Computational Science，2014，11:5(2014)140 3-1410．

[9]Cheng Y H，Kuo C N．SBCAW-PSO:A Sine-Based Chaotic Adaptive Inertia Weight Particle Swarm Optimization[C]//Proceedings of the International MultiConference of Engineers and Computer Scientists．2014，1．

[10]Liang X，Li W，Zhang Y，et al．An adaptive particle swarm optimization method based on clustering[J]．Soft Computing，2014:1-18．

[11]Kr mer P，Zelinka I，Sn á el V．Behaviour of pseudo-random and chaotic sources of stochasticity in nature-inspired optimization methods [J]．Soft Computing，2014，18(4):6 19-6 2 9．

[12]胥小波，蔣琴琴，鄭康鋒，等．基于混沌粒子群的ID S告警聚類算法[J]．通信學報，2013，3 4(3):10 5-110．

[13]Li L，Yang Y，Peng H，et al．An optimization method inspired by chaotic ant behavior[J]．International Journal of Bifurcation and Chaos，200 6，16(0 8):2 3 51-2 3 6 4．

[14]Sol é RV，Miramontes O，Goodwin B C．Oscillations and chaos in ant societies[J]．Journal of theoretical Biology，19 9 3，16 1(3):3 43-3 57．

[15]李麗，牛奔．粒子群優化算法[M]．北京：冶金工業出版社，200 9.

【Abstract】As a computational tool,calculator is used widely.This paper designs a calculator based on Swing and Action event handling mechanism.It is helpful to learn Java programming,and especially has guiding role for Java Programming.

【Keywords】calculator;Swing;Java

Clustering Algorithm Based on Novel Chaotic Particle Swarm Optimization

Wu Youxiao
(Guangdong Planning and Designing Institute of Telecommunications Co.Ltd.,Guangzhou 510630,Guangdong)

Aiming at the the low quality of feature clustering and excessive redundant alarms in IDS,an IDS alerts clustering algorithm based on novel chaotic particle swarm optimization is proposed.It combines the characteristics of chaotic PSO algorithms, adaptive inertia weight coefficient,and non-linear dynamic learning factor,so as to make particles move between the state of chaos and stable.It guarantees the particle motion inertia,and approaches the optimal value.It also can overcome the problems of premature convergence and"inert"reaction of PSO algorithm,and help the center of cluster to find the global optimal solution.The experiment results show that the improvement of particle swarm parameters improves the quality of feature clustering in IDS alarm,and has higher detection rate and lower false detection rate.

IDS;particle swarm optimization;chaos;adaptive inertia weight;non-linear dynamic learning factor

（上接第6 3頁）

Design and Implementation of Calculator Based on Java Swing

Yang Jianqiang Li Miaozai
（Hebi Polytechnic，Hebi 458030，Henan）

TP393

A

1008-6609(2016)10-0073-06

吳有曉(19 8 7－)，男，廣東廣州人，碩士研究生，二級通信設計師，研究方向為無線網絡規劃、計算機網絡安全、入侵檢測等領域。