粒子群优化的半监督入侵检测算法

贾志伟, 关忠仁, 赵建芳

(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.