优化的聚类算法在异常检测中的应用

李建国

（淮北师范大学 计算机科学与技术学院，安徽 淮北 235000）

优化的聚类算法在异常检测中的应用

李建国

（淮北师范大学 计算机科学与技术学院，安徽 淮北 235000）

分析原有k-means聚类算法在异常检测应用中的不足，并对其进行优化，将优化后的聚类算法应用到异常检测中.实验表明，优化后的算法在入侵检测率和抗干扰能力方面有很大的提高.

异常检测；误用检测；聚类分析；k-means算法

0 引言

入侵检测［1-2］（Intrusion Detection）技术作为新一代、动态的网络检测技术，主要用来识别对计算机和网络资源的恶意使用行为，包含外部和内部的各种非法授权行为.根据入侵行为的属性，入侵检测一般分为异常检测和误用检测两种方式［3］.异常检测（Anormaly Detection）是一种在不需要操作系统及其安全性缺陷的专门知识情况下，就可以检测入侵者的方法，采用定量的方式描述可以接受的行为特征，以区分异常的、潜在的入侵行为，通过该方式可以发现未知的新型攻击.误用检测（Misuse Detection）通过检测用户行为中的那些与某些已知的入侵行为模式类似的行为，或那些利用系统中缺陷实施攻击的行为，以判断是否属于入侵行为，通过该方式只能检测出已知攻击.目前，为提高对网络攻击的检测水平，通过引入聚类分析技术联合异常检测技术，已成为广大学者研究的热点领域.

本文研究当前网络攻击的多种形式结合异常检测的要求，对传统k-means聚类算法在实际应用中的缺陷进行认真总结，并结合实际应用对算法进行优化，通过实验证明，优化后的算法在入侵检测率和抗干扰能力方面都有很大的提高.

1 传统聚类算法分析

1.1 算法概述

聚类分析算法中最常用的算法是基于划分的k-means算法，该算法根据最终聚类的个数k随机地选取k个初始聚类中心，不停地迭代，当达到目标函数的最小值时结束，即得到最终的聚类结果［4］.其中，目标函数通常采用平方误差准则.定义如式（1）所示：

1.2 算法应用不足

实际应用时，由于网络环境十分复杂，网络数据属性较多，难以精确度量等因素，使得该聚类算法应用在异常检测中有如下不足：

（1）要先给出聚类的最终个数，并以此作为初始聚类中心的个数，然后迭代扫描数据簇，同时持续修改聚类中心和数据项所属的簇，直到聚类中心稳定.因此，聚类结果与聚类个数联系紧密，聚类个数不同聚类结果差异较大，这使得在具体应用中很难把握.

（2）算法执行结束后将会产生空聚类（即没有记录与聚类中心的值匹配），这将严重影响聚类效果；

（3）由于算法执行时，初始聚类中心的选取方式是任意的，并且该算法对初值敏感，对于不同的初值，容易导致不同的聚类结果.

2 优化聚类算法的设计

现针对传统聚类算法在异常检测中存在的缺陷，对其进行如下优化：

（1）首先假定一距离聚类中心值S作为参数，接着计算当前数据项到该中心的距离，若此值大于S，则以该数据项产生新的聚类中心.因此，最终聚类的个数可以随时调整.另外，对于异常数据项又可以被划分到新的聚类中去，聚类效果较好.

（2）对于空聚类，可以将距离聚类中心最远的数据项移除其所属的集合，并以该数据项作为另外一个新聚类的聚类中心.这样新的聚类就代替了空聚类.

（3）关于初始聚类中心选取的问题，可通过以下方法解决：从原始数据集中选取样本集A，计算出k个聚类中心.先计算样本集中数据之间的距离，以距离最近的两点组成样本集A1，并将此从A中删除，然后将A1中的样本与样本集中的数据比较，找出样本集中与A1最近的点，将它们并入A1，并从A中删除.直到A1中数据的个数达到预定的阈值.再从A中找到样本两两距离最近的样本组成A2，重复上述操作得到k个点集，再对k个点集分别取平均值，进而得到k个初始聚类中心，有效地避免了“孤立点”带来的不良影响，同时加强初始聚类中心的代表性.

优化后的算法如下（假定数据库中数据项的个数为M，聚类参数为S，初始聚类个数为n）：

7）若出现空聚类，则剔除出距离聚类中心最远的数据项，以此作为新产生的聚类中心；

8）直到聚类中心稳定，算法结束，并输出新的聚类.

3 优化算法在异常检测中的应用分析

本实验环境基本配置如下：Intel Dual-Core E5500，4GB内存，Windows2000操作系统，Visual C++ 6.0，采用KDD Cup 99数据集［8-9］作为实验数据.

实验从数据集中选取包含PROBE端口扫描攻击的记录21 396条，包含Dos拒绝服务攻击的记录20 832条.其中分别包含了397条PROBE攻击记录和370条DoS攻击记录.从每条记录的41个属性中选取14个属性作为测试样本，通过本文提出的优化聚类算法将数据划分成不同的集合，进而将正常数据与异常数据隔离.

3.1 网络检测数据的预处理

由于从网络中得到的检测数据，数据属性种类繁多，并且其属性的度量单位差异较大，因此在应用本算法之前要用无单位的值替换原属性的值［10］.先通过以下公式计算出检测数据中各属性的平均绝对误差及平均值，分别用s、m表示，如式（3）和式（4）所示.

其中，第 f个属性的平均绝对误差用sf表示，第 f个属性的平均值用mf表示，xif表示第i条记录的第f个属性.用zf表示预处理后的第 f个属性的值.

在对检测数据完成以上处理之后，接着对数据属性的值进行相似性计算，相似类的划分是以对象间的距离为依据的.检测数据的属性分为离散型符号属性和连续型数值属性两类.用欧几里德距离来度量连续型数值属性之间的距离，如式（6）所示；对于离散型符号属性之间的距离则以数据对象间不同符号特征的离散属性的个数来表示.假设在检测数据集中有两个数据对象xi和xj，其中连续型数值属性有p个，离散型符号属性有m个，两对象之间的距离可用式（7）来表示.其中，dm(xi,xj)表示数据xi与xj的离散型符号属性之间的距离，dp(χi,χj)表示对象xi与xj的连续型数值属性之间的欧几里得距离.δ表示离散型符号属性之间的距离在计算记录间距离中所占的权重［11］.

3.2 实验结果分析

假设本实验记录总数为N，Q代表异常记录的比例，若数据集中数据项的数目小于QN，则把其当作异常聚类.假设Q值为0.02，初始聚类中心的个数为2.通过采用本文提出的优化聚类算法分别对上文中提取的两类数据集进行检测，得出关于 DoS与PROBE攻击的检测率和误检率的变化情况如图1和图2所示.

图1 DoS攻击的检测率和误检率

图2 PROBE攻击的检测率和误检率

由以上检测结果可以看出，通常情况下初始聚类中心个数和异常数据所占比例固定时，检测率会随着聚类参数的减小而增大；同时检测率和误检率也随着聚类个数的增加而增加，因此选择一个较小的聚类参数就可以达到很好的聚类效果.通过图1和图2得知，当聚类参数为15时，检测率达到较高的水平，同时也保持相对低的误检率，系统状态最佳.

4 结束语

本文所提出优化后的聚类算法有效地解决原算法中聚类中心个数对聚类结果影响较大的问题，同时也把空聚类和孤立点对聚类结果的影响降到较低的水平.实验证明，聚类算法在异常检测中的应用有着重大的研究意义，下一步研究的目标和方向，应该结合其它的异常检测技术，继续优化算法，以更大程度地提高系统的有效性.

［1］史美林，钱俊，董永乐.入侵检测技术与发展趋势［J］.信息安全与通信保密，2002（5）：45-57.

［2］崔锦法，李甦，王伟平.入侵检测系统研究［J］.云南大学学报：自然科学版，2006，28（SI）.128-132.

［3］宋世杰，胡华平，胡笑蕾，等.数据挖掘技术在网络型误用入侵检测系统中的应用［J］.计算机工程，2004，34（4）：126-127.

［4］HAN Jiawei，KAMBER Micheline.数据挖掘概念与技术［M］.范明，孟小峰，译.北京：机械工业出版社，2001：223-225.

［5］OZGUR D，MURAT T，MIN A，et al.An intelligent intrusion detection system（IDS）for anomaly and misuse detection in computer networks［J］.Expert Systems with Applications，2005（29）：713-722.

［6］连一峰.分布式入侵检测系统研究［D］.合肥：中国科学技术大学，2002.

［7］RICHARD F，SUE R，LEE B，et al.Intrusion detection inter-component adaptive negotiation［J］.Computer Networks，2001（34）：605-621.

［8］STOLFO S J,FAN W，LEE W.KDD-CUP-99 Task Description［EB/OL］.［1999-06-19］.http：//kdd.ics.uci.edu/data⁃bases/kddcup99/task.html.

［9］赵悦，陈凌晖.基于数据挖掘的入侵检测系统［J］.计算机系统应用，2008（9）：2-5.

［10］李卫平.k-means算法研究［J］.中西部科技，2011，7（8）：51-53.

［11］孙士保，秦克云.改进的k-平均聚类算法研究［J］.计算机工程，2007（13）：200-201.

Application of Optimized Clustering Algorithm in Anomaly Detection

LI Jian-guo
（Department of Computer Science and Technology，Huaibei Normal University，235000，Huaibei，Anhui，China）

By analyzing the deficiency of the original k-means algorithm in intrusion detection，the k-means algorithm was optimized.The optimized algorithm was used in anomaly detection.Experiments show that the optimized algorithm can get better cluster result and progress was made in the rate of intrusion detection and anti-interference technique.

anomaly detection；misused detection；cluster analysis；k-means algorithm

TP 393.08

A

2095-0691（2013）04-0052-04

2013-10-08

淮北市科技局基金项目（20120308）

李建国（1975- ），男，安徽砀山人，副教授，主要研究方向：网络安全、数据挖掘.