基于改进混沌粒子群的聚类检测算法研究

吴有晓

(广东省电信规划设计院有限公司，广东 广州 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－)，男，广东广州人，硕士研究生，二级通信设计师，研究方向为无线网络规划、计算机网络安全、入侵检测等领域。