决策树1

决策树学习算法概要简介决策树表示法决策树学习的适用问题基本的决策树学习算法决策树学习中的假想空间搜索决策树学习的常见问题简介决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4.5。有名的决策树方法还有CART和Assistant。是应用最广的归纳推理算法之一一种逼近离散值目标函数的方法对噪声数据有很好的健壮性且能学习析取表达式1.决策树算法的框架(1/5)判定树分类算法output训练集决策树input决策树通过把实例从根节点排列到某个叶子节点来分类实例。叶子节点即为实例所属的分类每个节点说明了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值正实例：产生正值决策的实例负实例：产生负值决策的实例1.决策树算法的框架(2/5)1.决策树算法的框架(3/5)决策树代表实例属性值约束的合取的析取式(析取范式)。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取1.决策树算法的框架(4/5)1.决策树算法的框架(5/5)2.决策树学习的适用问题(1/2)适用问题的特征实例是由属性-值对表示的目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误训练数据可以包含缺少属性值的实例问题举例根据疾病分类患者根据起因分类设备故障根据拖欠支付的可能性分类贷款申请分类问题核心任务是把样例分类到各可能的离散值对应的类别2.决策树学习的适用问题(2/2)3.基本的决策树学习算法1.CLS学习算法2.ID3学习算法CLS学习算法基本思想：在CLS的决策树中，节点对应于待分类对象的属性，由某一节点引出的弧对应于这一属性可能去的属性值，叶节点对应于分类的结果。CLS算法描述(1)如果训练集TR中所有实例分类结果均为Ci，则返回Ci；(2)从属性表中选择某一属性A作为检测属性；(3)不妨假定|ValueType(Ai)|=k，根据A取值不同，将TR划分为k个集TR1,,…,TRk,；(4)从属性表中去掉已检验的属性A；(5)对每个i，用TRi和新的属性表递归调用CLS生成TRi的决策树；(6)返回以属性A为根，为子树的决策树。例1：鸟是否能飞的实例InstancesNo.ofwingsBrokenwingsLivingstatusWingarea/weightFly120Alive2.5True221Alive2.5False322Alive2.6False420Alive3.0True520Dead3.2False600Alive0False710Alive0False820Alive3.4True920alive2.0False属性表:{No.ofwings，Brokenwings，Livingstatus，wingarea/weight}各属性的取值域分别为：ValueType(No.ofwings)={0,1,2}ValueType(Brokenwings)={0,1,2}ValueType(Livingstatus)={alive,dead}ValueType(wingarea/weight)No.ofwingsNo.ofwingsNoNoNoNostatusNo.ofwingsNoyesNo210210alivedead5.2ID3算法CLS算法可以产生所有可能的决策树，正确分类训练实例。并能选择最简单的决策树。但是，它所面对的学习问题不能太大，并且一次对全部训练集构造决策的算法效率低。为此，Quinlan提出了逐步形成完整决策树的迭代思想。ID3的思想自顶向下构造决策树从“哪一个属性将在树的根节点被测试”开始使用统计测试来确定每一个实例属性单独分类训练样例的能力ID3的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程信息熵(InformationEntropy)信息熵是一个数学上颇为抽象的概念，在这里不妨把信息熵理解成某种特定信息的出现概率（离散随机事件的出现概率）。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。信息熵也可以说是系统有序化程度的一个度量。熵(Entropy)原是物理学中的一个概念，法国物理学家克劳修斯用熵描述一个物理系统的无序性。系统的无序程度越高，则熵越大。信息论在信息论中信源输出是随机量，因而其不定度可以用概率分布来度量。记H(X)＝H(P1，P2，…，Pn)，这里P(i)，i＝1，2，…，n为信源取第i个符号的概率。H(X)称为信源的信息熵。可以从数学上加以证明，只要H(X)满足下列三个条件：①连续性：H(P，1－P)是P的连续函数(0≤P≤1)；②对称性：H(P1，…，Pn)与P1，…，Pn的排列次序无关；③可加性：若Pn＝Q1+Q2＞0，且Q1，Q2≥0，则有H(P1，…，Pn-1，Q1，Q2)＝H(P1，…，Pn-1)+PnH；则一定有下列唯一表达形式：H(P1，…，Pn)＝-CP(i)logP(i)其中C为正整数，一般取C＝1，它是信息熵的最基本表达式。信息熵除了上述三条基本性质外，还具有一系列重要性质，其中最主要的有：①非负性：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；⑤上凸性：H[λP+(1-λ)Q]＞λH(P)+(1-λ)H(Q)，式中0＜λ＜1。属性选择熵(entropy)：给定有关某概念的正例和负例的集合S。对此BOOLEAN分类的熵为：Entropy(S)=-poslog2(pos)–neglog2(neg)“pos”和”neg”分别表示S中正例和负例的比例。并定义：0log2(0)=0如果分类器有c个不同的输出，则：Entropy(S)=-ci=1pilog2(pi)pi表示S中属于类i的比例例1：p1=p2=1/2H1=-(1/2)*log2(1/2)-(1/2)*log2(1/2)=1例2：p1=1/4p2=3/4H2=-(1/4)*log2(1/4)-(3/4)*log2(3/4)=0.81例3：p1=1p2=0H3=-1*log21=0属性选择构造好的决策树的关键在于如何选择好的属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的属性。由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的属性。ID3算法的本质：就是构造一棵熵值下降平均最快的决策树。最佳分类属性用信息增益度量期望的熵降低属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低Gain(S,A)是在知道属性A的值后可以节省的二进制位数)()(||)(),(AValuesvvvSEntropySSSEntropyASGainID3算法创建树的Root结点如果Examples都为正，那么返回label=+中的单结点Root如果Examples都为反，那么返回lable=-单结点树Root如果Attributes为空，那么返回单节点树Root，lable=Examples中最普遍的目标属性值否则开始AAttributes中分类能力最好的属性Root的决策属性A对于每个可能值在Root下加一个新的分支对应测试A=vi令Example-vi为Examples中满足A属性值为vi的子集如果Examples-vi为空在这个新分支下加一个叶子结点，节点的lable=Examples中最普遍的目标属性值否则在这个新分支下加一个子树ID3(example-vi,target-attribute,attributes-|A|结束返回RootID3主算法流程图训练集PE,NE取子集建窗口窗口PE’,NE’生成决策树测试PE,NE此决策树为最后结果扩展窗口PE’=PE’+PE’’NE’=NE’+NE’’存在错误的PE’’,NE’’例2.ageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno30…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentnoDecisionTree(结果输出)age?overcaststudent?creditrating?noyesfairexcellent=3040nonoyesyesyes30..40用信息增益度量期望熵最低举例用ID3算法得到的有关气候的决策树某市属建筑公司面临A,B两项工.本单位资源条件限制，只能选择其中一项工程投标或者这两项过程均不参加投标。根据过去类似工程投标的经验数据，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的改进算法对连续值的处理对未知特征值的处理对决策树进行剪枝规则的派生决策树学习中的假设空间搜索假设空间ID3算法中的假设空间包含所有的决策树当遍历决策树空间时，ID3仅维护单一的当前假设。基本的ID3算法在搜索中不进行回溯ID3算法在搜索的每一步都使用当前的所有训练样例决策树学习的常见问题(1)避免过度拟合数据基本的决策树构造算法没有考虑噪声，生成的决策树完全与训练例子拟合。有噪声情况下，完全拟合将导致过分拟合（overfitting），即对训练数据的完全拟合反而不具有很好的预测性能。解决方法剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。向前剪枝（forwardpruning）向后剪枝（backwardpruning）理论上讲，向后剪枝好于向前剪枝，但计算复杂度大。剪枝过程中一般要涉及一些统计参数或阈值，如停机阈值；有人提出了一种和统计参数无关的基于最小描述长（MDL）的有效剪枝法决策树学习的常见问题（2）合并连续值属性属性选择的其他度量标准信息增益比（gainratio）、Gini-index、距离度量（distancemeasure）等。不同的度量有不同的效果，特别是对于多值属性。决策树学习的常见问题（3）处理缺少属性值的训练样例处理不同代价的属性决策树的优点可以生成可以理解的规则；计算量相对来说不是很大；可以处理连续和离散字段；决策树可以清晰的显示哪些字段比较重要不足之处对连续性的字段比较难预测当类别太多时，错误可能会增加的比较快一般的算法分类的时候，只是根据一个属性来分类。不是全局最优。