基于粒子群和模糊数学的入侵检测系统的研究

林辉

（渭南师范学院 信息与教育技术中心，陕西 渭南　714000）

基于粒子群和模糊数学的入侵检测系统的研究

林辉

（渭南师范学院 信息与教育技术中心，陕西 渭南714000）

模糊C-均值算法是一种无监督的数据分类方法。基于FCM算法对随机初始值敏感，易陷入局部极致点这个问题，引入粒子群优化算法。粒子群算法的核心思想是让每个粒子根据自身和周围粒子的信息共享，实现全局搜索最优值。收敛速度快，全局搜索能力很强。利用粒子群算法的全局搜索能力，对FCM算法性能进行改进，将粒子群优化算法和FCM算法结合，用KDD99数据集进行测试，实验结果表明，改进算法具有较高检测率和降低误报率。

模糊；聚类；无监督；粒子群；KDD99

聚类分析算法是多元统计分析的重要方法之一，它也是统计模式识别中无监督模式识别的重要学科之一，聚类分析也常叫做无督导学习，希望将数据分为若干子类，在同一类的数据尽量相似，不同类的数据尽量不相似。从技术上划分分，聚类算法可分为硬聚类算法和模糊聚类算法。

1　FCM算法介绍

Zadeh提出的模糊集理论对数据的软化分提供了有利的工具，人们开始用模糊的方法来处理聚类问题，实际中受到普遍欢迎的是基于目标函数的聚类方法，该方法设计简单，解决问题应用范围广，最终可转化为优化问题而用经典的非线性规划理论求解，易于用计算机编程［1］。

2　粒子群算法介绍

粒子群算法产生于对简化的社会模型模拟，它是在鸟群，鱼群和人类社会的行为规律的启发下提出的［2］。它的基本思想是随机初始化一群没有体积没有质量的粒子，将每个粒子视为问题的一个可行解，解的好坏由适应度函数来确定。每个粒子可以在可行解的空间中运动，采用速度参数决定它的方向和距离。通常粒子在追随目前的最优粒子，并经过多次迭代后找到最优解。在每一代的粒子中，粒子将追踪两个极值，一个是粒子现阶段找到的最好解，另一个是整个群体现阶段找到的最优解。假设在一个D维的目标搜索空间中，由c个粒子组成一个群落，其中第i个粒子为一个D维的向量Xi=（xi1，xi2，L，xiD），i=1，2，L，N。第i个粒子的“飞行 ”速度也是一个D维的向量，第i个粒子目前搜索到的最优位置称为个体极值，记为pbest=（pi1，pi2，L，piD），i=1，2，L，N。整个粒子群现阶段搜索到的最优位置为全局极值，记为gbest=（pg1，pg2，L，pgD）。粒子根据如下的公式（1）和（2）来调整自己的速度和位置：

其中c1和c2为加速常数，r1和r2为［0，1］范围内的均匀随机数。式（1）右边由三部分共同组成，第一部分为“惯性”部分，反映了粒子的运动固有属性，代表粒子有维持自己以前速度的趋势；第二部分为“认知”部分，反映了粒子对自身历史经验的回忆（remembrance），代表粒子自己优化；第三部分为“社会（social）”部分，反映了粒子间协作的经验，代表粒子向群体最优值发展，一般取c1=c2=2。i=1，2，Λ，D。vid是粒子的速度，vid∈［-vmax，vmax］，vmax是常数，由用户设定用来限制速度。r1和r2是介于［0，1］之间的随机数。

3　基于粒子群的FCM优化

虽然FCM算法的每步都沿着好的方向前进，但是这种梯度下降的算法是一种局部寻优算法，易陷入局部极小值点。对于数量大时，这种情况更明显，FCM算法所能找到的最优解对和初始值关系很大。而基于群体思想的粒子群算法初始为均匀分布解空间中的若干可能解，具有很好的全局搜索能力，不易陷入局部极值点。利用粒子群算法的优点对FCM算法改进，能减慢局部搜索，增加隶属度矩阵的多样性，使算法在全局范围内找到最优点。

在使用粒子群算法进行优化FCM时，主要包括3部分：1）编码；2）适应度函数的确定；3）如何更新速度和位移公示。

聚类算法的核心步骤是确定聚类中心，所以我们可以选取聚类中心作为种群中的个体。设样本维数为d，聚类的中心数为c，则每个粒子实际上是一个d*c的矩阵。我们让粒子采用实数编码的方式，编码长度为d*c。对FCM，优化的目的就是使得目标函数取得最小值，我们定义FCM目标函数的倒数为适应度函数。速度-位移更新办法。定义粒子xi的领域极值是li，把该极值也作为粒子进化的一个信息来源。在优化的初始阶段，邻域定义为每个粒子自身，随着迭代次数的增加，将邻域范围逐步扩展到包含所有粒子，这样就能避免早熟，更新方法如下：

其中c1和c2的值均为2，r1和r2在（0，1）区间随机取值，ω较大则算法在较大的范围进行搜索，ω较小则算法在较小的范围进行搜索，开始热ω取值0.9，然后线性减小到0.4。

算法的结束条件:

1）最优解对应的目标函数值之差小于给定的阈值的持续迭代次数达到设定值；

2）达到最大迭代次数。

综上所述，基于粒子群的FCM算法步骤为：

1）对算法参数赋值：聚类数目c，粒子种群规模，允许的最大速度c，最大迭代次数，阈值和迭代次数阈值。

2）在属性值的范围内，随机生成初始种群，每个粒子代表各类的聚类中心。

3）求适应值；

4）根据（1）（2）式计算粒子的速度和位移；

5）计算种群中的个体适应值，若满足中止条件，则结束，否则转第四步。

实验：实验采用UCI数据库中著名的数据集Iris、Wine以及BreastCancer作为测试数据进行验证。Iris数据具有5个属性，前4个属性用来对特征进行描述，第5维属性用来说明所属的类别。Wine是来自3个不同品种的葡萄酒化学分析结果记录组成的葡萄酒辨识数据，有178个数据记录，每个记录有13个属性，它的样本可分为3类。不同数据集下的聚类准确率和执行时间如表1所示。

表1　实验结果

可以看出，K均值算法聚类准确率低，聚类结果波动性大，K均值算法对初始聚类中心的选取非常敏感，聚类中心初值不同结构不同，而本文改进后的算法利用了粒子群优秀的全局寻优能力，虽然时间复杂度比K均值稍高，但算法的聚类准确率得到了提高。

4　实验分析

本实验在Matlab环境下实现。采用用KDDCUP99入侵检测数据集作为实验对象。这个数据集是一个在军事网络环境中模拟的广泛的不同类型的数据，是DARPA（美国国防部）委托林肯实验室模拟空军网络环境所获取的原始入侵数据。其中训练数据5百万个连接记录，测试数据集包含了2百万个连接数据。网络入侵检测系统是针对网络上的数据包进行分析，而通常网络上的数据量非常之大，在网络入侵检测中，在对KDD99数据进行分析的时候，由于KDD99数据具有41维数据，其中每一维都有一定的含义，这就使一些方法如数据立方合计、数据块消减、利用编码压缩等方法不方便适用。所以在KDD99中用到的主要是级数消减，即减少或者消除无义数据的维数，常用的方法是采用PCA进行数据的属性约简。

1933年，Hotelling提出了主成分分析（Principle Component Analysis，PCA）方法［3］，PCA是一种将多个变量转换为少数几个不相关的综合指标的统计分析方法，由于实测的参数之间存在一定的相关性，因此有可能用较少数的综合参数分别综合存在于各变量中的各类信息，而综合参数之间彼此不相关，也就是说各个指标代表的信息不重叠。对KDD99数据集的41维属性进行分析，除去第7、8、9、11、14、15、16、17、18、20、21维后的其他属性的贡献率仍可达到99.9%［4］，故将第7、8、9、11、14、15、16、17、18、20、21维属性删除，从而得到将原来数据集的41维属性约简为30维属性。

由于KDD99原始数据是包含混合型属性的数据，它有离散型属性的数据和连续型的特征参数，各参数的量纲也不同，或者虽然量纲相同，但是数量级不同，如果我们直接用原始数据进行运算，会出现大数吃小数的问题，因此在计算之前，应对指标进行标准化处理。

在KDD99数据集中，共有9个离散型特征属性，为每一个特征属性的状态创建一个新的二元变量，用非对称的二元变量编码来表示状态信息。如分别赋予 UDP=（1，0，0），ICMP=（0，0，1），TCP=（0，1，0），该方法优点是可保障每条记录之间的同一离散特征属性之间的距离相等，在计算中彼此不会产生偏差。

由于原始数据量过于庞大，而且其中的入侵数据所占比例多大，和实际的网络环境相差很大，故我们选择部分数据进行测试［5-6］，结果如表2所示。

表2　实验结果

对于上表的实验结果，我们可以看到对于的neptune、Buffer_overflow、ftp_write、Nmap、Sendmail Waremaster Ipsweep 、Imap等入侵数据，算法能够较好地检查出来，但是也有Xterm、Loadmodule入侵的检测效果不是很好，我们估计检测率低的可能由于正常连接记录的数目相对来说太少，还有可能就是某些正常的数据非常接近于入侵数据。这种数据在大数据量的情况下所占的比例是很少的，但是在这里却在正常的数据中占据一定的比例，所以使得误报率较高。

5　结　论

模糊聚类算法是目前广泛使用的一种聚类算法，但是该算法也有它的一些局限性，它对初始值很敏感，且已陷入局部极致点，聚类结果随初始聚类中心的不同而波动，从而导致聚类结构稳定性差，本文提出的算法时将粒子群优化算法引入到模糊聚类算法中。该算法能较好的搜索全局极致点，仿真实验表明，该算法能有效解决聚类算法对初始值敏感和已陷入局部极致点的缺点，具有较好的聚类精度，算法有很强的全局寻优能力，用KDD99数据进行仿真实验，能有效检测出入侵数据。显然这对改进入侵检测系统的性能具有重要意义。

［1］何清.模糊聚类分析理论与应用研究进展［J］.模糊系统与数学，1998，12（2）：89-94.

［2］魏秀业，潘虹侠.粒子群优化及智能故障诊断［D］.北京：国防工业出版社，2010.

［3］黄伟如.基于聚类的入侵检测方法研究［D］.武汉：华中科技大学，2006.

［4］罗敏.基于聚类和支持向量机的网络入侵检测研究［D］.武汉：武汉大学，2003.

［5］左瑞娟，武永华.基于克隆选择的模糊分类规则提取算法［J］.智能系统学报，2007，2（4）：74-77.

［6］刘福荣，高晓智，王常虹，等.基于免疫克隆选择的模糊聚类分析［J］.传感器与维系统，2008，27（3）：26-56.

Research on intrusion detection system based on particle swarm optimization and fuzzy mathematics

LIN Hui
（Center of Information and Education Technology，Weinan Normal University，Weinan 714000，China）

Fuzzy C-means algorithm is an unsupervised classification method.Based on the FCM algorithm for random initial value sensitive，easy to fall into local extreme point of this problem，introduce particle swarm optimization algorithm to FCM. the core idea of particle swarm algorithm is to let each particle according to its own and the surrounding particles of information sharing，to achieve global search optimal value，convergence speed，global search ability is very strong.Using the global search ability of particle swarm optimization，to improve the performance of FCM algorithm.The particle swarm optimization algorithm and FCM algorithm are combined.Test using KDD99 data sets，The experimental results show that the improved algorithm has higher detection rate and lower false positive rate.

fuzzy；clustering；unsupervised；particle swarm；KDD99

TN391

A

1674-6236（2016）14-0024-03

2015-07-28稿件编号：201507184

渭南师范学院科研重点项目（14ykf005）

林 辉（1982—），男，陕西西安人，硕士，工程师。研究方向:网络安全。