组合聚类算法在异常检测中的应用研究

卢扬

摘要：该文结合当前网络异常检测的要求，在分析以往算法不足的基础上，提出了一种组合聚类算法，并应用到异常检测中。该算法先后使用蚁群聚类算法和K-means算法对数据进行聚类。通过两种聚类算法的有效组合，解决了原有聚类算法聚类结果受初始聚类中心选取的影响，实验证明该算法在保证较低误报率水平的前提下，提高了系统的的检测率。

关键词：入侵检测；异常检测；聚类分析；K-means算法；蚁群算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2012）33-8010-04

近年来随着Internet的快速发展，众多信息利用网络平台进行传输存储，随之而来的信息安全问题亦日显突出。入侵检测技术因能及时发现并报告系统中未授权或异常现象，越来越多的被用于动态检测网络，确保网络安全。入侵检测主要有误用检测和异常检测两种方法。异常检测是一种基于行为的检测，通过将过去观察到的正常行为与受到攻击时的行为相比较，根据使用者的异常行为或资源的异常使用状况来判断是否发生入侵活动。美国哥伦比亚大学WenkeLee教授最早提出将数据挖掘技术应用到入侵检测系统中。国内向继等人将聚类算法应用到异常检测中。目前，通过对各类聚类算法在异常检测应用中的改进，可以检测出不同攻击类型，从而大大提高系统的检测率，因此该工作已成为入侵检测领域研究的一大热点。

该文结合当前网络异常检测的要求，在分析以往算法不足的基础上，提出了一种组合聚类算法，并应用到异常检测中，以提高系统的检测性能。

1聚类算法介绍

聚类分析能发现新型的和未知的入侵类型，它是一种无监督的学习方法，其将一些未知模式分成若干类，若特征向量之间的距离在一定误差范围内相等，则认为它们是同一类型。下面将介绍入侵检测中两种常见的聚类算法。

1.1基于K-means的聚类算法

K-means算法是由MacQueen提出的一种经典的聚类算法。其算法思想是通过迭代过程将数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而生成的每个聚类内紧凑，类间独立。算法首先从n个数据对象任意选择K个对象作为初始聚类中心；剩下其它对象根据它们与这些聚类中心的距离，分别将它们归类最相似的簇中；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数该算法使用误差平方和准侧函数来评价聚类的性能。假设X包含K个聚类子集X1，X2，…，Xk；则误差平方和[E=i=1kp∈Xip-mi2]准则函数公式为：

E表示所有数据的均方差之和，P为对象中的一个点，mi为聚类中心值。各个聚类自己种的样本数量分别为n1，n2，…，nk各个聚类子集的平均值代表点分别是m1，m2，…，mk。

数据与聚类中心的距离由欧式距离公式计算而得。样本Xi与Xj之间的欧式距离公式为：

1.2基于蚁群的聚类算法

蚁群聚类算法是蚁群在觅食过程中，蚂蚁依据一定的概率选择觅食路径原理研究而得出的一种智能算法。研究发现，蚂蚁在此过程中，会在所经过的路径上不断释放一种信息素用于和其他蚂蚁进行信息的传递，这种物质能够被同类感知，并指导同类选择运动方向，因此有大量蚂蚁组成的蚁群集体行为便呈现出一种信息正反馈现象，即某一路经上走过的蚂蚁越多，则后来者选择该路径的概率就越大。在整个觅食寻径中，由于信息素的作用使得整个蚁群集体的行为具有了很高的自组性。因此，在入侵检测中，可以将检测数据视作蚂蚁，而聚类中心就是蚂蚁所要寻找的食物源。

设X={Xi|X=（xi1，xi2，…，xin），i=1，2，…，n}是待聚类的数据集合；[vj]为聚类中心；预设聚类半径为R，统计误差为[ε]，信息数量为[τij]。

t时刻，数据Xi到[vj]路径上的残留的信息素[τij]（t）为：当[dij]<=R时[τij]（t） =1；当[dij]>=R，[τij]（t）=0。其中[dij]表示数据Xi到[vj]之间的欧式距离。

t时刻，数据Xi是否属于聚类中心的概率计算方式为：[pij（t）=ταij（t）ηβij（t）s∈Sταsj（t）ηβij（t）]

其中S={Xs|[dsj]<=R，s=1，2，…，n}，它表示分布在聚类中心[vj]内的数据集合。[ηij]为1/[dij]，[α，β]是为了防止数据的沿相同路径得到相同聚类造成停滞搜索结果而设置的调节因子，

令VSj={Xk|[dkj]<=R，s=1，2，…，j}，式中VSj表示Vj 中的数据集合，j为Vj中的数据个数。那么理想的聚类中心由[v-=1jk=1jXk]公式计算得出。其中[Xk∈VSj]。

计算每个聚类的偏离误差公式为[εj=k=1ji=1m（xki-xji）2]，所有聚类的总偏差[ε=j=1kεj]

该算法具体描述：

2组合聚类算法的研究与实现

2.1组合聚类算法的研究

在该文所提到两种聚类算法中，K-means算法是数据挖掘中一种经典的划分聚类算法。它具有简单且收敛速度快的特点。其缺点在于聚类结果与初始聚类中心的选择有较大关系，一旦初始值选择的不好，可能无法得到有效的聚类结果。与此相比，遗传聚类算法的优势主要体现在其具有自组织、可伸缩性、鲁棒性等特性，但自身易出现早熟停滞的现象。由于现在网络中攻击方法呈现出多样化，且检测环境也在不断发生变化；而聚类算法都存在着自身的缺点，单一采用某种算法进行入侵检测，有一定的局限性，会影响检测效果。基于上述情况，该文提出了一种组合聚类算法，将以上提供的两种算法应用到适合自己特点的挖掘步骤中，以达到提高入侵检测系统检测效果的目的。该算法可以分为两步。第一步：蚁群聚类算法的聚类过程。为了克服K-means对聚类中心以及聚类的数目有着比较强的依赖性的缺点，首先采用传统的蚁群聚类算法进行聚类。将初始化后数据作为不同属性的蚂蚁，蚂蚁所要寻找的食物源表示为聚类中心。利用蚁群聚类算法有较强的鲁棒性，能够得到比较优越满足精度条件聚类结果的特点，得到相对可靠的聚类个数和聚类中心。第二步：K-means算法的聚类参数更新过程。将第一步得到的聚类结果作为此阶段的初始值，这样既克服K-means对聚类算法对初始聚类中心的要求的缺点，又能结合了其动态的搜索自适应特点，从而使得聚类结果更加合理可靠。

2.2组合聚类算法实现流程

聚类算法的挖掘过程可以概括为：初始化阶段、聚类算法实现阶段、聚类结果的输出阶段。

该组合聚类算法的流程描述如下：

1）组合聚类算法的参数初始化阶段

① 设置聚类包含的最小数据对象个数K，[α]，[β]，预设聚类半径R，初始概率P0、初始统计误差[ε0]等。

② 数据预处理，既选取数据中适当的属性并进行标准化。

③ 将待聚类的数据对象随机分布于二维区域中，赋予其一对坐标（[xi，yi]），其中[xi和yi]均属于整个对象集合所在区域，i=1，2，…，n。

2）组合聚类算法实现阶段

①蚁群聚类算法的聚类过程

a）设置所有蚂蚁初始状态值，选取K个蚂蚁放置在预先设置的K个聚类的聚类中心上。

b） 计算每个聚类中心的平均值和转移概率，并完成归类。

c） 计算每类聚类的偏离误差和所有聚类总偏差，更新聚类中心和信息素。

d） 程序直至总偏差小于等于初始偏差结束。

②利用K-means算法聚类，更新优化聚类结果

a） 将遗传算法获得的聚类中心作为K-means算法的初始聚类中心。

b） 以数据与聚类中心值的距离最近为标准，对每个数据进行聚类划分。

c） 通过K-means算法中定义的目标函数的再聚类，迭代优化，更新聚类中心值，直到聚类划分不再发生变化。

3）组合聚类算法聚类结果输出。

3实验结果分析

为了评价组合聚类算法应用到异常检测中的效率，选用目前入侵检测领域比较权威KDDCUP1999网络数据集作为测试数据，可从http：//kdd.ics.uci.edu下载。实验平台基本配置为Intel PentiumDual–Core的CPU，2GB内存；Windows2000的操作系统，VC++6.0编程语言。

在仿真试验中，从KDDCUP1999数据集中随机选取5组具有2100个数据的样本集，其中包含2000个正常连接记录和100个异常连接记录。为了便于观察实验结果进行分析，在表1中汇总了蚁群、K-means和组合聚类算法三种算法的五组实验数据。该实验数据中列出了检测到的异常事件个数、漏报事件个数、误报事件个数，并对检测率、漏报率、误报率和检测正确率进行了统计。

通过上述实验结果可知，组合聚类算法的平均检测率为78.40%和误报率为0.64%。与单一算法检测结果相比，检测率有了明显提高，而误报率也保持在较低的水平，这充分说明了该组合算法实现了聚类的优化。

4结束语

该文提出了一种组合聚类算法并应用到异常检测中。该算法先后使用了蚁群聚类算法和K-means算法对数据进行聚类。通过两种聚类算法的有效组合，解决了原有聚类算法聚类结果受初始聚类中心选取的影响。实验证明该算法在保持低水平误报率的前提下，具有较高的检测率，对于未知入侵行为检测的具有较好的可行性和有效性。

参考文献：

[1]Barrus，JosephD.IntrusionDetectioninRealTimeinalMulti-NodeMulti-HostEnvironment[D].Master5thesis.NavalPostgraduateSehool，CA，2006：23-34.

[2]阮耀平，易江波，赵战生.计算机系统入侵检侧模型与方[J].计算机工程，2005（9）：224-236.

[3]杨义先，钮心忻.入侵检测理论与技术[M].北京：高等教育出版社，2006：56-67.

[4]MehmedKantardxie.数据挖掘概念、模型、方法和算法[M].北京：清华大学出版社，2003：170-194.

[5]汤洁.分布式入侵检测系统的研究与设计[D].南京：南京信息工程大学，2008：89-96.

[6]熊家军.基于数据挖掘的入侵检测关键技术研究[D].武汉：华中科技大学，004：2-96.

[7]RumethartD，drowB，LehrM.Thebasicideasinneuralnetworks[J].ununieationsoftheACM，994，7（3）：7-92.

[8]梁红.利用划分方法进行混合数据聚类[J].地理空间信息，011（12）：8-19.

[9]秦姣华，旭宇.据挖掘在入侵检测中的应用[J].现代计算机，2008（1）：23-26.

[10]耿俊燕，吴灏.数据挖掘在入侵检测系统中的应用研究[J].计算机工程与设计，2007，26（4）：870-872.

[11]AprespectiveonDatabasesandDataMining，InproceedingsoftheFirstIntemationalConferceonKnowLedgeDiscoveryandDataMining（KDD95）.2009：150-155.

[12]王千.K-means聚类算法研究综述[J].电子设计工程息，2012（7）：21-22.

[13]LaiJZC，Tsung-JenH.FastglobalK-meansclusteringusingclustermembershipandinequality[J].PatternRecognition，2010（43）：1954-1963.

[14]匡青，鲍梦.改进蚁群算法的动态K-均值聚类分析[J].软件导刊，2008，7（1）：154-155.

[15]孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报，2008，19（1）：48-61.

[16]王英泽.一种数据挖掘技术在入侵检测系统中的应用[D].哈尔滨：哈尔滨理工大学，2007：34-43.

[17]夏天扬.蚁群算法在聚类分析中的应用研究[D].武汉：武汉理工大学，2010：34-45.

[18]陈军.用一种改进的蚁群聚类算法进行网络入侵检测[J].沈阳航空工业学院学报，2010（2）：72-73.

[19]范治军.基于数据挖掘的入侵检测研究[D].大连：大连理工大学，2012：28-38.

[20]梁君玲.蚁群聚类算法研究及其在聚类中的应用[D].广州：华南理工大学，2011：30-35.

[21]朱琳.基于数据挖掘的入侵检测的研究[D].兰州：兰州理工大学，2012：20-40.