《机器学习算法总结决策树资料》由会员分享，可在线阅读，更多相关《机器学习算法总结决策树资料（20页珍藏版）》请在金锄头文库上搜索。
1、第三章 决策树决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。2.1 决策树模型与学习2.1.1 决策树模型定义2.1（决策树） 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结
2、点（node）和有向边（directed edge）组成。决策点，是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案为最终决策方案。状态节点，代表备选方案的经济效果（期望值），通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。结果节点，将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。2.1.2 决策树学习决策树是以实例为基础的归纳学习算法。 它从一组无次序、无规则的元组中推理出
3、决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，并根据不同的属性值从该结点向下分支，叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上，1993年Quinlan又提出了C4.5算法。为了适应处理大规模数据集的需要，后来又提出了若干改进的算法，其中SLIQ(super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)
4、是比较有代表性的两个算法。2.1.3 决策树分析法决策树分析法是常用的风险分析决策方法。该方法是一种用树形图来描述各方案在未来收益的计算。比较以及选择的方法，其决策是以期望值为标准的。它利用了概率论的原理，并且利用一种树形图作为分析工具。它利用了概率论的原理，并且利用一种树形图作为分析工具。其基本原理是用决策点代表决策问题，用方案分枝代表可供选择的方案，用概率分枝代表方案可能出现的各种结果，经过对各种方案在各种结果条件下损益值的计算比较，为决策者提供决策依据。决策树分析法是常用的风险分析决策方法。该方法是一种用树形图来描述各方案在未来收益的计算。比较以及选择的方法，其决策是以期望值为标准的。人
5、们对未来可能会遇到好几种不同的情况。每种情况均有出现的可能，人们目前无法确知，但是可以根据以前的资料来推断各种自然状态出现的概率。在这样的条件下，人们计算的各种方案在未来的经济效果只能是考虑到各种自然状态出现的概率的期望值，与未来的实际收益不会完全相等。如果一个决策树只在树的根部有一决策点，则称为单级决策；若一个决策不仅在树的根部有决策点，而且在树的中间也有决策点，则称为多级决策。科学的决策是现代管理者的一项重要职责。我们在企业管理实践中，常遇到的情景是：若干个可行性方案制订出来了，分析一下企业内、外部环境，大部分条件是己知的，但还存在一定的不确定因素。每个方案的执行都可能出现几种结果，各种结
6、果的出现有一定的概率，企业决策存在着一定的胜算，也存在着一定的风险。这时，决策的标准只能是期望值。即，各种状态下的加权平均值。针对上述问题，用决策树法来解决不失为一种好的选择。决策树法作为一种决策技术，已被广泛地应用于企业的投资决策之中，它是随机决策模型中最常见、最普及的一种规策模式和方法此方法，有效地控制了决策带来的风险。所谓决策树法，就是运用树状图表示各决策的期望值，通过计算，最终优选出效益最大、成本最小的决策方法。决策树法属于风险型决策方法，不同于确定型决策方法，二者适用的条件也不同。应用决策树决策方法必须具备以下条件：1有决策者期望达到的明确目标；2存在决策者可以选择的两个以上的可行备
7、选方案；3存在着决策者无法控制的两种以上的自然状态(如气候变化、市场行情、经济发展动向等)；4不同行动方案在不同自然状态下的收益值或损失值(简称损益值)可以计算出来；5决策者能估计出不同的自然状态发生概率。2.2 特征选择2.2.1 特征选择问题1、为什么要做特征选择在有限的样本数目下，用大量的特征来设计分类器计算开销太大而且分类性能差。2、特征选择的确切含义将高维空间的样本通过映射或者是变换的方式转换到低维空间，达到降维的目的，然后通过特征选取删选掉冗余和不相关的特征来进一步降维。3、特征选取的原则获取尽可能小的特征子集，不显著降低分类精度、不影响类分布以及特征子集应具有稳定适应性强等特点4
8、、特征选择需要考虑的问题a、确定选择算法，在允许的时间内以最小的代价找出最小的、最能描述类别的特征组合，b、确定评价标准，衡量特征组合是否是最优，得到特征获取操作的停止条件。5、特征获取方法a、按照特征子集的形成方式可以分为三种，穷举法（exhaustion）、启发法（heuristic）和随机法（random）。穷举法需要遍历特征空间中所有的特征组合，所以方法复杂度最大，实用性不强；启发法通过采用期望的人工机器调度规则，重复迭代产生递增的特征子集，复杂度略低于穷举法，但是只能获取近似最优解；随即方法分为完全随机方法和概率随机方法两种，对参数设置的依赖性较强。b、按照特征评价标准来分，根据评价
9、函数与分类器的关心，可以分为筛选器和封装器两种，筛选器的评价函数与分类器无关，封装器采用分类器的错误概率作为评价函数。筛选器的评价函数可以细分为距离测度、信息测度、相关性测度和一致性测度。距离测度用距离来衡量样本之间的相似度，信息测度用利用最小不确定性特征来分类。6、特征获取方法的选取原则a、处理的数据类型b、处理的问题规模c、问题需要分类的数量d、对噪声的容忍能力e、无噪声环境下，产生稳定性好、最优特征子集的能力。 特征选择的一般过程可用图1表示。首先从特征全集中产生出一个特征子集，然后用评价函数对该特征子集进行评价，评价的结果与停止准则进行比较，若评价结果比停止准则好就停止，否则就继续产生
10、下一组特征子集，继续进行特征选择。选出来的特征子集一般还要验证其有效性。 综上所述，特征选择过程一般包括产生过程，评价函数，停止准则，验证过程，这4个部分。 (1) 产生过程( Generation Procedure )产生过程是搜索特征子集的过程，负责为评价函数提供特征子集。搜索特征子集的过程有多种，将在2.2小节展开介绍。 (2) 评价函数( Evaluation Function )评价函数是评价一个特征子集好坏程度的一个准则。(3) 停止准则( Stopping Criterion )停止准则是与评价函数相关的，一般是一个阈值，当评价函数值达到这个阈值后就可停止搜索。(4) 验证过程
11、( Validation Procedure )在验证数据集上验证选出来的特征子集的有效性。2.2.2 信息增益信息增益（KullbackLeibler divergence）又称information divergence，information gain，relative entropy 或者KLIC。在概率论和信息论中，信息增益是非对称的，用以度量两种概率分布P和Q的差异。信息增益描述了当使用Q进行编码时，再使用P进行编码的差异。通常P代表样本或观察值的分布，也有可能是精确计算的理论分布。Q代表一种理论，模型，描述或者对P的近似。尽管信息增益通常被直观地作为是一种度量或距离，但事实上信息
12、增益并不是。就比如信息增益不是对称的，从P到Q的信息增益通常不等于从Q到P的信息增益。信息增益是f增益（f-divergences）的一种特殊情况。在1951年由Solomon Kullback 和Richard Leibler首先提出作为两个分布的直接增益（directed divergence）。它与微积分中的增益不同，但可以从Bregman增益（Bregman divergence）推导得到。在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。因此先回忆一下信息论中有关信息量（就是“熵”）的定义。说有这么一个变量X，它可能的取值有n多种，分别
13、是，每一种取到的概率分别是，那么X的熵就定义为：意思就是一个变量可能的变化越多（反而跟变量具体的取值没有任何关系，只和值的种类多少以及发生概率有关），它携带的信息量就越大（因此我一直觉得我们的政策法规信息量非常大，因为它变化很多，基本朝令夕改，笑）。对分类系统来说，类别C是变量，它可能的取值是，而每一个类别出现的概率是，因此n就是类别的总数。此时分类系统的熵就可以表示为：信息增益是针对一个一个的特征而言的，就是看一个特征t，系统有它和没它的时候信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即增益。系统含有特征t的时候信息量很好计算，就是刚才的式子，它表示的是包含所有特征时系统的信息
14、量。问题是当系统不包含t时，信息量如何计算？我们换个角度想问题，把系统要做的事情想象成这样：说教室里有很多座位，学生们每次上课进来的时候可以随便坐，因而变化是很大的（无数种可能的座次情况）；但是现在有一个座位，看黑板很清楚，听老师讲也很清楚，于是校长的小舅子的姐姐的女儿托关系（真辗转啊），把这个座位定下来了，每次只能给她坐，别人不行，此时情况怎样？对于座次的可能情况来说，我们很容易看出以下两种情况是等价的：（1）教室里没有这个座位；（2）教室里虽然有这个座位，但其他人不能坐（因为反正它也不能参与到变化中来，它是不变的）。对应到我们的系统中，就是下面的等价：（1）系统不包含特征t；（2）系统虽然
15、包含特征t，但是t已经固定了，不能变化。我们计算分类系统不包含特征t的时候，就使用情况（2）来代替，就是计算当一个特征t不能变化时，系统的信息量是多少。这个信息量其实也有专门的名称，就叫做“条件熵”，条件嘛，自然就是指“t已经固定“这个条件。但是问题接踵而至，例如一个特征X，它可能的取值有n多种，当计算条件熵而需要把它固定的时候，要把它固定在哪一个值上呢？答案是每一种可能都要固定一下，计算n个值，然后取均值才是条件熵。而取均值也不是简单的加一加然后除以n，而是要用每个值出现的概率来算平均（简单理解，就是一个值出现的可能性比较大，固定在它上面时算出来的信息量占的比重就要多一些）。因此有这样两个条
16、件熵的表达式：这是指特征X被固定为值xi时的条件熵，这是指特征X被固定时的条件熵，注意与上式在意义上的区别。从刚才计算均值的讨论可以看出来，第二个式子与第一个式子的关系就是：2.2.3 熵在信息论中，要对符号进行编码，一个符号的熵就是要表示这个符号所需要的最少二进制数位数；这是一个极限；这也是信息压缩的基础；条件熵，当两个符号之间存在某种关系，或者两个随机变量不互相独立的时候，对于A，B两个随机事件，非独立，知道A的情况，B的不确定性减少。举例来说，假设S是一个关于布尔概念的有14个样例的集合，它包括9个正例和5个反例（我们采用记号9+，5-来概括这样的数据样例），那么S相对于这个布尔样例的熵为：注意，如果S的所有成员属于同一类，例如，如果所有的成员是正的，那么p-就是0，于是； 另
