基于改进差分进化的K均值聚类算法在入侵检测中的研究

王　广，张晓明，徐日华

(1.北京化工大学，北京 100029；2.北京石油化工学院，北京 102617)



基于改进差分进化的K均值聚类算法在入侵检测中的研究

王广1，2，张晓明1，徐日华1，2

(1.北京化工大学，北京 100029；2.北京石油化工学院，北京 102617)

针对K均值算法对初始聚类中心需要人为设定、对聚类中心敏感并且极易陷入局部最优的缺陷，用改进的DE算法对K均值算法进行优化。在DE算法中，采用动态交叉参数CR与缩放参数F，有效地平衡了DE算法的全局寻优能力与收敛速度二者的矛盾；利用混沌的随机性完成DE算法的种群初始化，利用其遍历性在DE进化后期的最优解附近进行混沌搜索，有效地提高了DE算法的全局寻优能力。最后，使用KDD99数据集对CDE-K均值算法进行验证，实验结果表明，CDE-K均值算法具有较好的聚类能力，在检验效果方面表现优秀。

入侵检测；K均值算法；混沌搜索；DE算法

网络安全已成为全社会性问题。迅速、有效地发掘各种网络攻击行为，保障网络系统和资源的安全，对国家安全和人民权益有着重大的意义[1]。K均值算法是最常用的聚类算法之一，在入侵检测(IDS)研究中有着广泛的应用[2]。但是此算法有两方面的缺陷：一是该算法受初始聚类中心的影响较大，聚类结果很难确定；二是收敛性能较弱，不易获取全局最优解。前人在研究K均值应用于IDS时，对K均值算法做了很多种优化：模拟退火算法对K均值聚类算法的优化[3]；粒子群算法对K均值聚类算法的优化[4]；人工鱼群算法对K均值聚类算法的优化[5]。

差分进化算法(DE算法)是20世纪90年代提出的一种新的进化算法。DE算法全局搜索能力比较优秀，经过这些年的研究，该算法已经成功地应用在很多领域[6-8]。但该算法也存在着不足：DE进化后期很可能跳不出局部最优解的范围；控制参数的设置对差分进化算法的影响很大。

基于改进差分进化的K均值聚类算法(CDE-K均值聚类算法)，笔者用改进的DE算法对K均值算法进行优化。有效地提高了DE算法的全局寻优能力。

1　CDE-KM聚类算法

1.1混沌

选用的Logistic混沌方程为[9-11]：

(1)

(1)利用混沌的随机性初始化DE算法：令tk的初始值分别取m个[0，1]的混沌数，产生相应的向量tk+1=(t1，k+1，…，tj，k+1，…，tm，k+1)，各分量表示为：

(2)

其中，j=1，2，…，m，k=1，2，…，N-1。将产生的混沌变量映射到初始种群个体的分量中：

(3)

(2)DE算法进化后期，在其最优解Xb正反两方向上搜索寻优：

(4)

式中，α为调节参数。

(5)

其中，β∈rand(0，1)。

1.2DE算法原理

DE算法主要包括变异、交叉和选择3大操作[9-10]；设N为种群规模的大小，D为个体的维数，tmax为迭代上限，X0表示初始种群：

(6)

变异操作为：

(7)

其中：r1，r2，r3∈{1，2，…，N}，且r1≠r2≠r3；t是当前代数；F是缩放参数，笔者所用的是一种动态的缩放参数F：

(8)

式中：Fmax=0.9；Fmin=0.4；tmax为迭代上限。

交叉操作为：

(9)

其中：j=1，2，…，D；rand()∈[0， 1]；CR为交叉参数，笔者所用到的是一种动态的指数递增交叉参数：

(10)

其中：a=30；b=3；CRmin=0.1;CRmax=0.9。

(3)选择操作为：

(11)

1.3k均值聚类算法

K均值聚类算法描述如下：

(1)随机选定K个初始聚类中心；

(2)计算数据点与各聚类中心距离的大小，依据数据点与各中心点距离的大小进行聚类。

(3)计算聚类准则函数：

(4)判断聚类准则函数是否收敛，若收敛停止并输出聚类结果；否则，重新计算K个聚类中心，返回(2)重新执行，直至收敛。

1.4基于CDE-K均值聚类算法

CED-K均值算法是对个体的聚类中心进行实数编码，假设初始聚类中心的数目为K，数据维数为d，每个个体就是由K个聚类中心组成，且每个聚类中心是d维的向量，编码方式如下：

X0i(ci1，ci2，…，ciK)(i=1，2，3，…，N)(12)

采用K均值聚类算法中的类内距离作为适应度函数：

(13)

其中：x为聚类中的数据样本；mi为聚类中心。

CDE-K均值聚类算法的整体思路是：用改进后的DE算法对K均值算法的初始聚类中心进行优化选择，然后用选择的聚类中心生成K个聚类结果。CDE-K均值聚类算法的具体流程如下：

(1)读取数据；

(2)通过CED-K均值算法确定K个初始聚类中心：

①设种群规模N、种群进化代数t、混沌控制参数μ以及混沌搜索次数k。

②混沌初始化种群。

③对初始种群评估个体适应度值。找出适应度最优的Xb;记录Xb的适应度Fb；置t=1。

⑥重复步骤②～⑤，直到最大迭代次数。

⑦在DE算法的Xb附近进行混沌搜索操作，根据式(1)、式(2)、式(3)，进而得到Xk。

⑧找出Xk中适应度最好的个体Xkb，若好于f(xkb)优于Fb，令Xb=Xkb，Fb=f(Xkb)，输出Xb和Fb。

(3)计算每个数据点xi与初始聚类中心Zk(I)的距离D(xi，Zk(I))。

(4)满足D(xi，Zk(I))=min{D(xi，Zi(I))}，则有则xi∈Ck。

(5)计算新的Zk(I)和

(6)判断是不是|Jc(I)-Jc(I-1)|<ξ，如果是，算法终止并输出结果；否则，I=I+1，重新计算K个聚类中心，跳转③重新执行，直到|Jc(I)-Jc(I-1)|<ξ，输出结果。

CDE-K均值聚类算法流程如图1所示。

2　实验结果

2.1实验数据描述与处理

为评价CDE-K均值聚类算法在入侵检测上的测试效果，选用KDD99数据集对CDE-K均值聚类算法进行实验。此数据集过大，一般选用KDD99的10%训练集，其每条记录都有41个特征属性，此外还有最后的标记(label)，其主要4大类攻击分别是Dos、Probe、U2R和R2L[12]。41个特征属性中除了数值属性外，还包含了3种符号属性，所以，需要对这3种符号属性进行符号转换为数值的处理，然后再对转换后的数据进行归一化处理，具体方式如下：

(13)

其中，yij_max和yij_min分别表示属性j的最大值和最小值。

通过降低数据维数可以减少算法所用的时间，笔者采用PCA降维法，在保证检测精度的基础上对数据集进行降维处理，并选取前12个主成分作为处理结果[13]。

2.2结果与分析

分别用K-均值、PCA降维后的K-均值、CDE-K-均值和PCA降维后的CDE-K-均值聚类算法，在检测率、误检率和检测时间3个方面得出各子集的检测结果并进行比较。训练子集与测试子集的选取如表1所示。

表1　训练与测试子集

分别从检测率、误报率、检测时间3个方面进行综合分析。结果如图2、图3所示。

从图2和3中可以看出，经过PCA降维后聚类算法在检测率和误检率上与没有经过PCA降维的结果相差不大，基本上相似，这也验证了基于PCA特征降维后的数据检测，不仅能够降低运算时间上的开销，同时还很好地维持了算法的检测精度和准确率。经过CDE算法改进后的K均值算法，比K-均值聚类算法的检测率提高了约20%，误检率降低了30%左右，检测系统的检测效果得到了大幅度提升。

4种攻击类型的检测率如表2所示，同时与GA-K均值、PSO-K均值应用于入侵检测的结果进行了比较[5]。

表2　4种攻击类型的检测率结果

从表2可知，笔者提出的算法比文献[5]中所述的2种检测方法的效果更佳，其平均检测率为89.41%，对比结果表明，通过CDE-K均值聚类算法找到的最优初始聚类中心和K值，可以克服传统K均值聚类算法存在的缺陷，进一步提高网络入侵检测的能力。

3　结论

针对K均值算法对初始聚类中心需要人为设定，对聚类中心敏感并且极易陷入局部最优的缺陷，提出一种改进的DE算法对K均值算法进行优化。实验结果表明，CDE-K均值聚类算法较好地改进了传统K-均值算法，提升了网络入侵的检测能力，降低了网络入侵检测时间，具有较佳的检测能力。

[1]肖立中，刘云翔，陈丽琼.基于改进粒子群的加速K均值算法在入侵检测中的研究[J].系统仿真学报，2014，26(8):1652-1657.

[2]Saeed Shahrivari， Saeed Jalili. Single-pass andlinear-timek-均值 clustering based on Map Reduce[J] . Information Systems， 2016，60:1-12.

[3]胡艳维，秦拯，张忠志.基于模拟退火与K均值聚类的入侵检测算法[J].计算机科学，2010，37(6):122-124.

[4]李永忠，杨鸽，徐静.基于粒子群优化的聚类入侵检测算法[J].江苏科技大学学(自然科学版)，2009，23(1):51-55.

[5]袁芳芳.人工鱼群和K均值算法相融合的网络入侵检测[J].计算机仿真，2013，30(9):274-277.

[6]梅振益，杨慧中.基于差分进化模糊聚类的多模型建模[J].计算机与应用化学，2011，28(3):291-294.

[7]Sudhakar G. Effective image clustering with differential evolution technique[J]. International Journal of Computer and Communication Technology， 2010，2(1):11-19.

[8]Edwin C Shi， Frank H F. Leung Differential Evolution with Adaptive Population Size[C]. Proceedings of the 19th International Conference on Digital Signal Processing, 2014:876-881.

[9]高平，毛力，宋益春.基于改进差分进化的K-均值聚类算法[J].电脑知识与技术，2013，9(22):5064-5067.

[10]Guo Zhenyu， Bai Zhifeng， Cao Binggang. Chaotic Immune Differential Evolution Algorithm[C]∥Proceedings of the 2007 IEEE International Conference on Robotics and Biomimetics, 2007:15-18.

[11]Yan PEI. A Chaotic Ergodicity Based Evolutionary Computation Algorithm[C]. 2013 Ninth International Conference on Natural Computation， 2013:454-459.

[12]张新有，曾华燊，贾磊.入侵检测数据集KDD CUP99 研究[J] .计算机工程与设计，2010，31(22):4809-4816.

[13]王晓霞，孙德才，唐耀庚.改进的入侵检测数据降维方法[J]. 计算机工程与应用，2011，47(25):85-88.

Research on K Mean Clustering Algorithm Based on Improved DEAlgorithm in Intrusion Detection

WANG Guang1，2， ZHANG Xiao-ming2， XU Ri-hua1，2

(1.College of Information Science and Technology， Beijing University of Chemical Technology， Beijing 100029， China; 2.School of Information Engineering， Beijing Institute of Petro-Chemical Technology， Beijing 102617， China)

While using theKalgorithm, the mean value ofK-means to the preliminary cluster center needs tobe set artificially, and the cluster center is sensitive, whicheasily leadsto thedefect ofpartial optimum.The researchers adopt the improved DE algorithm to optimizeKalgorithm. Using dynamic cross parameters of CR and the scaling parameter F, can effectively balance the general searching capacity and constriction speed. The chaos randomly completethe population initialization of DE algorithm and reuse characteristics of the ergodicity of the near optimal DEindividuals in chaotic search, which can effectively improve the DEalgorithm with global searching ability. Finally, the KDD99 data set is used to verify the optimization of the K algorithm. The results indicate that the CDE-KM has better clustering capacity and good performance in terms of test results.

intrusion detection;Kalgorithm; chaotic search; DE algorithm

2016-04-24

王广(1988—)，男，硕士研究生为研究方向 信息安全，E-mail:13811710921@163.com。

TP37

A