《人工智能机器学习专业课件.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《人工智能机器学习专业课件.优秀PPT.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、机器学习第3章 决策树学习2003.11.181机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏概论决策树学习是应用最广的归纳推理算法之一是一种靠近离散值函数的方法很好的健壮性能够学习析取表达式ID3,Assistant,C4.5搜寻一个完整表示的假设空间归纳偏置是优先选择较小的树决策树表示了多个if-then规则2003.11.182机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏提纲决策树定义适用问题特征基本ID3算法决策树学习的归纳偏置训练数据的过度拟合更深化的话题2003.11.183机器学习-决策树学习 译者：曾华军等 作者：Mit
2、chell 讲者：陶晓鹏决策树表示法决策树通过把实例从根节点排列到某个叶子节点来分类实例。叶子节点即为实例所属的分类树上每个节点说明白对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值图3-1决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。2003.11.184机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏决策树学习的适用问题适用问题的特征实例由“属性-值”对表示目标函数具有离散的输出值可能须要析取的描述训练数据可以包含错误训练数据可以包含缺少属性值的实例问题举例依据疾病分类患者依据起因
3、分类设备故障依据拖欠支付的可能性分类贷款申请分类问题核心任务是把样例分类到各可能的离散值对应的类别2003.11.185机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏基本的决策树学习算法大多数决策树学习算法是一种核心算法的变体接受自顶向下的贪欲搜寻遍历可能的决策树空间ID3是这种算法的代表2003.11.186机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏基本的决策树学习算法（2）ID3的思想自顶向下构造决策树从“哪一个属性将在树的根节点被测试”起先运用统计测试来确定每一个实例属性单独分类训练样例的实力ID3的过程分类实力最好的属性被选作
4、树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程2003.11.187机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏表3-1 用于学习布尔函数的ID3算法概要ID3(Examples,Target_attribute,Attributes)创建树的root节点假如Examples都为正,返回label=+的单节点树root假如Examples都为反,返回label=-的单节点树root假如Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值否则起先AAttribute
5、s中分类examples实力最好的属性root的决策属性A对于A的每个可能值vi在root下加一个新的分支对应测试A=vi令Examplesvi为Examples中满足A属性值为vi的子集假如Examplesvi为空在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-A）结束返回root2003.11.188机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏最佳分类属性信息增益用来衡量给定的属性区分训练样例
6、的实力ID3算法在增长树的每一步运用信息增益从候选属性中选择属性用熵度量样例的均一性熵刻画了随意样例集的纯度给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为Entropy(S)=-p+log2p+-p-log2p-信息论中对熵的一种说明，熵确定了要编码集合S中随意成员的分类所须要的最少二进制位数更一般地，假如目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为 Entropy(S)=2003.11.189机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏最佳分类属性（2）用信息增益度量期望的熵降低属性的信息增益，由于运用这个属性分割
7、样例而导致的期望熵降低 Gain(S,A)是在知道属性A的值后可以节约的二进制位数例子2003.11.1810机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏ID3算法举例表3-2接着这个过程，直到满足以下两个条件中的一个全部的属性已经被这条路经包括与这个节点关联的全部训练样例都具有相同的目标属性值2003.11.1811机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏决策树学习中的假设空间搜寻视察ID3的搜寻空间和搜寻策略，相识到这个算法的优势和不足假设空间包含全部的决策树，它是关于现有属性的有限离散值函数的一个完整空间维护单一的当前假设（
8、不同于其次章的变型空间候选消退算法）不进行回溯，可能收敛到局部最优每一步运用全部的训练样例，不同于基于单独的训练样例递增作出确定，容错性增加2003.11.1812机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏决策树学习的归纳偏置ID3的搜寻策略优先选择较短的树选择那些信息增益高的属性离根节点较近的树很难精确刻画ID3的归纳偏置近似的ID3的归纳偏置较短的树比较长的树优先近似在于ID3得到局部最优，而不确定是全局最优一个精确具有这个归纳偏置的算法，BFS-ID3更贴切近似的归纳偏置较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先2003.11.1813机
9、器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏限定偏置和优选偏置ID3和候选消退算法的比较ID3的搜寻范围是一个完整的假设空间，但不彻底地搜寻这个空间候选消退算法的搜寻范围是不完整的假设空间，但彻底地搜寻这个空间ID3的归纳偏置完全是搜寻策略排序假设的结果，来自搜寻策略候选消退算法完全是假设表示的表达实力的结果，来自对搜寻空间的定义2003.11.1814机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏限定偏置和优选偏置优选偏置ID3的归纳偏置是对某种假设赛过其他假设的一种优选，对最终可列举的假设没有硬性限制限定偏置候选消退算法的偏置是对待考
10、虑假设的一种限定通常优选偏置比限定偏置更符合归纳学习的须要优选偏置和限定偏置的结合考虑第1章的例子2003.11.1815机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏为什么短的假设优先ID3的归纳偏置的哲学基础奥坎姆剃刀优先选择拟合数据的最简洁的假设科学上的例子物理学家优先选择行星运动的简洁假设简洁假设的数量远比困难假设的数量少简洁假设对训练样例的针对性更小，更像是泛化的规律，而不是训练样例的另一种描述2003.11.1816机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏为什么短的假设优先奥坎姆剃刀的困难我们反问，运用上页的推理，应当优
11、先选择包含恰好17个叶子节点和11个非叶子节点的决策树？假设的规模由学习器内部运用的特定表示确定从生物进化的观点看内部表示和奥坎姆剃刀原则2003.11.1817机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏决策树学习的常见问题决策树学习的实际问题确定决策树增长的深度处理连续值的属性选择一个适当的属性筛选度量标准处理属性值不完整的训练数据处理不同代价的属性提高计算效率针对这些问题，ID3被扩展成C4.52003.11.1818机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏避开过度拟合数据过度拟合对于一个假设，当存在其他的假设对训练样例的拟
12、合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例定义：给定一个假设空间H，一个假设hH，假如存在其他的假设hH，使得在训练样例上h的错误率比h小，但在整个实例分布上h的错误率比h小，那么就说假设h过度拟合训练数据。图3-6的例子 2003.11.1819机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏避开过度拟合数据（2）导致过度拟合的缘由一种可能缘由是训练样例含有随机错误或噪声当训练数据没有噪声时，过度拟合也有可能发生，特殊是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标
13、函数并无关系。2003.11.1820机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏避开过度拟合数据（3）避开过度拟合的方法及早停止树增长后修剪法两种方法的特点第一种方法更直观第一种方法中，精确地估计何时停止树增长很困难其次种方法被证明在实践中更成功2003.11.1821机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏避开过度拟合数据（4）避开过度拟合的关键运用什么样的准则来确定最终正确树的规模解决方法运用与训练样例迥然不同的一套分别的样例，来评估通过后修剪方法从树上修建节点的效用。运用全部可用数据进行训练，但进行统计测试来估计扩展（或修
14、剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。运用一个明确的标准来衡量训练样例和决策树的困难度，当这个编码的长度最小时停止树增长。2003.11.1822机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏避开过度拟合数据（5）方法评述第一种方法是最一般的，常被称为训练和验证集法。可用数据分成两个样例集合：训练集合，形成学习到的假设验证集合，评估这个假设在后续数据上的精度方法的动机：即使学习器可能会被训练集合误导，但验证集合不大可能表现出同样的随机波动验证集合应当足够大，以便它本身可供应具有统计意义的实例样本。常见的做法是，样例的三分之二作训练集合，三分之一
15、作验证集合。2003.11.1823机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏错误率降低修剪将树上的每一个节点作为修剪得候选对象修剪步骤删除以此节点为根的子树，使它成为叶结点把和该节点关联的训练样例的最常见分类赋给它反复修剪节点，每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点接着修剪，直到进一步的修剪是有害的为止数据分成3个子集训练样例，形成决策树验证样例，修剪决策树测试样例，精度的无偏估计假如有大量的数据可供运用，那么运用分别的数据集合来引导修剪2003.11.1824机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏
16、规则后修剪从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则通过删除任何能导致估计精度提高的前件来修剪每一条规则依据修剪过的规则的估计精度对它们进行排序，并按这样的依次应用这些规则来分类后来的实例2003.11.1825机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏规则后修剪（2）例子图3-1的最左一条路径if(outlook=sunny)(Humidity=High)then PlayTennis=No考虑删除先行词(outlook=sunny)和(Humid
17、ity=High)选择使估计精度有最大提升的步骤考虑修剪其次个前件2003.11.1826机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏规则后修剪（3）规则精度估计方法运用与训练集不相交的验证集基于训练集合本身被C4.5运用，运用一种保守估计来弥补训练数据有利于当前规则的估计偏置过程先计算规则在它应用的训练样例上的精度然后假定此估计精度为二项式分布，并计算它的标准差对于一个给定的置信区间，接受下界估计作为规则性能的度量评论对于大的数据集，保守预料特殊接近视察精度，随着数据集合的减小，离视察精度越来越远不是统计有效（此概念第5章介绍），但是实践中发觉有效2003.11
18、.1827机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏规则后修剪（4）把决策树转化成规则集的好处可以区分决策节点运用的不同上下文消退了根节点旁边的属性测试和叶节点旁边的属性测试的区分提高了可读性2003.11.1828机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏合并连续值属性ID3被限制为取离散值的属性学习到的决策树要预料的目标属性必需是离散的树的决策节点的属性也必需是离散的简洁删除上面第2个限制的方法通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合2003.11.1829机器学习-决策树学习 译者：曾华
19、军等 作者：Mitchell 讲者：陶晓鹏合并连续值属性（2）例子，Temperature应当定义什么样的基于阈值的布尔属性选择产生最大信息增益的阈值依据连续属性排列样例，确定目标分类不同的相邻实例产生一组候选阈值，它们的值是相应的A值之间的中间值可以证明产生最大信息增益的c值位于这样的边界中（Fayyad1991）通过计算与每个候选阈值关联的信息增益评估这些候选值方法的扩展连续的属性分割成多个区间，而不是单一阈值的两个空间2003.11.1830机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏属性选择的其他度量标准信息增益度量存在一个内在偏置，偏向具有较多值的属性避
20、开方法，其他度量，比如增益比率增益比率通过加入一个被称作分裂信息的项来惩处多值属性，分裂信息用来衡量属性分裂数据的广度和匀整性SplitInformation(S,A)=GainRatio(S,A)=分裂信息项阻碍选择值为匀整分布的属性问题，当某个SiS。解决方法：接受一些启发式规则，比如仅对增益高过平均值的属性应用增益比率测试2003.11.1831机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏属性选择的其他度量标准（2）基于距离的度量定义了数据划分间的一种距离尺度计算每个属性产生的划分与志向划分间的距离选择最接近完备划分的属性Lopez de Mantaras定
21、义了这个距离度量，证明白它不偏向有大量值的属性此外Mingers试验，不同的属性选择度量对最终精度的影响小于后修剪得程度和方法的影响2003.11.1832机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏缺少属性值的训练样例例子，医学领域常常须要依据此属性值已知的实例来估计这个缺少的属性值为了评估属性A是否是决策节点n的最佳测试属性，要计算决策树在该节点的信息增益Gain(S,A)。假定是S中的一个训练样例，并且其属性A的值A(x)未知2003.11.1833机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏缺少属性值的训练样例（2）处理缺少属
22、性值的一种策略是赋给它节点n的训练样例中该属性的最常见值另一种策略是赋给它节点n的被分类为c(x)的训练样例中该属性的最常见值更困难的策略，为A的每个可能值赐予一个概率，而不是简洁地将最常见的值赋给A(x)2003.11.1834机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏处理不同代价的属性实例的属性可能与代价相关优先选择尽可能运用低代价属性的决策树，仅当须要产生牢靠的分类时才依靠高代价属性通过引入一个代价项到属性选择度量中，可以使ID3算法考虑属性代价Tan和Schlimmer的例子2003.11.1835机器学习-决策树学习 译者：曾华军等 作者：Mitche
23、ll 讲者：陶晓鹏小结和补充读物决策树学习为概念学习和学习其他离散值的函数供应了一个好用的方法ID3算法贪欲算法从根向下推断决策树搜寻完整的假设空间归纳偏置，较小的树过度拟合问题ID3算法的扩展2003.11.1836机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏小结和补充读物（2）HuntQuinlanMingers2003.11.1837机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏附录C4.5 is a software extension of the basic ID3 algorithm designed by Quinlan
24、 to address the following issues not dealt with by ID3:Avoiding overfitting the data Determining how deeply to grow a decision tree.Reduced error pruning.Rule post-pruning.Handling continuous attributes.e.g.,temperature Choosing an appropriate attribute selection measure.Handling training data with missing attribute values.Handling attributes with differing costs.Improving computational efficiency.2003.11.1838机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏