0 引言

　　聚类分析是将海量的数据划分为有意义或者有用的组（簇）。在同一簇中的数据相似度较高，不同的簇中数据差别比较大。聚类分析主要基于距离进行分析，它是一种无监视的学习训练方式。

　　K-means聚类算法是基于划分的经典算法，但存在难以确定初始聚类中心值、受噪声及孤立点影响较大的缺点[1]。基于此，很多学者研究提出了不同的改进K-means聚类算法的方法。参考文献[2]把相互距离最远的K个高密度区域的点作为初始聚类中心点；参考文献[3]利用密度指针初始化聚类中心，从而从真实聚类中心中选取数据库初始化聚类中心；参考文献[4]利用密度和最近邻的思想来寻找初始聚类中心；参考文献[5]基于最优划分初始聚类中心，该算法首先对数据样本进行划分，根据划分样本的分布特点确定初始聚类中心；参考文献[6]利用伪随机数产生初始聚类中心，但聚类数据庞大时，聚类效果不容乐观。参考文献[7]通过对样本数据进行阈值分层快速确定K-means算法的聚类数搜索范围及其上限，利用新的聚类有效性指标评价聚类后类内与类间的相似性程度，从而在聚类数搜索范围内获得最佳聚类数。

1 聚类分析的相似性度量和准则函数

　　1.1 相似性度量

　　聚类分析是依据对象两两之间的相似(或差异)程度来划分类的，而这相似程度通常是用距离来衡量的[8]。最广泛使用的距离计算公式是欧氏距离：

　　其中，i=(xi1，xi2，…，xip)，j=(xj1，xj2，…，xjp)。

　　1.2 准则函数

　　聚类结果的质量可以由聚类准则函数来判断，若准则函数选的好，质量就会高；反之，质量达不到要求时，则须反复运行聚类过程[9]。一般的聚类准则函数有以下3种：(1)误差平方和准则；(2)加权平均平方距离和准则；(3)加权类间距离和准则。

2 K-means聚类算法分析

　　2.1 K-means算法过程

　　K-means聚类的算法流程如下：

　　输入：含有n个对象的数据集X={xi|xi∈Rd，i=1，2，…，n}，聚类的个数k。

　　输出：k个类W1，W2，…，Wk。

　　(1)从数据集X中随机选取k个初始聚类中心c1，c2，…，ck。

　　(2)依据初始聚类中心c1，c2，…，ck对数据集进行划分，划分根据以下原则：若dij(xi，cj)<dim(xi，cm)，其中dij(xi，cj)是xi与cj的欧式距离，m=1，2，…，k，j=1，2，…，k，j≠m，i=1，2，…，n，则将xi划分到类cj。

　　(3)依据公式，ni为以聚类Ci为中心数据对象的个数，重新计算类的质心。

　　(5)输出聚类结果。

　　K-means聚类算法的流程如图1所示。

　　2.2 K-means算法缺点

　　(1)K-means算法需要首先设定K值，而算法运算中K是一个敏感值，不同的K值可能会造成不同的运算结果。

　　(2)对于一些噪声和孤立的数据较为敏感。

　　(3)簇的平均值只有被定义才能使用，这不利于处理一些有特殊属性的数据。

　　2.3 K-means算法的改进

　　(1)改进初始值K，尽量减少人工干预

　　利用类间相异度与类内相异度来确定最终的K值，具体分3步来实现：首先，选取数据集合的中间点即所有数据集合的平均值，利用欧几里得距离计算公式，计算出距离中间点最远距离的对象N1，再计算出与N1距离最远的对象N2，筛选出初始聚类中心。其次计算剩余数据对象与数据中心集合间的距离，取最小距离D，计算聚类中心之间的距离，找出最小距离C，如果D<C，则将对象放入到最小距离的聚合中，否则将其纳入初始聚合中心，生成新的聚合中心，后面的数据依次与聚合中心间最小距离与D对比，循环所有数据，最终形成聚类中心集。最后，采用类间相异度与类内相异度来确定最终的聚类个数K值。

　　类内的相异程度DOC：

　　类间相异度DAC：

　　其中，nc表示聚类的数目，mi表示类Cj中心，xkj表示Cj中的第k个数据对象的第j个属性值，d(mi，mj)表示Ci与Cj间的欧几里得距离，表示类中第j个属性值。

　　改进后的计算方法如下：

　　输入：含有n个对象的数据集X={xi|xi∈Rd，i=1，2，…，n}。

　　输出：k个类W1，W2，…，Wk。

　　①对聚类中心进行初始化，获得3个聚类中心。根据公式计算出第1个聚类中心m0，再根据欧几里得距离计算出与m0最远的数据对象作为第2个聚类中心m1，最后计算出与m1距离最远的数据对象当成第3个聚类中心m2。

　　②根据欧几里得公式计算数据集和聚类中心的距离，归类所有数据，重新计算聚类中心。

　　③计算剩余数据对象与聚类中心的最小距离D及聚类中心之间的最小距离C， 计算出此时的类内相异度DOC_old 和此时的类间相异度DAC_old。

　　④如果D>C，则把这个数据对象作为新的聚类中心，并且计算新的类内相异度DOC_new和新的类间相异度DAC_new，运行步骤⑤；否则转到步骤⑥。

　　⑤如果DOC_new<DOC_old且DAC_new>DAC_old则产生新类，转到步骤②重复步骤②～⑤；否则恢复状态，执行步骤⑥。

　　⑥取下一个类Wi，如果没有新的类，则转到步骤⑦；否则反复执行步骤②～⑤。

　　⑦输出聚类结果。

　　(2)对噪声和孤立点处理能力的改进

　　有时孤立点或噪声具有入侵特征，容易干扰 K-means算法的聚类结果，这里改进原始算法来消弱噪声和孤立点的影响。对于数据集中的所有点i，计算出每一点与剩余点的距离和Si，同时计算出距离均和H，当Si>H时，则点i被当做孤立点处理。其中n为样本数据，d为数据维数。计算如下：

　　算法描述如下：

　　①输入数据集，利用上述公式计算每一Si和H；

　　②对于每一点i，如果Si>H，则将i作为孤立点；

　　③删除孤立点，获得新的数据集。

3 改进算法在入侵检测系统中的应用及仿真分析

　　针对于入侵检测系统的缺陷,给出了基于改进算法的入侵检测模型流程，如图2所示。

　　系统检测的对象是网络日志中的数据。先做标准化处理，再进行聚类分析。通过筛选孤立点和改进聚类中心从而提高聚类的准确性。接着进入决策报警分析系统。根据聚类的结果甄别具有攻击特征的记录，一旦发现潜在威胁马上启动报警系统，阻止相关攻击的进一步操作，并报告网络管理者，与此同时挖掘其他的潜在特征，为以后判断攻击提供必要的依据。若没有发现攻击行为则继续监视网络动态。对网络日志文件进行标准化的同时，也将其存入历史数据库中。并进行标准化处理和特征挖掘，进而数据匹配分类，构建成分类器。在分类器的反复训练下可从这些记录中挖掘出正常和非正常行为，并存入到规则库中，作为今后判断入侵行为的决策机构。

　　表1列出的是20条网络连接记录的特征数据。其中，count表示目标主机与当前连接相同的次数；SY_error表示SYN错误连接所占的百分数；same_srv表示目标端口相同连接的百分数；Dif_srv表示目标端口不同连接的百分数；Srv_count表示目标主机与当前连接相同的次数；Srv_serror表示SYN连接错误的百分数；Rv_dif_host表示目标端口不同连接的百分数[10]。本文主要对三维数组（count，Srv_serror，Srv_count）进行分析。三组特征数据的空间分布图如图3所示。

　　这个三维数组基本显示了数据是否具有攻击特征。通过分析这3个参数可以区分攻击行为、异常行为和正常行为。当目标端口与当前连接相同的次数大于15次，并且主机出现错误SYN连接的百分数大于85％，目标端口与当前连接相同次数大于25次时认为是攻击行为；若目标端口与当前连接相同的次数大于6次，并且主机出现错误SYN连接的百分数大于75％，目标端口与当前连接相同次数大于6次时认为是异常行为；其他则认为是正常行为。

　　采用传统的 K-means 算法聚类分析3组数据后将20条数据信息分为3类：记录3为攻击行为(即图4中圆形区域)；记录4，5，6，12，13，19，20为异常行为(即图4中椭圆区域)；其余的记录为正常行为(即图4中矩形区域)。根据上述3种行为的特征，可以将攻击、异常和正常行为区分开来。传统K-means 算法却不能进一步分析异常行为是否有攻击特征。传统K-means 算法对实验数据聚类分析的空间结果如图4所示。

　　改进算法会分离出记录3（孤立点），并判断其为攻击行为，如图5中圆形区域。改进的K-means 算法将剩余的19条记录聚类为三部分，记录4，5，6，12，13，19，20为异常行为(如图5中椭圆区域)，其中5，19接近于攻击行为(如图5中正方形区域)。其余的记录为正常行为。改进算法有效地提高了检测的准确率。改进的K-means 算法对实验数据聚类分析的空间结果如图5所示。

4 总结

　　本文简单介绍了K-means算法，详细阐述了对算法的改进，针对聚类算法中心个数难以确定的问题，本文改进了传统K-means聚类算法中心个数确定的方法，提出了一种新的中心个数确定算法。同时对传统K-means算法进行进一步的改进，以减少数据中噪声点和孤立点对聚类精度的影响。并将传统K-means算法和改进的K-means算法应用于入侵检测系统中。实验结果发现，基于改进的K-means算法的入侵检测系统具有更好的入侵检测效果，改进算法不仅降低了关键参数的敏感性，提高了区分精度，还在一定程度上提高了网络入侵检测的检测率，降低了误检率。

参考文献

　　[1] 曹永春，蔡正琦，邵亚斌.基于K-means的改进人工蜂群聚类算法[J]．计算机应用，2014，34(1)：204-207.

　　[2] 傅德胜，周辰.基于密度的改进K均值算法及实现[J].计算机应用，2011，31(2)：432-434．

　　[3] 牛琨，张舒博，陈俊亮．融合网格密度的聚类中心初始化方案[J]．北京邮电大学学报，2007，30(2)：6-10．

　　[4] 张文明，吴江，袁小蛟.基于密度和最近邻的K-means文本聚类算法[J].计算机应用，2010，30(7)：1933-1935.

　　[5] 崔斌，卢阳.基于不确定数据的查询处理综述[J]．计算机应用，2008，28(11)：2729-2731.

　　[6] KOLEN J F，HNTCHESON T.Redneing the time complexityof the fuzzy c-means algorithm[J]．IEEE Transactions on Fuzzy Systems，2002，10(2)：263-267.

　　[7] 王勇，唐靖，饶勤菲，等.高效率的K-means最佳聚类数确定算法[J]．计算机应用，2014，34(5)：1331-1335.

　　[8] 吕明磊，刘东梅，曾智勇.基于改进的K-means算法的图像检索算法[J]．计算机应用，2013，33(S1)：195-198.

　　[9] 雷小锋，谢昆青，林帆，等.一种基于K-means局部最优性的高效聚类算法[J]．软件学报，2008，19(7)：1683-1692.

　　[10] 高红艳，刘飞.基于局部相似性的K-means谱聚类算法[J]．小型微型计算机系统，2014，35(5)：1133-1134.