决策算法（精选9篇）
决策算法 篇1
一、引言
入侵响应系统(Intrusion Response System,IRS)是对入侵检测系统检测出的安全事件进行响应,阻止攻击行为和降低损失的系统。入侵响应决策是指对攻击选择适当的响应方式的过程,是自动入侵响应系统的核心技术,是网络安全研究的热点问题。目前对于自动入侵响应决策模型的研究,大部分采用的是基于分类的入侵响应决策模型[1],2002年Wenke Lee[2]提出了成本敏感模型,以代价作为入侵响应策略的依据,Balepin等人在其研发的自动入侵响应原型系统ARB中提出了类似的思想方法[3],但是该模型没有考虑入侵检测系统所产生的误报和漏报等因素,且仅用于决策是否要进行响应,没有将代价应用到响应方式的决策中,过于简单实际应用效果并不理想。基于成本敏感模型,提出一种最小代价的入侵响应决策算法,并对攻击和响应相关的因素的代价进行了量化,测试结果表明,取得良好的效果。
二、成本敏感模型
成本敏感模型以代价作为入侵响应决策的基础,将入侵检测与入侵响应所涉及的代价分为检测代价(Operational Cost,Op Cost)、损失代价(Damage Cost,DCost)和响应代价(Response Cost,RCost)等三种。对于入侵检测系统检测到的攻击行为,计算其损失代价和响应代价,如果其损失代价大于响应代价,即DCost>RCost,则采取响应措施;反之,如果DCost
三、基于最小代价的响应决策算法[4]
入侵检测系统不能消除误报和漏报,建立在误报基础上的入侵响应就会导致系统的损失和资源的浪费。对于IRS如果响应代价大于损失代价,就没有必要响应,同时当响应措施实施后,如果还不能有效地阻止攻击进行,就要采取更加严厉的响应措施。
对于n种攻击类型,对应n种响应方式,假设用i表示攻击类型;j表示IDS的报警类型,αij表示第i种的攻击触发j类报警的次数。IDS报警可分为成功检测区、错报区、漏报区和误报区等四个区域,入侵检测相关的属性定义如下:
为了解决入侵检测系统报警的不确定性,IRS应根据入侵检测系统的报警可信度采取不同的响应措施。设IRS共支持n种响应方式,定义一个集合R=(r0,r1……,rn)表示系统支持的响应方式,其中r0表示空响应。对IDS的任意安全事件报告aj,响应决策模型要从R中挑选出有效且代价最小的响应方式。
用e=(a,r)表示实际发生的攻击类型为a,IDS检测出的类型为e,采取的响应方式为r。则IRS的总损失代价(Consequential Cost,记为CC)是响应操作代价(Response Cost,记为RC)与残留损失代价(Reside Damage Cost,记为RDC)之和。
(1)响应操作代价表示执行入侵响应方式所耗费的代价,如执行主动报文所耗费的计算资源等。
(2)残留损失代价是响应执行前系统已经造成的损失和响应方式不当给系统造成的损失。残留损失代价计算与四个因素有关:攻击损失代价(DCost)、攻击目标的重要性(criticality)、攻击目标对特定攻击的免疫力(immunity)、响应方式的负面效应(side Cost)。
基于代价响应决策模型对各种代价的量化,因为不是所有代价都能以特定量化形式表示,因此采用定性分析以测量其相对大小。根据攻击的分类定义攻击损失代价的量化如下表1所示。
攻击目标的重要性指受攻击目标在网络中的重要程度,依据重要程度讲攻击目标分为四类:防火墙和路由器、DNS服务器、Web服务器和Mail服务器、Unix和Windows工作站,各类攻击目标的重要程度量化值如表2所示:
响应目标的免疫力指目标系统对某些攻击的免疫能力,如Sadmind Ping攻击和Sadmind BOF攻击仅针对Solaris系统,对Unix和Windows工作站无效。免疫力用数值0和1表示,0表示系统对该攻击无免疫力,1表示对该攻击具有免疫力。
响应方式的负面效应表示响应执行后给合法用户带来的影响和损失,负面代价用DOS攻击代价进行量化,如关闭主机响应方式对合法用户相当于遭受DOS攻击,其负面代价等于DOS攻击损失代价。
根据IDS检测结果CC的计算分为四类,如下表3所示。
对于i类型攻击,IDS报告的攻击类型为j,定义响应系统的期望累积代价为ECC。ECC计算方式如下:
为支持自适应性,为每种攻击类型对应的响应方式定义一个成功率suc(a,r),表示对攻击类型a执行响应方式r的成功率,suc(a,r)计算公式如下:
响应决策的目标是为攻击a从响应方式集合R中找出最有效的响应方式r*,且使得系统的期望总代价最小。即:
ECC+=(公式3)
响应决策算法流程如下:
(1)通过机器学习的方式对IDS进行训练,为A,Q,mi,sj,pii,qj(1<=i,j<=n)置初值;
(2)设当前收到的报警为ha*,对响应方式集合R=(r0,r1……,rn)中每个响应方式ri利用公式1分别计算其期望累计代价ECC(ha*,ri);
(3)根据公式3计算最优响应方式r*,发送命令至响应执行模块以发起响应;
(4)更新A,Q,以及相应mi,sj,pii,qj的值,在响应执行后根据公式2更新suc(ha*,r*)的值。
四、入侵响应决策算法测试
以DDOS攻击和Port Scan端口扫描攻击为例,测试最小代价入侵响应决策算法的合理性和有效性。典型入侵响应及其响应操作代价、残留损失因子以及负面代价如下表4所示。
假设有两个攻击目标h1(131.83.1.31,遭受DDOS攻击)和h2(172.16.112.50,遭受Port Scan攻击),它们的属性如下:
由表1可知,DCost(DDOS)=30,DCost(Port Scan)=2。
对于正确报警,ECC的计算简化为ECC(a,r)=RC(a,r)+RDC(a,r)。各种代价以及总代价计算如表5和表6所示,其中表5对应h1遭受DDOS攻击,表6对应h2遭受Port Scan攻击。
可见对于DDOS攻击,最有效的响应方式为隔离服务,隔离受害主机的相关服务;对于Port Scan攻击,最有效的响应方式为阻止入侵者IP,对于一对一或一对多的Port Scan攻击,隔离攻击源是最为合理的响应方式。
五、结束语
针对成本敏感模型入侵响应决策存在的问题,综合考虑攻击和响应以及攻击目标等各方面的因素,以系统期望代价最低为目标,重新构建入侵响应总体损失代价算法,并对攻击和响应相关的因素进行了量化,系统对DDOS攻击和Port Scan端口扫描攻击的测试结果表明达到良好响应效果。如果需要增加新的响应方式,只需要提供关于该响应方式的几个参数,比如响应操作代价等,与基于分类的响应决策算法相比,该算法具有更高的有效性和扩展性。
摘要：借鉴成本敏感模型,综合考虑攻击和响应以及攻击目标等各方面的因素,提出基于最小代价响应决策算法,并对攻击和响应相关的因素进行了量化,与基于分类的响应决策算法相比,该算法具有更高的有效性、成功率和扩展性。
关键词：入侵响应决策,入侵检测,成本敏感,最小代价
参考文献
[1]Curtis A Carver.Adaptive-based intrusion response[D].College Station:Texas A&M University,2001.
[2]Wenke Lee,Wei Fan,Matthew Miller,et al.“TowardCost-Sensitive Modeling for Intrusion Detection and Response”[J].Journal of Computer Security,2002,10(1):318-336.
[3]Balepin I,Maltsev S,Rowe J,et al.Using specificationbased intrusion detection for automated response[C]//Proc of the 6thInt’l Symp on R ecent Advances in Intrusion Detection.Berlin:Springer,2003.
[4]游凤芹.基于主动网的自适应入侵响应系统的研究和实现[D].东南大学,2006.
决策算法 篇2
关键词：车辆路径问题；不确定决策；禁忌搜索算法
中图分类号：F224文献标识码：A
文章编号：1002-3100(2007)12-0026-04
Abstract: A vehicle routing problem in war is discussed, in which some routes may be destroyed uncertainly by competitor. A two-stage integer program model is constructed. The value of a route in a uncertain situation is analyzed. In the method, only the maximum value and the minimum value are countered into the object value, simpling the computation of the object value of the model. A two-stage tabu search algorithm is designed. In the end, an example is given.
Key words: vehicle routing problem; uncertain decision; tabu search algorithm
0引言
战争环境下，交通线路中的一些关键性的桥梁、隧道和线路枢纽随时可能被敌方破坏。利用这些关键性的桥梁（隧道）运输时间将会缩短，但如果这些桥梁被毁坏，运输车可能要绕道运输甚至原路返回，反而延误了运输时间。这一类问题同样也存在于自然灾害的救援活动中。在人类的发展历史上，地震、洪水、台风和雪崩等自然灾害也是破坏交通线的重要因素。1995年日本的神户地震、美国近期的飓风“丽塔”、我国1998年的特大洪水等都破坏了许多交通设施，同时这些自然灾害还随时威胁物资救援的运输线路。由于这类运输直接关系到整个军事（救援）活动的成功与否和人员的生命安全，因此研究这一类不确定的运输决策问题无论对于战争还是人类战胜自然灾害都具有重要的意义。目前关于车辆线路优化的研究很多，但涉及战争环境下（或自然灾害环境）的研究很少，正式的研究文献几乎没有看到。本文探讨了一个个别关键路段（桥梁、隧道等）可能被毁坏情况下的多车辆路径决策问题，提出了相应的数学模型并给出了求解模型的禁忌启发式算法。
1问题描述及复杂性分析
1.1问题的提出
2数学模型
调整上述模型的一些参数，即可建立不协作的两阶段规划模型，这里不再详述。
3线路方案的评价值
4禁忌搜索算法
禁忌搜索算法主要内容如下：
（1）随机产生一个路径序列为初始解。为n个需求点编序列号，仓库为0。路径解的首尾各为0，中间是n个需求点加上M-1个0的随机排列。相邻两个0之间为一个车辆的服务路径。以6个需求点，两辆车为例，一个路径解为0-1-2-3-0-4-5-6-0。
（2）邻域的产生。分别采用任意两个需求点交换位置、任意一个需求点插入到线路任意位置的方法产生新的解。
（3）车辆容量限制的处理。当一个车辆线路中的需求点的总需求量超过车辆最大载货量时，该线路方案被淘汰。
（4）禁忌对象为两个相邻的需求点。禁忌表的长度随进化代数的增加而加长。当前值优于历史最优值时，禁忌解除。
（6）线路的方向。在乐观准则下，毁坏后线路的调整变化没有被计算到评价值中，为了弥补这一缺陷，可选出乐观准则下的最优方案和多个次优方案，并计算出最坏情况下的结果，以供决策参考。即使是最优化方案，相同的线路次序但不同的线路方向也被认为是不同的方案。如线路0-1-2-3-4-0和0-4-3-2-1-0是不同的方案。
5示例
表1是一个路网的距离数据。其中路段2-4经过一个难以修复的桥梁，被敌方破坏的可能性非常大。0表示仓库，其它10个序号表示需求点，每个需求点需求为5，每辆车的最大载货量为35，用两辆车送货，要求规划不同期望值准则下的里程最短的线路。
由于车辆载货量的限制，完成任务必须两辆车。采用文中的禁忌搜索算法得到不同准则下的最优方案。
6结束语
战时或各种抢险救灾时的物流运输保障具有重大意义。但这类运输线路优化问题至今研究很少。本文把不确定决策技术和车辆路径优化技术结合起来，建立了不确定环境下的运输线路优化模型，研究结果可以为不确定环境下的物流配送决策提供参考。
参考文献：
[1] 李军，郭耀煌. 车辆优化调度理论与方法[M]. 北京：中国物资出版社，2001:7-10.
[2] 甘应爱，田丰,等. 运筹学[M]. 北京：清华大学出版社，1990.
[3] 柳春光，焦双健. 城市震后救灾系统救灾决策研究[J]. 自然灾害学报，2000,9(3):21-24.
[4] 吴育华，杜纲. 管理科学基础[M]. 天津：天津大学出版社，2001.
[5] 张凤林，武小悦，郭波,等. 物流网络可用性研究[J]. 系统工程理论方法应用，2002,12(1):16-19.
多目标模糊决策算法与应用 篇3
随着科技的发展,模糊理论己经渗入到了生产、工程和军事等各个领域中。如在军事研究中,由于作战具有多目标、多批次、多方向、空海潜立体战等攻击形式的特点,这就要求决策系统发挥更加重要的作用:参战舰艇能尽早发现敌方目标;对来自各传感器的目标信息,能快速进行识别、分类和决策,并迅速、准确地确定作战决策方案,以控制各种武器打击目标。而在实际应用中很难将多个决策者之间的偏好结构反映到多目标决策模型中,这就需要找到一种多目标模糊决策支持算法,以处理多种信息的决策情况。
2 最小(大)隶属度偏差法
最小(大)隶属度偏差法是基于正(负)理想解的方法来求解,这里考虑的是,越接近(远离)正(负)理想解越好。记正理想解为x+,负理想解为x-。下面讨论正理想解情况,负理想解类似分析。
正理想解x+就是使所有输入分量fi(x)的模糊最优点集fi的优属度μi(x)都取得最大值时的解。记正理想解x+处的优属度向量为
给出点x∈X与正理想解x+的Minkowski距离,即使得:
达到最小值。
3 多目标模糊决策
若输入空间X由无限个输入变量组成时,可利用模糊多目标决策的模糊最优解方法与最优化算法结合起来进行求解,可以有效地解决优化设计等问题。
输入类型一般有效益型和成本型两种,其中,效益型输入是指优属度越大越好,而成本型输入是指优属度越小越好。Zadeh教授给出了两种输入的优属度计算方法。对效益型输入fi(x)选取其优属度为
而成本型输入fi(x)选取其优属度为
其中,Pi是事先指定的参数。
在确定方案xi(i=1,2,…,n)关于目标fi(x)的优属度时,可用目标fi(x)在X上的相对最大值与相对最小值分别代替其上确界与下确界,从而确定xi关于fi(x)的相对优属度。因此,可以将式(3)和式(4)转换为
4 应用实例
假设在陆战中,我方部队发现了3个敌人目标(目标1、目标2和目标3)并获得敌人目标一些数据,现需要根据所获取的情报信息做出选择,以确定打击敌人目标的先后顺序。
得到目标的数据有:f1—目标距离、f2—目标速度、f3—目标类型威胁度和f4—兵力战场生存能力。各个目标的目标值由F给定,如表1所示。
为了求解出打击目标的数据,先将目标值F转化为相对优属度矩阵。对于f1,属于成本型目标,用式(6)求解;对于f3,属于效益型目标,用式(5)求解;对于f2是固定型目标,当达到f2=1.3时最佳,可采用
来求解;对于f4是模糊语言,这里取模糊判断“好”、“中等”与“差”分别为1.0、0.75和0.5。令Pi=1于是,可计算出目标相对优属度矩阵为
由式(1)可得正理想方案x+的相对优属度向量为
假设经过军事专家与指挥员的评判确定,目标fi(i=1,2,…,4)的权重向量为
利用式(2)与式(7)可计算出目标1、目标2和目标3的距离分别为0.086、0.368和0.4536。
因而,决策中最需要打击的目标是x3,即3号目标,其打击顺序为x3、x2、x1。
5 结束语
本文将最小(大)隶属度偏差法和多目标模糊决策算法相结合,对于多目标模糊问题,转换为数学规划优化问题(在一定条件下),将具体目标具体分析,使模糊问题具体化,进而多目标模糊模型的求解得到了比较彻底地解决,使选择结果更加科学合理。
参考文献
[1]徐泽水.基于期望值的模糊多属性决策法及其应用[J].系统工程理论与实践,2004(1):109-114.
[2]王坚强.多目标组合决策方法研究[J].系统工程与电子技术,2002(10):70-72.
决策算法 篇4
关键词：关联规则算法；新疆高职院校；录取决策
中图分类号：TP311.12 文献标识码：A文章编号：1007-9599 (2011) 15-0000-02
The Research Application of Association Rules Algorithm in XinJiang College Admit Decision
Lu Haiyan,Sha Hongmei
(Yili Vocational Technical College,Yining835000,China)
Abstract:The purpose of this paper is to research the report rate of collage students in XinJiang.The algorithm of association rules was used to mine knowledge in student information databases,with that obtain the rules about factors which influence student’s report rate,and predicted the new classification of the new case report.It has important realistic significance to improve the report rate.
Keywords:Association Rules algorithm;XinJiang college;Admit Decision
每年9月，各新疆高职院校都对新生报到率关心备至，因为新生报到率偏低会影响学院招生计划的完成，造成教学资源的极大浪费。将数据挖掘技术中的关联规则算法应用于录取决策中，挖掘影响学生报到率的规则，预测考生报到可能性，可以为高院院校录取决策提供有效帮助。
一、关联规则的定义
关联规则挖掘算法是一种在许多数据中找出隐藏的关联规则的方法。关联规则常常用一个蕴涵式来表示，如“啤酒=>尿布”。
一个事务数据库中的关联规则挖掘可以描述如下[1]：
设I＝{i1，i2，…，im}是一个项目集合，事务数据库D＝{t1，t2，…，tm}是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，…，n）都对应I上的一个子集。
定义1-1设I1 I，项目集（Itemset）I1在数据集D上的支持度（Support）是包含I1的事务在D中所占的百分比。
定义1-2一个定义在I和D上的形如I1=>I的关联规则的置信度（Confidence）是指包含I1和I2的事务数与包含I的事务数之比。其中I1，I2 I，I1∩I2= 。
关联规则就是支持度和置信度分别满足用户给定阈值的规则。
二、关联规则挖掘的一般过程
关联规则挖掘就是通过用户指定的最小支持度，在全部事务数据库中挖掘出满足支持度不小于最小支持度的频繁项目集，再通过用户指定的最小置信度，在全部频繁项目集中挖掘出置信度不小于最小置信度的强关联规则。关联规则挖掘过程由这两部分共同组成。在这两部分中，关联规则挖掘是否成功主要取决于第一部分，即挖掘频繁项目集。
三、挖掘影响新生报到率的规则
以新疆某高职学院新生注册信息库中的样本数据为例，挖掘新生基本属性（性别、考试语种、考生类别、毕业类别、科类、考生生源、高考成绩）与学生报到之间的规则。并根据此规则制定出有效的录取决策，指导录取人员进行录取。经过数据清洗，得到有效数据2989条。
根据近几年该学院的新生报到率，将最小支持度设为0.01，最小置信度设为54%。
表1.各属性人数
属性
录取人数报到人数
男性1288774
女性1701929
汉语言1454737
民语言1535966
城镇应届893458
城镇历届296219
农村应届1268642
农村历届532384
普通高考26311412
“三校生”高考358291
理科20151105
文科974598
生源：疆内外地21231193
生源：疆内本地605404
生源：疆外261106
考分：100-199204156
考分：200-299685401
考分：300-39919731081
考分：400-49912664
考分：500-59911
（一）找出所有频繁项目集
（1）根据Apriori算法，在所有报到学生信息中挑选支持度不小于最小支持度的项目集组成1－频繁项目集L1。L1＝｛性别∈｛男，女｝，考试语种∈｛汉语言，民语言｝，考生类别∈｛城镇应届，城镇历届，农村应届，农村历届｝，毕业类别∈｛高中，三校｝，科类∈｛文，理｝、考生生源∈｛疆内外地，本地，疆外｝，高考成绩∈｛［100-199］，［200，299］，［300，399］，［400-499］｝。为了理解方便，将以上集合简写为｛男，报到｝、｛女，报到｝、｛汉语言，报到｝、｛民语言，报到｝、｛城镇应届，报到｝、｛城镇历届，报到｝、｛农村应届，报到｝、｛农村历届，报到｝、｛高中，报到｝、｛三校，报到｝、｛理，报到｝、｛文，报到｝、｛疆内外地，报到｝、｛本地，报到｝、｛疆外，报到｝、｛100≦高考成绩<200，报到｝、｛200≦高考成绩<300，报到｝、｛300≦高考成绩<400，报到｝、｛400≦高考成绩<500，报到｝。（2）根据Apriori的改进算法－Partition算法，将学生数据库进行划分，每块包含两个属性或一个属性。据此，将学生数据库划分为含有项目｛性别，授课语言｝、｛考生类别，毕业类别｝、｛科类，考生生源｝和｛高考成绩｝的四个块。根据块中包含的属性，将上一步计算出的项集依照块的属性进行合并，组合成每块的频繁项集。计算合并后的项集的支持度，将支持度不小于0.01的项集挖掘出来。（3）重复（2），两两进行分块。此时学生数据库被分为含有｛性别，授课语言，考生类别，毕业类别｝和含有｛科类，考生生源，高考成绩｝的两块。同样的，将上一步中计算出的项集依据分块内容再进行组合，计算它们的支持度。将支持度不小于0.01的项集挖掘出来。（4）重复（3），此时，只剩下一个块，包含了所有的属性值。此时，这个块的频繁项目集就是最终的频繁项目集。
（二）计算频繁项目集对应的规则的置信度
（1）confidence｛男，民语言，农村历届，三校，理，本地，200≦高考成绩<299｝=>报到＝91%；（2）confidence｛男，汉语言，城镇应届，高中，理，疆内外地，300≦高考成绩<400｝=>报到＝45%；（3）confidence｛女，汉语言，城镇应届，高中，理，疆内外地，300≦高考成绩<400｝=>报到＝44%；（4）confidence｛男，汉语言，农村应届，高中，理，疆内外地，300≦高考成绩<400｝=>报到＝48%；（5）confidence｛男，民语言，农村应届，高中，理，疆内外地，300≦高考成绩<400｝=>报到＝65%；（6）confidence｛女，汉语言，農村应届，高中，理，疆内外地，300≦高考成绩<400｝=>报到＝46%；（7）confidence｛女，民语言，农村应届，高中，理，疆内外地，300≦高考成绩<400｝=>报到＝46%；（8）confidence｛女，民语言，农村历届，高中，理，疆内外地，300≦高考成绩<400｝=>报到＝58%；（9）confidence｛女，汉语言，城镇应届，高中，文，疆内外地，300≦高考成绩<400｝=>报到＝58%；（10）confidence｛男，民语言，农村应届，高中，文，疆内外地，300≦高考成绩<400｝=>报到＝54%；（11）confidence｛女，汉语言，农村应届，高中，文，疆内外地，300≦高考成绩<400｝=>报到＝69%；（12）confidence｛女，民语言，农村应届，高中，文，疆内外地，300≦高考成绩<400｝=>报到＝63%；（13）confidence｛女，民语言，农村历届，高中，文，疆内外地，300≦高考成绩<400｝=>报到＝77%。
（三）生成强关联规则
根据事先确定的最小置信度50%，得到8个强关联规则。分别为：（1）｛男，民语言，农村历届，三校，理，本地，200≦高考成绩<300｝=>報到；（2）｛男，民语言，农村应届，高中，理，疆内外地，300≦高考成绩<400｝=>报到；（3）｛女，民语言，农村历届，高中，理，疆内外地，300≦高考成绩<400｝=>报到：（4）｛女，汉语言，城镇应届，高中，文，疆内外地，300≦高考成绩<400｝=>报到；（5）｛男，民语言，农村应届，高中，文，疆内外地，300≦高考成绩<400｝=>报到：（6）｛女，汉语言，农村应届，高中，文，疆内外地，300≦高考成绩<400｝=>报到；（7）｛女，民语言，农村应届，高中，文，疆内外地，300≦高考成绩<400｝=>报到；（8）｛女，民语言，农村历届，高中，文，疆内外地，300≦高考成绩<400｝=>报到。
（四）结果说明及验证
根据以上8个强关联规则，可知基本信息与规则左边属性值相同的学生，报到可能性大。将此规则应用于今后的录取现场时，录取人员可在同等条件下可优先录取具有以上属性值的学生，以提高新生率。
四、关联规则挖掘的分类预测
在关联模型中，如果列用于输入，那么该列的值只能在频繁项集中和关联规则的左边使用。如果列用于预测，则可以在频繁项集中以及关联规则的左边和右边使用该列的状态。如果列是逻辑型的，则它的状态可以出现在频繁项集中及规则的右边。
在新生报到表中，“是否报到”列的值是逻辑型，可以出现在频繁项集中及规则的右边，因此，“是否报到”列的状态就可以用于预测。例如，有一个频繁项目集｛性别＝‘男’，考试语种＝‘民’，毕业类别＝‘三校’，是否报到＝‘是’｝，和由此产生的一个强关联规则｛性别＝‘男’，考试语种＝‘民’，毕业类别＝‘三校’｝=>报到，那么，可以预测出，性别为男性，考试语种为民语言，毕业类别为三校的新生将会来报到，或者说，他前来报到的可能性非常大。
利用关联规则算法进行关联推测的方法：（1）给定一系列项，找出左边匹配给定项集或者任何给定项集的子集的所有规则。应用这些规则来获取推荐列表。（2）如果没有合适的规则，或者可推荐的项太小，则应用边缘统计学来预测和返回出现最频繁的N个项。（3）基于概率对来自步骤1和步骤2的项进行排序。
根据以上方法，本文对该院2011级录取的新生数据进行了深入分析。将出现频率较高的项集预测为“会报到”，其它项集预测为“不会报到”，将所有频繁项集按概率大小顺序挖掘出来。将此挖掘结果应用于录取现场，可以指导录取人员按此顺序录取考生，提高考生的报到率。
五、结论
通过关联规则算法，在已有学生数据库中挖掘出学生信息与报到之间的规则，再将此规则应用于报考考生数据库，预测哪类考生报到可能性高，可以为高职院校录取人员提供有用信息，有效提高新生报到率。
参考文献：
[1]毛国君,段立娟,王实,石云.数据挖掘原理与算法[M].北京:清华大学出版社,2005,11-65
[2]于莉.基于高校学生信息库的数据挖掘[D].内蒙古:内蒙古大学,2004
[3]安淑芝等.数据仓库与数据挖掘[M].北京:清华大学出版社,2005,2-16
[4]彭松涛.数据挖掘技术在高校就业管理系统中的应用研究[D].浙江:浙江工业大学,2005
[5]刘玉文.数据挖掘在高校招生中的研究与应用[D].上海:上海师范大学,2008
[6]谢长卫.高校学生信息的数据挖掘研究[D].安徽:安徽理工大学,2008
[7]李万武.基于贝叶斯理论的数据挖掘在高校信息管理的应用研究[D].黑龙江:哈尔滨工程大学,2005
[作者简介]芦海燕（1974-），女，新疆伊宁市人，讲师，工程硕士，主要研究方向：数据挖掘、计算机辅助设计；沙红梅（1972-），女，新疆伊宁市人，助理讲师，本科，主要研究方向：计算机应用。
遥感监督分类的决策树算法研究 篇5
一、决策树算法的图像分类研究
1. 常用的决策树算法简介
决策树是一个类似流程图的树型结构, 其中树的每个内部节点代表对一个属性的测试, 其分支代表测试的每个结果, 而树的每个叶子节点代表一个类别, 树的最高层节点就是根节点, 是整个决策树的开始。这类算法无须相关领域知识, 且相对于基于模糊理论的分类方法, 具有更高的分类准确率和更快的处理速度。在很多领域特别是数据挖掘中, 决策树是一种经常要用到的技术, 它可以用于分析数据, 也可以用来作预测, 常用的算法有ID3, CART, C4.5等。
(1) ID3算法是最有影响和最早的决策树算法之一, 其建立在推理系统和概念学习系统的基础上, 但它是非递增学习算法。每当一个或数个新例子进来, 就必须重新执行一次该算法, 把新来的例子和以前旧的全部例子集合变成决策树, 因此效率非常低。而且它是基于单变量的, 难以表达复杂概念, 抗噪性差。
(2) C4.5是ID3的改进版本。它主要在以下几个方面对ID3作了改进:缺省值的预测属性仍可用, 提出了修剪思想, 可以进行规则推导。
(3) CART (ClassificationandRegressio nTree, 分类回归树) 是一种数据勘测和预测算法。它用一种非常简单的方法来选择问题, 即将每个问题均试一次, 然后挑出最好的一个, 用它把数据分成更有序的两个分割, 再对新的分割分别提出所有可能的问题。因此该算法得到的决策树每个节点有两个分支, 即二叉树。
2. 改进决策树生成算法
为了更好地将决策树算法应用于遥感图像分类中, 本文在CART算法的基础上作了以下改进。
(1) 常用的决策树算法均由用户提供训练样本集, 计算机执行算法生成决策树, 整个过程由计算机自动完成, 不需要任何人工干预。由于遥感图像训练集的属性取值太多, 而有些取值是用不到的, 需要把这些用不到的取值过滤掉, 否则会影响整颗树的质量。因此本文在决策树的生成过程中引入人机交互技术, 将用户的先验知识用于决策树的生成过程中, 使得生成的决策树更加合理可信。基于人机交互的决策树方法由用户与计算机相互交互, 共同完成, 故要求计算机提供可视化环境和工具, 友好的界面方便用户输入先验知识。
(2) 建立一棵树首先需要选择一个属性作为根节点, 然后将该属性的每一个可能值作为一个分支;再在每个分支所剩余的属性中找出一个属性作为该分支的下一个节点, 如此循环到所有属性均被选用为止。常用的决策树算法均采用信息熵作为选择标准。由于遥感图像中的噪音比较多, 而基于信息熵属性选择标准往往抗干扰能力不强且以对数计算为累加计算的计算量较大, 故本文采用了一种新型的属性选择标准:属性重要性来提高属性选择的效率。该方法是用训练值的变化而引起输出变化的累加值作为衡量属性重要性的标准, 即对于某个属性, 如果训练值的变化而引起的输出变化越大, 说明该属性就越重要。可用式 (1) 表示为C (K) =∑x (i, k) -x (j, k) ×signy (i) -y (j) (i≠j) (1) 式中:C (K) 表示第k个属性的输入/输出关联值;x (i, k) , x (j, k) 表示第i, j个样本的第k个条件属性值;y (i) , y (j) 表示第i, j个样本的决策属性值;sign (x) 表示符号函数。
3. 一种自定义的数据结构
数据结构的设计在程序设计中很关键, 一个好的数据结构可以让算法更加精练, 大大提高开发效率。本文采用的算法是在CART算法的基础上改进过来的, 因此生成的也是一棵二叉树。但由于在生成算法中要频繁地查找和调整决策树 (添加或者删除子树) , 传统的二叉树结构在速度上不能满足算法的需求, 故笔者在设计系统时创新了一种类二叉树的结构。在树的每一层都设置了一个头节点, 且树的每个节点只有指向父节点和左右兄弟节点的指针。
4. 系统实现
图3为系统架构图。其中D是训练集合, A为分类属性集合。另有测试数据集合T用来评估生成决策树的误差ε。整个过程分为两个部分进行: (1) 决策树构造, 也称学习过程, 主要工作是输入训练集, 采用改进的决策树生成算法生成决策树, 并作好分类前的预备工作, 即提取分类规则; (2) 决策树预测, 也称分类过程, 主要工作是应用分类规则进行分类, 并根据测试集, 计算出分类误差, 误差较大的对决策树作裁剪算法。误差较小的就输出其分类结果, 分类结果有两种: (1) 将分类结果写入新的遥感图像文件 (如MIG文件) 中; (2) 可视化的树结构, 在树的叶子节点保存着每一类的属性。
二、结语
通过本文研究发现:决策树算法对于输入数据的空间特征和分类标志具有更好的弹性和坚韧性, 它用于遥感数据分类的优势主要在于对数字图像数据特征空间的分割上, 其分类结构简单明了, 尤其是二叉树结构的单一决策树结构十分容易解释。因此, 当遥感图像数据特征的空间分布很复杂, 或者源数据各维具有不同的统计分布和尺度时, 基于决策树算法的分类方法能够获得较为理想的分类结果。
参考文献
[1]李宁, 等.决策树算法及其常见问题的解决[J].计算机与数字工程, 2010, 3 (33) :60264.
基于最大间隔的决策树归纳算法 篇6
关键词：支持向量机,支持向量机反问题,间隔,决策树归纳
0 引言
决策树归纳是归纳学习中最实用最重要的学习和推理方法, 由于构造最优的决策树问题已经被证明是NP完全问题[2,3,4], 因此典型的决策树学习算法都是在完全假设空间的自顶向下的贪心搜索算法, 但各搜索算法所采用的启发式有所不同。其中选用最小信息熵为启发式信息的ID3算法是一个典型代表, 这种方法生成的决策树规模小且计算复杂度低, 但其泛化能力 (generalization) 不佳。
统计学习理论 (Statistical Learning Theory或SLT) 是一种专门研究小样本情况下机器学习规律的理论, 它是建立在一套较坚实的理论基础之上的, 为解决有限样本学习问题提供了一个统一的框架。V.Vapnik等人从六、七十年代开始致力于此方面研究[5], 到九十年代中期, 随着其理论的不断发展和成熟, 也由于神经网络等学习方法在理论上缺乏实质性进展, 统计学习理论开始受到越来越广泛的重视[7,8]。在这一理论基础上发展了一种新的通用学习方法———支持向量机 (Support Vector Machine或SVM) , 它已初步表现出很多优于已有方法的性能, 尤其是较强的泛化能力。
根据统计学习理论, SVM分类间隔越大, 泛化能力越强, 考虑到这一关系, 我们可以用最大间隔作为决策树归纳的启发式信息, 以此来划分决策树结点, 构造决策树。一方面, 可以从原始数据中产生高质量的决策树, 最大限度地提高决策树对新观察事例的预测准确性;另一方面, 理论上它将两种重要的归纳方法互补地结合在一起 (支持向量机泛化能力强但得到的知识即超平面不易理解, 决策树泛化能力一般但归纳出的知识容易理解) 。
1 支持向量机
1.1 支持向量机基本问题
支持向量机是由Vapnik等人提出并以统计学习理论为基础的一种新的学习机器。其基本问题描述如下:设有训练数据
可以被一个超平面
分开。如果这个向量集合被超平面没有错误的分开, 并且离超平面最近的向量与超平面之间的距离是最大的, 则我们说这个向量集合被这个最优超平面 (或最大间隔超平面) 分开。如图1所示。
我们使用下面的形式;来描述分类超平面:
并且有紧凑形式:
yi (燮ω·xi) +b燮叟1, i=1, 2, ..., l. (2)
容易验证, 将样本点无错误分开的超平面 (1) , 其间隔为:
由统计学习理论可知, 一超平面的泛化能力, 即对未知样本准确预测能力, 取决于超平面的间隔margin, 从而最优超平面就是满足条件 (2) 并且使得
最小化的超平面。并且通过解决下述优化问题来构造最优超平面:
最优超平面是在线性可分的前提下讨论的, 在线性不可分的情况下, 可以在条件中加入一个松弛变量ξi叟0, 这时的最优超平面称为广义最优超平面, 通过解决如下问题得到:
其中C是一个常数。最优超平面可通过解下面对偶问题得到:
最优分割超平面有如下形式:
事实上, 对于大多数实际问题, 样本点在原空间中一般不是线性可分的, 所以用上述方法往往得不到好的决策函数 (最优超平面) 。为此, Vapnik将支持向量机从原空间中推广至特征空间。其基本思想如下:支持向量机通过某种事先选择的非线性映射将输入向量x映射到一个高维特征空间Z, 在这个高维特征空间中构造最优分类超平面。如图2。
Vapnik等人发现, 在特征空间中构造最优超平面并不需要以显示形式来考虑特征空间, 而只需要能够计算支持向量与特征空间中向量的内积。根据Hilbert-Schmidt定理, 在Hilbert空间中两个点的内积有下面的等价形式:
其中K (x1, x2) 式满足下面条件的对称函数, 也成为核函数。
所以有分割超平面有如下形式:
需要注意的是, 将上一节中的 (x1·x2) 换为K (x1, x2) , 结论仍然成立。
1.2 支持向量机反问题
对于给定的一组没有决策属性的样本点, 我们可以随机的把其分为两类。此时我们可以利用前面的知识来求出最优分割超平面, 并计算出最大间隔。若划分为两类的样本点线性不可分, 间隔计为0。显然, 间隔的大小取决于对原样本点的随机划分, 支持向量机反问题就是如何对样本点进行划分, 才能使最优分割超平面的间隔达到最大。
支持向量机反问题是一个优化问题, 其数学描述如下:设S=圳x1, x2, ..., xN圳为一样本集, 其中xi∈Rn, i=1, 2, ..., N, Ω表示从S到{-1, 1}的函数全体。对于给定的一个函数f∈Ω, 集合S被划分为两个子集, 并可以计算出其相应的间隔。我们用Margin (f) 表示由函数f所决定的间隔 (泛函) , 那么反问题就是要解决如下问题:
2 基于最大间隔的决策树归纳学习
2.1 算法描述
考虑到支持向量机较强的泛化能力, 我们可以将支持向量机反问题应用于决策树的归纳过程, 即在归纳过程中用最大margin来作为启发式。
其设计思想为:对于一个给定的各属性取值为连续型数据的训练样本集, 一开始我们不考虑样本的类别, 通过求解SVM反问题, 可以得到该样本集的一个具有最大margin的划分, 即将样本集分为两个子集。这些子集被作为决策树的分支, 被标记为-1的样本集合作为左支, 被标记为+1的样本集合作为右支, 和这一划分相对应的超平面被作为该结点处的决策函数。当我们对新来的样本进行测试时, 将其代入决策函数, 取值为负被分到左支, 取值为正被分到右支。
以两类问题为例, 具体算法为:
Examples即训练样例集。β是某一类别所占比例的一个阈值。返回能正确分类给定Examples的决策树。
创建树的Root结点
如果Examples正类的比例大于β, 那么返回label=+的单结点树Root
如果Examples负类的比例大于β, 那么返回label=-的单结点树Root
否则
对Examples进行SVM反问题求解, 获得最大margin的划分
令所得超平面为f (x) , 若f (x) 燮0, 记c (x) =-1
若f (x) 叟0, 记c (x) =+1
在Root下加两个分支, 分别对应f (x) 燮0和f (x) >0
令Examples-1为Examples中满足f (x) 燮0的子集
令Examples+1为Examples中满足f (x) >0的子集
在这两个分支下分别加子树MaximumMargin (Examples-1, β) 和MaximumMargin (Examples+1, β)
结束
返回Root
2.2 实验结果
用最大间隔作为启发式来生成决策树和用最小熵作为启发式生成二叉决策树针对的均为实值型数据, 我们从UCI数据库中挑选了Iris, Rice, Pima, Image Segment四个实值型数据库 (表1列出了各个数据库的特征) , 进行了实验, 对比了生成决策树的测试精度。对于多类数据库, 只选取了其中的两类来进行实验。
实验结果如表2所示, 算法1代表二叉决策树归纳算法, 算法2代表基于最大间隔的决策树归纳算法, 所用时间为运行算法2所需的时间。
从实验结果中可以看出, 用最大margin做启发式, 将SVM的相关理论用于决策树归纳过程, 使决策树的泛化能力在一定程度上得到了提高。
3 总结
启发式算法是决策树归纳学习的重要研究课题, 由于NP困难, 寻找最优的决策树是不现实的, 从而探索各种启发式算法去产生一个高精度的决策树变成了这类研究的焦点。
决策树的生成过程是对结点进行划分的过程, 而支持向量机反问题研究的是如何寻找具有最大间隔的划分, 因此可以将其应用到决策树归纳过程, 用最大margin作为启发式来生成决策树, 以提高其泛化能力。本文主要对基于最大间隔的决策树归纳学习算法进行了设计与实现。实验数据表明该算法生成的决策树的测试精度比用最小熵做启发式的二叉决策树有一定提高。
参考文献
[1]Tom M.Mitchell, Machine Learning, The Mcgraw-Hill Companies Inc, Singapore, 1997.
[2]Hyafil L, Rivest R L.Constructing Optimal Binary Decision Trees Is NP-Complete[J].Info Proc Letters, 1976, 5 (1) :15-17.
[3]Hong JR.AE1:An extension approximate method for general cover-ing problem[J].International Journal of Computer and Information Sci-ence, 1985, 14 (6) :421-437.
[4]谢竞博, 王熙照.基于属性间交互信息的ID3算法.计算机工程与应用, 2004:93-94.
[5]Vladimir N.Vapnik.Estimation of dependences based on empirical data.New York:Springer-Verlag, 1982.
[6]Vladimir N.Vapnik.The nature of statistical learning theory.Berlin:Springer-Verlag, 1995.
[7]Vladimir N.Vapnik.An overview of statistical learning theory, IEEE Trans.Neural Networks, 1999, 10 (5) :88-999.
一种改进的决策树算法研究 篇7
决策树分类算法中的ID3算法是Quilan在1986年提出来的,也是决策树构造中的经典算法[1]。ID3算法是以信息论为基础,它使用信息熵和信息增益两个指标为衡量标准,选择信息增益最大的属性划分训练样本,从而生成决策树。
定义1、按类标签对训练集D的属m性集A进行划分,信息熵为:
Pi为训练集D中属于第i类的概率。
定义2、按属性集A中每个属性进行划分,得到一组信息熵:
Dj为属性集中每个属性的出现的次数,D为所有属性的总次数。
定义3、信息增益为:
ID3算法对每个节点中选择Gain(A)中最大的属性A作为选择分支的属性。这种算法的缺点是:倾向于选择取值较多的属性[2],在有些情况下这类属性可能不会提供什么有意义的信息,ID3学习简单逻辑表达式的能力差[3]。此外,ID3将注意力集中在属性的选择方面,而属性的选择对决策树的影响如何, 仍无定论[4]。
2 改进的ID3算法
1)调整信息增益
针对ID3算法偏向于选择取值较多但实际中并不总是最优的属性作为测试属性的缺点,调整信息增益。Gain’(A)=Gain(A) /X,其中X的取值大于等于1,主要由属性A的取值个数和使用者根据经验及领域知识来确定,一般取值个数越多则X越大。改进的ID3算法通过调整每个属性的信息增益,使生成决策树时数量少但又很重要的属性不会被淹没,最终使决策树克服了对取值多的属性的偏爱,因为属性取值越多,调整后的信息增益就越小,这个属性当然就很难被选中为判断属性了。
2)剪枝
剪枝方法主要是考虑在决策树的哪个位置产生叶子合适 [5]。剪枝算法分前剪枝和后剪枝。前剪枝是在决策树构造过程中选取某个预定义的阀值,使得某些节点不再继续分裂,限制树的生长。后剪枝是将已生成的决策树做去分支处理[6]。前剪枝由于很难选取一个合适的阀值,应用困难。后剪枝的时间复杂度高,但生成的决策树准确度高,但主要应用的几种后剪枝算法都存在过剪枝或欠剪枝现象。由于各种剪枝算法都有缺点,所以本文提出采用灵活的剪枝方法进行剪枝。
剪枝方法为:首先,根据具体需要设定生成决策树的高度、精确度等信息,设定主要依据经验和领域知识来确定。然后, 针对决策树节点a来说,对a进行剪枝,则产生的错误分配样本数为:
未剪枝的子树错误分配样本数为:
未剪枝的子树误差为:
其中,e(a)为a节点的错误分配样本数,Ti(i=1,2,…,n)是Ta节点的子节点,Ca是Ta节点的子节点数。如果叶子节点的成立,那么Ta可以剪枝。
3实验测试结果
实验所用数据为UCI数据库中的Iris数据集(样本数209个,属性7个)、Breast数据集(样本数817个,属性11个)和Seg-mentation数据集(样本数2932个,属性26个)。对这三个数据集所有连续值的属性使用DBChi2算法对数据进行离散,随机抽取每个数据集中的2/3用于训练样本集,其余的1/3用作测试样本集,然后分别用传统的ID3算法和改进的ID3算法构建决策树,最后通过测试样本集测试准确度。上述构造决策树的方法反复进行十次,得出的结果如表1。
从表1中能明显的得出,改进的ID3算法平均的分类准确度更高,生成决策树的平均叶子数也高过传统的ID3算法,具有更低的复杂性。从实验还得出改进的ID3算法通过不断的学习调整信息增益,从而克服了传统ID3算法倾向于选择取值较多的属性的缺点,但是改进的ID3算法通过实验得出在时间复杂度上和传统ID3几乎一致。
4 结束语
改进的ID3算法调整了传统的ID3算法的信息增益计算方法,又加入了灵活的剪枝策略。它可以依靠经验或领域知识人工增强重要属性在分类决策中调整信息增益,从而减少非重要属性的信息量,特别是它可以减少ID3算法对取值较多的属性的依赖性,从而改善分类规则和结果。
摘要：决策树算法是数据挖掘中的一个常用算法,它通过构造决策树来发现数据中蕴含的分类规则,如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树算法中常用的一种是ID3算法,该文针对传统ID3算法的缺点,提出一种改进的ID3算法,通过实验证实,改进的ID3算法在生成的决策树的规模和精度方面都比传统的ID3算法好,使用这种改进的ID3算法可以提高性能。
决策算法 篇8
Forrest[2] 把人工免疫系统(Artificial Immune System,AIS)运用到入侵检测系统(Intrusion Detection Systems,IDSs)中提出了著名的否定选择算法(Negative Selection Algorithm,NSA)并利用r领域匹配函数(R-contiguous Matching Function, RCMF)来判定模式间的匹配程度。但是,Kim通过实验证明,只有在被检测对象是网络通信数据的一个小子集时NSA才是有效的。NSA的随机搜索特性导致其仅仅只能应用于有限网认为RCMF作为一种连续位匹配函数,在对具有多个分离特征区间的网络通信数据进行匹配程度判定时,其作用不明显。络入侵的识别。同时,Kim[3]Kim和Bentley[4,5]又年提出了动态克隆选择算法(DynamiCS),主要用于网络入侵检测。
针对传统的NSA算法中生成大量无效抗体,并且抗体之间缺乏多样性,不能保证识别器在一定数量内尽可能覆盖最大的nonself空间的问题,提出了基于决策树及遗传算法的人工免疫入侵检测算法。利用决策树对噪声数据有很好的健壮性,对随机生成的候选免疫细胞进行分类,并选取亲和力低的免疫细胞进行变异,再经过否定选择淘汰部分免疫细胞,最后淘汰种群中高浓度的免疫细胞,生成成熟的免疫细胞。
1 理论基础
1.1 基因型表示网络数据
国际上,K.De.Jong等人在1993年概念学习中提出的基因表达方法。国内吴泽俊,钱立进,梁意文等人提出了新的基因型和表现型的表达方式[6]。采用基因型表示网络数据。首先每个网络数据都是由多个属性组成,每个属性都有多个不同的属性值。每个属性就是一个基因,每个属性的不同属性值就是特征簇(Phototypes)。例如:协议类型,目的地址,发送数据等。不同的基因的特征簇也不相同,用“1”“0”的代码表示特征簇。例如协议类型有TCP、UDP和ICMP就可以用0001表示TCP,用0010表示UDP,用0100表示ICMP。每个基因都包含了若干个特征的特征区间,为1表示包含这个特征值,为0表示不包含。如果特征区间的第一位为1,则表示这个区间以后的值无效,该特征区间包含了任意值。一条网络数据就可以用多个基因来表示,如果网络数据有连续值,则将连续值离散化。因此随机生成的识别器以及self和nonself都可以用基因型来表示,有利于计算抗体和抗原之间的亲和力以及浓度计算。
2.2 决策树
决策树是一种逼近离散值目标函数的方法,这种方法中学习到的函数被表示为一棵决策树[7]。每种决策树都有自己不同的选择属性的标准。Id3用信息增益,C4.5用信息增益率。按属性选择标准选出当前属性,并按当前属性的n个属性值,把集合分裂成n个不同的子集。若分裂的子集中所有记录的目标属性值一致,则生成叶子节点停止分裂。否则继续选择属性再分裂直到选择的目标属性的属性值一致。决策树的分类实际是对训练样子的预测分类结果。
一棵完全决策树能非常准确地反映训练集中数据的特征,但是由于完全决策树对训练样本的特征描述得“过于精确”,有时候反而因失去了一般代表性而无法实现对新样本的合理分析,所以完全决策树不一定是一棵能对新数据进行合理预测的最佳决策树。这种现象一般称为“过度拟合(overfitting)” [7]。解决过度拟合的主要方法是对决策树进行剪枝,即剪去影响预测精度的分枝[9]。悲观错误剪枝(Pessimistic Error Pruning, PEP) 常用于Id3算法, 基于错误的剪枝(Error Based Pruning, EBP)常用于C4.5算法。
目前生成决策树方法的算法主要有3种:CART算法、CHAID算法、C4.5算法[8]。其中C4.5算法是发展的比较完善也是比较简单易懂的一种决策树算法,因此以C4.5算法为基础对决策树进行讨论。C4.5算法自顶向下选择不同的属性,对属性的每一个值产生一个分支,分支属性值的相应样本子集被移到新生成的子节点上,这个算法递归地应用于每个子节点上,直到节点的所有样本都分区到某个类中,到达决策树的叶节点的每条路径表示一个分类规则。C4.5算法的属性选择的基础是基于使生成的决策树中节点所含的信息熵最小。
Info(S)=undefined
式中:freq(Ci,S) 代表集合S中属于类Ci (k个可能类中的一个)的样本数量。 |S|表示集合中的样本数量。上面的公式仅仅给出了一个子集的熵的计算,如果按照某个属性进行分区后就涉及到若干个子集,需要对这些子集进行熵的加权和的计算,公式如下所示:
Infox(T)=-∑((|Ti|/|T|)×Info(Ti))
其中:T-按照属性x进行分区的集合。为了更加明显的比较不同集合的熵的大小,计算分区前的集合的熵和分区后的熵的差(我们把这个差叫做增益),增益大的就是我们要选取的节点。公式如下:
Gain(X)= Info(T)- Infox(T)
2 算法设计
2.1 算法的模型
假设一个抗体的指令集合包含N个分子(N个抗体),而每个分子又存在K个基因,每个基因都由长度不等的n位组成,其中每个分子都是从长度为L的“1”和“0”数字构成的属性串。
算法的步骤如下:
①随机生成长度为L的候选抗体(识别器)R。
②将self集和nonself集用遗传算法表示并生成决策树,决策树的目标属性为no和yes,满足self集的抗体的目标属性为yes,满足nonself集的目标属性为no。利用生成的决策树将候选抗体R进行分类,将分类得到目标属性为yes的抗体淘汰,并跳转到第①步,如果分类得到目标属性为no的抗体就继续到第③步。
③ 计算候选抗体适应度fitness,这里提出了fitness函数的计算公式
定义1 候选抗体与单位抗体的匹配度P
P=undefined (1)
其中,L为抗体的长度,i是抗体的第i位。P的取值范围Pϵ[0,1]。
定义2候选抗体与抗体集合的平均匹配度AP
AP=undefined (2)
其中Pj用公式1中的Pj代替,N位抗体集合的个数,j是抗体集合的第j位。
定义3候选抗体适应度fitness的公式如下:
fitness(R)=Ap (3)
④ 计算当前抗体集合的平均适应度,如果fitness小于平均适应度则当前候选抗体被淘汰并且转到第①步,否则就继续进行。平均适应度的计算公式如下:
afitness=undefined (4)
其中 N位抗体集合的个数,fitness(Pj)是第j个抗体的适应度。
⑤ 通过对抗前抗体进行杂交和变异:在当前抗体中的k个基因中的30%个基因进行变异,并生成一定数量的种群。
⑥ 生成的种群经过否定选择算法淘汰部分种群
⑦ 计算种群中抗体的浓度
依据Mori的算法给出计算抗体浓度的以下公式:
计算抗体中位置为j的信息熵的函数Hj(N)为
Hi(N)=-undefined (5)
其中,k为某个基因的长度,pi,j表示基因位j是字符串i的概率。所以一个抗体的平均信息熵就为
H(N)=undefined (6)
计算抗体v和ω间的亲和度
ayundefined (7)
其中,H(2)根据公式4计算。
计算每个抗体的浓度cv,如果cv大于一个给定的阀值δ1,则这个个体就会被抑制(从计算机中删除),否则他将成为记忆抗体。
⑧ 计算种群单位个体的浓度是否低于识别器集合的平均浓度,如果高于平均浓度则淘汰,否则就替换识别器集合中高浓度的抗体。
⑨ 当抗体集合的平均浓度低于一定的阈值的时候停止生成识别器,否则跳转到第①步。
2.2 算法的流程图
2.3 算法的伪代码
Procedure基于决策树及遗传算法的人工免疫入侵检测算法
利用公式3计算识别器总适应度;
While 识别器的适应度低于抗体集合的平均适应度
将识别器进行遗传变异产生识别器种群;利用公式8计算种群浓度;用低浓度种群替换识别器高浓度种群中
End
End
3 算法分析
决策树是一种逼近离散值函数的方法,对噪声数据有很好的健壮性。由于在计算机免疫学中目前还存在着"不完全self集问题"导致存在着大量nonself集的缩放,造成了在self集和nonself集中存在着一定数量的噪声数据,由self集和nonself集组成的训练样本集生成决策树再通过剪枝能够很好的对随机生成的候选识别器进行分类,并且得到较高的测试数据的精度,这样就减少了后续不必要的计算,提高了整个算法的效率。
随机生成的候选识别器通过与抗体集也就是self集的每个基因的每一位的匹配计算,统计最后的匹配结果生成适应度fitness函数。由于人为的制定self集空间总是有限,根据适应的函数,候选识别器与self集中每个抗体的差异程度来评判候选识别器,差异程度越大的候选识别器,越有利于覆盖更广的nonself集空间,提高了识别器集合的的多样性,降低了错误否定率,有利于提高识别器集合的检测效率。
在算法中,采用两种遗传算子进行繁殖即杂交和变异。杂交变异包括三种:第一种一个候选识别器中的某个基因中的两个基因值互相交换位置。第二种一个候选识别器中两个具有相同位数的基因进行交换。第三种候选识别器和self集中的某个抗体的相同的基因位进行交换。变异包括:第一种将某一基因的某一基因位取反。第二种将基因集体左移或右移。第三种对某基因全部取“1”表示这个基因可以取任意值。增加遗传算子的种类,就有利于繁殖后代的多样性,提高了识别器的识别能力。
由候选识别器通过遗传算子繁殖的候选识别器种群,可能产生大量错误的抗体或者无效的看体,有的抗体可能本身就是self集中的元素。这些错误的抗体可能造成错误肯定率,直接影响到识别器的识别效率。因此引入否定选择算法再次将错误的无效的候选识别器淘汰掉。减少错误肯定率,提高识别器的效率。
最后通过计算候选识别器种群的浓度,淘汰识别器集合中浓度较高的识别器。由于较高的浓度的识别器,降低了识别器集合的多样性,缩小了识别器集合对nonself空间覆盖程度。因此对较高浓度的抗体进行抑制。
4 结束语
基于Forrest将AIS应用到IDSs中的研究,提出了一种基于决策树及遗传算法的人工免疫入侵检测算发该算法与传统的克隆选择算法做了的改进:①利用决策树学习对噪声数据有很好的健壮性,提出了一种新的用于计算抗原和抗体之间的亲和力的方法。②提出了一种新的遗传算法中的适应度函数fitness的计算公式。③将否定选择算法与遗传算法相结合,并利用识别器之间的浓度高低,引入淘汰机制,使识别器具有动态性。
摘要：针对传统的否定选择算法中生成大量无效抗体,并且抗体之间缺乏多样性的问题,设计了基于决策树及遗传算法的人工免疫入侵检测算法。将决策树和遗传算法引入传统的否定选择算法中,利用决策树计算抗原和抗体之间的亲和力,提出了新fitness的计算公式,并利用抗体浓度衡量抗体集的多样性,将低浓度抗体代替高浓度抗体,实现了抗体的多样性,确保了当抗体集的数量一定时尽可能覆盖最大的非自体集空间,以提高抗体集的性能。
关键词：人工免疫,入侵检测,决策树,遗传算法,否定选择算法
参考文献
[1]李涛·计算机免疫学·北京:电子工业出版社,2004.
[2]Forrest S,Perleson A,Allen L,et al·Self-Nonself discrimination in a computer·Oakland,USA:Proceedings of IEEE Symposium on Research in Security and Privacy,2002·202～212
[3]Kim J,Bentley P·An Evaluation of Negative Selection in an Artificial Immune System for Network Intrusion Detection·In Genetic and Evolutionary Computation Conference2001(GECCO-2001),San Francisco USA,CA,2001,1330～1337
[4]J Kim,P J Bentley·Towards an Artificial Immune System for Network Intrusion Detection:An investigation of Dynamic Clonal Se-lection with negative Selection Operator·In:Proceedings of the Congress on Evolutionary Computation,(CEC-2002),Honolulu USA,2002-05-12-17:1015～1020
[5]J Kim,P J Bentley·AModel of Gene Library Evolution in the Dynamic Clonal Selection Algorithm·Proceedings of the First Interna-tional Conference on Artificial Immune Systems(ICARIS),Canterbury UK,2002-09-9-11:57～65
[6]吴泽俊,钱立进,梁意文·入侵检测系统中基于免疫的克隆选择算法·计算机工程,2004,30(6):50～52
[7]Tom M·Mitchell·机器学习·北京:机械工业出版社,2006·38～60
一种基于属性加权的决策树算法 篇9
ID3算法和C4.5算法应用于探井生产决策支持系统发现在解决复杂决策的问题准确性差的问题,由于基于信息墒的算法都没有考虑在实际应用中不同属性对决策结果影响的程度,并且由于在计算信息墒的过程中计算量大,算法复杂度高,导致对于探井生产管理决策支持系统中大数据量的计算存在计算准确率低。本文提出一种基于属性约简的加权决策树算法,根据不同属性对决策影响程度的不同进行加权,以提高决策结论准确性,实验结果表明,相比ID3和C4.5算法,基于属性约简的加权决策树算法应用于探井生产决策支持系统中有效地提高了决策的准确率,决策树算法的核心是分裂节点的选取,本文首先介绍决策树算法ID3和C4.5,然后介绍属性加权算法,以及权值选取标准,最后通过对实际探井数据测试,说明算法改进后的效果。
2 决策树算法简介
2.1 ID3算法
ID3算法[1]是一种基于信息熵的决策树学习算法,是决策树算法的代表。ID3算法把Shannon信息论引入到了决策树算法中,采用分治策略。在决策树各级结点上选择属性时,检测所有的属性,选择信息增益最大的属性产生决策树结点,由该属性的不同取值建立分支,再对各分支的子集递归调用该方法建立决策树结点的分支,直到所有子集仅包含同一类别的数据为止,最后得到一棵决策树,对新的样本进行分类。
2.2 C4.5算法
C4.5算法是在ID3算法的基础上增加了对连续型属性和属性值空缺情况的处理,对树剪枝和生成规则也有了较成熟的方法。与ID3不同,C4.5采用基于信息增益比的方法选择测试属性。
C4.5算法基本思想是把连续值属性离散化。若A是在连续区间取值的连续型属性,首先将训练集X的样本根据属性A的值按升序排列为a1,a2,…,am(m为训练集的样本数)。如果A有n种取值,则对每个取值vj(j=1,2,…,n)将所有的记录进行划分。这些记录被分成两个部分:一部分落在vj的范围内,而另一部分则大于vj。针对每个划分,分别计算增益比率,选择增益最大的划分来对相应的属性进行离散化。
3 基于属性加权的决策树算法
本文采用对属性加权的方法标记属性的重要性,根据不同属性对决策结果的影响程度不同,计算属性的权值,使对决策结果影响程度越大,也就是越重要的属性权值越大。在建立决策树的过程中每次选择权值最大的属性作为分裂节点。
3.1 属性约简
属性约简[3]是粗集理论[6]的核心内容之一,在数据库系统中,经常存在大量冗余的信息,为了减少冗余信息,提高数据库蕴含知识的可理解性,人们在属性约简上已做了很多工作,提出了一些比较有效的方法,例如基于条件熵的决策表约简[7]、基于可辨识矩阵的属性约简等等。本文利用属性约简方法对属性进行约减,去掉不重要的属性,再利用约简之后获取的可辨识矩阵进行权值计算。
属性简约算法是在保持分类能力不变的前提下,逐个约去冗余的属性,直到不再有冗余的属性,此时得到的属性集是最小属性集。
定义1:令R为等价关系族,设P⊆R,且P≠Φ,则P中所有等价关系的交集称为 P上的不可分辨关系,记作IND(P),IND (P)也是一种等价关系。
定义2:设K=(U, A)为一个信息系统,其中U为论域,A为属性的非空有限集合。若P∈A 是满足IND (P)= IND (A)的极小属性子集,则称 P为A 的一个约简。
定义3:(可辨识矩阵).令决策表系统S=< U,R,V,f >,R=C∪D是属性集合,子集C={ai|i=1,2, …,m}是条件属性集合,D={d}是决策属性集合,U={x1,x2,…,xn}是论域,ai(xj)是样本xj在属性ai上的取值。CD(i,j)表示可辨识矩阵中第i行j列的元素,则可辨识矩阵CD定义为
undefined
其中i,j=1,2,…,n
为了便于计算,本文把可辨识矩阵进行了量化,如下式:
undefined
其中i,j=1,2,…,n
属性约简的实现:
第1步:建立可辨识矩阵CD。在给定的数据矩阵M×N的基础上,把属性值两两比较,相同为0,不同为1,则可得到(M-1)!×N的可辨识矩阵。其中,前N-1列为条件属性,最后1列为决策属性。
第2步:逐个判定CD中的任一列,若删除第i列,对应的属性为ai(ai∈C),若IND(C)=IND(C-{ai}),则ai可以约去,删除CD中的第i列,属性子集C’=C-{ai};若IND(C)≠IND(C-{ai}),则ai不可以约去;
第3步:继续检查CD中每个属性是否能被约去,直到出现某个属性子集C’’中的每个属性都不能被约去为止,此时该属性子集C’’即为所有的属性简约。
3.2 属性加权
探井生产管理决策支持系统中处理的属性数据多数是连续型数据,而建立决策树必须使用离散化的属性值,因此在选择条件属性后必须对连续的属性值进行离散化[8]。本文对连续属性值离散化的方法采取二值分裂法,方法如下:
对于连续属性ai,首先对属性值由小到大排序:b0,b1,…,bn,其候选断点可取为
undefined
针对每个断点ci分别计算信息熵ei,选取ei最小的断点ci作为分裂点。一般信息熵越小,说明集合中个别决策属性值占主导地位,因此混乱程度越小。选取信息墒最小的断点cmin作为连续属性ai离散化的分裂点。
对离散化后的数据集建立可辨识矩阵CD,对CD进行属性约简。得到约简后的可辨识矩阵C’’。属性ai权值twi计算过程如下:
(1)计算属性ai在数值矩阵C’’中出现次数Mi:
undefined
其中,i=1,2,…,k,C’’(j,i)表示C’’中j行i列的数据。
(2)计算属性ai的频度:
undefined,其中,i=1,2,…,k
(3)计算属性ai的权值:
undefined, 0
其中,i=1,2,…,k,所有属性的权值之和满足:undefined。
表1是探井进尺调整决策过程利用加权算法计算的属性权值结果,对决策结果影响程度大的属性权值较大。
3.3 基于属性加权的决策树算法
把每个属性的权值作为属性对决策结果的影响程度,每次选择权值最大的属性为分裂属性,即对决策结果影响程度最大的属性作为分裂节点。
基于属性加权的决策树算法的具体建立步骤如下:
输入:训练样本samples;属性列表attribute_list;
输出:一棵判定树Generate_Decision_Tree(samples, attribute_list)。
(1)创建节点N;
(2)如果 samples都在同一类C,返回N作为叶节点,以类C标记;
(3)如果 attribute_list为空, 返回N作为叶节点,用samples中最普通的类标记;
(4)计算attribute_list中每个属性的权值;
(5)选择attribute_list中具有最大权值的属性test_attribute;
(6)标记节点N为test_attribute;
(7)对于每一个test_attribute中的已知值ai;
(8)由节点N长出一个条件为test_attribute= ai 的分支;
(9)设si为samples样本中test_attribute= ai的集合;
(10)如果si为空,加上一个树叶,用samples中最普通的类标记。否则,加上一个由Generate_Decision_Tree (si, (attribute_list-test_attribute))返回的节点。
上述建树过程是一个递归过程,其终止条件为:①给定节点的所有样本属于同一类(步骤2);②没有剩余属性可以用来进一步划分样本(步骤3);③没有样本满足test_attribute = ai (步骤10)。
算法流程如图1所示。
4 实验结果比较
实验采用探井生产管理决策支持系统中的下套管决策过程构建决策树。下套管决策过程所需数据包括测井数据和录井数据,其中测井数据记录每口井每个小层的测井属性数据及其测井解释结果;录井数据记录、录取钻井过程中的各种相关信息,主要包含气测综合录井解释成果数据、定量荧光分析数据、罐顶气评价成果数据等不同类别数据。
下套管决策过程的目的是根据录井数据推理出每口井每个小层含油、气、水产状解释结果。实验选择了气测综合录井解释成果数据、罐顶气评价成果数据及地化岩石热解分析储层含油气评价数据三种录井数据分别构建决策树。实验主要分为五个阶段:
第一步,确定一口测试井,选取聚类属性,聚类求参考井。
第二步,根据参考井,选取参考井在录井表中的小层属性数据,将参考井各小层的测井解释结果作为最后一列加入选出的录井小层数据,构成训练样本。
第三步,根据训练样本,将测井解释结果作为决策属性,使用决策树算法,建立决策树。
第四步,根据已建好的决策树推理出If-Then决策规则。
第五步,选取测试井小层在录井表中的属性数据,根据决策规则推理出测试井小层的决策结果。
实验按以上步骤选取已完钻井的相关数据,把利用属性加权算法、ID3算法、C4.5算法获得的决策结果与数据库中已完钻井的实际解释结果数据相比较,以测试三种不同算法的平均准确率,验证利用属性加权算法的改善决策准确度的有效性。
实验结果如表2所示。表2中各字段的含义:井号即为测试井名,层位是测试井对应的段层,底界深度和顶界深度为段层中一个小层的底界和顶界,测井结果是测试井小层对应的正确解释结果,ID3算法、C4.5算法和属性加权算法分别是三种决策树算法推理出的分类结果。将三种算法推理出的结果与测井结果进行比较,与测井结果一致,说明推理正确。统计计算平均准确率。
由实验结果表3看出,属性加权决策树算法比ID3算法的平均准确率高出近12个百分点,比C4.5算法高出4个百分点,实验效果显著。
5 结束语
本文主要根据实际应用系统研究决策树算法,针对ID3算法和C4.5算法在复杂决策问题准确性差的问题,将粗集理论与决策树有机结合,提出基于属性加权的决策树算法。实验表明属性加权算法准确率较高。
参考文献
[1]QUINLAN J R.Induction of Decision Tree[J].Machine Learning.1986.81-106
[2]BANFIELD R E,HALL L O,BOWYER K W.A Comparison of Decision Tree Ensemble Creation Techniques[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007.173?180
[3]ZDZISLAW P.Rough set theory[J].Kunstliche Intelligenz.2001,15(3):38-39
[4]LIU L L,ANDREW K.C.W,WANG Y.A Global Optimal Algorithm for Class-Dependent Discretization of Continuous Data[J].Intelligent Data Analysis.2004.151-170
[5]HU Keyun,LU Yunchang,SHI Chunyi.Feature Ranking in Rough Sets[J].AI Communications,2003,16:41-50
[6]王国胤.Rough集理论与知识获取[M].西安:交通大学出版社,2001.
[7]王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报,2002,7(25):759-766
[8]谢宏,程浩忠,牛东晓.基于信息熵的粗糙集连续属性离散化算法[J].计算机学报,2005,1570-1573
[9]吴成东,许可,韩中华,裴涛.基于粗糙集和决策树的数据挖掘方法[J].东北大学学报,2006,27(5):481-484
[10]乔梅,韩文秀.基于Rough集的决策树算法[J].天津大学学报,2005,138(9):842-846