决策树评估范文

决策树评估范文（精选9篇）

决策树评估 第1篇

1 卫生应急风险决策树模型的基本思想

通过对已经发生的突发公共卫生事件的属性及风险等级的分析,构建卫生应急风险决策树模型;并基于此模型,根据突发公共卫生事件的属性对未来可能发生的风险事件进行风险评估,见图1。其中,表示突发公共卫生事件的属性,表示突发公共卫生事件的风险等级。通常,根据风险评估的结果,将突发公共卫生事件的风险等级划分为高风险、中等风险和低风险三个等级。

我们称决策树中最顶层的属性为父节点,中间的属性为子节点,位于决策树末端的为叶节点,叶节点代表突发公共卫生事件的风险等级。假设突发公共卫生事件共有n个属性,那么选取哪个属性作为父节点,哪个属性作为下一层的子节点?对于突发公共卫生事件而言,往往希望能够用较少的关键属性快速、准确地判断事件的风险等级,也就是说构建的决策树模型应该有较少的分层和分枝。因此,如何选择判断属性是卫生应急风险决策树模型构建的关键。

2 卫生应急风险决策树模型的构建过程

此文采用ID3 算法,构建卫生应急风险决策树模型。首先从突发公共卫生事件样本集中找出最具判别力的属性,该属性把样本集划分成多个子集;然后从每个子集中选择最有判别力的属性进行划分,直到所有子集仅包含同一风险等级的事件为止;最后得到一棵决策树。ID3 算法是以信息增益作为选择属性的判别标准[3]。

假设突发公共卫生事件样本集X中有m个样本,将突发公共卫生事件的风险等级划分为三个等级xi(i=1,2,3):高风险(x1)、中等风险(x2)、低风险(x3)。突发公共卫生事件的属性有s个,记为Yi(i=1,2,Ls);对于属性Yi有n个属性取值,记为yj(j=1,2,Ln)。根据香农的信息论理论[4],卫生应急风险决策树模型的构建过程如下:

(1)定义突发公共卫生事件样本集的信息熵为:

其中P(xi)为样本集中突发公共卫生事件风险等级为xi的样本概率。信息熵H(X)度量了样本集中样本风险等级的混乱程度,熵值越大,等级越混乱,正确估计其值的可能性就越小。H(X)反映了在没有任何属性信息的辅助和帮助下,评估突发公共卫生事件风险等级的不确定程度。

(2)针对突发公共卫生事件的每个属性Yi,计算突发公共卫生事件样本集X的条件熵:

其中:P(yj)为样本集中属性Yi的属性值为yj的样本概率。P(xi|yj)表示筛选属性Yi的属性值为yj的样本为子样本集,计算子样本集中突发公共卫生事件风险等级为xi的样本概率,反映了在属性Yi取值为yj的条件下,突发公共卫生事件风险等级为xi的概率。

突发公共卫生事件样本集的条件熵H(X|Yi)是属性Yi取不同属性值时样本的平均信息熵,反映了在属性Yi的信息辅助下,评估突发公共卫生事件风险等级的不确定程度。

(3)针对每个属性Yi,计算相对于突发公共卫生事件样本集X的信息增益:

Gain=(X ,Yi)=H(X)-H(X|Yi)

信息增益Gain=(X,Yi)反映了在属性Yi的信息帮助下,判别突发公共卫生事件风险等级的不确定性的消除程度。

(4)选择信息增益最大的属性Yi作为根节点,根据该属性的取值将样本集X划分为n个样本子集。对于每个子集,如果该子集中所含事件样例均属于同一风险等级,则将其标记为叶节点;否则,重复上述过程。最终生成决策树。由于决策树的每一层都选择信息增益最大的属性作为判别属性,因此构建的决策树模型能够用最少的分层描述突发公共卫生事件属性与风险等级之间的规律。

每一条从根节点到叶节点的路径可转换为一条风险评估规则,故叶节点数即为突发公共卫生事件风险评估的规则数,叶节点的类型代表了风险评估的结果。

摘要：目的 探讨运用决策树模型进行突发公共卫生事件风险评估的技术和方法。方法 根据风险评估的结果将突发公共卫生事件划分为三个等级:高风险、中等风险、低风险。以某地区历史上已经发生的突发公共卫生事件为样本集,收集样本集中各个突发公共卫生事件的相关属性值及风险等级等信息,运用香农信息论中关于信息熵的理论,采取ID3算法,以各个属性为研究对象,以信息增益作为选择评价属性的衡量标准,逐层选择信息增益最大的属性作为节点(根节点或子节点),以某一树枝子集中包含的突发公共卫生事件是否为同一等级作为判断叶节点的标准,构建基于突发公共卫生事件属性进行风险评估的卫生应急风险决策树模型。结果 卫生应急风险决策树模型为突发公共卫生事件风险评估提供了评估规则,叶节点数代表了风险评估的规则数。结论 卫生应急风险决策树模型能够用较少的关键属性快速、准确地判断事件的风险等级,为实施突发公共卫生事件风险的快速评估提供技术支持。

数据挖掘中的决策树技术及其应用 第2篇

数据挖掘中的决策树技术及其应用

数据挖掘作为一种发现大量数据中潜在信息的.数据分析方法和技术,已经成为相关各界关注的热点.其中,决策树技术以其出色的数据分析效率、直观易懂的结果展示等特点,倍受广大用户的青睐.文章首先对决策树技术进行较为详尽的探讨,然后利用SAS/EM工具,对该技术在客户关系管理中的应用进行了初步尝试.

作 者：中国人民大学统计学系数据挖掘中心 作者单位：中国人民大学,统计学系,北京,100872刊 名：统计与信息论坛 CSSCI英文刊名：STATISTICS & INFORMATION TRIBUNE年，卷(期)：17(2)分类号：C8关键词：统计 数据挖掘 决策树 SAS/EM

决策树算法在银行信用评估中的研究 第3篇

1 决策树

决策树算法是数据挖掘技术的主流和核心, 它将大量的信息尽行了目标分类, 并找出了一些有价值的信息, 常用于预测的模型应用中。最早最有影响的决策树方法是由Quiulan研制的ID3算法。

ID3算法, 其基本原理是:将一棵决策树看作成为一个信息源, 利用信息增益, 寻找具有最大信息量的字段 (或者称之为属性) , 从而建立一个决策树节点, 再找出信息量最大的字段建立树分支;然后在每个分支的下层继续重复建立的过程, 由此就建立了决策树。对其分类时由树根开始判断, 对该对象的属性逐个判断属性值, 并顺分枝继续走, 直到叶节点, 此节点类就是该对象的类。实际应用中, 这即是需求预测的有用信息。

2 决策算法

ID3算法和C4.5算法都是决策树算法中的经典, C4.5是ID3的改进, 它继承了ID3的优点, 分类准确速度也更快, 在对于连续型属性的处理上, C4.5更为突出。如存在连续型描述性, 首先把这些连续型属性离散化。

以某银行客户信息库为例, 取一小部分数据生成决策树, 并研究其对信用评估库的应用。如表1所示, 现抽取25条信息进行生成决策树。

决策树的生成过程和树节点的选择过程相同:

⑴寻找具有最大信息量的字段属性作为根节点;

⑵选择学历属性作为树的根节点, 因为熵增益率最大;

⑶利用该样本子集, 重复 (1) 、 (2) 两步, 对分支子集依旧选择增益率最大的属性作为子节点, 直到分类到叶子为止。

3 简化的决策树

很多分类规则都有同一个问题那就是拟合度过高。训练集生成决策树分类的结果很好, 但用它来对新数据集进行分类并不理想。因此需要对初始决策树简化修正, 剪枝后的新决策树尽管可能会使训练集分类的误判率增大, 但却能减少新数据集分类的误判率。

决策树裁剪主要有2种方法。其一是错误率裁剪:把某个节点以下, 所有的树裁掉, 计算新树的错误率, 若减小就裁剪, 否则就恢复。其二是规则裁剪:把树的分支用IF语句描述, 以分类的好坏重新进行规则排序, 把后面的规则分支裁剪掉。这可以保证好分支不被裁掉, 只去掉了分类差的, 所以性能更好。

4 算法拟真

本文分别用ID3和C4.5形成两个决策树, 对C4.5算法使用了规则裁剪, 避免了过拟合。两种方法准确情况如图1所示。可以看出, 规则裁剪后准确度明显提高, 这在很大程度上避免了拟合度过高的问题。

5 结语

通过对信用评估数据的分析, 使用C4.5决策算法建立了银行个人贷款客户信用评估决策树模型。采用不同的测试集进行实验, 根据结果对最早生成的决策树进行裁剪, 有效地避免了拟合度过高的问题, 取得了理想的效果。

参考文献

[1]唐华松, 姚耀文.数据挖掘中决策树算法的探讨[J].计算机应用研究, 2001 (8) :18~20.

[2]张维东, 张凯, 等.利用决策树进行数据挖掘中的信息熵计算[J].计算机工程, 2001 (3) :71~72.

[3]Michael J A Berry, Gordon S L Inoff.数据挖掘技术[M].别荣芳, 尹静, 邓六爱译.北京:机械工业出版社, 2006:111~114.

[4]范明, 范宏建, 等, 译.MAR.数据挖掘导论[M].北京:人民邮电出版社, 2006:89~94.

[5]张冬艳.基于粗糙集合理论的决策树构造算法研究[D].合肥:合肥工业大学, 2006.

[6]苗夺谦, 王珏.基于粗糙集的多变量决策树的构造方法[J].软件学报, 1997, 8 (6) :425~429.

[7]PAWLA K Z.Rough Set Approach to Knowledge-Based De-cisionSupport[J].Institute of Computer Science Reports, 1995.

[8]PAWLA K Z, et al.Rough Sets[J].Communications of ACM, 1995.

重大事项决策后评估制度 第4篇

第一条 为加强对重大事项决策执行情况的跟踪、调查与反馈，促进决策的执行，提高重大事项决策水平，根据有关规定，结合工作实际，制定本制度。

第二条 重大事项决策后评估是指负责评估的单位，依据一定的标准和程序，运用科学、系统、规范的评价方法，对决策执行效果做出综合评定并提出决策延续、调整或终结意见建议的活动。

第三条 重大事项决策后评估工作应当遵循客观、公正、科学、实效的原则。

第四条 决策承办科室和局属单位（以下称承办单位）和局办公室具体负责并组织实施决策后评估工作。其他科室和有关单位应当积极配合。

第五条 下列事项应当作为后评估对象：

（一）公民、法人和其他组织提出意见集中、反映强烈的；

（二）决策执行效果不明显、存在问题较多的；

（三）重大政策、法律制度调整的；

（四）市委、市政府要求评估的；

（五）局负责同志或决策承办单位认为需要评估的。第六条 决策后评估应当围绕以下内容开展：

（一）决策的执行结果与制定目的是否相吻合；

（二）决策执行的成本、效益分析；

（三）决策执行中带来的负面因素；

（四）决策执行中被执行对象的接受程度；

（五）决策执行情况与全市畜牧业和农村经济发展方向的符合程度；

（六）决策执行带来的近期效益和长远影响；

（七）主要经验、教训、对策和建议等。第七条 决策后评估的准备工作包括：

（一）确定后评估对象；

（二）确定合适的后评估机构、人员；

（三）制定后评估方案，包括目的、标准、方法和经费。

（四）后评估方案报局分管负责同志批准。

第八条

承办单位会同局办公室应当成立后评估小组。后评估小组人员应当不少于3人。除承办单位、局办公室外，可从其他单位抽调人员或邀请相关专家参与。

根据需要，承办单位会同局办公室可以委托科研机构、高等院校、社会团体等第三方开展决策后评估。

第九条 决策后评估可以采取召开座谈会、督查督办、问卷调查、个体访谈、统计分析等方式进行，具体可以根据决策事项的性质、特点，选择一种或多种方法。

第十条 重大事项决策后评估工作应当根据实际，合理确定评估时间、任务安排。

第十一条 决策后评估小组或第三方完成评估后，应当提交决策后评估报告。决策后评估报告应当包括：对决策制定与执行情况的总体评价，对决策效益的分析，对决策延续、调整或终结的意见、建议等内容。

第十二条 决策后评估报告应当报局分管负责同志和主要负责同志审阅。按照决策程序集体研究决策后评估报告，应当形成对决策继续实施、调整或废止的决定并向社会公开。

决策树评估 第5篇

这一理念同样适用于新型信息技术[2]。随着新型信息技术的发展和应用,信息安全正逐步从技术层面扩展到技术与管理的相互融合。经过实践不断验证的虚拟化技术正体现了这种融合的趋势。虚拟化后的资源也同样面临着风险管控和安全评估。

安全评估属于信息安全风险管控的范畴。部署需要一个过程,评估也应该是一个开放的动态过程,如何从海量的信息中,快速、准确地抽取有用的信息,也是网络信息安全评估的关键。这一需求与数据挖掘中最优决策树的思想相一致,而这类研究越来越多地被应用于信息安全领域[3]。文献[4]阐述了在大数据背景下的系统评测基准,针对安全攸关系统提出了一种安全检测模型。网络安全包含预测、反应、防范和恢复[5],评估又是预测中最为重要的。

1 需求分析及评估模型

1.1 需求分析

空管信息网络具有分散性、即时性等特点。如何更加快速、客观地对空管信息网络安全进行评估,特别是在安全评估过程中能结合空管自身的特点,探索一种动态高效且更能突出安全关切的评估算法,值得我们深入研究。与其想如何快速准确地获取对空管信息网络相对有用的安全信息,不如转换角度考虑如何快速准确地剔除对其相对无用的信息,剩下的就是对安全最有价值的信息。这样既可突显重要的安全风险,又与数据挖掘中决策树的思想一致。

1.2 安全评估模型

空管信息网络的安全评估策略及模型均来源对空管安全需求的客观分析,安全评估模型如图1所示。

部署时间和费用决定了安全耗费值,而信誉度单独列出来则反映了空管人对信息网络安全风险的高度重视。信誉度量化后则为安全信誉值,时间权和费用权体现的是安全耗费内部对部署时间和费用的权重比,信誉权和耗费权则是总体上对风险耗费的关注程度。显然,由于空管的自身特点,对风险的关注程度要高于对耗费的关注程度,即信誉权会较高。如果特征值是一个动态变化的过程,那么基于它们建立的评估模型也会具有学习机制[6]。随着评估过程的不断进行,空管信息网络的信誉体系随之就建立好了,这些对于信息网络系统的规划决策也会起到重要的参考作用。模型中的各权值包含了空管多属性评估、决策问题的偏好信息[7]。

2 安全评估策略及目标函数

2.1 安全评估策略与最优决策树

在民航一些重要部件如飞机发动机、着落雷达控制系统[7]故障的预测和排除中也常用到最优决策树的思想。在一些涉及安全的领域,运用最优决策树的思想,对系统进行安全性评估越来越受到重视[8]。决策不仅是个评估的过程,也涉及评估后的规划。最优决策树因其高效性在数据挖掘中越来越受到重视,这一优点正是空管信息网络的安全评估所需要的。基于此,本文探讨了安全评估策略及方法。

将空管信息网络系统中的所有节点进行抽象,每个节点包含信誉度、部署时间、部署费用3个维度。所有节点将构成一棵树,整棵树包含了经过量化所有的评估结果,这是安全评估的解空间。于是,搜索该树即等同于进行动态评估。

搜索树需要从设定的3个维度来设置约束,每个约束就像是一把剪刀,将会使一些不符合条件的子树淘汰出局。本文设置了4把剪刀:剪刀1是节点的分层约束,剪刀2是部署时间约束,剪刀3是部署费用约束,剪刀4为安全耗费约束。4种评估约束依次对网络节点树进行剪枝,对应的正是评估策略。

2.2 安全评估目标函数

安全评估目标函数是评估的核心。根据空管信息网络安全评估模型,安全耗费的计算公式如式(1)所示。该公式提取了安全部署时间DeploymentCost和安全部署费用DeployrmerntTime两大特征量,用来量化安全耗费SafetyConsume,式(1)中DeploymentCostWeigths为耗费权重值。

通过定义目标函数,本文给出了获得评估因子AssessmentFactor的计算公示如式(2)所示。其中,Credit为信誉度,SafetyConsume为安全耗费;CreditWeigths和ConsumeWeigths则分别为安全信誉度权重和安全耗费权重。

3 算法实现及分析

3.1 算法实现

有了信息网络安全评估函数,对安全评估也就有了一个度量。本文抽象出三大特征量,然后用数据结构中的三叉树及链表来实现一种以这三大特征量为依据的民航信息网络安全评估方法。三叉树由链表来实现。

本文在Visual Studio 2010平台上实现并运行了该算法。编程平台如图2所示。

3.2 算法分析

为便于进行算法分析,本文设置节点为12个,节点ID从1到12。每个节点实际上是空管信息网络中各节点的抽象,它们构成了一棵待安全评估的三叉树。在主函数中首先利用初始化函数生成这棵树,然后调用ATM＿SafetyAssessment ()进行动态评估。显然,信誉度反应安全风险的程度,信誉度越高,安全风险越低。

条件1:设置安全信誉度权重为最高值,安全耗费权重为一个非常低的值。Weigths[2]={1,0.06},其中Weigths[0]为信誉权重,Weigths[1]为安全耗费权重。DeploymentCostWeigths[2]={5,3},12个节点的信誉度依次为{0.62,0.37,0.71,0.28,0.45,0.33,0.87,0.65,0.66,0.85,0.79,0.96}。

条件2:安全信誉度权重,安全耗费权重及信誉度均改变。设置Weigths[2]={0.99,0.29},其中Weigths[0]为信誉权重,Weigths[1]为安全耗费权重。DeploymentCostWeigths[2]={5,3},1 2个节点的信誉度依次为{0.65,0.40,0.74,0.31,0.48,0.36,0.90,0.68,0.69,0.88,0.82,0.99}。

条件3:在条件2的基础上继续降低安全耗费权重,同时提高节点10的信誉度,降低节点1 1的信誉度。设置Weigths[2]={0.99,0.09}。DeploymentCostW-eigths[2]={5,3},12个节点的信誉度依次为{0.65,0.40,0.74,0.31,0.48,0.36,0.90,0.68,0.69,1.00,0.38,0.99}。

调用ATM＿SafetyAssessment ()进行动态评估后,可得到3个条件下对应的安全评估因子(见表1)。

由表1可绘制其对应的评估因子图(如图3所示):横轴为Safety Path ID,纵轴为安全评估因子。条件1对应Curve 1,条件2对应Curve 2,条件3对应Curve 3。

在图3中对比Curve 1和Curve 2可以发现,Weigths的改变对评估因子的影响较大,特别是信誉权重,这也正体现了空管对风险管控的重视。对比Curve1、Curve 1和Curve 3发现,当权重和各节点的信誉度发生改变时,评估因子也会随之改变,评估因子的变化趋势也会有明显的变化。实际上权重也好,信誉度也好,这些都是一个动态开放的量,它们会随着学习过程的深入而改变,趋向于更加精准。

算法运行的过程也验证了其高效、快速的特点,节点越多,这一优势愈加明显。其实,这与本文采用了数据挖掘中的剔除策略有关,剔除相对不重要的节点,凸显其重要节点,这些节点既可以是安全评估因子最高的,也可以是最低的。总之,风险管控建立在节点信誉体系的建设上。

4 结语

传统信息系统与新型信息系统都应具有系统工程理念,都需要进行安全评估。通过抽象网络节点,本文以实际需求为导向的多个维度建模有助于找到一种更适合空管信息网络的安全评估方法,而最优决策树的动态性和高效性使得这种方法在空管信息网络安全评估策略上有着明显的优势。

本文通过为主要参数设置一些具体的值,在Visual Studio 2010平台上运行该算法,仿真结果证明了该算法的有效性。整理运行所得的数据,用MATLAB 7.0绘制出相应的对比图,直观地验证了本文的结论。信誉度的引入体现了“空管人”对安全的重视,更凸显对“安全第一”这一观念的贯彻。本文希望通过这种安全评估方法的探讨,能对空管信息网络信誉体系建设的研究和应用有所帮助,从而能更好、更高效地提高空管信息网络安全保障能力。

摘要：安全评估属于信息安全风险管控的范畴。高效而客观的安全评估方法,对于发现空管信息网络的薄弱节点,进行及时防护和科学规划都具有重要的指导意义,因此安全评估越来越受到重视。文章利用数据挖掘中决策树的思想来制定安全评估策略,从信誉度、安全部署时间、安全部署费用多个维度对空管信息网络安全进行抽象建模。以该模型为基础探讨了一种基于最优决策树的空管信息网络安全评估方法,并用C语言进行了实现。文章在Visual Studio 2010平台上运行并验证了该算法的有效性,结果表明,该方法能较好地满足空管对信息网络安全评估的要求。

关键词：数据挖掘,安全评估,信息网络,风险评估

参考文献

[1]斯坦普.信息安全原理与实践[M].北京:清华大学出版社,2013.

[2]姚宏宇,田溯宁.云计算:大数据时代的系统工程[M].北京:电子工业出版社,2015.

[3]金澈清,钱卫宁,周敏奇,等.数据管理系统评测基准:从传统数据库到新兴大数据[J].计算机学报,2015,38(1):18-34.

[4]杜德慧,程贝,刘静.面向安全攸关系统中小概率事件的统计模型检测[J].软件学报,2015,26(2):305-320.

[5]董会敏.银行网络信息安全的实现[D].上海:华东师范大学,2011.

[6]陈蔼祥,姜云飞,柴啸龙,等.面向结构的基于学习的规划方法[J].软件学报,2014,25(8):1743-1760.

[7]陶志,卞文静.基于先验概率优势关系的粗糙决策分析模型[J].中国民航大学学报,2013,31(4):60-64.

决策树评估 第6篇

关键词：懒惰式决策树,朴素贝叶斯,半懒惰式决策树算机

0引言

分类是数据挖掘和机器学习的一种非常重要的方法, 可以用来提取描述重要数据类的模型。分类是在已有数据集合的基础上学会一个分类函数或构造出一个分类模型 (即通常所说的分类器) 。该函数或模型能够给由属性集描述的未分类的实例指派最适合的类标签, 从而可以应用于数据分类和预测[1,2]。机器学习、数据挖掘、专家系统、统计学和神经生物学方面的研究者已经提出了许多的分类方法和技术, 例如, 懒惰式决策树、朴素贝叶斯方法[1,2]、贝叶斯网络[1,2]、双层贝叶斯[3]、决策树[4]、决策表[5]、K-最邻近以及支持向量机等等。众所周知, 没有一种分类方法在所有领域都是有效的。懒惰式决策树具有较高分类精确度[6], 决策树具有良好的可解释性[4], 从而使得这两种分类器模型逐渐成为机器学习和数据挖掘领域的研究热点。

本文仔细地分析了决策树和懒惰式决策树这两种分类模型的分类原则, 结合了这两者的长处, 从一种新的角度提出了一种新的分类模型Semi-LDtree。它生成的决策树的节点, 如普通决策树一样, 包含单变量分裂, 但是叶子节点相当于一个懒惰式决策树分类器。本文给出了Semi-LDtree分类模型的算法, 并实验比较了Semi-LDtree、weka包下的J48、懒惰式决策树和贝叶斯这四种分类器的分类精确度。

1决策树分类模型

分类方法中最为典型的是基于决策树的分类方法。它从训练集合中构造出决策树, 是一种有指导的学习方法。决策树的叶节点是类名, 中间节点是带有分支的属性, 该分支对应属性的某一可能值。最为典型的决策树学习系统是ID3, 它采用自顶向下分而治之的策略, 能保证构造出一棵简单的树。算法C4.5和C5.0都是ID3的扩展, 它们将分类领域从枚举型属性扩展到数值型属性[4]。

构建决策树最重要的是如何选择分裂属性。迄今为止已经提出了许多选择分裂属性的标准, 例如, 标准熵增益和增益比率, Gini索引, Kolmogorov-Smirnov度量, 基于Goodman-Kruskal关联索引等等。本文采用的是一种基于NBtree的思想[7]。对每一个候选属性划分当前节点的数据集合, 计算朴素贝叶斯分类器在分裂后的数据集合上的交叉验证精确度值的权重和。取精确度最大的属性作为最佳的分裂属性。

2懒惰式决策树与朴素贝叶斯的比较

朴素贝叶斯分类器是一种简单而有效的概率分类方法, 但是其“属性独立性假设”在现实世界中大多数数据集合上明显不成立, 从而使其分类性能受到限制;而懒惰式决策树分类器采用决策树思想和懒惰式分类思想, 从概念上为每一个待分类实例建立一棵“最优”的树, 不受属性独立性假设的约束, 在小一些的数据集合上, 其分类精确度十分高。大量实验表明:懒惰式决策树分类器在大多数数据集合上所得的分类精确度要比朴素贝叶斯分类器高, 但是朴素贝叶斯分类器在大多数据集合上的分类速度要比懒惰式决策树分类器快。

因此本文利用懒惰式决策树分类器代替仅仅预测一个简单类标签的普通决策树的叶子节点来建立半懒惰式决策树分类器:Semi-LDtree分类器。同时利用朴素贝叶斯分类器分类速度快的优点计算当前节点分裂后分类精确度的悲观估计, 来选择最佳的分裂属性。

3Semi-LDtree分类模型及算法

Semi-LDtree分类模型产生的分类器是一棵决策树, 它与普通决策树的不同之处在于它的叶子节点是一个懒惰式决策树。在训练阶段, 它利用训练实例集合递归迭代生成一棵决策树。当给定一个测试实例, 它从决策树根节点被分到一个叶节点时, 懒惰决策树开始学习, 学习完后给出了这个测试实例的类标签。

Semi-LDtree分类模型充分吸取了懒惰决策树在小的数据集合上分类精确度高这一优点, 同时保留了决策树良好的可解释性, 提高了分类速度和精确度。

本文提出的Semi-LDtree算法如下所示。这个算法类似于经典的C4.5算法, 采用的都是分而治之自顶向下迭代递归的策略。特别之处在于叶子节点是一个分类精确度高的懒惰决策树, 而不是仅仅预测一个简单类标的节点。

对于数值连续型属性的阈值的产生, 本文仍沿用J48提出的方法。首先将数据集合按照数值连续型属性排序选择多个分裂点。对每一个分裂点计算信息增益, 选择信息增益最大的分裂点作为阈值点[4]。

如何选择最佳的分裂属性, 本文采用的是对每一个候选属性划分当前节点的数据集合, 计算朴素贝叶斯分类器在分裂后的数据集合上的交叉验证精确度值的权重和, 记为AccW。取精确度最大的属性作为最佳的分裂属性[7]。

对于什么时候停止决策树的生长而生成相当于懒惰式决策树的叶子节点, 本文采用的是在当前节点上计算朴素贝叶斯分类器的交叉验证精确度 (记为Acc) , 当这个精确度大于给定的限制值, 或者这个精确度明显大于用属性分裂后的权重和精确度, 或者找不到最佳的分裂属性时, 停止决策树的生长, 否则继续在此节点上分裂。

Semi-LDtree算法:

输入:带有类标的训练数据集合;

输出:叶子节点是懒惰式决策树分类器的决策树。

1) 计算当前节点的Acc值;

2) 计算每个候选属性的AccW值, 选择一个AccW值最大的属性作为最佳的分裂属性;

3) 如果Acc值明显大于MAX (AccW) 值, 或者Acc值大于一个给定值, 或者当前节点的实例数目小于一个给定的值时, 生成叶子节点, 调用懒惰式决策树。否则按最佳属性分裂生成子节点。在每个子节点上递归建树。

4实验数据及实验结果分析

为了评估Semi-LDtree算法, 本文采用的实验数据集合都来自UCI的数据文件[8]。在所有的数据集合上评估分类器的性能所采用的方法都是十倍交叉验证的方法。在训练数据上建树的过程中本文删掉了那些类值缺省的训练实例。

实验的主要目的是对Semi-LDtree、J48、懒惰式决策树和贝叶斯分类器在每个数据集合上的分类精确度进行了比较。每个分类器的分类精确度是在测试集合上成功预测的实例占总实例的百分比, 采用的10重交叉验证估计分类器的精确度。每一个数据集合被分成十个没有交叉数据的子集, 所有子集的大小大致相同。分类器训练和测试共十次;每一次, 分类器使用去除一个子集的剩余数据作为训练集, 然后在被去除的子集上进行测试。把所有得到的精确度的平均值作为评估精确度, 即10重交叉验证精确度。在运行J48, lazytree和Naïve bayes三种分类器时候, 均采用的是默认的参数。实验结果如表1所示。

表1列出了Semi-LDtree, J48, lazytree和Naïve bayes这四种分类器在23个实验数据上分类精确度的对比。从实验结果可以看出, Semi-LDtree在大部分实验数据集上取得了最好的分类性能。在23个实验数据集合上, Semi-LDtree的平均分类精确度为82.5220;J48的平均分类精确度为81.5136;lazytree的平均分类精确度为81.4582;Naïve bayes的平均分类精确度为78.0976。对audio, lung-cancer, anneal, ttt数据集合, Semi-LDtree的分类精确度均比J48, lazytree和Naïve bayes分类器的精确度高。对audio, zoo, anneal, echocardiogram, weather, sonar, ttt数据集合上, Semi-LDtree的分类精确度均比J48高出许多。对于所有的数据集合, 因为Semi-LDtree分类器如果不构建决策树就相当于一个lazytree分类器, 所以它的分类精确度不会比lazytree分类器低。在audio, anneal, ttt, german, solarflare-m五个大数据集合上, Semi-LDtree体现了决策树的优势, 它的分类精确度比lazytree分类器的精确度高。

Semi-LDtree产生的决策树的节点数目明显少于J48产生的决策树的节点数目。例如, 对于数据集合anneal, J48生成了78个节点, 分类精确度为90.9800, 而Semi-LDtree只生成7个节点, 精确度却达到了92.5390;对于数据集合ttt, J48生成了142个节点, 分类精确度为85.0731, 而Semi-LDtree生成39个节点, 精确度却达到了92.5887。因此, 它比J48具有更好的可解释性。但是, Semi-LDtree的每个叶子节点的复杂度比J48要高。

在本文的实验中判断停止决策树生长的条件时, 精确度的界限值是0.95, 分裂前后精确度值的差本文采用-0.05, 叶子节点最少的实例数目是30。实际上, 这三个值的取值的变动均会引起Semi-LDtree分类器分类精确度的上下浮动。

5结论

懒惰式决策树分类模型从概念上为每一个测试实例建立一棵“最优”的决策树, 所以分类精确度高。但是, 在大的数据集合上, 它的分类速度慢、内存消耗大、易被噪声误导等缺点, 影响了它的分类性能。决策树分类模型, Semi-LDtree, 它生成的决策树的节点, 如普通决策树一样, 但是叶子节点相当于一个懒惰式决策树分类器。这种分类模型同时保留了普通决策树良好的可解释性和懒惰式决策树在小的数据集合上分类精确度高这两种优点。实验结果表明了它提高了分类速度和分类精确度, 在某些分类任务上它的分类性能经常性地胜过两者, 特别是在大的数据集合上。

在Semi-LDtree的实现中, 最佳分裂属性的选择标准是非常重要的。本文中采用的方法是比较每一个候选属性的交叉验证精确度值的大小来选择最佳的分类属性, 是否还有其它更好的分类标准, 是下一步研究的一个内容。另外, 在本文实验中判断停止决策树生长的条件时, 选用了三个参数。实际上, 对于不同的数据集合, 这三个值的取定也不同。是否有一个更好的判断停止决策树生长的标准, 这也是需要进一步研究的问题。

参考文献

[1]Han J, Kamber M.Data Mining Concepts and Techniques[M].San Francisco:Morgan Kaufmann Publishers, 2001:185-219.

[2]Mitchell TM.Machine Learning[M].McGraw Hill, 1997:112-140.

[3]石洪波, 王志海, 黄厚宽.一种限定性的双层贝叶斯分类模型[J].软件学报, 2004, 15 (2) :193-199.

[4]Simovici Dan A, Jaroszewicz Szymon.A Metric Approach to Building Decision Trees Based on Goodman-Kruskal Association Index[C].PA-KDD, 2004:181-190.

[5]Witten IH, Frank E.Data Mining:Practical Machine Learning Tools and Techniques with Java Implementations[M].Seattle:Morgan Kauf-mann, 2000.

[6]Friedman JH, Kohavi Ron, Yeogirl Yun.Lazy Decision Trees[C].AAAI-96, 1996:717-724.

[7]Kohavi R.Scaling up the accuracy of Na ve-Bayes classifiers:A deci-sion-tree Hybrid[C].In:Simoudis E, Han J, Fayyad UM, eds.Proc.of the2Int l Conf.on Knowledge Discovery and Data Mining.Menlo Park:AAAI Press, 1996:202-207.

决策树算法综述 第7篇

随着数据库技术的发展,人们搜集数据的能力大幅度提高,可以非常方便地获取和存储大量的数据,但却无法从这些数据中发现潜在的规律,无法预测未来的发展趋势。如何有效的利用这些数据为人类服务,已成为人们研究的热点之一。数据挖掘技术能自动和智能地从大型数据库中提取隐含的、未知的信息和知识［１－３］。

分类是数据挖掘的重要分支,可用于提取、描述重要数据类的模型或预测未来的数据趋势［４］。通过分类和预测,能够对各个行业提供良好的决策支持,对整个社会的发展产生重要而深远的影响［５］。决策树算法是数据挖掘分类算法中常见的一种方法。它以树状结构表现,叶子结点代表一个结论,内部结点描述一个属性,从上到下的一条路径,确定一条分类规则。与其它技术相比,决策树算法结构简单直观,容易理解,有较高的分类精度,在数据挖掘、机器学习、人工智能等领域等都有广泛的应用。所以研究并提出高效、适用的决策树算法对整个社会的发展意义重大。

本文对几种经典的决策树分类算法进行了分析,指出不同算法的优点和不足,并讨论了决策树算法今后的研究方向。

1几种决策树分类算法介绍

决策树算法是一种逼近离散值目标函数的方法,它将分类规则以树状结构表示［６］。

1.1 ID3算法

机器学习研究者J.Ross Quinlan在1986年把Shan- non的信息论引入到了决策树算法中,提出了ID3算法［７］。ID3算法的概念如下［８－９］:

设样本集E共有C类样本训练集,每类样本数为pｉ, i=1,2,...C 。如果以属性A作为测试属性,属性A的v个不同的值为{v１,v２,...,vｖ},可以用属性A将E划分成v个子集{E１,E２,...,Eｖ},假定Eｉ中含有第j类样本的个数为pｉｊ,j=1,2,...C ,那么子集Eｉ的熵为［１０］:

属性A的信息熵为:

将Infor_Entropy(Eｉ)代入公式(2)后可得:

一棵决策树对一样例作出正确类别判断所需的信息为:

信息增益:

ID3算法存在着属性偏向、对噪声敏感等问题[10,11]。

1983年,T.Niblett和A.Patterson在ID3算法的基础上提出了ACLS Algorithm。该算法可以使属性取任意的整数值,这扩大了决策树算法的应用范围[12]。

1984年,I.Kononenko、E.Roskar和I.Bratko在ID3算法的基础上提出了ASSISTANT Algorithm,它允许类别的取值之间有交集［１２］。

1984年,A.Hart提出了Chi—Square统计算法,该算法采用了一种基于属性与类别关联程度的统计量［１３］。

L.Breiman、C.Ttone、R.Olshen和J.Freidman在1984年提出了决策树剪枝概念,极大地改善了决策树的性能［１４］。

1986年,T.Niblett提出了Minimum-Error Pruning Algorithm［１５］。1987年,J.R.Quinlan提出了Reduced Er- ror Pruning Algorithm［１６］。1987年,J.Mingers提出了Critical Value Pruning Algorithm［１７］。1992年,K.Kira和L.Rendell提出了RELIEF Algorithm,该算法是决策树算法发展史上一座里程碑［１８］。

1.2 C4.5算法

在ID3算法的基础上,Quinlan在1993年又提出了一种改进算法,即C4.5算法［１９］。

信息增益率计算如下［１０］:

C4.5算法克服了ID3算法属性偏向的问题,增加了对连续属性的处理,通过剪枝,在一定程度上避免了“过度适合”现象［２０］。但是该算法将连续属性离散化时,需要遍历该属性的所有值,降低了效率;要求训练样本集驻留在内存,不适合处理大规模数据集。

1.3 CART算法

CART算法是描述给定预测向量X 、条件分布变量Y的一个灵活方法,最早是由Breman等人提出,已经在许多领域得到了应用。

CART算法可以处理无序的数据。采用基尼系数作为测试属性的选择标准。

基尼系数计算如下:

其中|T|,|T1|,|T2|分别是样本集T、T1和T2中的样本个数。

其中pｉ是类别j在T中出现的概率。

CART算法生成的决策树精确度较高,但是当其生成的决策树复杂度超过一定程度后,随着复杂度的提高,分类精确度会降低。因此,用该算法建立的决策树不宜太复杂［２０］。

1.4 SLIQ算法

决策树分类算法研究一直朝着处理大数据集的方向进行,但大部分方法在减少了运算时间的同时也降低了算法的精度。SLIQ的分类精度与其它决策树算法不相上下,但其执行的速度比其它决策树算法快。SLIQ算法对训练样本集的样本数量以及属性的数量没有限制。SLIQ提高了分类的精确度［２１］。

SLIQ算法能够处理大规模的训练样本集,具有较好的伸缩性;执行速度快而且能生成较小的二叉决策树; SLIQ算法允许多个处理器同时处理属性表,从而实现了并行性［２１］。但是SLIQ算法依然不能摆脱主存容量的限制。

1.5 SPRINT算法

SLIQ算法要求类表驻留内存,当训练集大到类表放不进内存时,SLIQ算法就无法执行。为此,IBM研究人员提出SPRINT算法,它处理速度快、不受内存的限制。

SPRINT算法可以处理超大规模训练样本集,数据样本集数量越大,SPRINT的执行效率越高,并且可伸缩性更好。但是,SPRINT算法存在着一些缺陷:在SLIQ的类表可以存进内存时,SPRINT算法的执行速度比SLIQ算法慢;该算法由于使用了属性表,增加了存储代价。

1.6 PUBLIC算法

上述含有剪枝的算法都是分成两步进行,即先建树再剪枝。然而,这种方法将已生成的分枝再剪去是一种效率较低的重复劳动,于是Rajeev RaSto等人在2000年提出了PUBLIC算法(Pruning and Building Integrated in Clas- sification)［２３］。由于PUBLIC算法是对尚未完全生成的决策树进行剪枝,因而提高了效率。近几年,模糊决策树也得到了蓬勃发展［２４－２５］。

上述算法未考虑属性间的相关性。因此,后来人们又提出了分层回归算法、约束分层归纳算法和功能树算法。

分层回归算法、约束分层归纳算法和功能树算法都是基于多分类器组合的决策树算法,它们对属性间可能存在的相关性进行了部分实验和研究,但是这些研究并没有从总体上阐述属性间的相关性是如何影响决策树性能的［２６－２８］。

基于粗糙集的决策树方法也是典型的决策树算法。 文献[29]提出了基于粗糙集的优化算法,并且分析了各自的优缺点。文献[30]通过设计特殊的Hashtable减少了每次读取I/O的开销,这种方法很大程度上降低了时间复杂度,但是并没有考虑到精确度的改进,而且由于数据量大时,哈希表也会很占内存。文献[31]提出了基于极端学习树的模型,也是能够降低时间复杂度,但是不易实现并行化计算和设计。

1.7经典决策树算法比较

基于决策树的分类算法自提出至今,种类不下几十种。各种算法在执行速度、可扩展性、输出结果的可理解性、分类预测的准确性等方面各有所长。表1是几种经典的决策树算法比较［３２］。

2结论及展望

决策树虽然在理论研究和实际应用方面都取得了很多进展,但还存在不少问题亟待解决,这正是今后的研究方向,主要有:

(1)实验证明:要找到最优的决策树是NP问题［３３］, 必须寻找更好的方法,将决策树技术和其它新兴技术相结合,取长补短,提高决策树的抗噪声能力和准确性。

(2)研究属性间的相关性对决策树产生的影响,以及如何利用或者消除这些相关性来构造决策树,值得关注。

(3)决策树技术中如何处理时间复杂度和分类准确性之间的矛盾,一直以来都是一个令人感兴趣的问题。怎样在提高准确度的前提下降低时间复杂度,是今后研究的一个重点及难点。

决策树算法及其应用 第8篇

1 决策树生产过程

决策树进行传统的数据分类包含两个步骤:

第一步:利用训练集进行创建模型阶段, 找到映射函数表示模型, 从指定的训练集中获取知识, 这是一个学习的过程。

第二步:利用生成的决策树预测数据的类别, 使用上一步训练完成的函数模型进行预测, 对输入的记录, 从根结点开始一直到叶结点进行测试属性值, 然后对数据集中的每一类数据进行描述, 生成分类规则。

具体工作过程如图1所示。

2 决策树算法的优点

(1) 学习该算法, 不要求使用者的知识背景丰厚, 就能够在训练事例中用属性结论的方式来进行表达。

(2) 训练集数据量较大的情况下, 决策树模型效率较高。

(3) 决策树是一种树状结构, 它是最简单直观的, 因此在分类模型中经常被应用的方法之一, 通过从根结点一直到达叶子结点的路径转换, 最终能够生成分类规则以IFTHEN形式进行表示, 这样更能够让人容易理解。

(4) 决策树方法对于分类而言, 精确度较高。

3 决策树的评价指标

(1) 准确的预测性。决策人员最关心的就是预测的准确性, 分类模型具有对未知新数据进行准确预测的能力、也能对未知的数据类的预测能力。

(2) 描述的简洁性.分类发现模型对问题的描述方式提出的分类发现模型只有越简洁越容易理解才能够方便决策人员使用。

(3) 计算复杂性。在数据挖掘的过程中, 操作的数据对象是海量信息的数据库, 所以空间和时间的复杂性将直接影响模型的计算成本, 计算的复杂度是在海量数据库中具体实现的细节决定的。

(4) 处理规模性。

(5) 模型强健性。

4 决策树算法在学生就业工作中应用

4.1 设计方案

利用决策树C4.5算法分析哪些因素对学生就业有影响。

选取计算机系10届、11届、12届计算机科学与技术专业学生为研究对象, 学生人数为200人。

4.2 数据采集

(1) 学生基本信息库。数据结构如下:姓名、学号、性别、班级、籍贯。

(2) 学生就业信息库。内容包括学号、姓名、参加公司培训、是否优质就业 (工资在3000元以上为优质就业) 等。

(3) 成绩表。成绩数据库中包括了学生的课程总成绩平均分和综合测评成绩平均分, 这个数据库由教师在教学过程中和辅导员对学生表现评定产生。

4.3 数据项处理

数据集成。根据给出的数据文件, 将三个数据源的数据利用数据库技术生成学生就业分析表。

数据清理。生成学生就业分析表工作要进行填补遗漏的数据值。

数据转换。数据转换中离散值属性要占大多数, 连续值属性并不多, 只有个别的需进行离散化处理。现将上述综合成绩属性的属性值化分为4类:成绩从0~60分属于“及格”, 60~80分属于“中”, 80~90分属于“良好”, 90~100分属于“优”, 性别两类:男或女;参加公司培训分为两类:是或否;就业分为三类:工资在3000元以上为优质就业, 2000-3000元为普通就业, 2000元以下为一般就业, 无工作为待就业。增加参加公司培训可以判断优质就业的可信度。

数据消减。由于学生基本信息表和学生就业信息表中的属性比较多, 笔者为了便于分类挖掘, 将籍贯、班级这两个属性进行删除, 原因是这两个属性与就业相关性不大, 为了能够保护学生的隐私, 笔者将学生姓名属性也删除掉, 从而生成新的学生就业分析表与转换数据表。

参考文献

[1]郭佳, 陈春燕.数据挖掘技术在高校毕业生就业工作中的应用[J].中国科技信息, 2008, 14:67-69

决策树相关算法研究 第9篇

1 ID3算法和C4.5算法的比较

ID3算法是Quinlan于1993年提出的[1,2],它使用信息增益来选择分裂属性。ID3算法的根本问题是怎样选取树的每个节点的分裂属性。ID3算法[4]用“信息增益”去衡量给定的属性区分训练样例的能力。它在增长树的每一步都是使用信息增益标准从候选属性中选择属性。C4.5算法[5]是ID3算法的改进,它使用信息增益率来进行分裂属性的选择。

1.1 ID3算法信息增益与C4.5信息增益率的计算步骤1)ID3算法信息增益计算的步骤

步骤1.若一个记录集合T,根据类别属性的值被分成互相独立的类,则识别T的一个元素所属哪个类所需要的信息量为,其中的概率分布,即。

步骤2.先根据非类别属性X的值将T分成集合T1,T2Tn则确定T中的一个元素类的信息量可以通过确定Ti的加权平均值来得到,即Info(Ti)的加权平均值为:

步骤3.信息增益度是两个信息量之间的差值,其中一个信息量是需要确定的T的一个元素的信息量,另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量,信息增益度的公式为:

2)C4.5信息增益率的求解步骤

C4.5在ID3的基础上利用信息增益率来对分裂属性选择,步骤1、2、3同ID3。

步骤4.增加了属性X的信息熵。

步骤5.用信息增益去除属性X的信息熵,得到信息增益率。

1.2 ID3与C4.5数据结构[3,7]比较(见表1)

由于C4.5算法是ID3算法的改进,所以在C4.5计算增益率的结构体中增加Gain_ratio用于存储信息增益率。从表1比较可以看出ID3和C4.5的结构体基本上都是可以共用的。

1.3 ID3与C4.5的算法[4,8]比较(见表2)

ID3算法计算每个属性的信息增益,并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个结点,并以该结点的属性标记,对该属性的每个值创建一个分支据此划分样本。直到划分的样本属于同一类为止,输出其类别值作为分类结果(即叶子节点)。C4.5以ID3类似的方法选择分裂属性,只是在以信息增益率最高的作为分裂属性选择的标准。

基于上述分析,ID3树的构造过程是一种贪婪算法的思想,每次选择局部信息增益最高属性作为分裂属性,并不进行回溯。构造的树是多分枝的树,树的规模随训练样本的增加而扩大。C4.5可以在ID3的基础上,也就是在计算信息增益的函数中,根据信息增益率对要选择的分裂属性进行选择,这样其他部分仍可以使用ID3的模块,只需修改下标识符。C4.5还可在计算增益率之前,添加一个对连续值的划分模块,这样C4.5就可以对连续值属性进行处理。

2 利用气候训练集的计算实例

2.1 数据准备,

测试训练集(见表3)选取了50条数据进行测试分析。

2.2 ID3和C4.5的实例计算(根据表3数据)

1)ID3的信息增益计算

步骤1:类别C(运动)的信息熵计算

类别中u1=适合,u2=不适合,。

则:

步骤2:属性的条件熵的计算

属性V取“天气”,V1=晴(16),V2=多云(15),V3=雨(14),V4=阴(5)。

所以。

取值为晴的16个样本中有5个为合适和11个不合适,根据步骤2有:

同理:

阴

Info(v)的加权和如下:

同理:V取气温时:Info(C,V)=0.8785,V取湿度时:=0.6738,V取风时:=0.8904。

步骤3:属性V的信息增益

同理类似可得:Gain(气温)=0.0258,Gain(湿度)=0.2306,Gain(风)=0.014。

2)C4.5信息增益率计算

前三个步骤分别和ID3的步骤1、2、3相同。

步骤4:属性的信息熵V

由,则天气中:v1=晴(16),v2=多云(15),v3=雨(14),v4=阴(5),p(v1)=16/50,p(v2)=15/50 p(v3)=14/50p(v4)=5/50

则:

同理:Split_Info(气温)=1.4948 Split_Info(湿度)=0.9988 Split_Info(风)=0.971

步骤5:信息增益率

Gain_ratio(天气)=Gain(天气)/Split_info(天气)=0.1871

Gain_ratio(气温)=Gain(气温)/Split_info(气温)=0.0173

Gain_ratio(湿度)=Gain(湿度)/Split_info(湿度)=0.2309

Gain_ratio(风)=Gain(风)/Split_info(风)=0.0144

2.3 ID3和C4.5对属性取值个数较多的偏向比较

表5是通过表3中的数据计算出来的,其中ID3选择分裂属性为天气,C4.5选择分裂属性为湿度。表6是表4(表4和表3的数据仅有第二列不同,即天气那列,其余数据不变)中的数据计算出来的,ID3选择分裂属性为湿度,C4.5选择分裂属性为湿度。

由表5和表6可知在数据表3中第二列属性值个数为4,表4中的第二列属性值个数为2。ID3在表3的数据下选择分裂属性为天气,在表4的数据下选择分裂属性为湿度。但

C4.5一直选择的分裂属性为湿度,可以看到属性值个数变动对ID3中的属性选择的偏向影响较大(如0.3544与0.0389)。

2.3 根据ID3和C4.

5算法构造的树(根据表3数据)

由表8可知在左子树的风中有三个#,其中第二#个是因为其所有的记录都为一类,已完成分类,故也把它标记为已经选择过的。从#、#、#、1.000可以看到其他属性选择过后,剩下的最后一个属性对记录的信息增益为1,分类能力很强。以上两棵树(图1,图2)比较可以看出:C4.5构造的树的高度比ID3构造的树的得到的规则较多,其分类的准确性比ID3要高。例如在ID3中的规则”天气=’阴’”=>适合,”天气=多云”=>适合和我们的生活习惯相比较,决策因素太简单,也有些不符。而C4.5构造的决策规则要明显好于ID3,更准确些。

2.4 ID3和C4.5的特性比较(见表9)

表9为ID3和C4.5的特性比较。

3 结束语

通过对决策树上的ID3和C4.5的数据结构与算法描述算法比较,及利用训练数据集建树,可知:ID3算法的优点是使用了窗口的概念,以信息熵为选择分裂属性的标准,构建树的速度加快。C4.5除了ID3的优点外,增加了对连续属性值的离散化处理;缺失数据的处理;解决了ID3属性值偏向问题。

参考文献

[1]Dunham M H.数据挖掘教程[M].北京:清华大学出版社,2005.

[2]周爱华,申玉静.决策树技术在高校实验队伍评估中的应用[J].电脑知识与技术,2011,7(2):285-286.

[3]程龙,蔡远文.数据挖掘C4.5算法的编程设计与增量学习改[J].计算机技术与自动化,2009(4):83-87.

[4]李川.决策树分类算法_ID3算法及其讨论[J].软件导刊,2010(10):68-70.

[5]王桂琴.决策树算法研究及应用黄道[J].电脑应用技术,2008(72):1-7.

[6]路红梅.基于决策树的经典算法综述[J].宿州学院学报,2007,22(2):91-95.

[7]乔增伟.孙卫祥.C4.5算法的两点改进[J].江苏工业学院学报,2008,20(4)56-59.

[8]黄爱辉.决策树.C4.5算法的改进及应用[J].计算机技术,2009,9(1):35.