《[精选]决策树1》由会员分享，可在线阅读，更多相关《[精选]决策树1（49页珍藏版）》请在金锄头文库上搜索。
1、决策树学习算法概要,简介 决策树表示法 决策树学习的适用问题 基本的决策树学习算法 决策树学习中的假想空间搜索 决策树学习的常见问题,简介,决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4.5。有名的决策树方法还有CART和Assistant。 是应用最广的归纳推理算法之一 一种逼近离散值目标函数的方法 对噪声数据有很好的健壮性且能学习析取表达式,1.决策树算法的框架(1/5),决策树 通过把实例从根节点排列到某个叶子节点来分类实例。 叶子节点即为实例所属的分类 每个节点说明了对实例的某个属性的测试 节点的每个后继分支对应于该属性的一个可能值
2、 正实例：产生正值决策的实例 负实例：产生负值决策的实例,1.决策树算法的框架(2/5),1.决策树算法的框架(3/5),决策树代表实例属性值约束的合取的析取式(析取范式)。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取,1.决策树算法的框架(4/5),1.决策树算法的框架(5/5),2.决策树学习的适用问题(1/2),适用问题的特征 实例是由属性-值对表示的 目标函数具有离散的输出值 可能需要析取的描述 训练数据可以包含错误 训练数据可以包含缺少属性值的实例,问题举例 根据疾病分类患者 根据起因分类设备故障 根据拖欠支付的可能性分类贷款申请 分类问题 核心任务是把样
3、例分类到各可能的离散值对应的类别,2.决策树学习的适用问题(2/2),3.基本的决策树学习算法,CLS学习算法 ID3学习算法,CLS学习算法,基本思想： 在CLS的决策树中，节点对应于待分类对象的属性，由某一节点引出的弧对应于这一属性可能去的属性值，叶节点对应于分类的结果。,CLS算法描述,如果训练集TR中所有实例分类结果均为Ci，则返回Ci； 从属性表中选择某一属性A作为检测属性； 不妨假定|ValueType(Ai)|=k，根据A取值不同，将TR划分为k个集TR1, TRk, ； 从属性表中去掉已检验的属性A ； 对每个i，用TRi和新的属性表递归调用CLS生成TRi的决策树； 返回以属
4、性A为根，为子树的决策树。,例1：鸟是否能飞的实例,属性表: No. of wings， Broken wings， Living status， wing area/ weight 各属性的取值域分别为： ValueType(No. of wings)=0,1,2 ValueType(Broken wings)=0,1,2 ValueType(Living status)=alive, dead ValueType(wing area/ weight),ID3算法,CLS算法可以产生所有可能的决策树，正确分类训练实例。并能选择最简单的决策树。但是，它所面对的学习问题不能太大，并且一次对全部训
5、练集构造决策的算法效率低。为此，Quinlan提出了逐步形成完整决策树的迭代思想。,ID3的思想 自顶向下构造决策树 从“哪一个属性将在树的根节点被测试”开始 使用统计测试来确定每一个实例属性单独分类训练样例的能力 ID3的过程 分类能力最好的属性被选作树的根节点 根节点的每个可能值产生一个分支 训练样例排列到适当的分支 重复上面的过程,信息熵(Information Entropy),信息熵是一个数学上颇为抽象的概念，在这里不妨把信息熵理解成某种特定信息的出现概率（离散随机事件的出现概率）。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。信息熵也可以说是系统有序化程度的
6、一个度量。,熵(Entropy),原是物理学中的一个概念，法国物理学家克劳修斯用熵描述一个物理系统的无序性。系统的无序程度越高，则熵越大。,信息论,在信息论中信源输出是随机量，因而其不定度可以用概率分布来度量。记 H(X)H(P1，P2，Pn)，这里P(i)，i1，2，n为信源取第i个符号的概率。H(X)称为信源的信息熵。,可以从数学上加以证明，只要H(X)满足下列三个条件： 连续性：H(P，1P)是P的连续函数(0P1)； 对称性：H(P1，Pn)与P1，Pn的排列次序无关； 可加性：若PnQ1+Q20，且Q1，Q20，则有H(P1，Pn-1，Q1，Q2)H(P1，Pn-1)+PnH；则一定
7、有下列唯一表达形式：H(P1，Pn)-CP(i)logP(i) 其中C为正整数，一般取C1，它是信息熵的最基本表达式。,信息熵除了上述三条基本性质外，还具有一系列重要性质，其中最主要的有： 非负性：H(P1，Pn)0； 确定性：H(1，0)H(0，1)H(0，1，0，)0； 扩张性：Hn-1(P1，Pn-，)Hn(P1，Pn)； 极值性：P(xi)logP(xi)P(xi)logQ(xi)；这里Q(xi)1； 上凸性：HP +(1-)QH(P)+(1-)H(Q)，式中01。,属性选择,熵(entropy)：给定有关某概念的正例和负例的集合S。对此BOOLEAN分类的熵为： Entropy(S)
8、= - pos log2(pos) neg log2(neg) “pos”和”neg”分别表示S中正例和负例的比例。并定义：0log2(0)=0 如果分类器有c个不同的输出，则： Entropy(S)= - ci=1pi log2(pi) pi表示S中属于类i的比例,例1：p1 = p2 = 1/2 H1 = -(1/2)*log2(1/2) - (1/2)*log2(1/2) = 1 例2：p1 = 1/4 p2 = 3/4 H2 = -(1/4)* log2(1/4) - (3/4)*log2(3/4)=0.81 例3：p1 = 1 p2 = 0 H3 = -1 * log21 = 0,属
9、性选择,构造好的决策树的关键在于如何选择好的属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的属性。由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的属性。,ID3算法的本质： 就是构造一棵熵值下降平均最快的决策树。,最佳分类属性,用信息增益度量期望的熵降低 属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低 Gain(S,A)是在知道属性A的值后可以节省的二进制位数,ID3算法,创建树的Root结点 如果Examples都为正，那么返回label=+中的单
10、结点Root 如果Examples都为反，那么返回lable=-单结点树Root 如果Attributes为空，那么返回单节点树Root，lable=Examples中最普遍的目标属性值 否则开始 AAttributes中分类能力最好的属性 Root的决策属性A 对于每个可能值 在Root下加一个新的分支对应测试A=vi 令Example-vi为Examples中满足A属性值为vi的子集 如果Examples-vi为空 在这个新分支下加一个叶子结点，节点的lable=Examples中最普遍的 目标属性值 否则在这个新分支下加一个子树ID3(example-vi,target-attribut
11、e,attributes-|A| 结束 返回 Root,ID3主算法流程图,训练集PE,NE,取子集建窗口,窗口PE,NE,生成决策树,测试PE,NE,此决策树为 最后结果,扩展窗口 PE=PE+PE NE=NE+NE,存在错误的 PE,NE,例2.,Decision Tree (结果输出),age?,overcast,student?,credit rating?,no,yes,fair,excellent,=30,40,no,no,yes,yes,yes,30.40,用信息增益度量期望熵最低,举例,用ID3算法得到的有关气候的决策树,某市属建筑公司面临A, B两项工.本单位资源条件限制，只
12、能选择其中一项工程投标或者这两项过程均不参加投标。根据过去类似工程投标的经验数据，A工程投高标的中标概率为0.3,投低标的中标概率为0.8,编制该工程投标文件的费用为4万元；B工程投高标的中标概率为0.5,投低标的中标概率为0.6，编制该工程投标文件的费用为2.5 万元各方案承包的效果、概率、损益值如表1所示,ID3算法的优缺点,ID3算法的优点：分类和测试速度快 缺点： 1.知识表示没有规则容易理解； 2. 两棵决策树是否等价的判定问题是NP问题； 3.不能处理未知属性值的情况。,C4.5,C4.5是对ID3的改进算法 对连续值的处理 对未知特征值的处理 对决策树进行剪枝 规则的派生,决策树
13、学习中的假设空间搜索,假设空间 ID3算法中的假设空间包含所有的决策树 当遍历决策树空间时，ID3仅维护单一的当前假设。 基本的ID3算法在搜索中不进行回溯 ID3算法在搜索的每一步都使用当前的所有训练样例,决策树学习的常见问题(1),避免过度拟合数据 基本的决策树构造算法没有考虑噪声，生成的决策树完全与训练例子拟合。有噪声情况下，完全拟合将导致过分拟合（overfitting），即对训练数据的完全拟合反而不具有很好的预测性能。,解决方法,剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。 向前剪枝（forward pruning） 向后剪枝（backward pruning）
14、 理论上讲，向后剪枝好于向前剪枝，但计算复杂度大。剪枝过程中一般要涉及一些统计参数或阈值，如停机阈值；有人提出了一种和统计参数无关的基于最小描述长（MDL）的有效剪枝法,决策树学习的常见问题（2）,合并连续值属性 属性选择的其他度量标准 信息增益比（gain ratio）、Gini-index、距离度量（distance measure）等。不同的度量有不同的效果，特别是对于多值属性。,决策树学习的常见问题（3）,处理缺少属性值的训练样例 处理不同代价的属性,决策树的优点,可以生成可以理解的规则； 计算量相对来说不是很大； 可以处理连续和离散字段； 决策树可以清晰的显示哪些字段比较重要,不足之处,对连续性的字段比较难预测 当类别太多时，错误可能会增加的比较快 一般的算法分类的时候，只是根据一个属性来分类。 不是全局最优。,
