决策树算法研究及应用? 王桂芹黄道 华东理工大学实验十五楼206室 摘要:信息论是数据挖掘技术的重要指导理论之一,是决策树算法实现的理论依据。决 策树算法是一种逼近离散值目标函数的方法,其实质是在学习的基础上,得到分类规则。本文简要介绍了信息论的基本原理,重点阐述基于信息论的决策树算法,分析了它们目前 主要的代表理论以及存在的问题,并用具体的事例来验证。 关键词:决策树算法分类应用 Study and Application in Decision Tree Algorithm WANG Guiqin HUANG Dao College of Information Science and Engineering, East China University of Science and Technology Abstract:The information theory is one of the basic theories of Data Mining,and also is the theoretical foundation of the Decision Tree Algorithm.Decision Tree Algorithm is a method to approach the discrete-valued objective function.The essential of the method is to obtain a clas-sification rule on the basis of example-based learning.An example is used to sustain the theory. Keywords:Decision Tree; Algorithm; Classification; Application 1 引言 决策树分类算法起源于概念学习系统CLS(Concept Learning System,然后发展 到ID3
一种不均衡数据集的决策树改进算法 一、MCMO-Boost算法 设定训练样本Ai、类标号Bi，训练集P={（Ai，Bi）|Bi∈{true，false}}，i=1，2，…，total。如Bi=true则为少数类，如Bi=false则为多数类，设x为少数类样本的个数，y为多数类样本的个数，且xrmax，则转到步骤（6）。 （4）根据Dt分布从P中抽样的数据装入集合SET，创建若干单特征分类器并选择最适合的一个样本，用弱分类器验证集合P中的样本x，若判断失误，则装入“通过集合”M。 （5）对于通过集合中的任一数据样本x”，在S中找出同类近邻k，并选择任意y∈（1，k）个，依据synth=x”+rj×difj，j=1 to n对扩充x”样本记录，其中，rj是0～1之间的随机数；difj是x”与第j个近邻的矢量差。因此少数类样本扩充了n倍并且合并装入到SET中。 （6）征对SET中的数据，采用AdaBoost建立多层次级联分类器。 四、实验及分析 在实际应用中建立良好的客户离网趋势模型比较困难，离网趋势的变化程度受到各种主、客观因素的刺激。研究此类问题采用的数据挖掘方式从传统的单层次级别算法，发展到多层次多级别算法的组合，虽然多层次多级别算法设计了构建挖掘策略模型、验证测试数据的准确性，但在现实运用中总是无法解决数据的不均衡难题、很难生产出方便客户理解的策略模型。 以eclipse开发工具为依据，应用改进后的AdaBoost算法，在样本系统中进行测试实验。应用M-AdaBoost级联决策树算法，先使不均衡原始数据样本集进行均衡化处理，获得提升少数类后的样本，再将均衡后的数据样本集以7：3拆分为测试集和训练集；确认级联分类器的总体虚警率F和每层次可接受的最大虚警率f，应用第1级分类器对样本集进行分类；用第1级分类器对测试集进行评估，运算虚警率f并判决，将出错的非离网数据样本和通过第1级分类器确认的离网数据样本作为第2级分类器的原始数据，第2级分类器再估算数据测试集，计算虚警率f并判决，同上，将出错的非离网样本和通过第2级分类器确认的离网样本作为第3级分类器的原始数据。对第3级分类器进行测试评估——类似2级分类器评估的形式，计算虚警率f并判决，再把本层级出错的非离网样本和通过第3级分类器的离网样本作为第4级分类器的样本数据，获得的模型达到了预定的性能指标。级联分类器相应于单层次分类结构，在判决非离网数据样本时的准确度变化较小，但离网判断虚警率f明显降低，提升了数据策略的可读性。 征对AdaBoost多层次级联分类器、具备数据均衡处置的AdaBoost的多层次级联分类器决策树，在确认多层次级联分类器准确度降低较少的前提下，加大了
3.1 分类与决策树概述 3.1.1 分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是一个离散属性，它的取值是一个类别值，这种问题在数据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 3.1.2 决策树的基本原理 1.构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D，建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是“差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={“优”，
数据挖掘决策树算法的改进与实现 Data Mining Decision Tree Improvement&Implementation Xia Yan,Zhou Xiaohong,Wang Dong (Changchun Technology College,Changchun130033,China) :The author studied on existing Data Mining decision tree classification method based on the practical application,and applied to the system,achieved a decision support module. Keywords:Data Mining;Decision tree algorithm;Improve;Achieve 随着数据库技术的不断发展及数据库管理系统的广泛应用数据库中存储的数据量急剧增大, 在大量的数据背后隐藏着许多重要的信息, 如果能把这些信息从数据库中抽取出来, 将会产生重要的作用。 因此,数据挖掘涉及的学科领域逐渐扩大, 数据挖掘的方法也在不断地改进和提高。分类在数据挖掘中是一项非常重要的任务, 分类算法可以分为决策树分类算法、遗传算法、神经网络方法、K-最近邻分类算法等。这里，以疾病防控与儿童免疫管理系统中决策支持子系统的开发过程为例, 对决策树分类算法的改进及在实际中的应用进行阐述。 、数据选取和数据预处理
在本系统中 , 以预防接种中遇到异常反应后记录的“异常反 中的数据为例进行说明。具体实现过程详细说明 : 首 先输入训练集 , 由于在真实的 SQL Server 数据库当中 存储要求和减少存储时间 , 并非真正存储每个数据项的 属性值 而是用存储数字来对应相应的意义 , 如在数据库的数据表 程序页面时再映射回原来的值 , 为了说理清晰又限于篇幅 , 这里 只将所有数据集中有代表性的十几组数据作为分类模型创建的 输入训练集。 二、生成决策树 对训练集的每一个属性 , 计算其信息增益。以“月龄”属性 为例 , 每个结点中的正反例的个数分别为 [2,3] 、[3,2] 、[4,0], 分别计算如下 : info[2,3]= =0.971; info[3,2]= =0.971;info[4,0]=0; 计算信息熵 :E （ 月龄 ）= =0.693; 计算该属性的信息增益量 , 选取信息增益最大的属性为节点 按该属性的值划分数据集合 :Gain （ 月龄 ）=Info （9,5）-E （ 月 龄）=0.940-0.693=0.247; 属性都可计算每个结点的正反例的个数 （ 由于篇幅有限 , 不作计 算） 。通过对各属性信息增益的计算结果 , 选择“月龄”属性作为应调查表” , 为了降低 中, “性 性别”字段中 1”代表“男”、 “2”代表“女” , 反应到 同理, 对“注射反应”属性、 “出生状态”属性、 常住地”
摘要 随着信息科技的高速发展，人们对于积累的海量数据量的处理工作也日益增重，需发明之母，数据挖掘技术就是为了顺应这种需求而发展起来的一种数据处理技术。 数据挖掘技术又称数据库中的知识发现，是从一个大规模的数据库的数据中有效地、隐含的、以前未知的、有潜在使用价值的信息的过程。决策树算法是数据挖掘中重要的分类方法，基于决策树的各种算法在执行速度、可扩展性、输出结果的可理解性、分类预测的准确性等方面各有千秋，在各个领域广泛应用且已经有了许多成熟的系统，如语音识别、模式识别和专家系统等。本文着重研究和比较了几种典型的决策树算法，并对决策树算法的应用进行举例。 关键词：数据挖掘；决策树；比较
Abstract With the rapid development of Information Technology, people are f acing much more work load in dealing with the accumulated mass data. Data mining technology is also called the knowledge discovery in database, data from a large database of effectively, implicit, previou sly unknown and potentially use value of information process. Algorithm of decision tree in data mining is an important method of classification based on decision tree algorithms, in execution speed, scalability, output result comprehensibility, classification accuracy, each has its own merits., extensive application in various fields and have many mature system, such as speech recognition, pattern recognition and expert system and so on. This paper studies and compares several kinds of typical decision tree algorithm, and the algorithm of decision tree application examples. Keywords: Data mining; decision tree；Compare
土地开发权购买战略分析-决策树及线性最优化求解 一、相关计算 1、确定决策变量 2、确定目标函数 设修建大户型x座，小户型y座。 构建线性最优化模型 总利润max z = 185x+130y-100*500-(0.5x+0.4y)*100-(4x+3y)*10 = 185x+130y-50000-50x-40y-40x-30y=(185x-50x-40x)+(130y-40y-30y)-50000=95x+60y-50000 3、确定约束方程 0.41x+0.08y<=100 0.5x+0.4y<=400 4x+3y<=4000
4、线性最优化模型求解 采用 SOLVER宏，解出 X=500, y=375 5、公寓利润计算 A 全部建大户型大户型套数应为714，利润z=95x714-50000=17830万元 B 全部建小户型，小户型套数应为1000，利润z=60x1000-50000=10000万元 C大小户型混合修建，利润最大化条件下，大户型套数为500，小户型套数为375，利润z=95x500+60x375-50000=20000万元。 二、问题结论 1、根据决策树分析，海景公司应采取的最佳策略是，不请咨询公司投标。 2、根据决策树中计算的情报价值，咨询公司的情报价值为443万元，小于500 万元，因此不应考虑请调查咨询公司，其提出的500万元咨询费过高。 3、如果海景公司获得了地块的开发权，应该根据11月居民的投票结果来确定是 否完成土地的购买手续。如果投票结果改变计划，则完成购买手续，如果不 改变计划，则放弃购买。 4、如果完成了土地购买，根据利益最大化原则，采取大小户型混合修建的方式， 其中大户型500个，小户型375个。 5、如果采取了最佳策略，他可能获得的最大期望利益是20000万元。 附决策树分析图。
数据挖掘决策树算法的改进与实现 发表时间：2010-05-13T09:55:26.653Z 来源：《计算机光盘软件与应用》2010年第4期供稿作者：夏琰，周晓红，王东[导读] 本文作者从实际应用出发，对现存数据挖掘决策树分类方法进行了研究，并应用到系统当中，实现了决策支持模块。 夏琰，周晓红，王东 （长春职业技术学院，长春 130033）摘要：本文作者从实际应用出发，对现存数据挖掘决策树分类方法进行了研究，并应用到系统当中，实现了决策支持模块。关键词：数掘挖掘；决策树算法；改进；实现 中图分类号：TP301.6 文献标识码：A 文章编号：1007-9599 (2010) 04-0000-02 Data Mining Decision Tree Improvement&Implementation Xia Yan,Zhou Xiaohong,Wang Dong （Changchun Technology College,Changchun 130033,China）Abstract:The author studied on existing Data Mining decision tree classification method based on the practical application,and applied to the system,achieved a decision support module. Keywords:Data Mining;Decision tree algorithm;Improve;Achieve 随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储的数据量急剧增大，在大量的数据背后隐藏着许多重要的信息，如果能把这些信息从数据库中抽取出来，将会产生重要的作用。 因此，数据挖掘涉及的学科领域逐渐扩大，数据挖掘的方法也在不断地改进和提高。分类在数据挖掘中是一项非常重要的任务，分类算法可以分为决策树分类算法、遗传算法、神经网络方法、K-最近邻分类算法等。这里，以疾病防控与儿童免疫管理系统中决策支持子系统的开发过程为例，对决策树分类算法的改进及在实际中的应用进行阐述。 一、数据选取和数据预处理 在本系统中，以预防接种中遇到异常反应后记录的“异常反应调查表”中的数据为例进行说明。具体实现过程详细说明：首先输入训练集，由于在真实的SQL Server数据库当中，为了降低存储要求和减少存储时间，并非真正存储每个数据项的属性值，而是用存储数字来对应相应的意义，如在数据库的数据表中，“性别”字段中“1”代表“男”、“2”代表“女”，反应到程序页面时再映射回原来的值，为了说理清晰又限于篇幅，这里只将所有数据集中有代表性的十几组数据作为分类模型创建的输入训练集。 表1 判断是否需要计划外加强免疫的属性表 儿童编号月龄出生状态常住地上次注射后反 应是否需要计划外加强免疫 0405102<=2正常产城市无不良反应否 0405495<=2正常产农村无不良反应否 0401342>5正常产城市无不良反应是 04054352…5正常产城市轻度反应是 04065342…5非正常产城市重度反应是 04072342…5非正常产农村重度反应否 0401544>5非正常产农村重度反应是 0408519<=2正常产城市轻度反应否 0404566<=2非正常产城市重度反应是 04035472…5非正常产城市轻度反应是 0401534<=2非正常产农村轻度反应是 0405856>5正常产农村轻度反应是 0409533>5非正常产城市无不良反应是 04053442…5正常产农村轻度反应否 二、生成决策树 对训练集的每一个属性，计算其信息增益。以“月龄”属性为例，每个结点中的正反例的个数分别为［2，3］、[3，2]、[4，0]，分别计算如下： info[2，3]=； info[3，2]=；info[4，0]=0； 计算信息熵：E(月龄)＝＝0.693； 计算该属性的信息增益量，选取信息增益最大的属性为节点，按该属性的值划分数据集合：Gain(月龄)=Info(9，5)-E(月龄)=0.940-0.693=0.247； =0.971 =0.971
决策树剪枝的讨论 1.剪枝的必要性 现实世界的数据一般不可能是完美的，可能某些属性字段上缺值；可能缺少必要的数据而造成数据不完整；可能数据不准确、含有噪声甚至是错误的。基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练例子拟合。在有噪声情况下，完全拟合将导致过分拟合，即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。 2.剪枝的策略 有两种基本的剪枝策略： 1）预先剪枝：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。 2）后剪枝：是一种拟合-化简的两阶段方法。首先生成与训练数据完全拟合的一颗决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合，如果存在某个叶子剪去后使得在测试集上的准确度或其他测度不降低（不变的更坏），则剪去该叶子；否则停机。 理论上，后剪枝要好于预先剪枝，但计算量大。 3.决策树剪枝的方法 1）CCP方法 CCP 方法主要包含两个步骤: (1) 从原始决策树T0开始生成一个子树序列T0,T1,、、，Tn。其中,T(i + 1)从Ti产生, Tn为根节点。(2)从第1步产生的子树序列中,根据树的真实误差估计选择最佳决策树。 在步骤1中,生成子树序列{T 0, T 1, , , T n}的基本思想是从T0开始,裁剪Ti中关于训练数据集误差增加最小的分枝来得到T(i+1)。实际上,当1棵树T在节点t处剪枝时,它的误差增加直观上认为是R(t)-R( T t ) , 其中,R(t)为在节点t的子树被裁剪后节点t的误差,R(Tt)为在节点t的子树没被裁剪时子树Tt的误差。然而, 剪枝后,T的叶子数减少了L(Tt)-1,其中,L(Tt)为子树Tt的叶子数,也就是说,T的复杂性减少了。因此,考虑树的复杂性因素,树分枝被裁剪后误差增加率由下式决定: A=[R(t) - R(Tt)]/[|L(Tt)|-1] T(i+1)就是选择Ti中具有最小A值所对应的剪枝树。 2）REP方法 REP 方法它需要一个分离数据集D用于剪枝。该方法的基本思路是,对于决策树T的每棵非叶子树S,用叶子替代这棵子树。如果S被叶子替代后形成的新树关于D的误差等于或小于S关于D所产生的误差,则用叶子替代子树S。
精心整理 C4.5算法生成决策树 1、基础知识 当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。在这种情况下，概率分布最均SEE5、SLIQ 算法的的标准，克服了ID3算法中信息增益选择属性时偏向选择取值多的属性的不足，并能够完成对连续属性离散化的处理，还能够对不完整数据进行处理。根据分割方法的不同，目前决策的算法可以分为两类：基于信息论（InformationTheory ）的方法和最小GINI 指标（LowestGINIindex ）方法。对应前者的算法有ID3、C4.5，后者的有CART 、SLIQ 和SPRINT 。
C4.5算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。 2、算法 以下图数据为例，介绍用C4.5建立决策树的算法。 表1 ID3算法最初假定属性都是离散值，但在实际应用中，很多属性值都是连续的。C4.5对ID3不能处理连续型属性的缺点进行了改进。如果存在连续型的描述性属性，首先将连续型属性的值分成不同的区间，即“离散化”。
对上表中将实际耗电量分为10个区间（0—9） （300~320,320~340,340~360,360~380,380~400，400~420,420~440,440~460,460~480,480~500）因为最终是要得到实际的耗电量区间，因此“实际耗电量”属于“类别属性”。“室外温度”、“室内温度”、“室外湿度”、“风力大小”、“机房楼层”、“机房朝向”、“机房开启设备总额定功率”属于“非类别属性”。 表2 通过表 知，实 际耗电的个数表3
决策树研发二部
目录 1. 算法介绍 (1) 1.1.分支节点选取 (1) 1.2.构建树 (3) 1.3.剪枝 (10) 2. sk-learn中的使用 (12) 3. sk-learn中源码分析 (13)
1.算法介绍 决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对ID3优化出现的，既可以做分类，可以做回归。 决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。 决策树算法主要分为以下3个步骤： 1.分支节点选取 2.构建树 3.剪枝 1.1.分支节点选取 分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。 熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。 基尼系数：同上，也可以作为信息混乱程度的衡量指标。
有了量化指标后，就可以衡量使用某个分支条件前后，信息混乱程度的收敛效果了。使用分支前的混乱程度，减去分支后的混乱程度，结果越大，表示效果越好。 #计算熵值 def entropy(dataSet): tNum = len(dataSet) print(tNum) #用来保存标签对应的个数的，比如,男：6，女：5 labels = {} for node in dataSet: curL = node[-1] #获取标签 if curL not in labels.keys(): labels[curL] = 0 #如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 #将标签记录个数加1 #此时labels中保存了所有标签和对应的个数 res = 0 #计算公式为-p*logp，p为标签出现概率 for node in labels: p = float(labels[node]) / tNum res -= p * log(p, 2) return res #计算基尼系数 def gini(dataSet): tNum = len(dataSet) print(tNum) # 用来保存标签对应的个数的，比如,男：6，女：5 labels = {} for node in dataSet: curL = node[-1] # 获取标签 if curL not in labels.keys(): labels[curL] = 0 # 如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 # 将标签记录个数加1 # 此时labels中保存了所有标签和对应的个数 res = 1
决策树决策树研发二部
目录 1. 算法介绍 (1) 1.1. 分支节点选取 (1) 1.2. 构建树 (3) 1.3. 剪枝 (10) 2. sk-learn 中的使用 (12) 3. sk-learn中源码分析 (13)
1. 算法介绍 决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作 为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对 ID3优化出现的，既可以做分类，可以做回归。 决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。 决策树算法主要分为以下3个步骤： 1. 分支节点选取 2. 构建树 3. 剪枝 1.1. 分支节点选取 分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。 熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。 Entropy = -V p ” 基尼系数：同上，也可以作为信息混乱程度的衡量指标。 Gini = 1 - p： l-L
决策树算法的原理与应用 摘要：在机器学习与大数据飞速发展的21世纪，各种不同的算法成为了推动发 展的基石.而作为十大经典算法之一的决策树算法是机器学习中十分重要的一种算法。本文对决策树算法的原理，发展历程以及在现实生活中的基本应用进行介绍，并突出说明了决策树算法所涉及的几种核心技术和几种具有代表性的算法模式。 关键词：机器学习算法决策树 1.决策树算法介绍 1.1算法原理简介 决策树模型是一种用于对数据集进行分类的树形结构。决策树类似于数据结 构中的树型结构，主要是有节点和连接节点的边两种结构组成。节点又分为内部 节点和叶节点。内部节点表示一个特征或属性, 叶节点表示一个类. 决策树(Decision Tree),又称为判定树, 是一种以树结构(包括二叉树和多叉树)形式表达的 预测分析模型，决策树算法被评为十大经典机器学习算法之一[1]。 1.2 发展历程 决策树方法产生于上世纪中旬，到了1975年由J Ross Quinlan提出了ID3算法，作为第一种分类算法模型，在很多数据集上有不错的表现。随着ID3算法的 不断发展，1993年J Ross Quinlan提出C4.5算法，算法对于缺失值补充、树型结 构剪枝等方面作了较大改进，使得算法能够更好的处理分类和回归问题。决策树 算法的发展同时也离不开信息论研究的深入，香农提出的信息熵概念，为ID3算 法的核心，信息增益奠定了基础。1984年，Breiman提出了分类回归树算法，使 用Gini系数代替了信息熵，并且利用数据来对树模型不断进行优化[2]。 2．决策树算法的核心 2.1数据增益 香农在信息论方面的研究，提出了以信息熵来表示事情的不确定性。在数据 均匀分布的情况下，熵越大代表事物的越不确定。在ID3算法中，使用信息熵作 为判断依据，在建树的过程中，选定某个特征对数据集进行分类后，数据集分类 前后信息熵的变化就叫作信息增益，如果使用多个特征对数据集分别进行分类时，信息增益可以衡量特征是否有利于算法对数据集进行分类，从而选择最优的分类 方式建树。 如果一个随机变量X的可以取值为Xi（i=1…n），那么对于变量X来说，它 的熵就是 在得到基尼指数增益之后，选择基尼指数增益最大的特征来作为当前步骤的 分类依据，在之后的分类中重复迭代使用这一方法来实现模型的构造。 3. 决策树算法的优缺点 3.1决策树算法的优点[3] （1）计算速度快，算法简单，分类依据清晰 （2）在处理数据时，有很高的准确度，同时分类结果清晰，步骤明朗。 （3）可以处理连续和种类字段 （4）适合高维数据 3.2决策树算法的缺点 （1）决策树算法可以帮助使用者创建复杂的树，但是在训练的过程中，如
Computer Science and Application 计算机科学与应用, 2015, 5, 171-178 Published Online May 2015 in Hans. https://www.doczj.com/doc/ff2610143.html,/journal/csa https://www.doczj.com/doc/ff2610143.html,/10.12677/csa.2015.55022 C4.5 of Decision Tree Algorithm Optimization of Property Values Shifan Huang*, Yong Shen, Ruifang Wang, Huali Ma, Changgeng Chen, Yuhao Zhang School of Software, Yunnan University, Kunming Yunnan Email: *974794674@https://www.doczj.com/doc/ff2610143.html, Received: May 7th, 2015; accepted: May 23rd, 2015; published: May 28th, 2015 Copyright ? 2015 by authors and Hans Publishers Inc. This work is licensed under the Creative Commons Attribution International License (CC BY). https://www.doczj.com/doc/ff2610143.html,/licenses/by/4.0/ Abstract About the decision tree algorithm, the quantity of the attribute value types determines the quan-tity of the decision tree branch. Based on this, we put forward a new method which can optimize attribute value. The examples show that the method can optimize the quantity of the decision tree branch, and reach the purpose that simplifies the decision tree structure. This method has no ef-fect on the classification accuracy of the C4.5 algorithm. Keywords Decision Tree, C4.5 Algorithm, Property Values, Optimization 决策树C4.5算法属性取值优化研究 黄世反*，沈勇，王瑞芳，马华丽，陈长赓，张宇昊 云南大学软件学院，云南昆明 Email: *974794674@https://www.doczj.com/doc/ff2610143.html, 收稿日期：2015年5月7日；录用日期：2015年5月23日；发布日期：2015年5月28日 摘要 在决策树算法中，属性取值种类的多少决定着决策树分支数量的多少。基于此，提出了一种新的属性取*通讯作者。
分类论文决策树相关算法论文：决策树相关算法研究 摘要：id3算法和c4.5算法是经典的决策树算法，通过对id3算法和c4.5算法的数据结构、算法描述和分裂属性选取等方面进行比较，为其他研究者提供参考。 关键词：分类；id3；c4.5 an association explore based on decision tree algorithm wang hui, hou chuan-yu (school of information engineering, suzhou university, suzhou 234000, china) abstract: id3 algorithm and c4.5algorithm is classic decision tree algorithm in data mining. the article has some comparisons about c4.5 algorithm and id3 algorithm ,for example, data structure of decision tree, the process of algorithm of c4.5 and id3, and the choice of division attribute and so on, in order to provide this for others. key words: categories; id3; c4.5 随着计算机的普及和网络的高速发展，人们获得信息的途径越来越多，同时获取信息的量呈几何级数的方式增长。如何从海量信息获得有用知识用于决策，成为大家关注的问
如何运用决策树进行分类分析 前面我们讲到了聚类分析的基本方法，这次我们来讲讲分类分析的方法。 所谓分类分析，就是基于响应，找出更好区分响应的识别模式。分类分析的方法很多，一般而言，当你的响应为分类变量时，我们就可以使用各种机器学习的方法来进行分类的模式识别工作，而决策树就是一类最为常见的机器学习的分类算法。 决策树，顾名思义，是基于树结构来进行决策的，它采用自顶向下的贪婪算法，在每个结点选择分类的效果最好的属性对样本进行分类，然后继续这一过程，直到这棵树能准确地分类训练样本或所有的属性都已被使用过。 建造好决策树以后，我们就可以使用决策树对新的事例进行分类。我们以一个生活小案例来说什么是决策树。例如，当一位女士来决定是否同男士进行约会的时候，她面临的问题是“什么样的男士是适合我的，是我值得花时间去见面再进行深入了解的？” 这个时候，我们找到了一些女生约会对象的相关属性信息，例如，年龄、长相、收入等等，然后通过构建决策树，层层分析，最终得到女士愿意去近一步约会的男士的标准。 图：利用决策树确定约会对象的条件
接下来，我们来看看这个决策的过程什么样的。 那么，问题来了，怎样才能产生一棵关于确定约会对象的决策树呢？在构造决策树的过程中，我们希望决策树的每一个分支结点所包含的样本尽可能属于同一类别，即结点的”纯度”（Purity ）越来越高。 信息熵（Information Entropy ）是我们度量样本集合纯度的最常见指标，假定当前样本集合中第K 类样本所占的比例为P k ，则该样本集合的信息熵为： Ent (D )=?∑p k |y| k=1 log 2p k 有了这个结点的信息熵，我们接下来就要在这个结点上对决策树进行裁剪。当我们选择了某一个属性对该结点，使用该属性将这个结点分成了2类，此时裁剪出来的样本集为D 1和D 2， 然后我们根据样本数量的大小，对这两个裁剪点赋予权重|D 1||D|?，|D 2||D|?，最后我们就 可以得出在这个结点裁剪这个属性所获得的信息增益（Information Gain ） Gain(D ，a)=Ent (D )?∑|D V ||D |2 v=1Ent(D V ) 在一个结点的裁剪过程中，出现信息增益最大的属性就是最佳的裁剪点，因为在这个属性上，我们获得了最大的信息增益，即信息纯度提升的最大。 其实，决策树不仅可以帮助我们提高生活的质量，更可以提高产品的质量。 例如，我们下表是一组产品最终是否被质检接受的数据，这组数据共有90个样本量，数据的响应量为接受或拒绝，则|y|=2。在我们还没有对数据进行裁剪时，结点包含全部的样本量，其中接受占比为p 1= 7690，拒绝占比为p 2=1490，此时，该结点的信息熵为： Ent (D )=?∑p k |y|k=1log 2p k =-（7690log 27690+1490log 21490）=0.6235
决策树分类 决策树（Decision Tree）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（internal node）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（leaf）代表某个类（class）或者类的分布（class distribution），最上面的结点是根结点。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。 构造决策树是采用自上而下的递归构造方法。决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为(a = b)的逻辑判断，其中a 是属性，b是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ID3）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。 使用决策树进行分类分为两步： 第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。 第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。 问题的关键是建立一棵决策树。这个过程通常分为两个阶段： (1) 建树（Tree Building）：决策树建树算法见下，可以看得出，这是一个递归的过程，最终将得到一棵树。 (2) 剪枝（Tree Pruning）：剪枝是目的是降低由于训练集存在噪声而产生的起伏。 决策树方法的评价。 优点 与其他分类算法相比决策树有如下优点： (1) 速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。 (2) 准确性高：挖掘出的分类规则准确性高，便于理解，决策树可以清晰的显示哪些字段比较重要。 缺点 一般决策树的劣势： (1) 缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。一个例子：在Irvine机器学习知识库中，最大可以允许的数据集仅仅为700KB，2000条记录。而现代的数据仓库动辄存储几个G-Bytes的海量数据。用以前的方法是显然不行的。
用决策树法进行方案优选 期望值决策方法，除用决策益损表分析外，也可采用决策树法进行分析，这种决策方法的思路如树枝形状，所以，称为决策树。 （1）决策树的结构。决策树是以方块和圆点作为结点，并由直线连接而形成一种树枝状结构，图中符号说明如下： □——表示决策结点，由它引出的若干条树枝，每枝代表一个方案。 ○——表示状态结点，由它引出的若干条树枝，每枝代表一个自然状态，并在其上写明自然状态及其概率。 △——表示每种自然状态相应的益损值 一般决策问题具有多个方案，每个方案可能有多种状态。因此，图形从左向右，由简到繁组成为一个树枝网状图。 应用树枝图进行决策的过程是：由右向左，逐步后退。根据右端的益损值和状态枝上的概率，计算出同一方案的不同状态下的期望益损值，然后根据不同方案的期望益损值的大小进行选择。方案的舍弃称为修枝，舍弃的方案只需在枝上画出“//”的符号，即表示修枝的意思。最后决策结点只留下一条树枝，就是决策的最优方案。 例题1：某土建承包公司确定今后6年内机械设备的投资计划。公司有两种方案： （1）投资1050万元购买大型车队 （2）投资350万元购买小型车队 经理估计能签到大宗合同的概率是0.6，而只能签到少量合同的概率是0.4。假如购置大型车队又签到大宗合同，在今后6年中，每年收入为400万元；假如购置大型车队而只能签到少量合同，每年收入为100万元。假如购置小型车队而又可签到大宗合同，由于车队的限制，每年收入为200万元；假如购置小型车队而只签到少量合同，则每年收入为120万元。 当购置大型车队只签到少量合同，那么在两年后公司要决定如何处理已有设备。他有四种选择： （1）公司将不用的设备出租，估计能出租全部闲置设备的概率是0.7，在出租的4年内每年平均收入350万元；只能出租部分闲置设备的概率是0.3，4年内平均每年净收入150万元。 （2）现将设备暂时存放在库房里不用，等到以后工程合同多时使用。估计这段时间内有1/2的机会签到更多合同，这时前两年的收入150万元，后两年每年获利为250万元； 如果在这段时间只能签到少数的工程合同，那4年每年内收入100万元。 （3）及时出售多余的设备，估计可得500万元，另外保留的机械每年能获100万元。（4）马上全部卖掉所有车队，估计可得800万元。 如果当初决定购置小型车队又签到大宗合同，那么在作出最初决策后的12个月内，经理不得不对未来行动作出决策。有三种选择： （1）再购置更多的设备，花费700万元，获得满意合同收入的概率是0.6，余下的5年内每年平均收入400万元；另一方面是合同签订不太理想，其概率是0.4，5年内每年平均收入为150万元。 （2）租借更多的设备，有三种可能结局：一是能以优惠的合同条件从其他单位租借到完全符合要求的设备，发生的概率是0.2，估计5年内每年可得净收入300万元。二是租到租金较高又不完全符合要求的设备，发生的概率是0.5，估计5年内收入每年