改进的聚类算法在入侵检测系统中的应用*

邢瑞康，李成海

（空军工程大学防空反导学院，西安 710051）

0 引言

在网络信息技术高速发展的时代，计算机网络正以难以想象的速度向全世界各个角落渗透，使其成为当今人类社会运转必不可少的一部分。随着网络技术的不断发展和网络工具的广泛应用，网络空间蕴藏的巨大力量，以及网络资源的战略性意义正逐渐被世人发现、认可并着手发掘，世界各国在军事领域也随着网络的变革而不断发生变化。一个全新的军事竞争平台——网电空间成为现代军事化战争的又一主战场。然而，随着网络范围的日益扩大，由于安全机制的不尽完善，网络空间所要面对的威胁也不断增多，网络安全就成为一个十分重要的问题。因此，如何有效抵御各种入侵和攻击的行为成为重要课题。入侵检测（Intrusion Detection）主要建立在侵犯行为与系统行为不同的这一假设基础上，是一种动态的网络安全技术，它通过分析网络流量以及系统审计记录数据等，实时监控网络系统中是否存在与安全策略不相吻合的“入侵”行为，并且对可能危害到系统机密性、完整性和可用性的行为进行响应和拦截［1］。入侵检测技术作为网络与信息安全系统的关键技术，已经成为网络与信息安全体系中十分重要的部分。

聚类分析广泛地应用在统计学、决策支持、机器学习、模式识别、图像处理、空间数据库技术以及电子商务等相关领域，是一种十分高效的数据分析方法和一项重要的数据挖掘技术。数据挖掘能从大量的审计数据中挖掘出正常和异常的行为模式，使得人工分析和编码的工作量大大减少，入侵检测系统的检测效率也因此得到提高。因而，也被广泛地应用在入侵检测系统。

聚类算法的优劣往往直接会影响到聚类过程的最终效果。k-中心点算法作为其中的代表性算法之一，具有不易被极端的数据影响，适应性广泛，特别是针对“噪声”点、孤立点不敏感并且在检测当中应用广泛的特点，而且对数据属性的类型没有局限性，具有比较强的鲁棒性等。但是，该算法也存在许多缺陷。主要表现在：在对于处理规模较大的数据集时，K-中心点算法在聚类过程中的高耗时性。

因此，针对传统聚类算法的不足，本文结合算法和有效性指标提出了一种基于“密度”信息改进的算法。并将优化算法应用于入侵检测系统中。用实验验证了以这种方法来进行数据的聚类，显著地提高了数据尤其是大数据集聚类的效果。结果显示，改进的算法应用在入侵检测系统中提高了检测率并降低了误检率。

1 入侵检测

1.1 入侵检测的原理

现有的入侵检测系统主要采用以下方法来实现系统的检测机制，包括：代理、行为分析、概率统计、模式匹配、生物免疫系统、神经网络、专家系统、数据挖掘、遗传算法等。这些方法优劣不同，所应用的情形亦不同。它们不同程度地提高了处理的效率和有效性，能够满足一定的需求。

1.2 入侵检测的系统构成

一个完整的入侵检测系统通常包括以下基本组件，如图1所示：

图1 入侵检测系统的基本构成

1.3 入侵检测存在的不足

对于网络的各种攻击入侵，如果系统能够迅速高效地检测出来，就可以使得系统免于遭受各种不必要的资源以及网络空间的浪费，目前的IDS还有着诸多不足。主要包括：误报/漏报率较高，产品适应能力差，检测性能不足，同时检测实时性较差，缺少主动防御功能等等［3］。

2 聚类分析算法研究

设数据集合是由n个样本所组成的集合X={x1，x2，…，xn}，其中任一元素 xi，可表示为 m 维实数空间的向量，xi={xi1，xi2，…，xim}。任意两个样本 xi和xm之间的距离采用欧几里得距离，计算公式如下：

2.1 K-中心算法基本思想

k-中心点算法的处理过程主要是：首先，随机地从样本集中选取k个样本点作为划分k的个簇的代表点，即初始中心点，随即将其他剩余对象根据该点与代表点对象的远近分配到最近的中心点所代表的簇群中；然后，多次用非中心点来替换中心点，以此来不断改进聚类的效果，聚类的效果用“代价”函数进行估算。

K-中心点算法以这样的方式来计算代价S：

假设中心点xi1，然后用非中心点xh来替换中心点xi1，则产生下面4种情况。

1）如果点xj代表属于xi1所表示簇的任意一点，对于另一个中心点xi2，若，此时，xj重新归入xi2所代表的簇中，则其所产生的代价为：；

2）如果点xj代表属于xi1所表示簇的任意一点，对于另一个中心点xi2，若，此时，xj重新归入xh所代表的簇中，则其所产生的代价为：；

3）如果点xj不属于xi1所表示的簇，而属于xi2所代表的簇中任意一点，若，此时，xj所属簇不变，则其所产生的代价为：sji1h=0；

4）如果点xj不属于xi1所表示的簇，而属于xi2所代表的簇中任意一点，若，此时，xj重新归入xh所代表的簇中，则其所产生的代价为：。

上述4种情况如图2所示：

图2 k-中心点算法计算代价示意图

2.2 k-中心点算法描述

输入：包含n个对象的数据集，需要得到划分簇的簇数k；

输出：全部对象与中心点的距离总和最小的k个簇。

流程：

Step1：随机选择k个对象作为初始的簇中心；

Step2：重复以下步骤直到中心点不会再发生改变；

Step2.1：计算每一对象距离其最近的簇的中心点，并将其划分到该中心点所代表的簇中；

Step2.2：随机选取非中心点Orandom；

Step2.3：用Orandom代替Oj，计算形成新簇的总代价S；

Step2.4：如果 S＜0，用 Orandom代替 Oj，形成新集的k个中心点的集合；

Step3：输出k个簇。

3 改进k-中心点聚类算法的入侵检测模型

3.1 改进算法的基本思想

3.2 改进的k-中心点算法描述

输入：包含n个对象的数据集，需要得到划分簇的簇数k；

输出：全部对象与中心点的距离总和最小的k个簇；

流程：

Step1：计算每一个样本点的样本空间内所有点与该点的距离的和；

Step2：取样本点中计算所得的最大距离和与最小距离和的均值作为高密度样本的阈值；

Step3：取所有距离和小于该阈值的点组成高密度样本集合M；

Step4：对于所有样本点 xi，计算距离比 Vi：

选择使Vi最小的点x1作为第1个簇中心点；

Step5：从M中找出与x1距离相差最大的样本x2作为选取的第2个聚类中心；

Step6：从M中找出与x1和x2距离和相差最大的样本点x3作为第3个初始聚类中心；

Step7：从M中找与x1，…，xk-1距离和相差最大的样本xk作为最后一个初始聚类中心；

Step8：重复以下步骤直到中心点不会再发生改变；

Step8.1：将剩余的n-k个样本点按照距离远近分别分配到与它距离最小的中心点所代表的簇中；

Step8.2：随机选取非中心点；

Step8.3：计算用非中心点代替中心点，形成新簇群的总代价S；

Step8.4：如果 S＜0，用该点代替中心点，形成新的k个中心点集合；

Step9：输出k个簇。

3.3 改进的k-中心点算法的入侵检测模型

入侵检测系统分为训练部分和异常行为检测部分［4］。模型如图3所示：

图3 基于聚类算法的入侵检测模型

4 仿真研究

4.1 实验环境与数据源

为了验证聚类算法的有效性以及入侵检测模型的特点，本文分别采取两种数据进行验证。UCI数据库是国际上通用的专门进行数据挖掘与机器学习算法测试的数据库。对本实验进行评估所选取的Iris数据集合是UCI数据库中最常用于测试验证聚类算法优劣性的数据集。

为了测试新建立的入侵检测算法性能，采用KDD CUP 99数据集。采用训练数据和测试数据的10%数据集并对结果作出相应的分析。

入侵检测的性能指标用检测率（Detection Rate，DR）和误报率（False Positive Rate，FPR）进行描述：

检测率=正确检测出的入侵样本数/入侵样本总数。

误报率=将正常行为检测为入侵的样本数/正常行为样本总数。

4.2 实验结果与分析

为了测试基于密度信息来确定初始簇中心点算法的聚类性能，首先，将初始聚类的目标数目设置为3，即k=3，且在聚类时不考虑类别属性存在的影响（类别信息主要用来对聚类结果进行评估）。

对于原始的k-中心点聚类算法，实验时需要对其进行多次测试以得到实验的平均值作为结果（本次进行了10次实验操作），而本文提出的改进算法所采用的是基于“密度”的方式来处理初始中心点，对于处理同一数据集，其产生的初始中心点是唯一确定的，所以只需要进行一次实验即可。

原始的K-中心点聚类算法10次实验后的聚类结果如表1所示。两种算法迭代的次数以及聚类结果中错误样本比的实验对比结果由表2所示。

表1 传统k-中心点聚类算法结果统计

表2 多种算法聚类结果比较

由表1可以得到，传统k-中心点聚类算法会因为选取不同的初始中心点，而经过不同次数的迭代后才趋于收敛。如果存在随机选择的初始中心点有两个或者多个位于同一簇中的情况时，则算法需要多次迭代才能结束。甚至，在有些情况下，结束时所得到的结果仅仅是局部最优解，同时目标函数的值也会随着迭代次数的增加而逐渐变大，在第6次运行中，传统算法经过了较长的13次迭代才最终结束运算，而且得到了12.00%的错误率，簇中心的位置符合真实的分布情况。而第8次运算，算法甚至经过了14次迭代，运算才得以结束，同时得到较高的错误率，高达42.66%，算法显然陷入了局部最优解。

从表2可以看出，本文所提出的基于密度信息进行的改进算法不仅大大减少了迭代的次数，保证了算法运行的稳定性，而且避免了算法陷入局部最优解的可能。通过实验可以看到，改进的算法仅仅经过2次迭代就达到收敛，得到的错误率更低，远远优于传统k-中心点聚类算法平均的迭代次数和错误率，而且得到的簇中心也更加符合集合的真实分布情况。

表3 入侵检测模型结果比较

由表3实验数据显示，基于改进的K-中心点聚类算法的入侵检测系统经验证不仅是有效可行的，而且检测率也得以提高，误报率有所降低。

5 结论

入侵检测技术是计算机网络安全的重要保障，本文提出了一种基于“密度”信息改进的K-中心点算法，设计了入侵检测系统。采用基于密度的方式抽取样本集来确定初始中心点，充分考虑到训练集的分布情况，该算法通过将训练数据集转换为标准的单位特征度量空间；然后利用密度信息对数据进行初步划分，并以此找到聚类中心，这样得到的初始聚类中心相对准确，算法稳定性和时效性提高，同时有效降低了错误率。对改进的K-中心点算法的入侵检测模型进行检测，提高了入侵检测系统的性能。结果表明本文设计的检测模型能够有效抵抗异常攻击，可行性和有效性高，与传统的入侵检测系统相比具备一定的实用价值。