改进的聚类算法在网络异常行为检测中的应用

辛 壮，万 良，李均涛

(1.贵州大学 计算机科学与技术学院，贵州 贵阳 550025;2.贵州财经大学 信息学院，贵州 贵阳 550025)

1 概 述

现阶段，计算机网络已经基本实现全球化，庞大的网络体系方便了信息的交流与传递，但是也给网络黑客提供了更多的便利。面对着越来越复杂的网络环境、灵活多变的网络攻击手段，如何快速、准确地识别网络异常行为，并减轻异常行为对网络环境的破坏具有非常重要的意义。对此，专家学者们将数据挖掘技术应用到检测技术中，依靠无监督、半监督的方式快速准确地识别异常、非异常行为，这也是当前的研究热点之一[1-2]。

K-means作为传统的聚类算法，能够对大量的数据进行快速聚类，较好地符合了网络异常行为检测的实时性要求。K-means算法能够对无标记的数据样本进行有效聚类，相比于有监督的方法能够大大减少标记时间并且降低数据开销。国内外不断有学者将聚类算法与分类算法相结合的半监督学习方式应用于异常行为检测，例如，Zhang等[3]分析了半监督学习方式对于聚类效果的影响，Erman等[4]将半监督学习方式应用到流量分类中，并且验证了半监督学习方式对于网络流量分类的有效性。

传统的K-means算法虽然简单有效，但需要事先确定k值，并且算法对于噪声敏感。为了克服K-means算法的不足，许多专家学者都曾试图从各个角度对K-means算法进行改进与优化。文献[5]提出了一种快速的最小生成树算法，该算法与K-means算法结合使用能够快速处理大规模数据集。把精确的最小生成树算法应用到通过K-means算法得到的K个聚类之中，根据提出的准则连接每个处理之后的聚类，形成近似的最小生成树。再将聚类产生的相邻对的相邻边界划分为一个聚类，并构建另一个近似的最小生成树。通过合并操作，将两个近似最小生成树合并成一个图形，从而生成更精确的最小生成树，以提高算法的运行效率，使结果更加有效。文献[6]提出了一种能够快速对多维数据进行K-means聚类的方法。通过将多维数据分组，不同的组对应不同的带权值的非空单元格，K-means聚类对象不再作用于单个的多维对象而是直接对非空单元格的哑元点进行操作，并且在算法的迭代过程中不再重复计算哑元点与不同聚类中心之间的聚类。这种改进能够对大量的多维数据进行快速有效的聚类。文献[7]提出一种新的聚类算法，将最小生成树算法与K-means算法结合使用，通过基于质心的最近邻规则来划分局部邻域图以代替传统的构造完全图的方法。该算法能够在保证簇质量的前提下降低计算时间。文献[8]提出一种异常检测技术，通过K-means算法将数据集聚类并构建最小生成树，将树中的最长边删除形成新的聚类，将小聚类中的数据点作为异常值的候选点并进行分析，从而找出真正的异常点。文献[9]提出一种无参数最小生成树算法来自动地确定簇数，通过计算簇间与簇内距离的比例，对K-means聚类结果进行测试。结果表明，改进算法有更好的聚类效果。文献[10]提出使用模糊聚类算法，将聚类边缘的网络数据特征值再次模糊聚类的异常行为判断方法。

上述改进虽然能够在聚类前事先确定k值，也能减少噪声点对聚类效果的影响，但是对于准确选择初始聚类中心和有效识别非球状簇这两个问题并没有得到改善。对此，文中提出一种改进的聚类算法应用在网络异常行为检测中，该算法的优越性表现在：融合最小生成树算法，能够更佳有效地判断聚类中心，避免了传统K-means算法依靠随机生成聚类中心从而造成聚类结果不准确的情况；使用重心算法更新聚类中心，能够更好地识别非球状簇；通过距离比值在聚类的迭代过程中判断聚类效果的优劣，使得聚类结果始终保持在最优状态。

2 传统K-means算法

K-means算法是经典的聚类算法，应用在异常行为检测中能很好地对训练数据集进行训练从而构建分类器，检测模块根据分类器来判断是否发生异常行为。算法应用如图1所示。

图1 聚类算法在网络异常行为检测中的应用模型

算法能够根据预先给定的k值，随机地在样本集中选取k个聚类中心，通过计算欧氏距离与预先设置好的阈值进行对比，把相似度高的样本分配到同一个簇中。之后不断的进行迭代，更新聚类中心，直到目标函数收敛，最终把样本集聚类成k个类[11]。算法步骤如下：

设聚类样本集为X={x1,x2,…,xn},其中x为样本数据，n为样本总数；聚类类别为Zk={z1,z2,…,zk}，其中k为类别数目，nk表示第k类的样本数目；{c1,c2,…,ck}为k个聚类中心。

定义样本数据平均值：

(1)

定义目标函数：

(2)

目标函数J为样本数据集每个类中所有点到聚类中心的距离平方和，当J最小即得到最小均方差时，迭代完成。

(1)预先指定聚类个数k；

(2)随机选取k个样本数据c1,c2,…,ck作为初始聚类中心；

(3)根据公式d(xi,xj)计算每个点与聚类中心的距离，根据欧氏距离对样本数据进行聚类，每个样本数据总是聚类到与包含样本点最近的聚类中心的簇中；

(4)根据式1重新计算聚类中心c1,c2,…,ck；

(5)若式2收敛，则聚类完成，若不收敛，则重复执行步骤3～4。

K-means算法作为传统的聚类算法，能够应付大规模的数据处理，并且聚类速度快，但当K-means算法应用在网络异常行为检测领域时也有一定的缺点：

(1)要人为确定k值，这需要进行大量的实验和具备一定的学术经验才能对k值进行准确判断，不同的k值对聚类结果影响巨大，一个不好的k值往往会降低聚类效果；

(2)K-means算法中初始聚类中心的确定是随机的；

(3)对离群值与噪声数据敏感；

(4)对非球状簇的聚类效果不明显；

(5)容易陷入局部最优解[12-13]。

K-means聚类算法也有要遵循的前提条件，这也是所有聚类算法要遵循的几点假设。

(1)在聚类过程中，正常网络数据流量的数目要占多数，远远大于非正常网络数据流量的数目；

(2)正常网络数据流量要与非正常网络数据流量特征有明显的差异。

3 改进的聚类算法

根据对K-means聚类算法的大量研究，以K-means聚类算法为基础，添加最小生成树概念，在已经确定好k值的情况下，通过融合最小生成树算法，将训练数据集进行合并和分裂操作来确定训练样本关键点。把关键点映射成训练数据集的初始聚类中心，在数据迭代过程中，通过重心算法重新计算聚类中心，通过对比距离比值聚类结果的优劣，直到收敛函数收敛，得到最终的聚类结果[14-17]。

3.1 相关概念

(1)重心。

传统的K-means算法由于算法限制及依据数据点距离平均值选取聚类中心的方法，使其对非球状簇的识别效果并不理想。通过计算聚类重心来更新聚类中心的方法，能够使得聚类中心不会偏离聚类本身，使得算法在识别非球状簇时也能有很好的聚类效果。公式如下：

g=(w1+w2+…+wn)/n

(3)

(2)类内距离。

设cj(j=1,2,…,k)为聚类中心，xi是以cj为中心的聚类中的任意数据。类内距离DWC为类内任意数据点到聚类中心距离的平均值，即：

(4)

其中，nj为某一类中的数据个数。

(3)类间距离。

(5)

(4)距离比值。

距离比值WB是类内距离DWC与类间距离DBC的比值，公式为：

(6)

通过WB来反映聚类效果的优劣。K-means算法根据类间分离、类内紧凑的原则进行聚类划分，通过对单个数据点进行研究分析，分别用类间距离DBC与类内距离DWC表示类间分离度、类内紧凑度，计算出的结果能够更加直观准确地对聚类效果进行判断。如图2所示，网络数据流量样本被分为四类，分别为j、x、y、z，j类中的样本中心点为i。根据概念2得知，样本中心点i到j类内其他样本数据距离的平均值为类内距离，反映了类内的紧凑程度，从数值上看，得到的DWC数值越小，类内紧凑程度就越大。根据概念3，j类样本中心点i到其他类x、y、z的样本中心点距离的平均值称为类间距离，反映了类间的离散程度，类间距离越大，DBC越大，离散程度越高。从类内紧凑程度来看，希望DWC越小越好，从类间离散程度来看，希望DBC越大越好。因此单一的DBC或者DWC都无法准确地判断聚类效果的优劣，于是将WD作为聚类结果的评价标准。WD通过类间距离与类内距离的比值作为评判标准，WD越小说明聚类效果越好，但是并不适用于聚类数为1的情况。

图2 聚类结构示意

3.2 算法思想

(1)初始聚类中心的选取。

最小生成树是完全图的最小连通子图，包含完全图的所有点。将网络流量数据作为完全图的连接点构建带权完全图G(x)={V,E,D}，其中V(V∈X)为完全图的顶点集，E(E={(xi,xj)|xi,xj∈X})为完全图的边，将任意两个连接点xi,xj之间的距离d(xi,xj)作为边的权重D(D={d(xi,xj)|xi,xj∈X})。通过Kruskal算法构建出完全图的最小生成树，通过最小生成树确定网络数据流量关键点，其具体过程如下：

首先，确定网络流量数据关键点的所有候选点。计算完全图中所有边的权值D，寻找权值最小边的点，如xi,xj是权值最小边的点，将两点存入集合Bx，将边存入集合Ex。搜索完全图中所有的边，此时集合Bx与集合Ex包含全部的数据点与边，并且边集Ex中的数据是以边权重的大小进行排列的。

遍历边集Ex，将最小权值的边添加到最小生成树中，若添加一条边之后，最小生成树构成回路则删除边集Ex、点集Bx中对应的数据，最终构建出最小生成树T(E1,E2,…,En)。根据最小生成树，逐层查找距离最小的两个点，计算两个点的中心O=d(xi,xj)/2。用计算出的中心点O代替两个连接点的边，并且将中心点作为父节点处理，更新边集Ex与点集Bx，此时两个集合中的数据都将减少1，重复执行合并操作，直到最小生成树只含有k个连接点时，查找结束。将最小生成树剩余的连接点作为网络流量数据的初始聚类中心。

(2)初始聚类的划分。

将最小生成树算法得到的数据点作为初始聚类中心，得到聚类中心集C={o1,o2,…,on}。取其中一个聚类中心点ox为例，遍历新数据样本集X'(X'∈{X-ox})，根据预先设置的半径R，若样本数据集中的数据元素与聚类中心点ox的距离小于半径R，则划分到以ox为聚类中心的簇中，并修改类标识，在新的样本数据集中删除此样本数据。若距离大于半径R，则将此样本数据点与其他聚类中心点进行比较。

(3)生成新的聚类。

根据式3计算新的聚类中心，得到新的聚类中心集C。与初始聚类划分的操作类似，根据半径R进行新聚类的划分。新聚类划分完成之后，计算每个点的DWC与DBC，得到距离比值WB。若比值过大或超过阈值，则需要重新聚类。

具体的算法实现如下：

步骤1：根据公式d(xi,xj)计算出任意样本数据xi(i=1,2,…,n)与其他样本数据x∈X，{X-{x}}的欧氏距离d，获得数据集D，用来存储样本的数据距离。

步骤2：根据Kruskal算法，把样本数据集D中的数据作为最小生成树的端点，将两点之间的距离作为最小生成树的边，从而构建最小生成树，将边长存入数据集E。从数据集E中寻找权重最小的边即欧氏距离最小的两个点，公式如下：

Dmin=min{d(xi,xj)}

(7)

其中，xi，xj为训练集中的任意数据，若其权重最小，则计算出中心点dij，用计算出的值代替权重最小的边，更新数据集E，直到数据集E中的元素个数剩余k个。

步骤3：以数据集E中的元素作为关键点，映射到样本数据集合X中，以关键点作为初始聚类中心，获得聚类中心集合C。

步骤4：以集合C中的元素ox为中心，遍历训练集的样本数据，根据距离最近的原则将数据点划分成k个簇。

步骤5：根据式3重新计算出新的聚类中心，根据新的聚类中心更新聚类中心集合C，根据数据集中点的相似度进行重新聚类。

步骤6：根据式6计算出样本的WB，与预先设置好的阈值进行比较，若不满足条件则重新执行步骤4，重新聚类，若满足则执行步骤7。

步骤7：若目标函数(式2)收敛，则输出最终聚类结果，若不收敛，则重新聚类。

在聚类过程中会遇到边缘值的问题，样本数据点会在类的交界处，这种数据至少拥有几个类的属性特征，没办法明确地确定这种数据点到底属于哪一个类。通过计算余弦相似度来进行区分，计算公式如下：

(8)

其中，n表示样本数据维度；x表示在类交界处的数据点；y表示处于交界类中的任意数据。改进的K-means算法将处于类交界处的数据点划分到余弦相似度最大的类中。

4 实 验

采用KDD Cup99数据集进行仿真实验，该数据集是由哥伦比亚大学教授和北卡罗来纳州立大学教授通过数据挖掘技术对DARPA数据进行处理形成的。数据集中包括Normal、DOS、Probe、R2L、U2R五大类攻击类型的数据，并且又细分为22种攻击行为数据，其中训练集仅存在8种攻击行为数据，另外14种攻击行为数据存在于测试集中。

4.1 数据预处理

数据预处理的目的是使数据能够更加快速有效地进行数据挖掘。首先把离散属性转换为连续属性，然后再进行数据点标准化与归一化。计算公式如下：

(9)

(10)

|Xnj-AVGj|)

(11)

数据归一化是把标准化的数据归一到[0-1]区间之内，归一化的公式如下：

(12)

(13)

(14)

从KDD Cup99数据集中按比例抽取一部分数据作为训练集与测试集，把训练集和测试集分为四组进行测试。其中每组正常行为数据为4 890条，非正常行为数据为110条，如表1所示。

表1 异常行为检测测试数据集

4.2 实验结果与分析

实验使用检测率与误检率作为网络异常行为检测的评判标准，公式如下：

(15)

误检率=

(16)

经过多次实验，得出能实现较好聚类结果的k值，首先对传统的K-means算法与融合高斯随机数的K-means算法进行比较，结果如表2所示。

表2 算法检测结果比较

使用融合最小生成树的K-means算法对数据集进行检测，检测结果如表3所示。

表3 融合最小生成树的K-means算法检测结果

由对比结果可以看出，对于网络异常行为检测，传统的K-means算法误检率较高，容易产生误报，将正常的网络行为检测成异常网络行为，误检率平均值为9.3%。检测率在三种方法中最低，平均值为74.0%，对于异常网络行为，容易产生漏报。而融合高斯随机数的K-means算法对于网络异常行为检测，检测率相对于传统K-means有所提高，但是检测率波动较大，具有随机性。

由表3可以看出，融合最小生成树的K-means算法，在网络异常行为检测方面有较好的效果。与传统K-means算法、融合高斯随机数的K-means算法相比，检测率有明显的提升，均值提升到95.2%，误检率平均值下降到1%以下。

为了更好地检验融合最小生成树的K-means算法对于网络异常行为的检测效果，将其与传统K-means算法进行比较，检测效果如表4所示。

表4 对不同攻击类型检测效果

传统的K-means算法对于U2R、R2L的检测效果不是太理想，这两种攻击类型都是伪装成用户正常行为来实现攻击的，数据特征与正常行为特征具有相似性，并且两种攻击类型数据数目较少，在数据训练时对其处理效果不好，导致后期检测效果下降。另一方面，改进后的K-means算法对于四种攻击都有很好的检测效果，尤其是Prohe类型攻击，达到了完全检测的效果。对于U2R类型攻击，不可避免地将其聚类到正常网络行为中，使得其误检率较高。

从实验结果可以看出，融合最小生成树的K-means算法对网络异常行为具有更高的检测效果，由最小生成树得到数据关键点，以关键点为初始聚类中心。相对于传统的K-means算法，该算法能够较好地解决初始聚类中心随机选择的问题，克服了聚类容易陷入局部最优的问题。自定义的有效性指标能够判断聚类效果的好坏，确保最佳聚类效果，通过重心选择算法更新聚类中心的方法，使得聚类不再因为聚类簇图像过于狭窄或者非球形而使得聚类中心偏离簇本身，与传统的K-means算法相比，检测效果明显提升。

5 结束语

通过仿真实验可以看出，融合最小生成树算法能够使得K-means算法在网络异常行为检测中得到更好的应用，并且改进的重心选择算法能够使得K-means算法的聚类效果更加准确有效。该算法在k值确定的情况下，通过最小生成树算法确定初始聚类中心，克服了初始聚类中心随机性选择的问题，距离比值的存在确保了输出的聚类能够达到最好的效果，在更新聚类中心的过程中，通过重心选择算法选取新的聚类中心，这有别与传统的计算平均值算法，有效解决了聚类中心因为聚类簇太狭窄而使得聚类中心偏移的问题。

然而融合最小生成树的K-means算法，时间复杂度太高，要迭代数次才能完成数据关键点的确认。并且该算法仍然要事先确定k值，还是不能摆脱算法对k值的依赖。在今后的工作中仍要对该算法进行进一步优化，在确保检测率提升的同时，降低误检率与时间复杂度。