基于决策树算法的网络入侵检测研究分析

基于决策树算法的网络入侵检测研究摘要随着现代互联网的快速发展以及规模的不断扩大，网络信息技术已经进入了千家万户。人们在享受网络带来的方便快捷的同时，也不得不面对越来越多的来自网上的恶意入侵。由此可见，人们对于网络信息安全的需求变得越来越迫切。网络入侵会阻碍信息化社会的正常运行，影响社会经济的发展。目前许多国家都投入了大量资金以整治网络安全，但取得的效果并不明显。这不仅仅是因为检测入侵技术的不成熟，更是因为网络入侵的方式正在变的越来越多样化与复杂化。因此，对入侵检测技术进行开发与优化具有重要意义，是急需研究的重要课题。本文共分为五个章节。首先第一章介绍了选题的研究背景与意义，网络入侵检测技术的发展历史与研究现状，然后列出了本文的研究内容与组织结构。其次第二章简单阐述了入侵检测技术和数据挖掘技术的概念，论述了入侵检测系统的通用模型并以数据来源和采用技术为分类标准对入侵检测系统进行了分类，然后对入侵检测的四个工作流程进行了详细叙述。最后详细阐述了决策树构造的过程以及构造规则。之后第三章研究了ID3、C4.5和CART三种经典的决策树算法，给出了他们的原理公式以及分类过程。第四章则以C4.5算法为基础进行改进，并设计实验进行改进前后的算法准确率对比，最终实验证明改进的算法能够运行出更准确的分类结果。最后第五章对全文进行总结展望，并提出工作不足之处。在文章末尾致谢导师以及同学在本文完成的过程中给予的宝贵指导意见与建议。关键词：数据挖掘；决策树；网络入侵检测；入侵检测系统；C4.5算法

AbstractWiththerapiddevelopmentofmodernInternetandthecontinuousexpansionofitsscale,networkinformationtechnologyhasenteredthousandsofhouseholds.WhileenjoyingtheconveniencebroughtbytheInternet,peoplehavetofacemoreandmoremaliciousintrusionsfromtheInternet.Thus,people'sdemandfornetworkinformationsecuritybecomesmoreandmoreurgent.Networkintrusionwillhinderthenormaloperationofinformationsocietyandaffectthedevelopmentofsocialeconomy.Atpresent,manycountrieshaveinvestedalotofmoneytoimprovenetworksecurity,buttheeffectisnotobvious.Thisisnotonlybecausetheintrusiondetectiontechnologyisnotmature,butalsobecausethewayofnetworkintrusionisbecomingmoreandmorediversifiedandcomplex.Therefore,itisverymeaningfultodevelopandoptimizetheintrusiondetectiontechnology,whichisanimportantsubjectinurgentneedofresearch.Thispaperisdividedintofivechapters.Thefirstchapterintroducestheresearchbackgroundandsignificanceofthetopic,thedevelopmenthistoryandresearchstatusofnetworkintrusiondetectiontechnology,andthenliststheresearchcontentandorganizationalstructureofthispaper.Thesecondchapterbrieflyexpoundstheconceptsofintrusiondetectiontechnologyanddataminingtechnology,discussesthegeneralmodelofintrusiondetectionsystem,classifiesintrusiondetectionsystembasedondatasourceandtechnology,andthendescribesthefourworkingprocessesofintrusiondetectionindetail.Finally,theprocessandrulesofdecisiontreeconstructionaredescribedindetail.ThenthethirdchapterstudiesthethreeclassicdecisiontreealgorithmnamedID3,C4.5andCART,andgivestheprincipleoftheirformulaandtheclassificationprocess.ThefourthchapterisbasedontheC4.5algorithmtoimprove,anddesignexperimentstocomparethealgorithmaccuracybeforeandaftertheimprovement.Finally,theexperimentprovesthattheimprovedalgorithmcanrunmoreaccurateclassificationresults.Atlast,thefifthchaptersummarizesandforecaststhewholepaper,andpointsouttheshortcomingsofthework.Attheendofthearticle,Iwouldliketothankmytutorandclassmatesfortheirvaluableguidanceandsuggestionsduringthecompletionofthispaper.Keywords:datamining;decisiontree;networkintrusiondetection;intrusiondetectionsystem;C4.5algorithm目录TOC\o"1-3"\h\u23299摘要 I8838Abstract II19610第一章绪论 1141951.1.研究背景与意义 1150621.2.国内外网络入侵检测技术研究现状 1100681.3.论文主要研究途径 2303581.4.论文组织排版 28330第二章入侵检测技术与数据挖掘技术简介 365792.1.入侵检测技术概要 3201282.1.1入侵检测技术的定义 3323342.1.2入侵检测系统的通用模型 387962.2.入侵检测系统的分类 3301882.3.入侵检测系统的工作流程 4262702.4.数据挖掘技术的概念 5246292.4.1产生背景 54732.4.2数据挖掘的内涵 6239102.5.决策树算法概述 61600第三章三种经典决策树算法研究 888013.1.ID3算法 8282593.1.1信息熵、条件熵和信息增益 8153273.2.C4.5算法 9190643.3.CART算法 95961第四章C4.5算法研究 11168574.1.经典C4.5算法对数据集的分类流程 1129824.2.仿真实验 11224224.2.1数据集选择 1171334.2.2编程软件 11133594.2.3算法详解 118384.3.实验结果 1324007第五章全文总结 145240参考文献 1512729附录 166700致谢 23绪论研究背景与意义在全球化趋势下，因特网络已经渗透到我们社会经济、文化和科学的各个领域。每个人都需要应用互联网进行日常工作。而对于信息系统来说,由于不同的信息系统依靠网络进行相互连接，因此所衍生出的重要的安全问题是由用户或软件引起的恶意的或不期望发生的非法入侵。而且这种网络入侵现象伴随着网络的广泛应用也变得越来越频繁，入侵模式也变得越来越新颖。传统计算机系统的第一道防线，如数据加密、防火墙、VPN和身份识别等静态防御手段[1]，虽然在互联网发展的初期显示出了很好的防御效果。但是由于系统不可避免的漏洞和网络入侵技术的不断升级，也开始暴露出不少的缺点。例如防火墙技术，作为普通家用计算机中最常见的防御手段。虽然它可以识别用户身份，不允许未知的用户登录到计算机账户上。但如果入侵者利用某系程序绕过防火墙，或者采用一些以前防火墙未曾检测到过的新技术，那么防火墙就显得非常脆弱了。由此可以看出，传统的静态防御技术虽然有效，但仍然存在不足，急需人们开发出新的攻击防御手段。在大环境的需求下，人们开始研发一种积极动态的安全防御机制—入侵检测技术[2]。作为对传统防御技术的缺陷的弥补。入侵检测技术能够实时的监控网络的状态又不影响网络的正常运转，在入侵发生的时候主动进行防御，同时对入侵的信息进行采集和分析，并在入侵后将本次入侵的数据信息存储起来，以便管理员进行分析。下次若遇见相同类型的入侵能够更加快速高效的进行提前预防和响应。提高了信息的安全性，同时加强了管理员对网络安全的管理能力。决策树是数据挖掘技术中的一种分类算法，从一棵树的根节点到叶节点所产生的路径表示一条分类规则。通过遍历训练集数据自动生成分类模型，从而对未知类型的数据进行预测分类。在预测过程中根节点是每一条数据选择匹配路径的起点，如果一个节点的属性值符合决策规则的条件就进入相应的分支，直到整个数据集预测完毕。许多网络入侵检测系统都是以决策树算法为核心算法来对未知的数据进行预测分类。国内外网络入侵检测技术研究现状1980年。JamesP.Anderson在题为“控制对计算机安全的威胁”的技术报告中，第一次对网络侵略的威胁进行了分类，并提出了入侵检测的概念。这份报告被公认为入侵检测的开山之作。在JamesP.Anderson提出入侵检测的概念之后。1990年，L.T.Heberlein提议并建立了一个名为NSM（NetworkSecurityMonitor，网络系统监控器）的入侵检测系统[3]。该系统第一次直接监控互联网络上的数据流并将收集到的数据进行统计分析。自此，入侵检测系统的发展进入了新的阶段。经过了20多年的发展，入侵检测技术已经成为了解决网络安全问题的重要研究领域，尤其是伴随着如今信息技术的飞速发展，入侵检测技术也开始变得日新月异。但是，目前技术成熟的入侵检测系统（IDS，IntrusionDetectionSystems）所占的比例还是较少，更多的产品还处在实验室研究甚至理论研究阶段。这些产品普遍具有错误率高、漏报严重，缺少统一的规范标准，不能很好的与其他安全防御手段进行交互运行的缺点[4]。这是入侵检测系统发展至今一直存在的问题，也是科研人员一直以来的重点研究方向。论文主要研究途径（一）文献研究法：本文主要采用文献研究法进行撰写，通过查阅期刊、文书档案、书籍、报纸，互联网的收集和整理决策树算法的资料文献，确定自己的研究思路。（二）实证调查法：采用程序编程设计等形式进行算法的仿真性能测试，为此次论文提供理论依据，推进研究的进展。（三）统计分析法：使用统计分析法对实验产生的数据进行统计分析，以此作为衡量算法准确率的指标，并进行改进前后算法准确率的对比来得出实验结论。论文组织排版第一章：首先论述了大环境驱使下研究网络入侵检测技术的重要性与必要性，然后总结了前人对入侵检测的研究成果，最后列出了论文的主要研究途径和总体大纲。第二章：简单阐述了入侵检测技术和数据挖掘技术的概念。论述了入侵检测系统的通用模型并按照数据来源和采用技术为分类标准对入侵检测系统进行了分类，然后对入侵检测的四个工作流程进行了详细叙述。最后详细阐述了决策树构造的过程以及构造规则。第三章：研究了ID3、C4.5和CART三种经典的决策树算法，给出了他们的原理公式以及分类过程，最后总结了每种算法的优点和局限性。第四章：以C4.5算法为基础进行改进，并设计实验选取UNSW_NB15数据集来对改进前后的算法进行准确率对比，实验证明改进的算法具有更高的分类准确率。第五章：对全文进行总结展望，并提出工作不足之处，感谢导师以及同学在本文完成的过程中给予的宝贵指导意见与建议。入侵检测技术与数据挖掘技术简介入侵检测技术概要2.1.1入侵检测技术的定义所有的网络信息都有完整性、可获取性以及保密性的特点。如果某一种网络行为破坏了系统信息的这三种特性，那么这种行为就被定义为“入侵”[5]。例如篡改信息导致系统文件被破坏、用户的合法服务请求被拒绝等。入侵检测技术是一种积极动态的网络保护方法，通过分析网络行为信息的特点，总结出入侵行为与非入侵行为之间的区别。在入侵行为发生时能够将其识别出来、切断联系并采取措施警告用户，实现对网络入侵的预防。2.1.2入侵检测系统的通用模型进入21世纪，随着互联网的快速发展，越来越多的网络入侵检测系统浮出水面。然而，随之而来的是各种系统之间各自为阵，交互性很差。基于此，入侵检测架构组织CIDF（CommonIntrusionDetectionFramework）提出了一个入侵检测系统的通用模型[6]：响应单元响应单元事件数据库时间分析器事件数据库时间分析器事件产生器事件产生器图2-1入侵检测系统的通用模型该模型提出，入侵检测系统应划分为四个组件：事件产生器（EventGenerators）、事件分析器（EventAnalyzer）、响应单元（ResponseUnits）和事件数据库（EventDatabases）。其中，事件产生器是从整个网络环境中收集数据并传送给其他组件；事件分析器接收数据后进行分析并将结果再发送给其他组件；当分析结果传送到响应单元后，该组件会根据分析结果作出反应，如切断网络，对用户报警等；当响应完成后，由事件数据库对数据及结果进行存储，以备管理员和用户查询。入侵检测系统的分类根据数据来源的不同，入侵检测系统大致可以分为三类，分别是基于主机、基于网络、以及混合型的入侵检测系统[7]。（1）基于主机:系统分析的数据是计算机操作系统事件日志、应用程序事件日志、端口呼叫等。主机系统通常受到主机型入侵检测系统的保护。在目标主机上执行小型可执行程序代理(agent)并与控制台通信。（2）基于网络:系统分析的数据是在线数据包。网络入侵检测系统由传感器组成，通过网络检测数据包来保护整个网络。（3）混合型:由于基于网络和主机的入侵检测系统都有各自的缺陷，会导致所保护的系统出现故障。因此人们将两种系统相结合研究出了综合型入侵检测系统，该系统兼具了基于主机和基于网络两种系统的特点。以采用的不同技术作为分类依据，入侵检测系统可以划分为异常检测系统和误用检测系统两类[8]。（1）异常检测系统(AnomalyDetection):该类系统的原理是发现可接受行为之间的偏差。如果每一个可接受的行为都是可以确定的，那么每项不可接受的行为就一定是入侵。首先系统会总结正常操作的特点(用户轮廓)，当用户活动与正常行为之间相差巨大时即被认为是入侵。这种检测模型虽然漏报率低，但误报率高。因为没有必要确定每一种类型的入侵，所以异常检测系统可以有效识别未知的入侵。（2）误用检测系统(MisuseDetection):该类系统的原理是预先定义所有的入侵行为，当某些行为与已定义的行为相匹配，那么这些行为就很被认为是入侵行为并引起警告。误用检测要求预先收集入侵行为的行为特点，建立相关的入侵特征库。这种检测模型与异常检测相反，它的误报率低而漏报率高。能够检测出已知的入侵行为，但是对未知的入侵手段束手无策，需要不断的更新特征库。入侵检测系统的工作流程入侵检测的工作流程[9]主要有四个步骤，分别是：信息收集，信息分析，信息存储，攻击响应。入侵检测首先要进行信息收集，从网络、系统等不同的途径上收集数据信息，如用户的操作记录，用户的行为状态等。而且为了扩大收集范围要在不同的关键节点上进行信息的收集。同时，不同的数据来源还会更快速的辨别入侵行为是否存在。收集信息完毕后，系统开始分析所收集的信息，通常是基于统计分析，模式匹配和完整性分析三种方法。前两种方法用于实时探测入侵，而完整性分析则用于事后分析。统计分析方法简单来讲就是就是将系统正常运行时的测量属性进行一个全方位统计，例如用户访问时的IP地址，访问所在的时间段等等。统计归纳这些属性的特征值然后与收集到的网络行为和系统行为的特征值进行比较。如果采集到的值不在系统正常运行的特征库范围内，就认为这种行为是入侵行为。例如，一个通常登录时间在早八点至晚六点，登陆地点为济南的账户却在某一天凌晨两点，在河北试图登录。此时入侵检测系统运用统计分析方法就会将其表示为一个不正常行为，对用户进行警告并提醒管理员。运用这种方法可以检测到系统未知的、复杂多变的入侵行为，但是当用户的正常行为主动发生改变时，这种方法变得不再适用，具有误报、漏报率高的缺点。与统计分析不同，模式匹配的原理就是将收集到的信息特征与己知的网络入侵行为的特征进行比较,如果相符则认为是入侵行为。采用的方法有字符串匹配等。这种方法只要能够将收集到的信息与已知的入侵模式相比较就能判断其是否是入侵行为，对于系统的负担较小，且现在对这种方法的研究已非常成熟，检测准确率和效率都相当高。我们电脑上经常安装的杀毒软件，防火墙采用的就是这种原理，但是，该方法存在的弱点也很明显，就是需要不断的进行系统升级以对付那些新出现的入侵攻击手段，一旦有一个系统从未发现过的入侵行为出现就显得束手无策。如果某一种入侵行为越过了统计分析与模式匹配两种防御手段，但只要最终它造成了系统文件的变化，运用完整性分析手段就能够检测出来。这种方法的关注点在于系统文件内容、目录属性等非常微小的变化。但是由于是以批处理方式进行，无法用于实时响应。当入侵检测系统检测出存在入侵情况时，为方便用户和管理员进行事后分析，还需要将在数据收集阶段采集的数据保存在系统日志文件中。同时，存储的信息也包含了入侵行为的数字证据。最后，当对入侵的数据进行了分析并确定入侵的类型后，入侵检测系统会对入侵行为进行响应，例如对用户发出警报、给管理员发送邮件提示、自动断开网络连接、过滤入侵者的IP地址等，这些相应手段一般都是系统的开发者提前进行的设置，目的是能够让系统能够较早的阻断或避开攻击。数据挖掘技术的概念2.4.1产生背景随着计算机技术在企业生产运营中的广泛应用，企业存储和处理数据的能力大大提高，数据量与日俱增。数据的积累实质上是企业的经验和业务的沉淀，越来越多的企业引入“数据思维”，即不只是依赖于数据的统计分析，更强调对数据进行挖掘，期待从这一“未来世界的石油”中发现潜在的价值。这一迫切的“开采”需求在世界范围内酝酿了一次“大数据”变革。由于传统的数据分析方法已无法得到隐藏在数据海洋背后对决策至关重要的隐性知识，产生了数据的丰富性和知识的贫乏性之间的矛盾，进而引发了数据挖掘技术(KnowledgeDiscoveryingDatabases)的出现。2.4.2数据挖掘的内涵广义的数据挖掘(DataMining)是指针对收集的大规模数据，应用整套科学工具和挖据技术(如数据、计算、可视化、分析、统计、实验、问题定义、建模与验证等)，从数据之中发现隐含的、对决策有参考意义的信息、价值和趋势。[10]因此，数据挖掘是一个横跨多学科的计算机科学分支，是21世纪最具话题性的技术之一。这种技术包含数据预处理、算法应用、模型评价、结果检验等多个部分，并依靠其丰富的内涵向外延伸出数据分析、数据ETL、机器学习等多个领域。从商业应用的角度，数据挖掘是处理商业信息的新技术。通过提取、转换和分析业务数据库中的大量业务数据，来获取支持业务决策的关键信息。数据挖掘通常具有如下特点：（1）通常采集分析的数据量都很庞大，覆盖范围很广泛，以GB甚至TB计算。

（2）其目标是寻找决策者们可能感兴趣的规则或模式。

（3）挖掘出来的信息能够被决策者们理解和运用。

（4）在数据挖掘中，是基于统计规律来发现规则的。且只要有超过某一阈值的数据遵循这种规则就认为是有效的，不需要适用于整个数据库。（5）随着数据库的不断更新，更多不同种类的数据加入进来，数据挖掘所产生的规则也会随之变化。数据挖掘是一个在没有明确假设的情况下提取信息和发现知识的过程。通过数据提取获得的信息应具有三个特征：不确定性、有效性和实用性。[11]而传统的数据分析方法(如查询、报表、联机分析处理)一般都是先给出一个假设然后通过数据验证。虽然两种方法产生的结果都是通过大量的搜索工作从数据中自动提取出来的。但传统的数据分析方法在一定意义上是假设驱动的。而数据挖掘在一定意义上是发现驱动的。这是数据挖掘与传统的数据分析方法的本质区别。决策树算法概述在数据挖掘的众多实际应用方法中，决策树算法是处理分类问题的非常有效的方法，该算法通过训练集建立决策树模型，使模型具有识别能力，以便于对后面测试集进行分类归纳，是一种学习算法[12]。所谓的归纳就是从大量的具有不同特征属性的数据中，通过公式计算，总结概括等方式找到规律性并得出结论。归纳学习的过程就是从特殊性描述到一般性描述的过程，这种一般性描述能够解释给定的输入数据，并可以用来预测新的数据。以下图为例：年龄？年龄？≤30>40≤30>4030~4030~40学生？学生？信誉？信誉？买买坏好否是坏好否是买买不买不买买买不买不买

图2-2决策树示例图中这颗决策树由三类节点构成：根节点、内部节点（决策节点）和叶子节点，用来将给定的数据集中每一条数据进行分类（是否购买计算机）。由于数据集中有年龄、学生和信誉三列描述属性和一列类别属性（购买计算机与不购买计算机）。所以，根节点和内部节点（方框)都对应着数据集中的三个描述属性，而叶子节点（圆圈）则对应着类别属性集合。在建立决策树后，每一条从根节点到叶子节点的路径都可以创建一条IF-THEN分类规则[8]，上图转化为IF-THEN分类规则如下：IF年龄=≤30AND学生=否THEN是否购买=不买IF年龄=≤30AND学生=是THEN是否购买=买IF年龄=30~40THEN是否购买=买IF年龄=>40AND信誉=好THEN是否购买=买IF年龄=>40AND信誉=坏THEN是否购买=不买综上所述，决策树分类模型的运作流程就是将所有数据从根节点开始，为每一个描述属性值创建分支，直至所有描述属性被划分完毕。而网络入侵检测的过程概括起来就是对所收集到的数据进行分类(入侵与非入侵）的过程。基于此，决策树算法可以作为检测模型应用于网络入侵检测中，使得匹配次数降低，运算量减少，提高检测效率。由于不同的决策树算法公式原理不同，因此生成的决策树模型也不尽相同。下一章将对ID3、C4.5和CART三种经典决策树算法进行研究，给出算法的分类公式并分析其分类特点。三种经典决策树算法研究ID3算法在决策树的众多分类算法中，ID3算法在1979年被科学家J.R.Quinlan提出并成为了众多后继算法的思想基础，是数据挖掘中非常经典的决策树算法。ID3算法主要通过信息增益的方式来选择测试属性，这是因为从信息论角度来看，通过描述属性可以减少类别属性的不确定性，而不确定性可以用熵来描述。熵是信息论中非常一个非常重要的概念，表示信息源的总体信息测度。3.1.1信息熵、条件熵和信息增益假设数据集S中共有n个元组和m+1个属性，其中A1、A2、Am为描述属性，C为类别属性，其取值个数即类别数为u，其值域为（C1、C2、Cu），在S中类别属性C取值为Ci的元组个数为Si。对于描述属性Ak（1≤k≤m），它的不同取值个数为v，值域为（a1、a2、av）。在类别属性C取值为Ci（i≤1≤u）的子区域中，描述属性Ak取aj的（1≤j≤v）的元组个数为Sij。[13]则数据集S的信息熵E(S)定义为：公式(3-1)其中，表示每一种类别属性所占的比例。取所有类别的占比乘上它们的对数，并加到一起就是数据集A的信息熵。对于描述属性Ak（1≤k≤m），其条件熵E(Ak)定义为：公式（3-2）当信息熵与条件熵均计算完毕之后，该描述属性Ak的信息增益定义为：公式（3-3）信息增益的含义是在已知某一描述属性的情况下，类别属性对数据集分类能力的增加程度。数值越大，该描述属性对分类提供的信息越多，使用该属性划分数据集时所需要的信息量最小。ID3算法就是根据此原理，每次从描述属性集中都会选取信增益值最大的描述属性作为测试属性来划分数据集。ID3算法的优点是它的理论清晰简单易于理解，而且学习能力比较强。ID3算法的缺点：由于采用信息增益作为选择分类属性的标准，每次分类时都会偏向取值较多的属性。同时，ID3算法只能处理离散型属性，对连续型数据无能为力。C4.5算法1993年，Quinlan在分析总结ID3算法的基础上提出了C4.5算法。该算法采用信息增益率选择最佳划分属性[14]。对于训练数据集S（含n个元组），若描述属性Ak的v个取值将训练集划分为v个子集，子集的元组数目为nj(1≤j≤v),则C4.5算法定义的信息增益比率GRatio(S,Ak)为：公式（3-4）其中Gain(S,Ak)为公式（3-3）中的G(Ak)，而SplitE(S,Ak)=。与ID3算法相比，C4.5算法解决了用信息增益选择属性时偏向选择取值较多的不足。同时能够对连续型属性进行处理。C4.5算法的缺点是在构造决策树的过程中，需要多次扫描数据集，因而导致算法的低效。而且如果训练集大小超过了内存上限则程序无法运行，故C4.5算法只适合能够存储于内存中的数据集。CART算法1984年，Breiman等人提出了分类回归树(ClassificationAndRegressionTree)模型[15]。由于采用的是一种二分递归分割技术，简化了分区准则。CART算法构建的决策树生成的非叶子节点都只有两个分支，是一颗二叉树。CART算法采用GINI值作为分裂节点的依据，GINI指标用于在决策树的每个内部节点上选择属性。假设数据集为S,则其GINI值为公式（3-5）其中，K代表了样本中的类别个数，Pk代表了第k个类别占所有样本数的比例。如果是二分类问题，某一个样本输出概率为p，则公式变为：公式（3-5）当计算出所有属性的GINI值后，选取最小的作为划分节点。这与C4.5和ID3选取最大信息增益（比）的方法是相反的。因为基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。CART算法的主要优点是对异常点和干扰数据的抵抗性较强。而缺点是创建出来的决策树可能不稳定，对样本数据进行细微的修改都可能导致决策树的显著变化。C4.5算法研究经典C4.5算法对数据集的分类流程给定数据集S（分为若干列描述属性和一列类别属性）。对于离散属性，采用公式（3-4）计算每个属性的信息增益比率。而对于连续属性，先对连续属性的值从小到大进行排序，然后再按该顺序逐一的将两个相邻值的平均值（阈值）作为分割点，分割点将数据集划分为两个子集（大于该值和小于该值），假设该属性有m个取值，则共有m-1个分割点。最后分别计算每个分割点的信息增益比率。当离散属性和连续属性的信息增益比都计算出来之后，选取其中信息增益比最大的属性作为划分节点。不断的重复上述分类过程，直至所有属性划分完毕，当每个划分节点中的样本子集都属于同一类是结束，此时生成最终的叶子节点（类别属性）。仿真实验4.2.1数据集选择为了验证C4.5算法的效率，本文选取UNSW_NB15数据集进行测试，该数据集是网络入侵检测研究人员根据KDD-CUP99数据集归纳简化而来。KDD是数据挖掘与知识发现（Data

Mining

and

Knowledge

Discovery）的简称，是由ACM组织的年度竞赛。1998年该竞赛建立了模拟美国空军局域网的一个网络环境，收集了9周时间的网络数据，随后来自哥伦比亚大学的SalStolfo教授和来自北卡罗莱纳州立大学的WenkeLee教授对收集的数据进行数据分析和预处理，形成了著名的KDD-CUP99数据集。是国际上公认的进行网络入侵检测研究的经典数据集。4.2.2编程软件本文选取Pycharm软件、运用python语言进行算法的编写，python语言的创始人为荷兰人吉多·范罗苏姆(GuidovanRossum)，是一种面向对象的动态类型语言。最初被设计用于编写自动化脚本(shell)，随着版本的不断更新和语言新功能的添加，以其简洁性、易读性以及可扩展性，越来越多被用于独立的、大型项目的开发。4.2.3算法详解传统的C4.5算法相比于前身ID3算法有了不小的进步，比如能够对连续值进行处理。但该算法的缺点也很明显，当数据规模较大时，C4.5算法的效率将会降低。而本文选取的数据集复杂而且规模庞大。因此，为了提高C4.5算法的分类效率。本文对C4.5算法进行了一些改进。首先是对于数据集的处理，本文在UNSW_NB15数据集中随机抽取1000条数据作为训练集、300条数据作为测试集。这么做是为了避免偶然性，防止样本不均衡，实现代码如下图所示：图4-1随机选取训练集与测试集之后采用了continuous这个符号判断属性是离散属性和连续属性，实现代码如下图所示：图4-2判断属性为离散值还是连续值该条代码中set后面括号中的字段为数据集中的离散属性，当所要判断的属性不在这些字段之列时，程序判断其为连续值（continuous=True），否则为离散值（continuous=False）。采用这种方法能够减少对属性的扫描。如果划分后子集中所有的数据都属于同一个类别，则返回该类别，直接生成叶子节点。实现代码如下图所示：图4-3对属于同一类别数据的处理如果有某一条数据没有属性值，则返回该列属性中出现最多的取值，这种方法是一种对异常值处理的常用方法，实现代码如下图所示：图4-4对异常数据的处理当找到最佳划分属性后要将其从属性名列表中删除，减少不必要的遍历，实现代码如下图所示：图4-5删除已确定的最佳划分属性最后，改进前后的运行结果如下图所示（0表示非入侵数据，1表示入侵数据）：改进前：图4-6该进前的运行结果改进后：图4-7改进后的运行结果实验结果本文采用的准确率计算方法为：预测出的标签类型与实际类型相同的数量/测试集的总数量（300）。改进前后的准确率比较如下图所示：图4-8改进前后的准确率比较由上图可以得出实验结论，改进的算法比起改进前具有更高的检测准确率。全文总结本文从入侵检测技术的发展历程入手，介绍了选题的研究背景与意义，然后列出了全文的研究内容与组织结构。然后论述了入侵检测系统的通用模型和工作流程，并且引入了数据挖掘的概念。全文的重点在于对ID3、C4.5和CART三种经典的决策树算法的研究，阐述了每一种决策树构造的过程以及原理公式。第四章则以C4.5算法为基础进行改进，并设计实验进行改进前后的算法效率对比，实验证明改进的算法具有更准确的分类效率。最后第五章对全文进行总结展望，并提出工作不足之处。在文章末尾致谢导师以及同学在本文完成的过程中给予的宝贵指导意见与建议。对三种经典决策树算法原理公式进行了详细讲述。最后选取了C4.5算法应用于网络入侵检测中，通过实验证明了改进的算法具有更高的效率。受作者的知识水平和创新能力限制，本文没有以C4.5算法为基础设计出一套完善的IDS系统，只是通过程序编写来检测已有的数据集，这是本文的不足之处。真实的网络环境复杂多变，入侵的数据与手段几乎每天都在变化，并不是简单的编写一次代码就可以解决，还需要我们具有刻苦钻研的精神和创新能力，能够对网络入侵技术及时进行更新，这样才不会被时代所淘汰。希望本文提出的算法能够对入侵检测系统的研究提供帮助。参考文献[1]JinpingLiu,WuxiaZhang,ZhaohuiTang,YongfangXie,TianyuMa,JingjingZhang,GuoyongZhang,JeanPaulNiyoyita.AdaptiveintrusiondetectionviaGA-GOGMM-basedpatternlearningwithfuzzyroughset-basedattributeselection[J].ExpertSystemsWithApplications,2020,139.[2]QiGuanglei,ChenZhijiang,ZhaoHaiying,WuChensheng.ConstructionandApplicationofMachineLearningModelinNetworkIntrusionDetection[P].Proceedingsofthe2019InternationalConferenceonPrecisionMachining,Non-TraditionalMachiningandIntelligentManufacturing(PNTIM2019),2019.[3]YansongLiu,LiZhu.Anewintrusiondetectionandalarmcorrelationtechnologybasedonneuralnetwork[J].EURASIPJournalonWirelessCommunicationsandNetworking,2019,2019(1).[4]刘佳.基于决策树的自适性入侵检测系统设计与实现[D].山东大学,2017.[5]邹勉.基于数据挖掘的混合型入侵检测研究[D].南京信息工程大学,2015.[6]易倩.改进的聚类与决策树算法在入侵检测中的应用[D].广东工业大学,2012.[7]史珊姗.基于决策树C4.5算法的网络入侵检测研究[D].苏州大学,2012.[8]王超,辛阳.C5.0分类算法在网络入侵检测中的应用[C].中国科学技术协会、天津市人民政府.第十三届中国科协年会第11分会场-中国智慧城市论坛论文集.中国科学技术协会、天津市人民政府:中国科学技术协会学会学术部,2011:178-184.[9]向昕彦.决策树在入侵检测中的应用研究[D].哈尔滨理工大学,2009.[10]郑再.决策树分类算法在网络入侵检测中的应用研究[D].东北大学,2008.[11]彭国星.分布式关联规则算法和分布式决策树算法的对比研究[D].中南大学,2008.[12]刘玉.利用多决策树合并算法实现网络入侵检测[J].科技创新导报,2008(12):26+28.[13]凌昊.基于决策树分类算法的网络入侵检测系统的研究[D].湖南大学,2007.[14]段红勇.分布式关联规则算法和分布式决策树算法的对比研究[D].中南林学院,2005.[15]史长琼,易昂.基于多决策树算法的网络入侵检测[J].计算机工程与设计,2004(04):518-519+529.

附录：改进后的C4.5算法代码（部分）如下：defload_data():

train_data=pd.read_table('UNSW_NB15_training-set.csv',delim_whitespace=True).drop(['id','proto','service','state','attack_cat'],axis=1).dropna().sample(1000)

train_data.index=range(train_data.shape[0])

test_data=pd.read_table('UNSW_NB15_testing-set.csv',delim_whitespace=True).drop(['id','proto','service','state','attack_cat'],axis=1).dropna().sample(300)

test_data.index=range(test_data.shape[0])

returntrain_data,test_datadefgenerate_decision_tree(data_set,attribute_label):

label_list=[entry[-1]forentryindata_set]

iflabel_list.count(label_list[0])==len(label_list):

returnlabel_list[0]

iflen(data_set[0])==1:

returnmost_voted_attribute(label_list)

best_attribute_index,best_split_point=attribute_selection_method(data_set)

best_attribute=attribute_label[best_attribute_index]

decision_tree={best_attribute:{}}

del(attribute_label[best_attribute_index])

ifbest_split_point==None:

attribute_list=[entry[best_attribute_index]forentryindata_set]

attribute_set=set(attribute_list)

forattributeinattribute_set:

sub_labels=attribute_label[:]

decision_tree[best_attribute][attribute]=generate_decision_tree(

split_data_set(data_set,best_attribute_index,attribute,continuous=False),sub_labels)

else:

sub_labels=attribute_label[:]

decision_tree[best_attribute]["<="+str(best_split_point)]=generate_decision_tree(

split_data_set(data_set,best_attribute_index,best_split_point,True,0),sub_labels)

sub_labels=attribute_label[:]

decision_tree[best_attribute][">"+str(best_split_point)]=generate_decision_tree(

split_data_set(data_set,best_attribute_index,best_split_point,True,1),sub_labels)

returndecision_treedefattribute_selection_method(data_set):

num_attributes=len(data_set[0])-1

info_D=calc_info_D(data_set)

max_grian_rate=0.0

best_attribute_index=-1

best_split_point=None

continuous=False

foriinrange(num_attributes):

attribute_list=[entry[i]forentryindata_set]

info_A_D=0.0

split_info_D=0.0

ifattribute_list[0]notinset(['sloss','dloss','trans_depth','response_body_len','ct_state_ttl','is_ftp_login','ct_ftp_cmd','ct_flw_http_mthd','is_sm_ips_ports']):

continuous=True

ifcontinuous==True:

attribute_list=sort(attribute_list)

temp_set=set(attribute_list)attribute_list=[attrforattrintemp_set]

split_points=[]

forindexinrange(len(attribute_list)-1):

split_points.append((float(attribute_list[index])+float(attribute_list[index+1]))/2)

forsplit_pointinsplit_points:info_A_D=0.0

split_info_D=0.0

forpartinrange(2):sub_data_set=split_data_set(data_set,i,split_point,True,part)

prob=len(sub_data_set)/float(len(da