基于数据挖掘K—means算法的异常检测模型的研究与实现

张邻

【摘 要】本文结合数据仓库的优势采用数据挖掘中的K-means算法，对经过标准化预处理的数据进行训练、分类，获得可用的入侵检测规则。实验结果表明，K-means算法设计的异常检测模型可以作为预测和判断用户行为合法性的依据，并有较高的正确率，能降低系统的漏报率和误报率。

【关键词】K-means算法；入侵检测规则；用户行为；正确率

引言

入侵检测是当前流行的安全防御技术，一般可分为异常检测和误用检测两种类型[1]，异常检测主要用来发现未知的、可疑的攻击行为。提高异常检测的性能可以降低入侵检测系统的漏报率和误报率。数据挖掘K-means算法能高度自动化地分析原有数据，从中挖掘出潜在的模式，预测用户行为，对入侵行为重新划分，获得入侵行为规则。从本文实验结果表明，其可以降低入侵检测系统的漏报率和误报率。

1.数据挖掘（Data Mining）

数据挖掘就是要从大量的数据中整理出或挖掘出有用的知识，这些知识是隐含的、事先未知的具有潜在有用信息，它们可表示为概念、规则、规律、模式等形式[2]。数据挖掘技术是一种决策支持过程，它主要基于人工智能（AI）、机器学习统计等技术，能从大量数据中提取或挖掘知识。

2.数据挖掘的K-means算法

入侵检测模型需要高效、准确地处理海量的用户行为数据，并尽可能降低误判率、漏判率是判断一个入侵检测系统成功与否的标志。聚类分析方法具有可伸缩性、高维性、能处理不同类型属性、可按各种约束聚类等优点，尤其适用大型数据库的模式分类[3]。

2.1聚类分析

聚类按照“最大化类内相似性，最小化类间相似性”的原则，将数据对象分组为多个类或簇（cluster），同一个簇中的对象具有较高相似度，而不同簇间的对象差别较大，对象间的相异度根据对象的属性值计算。

给定一个有N个对象或元组的数据库，用聚类划分法构建数据的K个划分，每个划分表示一个聚簇，并且 K≤N。在聚类划分中，基于距离的分类采用度量方式，例如K-means、K-medoids等。当前比较流行的启发式方法首推K-means算法，我们在此用此算法对已知用户行为数据库进行聚类划分，检测入侵行为[4]。

2.2 K-means算法

K-means算法以K为参数，把N个对象分为K个簇，以使簇内具有较高的相似度，而簇间的相似度较低。相似度的计算根据一个簇中的平均值（视为簇重心）进行。K-means算法的处理过程为：

1）随机选择K个对象，每个对象初始代表一个簇的平均值或中心。对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。

2）重新计算每个簇的平均值。这个过程不断重复，直至准则函数收敛到期望值。由于实际应用中对象数据选用的度量单位将直接影响聚类分析结果，不同度量单位可能产生迥异的聚类结构，因此为避免对度量单位选择的依赖，实际中应先对数据进行标准化处理。

每个对象与簇中心的距离采用欧几里德距离，其定义如式（2-1）所示，其中i =（Xi1，Xi2，...，Xip）和 j =（Xj1，Xj2 ， ...， Xjp）是2个p维的数据对象。

（2-1）

该算法试图找出使均方误差函数值最小的 K个划分，令生成的结果尽量紧凑、独立。下面是K-means算法的流程，从中可以得到，算法的复杂度为O（nkt），远小于O（n2），其中，n是所有对象的数目，K是簇的数目，t是迭代次数（一般k和t均小于n）。鉴于待划分的数据库通常比较大，这种性能还是比较优良的。

K-means算法流程如下：

（1）算法K-means基于簇中对象平均值。

（2）输入簇的数目K和N个对象的数据库。

（3）输出K个簇，满足均方误差函数值最小。

3.异常检测模型

通过数据仓库的数据采集、预处理及分析后，形成一个以异常检测为主题的数据集市，该数据集市的模型包含IP地址ID、连接次数、访问协议ID、访问协议次数、访问目标端口次数、出现连接错误次数、访问资源级别ID、访问资源次数。

对生成的异常检测数据进行标准化处理，成为可供K-means使用的特征数据。采用C++语言按照上述原理与流程进行编程，对数据进行分析，经过有限次的迭代即可识别出异常、攻击、安全3种类型的记录，当然也可以按照自己的要求设置分类数。

图1是使用K-means算法设计异常检测模型的设计流程图，用它来生成异常检测规则。

图1异常检测模型的设计流程图

对K-means聚类结果进行分析后，总结出不同类规则及其含义，把这些规则中的正常与攻击行为模式作为入侵检测模式存入在数据仓库中，用以预测和判断用户行为合法性的依据。

4.实验

4.1实验用例

本测试使用MIT林肯实验室开发的DARPA 1999年IDS评测数据集进行了实验测试。异常检测实验时把星期一的部分数据用来经过入侵检测模型来生成异常检测规则，把星期二、星期四、星期五的数据用来进行异常检测实验。

4.2测试过程

处理星期一的部分数据，使数据的形式满足异常检测模型的需要，表4-1是处理数据的最终形式，太多的数据会使程序运行缓慢，而且没有太大的必要。把此数据以文件的形式提交给异常检测模型，我们根据异常检测模型的运行结果（运行时间与主机配置有关）得到异常检测规则。接下来把星期二、星期四、星期五的数据进行异常检测。

表1中各参数含义：

Ip 源IP地址。

count 在一个时间窗口内目标主机的连接次数。

error 出现syn错误的连接百分比。

same_srv 目标端口相同的连接所占的百分比。

diff_srv 目标端口不同的连接所占的百分比。

srv_count 目标端口与当前连接相同的连接次数。

srv_diff_host 目标主机不同的连接所占的百分比。

通过异常检测模型分析，发现SYN错误为0.9、0.75、0.8属于同一类，所以SYN大于0.75的应属于是攻击行为，SYN错误为0.2-0.7属于同一类作为异常行为，而SYN错误小于0.2的属于正常行为。

5.结束语

本文采用数据挖掘K-means算法来建立异常检测模型。通过以上模拟实验可知，使用K-means算法可以形成可用的异常检测规则，用于异常检测时也有较高的正确率。影响异常检测因素很多，比如异常检测模型规则的数据的正确性、数据的角度等。以后的研究中可以提供不同角度不同主题的数据给异常检测模型，以生成其他角度的异常检测的规则，提高入侵检测的精确度。

参考文献：

[1] 杨永铭.异常点检测算法在入侵检测中的应用研究.现代计算机.2008.1：35-38.

[2] Chen W M.Data Mining：an Overview from An Database Perspective.IEEE Trans on Knowledge and Data Eng，l996（8）：866.

[3] 李洋.K-means聚类算法在入侵检测中的应用.计算机工程.2007年7月：155-156.