决策树学习课件(PPT 44页).ppt

机器学习,第3讲决策树学习,内容,简介决策树原理决策树算法决策树中的过拟合问题决策树的其他问题属性的其他度量,简介,决策树也称为判定树。在决策树方法中，首先从实例集中构造决策树，这是一种有指导学习的方法。该方法先根据训练集数据形成决策树。如果该数不能对所有对象给出正确的分类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树性结构。最终结果是一棵树，其叶结点是类名，中间结点是带有分枝的属性，该分枝对应属性的某一可能值。决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散值函数的方法，对噪声数据有很好的健壮性且能够学习析取表达式。学习得到的决策树能够被再次表示为多个if-then的规则，提高可读性。这种学习算法是最流行的归纳推理算法之一，被成功的应用到从医学医疗诊断到学习评估贷款申请的信用风险的广阔领域。,决策树原理,决策树方法首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。归纳学习决策树技术发现数据模式和规则的核心是归纳算法。归纳算法是从特殊到一般的过程。归纳推理从若干个事实中表征出的特征、特性或属性中，通过比较、总结、概括而得出一个规律性的结论。归纳推理视图从对象的一部分或整体的特定观察中得到一个完备且正确的描述，即从特殊事实得出普遍规律性的结论。归纳对于认识的发展完善具有重要的意义。归纳学习的过程就是寻找一般化描述的过程。这种一般化描述能够解释给定的输入数据，并可以用来预测新的数据。归纳学习存在一个基本的假定：任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则他也能在未见样本中很好地逼近目标函数。这个假定是归纳学习的前提条件。,决策树的表示决策树的基本组成部分：决策结点、分支和子叶。决策树最上面的结点称为跟结点，是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或决策，通常对应于待分类对象的属性。每一个叶结点代表一种可能的分类结果。在沿着决策树从上到下遍历的过程中，在每个结点都会遇到一个测试，对每个节点上问题的不同测试输出导致不同的分支，最后会到达一个叶子结点。这个过程就是利用决策树进行分类的过程，利用若干个变量来判断所属的类别。,决策树表示法,决策树通过把实例从根节点排列到某个叶子节点来分类实例；叶子节点即为实例所属的分类；树上每个节点说明了对实例的某个属性的测试；节点的每个后继分支对应于该属性的一个可能值。,7,图3-1Playtennis决策树,此图为典型学习到的决策树，这棵树根据天气情况分类“星期六上午是否适合打网球”，上面的实例沿着这棵决策树的最左分支向下排列，因而被判定为反例（也就是这棵树预测这个实例Playtennis=no）。,8,图3-1对应于一下表达式,决策树代表实例属性值约束的合取的析取式从根结点到叶结点的每一条路径对应一组属性的合取，树本身对应这些合取的析取。,9,决策树学习的适用问题,适用问题的特征实例由“属性-值”对表示目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误训练数据可以包含缺少属性值的实例分类问题核心任务是把样例分类到各可能的离散值对应的类别,10,决策树算法,大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间贪心算法算法代表：ID3,11,基本的决策树学习算法（2）,ID3的思想自顶向下构造决策树从“哪一个属性将在树的根节点被测试”开始使用统计测试来确定每一个实例属性单独分类训练样例的能力ID3的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程,12,熵:物理学概念宏观上：热力学定律体系的熵变等于可逆过程吸收或耗散的热量除以它的绝对温度（克劳修斯，1865）微观上：熵是大量微观粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数（波尔兹曼，1872）结论：熵是描述事物无序性的参数，熵越大则无序性越强,在信息领域定义为“熵越大，不确定性越大”（香浓，1948年）,13,最佳分类属性,信息增益用来衡量给定的属性区分训练样例的能力ID3算法在增长树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性熵刻画了任意样例集的纯度给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为Entropy(S)=信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为Entropy(S)=,14,假设S是关于某布尔概念的有14个样例的集合，它包括9个正例和5个反例，（我们采用记号9+,5-来概括这样的数据样例）。那么S相对于这个布尔分类的熵为：,注：如果S的所有成员属于一类那么S的熵为0，例：如果所有成员都是正的（p+=1），那么p-=0,于是Entropy（S）=0，集合中正反样例相等时，熵为1，正反样例不等时，熵介于0,1之间右图显示了布尔型的分类的熵函数随着p+从01的变化曲线。,15,最佳分类属性（2）,用信息增益度量期望的熵降低属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低Gain(S,A)是在知道属性A的值后可以节省的二进制位数例子,16,S：共14个例子，其中9正、5负使用属性Wind（取值为Weak或Strong）对S进行分类：Sweak（6正、2负）、Sstrong（3正、3负）,17,谁是最佳属性？,18,ID3算法一个完整的例子,2020/6/5,19,20,决策树学习中的假设空间搜索,ID3的优势和不足假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间维护单一的当前假设（不同于变型空间候选消除算法）不进行回溯每一步使用所有的训练样例，不同于基于单独的训练样例递增作出决定，容错性增强,21,决策树学习的归纳偏置,ID3的搜索策略优先选择较短的树选择那些信息增益高的属性离根节点较近的树很难准确刻画ID3的归纳偏置近似的ID3的归纳偏置较短的树比较长的树优先局部最优实现全局最优一个精确具有这个归纳偏置的算法，BFS-ID3更贴切近似的归纳偏置较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先,22,限定偏置和优选偏置,ID3和候选消除算法的比较ID3的搜索范围是一个完整的假设空间，但不彻底地搜索这个空间候选消除算法的搜索范围是不完整的假设空间，但彻底地搜索这个空间ID3的归纳偏置完全是搜索策略排序假设的结果，来自搜索策略候选消除算法完全是假设表示的表达能力的结果，来自对搜索空间的定义,23,限定偏置和优选偏置,优选偏置ID3的归纳偏置是对某种假设胜过其他假设的一种优选，对最终可列举的假设没有硬性限制限定偏置候选消除算法的偏置是对待考虑假设的一种限定通常优选偏置比限定偏置更符合归纳学习的需要,24,为什么短的假设优先,思考：ID3算法中优先选择较短决策树的归纳偏置，是不是从训练数据中泛化的一个可靠基础？ID3的归纳偏置的哲学基础奥坎姆剃刀优先选择拟合数据的最简单的假设科学上的例子物理学家优先选择行星运动的简单假设简单假设的数量远比复杂假设的数量少，找到一个短的同时与训练数据拟合的假设可能性小。简单假设对训练样例的针对性更小，更像是泛化的规律，而不是训练样例的另一种描述,25,为什么短的假设优先,例如：考虑决策树假设，500个结点的决策树比5个结点的决策树多得多，如果给定一个20个训练样例的集合，可以预期能够找到很多500个结点的决策树与训练数据一致，而如果一个5个结点的决策树可以完美地拟合这些数据则是出乎意料的。所以我们会相信5个结点的树不太可能是统计巧合，因而优先选择这个假设，而不选择500个结点的。,26,过度拟合数据,过度拟合对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例定义：给定一个假设空间H，一个假设hH，如果存在其他的假设hH，使得在训练样例上h的错误率比h小，但在整个实例分布上h的错误率比h小，那么就说假设h过度拟合训练数据。,27,在此例中，ID3算法用来学习哪个病人患有糖尿病。横轴表示决策树结点总数，纵轴为决策树做出的预测精度。实线显示决策树在训练样例上的精度，虚线为一套独立的测试样例（没有被包括在训练样例中）上测出的精度。可以看出，随着树的增长，在训练样例上的精度是单调上升的。然而独立的测试样例上测出的精度先上升后下降。当树超过大约25个结点时，对树的进一步精化尽管可以提高它在训练数据上的精度，却降低了它在测试样例上的精度。,28,避免过度拟合数据（2）,导致过度拟合的原因训练样例含有随机错误或噪声当训练数据没有噪声时，过度拟合也有可能发生特别是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。,29,避免过度拟合数据（3）,避免过度拟合的方法及早停止树增长后修剪法两种方法的特点第一种方法更直观第一种方法中，精确地估计何时停止树增长很困难第二种方法被证明在实践中更成功,30,避免过度拟合数据（4）,避免过度拟合的关键使用什么样的准则来确定最终正确树的规模解决方法使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修建节点的效用。使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的长度最小时停止树增长。,31,避免过度拟合数据（5）,方法评述第一种方法是最普通的，常被称为训练和验证集法。可用数据分成两个样例集合：训练集合，形成学习到的假设验证集合，评估这个假设在后续数据上的精度方法的动机：即使学习器可能会被训练集合误导，但验证集合不大可能表现出同样的随机波动验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。常见的做法是，样例的三分之二作训练集合，三分之一作验证集合。,32,错误率降低修剪,将树上的每一个节点作为修剪得候选对象修剪步骤删除以此节点为根的子树，使它成为叶结点把和该节点关联的训练样例的最常见分类赋给它反复修剪节点，每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点继续修剪，直到进一步的修剪是有害的为止（降低了验证集合上的精度）,33,数据分成3个子集训练样例，形成决策树验证样例，修剪决策树测试样例，精度的无偏估计如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪,34,规则后修剪,从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则通过删除任何能导致估计精度提高的前件来修剪每一条规则按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例,35,规则后修剪（2）,例子最左边一条路径if(outlook=sunny)(Humidity=High)thenPlayTennis=No考虑删除不会降低估计精度的先行词(outlook=sunny)和(Humidity=High)来修剪规则选择使估计精度有最大提升的步骤考虑修剪第二个前件,36,规则后修剪（3）,把决策树转化成规则集的好处可以区分决策节点使用的不同上下文消除了根节点附近的属性测试和叶节点附近的属性测试的区别提高了可读性,37,决策树学习的其他常见问题,决策树学习的实际问题处理连续值的属性选择一个适当的属性筛选度量标准信息增益度量存在一个内在偏置，偏向具有较多值的属性处理属性值不完整的训练数据处理不同代价的属性提高计算效率针对这些问题，ID3被扩展成C4.5,38,合并连续值属性,ID3被限制为取离散值的属性学习到的决策树要预测的目标属性必须是离散的树的决策节点的属性也必须是离散的简单删除上面第2个限制的方法通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合,39,合并连续值属性（2）,例子，Temperature应该定义什么样的基于阈值的布尔属性选择产生最大信息增益的阈值按照连续属性排列样例，确定目标分类不同的相邻实例产生一组候选阈值，它们的值是相应的A值之间的中间值可以证明产生最大信息增益的c值位于这样的边界中（Fayyad1991）通过计算与每个候选阈值关联的信息增益评估这些候选值方法的扩展连续的属性分割成多个区间，而不是单一阈值的两个空间,40,属性选择的其他度量标准,信息增益度量存在一个内在偏置，偏向具有较多值的属性避免方法，其他度量，比如增益比率增益比率通过加入一个被称作分裂信息的项来惩罚多值属性，分裂信息用来衡量属性分裂数据的广度和均匀性SplitInformation(S,A)=GainRatio(S,A)=分裂信息项阻碍选择值为均匀分布的属性问题，当某个SiS。解决方法：采用一些启发式规则，比如仅对增益高过平均值的属性应用增益比率测试,41,属性选择的其他度量标准（2）,基于距离的度量定义了数据划分间的一种距离尺度计算每个属性产生的划分与理想划分间的距离选择最接近完美划分的属性LopezdeMantaras定义了这个距离度量，证明了它不偏向有大量值的属性此外Mingers实验，不同的属性选择度量对最终精度的影响小于后修剪得程度和方