２０１１年９月 广西师范学院学报：自然科学版 Ｊｏｕｒｎａｌ ｏｆ Ｇｕａｎｇｘｉ Ｔｅａｃｈｅｒｓ Ｅｄｕｃａｔｉｏｎ Ｕｎｉｖｅｒｓｉｔｙ：Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ Ｓｅｐ．２０１１ ＶＯＩ．２８ ＮＯ．３ 第２８卷第３期 文章编号：１００２—８７４３（２０１１）０３—００８２—０６ 基于聚类与分类混合算法的应用研究 谢雄程，刘之家 （广西师范学院计算机与信息工程学院，广西南宁５３０００１） 摘 要：虽然聚类与分类算法的研究应用已很普遍，但在入侵检测领域把二者结合起来进行研究分析的情况 并不普遍，因此，提出了一个分层的聚类与分类算法混合模型，并通过Ｋ—Ｍｅａｎｓ聚类算法、改进的差分进化算法与 最近相邻分类算法为例对入侵数据集样本进行聚类与分类，最后得出有效的实验结果。 关键词：聚类；Ｋｍｅａｎｓ算法；差分进化；人侵检测 中图分类号：ＴＰ３９３ 文献标识码：Ａ Ｗｏｒｌｄ Ｗｉｄｅ ｗｅｂ（ｗｗｗ）经过多年的发展，许多与之相关的研究领域也随之产生，但伴随而来的则 是无数的安全威胁问题。对Ｗｅｂｓｉｔｅ的入侵是许多网络入侵威胁中的一种，入侵行为的特点表现为在 网络中异常、不正确、不恰当的事件发生。这里的异常指的是对网络主机非法访问，即违反主机访问策 略的事件行为。因此，网络安全受到越来越大的关注。为了防止这种网络的非法访问的行为，用于检测 各种入侵行为的入侵检测系统就应运而生了。 本文的研究目的是在基于入侵数据的基础上找到一种能自动建立分类并用于分析入侵行为的方 法。具体解决的问题是如何构造Ｋ—ｍｅａｎｓ算法、改进的差分进化算法与最近相邻算法（ＫＮＮ）相结合 的实验模型。 １ 基本理论 １．１ 入侵检测系统（ＩＤＳ） 入侵检测就是对入侵行为的发觉。它通过对计算机网络或计算机系统中得若干关键点进行信息收 集并对其分析，从中发现是否有违反安全策略的行为和被攻击的迹象。进行人侵检测的软件与硬件的 组合便是入侵检测系统（Ｉｎｔｒｕｓｉｏｎ Ｄｅｔｅｃｔｉｏｎ Ｓｙｓｔｅｍ，简称ＩＤＳ）ｎ］，它的功能就是察觉那些尝试访问网络 的非法行为。目前常用的入侵检测系统有Ｓｎｏｒｔ与Ｓｏｕｒｃｅｆｉｒｅ。 对于网络中存在的大量的入侵行为，入侵检测系统应能记住那些新的攻击行为特征，而对入侵数据 进行分析则能帮助ＩＤＳ找到这些最新攻击行为的特征，常用的分析技术有数据挖掘技术中的聚类算法 与分类算法。 １．２聚类算法 聚类（Ｃｌｕｓｔｅｒｉｎｇ）就是将数据分组成为多个类（Ｃｌｕｓｔｅｒ）。在同一个类内对象之间具有较高的相似 度，不同类之间的对象差别较大，它是模式识别中一种常用的方法。聚类算法应用于网络入侵检测系统 中，可以将网络流量样本集中的正常流量和异常流量区分开来。 聚类的基本要素包括： （１）定义数据之间的相似度； 收稿日期：２０１ｌ一０７—２０ 作者简介：谢雄程（１９７２一 ），男，讲师，主要研究：网络安全技术（ｘｘｃｈｅｎｇ＠１６３．ｃｏｒｎ） 第３期 谢雄程，等：基于聚类与分类混合算法的应用研究 ・８３・ （２）聚类有效性函数（停止判别条件）：在聚类算法的不同阶段会得到不同的类别划分，可以通过聚 类有效性函数来判断多个划分结果中哪个是有效的；使用有效性函数作为算法停止的判断条件，当类别 划分结果达到聚类有效性函数时即可停止算法的运行； （３）类别划分策略：通过何种类别划分方式使类别划分结果达到有效性函数。 聚类有效性函数包括的要素： （１）最小误差（Ｊ Ｃ个类别，待聚类数据ｚ， ，为类别Ｃ，的中心 ＝ｚ∈Ｃ ∑ｘ／Ｃ ， ＝∑ ｚ∈Ｗ（ｋ） 一 『 ｆ式中Ｊ 越小聚类结果越好，Ｊ 衡量属于不同类别的数据与类别中心的误差和。 （２）最小方差丽， 是衡量同一类别内数据的平均误差和。 ＝ ‘ ∑∑ ∈【Ｉ∈Ｕ一 ｝ ｆ２］ ｌ ￡ １．２．１ Ｋ—ｍｅａｎｓ聚类算法 Ｋ—ｍｅａｎｓ＿２ 算法的基本思想是，以ｋ为参数，把 个对象划分成Ｃ个簇。以使簇内具有较高的相 似度，而簇间的相似度较低。相似度的计算根据簇的重心，其值用簇中各对象的平均值来计算。首先从 数据集中随机选取Ｃ个点作为初始聚类中心，然后对剩余的每个对象，根据其与各个簇中心的距离， 将它赋予最近的簇。重新计算每个簇的平均值来找簇的重心，如此反复，直到准则函数收敛为止。通 常采用平方误差准则，其定义为式３］。 ｃ Ｊ＝∑∑ 一 ｆ『 ３］ 其中，Ｊ：１，２，…，ｃ；优，是ｃ个聚类的中心，它的值为簇ｃ 的均值，即： １ 优，＝ ，４］ Ｋ—ｍｅａｎｓ算法的处理过程： （１）从 个数据对象集｛ ， ，…，－ｚ ｝中随机选取ｋ个对象｛Ｙ ，Ｙ ，…， ｝为初始聚类中心； （２）计算各对象到中心对象的距离，并根据最小距离重新划分，距离可按５］计算： 厂 ———————一 ｄ“＝√∑（ 一 ） ５］ 其中ｄ 为欧氏距离，表示对象ｉ与对象Ｊ之间的跑离。 （３）更新簇的平均值，即计算每个簇中对象的平均值； （４）循环（２）到（３），直到每个聚类不再发生变化时算法结束。 从算法流程不难看出，该算法得到的聚类结果受初始时聚类中心对象的选取的影响很大，随机选 取的不同的初始值可能导致不同的聚类结果，甚至可能出现得不到有意义的聚类结果的情况。另外， 由于该算法是采取梯度法求解极值，而梯度法的搜索方向是沿能量减小的方向进行的，所以得到的结 果往往是局部最优而非全局最优。 １．２．２差分进化算法 差分进化算法 。 的基本思想是：首先在问题的可行解空间随机初始化种群，使当前种群父代个体 间的差分矢量构成变异算子，接着按照一定的概率，父代个体与变异个体进行交叉，生成试验个体，然后 在父代个体与试验个体之间根据适应度的大小进行选择，选择适应度更优的个体作为子代。具体的数 学定义式如下所述： 设参数界限ｚ ≤ ≤－ｚ ，Ｊ＝１，２，…，Ｄ，其Ｄ是解空间的维数，．ｚ 、ｚ Ｕ分别表示第Ｊ个分量 取 值范围的上界和下界。算法流程如下： （１）初始化种群。初始种群｛ （０）Ｉ ｘ ≤ｚ （０）≤ｚ ，Ｊ＝１，２，…，ＮＰ； ＝１，２，…，Ｄ｝｝随机产 ・８４・ 广西师范学院学报：自然科学版 第２８卷 生： ｚ （０）＝＿ｚ Ｌ 十ｒａｎｄ（０，１）（ｚ 一ｚ ） ６］ 其中ｚ （０）表示种群中第０代的第ｉ条“染色体”（或个体），ａＴ． （０）表示第０代的第ｉ条“染色体”的第Ｊ 个“基因”。ＮＰ表示种群大小，ｒａｎｄ（０，１）表示在区间均匀分布的随机数。 （２）变异操作．ＤＥ通过差分策略实现个体变异，常见的差分策略是随机选取种群中两个不同的个 体，将其向量差缩放后与待变异个体进行向量合成，即： （ｇ＋１）＝ｚ Ｉ（ｇ）＋Ｆ（ｚ，２（ｇ）一ｚ ３（ｇ））， ≠ｒ１≠ｒ２≠ｒ３ 式中Ｆ为缩放因子，ｚ （ｇ）表示第ｇ代种群中第ｉ个个体。 在进化过程中，为了保证解的有效性，必须判断“染色体”中各“基因”是否满足边界条件，如果不满 足边界条件，则“基因”用与初始种群相同的产生方法重新生成。 ７］ 第ｇ代种群｛５０ （ｇ）ｌ ｚＬ ≤ｚ （ｇ）≤ｚ Ｕ，ｉ＝１，２，…，ＮＰ； ＝１，２，…，Ｄ｝通过变异后，产生一个中 间体｛ （ｇ＋１）Ｉ Ｌ， ≤ ，， （ｇ＋１）≤ ，Ｕ， ，ｉ＝１，２，…，ＮＰ； ＝１，２，…，Ｄ｝。 （３）交叉操作．对第ｇ代种群｛３７。（ｇ）｝及其变异的中间体｛７３ （ｇ＋１）｝进行个体间的交叉操作： ， 、 “ （ｇ＋１）＝ Ｉ，ｉｆ ｒａｎｄ（０，１）≤ＣＲ ｏｒ Ｊ＝ｊ ．，、 、 ． ８ｊ ｌＩｚ…Ｌｇ ，ｏｔｈｅｒｗｉｓｅ 式中ＣＲ为交叉概率，Ｊ 为［１，２，…，Ｄ］的随机整数。 （４）选择操作．ＤＥ采用贪婪算法来选择进入下一代种群的个体： ｆ“ （ｇ＋１），ｉｆ ｆ（“ （ｇ＋１））≤ｆ（ｚ （ｇ）） ｏＺ＂ （ｇ＋１）｛ ，、 ． ． ， 、ＩＸｉ Ｌｇ ，ｏｔｈｅｒｗｉｓｅ ， ９ Ｊ 由于选择作用的影响，进化代数的增加，个体间的差异会逐渐降低，这又会影响变异所带来的多样 性，从而导致算法过早收敛到局部极值附近时，形成早熟收敛现象。经过十几年的研究，ＤＥ算法得到 了较大发展，出现了很多改进的ＤＥ算法，主要包含以下几个方面： 控制参数的改进、差分策略的改进、选择策略的改进等。本文提出的分层的聚类与分类算法混合模 型中采用的是改进的差分进化算法。 １．３分类算法 分类是一种重要的数据挖掘技术，可用于预测，在生物与金融领域应用较广。分类的目的是根据数 据集的特点构造一个分类函数或分类模型，该模型能把未知类别的样本映射到给定类别中的某一个。 １．３．１分类的原理 构造模型的过程一般分为训练和测试两个阶段。在构造模型之前，要求将数据集随机地分为训练 数据集和测试数据集。在训练阶段，使用训练数据集，通过分析由属性描述的数据库元组来构造模型， 假定每个元组属于一个预定义的类，由一个称作类标号属性的属性来确定。训练数据集中的单个元组 也称作训练样本，由于提供了每个训练样本的类标号，该阶段也称为有指导的学习，通常，模型用分类规 则、判定树或数学公式的形式提供。在测试阶段，使用测试数据集来评估模型的分类准确率，如果认为 模型的准确率可以接受，就可以用该模型对其它数据元组进行分类。一般来说，测试阶段的代价远远低 于训练阶段。常用的分类算法有Ｋ—Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ算法、决策树、支持向量机（ＳＶＭ）。 １．３．２ Ｋ—Ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ（ＫＮＮ） Ｋ最近相邻（ｋ—Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ，ＫＮＮ） 分类算法的原理是：如果一个样本在特征空间中的ｋ个 最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别。ＫＮＮ算法中，所选的邻居都是 已经正确分类的对象，该算法在类别决策上只依据最邻近的一个或者几个样本的类别来决定待分样本 所属的类别。ＫＮＮ方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有 关。由于ＫＮＮ方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此 对于类域的交叉或重叠较多的待分样本集来说，ＫＮＮ方法较其他方法更为适合。ＫＮＮ算法描述如下： （１）选定最近邻居的数量定义为Ｋ； ・８６・ 广西师范学院学报：自然科学版 第２８卷 据分两种，第一种是有类标号的样本数据，第二种则是随机的无类标号的样本数据。 聚类与分类主要是对ＴＣＰ连接的８个属性进行，这８个属性值见表１。 表１属性选择表 属性 ．描述 ｍ－百 一 ｛８ ｛８ 连接持续时间 协议类型 ｈ ｍ 目标主机的网络服务类型 连接正常或错误的状态 从源主机到目标主机的数据的字节数 从目标主机到源主机的数据的字节数 连接端口的标志 错误分段的数量 测试用的仿真环境为Ｍａｔｌａｂ２００９ｂ，样本数据集分别用Ｋ—ｍｅａｎｓ和改进的差分进化算法进行聚类。 Ｋｍｅａｎｓ算法中Ｋ值取１０，改进的差分进化算法中种群数取ＮＰ＝３０，比率系数Ｆ取０．５，交配系数ＣＲ 取０．８，交叉策略ｓｔｒａｔｅｇｙ采用ＤＥ／ｒａｎｄ／ｌ／ｂｉｎ与ＤＥ／ｂｅｓｔ／ｌ／ｂｉｎ两者相结合的交叉选择策略，判定入侵数 据的阈值取Ｏ．８。实验结果见表２、表３。 表２有类标号的聚类性能表 聚类算法 Ｋ—ｍｅａｎｓ ５－ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ９７．２％ 改进的差分进化算法 ９５．１％ Ｋ—ｍｅａｎｓ ８６．２％ ７２．１％ 改进的差分进化算法 在实验结果中，Ｋ最近相邻算法中Ｋ值取５时能获得较高的聚类准确率。对于有类标号的样本数 据，基于Ｋ—ｍｅａｎｓ聚类算法的ＫＮＮ分类仅仅出现不到３％的误分类情形。再对比表２与表３，在采用 的两种聚类算法的ＫＮＮ分类中，有类标号的样本数据比无类标号的随机样本数据有更好的分类准确 率，原因就是前者样本数据中有类标号，而后者是随机的而且没有类标号的样本数据。 ４结 语 实验中用到的数据有些是重叠的，不同类标号的数据集聚类时可能会分组到同一簇当中。Ｋ— ｍｅａｎｓ聚类算法使用的是线性方程，对于如ＫＤＤ ＣＵＰ９９这类的没有分隔好的数据集，它不能自身创建 簇群，尽管与差分进化算法相比它能生成较好的聚类效果。未来的工作是如何进一步优化聚类的效果， 这可能会用到多项式与高斯方程将数据集映射到较高的维数进行处理。非线性方法也许更适合于解决 聚类时遇到重叠数据的难题。 参考文献： ［１］ＳＡＮＧ ＫＹＵＮ ＮＯＨ，ＹＯＮＧ ＭＩＮ ＫＩＭ，ＤＯＮＧ ＫＯＯＫ ＫＩＭ，ｅｔ ａ１．Ｎｅｔｗｏｒｋ Ａｎｏｍａｌｙ Ｄｅｔｅｃｔｉｏｎ Ｂａｓｅｄ ｏｎ Ｃ１ｕｓｔｅｒｉｎｇ ｏｆ Ｓｅｑｕｅｎｃｅ Ｐａｔｔｅｒｎｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２００６（３９８１）：３４９．３５８． ［２］ＨＵＹ ＡＮＨ ＮＧＵＹＥＮ，ＤＥＯＫＪＡＩ ＣＨＯＩ．Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Ｄａｔａ Ｍｉｎｉｎｇ ｔｏ Ｎｅｔｗｏｒｋ Ｉｎｓｔｒｕｓｉ。ｎ Ｄｅｔｅｃｔｉｏｎ：Ｃｌａｓｓｉｆｉｅｒ Ｓｅ１ｅｃ ｔｉｏｎ Ｍｏｄｅｌ［Ｊ］．Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２００８（５）：３９９—４０８． ［３］ＳＴＯＲＮ Ｒ，ＰＲＩＣＥ Ｋ．Ｄｉｆｅｒｅｎｔｉａｌ Ｅｖｏｌｕｔｉｏｎ－－Ａ Ｓｉｍｐｌｅ ａｎｄ Ｅｆｆｉｃｉｅｎｔ Ｈｅｕｒｉｓｔｉｃ ｆｏｒ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ ＯＶｅｒ ＯｎｔＣｉｎｕｏｕｓ Ｓｐａｃｅｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ，１９９７，１１（４）：３４１—３５９． 第３期 谢雄程，等：基于聚类与分类混合算法的应用研究 ・８７・ ＳＴＯＲＮ Ｒ，ＰＲＩＣＥ Ｋ．Ｄｉｆｆｅｒｅｎｔｉａｌ Ｅｖｏｌｕｔｉｏｎ－－Ａ Ｓｉｍｐｌｅ ａｎｄ Ｅｆｆｉｃｉｅｎｔ Ａｄａｐｔｉｖｅ Ｓｃｈｅｍｅ ｆｏｒ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｖｅｒ Ｃｏｎ． ｔｉｎｕｏｕｓ Ｓｐａｃｅｓ［Ｒ］．Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ，ＴＨ一９５—０１２，Ｂｅｒｋｅｌｅｙ，ＵＳＡ：Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｇａｌｉｆｏｒｎｉａ．Ｉｎｔｅｒｎａｔｉｏｎａｌ ｏｍｐｕｔＣｅｒ ｃｉＳ— ｅｎｃｅ Ｉｎｓｔｉｔｕｔｅ，１９９５． ＡＤＥＴＵＮＭＢＩ，Ａ ０，ＦＡＩ ＡＫＩ，Ｓ ０，ＡＤＥＷＡＬＥ，０ Ｓ，＆ＡＬＥＳＥ，Ｂ Ｋ（２００６）．Ｎｅｔｗｏｒｋ Ｉｎｔｒｕｓｉｏｎ Ｄｅｔｅｅｔｉｏｎ Ｂａｓｅｄ ｏｎ Ｒｏｕｇｈ Ｓｅｔ ａｎｄ Ｋ—Ｎｅａｒｓｔｅ Ｎｅｉ ｇｈｂｏｕＫＪ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ ｏｍｐｕｔＣｉｎｇ ａｎｄ ＩＣＴ Ｒｅｓｅａｒｃｈ，２００８，２（１）：６０．６６． Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃａｌｉｆｏｒｎｉａ．ＫＤＤ ＣＵＰ １９９９ ｄａｔａ［ＯＬ／ＥＢ］．Ａｖａｉｌａｂｌｅ ａｔ ｈｔｔｐ：／／ｋｄｄ．ｉｃｓ．ｕｓｉ．ｅｄｕ／ｄａｔａｂａｓｅ／ｋｄｄｃｕｐ９９．ｄｉａｋｓｅｓ ｔｅｒａｋｈｉｒ ｔａｎｇｇａｌ ２７ Ｏｃｔｏｂｅｒ ２００９． Ａｐｐｌｉｃａｔｉｖｅ Ｒｅｓｅａｒｃｈ ｏｆ Ｍｉｘｅｄ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｌａｙｅｒｅｄ Ｃｌｕｓｔｅｒｉｎｇ ａｎｄ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ＸＩＥ Ｘｉｏｎｇ—ｃｈｅｎｇ，ＬＩＵ Ｚｈｉ—ｊｉａ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ＆Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ．Ｇｕａｎｇｘｉ Ｔｅａｃｈｅｒｓ Ｅｄｕｃａｔｉｏｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｎｉｎｇ ５３０００１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｌｔｈｏｕｇｈ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ａｎｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｉｓ ｖｅｒｙ ｗｉｄｅ，ｔｈｅ ｒｅｓｅａｒｃｈ ｆｏｒ ｂｏｔｈ ｉｎ ｃｏｍｂｉｎａｔｉｏｎ ｉｓ ｌｉｍｉｔｅｄ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ ｉｎｔｒｕｓｉｏｎ ｄｅｔｅｃｔｉｏｎ．Ｔｈｅｒｅｆｏｒｅ，ａ ｍｏｄｅｌ ｏｆ ｌａｖｅｒｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｎｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｅｓｅｎｔｅｄ ａｎｄ ｔｈｏｓｅ ｅｘａｍｐｌｅｓ ｏｆ ｉｎｔｒｕｓｉｏｎ ｄｅｔｅｃｔｉｏｎ ｄａｔａ ａｒｅ ｃｌｕｓｔｅｒｅｄ ａｎｄ ｃｌａｓｓｅｄ ｆｏｒ Ｋ Ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ，ｉｍｐｒｏｖｅｄ ｄｉｆｆｅｒｅｎｔｉａｌ ｅｖｏｌｕｔｉｏｎ ａｌｇｏｒｉｔｈｍ ａｎｄ Ｋ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ａｌｇｏ— ｒｉｔｈｍ．Ａｎｄ ｆｉｎａｌｌｙ ｔｈｅ ｅｆｆｅｃｔｉｖｅ ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｌｔｓ ａｒｅ ｏｂｔａｉｎｅｄ． Ｋｅｙ ｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ；Ｋ Ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ；ｄｉｆｆｅｒｅｎｔｉａｌ ｅｖｏｌｕｔｉｏｎ；ＩＤＳ ［责任编辑：黄天放］
