【摘要】针对传统K-means算法对初始聚类中心选取的问题，提出了基于数据样本密度和距离来选取初始聚类中心的改进K-means算法，该算法保证了初始中心点集的第一点为确定的（最大密度点），在基于距离最远的其他中心点搜索过程中，得到的中心点也基本上是确定的，消除了初始中心点选择的随机性，同时保证了获得较高质量的初始中心点。理论分析和实验结果表明：改进的k-means算法是一种有效的入侵检测方法，根据此方法设计的入侵检测系统是有效可行的。
【关键词】K-means算法；初始聚类中心；入侵检测
1.引言
聚类分析是源于许多研究领域，包括数据挖掘，统计学，生物学，以及机器学习[1]。设想要求对一个数据对象的集合进行分析，但与分类不同的是，它要求划分的类是未知的。那么我们就需要聚类分析中的基于多种不同思想的聚类算法，主要有基于划分的算法、基于层次的算法、基于密度的算法、基于网络的算法和基于模型的算法等。这些算法都能取得不错的聚类效果，其中应用最多且算法逻辑思维比较简单的就是基于K-means算法。
1967年，J.B.MacQueen提出了K-means算法，是一种基于质心的经典聚类算法。K-means算法以k为参数，把n个对象分为k个簇，以使簇内具有较高的相似度，而簇间的相似度较低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。K-means算法的处理流程如下：首先，随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。
2.K-means算法的改进
无论是原始K-means算法还是使用了聚类准则函数的K-means算法，他们有一个共同的特点：在算法的初始阶段都需要随机的选取k个点作为初始聚类中心点，然后在此基础上进行迭代。
2.1 k-means算法初值选取的现有方法
针对初值选取的问题，目前主要有以下几种选取方法[3][4]：
①任意的选取k个样本数据作为初始聚类中心。
②把全部混合样本直观地分成k类，计算各类均值作为初始聚类中心。
③依据经验选取有代表性的点作为初始聚类中心。
④通过“密度法”选择代表点作为初始聚类中心。
⑤由(k-1)类聚类问题解出k类问题的代表点。
⑥采用遗传算法或者免疫规划方法进行混合聚类。
⑦进行多次初值选择、聚类，找出一组最优的聚类结果。
⑧按最大最小距离聚类法中寻找聚类中心的方法确定初始聚类中心。
⑨聚类中心由原来的点延伸到一条线段，这种选取方法可以避免类间有干扰点的情况。
2.2 新的初始聚类中心选取方法
直观上，类中心应处于所代表类的中心部分，所有属于该类的样本都在其周围某一邻域内。因而在空间上，类中心所处的位置样本点分布密度较大。同时，在样本点密度连续的范围内，应该只具有一个聚类中心，否则就会出现两个类交错在一起的情况。因此，初始类中心的选择应该满足两个条件：
①类中心所处位置样本点密度较高；
②类中心之间的距离应尽可能地大。
因此，在初始点的选择上，应考虑两个因素：密度因素和聚类因素。由于类中心所处位置总是在样本比较密集的地方，因而总是存在某些样本距离类中心比较近。如果能够找到这些样本并作为初始类中心，就能避免k-means算法因为初始化不合理而出现的种种问题。
①样本点密度的度量
对于一个数据集，当样本呈团状分布时，根据一般常识，某个样本点周围其它样本点越多时，则该样本点处的样本分布密度就越大，则该样本点对于分类的影响就越大。因此，每个样本点都存在一个分布密度，对于每个样本点xi，其点密度函数定义如下：
2.1
其中zi是一个关于样本点间距离的参数，其定义如下：
2.2
2.3
Pi表示第i个样本点xi对分类影响的程度，Pi越大，样本点xi周围的点越多，样本点xi的密度越大；反之Pi越小，样本点xi周围的点越少，样本点xi的密度越小。
②选择样本点作为初始类中心
通过pi的值可以轻易地找到密度较高的样本点，但还要保证所选择的样本点之间的距离尽可能的大，否则选择的类中心必然会聚集在样本密度最高的区域内。因此，除了第一个类中心可以根据密度的大小来选择外，选择其它类中心时还需要考虑距离的因素。本文使用密度和距离的乘积作为选择的度量。密度和距离的单位不同，直接相乘不具有可比性，因此需要进行归一化处理。对于给定的样本xi，将其到样本点xj（=1，2，…，N）的距离按式2.4进行变换：
2.4
设已选定多个类中心，则在新增类中心时要考虑使它到已有类中心的总的距离较大，同时该样本点的密度也较大。总的来说，就是在剩余的样本中选取xi，使得该样本点的分布密度乘以该样本点到已选聚类中心的归一化距离和wi最大：
2.5
其中（n1，…，nk）是已确定k(k≥1)个初类中心在样本中的序号。
③聚类中心初始化算法执行流程
结合以上两个小节的讨论结果，得到一种新的聚类中心选取算法，算法流程描述如下：
输入：待处理数据集wi，聚类个数K
输出：初始中心点集M
步骤：
步骤1：根据式㈠计算每一个样本的密度；
步骤2：初始中心点集M初始化为空集，即M=｛｝，初始累加参数wi为0，即：wi=0，（i=1，2，…，N）；
步骤3：令j=1，选择密度最大的样本点m1（第v1个点）作为第一个初始中心点，即：
Pv1=Max（Pi），（i=1，2，…，N）；
M=M∪｛m1｝；
步骤4：按㈣式计算已选初始中心点mj到所有样本的归一化距离，累加wi：
wi=wi+Pi，（i=1，2，…，N）；
步骤5：令j=j+1，选择使得wi取得最大值时所对应的样本点mj（第vj个点）（已选作中心点的样本除外）为第j个初始中心点，即：
=max{wi|i=（1，2，…，N），i≠（v1，…vj-1）}，
M=M∪｛mj｝；
步骤6：重复步骤4、步骤5直至找到k个中心点；
步骤7：输出中心点集M，算法结束。
从上述算法可以看出，由于初始中心点集的第一点为确定的（最大密度点），在基于距离最远的其他中心点搜索过程中，得到的中心点也基本上是确定的，消除了初始中心点选择的随机性，同时保证了获得较高质量的初始中心点。
2.3 算法的改进
改进后的k-means算法中，首先根据样本的每个属性在聚类过程中所起的作用的程度不同，利用变异系数赋权法给每一个属性赋一个相应的权值。然后通过一种简洁快速的初始聚类中心选取规则，变随机为有目的地确定了k-means算法的初始聚类中心，消除了初始中心点选择的随机性，同时保证了获得较高质量的初始中心点，解决了k-means算法对初始值敏感、易陷入局部最优的问题。改进的算法描述如下：
输入：待处理数据集，聚类个数K
输出：聚类结果
步骤1：对数据集执行加权处理程序，得到新的数据集；
步骤2：对加权后的数据集执行聚类中心初始化程序，得到K个初始聚类中心；
步骤3：调用跳过随机选取聚类中心的k-means算法进行聚类；
步骤4：输出聚类结果，算法终止。
3.实验设计与研究分析
入侵检测以探测入侵为中心，目的是为系统提供实时发现入侵行为并及时采取相应的防护手段。本章将介绍一种基于聚类的入侵检测系统模型以及数据预处理方法，并在入侵检测经典数据集KDD Cup 1999[5]上进行一系列的实验。
3.1 基于聚类的入侵检测系统模型
入侵检测分为两个阶段：训练阶段和检测阶段：
①训练阶段：输入训练数据，系统自动生成聚类，同时对这些聚类进行标类。
②检测阶段：收集到新的记录后进行标准化处理，计算标准化后的数据到各个
聚类中心的距离，取距离最近的聚类，若该聚类标记为正常类，则该数据为正常数据，否则则认为该数据为异常数据。
以下将介绍一种基于聚类分析的入侵检测系统模型，模型图如图1所示。
它由四个模块组成：数据预处理模块、聚类分析模块、标类模块、检测模块。各个模块的功能如下：
①网络数据收集
网络数据收集是入侵检测的基础，该模块主要是从网络上提取数据进行监视和检测，例如链路层的数据帧、通过网络层的IP包等。本文采用KDD Cup 1999数据集做实验。
②数据预处理模块
在数据预处理模块，主要是把收集到的网络数据进行标准化，转化为适合聚类算法运算的数据格式，同时对数据进行过滤、除噪等操作。
③聚类分析模块
数据经过预处理后，聚类分析模块利用聚类算法对这些数据（一般是连接记录）进行聚类和分类，区分哪些是正常连接记录，哪些是异常连接记录。本文采用第四章中介绍的改进k-means算法进行聚类分析。
④标类模块
数据经过聚类分析模块后，产生若干个簇，每个簇都包含一些连接记录；由于正常连接记录和异常连接记录的特性不同，不具有相似性，因此会被放入不同的簇中。这样就可以进行标记类（簇）的操作。那些包含较多数据的类是正常类，而包含较少数据类则是异常类。
⑤检测模块
在完成对聚类结果的标识后，我们就可以利用标类结果对新来数据进行检测，在不断完善和更新聚类结果的同时快速有效地检测各种入侵行为。计算标准化后的数据到各个聚类中心的距离，选取距离最近的聚类，若该聚类标记为正常类，则判定该数据为正常数据，否则认为该数据为异常数据。
3.2 实验结果与分析
在实验中，选用实验平台Win-
dowsXP，Matlab6.5语言编程环境，Intel Pentium3GHz CPU，1GB内存。评价入侵检测算法时采用两个性能指标其定义如下所示：
3.2
3.3
这两项性能指标充分反映了入侵检测系统的检测能力，能够对系统检测出多少入侵和做出多少不正确的分类做出评价。显然一个好的入侵检测系统应该使DR尽可能得大，而FR则尽可能的小。
在KDD Cup 1999训练数据集中的攻击数据有接近40万条，约占总数的80%，由于无监督入侵检测算法对于数据集中的入侵记录所占的比率十分敏感，如果入侵记录的数量太大，入侵在表现形式上就不会被看做入侵，所以必须首先对数据集进行过滤，选择合适的数据，然后才能进行实验，在现实中，入侵记录所占所有记录的比例在1%到1.5%之间。
试验中聚类数K的变化自由度比较大，具体取值和领域知识强相关，不同应用领域取不同的值才能得到理想的效果，因此不能直观的给出，只能通过实验进行估计。以下将进行K取值估计，改进k-means算法和传统k-means算法性能比较实验。
为了满足实验需要，我们从kdd-
cup.data_10_percent包选取了5个数据集作实验，其中一组训练数据集和四组测试数据集，训练数据集包含30300条数据，其中300条入侵数据，包含了DOS、PROBING、R2L、U2R所有四种类型的入侵数据类型。测试数据集包含10100条数据，100条入侵数据。
为了操作方便，在实验过程中我们只选取数据中的15关键属性进行聚类，其中12个连续属性，3个离散属性。利用以上数据集分别在传统k-means算法和本文改进k-means算法上进行实验，首先使用训练数据进行训练标类，然后依次输入其他四个测试数据集进行测试，对四次测试结果取平均，结果如表1所示。
由表3可知，改进k-means算法的检测率和误检率明显优于传统k-
means算法，同时随着聚类个数的增加，检测率和误检率也随之增大。因为当聚类数目很少时，系统训练之后的异常类也就很少，很多异常的记录被分到了正常的类中，而正常记录很少被分到异常的类中，这就导致系统对异常记录的低检测率，同时也获得了对正常记录的低误检率。而当聚类数增多时，系统训练之后的异常类也随之增多。此时，越来越多的异常记录被标记出来，但同时越来越多的正常记录也被分到了异常类中，系统获得高检测率的同时也不得不忍受高误检率的结果。
前面做了混合入侵类型的实验，系统在聚类数取25左右时获得了最佳检测结果，下面对指定攻击类型单独进行实验。选取8个是测试数据集，每个测试数据集包含5000条数据；而且训练数据集分别只包含50条DOS、U2R、R2L、PROBING入侵攻击数据。
聚类数取25，已知入侵指的是在测试集和训练集中都包含的入侵，未知入侵指的是测试集包含但训练集中没有的入侵。实验结果如表2所示。
由表2和表3可知，无论是已知的单一入侵类型还是未知的单一入侵类型，基于改进k-means算法的入侵检测效果都明显优于基于传统k-means算法的入侵检测效果，而且在对DOS、PROBING入侵攻击的检测都取得了比较高的检测率，但是对U2R和R2L入侵类型的检测效果不理想。出现这种结果的原因一方面是因为数据集中U2R和R2L入侵记录少，在训练时，对这两种类型的处理不太理想，导致后期的检测效果不理想，另一方面是因为U2R和R2L入侵一般通过伪装成合法用户身份进行入侵攻击，使得其表现出来的特征与正常网络数据包非常相似，造成较低的检测率。
在误检率方面，改进算法对单一攻击类型的检测优势。值得注意的是R2L攻击类型的误检率普遍较高。这是因为在训练时，很多R2L入侵记录都混进了正常聚类，而不少正常记录难免就被分到了异常聚类，致使检测阶段时很多正常记录被判定为异常。
在实际环境中，大多数入侵攻击类型都是DOS和PROBING。无论是已知入侵类型还是未知入侵类型，本文算法都取得了良好的检测效果。而对于实际环境中少见的R2L和U2R，本文算法也有检测能力。说明本文入侵检测能够比较有效的检测入侵行为。通过以上分析，基于本文改进的k-means算法应用于异常入侵检测中是可行而且有效的。
4.结论
本文详细介绍了k-means算法的思想原理、流程步骤，针对该算法的初值依赖性提出改进的聚类中心选取算法，获得较高质量的确定的初始聚类中心，消除了经典k-means初始中心选择的随机性，解决了该
（下转第18页）
（上接第14页）
算法对初始值敏感、易陷入局部最优的问题。阐述了基于聚类的入侵检测模型，并在此模型的基础上使用入侵检测数据集KDD Cup 1999对改进k-means算法和经典k-means算法作了对比仿真实验。实验结果表明：不管对存在单种攻击的网络连接记录集还是多种攻击同时存在的网络连接记录集，基于改进k-means算法的入侵检测系统都能够在保持较低的误报率的基础上，很好的检测出记录集中的攻击数据，包括未知类型的攻击数据。本文改进的k-means算法是一种有效的无监督入侵检测方法，根据此方法设计的入侵检测系统是有效可行的。
参考文献
[1]Jiawei Han,Micheline Kamber.数据挖掘概念与技术[M].北京：机械工业出版社,2001.8.
[2]MacQueen J.Some Methods for Classification and Analysis of Multivariate Observations[C].In:Proceedings of the 5thBerkeley Symposium on Mathematical Statistics and Probability.Berkeley,University of California Press,1967:281-297.
[3]U.M.Fayyad,C.Reina and P.S.Bradley.Initialization of iterative refinement clustering algorithms[A].In:Knowledge Discovery and Data Mining.1998:194-198.
[4]R.O.Duda,P.E.Hart.Pattern Classification and Scene Analysis[M].New York.John Wiley and Sons.1973.
[5]http://www.sigkdd.org/kddcup/index.php.
作者简介：
薛京花（1984—），女，湖南益阳人，硕士研究生，现就读于中南林业科技大学计算机与信息工程学院，研究方向：网络与信息系统。
刘震宇（1969—），女，湖南衡阳人，副教授，现供职于中南林业科技大学计算机与信息工程学院，研究方向：网络与信息系统。
崔适时（1988—），男，湖南益阳人，硕士研究生，现就读于中南林业科技大学计算机与信息工程学院，研究方向：网络与信息系统。