基于平均适应度空间的异常检测

《基于平均适应度空间的异常检测》由会员分享，可在线阅读，更多相关《基于平均适应度空间的异常检测（45页珍藏版）》请在装配图网上搜索。

1、编号：（ ）字 号本科生毕业设计（论文）基于平均适应度空间的异常检测吕超 04101321电气工程与自动化2010-10班题目： 姓名： 学号： 班级： 二一四年六月中 国 矿 业 大 学本科生毕业设计姓 名： 吕超 学 号： 04101321 学 院： 信息与电气工程学院 专 业： 电气工程与自动化 设计题目： 基于平均适应度空间的异常检测 指导教师： 王雪松 职 称： 教授 二一四年 六月 徐州中国矿业大学毕业设计任务书学院 信息与电气工程学院 专业年级 电气10级 学生姓名 吕超 任务下达日期： 2013年12月30日毕业设计日期： 2013年12月30日至2014年6月10日毕业设计题

2、目： 基于平均适应度空间的异常检测毕业设计主要内容和要求：1. 数据挖掘的基本概念与意义；2. 分析异常检测存在的问题；3. 构建平均适应度空间；4. 使用分类技术识别出异常类型；5 使用标准数据集进行算法评估。6 翻译一篇近三年发表的相关英文文献院长签字： 指导教师签字： 年 月 日中国矿业大学毕业设计指导教师评阅书指导教师评语（基础理论及基本技能的掌握；独立解决实际问题的能力；研究内容的理论依据和技术方法；取得的主要成果及创新点；工作态度及工作量；总体评价及建议成绩；存在问题；是否同意答辩等）：成 绩： 指导教师签字： 年 月 日中国矿业大学毕业设计评阅教师评阅书评阅教师评语（选题的意义；

3、基础理论及基本技能的掌握；综合运用所学知识解决实际问题的能力；工作量的大小；取得的主要成果及创新点；写作的规范程度；总体评价及建议成绩；存在问题；是否同意答辩等）：成 绩： 评阅教师签字： 年 月 日中国矿业大学毕业设计答辩及综合成绩答 辩 情 况提 出 问 题回 答 问 题正 确基本正确有一般性错误有原则性错误没有回答答辩委员会评语及建议成绩：答辩委员会主任签字： 年 月 日学院领导小组综合评定成绩：学院领导小组负责人： 年 月 日摘 要本文针对当前网络环境下的入侵问题，提出了一种基于异常的入侵检测方法，从而为互联网的安全提供了一道保障。由于异常检测需要建立正常访问的行为模式库，本文用数据挖

4、掘的方法从大量正常访问的数据中提取频繁项集，形成关联规则，把这种规则作为正常访问的行为轮廓。轮廓构建出来后，采用构建平均适应度空间的方法比较数据与轮廓的相似度，从而判断其是否为入侵数据。这实际上也是对未知类型访问数据的分类。本文不仅验证了数据挖掘技术应用在异常检测当中的可行性，还研究了支持度的变化对规则集数量以及检测率的影响和分类器阈值的变化对检测率的影响两个关键问题，发现了检测率的“跃变”现象并对实际应用提供了指导意见。最后针对本文的问题和不足提出了今后改进的方向，还展望了数据挖掘发展的美好前景。本文采用了KDD标准数据集作为测试和训练数据，使用从测试数据集当中提取出的规则对测试数据集进行异

5、常检测，实验仿真证明这种方法是有效的，具有较高的检测率。同时该方法简单易行，容易理解，可操作性较强。关键词：数据挖掘; 异常检测; 关联规则; 平均适应度空间 ABSTRACTIn this thesis, a new anomaly detection method is proposed, which aims at improving the detection performance in the current environment of the Internet. Because this detection needs to build the profiles of norm

6、al behaviors, so data mining is necessary to extract information from normal audit data, which is in the form of class association rules. The association rules are just the profile. After building the profiles, the average fitness space of the data can be built on it. On the influence of threshold,

7、the class of a record can be recognized. Actually this technology can be treated as a classification on data sets which are unknown. Then we studied the relationship between with detection rate and the relationship between confidence with rulesets scale. Through many simulations, a phenomenon called

8、 step change in detection rate was discovered. In this thesis, KDD CUP1999 is used to evaluate the performance of the proposed method. get higher detection rate. Both the training set and testing set are selected randomly from KDDCUP 1999 data set. The simulation results show that the proposed metho

9、d get higher detection rate.Keywords: Data Mining; Anomaly Detection; Association Rule; Average fitness space目 录1 绪论11.1本文的研究背景和意义11.2 国内外研究现状21.3 本文组织结构32 挖掘关联规则的基本算法42.1 关联规则的概念和产生方法42.2 频繁项集挖掘算法52.2.1 Apriori算法原理52.2.2 Apriori算法评价72.2.3 Apriori算法改进82.3 由频繁项集产生关联规则83 基于规则的分类103.1 分类的基本概念103.2 常用分类

10、方法103.2.1 决策树归纳法103.2.2 贝叶斯分类法113.2.3 关联规则分类法114 异常检测及其仿真分析134.1 数据的预处理134.1.1 数据抽取134.1.2 属性选择134.1.3 离散化处理154.2 挖掘关联规则184.3 构建平均适应度空间和异常检测204.3.1 平均适应度空间的概念与建立方法204.3.2 对测试数据集的检测和分类225 总结与展望285.1 工作总结285.2 数据挖掘展望296 翻译部分.307 致谢.418 参考文献.429 附录.43第36页中国矿业大学2014届本科生毕业设计1 绪论计算机的发明和普及标志着信息时代的到来，随着计算机技

11、术的不断发展以及生活水平的不断提高，人们对信息的需求越来越大，同时，所需的信息也朝着多元化的方向发展。因此有人把21世纪叫做“信息世纪”。由于人们所需的信息量正在以指数方式飞速增长，面对这些极度膨胀的数据，“人们却无法从表面上看出其中所蕴含的的真正有价值的信息，不断感受着来自信息爆炸和数据过剩的巨大压力”1。因此，如何从数据库中存储的海量数据中找到对人们有用的信息，也就是把“数据”变成“知识”的过程成了人们关注并研究的重点。1.1 国内外研究现状1980年4月，J. P. Anderson做了题为Computer Security Threat Monitoring and Surveilla

12、nce的报告，第一次提出了入侵检测的概念21。进入90年代后，入侵检测技术就进入了快速发展阶段，神经网络和智能系统也开始与之相结合，同时，数据挖掘技术和自适应技术也开始应用到入侵检测当中去。进入21世纪后，由于物联网的发展和普及，人们开始考虑改进检测算法，使异常检测更加有效。主要集中在分布式检测和基于网络的入侵检测等几个领域。国内的入侵检测研究起步较晚，国内一些重点高校和科研院所也对此进行了相关研究，工业界也开发了相关产品。联想的“网御”便是其中的代表。入侵检测可分为异常检测和误用检测两大类，由误用检测只能检测到已知类型的入侵，不能识别未知入侵；而异常检测则能够识别已知的和未知的入侵，其通用性

13、更强。Hawki首先定义了什么是“异常”。他指出：“如果一个数据样本与其他样本之间存在足以引起令人怀疑的差异，则称其为异常点”8。基于该定义，Kausta提出了检测异常数据的方法。他指出，若一条数据的属性值与正常数据的属性值差别较大，就称之为“异常”。Chan等提出了一种基于关联规则的异常检测算法LERAD ，“该算法利用产生关联规则时置信度计算思想，从概率的角度预测每个样本中各属性出现的概率，建立异常检测模型”9。当前的异常检测技术，一般采用从正常类的已知数据中进行学习，建立起正常数据的行为模型（也叫轮廓），然后对位置数据也建立起这样一个模型并与正常模型进行比较，通过阈值的作用来判断其是否为

14、入侵。显然，这种行为模型的建立需要数据挖掘技术作为支持。数据挖掘也叫做数据库中的知识发现(Knowledge Discovery in Database,KDD)。1989年8月，第11届国际人工智能联合会议在美国底特律召开，在会议的专题讨论会上，专家们首次提出了数据库中的知识发现(Knowledge Discovery in Database,KDD)这个概念。“在此之后，KDD会议在世界各地陆续召开了八次，研究重点也逐渐由发现方法转为系统应用，以及多学科之间的相互渗透”4。数据挖掘的一个重要领域是关联规则挖掘。“从大量商务事物记录中发现有趣的关联关系，可以帮助许多商务决策的指定，如分类设计

15、、交叉购物和贱卖分析等”5。关联规则挖掘最早由Agrawal在1993年提出来。之后Apriori算法便被研究者提了出来，这是一种最有影响的挖掘布尔关联规则频繁项集的算法，也是关联规则挖掘的最基本的算法。但是该算法需要生成大量的频繁项候选集共筛选，因此加大了内存的开销。之后一种不产生候选频繁项集的挖掘方法被提了出来，即频繁模式增长（frequent-pattern growth）,简称FP-增长，从而大大降低了搜索开销。起初，关联规则挖掘仅仅用于对数据相关性的概念性描述，“1997年Ali等人提出了将关联规则用于部分分类的思想”6，但没有取得实质性进展。直到1998年，在纽约召开的国际KDD会

16、议上，Liu Bing等人提出了将挖掘出的关联规则用于分类的算法，即所谓CBA算法，关联分类研究的大门才被真正打开。该算法来源于Apriori算法，但与之又有所不同。2001年，Li等人提出了新的CMAR算法，CMAR 算法在分类准确率和算法效率上要优于 CBA 算法，但 CMAR 算法需要更多的内存。之后，国外的研究者们又相继提出了CPAR、FCMAR以及Apriori-TFP-CMAR等各种改进方法，使得关联分类算法得以不断完善和发展。国外对资料挖掘技术的研究起步较早，许多国际知名的大公司都在该领域的研究上投入了大量人力和物力，这无疑给资料挖掘技术带来了难得的发展机遇。目前，世界上典型的数

17、据挖掘系统有：Sybase公司的Warehouse Studio；SAS公司的Enterprise Miner；SPSS公司的Clementine；IBM公司的Inielligent Miner；RuleQuest Research公司的See5；SGI公司的Setminer.除此之外，微软（Microsoft）公司，Oracle公司以及MapInfo公司也都开发了自己的数据挖掘产品。与国外相比，国内对资料挖掘的研究起步较晚，但发展十分迅速。1993年，国家自然科学基金首次支持该领域的研究项目，在此之后，国内的许多科研院所及重点高校便开始投入到数据挖掘的理论和应用研究中，取得了一批具有重要影响

18、力的研究成果。目前国内从事数据挖掘研究的单位包括：中国科学院计算技术研究所、空军第三研究所、中国科学院数学研究所、清华大学、中国科学技术大学、复旦大学、北京大学、南京大学、上海交通大学、华中科技大学等。基于关联规则的分类是一种新的分类方法，该方法虽然有效，但发展还不成熟，还有诸多问题需要改进。首先该算法需要产生大量的频繁数据项集，这无疑加大了对内存、CPU等系统资源的开销。尤其在挖掘大型数据库中的规则时，这一不足暴露得更加明显；其次，为了避免遗漏潜在的、有价值的知识,“通常都在低支持度下挖掘规则,因而产生了大量的冗余规则”7，这便大大剧了规则枝剪的工作量；第三，该方法产生的分类器往往较为复杂，

19、不便于被人们理解。因此，基于关联规则挖掘的分类与检测方法还有待于人们进一步研究与改进。1.2本文的研究背景和意义 数据挖掘就是从数据库的大量数据集中找到人们感兴趣的，对人们有用的信息的过程。现代的大型数据库中存储着大量的数据，传统的利用数据库的手段是从数据库中直接提取相关数据集，如储户要从银行的数据库中查询自己账户的交易信息。而对于数据库拥有者（如银行）而言，他们还有一项重要任务是对数据库中的数据进行分析，发现一些事先并不知道的，但又是有趣的东西。“数据挖掘就是利用各种分析工具在海量数据中发现模型以及数据间的关系，这些模型和关系可以用来作出预测”2，因此，了解并掌握这些规律对于决策者而言往往具

20、有重要意义。异常检测(Anomaly Detection)技术同样是伴随着信息时代的到来而产生的。由于当今的Internet大多采用开放式结构，人们可以轻松地获取网络中的各种信息，同时也带来了网络安全性的问题并越来越引起了人们的注意，加之Internet所采用的TCP/IP协议几乎没有将安全问题考虑在内，所以研究并发展网络安全产品使互联网免遭不良入侵，使其安全稳定运作对互联网的长远发展具有重要意义。随着信息技术的进步，各种安全产品蜂拥而至，如已发展成熟的防火墙技术、身份认证技术等，都属于传统的进入控制技术。但这些手段也有失效的时候，为了保证网络和计算机系统的安全，需要在最后加一道防线，即所谓异

21、常检测，使入侵在进入之前被发现，从而避免系统遭到而已攻击。“异常检测基于已掌握了的被保护对象的正常工作模式，并假定正常工作模式相对稳定，有入侵发生时，用户或系统的行为模式会发生一定程度的改变”3，通常方法是收集大量正常访问的数据，研究其特征，并建立起正常行为轮廓(Profile)需要检测异常入侵时，就将当前活动与其作比较，判断是否有较大偏差，如果是，就将其判定为异常行为，即入侵活动，并发出告警。这里有两个关键问题，一个是怎样从大量正常访问的数据中提取特征，另一个是怎么把待检测活动与正常活动的特征作比较。要解决第一个问题就需要数据挖掘技术的支持，如前所述，数据挖掘技术解决的就是在大量数据中发现规

22、律和特征的问题。要解决第二个问题就要利用“平均适应度”这个概念，这样能较客观地比较当前活动和正常行为轮廓之间的差异，为异常活动的判断提供关键依据。本文研究的就是如何将数据挖掘技术和基于“平均适应度空间”的判断技术结合起来，使得异常活动能够准确、快速地被检测到，从而保障计算机和互联网系统的安全。本文尝试将数据挖掘和异常检测技术结合起来，使异常检测更加有效。1.3 本文组织结构 第一章 绪论。本章主要讲述了本文的研究背景和意义、数据挖掘技术和异常检测技术在国内外发展的现状。另外介绍了本文主要的研究内容和方法以及本文的提纲框架。第二章 挖掘关联规则的基本算法。本章首先对数据挖掘特别是关联规则挖掘的基

23、本概念和理论做了简单介绍，其次针对数据挖掘的基本算法Apriori的原理和方法做了较为详尽的叙述。第三章 分类方法。本章先介绍了数据挖掘中常用的分类方法，然后对叙述了本文所采用的方法，以及用该方法构造的分类器。第四章 数据挖掘在异常检测中的应用。本章研究了如何用上一章中构造的分类器来对未知数据项进行分类，从而判断其是否为异常项。并且进行了仿真测试，对该方法的有效性做了评价。第五章 总结与展望。本章对本次研究工作做了总结，分享了心得，指出了不足和今后改进的方向。2 挖掘关联规则的基本算法数据挖掘的种类有很多，近年来活跃在人们研究领域中的是关联规则挖掘。它挖掘的知识主要是频繁模式及由此生成的关联规

24、则。即对数据库进行分析，找到那些属性值频繁地共同出现在一项数据中，这就蕴含了属性值之间的相互联系，这种联系往往是重要的，因为它一定程度上描述了该类数据的特征，这就为的分类提供了重要的依据。关联规则最早被用来发现顾客交易数据库中不同商品之间的联系，也有人称之为“超市购物篮分析”。对超市经理来说，发现顾客频繁购买的商品组合可以为商品正确摆放提供重要依据。本章将介绍经典挖掘算法：Apriori算法。2.1 关联规则的概念和产生方法【定义2.1】设是项的集合，则称为一个项集。包含个项的项集称为项集。根据以上定义，可以把数据库中的每个事务作为一个非空项集，即。且每一个T都有一个唯一的标志，记为。【定义2

25、.2】设是一个项集，关联规则是形如的蕴含式，其中，且。【定义2.3】设所构成的事务集为，规则在事务集中成立，那么这条规则的支持度就定义为中事务包含的百分比，即 (2.1)支持度通常简写为。【定义2.4】设在事务集中有规则，其置信度就定义为中包含的事务同时也包含的事务的百分比，即 (2.2)支持度通常简写为。由式(2.2)，有如下关系：= = (2.3)其中，叫做项集的支持度计数，简称计数，是事务集中包含项集的事务数。【定义2.5】如果项集的支持度满足预定义的最小支持度阈值，则称是一个频繁项集，通常记为。【定义2.6】如果规则即满足最小支持度阈值，又满足最小置信度阈值，那么称它为强关联规则。挖掘

26、关联规则一半要经过两个步骤：(1)找到所有频繁项集这是关联规则挖掘最重要的步骤，频繁项集是强关联规则产生的及时，它的效率直接影响到数据挖掘的效率，进而影响到后面的分类和预测。根据定义，挖出的规则都要满足最小支持度阈值限制。(2)由频繁项集产生强关联规则由于上一步已经产生了频繁项集，这一步就较为简单，只要生成的规则满足最小置信度阈值限制。2.2 频繁项集挖掘算法2.2.1 Apriori算法原理“Apriori算法最早是由Agrawal和R.Srikant于1994年提出的”10，这是挖掘布尔型数据频繁项集的基本算法，该算法产生后，大量学者对此算法做了深入研究，并提出了许多改进算法以提高其效率。

27、该算法采用了逐层迭代的思想，即通过生成好的项集产生项集，再对其进行筛选。该算法首先遍历数据库，统计各个属性值的出现频度，根据预先设定的最小支持度，找到满足这个阈值的属性值。每个属性值即可构成一个频繁1项集集合，再由自连接产生2项频繁候选集，然后筛选出满足最小支持度阈值的项集，构成频繁2项集集合，如此往复进行下去，知道某一项集集合为空。由于项集自连接会产生大量的项集，因此就要频繁遍历数据库，这就产生了很大的搜索量。于是引入了一个先验知识来压缩搜索空间，从而提高算法的效率。表述如下：【性质2.1】频繁项集的所有非空子集也是频繁的。由该性质易得到如下推论：【性质2.2】任何非频繁项集都不是频繁项集的

28、子集。可以利用该性质压缩候选项集的数量：在项集自连接产生项候选集集合后，考察项集的所有项子集，如果有任意一个子集不在中，那么就将该项集就从中删除，这样就能大大减少中项集的数量。下面通过一个具体例子来说明这种算法。【例2.1】给出AllElectronics的事务数据库如下：表2-1 All Electronics某分店的事务数据TID商品ID号列表T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3第一步：扫描中的所有商品，统计每个商品出现的次数，得到。第

29、二步：假设,删掉不满足这个阈值的项集，得到。第三步：将L1做自连接产生。第四步：统计其中每个项集的出现次数，删去那些不满足的项集，这样就得到了。第五步：将做自连接产生。第六步：利用性质(2.2)，检查其中每个项集，一旦发现某个项集的某个2项子集不在L2中，就将该项集删去，得到枝剪后的。第七步：统计中每个项集的出现次数，删去那些不满足的项集，这样就得到了。第八步：自连接产生，重复4-7步，发现得到的是空集，算法至此结束。图示如下：扫描D，对每个候选计数项集支持度计数I1I2I3I4I567622用最小支持度筛选项集支持度计数I1I2I3I4I567622由L1产生候选C2C2项集I1，I2I1，

30、I3I1，I4I1，I5I2，I3I2，I4I2，I5I3，I4I3，I5I4，I5扫描D，对每个候选计数项集支持度计数I1，I2I1，I3I1，I4I1，I5I2，I3I2，I4I2，I5I3，I4I3，I5I4，I54412422010C2用最小支持度筛选项集支持度计数I1，I2I1，I3I1，I5I2，I3I2，I4I2，I5442422L2由L2产生候选C3C3项集I1，I2，I3I1，I2，I5扫描D，对每个候选计数C3用最小支持度筛选项集支持度计数I1，I2，I3I1，I2，I5 22 L3项集支持度计数I1，I2，I3I1，I2，I5 22 C1L1图2-1 Apriori算法原

31、理2.2.2 Apriori算法评价Apriori算法具有以下优点：1 原理简单、容易理解、便于实现；2 采用了先验知识压缩了搜索空间；3 对数据库进行完整详尽的扫描，挖出的信息量大。当然，该算法也有一些不足，比如它需要大量重复遍历数据库，当数据项较多时，会产生大量的候选集项，不便计算。 “尤其是候选2项目集的情况最为严重，因为相当于计算了所有的项目集”11。2.2.3 Apriori算法改进 由于基本Apriori算法有一些不足之处，为了提高它的运算效率，人们研究并提出了很多改进的方法，现归纳如下：(1)事务压缩：采用事务集划分技术，只需要两次遍历数据库就能找出符合要求的频繁项集。首先把划分

32、成若干分区，对每个分区找到局部频繁项集，这些项集，这些项集就构成了的全局候选项集。之后再扫描，根据候选项集的支持度确定全局频繁项集。(2)抽样技术：方法是从事务集中抽出一个随机样本,然后在中搜寻所需的频繁项集。这种方法虽然牺牲了所搜精度（因为它可能丢失了部分全局频繁项集），但大大减少了搜索的空间，从而提高了算法的有效性。(3)基于散列的技术：其基本思想还是压缩候选项集集合，例如：由候选频繁1项集集合产生频繁1项集集合时，可以将每个事物产生的所有2项集映射到散列表的桶中，并统计桶计数。然后将桶支持度计数不满足阈值的桶内的所有候选项集清除，这样就可以在很大程度上压缩项候选集，特别是在时，应用散列技

33、术的效果尤为明显。(4)动态计数项集：也是将数据库划分为若干块，并用开始点标记以便区分，这样新候选项集就可以在开始点处添加。将迄今为止的计数与最小支持度计数作比较以决定该候选项集的取舍，这种方法也能减少对数据库的遍历次数。2.3 由频繁项集产生关联规则频繁项集的挖掘是关联规则生成的基础和直接依据，由于Apriori算法已经生成了频繁项集，那么关联规则便可以顺理成章地产生了。这里的关联规则通常指的是强关联规则（即同时满足最小支持度和最小适应度限制）。由于之前已经产生了满足最小支持度要求的频繁项集，由它生成的规则也就相应的满足最小支持度。因此这里主要考虑的是置信度。置信度可以根据式(2.3)来计算

34、，这实际上是一个条件概率，由该式可以得出强关联规则的产生法则，步骤如下：（1）对每个频繁项集产生它的所有非空子集；（2）对每个非空子集计算支持度；（3）得到每个非空子集的支持度计数。由于Apriori算法已经统计了频繁项集的支持度，这里只需到存储他们的散列表里查阅即可；（4）写出可能生成的所有关联规则，这里就是除频繁项集本身外的所有非空子集，是的补集，也是频繁项集的非空子集；（5）按式(2.3)计算关联规则的置信度，其中分母便是的支持度计数，分子便是包含元素最多的非空子集的支持度计数；（6）将每一条关联规则的置信度与最小置信度作比较，删除那些不满足最小置信度要求的关联规则，剩下的规则便是强关联

35、规则。下面通过一个例子来说明：【例2.2】 例2.1中得到有频繁项集=I1，I2，I5，下面以此频繁项集为基础在AllElectronics事务数据库中产生强关联规则。的非空子集有7个，分别是：、I2、I5、I1，I2、I1，I5、I2，I5和I1，I2，I5。它们的支持度计数分别为：6、7、2、4、2、2、2 。现写出所有可能的强关联规则，并计算其置信度：I1I2，I5，置信度（confidence）=2/6=0.33I2I1，I5，置信度（confidence）=2/7=0.29I5I1，I2，置信度（confidence）=2/2=1.00I1，I2I5，置信度（confidence）=

36、2/4=0.50I1，I5I2，置信度（confidence）=2/2=1.00I2，I5I1，置信度（confidence）=2/2=1.00如果设定最小置信度阈值为60%=0.60，那么满足条件的规则就有：(1) I5I1，I2(2) I1，I5I2(3) I2，I5I1它们便构成了强规则集，这是下一步做分类和检测的重要依据。3 基于关联规则的分类分类是数据挖掘的重要研究领域，“目前，分类技术在统计学、模式识别以及机器学习等方面发挥了重要作用”12，简单地说，分类就是挖掘研究数据集的规律，建立起一个刻画数据类的模型（也叫分类器），然后用它来预测未知数据的类别属性，输出一个离散的类别标签值。

37、3.1 分类的基本概念通常的数据都有若干个属性组成，而这些属性中有一个属性很特殊，那就是类别属性，或者叫类别标签。它决定了这条数据的类别特征，不同的数据如果具有相同的类别属性值就叫同一类数据。例如：网站的访问可以分为正常访问和入侵，那么就可以将访问记录分成正常和入侵两类。要做的就是构造一个分类器，用于检测一条未知的访问记录属于正常访问还是入侵。当然还可以将数据划分成几种不同类别，即类别属性值可以有种，分别标记成A、B、C等，这里类别属性值必须是离散值。通常情况下，分类过程可以分成两个阶段：第一阶段：学习阶段。也叫训练阶段，采用的数据集叫训练数据集。这里需要知道数据集的所有属性值（包括类别属性值

38、），据此构造一个分类器。由于预先知道了数据是属于哪一类的，因此这种学习方式也叫监督学习，以区别于另一种无监督学习方式，即事先不知道数据集中的数据分别属于哪一类，需要将数据分成几个类别也不知到。这种无监督的学习方式称为聚类。由于本文采用的分类方法是基于监督学习的，因此本文只讨论前一种学习分类方法。第二阶段：分类阶段。这一阶段主要是检测第一阶段构造的分类器的性能，测试其分类的准确率。采用的数据叫测试数据，在这里，数据的类别属性值是未知的，需要通过分类器的判断来确定它属于哪一类，即得出每条数据类别属性的值，然后将预测值与实际值作比较，然后统计出分类的准确率和误检测率，从而判断分类器分类效果的好坏。3

39、.2 常用分类方法下面介绍三种常见的分类方法，分别是：决策树归纳法、贝叶斯分类法、关联规则分类法。这里着重讲解第三种分类法，对前两种方法只做简单介绍。3.2.1 决策树归纳法决策树是一种特殊的树结构，它和流程图有相似之处，由内部结点、终端结点、根结点和很多分支组成。其中类别属性值存放于终端节点中。在分类时，将未知类型的待测试数据的属性值在改决策树上测试，这样就能画出一条由根结点到叶结点的路径，找到了相应的叶结点就找到了该数据所属的类别。经过简单转换处理，决策树就成了熟悉的分类规则。这种分类方法比较直观易懂，实现起来较为容易，精确度较好，分类速度也较快，并且对高维数据的分类尤其有效。另外，这种分

40、类器的构造不需要先验知识，因此适合于探索式的知识挖掘和发现。目前，这种分类方法在金融学、生物医学、工业生产等领域都得到了广泛的应用。3.2.2 贝叶斯分类法如果将统计学中的分类方法引入数据挖掘中的分类问题中，便形成了一种新的分类方法贝叶斯分类法。这种分类方法基于概率论中的贝叶斯定理，它给出了一种由先验概率计算后验概率的方法。表述如下： (3.1)该分类方法是通过给定一个数据的维属性向量，来确定在条件下，属于某一类型的后验概率，然后将具有后验概率的类型作为这条数据所属的类型。这种分类方法称为朴素贝叶斯分类。从理论上讲，这种方法的错分率最低。但在实际中，由于各种条件的限制，错分率也可能较其他方法高

41、。3.2.3 关联规则分类法基于关联规则的分类(Classification Based on Association)，简称CBA，最早由新加坡国立大学的Bing Liu、Wynne Hsu和Yiming Ma等人提出。它将数据挖掘中的两个重要领域关联规则挖掘和分类技术结合到了一起，将挖出的强关联规则有效地应用到了数据分类中，并取得了很好的效果，为分类技术的研究开辟了一个新的路径。这种方法挖掘出的规则集叫做分类关联规则(class association rules)简称CARs，“包括两个阶段：规则生成(CBA-RG)，和分类器构造(CBA-CB)”13，其中关联规则的生成算法类似于Apr

42、iori算法，然后用产生出的分类关联规则CARs构造出分类器。由于挖掘出的关联规则往往较多，这就需要对规则进行比较以选出更好的分类规则。首先比较规则的置信度，如果置信度相同就比较支持度，如果前两个指标都相同，那么就将先产生的规则作为好的规则。这种方法的详细论述和分析见参考文献13。本文所采用的分类方法也属于关联规则分类法，因为分类的依据是由挖掘出的频繁项集产生的强关联规则，考虑到这种分类是用于异常检测的，前面已经提到，基于异常的入侵检测需要构造正常访问的行为模型（也称轮廓），这里便把挖出的关联规则作为这种轮廓。具体方法见第四章。这里的轮廓就相当于CBA中的分类器(Classifier)。本文所

43、做的分类实际上就是比较，比较未知类型的数据与轮廓(profile)的偏离程度。这里的比较是基于平均适应度空间的，也就是通过计算正常访问数据对轮廓的平均适应度，建立一个平均适应度空间（这里是一维的，可以当做一个向量）提取其有用的特征值（这里用均值+方差的模式）作为阈值。再计算未知类型的数据对轮廓的平均适应度，同样建立出一个平均适应度空间（向量），向量的分量对应一条数据（项目）队轮廓的平均适应度，将各个分量与阈值做比较，超过这个阈值便被判定为入侵，相当于将该条数据分为入侵类；反之就认为是正常访问，相当于将该条数据分为正常类，这样便实现了所谓入侵检测，也就完成了对未知类型数据的分类工作。这里的正常数

44、据就是第二章中提到的训练数据，未知类型的数据（包括正常数据和入侵数据）就是测试数据。该方法的详细步骤见第四章。本文所采用的分类与检测原理如下图所示：正常访问记录正常访问的行为模式 当前访问记录平均适应度空间平均适应度空间分类阈值Q正常入侵图3-1 基于平均适应度空间的分类原理这种分类方法的好处是： 它利用了规则集中的全部数据，最大限度地保留了数据挖掘得到的信息，且实现起来较为容易，同时易于理解。 4 异常检测及其仿真分析这一章，尝试将挖掘出的强关联规则用于分类，即通过构造正常访问数据对轮廓的的平均适应度空间来检测数据是否正常，主要包括挖掘规则和测试数据两块内容，分别对应于第二章中提到的训练阶段

45、和测试阶段。采用的仿真工具是matlab（软件版本：6.1）。4.1 数据的预处理本文研究所用数据源自国际知识发现和数据挖掘竞赛(KDD-CUP 1999)提供的标准数据集，这些数据全部来自网络上对访问数据的真实记录，具有较高的可信度，可以作为研究使用。在进行数据挖掘工作之前，需要对原始数据进行处理，包括抽取、属性选择和离散化三个方面。4.1.1 数据抽取实验所采用的每条数据包含42个属性，其中前41个属性为普通属性，最后一个是数据类别标签，其值就是这条数据所属的类别标签号，包括正常(normal)和入侵(intrusion)两大类，其中入侵类型的数据又包含诸如smurf、neptune、ba

46、ck等多种类别。之前已经说明，数据分类需要两部分数据：训练数据和测试数据。根据异常检测的原理，先从61235条数据中随机抽取1000条正常数据（即第42个属性值为normal）作为训练数据，用来挖掘关联规则。这里在数据库软件平台(Microsoft Access)上采用SQL语句实现随机查询功能。首先新建数据库，然后将61235条数据导入表中，表名取做Sheet1，然后在SQL视图下，对Sheet1执行查询操作，指令语句如下：SELECT TOP 1000* FROM Sheet1 WHERE 字段42=”normal.” ORDER BY RND字段1系统自动生成一个名叫“查询1”的表格，其

47、中就包含了随机筛选出的1000条正常数据。然后将查询得到的数据导入到EXCEL工作表中，取名book1。至此，原始训练数据就产生了。还需要照此方法产生测试数据。首先考虑测试500条非正常数据，因此需要从61235条数据集中随机抽取非正常数据，SQL查询语句如下：SELECT TOP 500* FROM Sheet1 WHERE 字段42”normal.” ORDER BY RND字段1然后也将其导入book1工作表中，排列在1000条正常数据之后。4.1.2 属性选择 由于所用数据集包含42个属性，“海量的实际数据中无意义的成分很多，严重影响数据挖掘算法的执行效率”15，因此就需要从大量的属性

48、中按照一定的准则选取一个子集，使属性空间得到约减，这对节约计算机资源开支、提高算法效率具有重要意义。本文拟采用信息增益度量的方法选取属性。对数据集中的每条数据（元组）进行分类所需要的期望信息增益定义如下： (4.1)其中，是类别个数，即在数据集上定义了个不同的类，分别记做、；是中任意一条数据属于类的概率，用中属于类的元组个数和中元组总数的比值近似计算。式(4.1)从信息论的角度定义了判断D中元组所属的类所需的平均信息量。又称的熵(entropy)。下面定义一列属性的熵，对于属性，有如下熵定义： (4.2)其中，表示中属于类元组的个数，表示中元组的总数。式(4.2)给出了基于属性对中的元组进行分

49、类所需的期望信息量。用式(4.1)减去式(4.2)就得到了属性的信息增益，即 (4.3) 如果属性A的信息增益大，就说明对于分类别所起的作用大，这类属性应该被保留，反之就说明对于分类起的作用小，这类属性可以考虑除去。式(4.3)是选择属性的主要依据。由式(4.1)和式(4.2)易知，如果有一列属性在两类数据集（正常和入侵）中都有相同的取值，即训练数据集和测试数据集中的每条数据在该属性上的属性值均相同，那么就有： (4.4)也就有=0，这说明此属性对分类不起作用，对分类来说可有可无，那么可以直接将其剔除。 现需要考察Book1中的数据分布规律。为方便起见，在Excel 2007软件中安装一个插件

50、叫做“SQL Server 2005数据挖掘外界程序”以方便预览数据并且对之后的数据离散工作提供便利。首先需要在计算机上安装SQL Server 2005数据库软件，由于数据挖掘加载项必须连接SQL Server 2005 Analysis Services才能正常运行，因此必须确保SQL Server 2005中的Analysis Services正常工作。接下来就需要将SQL Server 2005数据挖掘外界程序安装在计算机上并完成相关配置工作，之后还需要修改Excel 2007中的一些参数使得安装的加载项能够正常运行。在完成上述工作后，打开Excel 2007就能看到“数据挖掘”选项卡

51、，如图4-1所示：图4-1 增加数据挖掘功能的Excel软件下面选中一列属性值，点击数据挖掘选项卡中的“预览数据”按钮，就可以看到这条属性的取值情况，如果它只取得单一的值，或只有零星的离群值，那么就将这条属性所在的一列数据删除。按照这种方法最终得到的数据有22个属性值。至此，属性筛选工作就完成了。4.1.3 离散化处理 由于本实验所采用的数据集中含有大量连续数据，是无法直接用来提取规则的，这就需要对其进行离散化处理。离散化的方法有很多，如：通过分箱离散化、通过直方图分析离散化、通过聚类和决策树离散化、通过相关性分析离散化等，这里只采用简单的人工离散化方法，即通过几个点将连续数据取值区间分成几个

52、等长或不等长的子区间并对每个区间标号，然后将落入该区间的所有数据一律用对应的标号代替，采用的工具依然是带有数据挖掘加载项的Excel 2007。考虑到有些属性的取值范围较大，且数据在取值区间上的本部不均匀，需要继续考察数据的本部情况以确定子区间分裂点的选取。下面以其中一列数据为例说明：选中该列数据，依次点击“数据挖掘-清除数据-离群值”，就可以看到该列属性值的分布情况，如图4-2所示：以上数据量属性值图4-2 原始数据属性值分布由图可以看出，随着值的增大，大于它的数据的数量逐渐减少，图中可以看到一个明显的拐点，超过这个拐点横坐标的数据数量近乎为零，用移动光标携带纵轴，将改点以上的所有数据记为空

53、（null）并做就地修改。之后再点击“预览数据”按钮，可以看到数据被存储桶分成了等宽度的几块，这里桶的数量选为4，如图4-3所示：数据量 离散区间图4-3 一次离散后数据分布情况由图可知，第二个存储通包含的数据量过大，这样的离散会丢失大量的信息，因此需要将其进一步细分。需要继续对离群值做标记，照上面的方法，依次点击“数据挖掘-清除数据-离群值”，可以看到数据的分布发生了明显变化，如图4-4所示：以上数据量属性值图4-4 一次离群值清理后数据分布情况移动坐标轴，选中阴影区为清理对象，将其标记为空，再次预览数据，可以看到这次数据在每个存储桶的分布就较为均匀了，如图4-5。数据量离散区间图4-5 二

54、次离散后数据分布情况如果数据分布还不够理想，可以继续标记离群值，预览数据，直到数据在存储桶中的分布足够均匀为止。在完成上述工作后，点击“添加新列”按钮，就将原始数据替换成其所对应的区间。在这里，空值（null）就表示大于最高的存储区间的上限（或小于最低存储区间的下线）的所有值。由于每个数据都用所在区间表示，不方便阅读和观察，可以将不用区间用简单的数字作为标记。，例如：区间0-160可以用数字1代替，区间null可以用数字2代替，以此类推。需要说明的是：由于本实验采用的数据集是以表的形式存放的，它不同于事务型数据集（如超市记录的每个顾客购买商品的记录），这里每一条数据（元组）都由若干个属性构成，

55、这里的属性就相当于事务数据集中每个事务包含的内容（顾客购买的商品名称），由于采用的Apriori算法程序是为挖掘事务型数据集而设计的，即它不识别属性编号，对不同列的相同的数据等同对待，这显然不能帮助挖掘表格数据的规则，因此，要对数据做一些处理，使它变成事务型数据，但又不丢失属性编号的信息。这里采用的方法是将每列数据的数字前面加上相应的列编号，比如，第一条数据的第五个属性值已经离散化，结果为1，那么就在这个数字前加上5，使其变成5.1。这样，在Apriori算法得出规则后，只要见到5.1，就表示它代表第五条属性的第一个离散值。对于原本就是离散的数据，则不需要离散化处理，只在原数据前加上相应的列标

56、号即可。至于如何替换、修改数据，可以依次点击数据挖掘-清除数据-重新标记，将数据替换为“列标号.属性标号”的形式，如图4-6所示：图4-6 为离散后的数据标号照此方法将所有连续数据离散化，并对所有数据做列标记，然后将训练数据与测试数据分开，接着分别将其从Excel工作表中导出并保存在文本文档中，分别取名“训练数据”和“测试数据”。至此，数据预处理工作就全部完成了。4.2 挖掘关联规则关联规则的挖掘是本次试验最重要的工作，因为挖出的规则直接决定了分类和检测的效果，由于Apriori算法是一种简单有效地算法，且自诞生之日起经过了无数人的检验，成为关联规则挖掘的经典算法，因此本实验仍采用经典Apri

57、ori算法。算法原理详见第二章。根据该算法的原理，现编写Apriori算法源代码如下：(1) C1=candidate1-itemsets;(2) L1=cC1|c.countminsupport;(3) for(k=2,Lk-1,k+) /直到不能再生成最大项目集为止(4) Ck=sc_candidate(Lk-1); /生成含k个元素的侯选项目集(5) for all transactions tD /办理处理(6) Ct=count_support(Ck,t); /包含在事务t中的侯选项目集(7) for all candidates cCt(8) c.count=c.count+1;(9) next(10) Lk=cCk|c.countminsupport;(11) next(12) resultset=resultsetLk其中，表示数据库；表示给定的最小支持度；resultset表示所有最大项目集。Sc_candidate该函数的参数为，即：所有最大维项目集,结果返回含有个项目的侯选项目集。事实上，是维最大项目集的超集,通过函数count_support计算项目的支持度，然后生成。根据设计好的源代码，用matlab软件作为编程工具，将其编写成可执行的matlab程序代码。由于需要读取数据，本设计考虑将训练数据以文本的格式存放在记事本中（文件后缀为txt），