１ ０６ ２０ １ １，４７（１ １） Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 基于改进聚类分析算法的入侵检测系统研究 杜强，孙敏 ＤＵ Ｑｉａｎｇ，ＳＵＮ Ｍｉｎ 山西大学汁算机与信息技术学院，太原０３０００６ Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈａｎｘｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｔａｉｙｕａｎ ０３０００６，Ｃｈｉｎａ ＤＵ Ｑｉａｎｇ，ＳＵＮ Ｍｉｎ．Ｉｎｔｒｕｓｉｏｎ ｄｅｔｅｃｔｉｏｎ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉ— ｃａｔｉｏｎｓ，２０１１．４７（１１）：１０６．１０８． Ａｂｓｔｒａｃｔ：Ｔｈｅｒｅ ａｒｅ ｔｗｏ ｍａｊｏｒ ｐｒｏｂｌｅｍｓ ｅｘｉｓｔ ｉｎ ｃｏｍｍｏｎｌｙ ｕｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｉｎｔｒｕｓｉｏｎ ｄｅｔｅｃｔｉｏｎ ｓｙｓｔｅｍｓ：Ｏｎｅ ｉｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｈａｔ ＵＳｅＳ ｔｈｅ ｒａｎｄｏｍ ｍｅｔｈｏｄ ｔｏ ｄｅｔｅｒｍｉｎｅ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ，ｔｈｅ ｏｔｈｅｒ ｉＳ ｔｈａｔ ｉｔ ｉｓ ｅａｓｙ ｔｏ ｆａｌｌ ｉｎｔｏ ｌｏｃａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｃａｕｓｅｄ ｂｙ ｃｌｉｍｂｉｎｇ—ｔｙｐｅ ｔｅｃｈｎｏｌｏｇｙ．Ｂａｓｅｄ ｏｎ ｔｈｉｓ，ａｔｌ ｉｍｐｒｏｖｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ．Ｂｙ ｄｅ— ｔｅｒｍｉｎｉｎｇ ｔｈｅ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ ｏｆ ｔｈｅ ｔｗｏ ｆａｒｔｈｅｓｔ．ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｏｎ ｔｈｅ ｍａｘｉｍｕｍ．ｍｉｎｉｍｕｍ ｄｉｓｔａｎｃｅ ａｎｄ ＤＢＩ ｉｎｄｅｘ ｉｔ ｄｅｔｅｒｍｉｎｅｓ ｔｈｅ ｒｅｍａｉｎｉｎｇ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒ．ｔｈｅ ｍｅｔｈｏｄ ｓｏｌｖｅｓ ｔｈｅ ｍｅｎｔｉｏｎｅｄ ｉｓｓｕｅ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｖｅｒｉｉｅｓ ｆｔｈｅ ｆｅａｓｉｂｉｌｉｙ ａｎｄ ｓｕｐｅｒｔｉｏｒｉｔｙ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｉｎｔｒｕｓｉｏｎ ｄｅｔｅｃｔｉｏｎ：ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ： ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ 摘要：针对常用聚类分析算法应用于入侵检测系统所存在的两大方面的问题：一是其采用随机法确定初始聚类中心，不同的初 始值可能产生不同的聚类结果；二是采用爬山式技术导致容易陷入局部最优解。基于此提出一种改进的聚类分析算法，通过确 定两个最远初始聚类中心和基于最大最小距离的层次聚类、ＤＢＩ－￣标来确定剩余初始聚类中心，该方法使上述问题得到解决，并 通过仿真实验验证了该算法的可行性和优越性。 关键词：入侵检测；聚类分析；Ｋ－ｍｅａｎｓ算法 ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２．８３３１．２０１１．１１．０３０ 文章编号：１００２．８３３１（２０１１）ｌ１－０１０６．０３ 文献标识码：Ａ 中图分类号：ＴＰ３９３．０８ １引言 随着网络广泛应用和网络技术特别是黑客技术的发展， 网络系统面临着越来越多的攻击和安全问题。为了有效地保 ２入侵检测系统简介及常用的聚类分析算法 ２．１入侵检测系统简介 入侵检测系统（Ｉｎｔｒｕｓｉｏｎ Ｄｅｔｅｃｔｉｏｎ Ｓｙｓｔｅｍ，ＩＤＳ）从系统 护网络环境，及时有效地发现攻击行为，继防火墙、数据加密 等传统安全保护措施后入侵检测作为一种新的安全防护技术 应运而生。如今，网络速度不断加快，入侵方式和种类的不断 更新，这些都对入侵检测技术提出了新的要求。入侵检测分 为误用检测和异常检测两种类型，其中异常检测技术根据使 用者的行为或资源使用状况来判断是否存在入侵，不依赖具 体入侵是否出现来检测，而且对系统的依赖性相对较小，从而 成为了近几年来网络安全研究的热点之一。 数据挖掘技术于１９９９年由Ｗｅｎｋ Ｌｅｅ” 等人引入到入侵检 测系统中。聚类分析作为一种常用的数据挖掘技术，其算法 内部和各种网络资源信息中，分析可能的入侵攻击行为，扩展 系统管理员的安全管理能力（包括安全审计、监视、进攻识别 和响应），提高信息安全基础结构的完整性。入侵检测系统根 据用户的历史行为，基于用户的当前行为，完成对入侵的检 测，并留下证据，为数据恢复和事故处理提供依据。就检测技 术而言，ＩＤＳ有误用检测和异常检测之分。一个入侵检测系 统一般包含数据搜集、入侵检测和入侵响应三个部分，其一般 结构如图１所示［２１。 简单、计算复杂度低，尤其适用于高速网络环境。然而聚类分 析算法本身采用随机法选择初始聚类中心和易陷入局部最优 解等问题极大地了其在网络入侵检测方面的应用。基于 上述现实背景，提出了一种基于改进聚类分析算法的入侵检 测系统，并通过仿真实验验证了该系统的优趱陛。 基金项日：山西省高校科技开发项目（Ｎｏ．２００５１２Ｇ２）；山西大学科研项目（Ｎｏ．２００５１０３）。 作者简介：杜强（１９８５一），男，硕士研究生，主要研究方向：网络安全；孙敏（１９６８一），女，副教授，硕士研究生导师。Ｅ－ｍａｉｌ：ｄｕｑｉａｎｇ．ｓｔｕｄｅｎｔ＠ｓｉｎａ．ｃｏｒｎ 收稿日期：２０１０—０５—１２；修Ｍ日期：２０１０—０８—０９ 图１入侵检测系统结构圈 杜强，孙敏：基于改进聚类分析算法的入侵检测系统研究 ２．２入侵检测中常用的聚类分析算法介绍 聚类分析是将数据集合中的对象划分成若干个类的过 ３改进的Ｋ－ｍｅａｎｓ算法 ３．１确定两个最佳的初始聚类中心 选取两个最佳最远聚类中心的思想是为了避免算法初始 值选取时很可能出现的初始聚类种子过于邻近的问题，算法 初始时选出距离最远的两个数据对象，从而形成两个初始的 聚类中心，以便很好地保证后续的处理使同一类内的对象有 程，使得同一个类的对象具有较高的相似度，而不同类的对象 之问相似度较低，或者说不同类之间的对象差异较大。因此， 基于聚类分析的入侵检测技术就是用无参数的方法将事件流 用向量表示，然后再利用聚类分析算法将它们分为行为类。 每一类都代表相似的活动或用户的行为，这样就能够辨别出 正常和异常的行为。无监督聚类分析算法应用于入侵检测不 需要对训练集进行标类和严格的过滤，而且对于检测网络数 据中的未知攻击行为有比较好的效果，因此聚类分析算法在 极高的相似性 ，而不同类之间有极低的相似性。为保证系统 在处理大数据量时的高效率，本文设计一种时间复杂度为 Ｏ（ｎ）的计算方法，其相关说明如下： 假设数据库中有 个数据对象，Ｏ ： ，Ｘ，，…，Ｘ ｝，随机 入侵检测领域［３Ｊ值得进一步深入研究。 在众多聚类分析算法” 中，将Ｋ－ｍｅａｎｓ算法应用于异常检 测的优点是其方法简单、计算复杂性小，因此容易达到入侵检 测实时性的要求，而且也比较容易实现。其基本思想是：随机 地选择ｋ个对象，每个对象初始化地代表了一个类的平均值或 中心。对剩余的每个对象，根据其与各个类中心的相似度，将 它赋给最近的类，然后重新计算每个类的平均值，这个过程不 断重复，直到准则函数收敛。其主要步骤 】｝苗述如下： 输入：指定类的个数 和包含Ⅳ个对象的数据集。 输出：ｋ个类。 方法： （１）从 魄营对象中任意选择 个对象作为初始的类中心。 （２）计算剩余数据对象到各个聚类中心的距离，并把对象 分配到离各自最近的聚类中。 （３）分配完成后，重新计算 个聚类的中心，即计算聚类中 对象的平均值。 （４）与前一次计算得到的ｋ个聚类中心比较，是否准则函 数开始收敛，是则转（５），否则转（２）。 （５）输出ｋ个聚类结果。 该算法在计算两个数据对象之间相似度时，考虑到网络 入侵检测效率的因素一般采用计算复杂度较小的欧几里德距离 作为两个数据对象之间属性值的相似性度量，式子表示为： ｄｃ（ｉ，ｕ，）＝ＪＩｚ ｌ— ，ｌｒ＋ — ，２ ＋…＋ 一 （１） 其中Ｘ 和Ｘ， 分别表示数据对象ｉ和数据对象．，的第Ｐ个属 性值，ｄ（ｉ，Ｊ）表示数据对象ｉ和，之间所有屙Ｉ生值的相似度之 和。同时，算法采用均方差作为准则函数，其定义如下： ｋ Ｅ＝∑∑Ｌｏ－ｍ ｌ（２） ｉ １Ｐ∈ｃ 其中 为数据库中所有数据对象的均方差之和，Ｐ代表其所 在聚类空间的一个数据对象点，ｍ 为聚类ｃ 平均值，Ｐ和ｍ， 均为的数据对象。 可见，Ｋ－ｍｅａｎｓ算法是解决聚类问题的一种经典算法。它 的主要优点是算法简单、快速而且能有效地处理大数据库。 然而这种算法采用随机法选取初始聚类中心，因此对不同的 初始值可能会导致不同的聚类结果，使聚类结果产生不稳定 性，应用于在线入侵检测系统导致该算法的执行结果与输入 顺序 有关。其次，这种算法采用了所谓的爬山式技术来寻找 最优解，其每次调整都为了寻求更好的聚类结果，因此很容易 陷入局部最优解 。由于这两大缺陷极大地了该算法的 应用范围，因此本文选择改进的Ｋ－ｍｅａｎｓ算法应用于网络入 侵检测 系统。 选择一个数据对象 ，， ，表示数据对象ｉ和．，之间的距离。 （１）寻找与数据对象 ，距离最远的对象 ，两者间距离用 表示。 （２）寻找与数据对象Ｘ。距离最远的对象Ｘ ，两者间距离用 表示。 ， （３）如果，＝ｔ，那么Ｘ，与ｘ 互为最大距离点，则转到（６）； 女Ⅱ果，≠ｔ，贝０转至 （４）。 （４）如果ｄｔ ｄｉ ，则与（３）结果一致， 与ｘ，互为最大距 离点。 （５）如果 ＜ ，则Ｘ，与 ，距离最远，二者互为最大距 离点。 （６）Ｃ 和ｃ，分别用于存储找到的互为最大距离的两个点， 用作初始两个聚类中心。 ３．２搜索初始两个聚类中心ｃ 和ｃ，的聚类对象 这一步的思想是通过上面介绍算法选出了距离最远的两 个数据对象后，取合适的阈值ｑ来查找这两个中心的近邻。 假设有／／．个数据对象，０ ＝ ，Ｘ 一， ｝，目前已经找到最新 聚类中心Ｃ ，针对０ 中剩余的数据对象，分别计算到Ｃ 的距 离ｄ（ｘ ，ｃ ），如果ｄ（ｘｆ，ｃ ）＜ｑ，那么Ｘ 和Ｃ 就属于同一个聚 类。通过上述思想查找出初始两个聚类中心的近邻并归为同 一个聚类，这样可以有效地减少算法以后的数据运算量，提高 算法的执行效率。 ３．３确定剩余初始聚类中心 Ｋ－ｍｅａｎｓ算法要获得更好的性能，就必须解决其容易陷入 局部最优解的缺点，需要一种能够在全局范围内查找的快速 算法用于确定初始聚类中心。本文提出一种基于最大、最小 距离的层次聚类算法，并利用ＤＢＩ（Ｄａｖｉｅｓ．Ｂｏｕｌｄｉｎ Ｉｎｄｅｘ）指 标来最终确定初始聚类个数 和中心点。该算法易于实现， 时间复杂度低，适合于处理大数据量的入侵检测系统使用。 ＤＢＩ指标是一种非模糊型的集群评估指标，以聚类问离散 程度和同一聚类内数据对象的紧密程度为基本依据，使同一 聚类中数据相似性高，聚类之间则相异性高，以此来对聚类的 结果进行评估，其计算公式如下： Ｋ ｒ Ｉ １ ＤＢＩ＝ ∑ｍａｘ｛ｌ ３） ，，Ｊ ｝ （其中Ｓｉ＝ ∑［ｌＬｉｌ ∈ｃｉ ＩＸ－Ｖ，ｌ表示第ｆ个聚类内数据对象与中心的 标准误差， 表示第ｉ个聚类内的各个数据对象，ｖ 表示第ｉ 个类的平均值，Ｃ 表示第ｉ个聚类内数据对象的个数，ＪＩｘｌｌ表 示欧几里德距离， ．，表示第ｆ个类与第 个类中心之间的欧 １０８ ２０１１，４７（１１） ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 据集包含１Ｏ万条数据项共分５组数据进行，入侵数据占总数 据的１％共１ ０００条。其中８０％的数据用于对算法的训练，然 后用剩下的２０％的数据分５组用于测试。本实验两个算法均 取阈值ｑ＝０．４，Ｋ－ｍｅａｎｓ算法 值取５，即以前５个数据包为初 始聚类中心，实验结果如表１～表３。 表１训练算法运行耗时 笪法 托时 ４１ ２３８ ３９．５２４ 几里德距离。确定剩余初始聚类中心的算法描述如下： 对于有Ⅳ个数据对象的数据集０ ＝ ， 五、Ｘ，，用于初始两个聚类中心。 ．．，Ｘ ｝： （１）通过３．１节介绍的算法找到了互为最大距离的两个点 （２）对集合Ｄ 中剩余的对象ｘ ，分别汁算到Ｘ，、Ｘ，的距 离 。和 。 （３）记 ＝ｍａｘ｛ｍｉｎ（￣ ， ）｝，则取 为新的聚类中心，找 出满足给定阈值ｑ的Ｘ 的近邻，加入到Ｃ 中，计算ｃ 的中心。 （４）根据公式（３），汁算出本次加入新聚类Ｃ 后的ＤＢＩ。 （５）重复步骤（２），在找出来的新聚类中心Ｘ．并查找近邻 改进聚类分析算法 Ｋ－ｍｅ￣ｓ算法 表２基于改进聚类分析算法ＩＤＳ聚类结果 加入后计算得出新ＤＢＩ，与上一次的ＤＢＩ相比较，如果 ＤＢＩ．。 ＜ＤＢ１ ，则 ，附近可以形成新的聚类；直到某次计算 出来的ＤＢＩ值大于 一次的ＤＢＩ的值，则终止查找初始聚类 数目 的过程。 ３．４改进Ｋ－ｍｅａｎｓ算法的整体描述 通过上述改进，解决了Ｋ－ｍｅａｎｓ算法随机法选取初始聚类 中心和容易陷入局部最优解的问题，使得该算法应用于入侵 检测系统在提高检测率和降低误检率 上取得了较大的进步， 改进算法的整体流程图如图２所示。 定两个最远初始聚类中心Ｘ 、 ： 聚类中心 ．、ｚ 的近邻搜索 １ｒ 确定新聚类中心 ｝ 一 区堕 ————土——一 ｌｉ十三 ＩＮ Ｉ确定初始聚类中心 ｌ ￣－ｍｅａｎｓ算法剩余数据对象归类 图２改进Ｋ－ｍｅａｎｓ算法流程图 ４仿真实验及结果分析 为了对改进聚类分析算法的入侵检测系统的检测效果进行 评估，本实验将对照Ｋ－ｍｅａｎｓ算法，在算法训练运行耗时和入侵 检测的检测率与误检率三个方面对二者进行对比。本次实验 的是在Ｗｉｎｄｏｗｓ ＸＰ平台上，Ｖｉｓｕａｌ ｃ＋＋６．０框架下进行的。 本实验采用ＫＤＤ９９数据集ｎ”，该数据集采用的是ＭＩＴ Ｌｉｎｃｏｌｎ Ｌａｂｓ９８的数据，提供了从模拟局域网上采集了９周的 网络数据包，其中的每条记录包含了４１个特征量，能够模拟４ 大类共３８种攻击类型。为了避免对聚类分析产生不良影响和 提高实验的检测效率，剔除了对聚类分析没有太大意义的数 据属性，经过分析筛选了每条记录的生存期、协议类型、ＩＰ服 务类型、ＴＣＰ窗口大小、报文长度等ｌ０个属性作为研究对象。 由于在一个正常的网络环境中，正常的数据占绝大部分，入侵 数据只占极少的一部分（一般不超过２％），所以实验采用的数 结果分析：网络入侵检测系统的性能是由检测率和误检 率来进行判断的，在保证较低的误检率的基础之上，能够获得 尽可能高的检测率。通过表１可以看出，在使用较大数据量对 算法进行训练的阶段，改进聚类分析算法与Ｋ－ｍｅａｎｓ算法的运 行消耗时间基本相等，而表２和表３的对比明显可以看出，基 于改进聚类分析算法的入侵检测系统检测率明显高于 Ｋ－ｍｅａｎｓ算法，同时误检率明显低于Ｋ－ｍｅａｎｓ算法，进而使入 侵检测系统的综合检测水平得到了较大提高。 ５结论 采用改进的聚类分析算法应用于入侵检测系统，通过首 先确定两个最佳初始聚类中心和基于最大、最小距离的层次 聚类来确定剩余初始聚类中心的方法，克服了Ｋ－ｍｅａｎｓ算法随 机选取初始聚类中心和容易陷入局部最优解的缺陷。在保证 训练算法运行消耗时间基本不变的情况下，有效地提高了算 法应用于入侵检测系统的检测率且降低了误检率，提升了聚 类分析算法应用于入侵检测系统的性能。 参考文献： ［１】Ｌｅｅ Ｗ，Ｓｔｏｌｏｆ Ｓ Ｊ．Ｄａｔａ ｍｉｎｉｎｇ ａｐｐｒｏａｃｈｅｓ ｆｏｒ ｉｎｔｒｕｓｉｏｎ ｄｅｔｅｃ— ｔｉｏｎ［Ｃ］／／Ｓａｎ Ａｎｔｏｎｉｏ Ｔ Ｘ．Ｐｒｏｃ ７ ＵＳＥＮＩＸ Ｓｅｃｕｒｉｔｙ Ｓｙｍｐｏｓｉｕｍ， １９９８． ［２】李玲娟．数据挖掘技术在入侵检测系统中的应用研究［Ｄ］．苏州：苏 州大学，２００８． 【３张亚玲，３］康立锦．基于数据挖掘的ｓｎ０ｒｔ系统改进模型［Ｊ】．计算机应 用，２００９，２９（２）：４０９—４１１． ［４李雷，４］罗红旗，丁亚丽．一种改进的模糊Ｃ均值聚类算法［Ｊ］．计算机 技术与发展，２００９，１９（１２）：７１—７３． （下转１８１页） 吴文辉，苏晓龙，孙统风：动态图像特征空间的立体视觉匹配算法 Ｍａｔｌａｂ ７．Ｘ以及Ｗｉｎｄｏｗｓ操作系统平台和Ｖｃ＋＋６．０编写的 程序进行实验。 （１）对静态图像进行实验 ２０１１，４７（１１） １８１ ６结束语 结合动态Ｂａｙｅｓ网和无监督学习的思路，解决了概率分布 参数时变的立体视觉匹配的问题。动态Ｂａｙｅｓ网拥有动态推 断的能力，充分反映了时间片断之间的关联和因果关系。可 以充分利用先验和在线学习所获得的样本空间变化和演进的 概率知识，预测和估计实时的数字特征。同时将增量式学习 本文算法对测试图Ｔｓｕｋｕｂａ的实验结果如图３所示。 引入动态贝叶斯网，使得在图像分割过程中充分利用动态 Ｂａｙｅｓ网的推断结果。平衡移动视觉系统对立体视觉匹配算 （ａ）原始图像 （ｂ）真实分割 法的实时性和准确性。 参考文献： ［１］Ｓｃｈａｒｓｔｅｉｎ Ｄ，Ｓｚｅｌｉｓｋｉ Ｒ．Ｍｉｄｄｌｅｂｕｒｙ ｓｔｅｒｅｏ ｖｉｓｉｏｎ ｐａｇｅ［ＥＢ／ＯＬ］． ［２００６—１２—２４］．ｈｔｔｐ：／／ｗｗｗ．ｍｉｄｄｌｅｂｕｒｙ．ｅｄｕ／ｓｔｅｒｅｏ／． ［２］Ｓｃｈａｒｓｔｅｉｎ Ｄ，Ｓｚｅｌｉｓｋｉ Ｒ，Ｔａｘｏｎｏｍｙ Ａ．Ｅｖａｌｕａｔｉｏｎ ｏｆ ｄｅｎｓｅ （ｃ）初步分割结果 （ｄ）本文算法的最终结果 ｔｗｏ—ｆｒａｍｅ ｓｔｅｒｅｏ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ａｌｇｏｒｉｔｈｍｓ［Ｊ］．Ｉｎｔｅｍａｔｉｏｎａｌ Ｊｏｕｒ－ ｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，２００２，４７（１／２／３）：７—４２． 图３ Ｔｓｕｋｕｂａ实验结果 ［３］Ｂｒｏｗｎ Ｍ Ｚ，Ｂｕｒｓｃｈｋａ Ｄ，Ｈａｇｅｒ Ｇ Ｄ．Ａｄｖａｎｃｅｓ ｉｎ ｃｏｍｐｕｔａｔｉｏｎ— 同时，文献（１】总结了各种立体匹配方法，对该文献提及到 的４幅测试图像进行本文算法和各种其他算法的实验和匹配 结果的比较，关于它们的详细介绍可以见网址ｈｔｔｐ／／ｗｗｗ．ｍｉｄ． ｄｌｅｂｕｒｙ．ｅｄｕ／ｓｔｅｒｅｏ。表１给出了本文算法与其他几种匹配算法 ａｌ ｓｔｅｒｅｏ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｍ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００３．２５（８）：９９３—１００８． ［４］Ｓｈｅｎｏｙ Ｐ，Ｒａｏ Ｒ Ｐ Ｎ．Ｄｙｎａｍｉｃ Ｂａｙｅｓｉａｎ ｎｅｔｗｏｒｋｓ ｆｏｒ ｂｒａｉｎ—ｃｏｍ－ ｐｕｔｅｒ ｉｎｔｅｒｆａｃｅ［Ｃ］／／Ａｄｖａｎｃｅｓ ｉｎ ＮＩＰＳ．ＵＳＡ：ＭＩＴ Ｐｒｅｓｓ，２００５，１７． ［５］Ｗｅｂｅｒ Ｍ，Ｗｅｌｌｉｎｇ Ｍ，Ｐｅｒｏｎａ．Ｕｎｓｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ ｏｆ ｍｏｄｅｌｓ 的误差率进行比较，从中可以看出本文算法的该指标下是比 较前列的。 表１ 本文算法与其他算法的误差率比较 （％） ｆｏｒ ｒｅｃｏｇｎｉｔｉｏｎ［Ｃ］／／Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ．Ｂｅｒｌｉｎ／ Ｈｅｉｄｅｌｂｅｒｇ，Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ，２０００，１８４２：１８—３２． ［６］Ｓｕｎ Ｊ，Ｚｈｅｎｇ Ｎ Ｎ，Ｓｈｕｍ Ｈ Ｙ．Ｓｔｅｒｅｏ ｍａｔｃｈｉｎｇ ｕｓｉｎｇ ｂｅｌｉｅｆ ｐｒｏｐａｇａｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｍ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａ— ｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００３，２５（７）：１－１４． ［７］Ｃｏｍａｎｉｃｉｕ Ｍ．Ｍｅａｎ ｓｈｉｆｔ：Ａ ｒｏｂｕｓｔ ａｐｐｒｏａｃｈ ｔｏｗａｒｄ ｆｅａｔｕｒｅ ｓｐａｃｅ ａｎａｌｙｓｉｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００２，２４（５）：６０３—６１９． 【８］Ｓｔｅｆａｎｏ Ｌ Ｄ，Ｍａｔｔｏｃｃｉａ Ｓ，Ｔｏｍｂａｒｉ Ｆ．ＺＮＣＣ—ｂａｓｅｄ ｔｅｍｐｌａｔｅ ｍａｔｃｈｉｎｇ ｕｓｉｎｇ ｂｏｔｍｄｅｄ ｐａｒｔｉａｌ ｃｏｒｒｅｌａｔｉｏｎ［Ｊ］．Ｐａ￣ｅｍ Ｒｅｃｏｇｎｉ— （２）对动态图像进行实验 针对上一实验所提到的ＧＣ，ＲＢＰ和本文算法作比较。在 某一时间段内，对Ｔｓｕｋｕｂａ图像添加调整函数，该函数可以对 ｔｉｏｎ Ｌｅｔｔｅｒｓ，２００５，２６：２１２９—２１３４． ［９］Ｄｕｄａ Ｒ Ｏ，Ｈａｒｔ Ｐ Ｅ，Ｓｔｏｒｋ Ｄ Ｇ．Ｐａｔｔｅｒｎ ｃｌａｓｓｉｉｆｃａｔｉｏｎ［Ｍ］．２ｎｄ ｅｄ． ＵＳＡ：Ｊｏｈｎ Ｗｉｌｅｙ＆Ｓｏｎｓ．２００１． ［１０］Ｓｃｈｗａｒｚ Ｇ．Ｅｓｔｉｍａｔｉｎｇ ｔｈｅ ｄｉｍｅｎｓｉｏｎ ｏｆ ａ ｍｏｄｅｌ［Ｊ］．Ｔｈｅ Ａｎ— ｎａｌｓ ｏｆ Ｓｔａｔｉｓｔｉｃａｌｓ，１９７８，６（２）：４６１—４６４． ［１１］Ｂｏｙｋｏｖ Ｙ，Ｖｅｋｓｌｅｒ ０，Ｚａｂｉｈ Ｒ．Ｆａｓｔ ａｐｐｒｏｘｉｍａｔｅ ｅｎｅｒｇｙ ｍｉｎｉｍｉ— 图像做一个随机平移的变化量，对该变化图像进行多次匹配， 比较该时间段内完成匹配的次数。实验结果如图４Ｎ示。 ２００ １５０ １Ｏ０ ５０ ０ ｚａｔｉｏｎ ｖｉａ ｇｒａｐｈ ｃｕｔｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ＰａＲｅｍ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００１，２３（１１）：１２２２—１２３９． ［１２］Ｂｏｓｓｍａｎｎｓ Ｂ，Ｔｕ Ｊ Ｆ．Ａ ｔｈｅｒｍａｌ ｍｏｄｅｌ ｆｏｒ ｈｉｇｈ ｓｐｅｅｄ ｍｏｔｏｒ－ 礅 （上接１０８页） 卅Ｉ：暨南大学，２００６． 慧 ｉｚｅｄ ｓｐｉｎｄｌｅｓ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｍａｃｈｉｎｅ Ｔｏｏｌ＆Ｍａｎｕ— ｆａｃｔｕｒｅ，１９９９，３９：１３４５—１３６６． ［１３】夏永泉，刘正东，杨静宇．一种基于正交矩的立体匹配方法［Ｊ】．系 统仿真学报，２００５，１７（９）：２０８２—２０８４． 图４本文算法与其他算法的实时性比较 ［８］周娟，熊忠阳，张玉芳，等．基于最大最小距离法的多中心聚类算法［Ｊ】． 计算机应用，２００６，６（２６）：】４２５—１４２７． ［９］Ｗｕ Ｓｕｙｕｎ，Ｙｅｎ Ｅ．Ｄａｔａ ｍｉｎｉｎｇ—ｂａｓｅｄ ｉｎｔｒｕｓｉｏｎ ｄｅｔｅｃｔｏｒｓ［Ｊ］．Ｅｘ— ［５张昌城．５］基于数据挖掘的网络入侵检测系统的研究与应用［Ｄ］．广 ［６郑仁毅．６］基于数据挖掘技术的入侵检测系统研究与设ｉｆ［Ｄ］．厦门： 厦门大学，２００７． ［７］ Ｓａｍｂａｓｉｖａｍ Ｓ，ＴｈｅｏｄｏｓｏｐｏｕＩｏｓ Ｎ．Ａｄｂａｎｃｅｄ ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄｓ ｏｆ ｍｉｎｉｎｇ ｗｅｂ ｄｏｃｕｍｅｎｔｓ［Ｊ］．Ｉｓｓｕｅｓ ｉｎ Ｉｎｆｏｒｍｉｎｇ Ｓｃｉ— ｐｅｒｔ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ，２００９，３６（２）：５６０５—５６１２． ［１０］Ｗｕｕ Ｌ Ｃ，Ｈｕｎｇ Ｃ Ｈ，Ｃｈｅｎ Ｓ Ｆ．Ｂｕｉｌｄｉｎｇ ｉｎｔｒｕｓｉｏｎ ｐａｔｔｅｍ ｍｉｎ— ｅｒ ｆｏｒ ｓｎｏｒｔ ｎｅｔｗｏｒｋ ｉｎｔｒｕｓｉｏｎ ｄｅｔｅｃｔｉｏｎ ｓｙｓｔｅｍ［Ｊ］．Ｔｈｅ Ｊｏｕｒｎａｌ ｏｆ Ｓｙｓｔｅｍｓ ａｎｄ Ｓｏｆｔｗａｒｅ，２００７，８０（２）：１６９９—１７１５． ［１ １］Ｃｏｒｒｅｃｔｅｄ．ｇｚ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｋｄｄ．ｉｃｓ．ｕｃｉ．ｅｄｕ／ｄａｔａｂａｓｅｓ／ｋｄｄｃｕｐ９９／ｋｄ— ｄｃｕｐ９９．ｈｔｍ１． ｅｎｃｅ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｏｌｏｇｙ，２００６，８（３）：５６３—５７９．
