维普资讯 http://www.cqvip.com ２ＯＯ８牵 期年９月 Ｊｏｕｒｎａｌ ｏｆ Ｓｏｕｔｈ－Ｃｅ耋ｎｔ塞ｒ一ａ墨ｌＵ薹ｎｉ奎ｖｅ薹ｒｓ篓ｉｔｙｆｏｒ！Ｎ篓ａｔ鍪ｉｏｎａ ｌｉｔｉｅｓ（Ｎａｔ．Ｓｃ ｉ．Ｅｄ ｉｔｉｏｎ）： ＶｏＩＳ．Ｚｅｐ７．Ｎ２０ｏ０．３８ 改进ｋ均值聚类算法在网络入侵检测中的应用研究 覃 俊 ，易云飞 ，李 林 （１中南民族大学计算机科学学院，武汉４３００７４；２河池学院计算机与信息科学系，河池５４６３００） 摘要针对ｋ－ｍｅａｎｓ算法事先必须获知聚类数目以及难以确定初始中心的缺点，提出了一种改进的ｋ－ｍｅａｎｓ聚 类算法．改进后的算法首先使用了复合形和粒子群算法来选取聚类的初始中心点，然后使用志一ｍｅａｎｓ算法快速收敛 获取聚类结果．实验表明：把改进后的算法用于网络入侵检测系统中，可以提高不需指导的异常检测的检测率，降 低误检率． 关键词 复合形法；粒子群优化算法；五一ｍｅａ￣ｓ算法；入侵检测 中图分类号ＴＰ３９３．０８文献标识码Ａ文章编号１６７２－４３２１（２００８）０３—００７５—０４ Ｒｅｓｅａｒｃｈ ｏｆ Ｉｍｐｒｏｖｅｄ ｋ－Ｍｅａｎｓ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ ｉｎ Ｎｅｔｗｏｒｋ Ｉｎｔｒｕｓｉｏｎ Ｄｅｔｅｃｔｉｏｎ Ｑｉｎ Ｊｕｎ ，Ｙｉ Ｙｕｎｆｅｉ ，Ｌｉ Ｌｉｎ （１ Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｓｏｕｔｈ—Ｃｅｎｔｒａｌ Ｕｎｉｖｅｒｓｉｔｙ ｆｏｒ Ｎａｔｉｏｎａｌｉｔｉｅｓ，Ｗｕｈａｎ ４３００７４，Ｃｈｉｎａ； ２ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ，Ｈｅｃｈｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｈｅｃｈｉ ５４６３００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ Ｉｎ ａｌｌｕｓｉｏｎ ｔｏ ｔｈｅ ｄｉｓａｄｖａｎｔａｇｅ ｏｆ ｈａｖｉｎｇ ｔｏ ｏｂｔａｉｎ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ｏｆ ｄａｔａｓｅｔｓ ｉｎ ａｄｖａｎｃｅ ａｎｄ ｔｈｅ ｓｅｎｓｉｔｉｖｉｔｙ ｔｏ ｓｅｌｅｃｔｉｎｇ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｅｒｓ ｉｎ ｔｈｅ ｋ－ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ，ａｎ ｉｍｐｒｏｖｅｄ ｋ－ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｃｏｍｐｌｅｘ－Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ ｉｓ ｐｒｏｐｏｓｅｄ．Ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ｏｆ ｄａｔａ ＳｅｔＳ ａｎｄ ｔｈｅ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｅｒｓ ｉｎ ｔｈｅ ｋ－ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｈａｓ ｂｅｅｎ ａｓｓｉｇｎｅｄ ｂｙ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｔｈｒｏｕｇｈ ｔｈｅ Ｃｏｍｐｌｅｘ—Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ－ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ＤＲ ａｎｄ ｒｅｄｕｃｅ ｔｈｅ ＡＲ ｏｆ ｔｈｅ Ｕｎｓｕｐｅｒｖｉｓｅｄ Ａｂｎｏｒｍａｌ Ｄｅｔｅｃｔｉｏｎ ｉｎ ＮＩＤＳ（Ｎｅｔｗｏｒｋ Ｉｎｔｒｕｓｉｏｎ Ｄｅｔｅｃｔｉｏｎ Ｓｙｓｔｅｍ）． Ｋｅｙｗｏｒｄｓ ｃｏｍｐｌｅｘ ｍｅｔｈｏｄ；ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ；ｋ－ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ；ＩＤＳ 根据数据分析手段的不同，常用的入侵检测方 法［１ ］可以分为滥用检测和异常检测．滥用检测是利 用已知的系统缺陷和已知的入侵方法进行入侵活动 的行为特征来检测入侵．异常检测模型把用户习惯 行为特征存储在特征数据库中，然后将用户当前行 为与特征数据库中的特征进行比较，若两者偏差足 够大，则说明发生了人侵．这种方法的优点是能检测 未知的攻击类型，适应性强．异常检测又分为需指导 的异常检测和不需指导的异常检测两种．当今，不需 的检测，其优点是准确度很高，缺点是误检率和漏检 率较高．异常检测是指利用定量的方式来描述可接 受的行为特征，以区分和正常行为相违背的、非正常 收稿日期 ２００８．０６—２３ 作者简介覃ｃｏｒｎ ￣（１９６８一），女，副教授，博士，研究方向：数据挖掘，智能计算和网络安全，Ｅ—ｍａｉｌ：ｗｒｊｑｊ＠ｈｏｔｍａｉｌ． —基金项目 国家民委自然科学基金资助项目（ＰＭＺＹ０６００４）；中南民族大学大学生科研创新基金项目（ｃｘｃｙ２００８００３ｙ）；河 池学院自然科学基金资助项目（２００７Ｂ—Ｎ００４） 维普资讯 http://www.cqvip.com ７６ 中南民族大学学报（自然科学版） 第２７卷 指导的异常检测方法的入侵检测技术已经成为研究 的焦点．该技术可以利用不完全正常的训练数据，只 需要未加工的网络原始数据作为输入，就能发现其 中存在的攻击数据．现有的入侵检测系统大都采用 专家系统或基于统计的方法，这都需要较多的经验， 数据挖掘方法的优势在于它能从大量数据中提取人 们感兴趣的、事先未知的知识和规律，而不依赖 经验． ｋ－ｍｅａｎｓ聚类算法 可以用于不需指导的异 常检测技术中，并且可以在未标记的数据上进行．它 将相似的数据划分到同一个聚类中，而将不相似的 数据划分到不同的聚类，并为这些聚类加以标记表 明它们是正常还是异常，然后将网络上数据划分到 各个聚类中，根据聚类的标记来判断网络数据是否 异常．然而该算法也存在着不足之处：忌个初始聚类 中心点的选取对聚类结果有较大的影响，同时由于 该算法是采用梯度法求解极值，结果可能只是局部 而非全局最优．为了克服这些缺陷，有文献结合遗传 算法对愚均值算法进行改进，如，Ｍａｌｉｋ等采用了聚 类中心的浮点编码方式，并设计了浮点数交叉和变 异算法，从而提高了遗传聚类算法的搜索效率＿＿３］．但 是，实验表明，当样本数目、维数和类别数较大时，这 些算法常常过早的收敛于局部极优点的现象．本文 提出了一种基于粒子群和复合形法的改进的愚均值 聚类算法（Ｃｏｍｐｌｅｘ—ＰＳＯ ａｎｄ ｋ－ｍｅａｎｓ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ），简称ＣＯＰＳＯＫ算法．改进后的是一ｍｅａｎｓ 算法可以选择适当的初始聚类中心点，同时也能得 到更好的聚类结果．实验表明，把改进后的算法用于 网络入侵检测系统中，可以提高不需指导的异常检 测的检测率，降低误检率． １尼一ｍｅａｎｓ聚类算法 ｋ－ｍｅａｎｓ算法的基本思想是，以忌为参数，把ｎ 个对象划分成Ｃ个簇．以使簇内具有较高的相似度， 而簇间的相似度较低 ］．相似度的计算根据簇的重 心，其值用簇中各对象的平均值来计算．首先从数据 集中随机选取ｃ个点作为初始聚类中心，然后对剩 余的每个对象，根据其与各个簇中心的距离，将它赋 予最近的簇．重新计算每个簇的平均值来找簇的重 心，如此反复，直到准则函数收敛为止．通常采用平 方误差准则，其定义如公式（１）所示： ｃ ｔ，一 Ｉｌ ｚ｛ ）＿ ， （１） 其中， 一１，２，…，ｃ； ，是Ｃ个聚类的中心，它的值 为簇ｃ 的均值，即： ，一音 ～１三 ． （２） Ｊ—ｉ ｋ－ｍｅａｎｓ算法的处理过程： ①从 个数据对象集｛３－２＂ ， ：，…，ｚ ｝中随机选 取是个对象｛Ｙ ， 。，…， ｝为初始聚类中心； ②计算各对象到中心对象的距离，并根据最小 距离重新划分； ③更新簇的平均值，即计算每个簇中对象的平 均值； ④循环②到③，直到每个聚类不再发生变化时 算法终止． 从算法流程不难看出，该算法得到的聚类结果 受初始时聚类中心对象的选取的影响很大，随机选 取的不同的初始值可能导致不同的聚类结果，甚至 可能出现得不到有意义的聚类结果的情况．另外，由 于该算法是采取梯度法求解极值，而梯度法的搜索 方向是沿能量减小的方向进行的，所以得到的结果 往往是局部最优而非全局最优． ２粒子群复合形算法 ２．１ 复合形法 复合形法 （Ｃｏｍｐｌｅｘ Ｍｅｔｈｏｄ）是一种常用的 直接搜索方法，该算法只需通过直接比较和利用个 设计点的约束函数和目标函数本身的值来进行搜 索，每一步都寻找一个较好点取代最差点，若未找到 就剔除最差点．该算法局部搜索能力很强，但结果全 局性较差．复合形法的基本思想是：在解空间中随机 地给出五个初始点ｚ。， 一， ，称为初始原形，每进 行一步都对这是点以目标函数值ｆ（ｘ。），ｆ（ｘ ），…， ｆ（ｘ ）为据排序，假设函数值最大的点ｚ 为最差点， 函数值最小的点 为最好点，然后分别使用公式 （３）和（４）求除最差点外其余各点的中心点Ｘ。和反 射点 （检查ｚ 是否可行，若不可行，令ａ一号，再 由公式（４）计算 ，直到可行为止），当ｆ（ｘ ）＜厂（ｚ ） 时，由 代替Ｘ ，从而得到一个新的复形，如此循环 计算直到满足以下终止条件： １ ｋ－１ 一３１，２７ｏ一７一西 ∑Ｘｉ厶．・ （３）， １１ ｚ。一ｚ０＋ａ（ｘｏ－－Ｘ ）． （４） ２．２粒子群算法 维普资讯 http://www.cqvip.com 第３期 覃 俊，等：改进ｋ均值聚类算法在网络入侵检测中的应用研究 ７７ 粒子群算法（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ， ＰＳＯ）是Ｋｅｎｎｅｄｙ与Ｅｂｅｒｈａｒｔ于１９９５年提出的一种 全局优化算法，该算法的基本思想来源于对鸟群简 化社会模型的研究及行为模拟，其中的每个个体充 分利用群体的与自身的智能，不断地调整学习，最终 得到满意解 ¨．在ＰＳＯ算法中，每个备选解都是搜 索空间中的一个“粒子”，每个粒子根据它自身的“经 验”和粒子群的最佳“经验”，在问题空间中向更好的 位置“飞行”，如此循环搜索直到发现最优解． 在基本ＰＳ０算法中，粒子群在一个Ｄ维空间中 搜索，粒子的总数为 ，粒子群的初始位置和速度随 机产生，然后按照公式（５）和（６）进行迭代计算，直到 满足终止条件． 一 ＋ｃｌｒａｎｄ１（）×（ ｄ—ｚ ）＋ Ｃｚｒａｎｄ２（）×（户 一ｚ ）． （５） 一 ＋ ，１≤ ≤ ，ｌ≤ ≤Ｄ． （６） 式中， 表示第志次迭代后粒子ｉ飞行速度矢量 的第 维分量；ｚ 表示第七次迭代后粒子 位置矢量 的第ｄ维分量；Ｐ 表示粒子ｉ个体最好位置的第ｄ维 分量；户 表示群体最好位置的第ｄ维分量； 为惯性 权重函数；ｆ１，ｆ２表示权重因子；ｒａｎｄｌ（），ｒａｎｄｚ（）分 别为产生［Ｏ，１］的随机数的随机函数． ２．３粒子群复合形算法 粒子群算法源于对鸟群觅食过程中的迁徙和群 居的模拟，系统初始化为一组随机解，通过迭代搜寻 最优值，粒子在解空间中追随最优的粒子进行搜索． 该算法以种群行为而不是适者生存原则来激励粒子 的运动．每个潜在解与粒子运行速度相联系，该速度 根据自身和种群的经验来调整大小、方向，总是希望 朝着更好的方向发展．在搜索过程中，全局搜索能力 与局部搜索能力的平衡关系对于算法的成功起着至 关重要的作用．复合形法是一种常用的直接搜索方 法，该算法局部搜索能力很强，但结果全局性较差． 算法中的每一步都寻找一个较好点取代最差点，若 未找到就剔除最差点．本文将复合形法作为一个算 子对粒子群算法中的粒子进行运算，以充分发挥两 种算法的优点，在更有利于最优搜索的基础上，构建 粒子群复合形算法． ２．４ 基于粒子群和复合形算法的改进ｋ－ｍｅａｎｓ 算法 本文提出的基于复合形和粒子群算法的改进ｋ— ｍｅａｎｓ聚类算法的基本思想是，首先利用复合形和 粒子群算法寻找最优的五个初始聚类中心点，然后 利用ｋ－ｍｅａｎｓ算法找到聚类结果，最后把找到的结 果输出即可．算法中待求解的向量空间中每个向量 被描述为一个点，在数据集中的每个项目被描述为 解空间中的一个维，整个数据集作为一个带很多点 的空间来描述，每个点映射为一个粒子，整个数 据集就是一个粒子群． 基于复合形和粒子群算法的改进的志一ｍｅａｎｓ算 法的流程如下： ①从ｎ个数据对象集｛ ，ｚ ”，ｚ ）中随机选 择不同的对象，每个对象当作一个初始粒子分别用 公式（５）和（６）来计算其速度和位置值； ②在①的处理过程中，把复合形法作为其中的 一个算子对其中的每个粒子进行运算，找出初始的五 个初始聚类点； ③利用②得到的志个初始聚类点，使用传统的 ｋ－ｍｅａｎｓ算法进行聚类； ④输出志个聚类中心及其所划分的集合． ３实验分析及结论 聚类算法能够用于异常检测，要求训练集数据 中异常行为的数据占正常行为数据的比例为３ ～ １０ ，当聚类簇集合中包含的异常行为记录大于训 练集异常记录的比例时，称此集合为异常行为集合， 其余为正常行为集合．异常检测是通过训练过程建 立类别模式，然后将检测数据与类别模式逐一比较， 一般用检测率和误检率评价检测结果． 实验选用的数据集是测试数据ＫＤＤ ｃｕｐ９９数 据中的“ｋｄｄｃｕｐ ｄａｔａ １０ ｐｅｒｃｅｎｔ”，该数据集共有 ４９４ ０２１个记录，其中正常记录数据是：９７ ２７８，其余 ３９６ ４７３的是异常数据，异常数据分为４类：Ｄｏｓ （Ｄｅｎｉａｌ ｏｆ Ｓｅｒｖｉｃｅ）、Ｕ２Ｒ（Ｕｓｅｒ ｔｏ Ｒｏｏｔ）、Ｒ２Ｌ （Ｒｅｍｏｔｅ ｔｏ Ｕｓｅｒ）和Ｐｒｏｂｅ．为了满足聚类算法能用 于异常检测的条件，从整个检测数据集中提取４组 数据作为实验用数据，每组数据中包含３０ ９１０条记 录，其中２９ ９８６条正常数据，９２４条异常数据，异常 数据占正常数据的比例为３．Ｏ８ ，符合正常数据的 数目要远多于入侵数据数目的要求．由于所选择的 数据集“ｋｄｄｃｕｐ．ｄａｔａｌＯ——ｐｅｒｃｅｎｔ”中Ｕ２Ｒ异常数 据个数只有５Ｏ多个，没有必要进行同一入侵类型检 测．所以前３组数据集分别对应的是只包含Ｄｏｓ， Ｒ２Ｌ，Ｐｒｏｂｅ入侵的数据，第４组数据集包括所有４ 类入侵数据．对于每个ＴＣＰ／ＩＰ连接，除了一些基本 属性外，还有利用领域知识扩展了一些属性．每个连 接有４１种符号型和数值型的特征属性．在实验过程 维普资讯 http://www.cqvip.com
７８ 中南民族大学学报（自然科学版） 第２７卷 中只选取数据中的１５种关键属性进行聚类，其中１２ 个数值属性，３个字符属性．为了评价分析结果，采 操作系统为ＷｉｎＸＰ，开发平台为ＶＣ＋ ６．０）分别实 现传统的ｋ－ｍｅａｎｓ算法和本文提出的ＣＯＰＳＯＫ算 用检测率和误检率来衡量． 法所得的实验结果分别如表Ｉ和表２所示． 用实验环境（内存为５１２Ｍ，ＣＰＵ为Ｐ４ ２．４ＧＨｚ， 表１ ｋ－ｍｅａｎｓ算法实验结果 Ｔａｂ．１ Ｒｅｓｕｌｔｓ ｏｆ ｔｈｅ ｋ—ｍｅａｎｓ 从２个表不难看出，Ｃ０ＰＳ０Ｋ算法所得实验结 果的误检率都比ｋ－ｍｅａｎｓ算法的低，检测率要高．究 参考文献 其主要原因，是文章采用的算法改进策略，即，将复 合形和粒子群算法来确定聚类的最佳数目以及选取 ［１］ Ｘｕ Ｒｕｉ，Ｗｕｎｓｃｈ Ｄｏｎａｌｄ．Ｓｕｒｖｅｙ ｏｆ ｃｌｕｓｔｅｒｉｎｇ 聚类的初始中心点，这正好弥补了ｋ－ｍｅａｎｓ算法的 ａｌｇｏｒｉｔｈｍｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｕｒａｌ 不足之处．实验表明，本文提出的算法是有效的． Ｎｅｔｗｏｒｋｓ，２００５，１６（３）：６３４—６７８． ［２］ Ｘｉａ Ｓｈｉｘｉｏｎｇ，Ｌｉ Ｗｅｎｃｈａｏ，Ｚｈｏｕ Ｙｏｎｇ，ｅｔ ａ１． ４ 结束语 Ｉｍｐｒｏｖｅｄ ｋ－ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｓｏｕｔｈｅａｓｔ Ｕｎｉｖｅｒｓｉｔｙ（Ｅｎｇｌｉｓｈ Ｅｄｉｔｉｏｎ），２００７，２３ （３）：４３５—４３８． 聚类算法被引入到入侵检测中，主要运用在异 ［３］ Ｍａｕｌｉｋ Ｕ，Ｂａｎｄｙｏｐａｄｈｙａｙ Ｓ．Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ—ｂａｓｅｄ 常检测技术中．在实现系统自动检测，预防未知攻击 ｃｌｕｓｔｅｒｉｎｇ ｔｅｃｈｎｉｑｕｅ［Ｊ］．Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，２０００，３３ 方面具有巨大的优势．用聚类方法建立的系统不需 （９）：１ ４５５—１ ４６５． 要任何事先标记信息的数据记录，它在保持较低误 ［４］ 谷保平，许孝元，郭红艳．基于粒子群优化的五均值算 检率的同时可以有很高的检测率．ｋ－ｍｅａｎｓ算法是 法在同络入侵检测中的应用ＥＪ］．计算机应用，２００７，６ 一种简便实用的无监督学习算法，但是该算法通常 （２７）：１ ３６８—１ ３７０． 受初始的聚类中心点的选取的影响很大，特别当出 Ｅ５３ 赵锋，薛惠锋，王 伟．基于复合形遗传算法的七一 现异常点的情况时，该算法将很难得到理想的聚类 ｍｅａｎｓ优化聚类方法［Ｊ］．航空计算技术，２００６，３６（５）： 结果．针对该算法的一些不足之处，本文引入了复合 ５９—６１． 形和粒子群算法来选取聚类的初始中心点，改进传 ［６］ 沈显君，王伟武，郑波尽，等．基于改进的微粒群优化算 法的Ｏ一１背包问题求解［Ｊ］．计算机工程，２００６，３２（１８）： 统的ｋ－ｍｅａｎｓ聚类算法．实验表明，把改进后的算法 ２３—２４． 用于网络入侵检测系统中，可以有效提高不需指导 ［７］ 杨 勋，王江晴．求解聚类问题的混合ＰＳＯ算法设计 的异常检测的检测率，降低误检率，进一步的研究计 ［Ｊ］．微电子学与计算机，２００７，２４（１０）：４３—４５． 划是如何优化算法，节省程序执行开销．
