决策树学习-机器学习

机器学习第3章决策树学习1概论决策树学习是应用最广的归纳推理算法之一是一种逼近离散值函数的方法很好的健壮性能够学习析取表达式ID3,Assistant,C4.5搜索一个完整表示的假设空间归纳偏置是优先选择较小的树决策树表示了多个if-then规则2提纲决策树定义适用问题特征基本ID3算法决策树学习的归纳偏置训练数据的过度拟合更深入的话题3决策树表示法决策树通过把实例从根节点排列到某个叶子节点来分类实例。叶子节点即为实例所属的分类树上每个节点说明了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值图3-1决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。4决策树学习的适用问题适用问题的特征实例由“属性-值”对表示目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误训练数据可以包含缺少属性值的实例问题举例根据疾病分类患者根据起因分类设备故障根据拖欠支付的可能性分类贷款申请分类问题核心任务是把样例分类到各可能的离散值对应的类别5基本的决策树学习算法大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3是这种算法的代表6基本的决策树学习算法（2）ID3的思想自顶向下构造决策树从“哪一个属性将在树的根节点被测试”开始使用统计测试来确定每一个实例属性单独分类训练样例的能力ID3的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程7表3-1用于学习布尔函数的ID3算法概要ID3(Examples,Target_attribute,Attributes)创建树的root节点如果Examples都为正,返回label=+的单节点树root如果Examples都为反,返回label=-的单节点树root如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值否则开始AAttributes中分类examples能力最好的属性root的决策属性A对于A的每个可能值vi在root下加一个新的分支对应测试A=vi令Examplesvi为Examples中满足A属性值为vi的子集如果Examplesvi为空在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-{A}）结束返回root8最佳分类属性信息增益用来衡量给定的属性区分训练样例的能力ID3算法在增长树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性熵刻画了任意样例集的纯度给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为 Entropy(S)=-p+log2p+-p-log2p-信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为 Entropy(S)=9最佳分类属性（2）用信息增益度量期望的熵降低属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低

Gain(S,A)是在知道属性A的值后可以节省的二进制位数例子10ID3算算法法举举例例表3-2…继续这个个过程，，直到满满足以下下两个条条件中的的一个所有的属属性已经经被这条条路经包包括与这个节节点关联联的所有有训练样样例都具具有相同同的目标标属性值值11决策树学学习中的的假设空空间搜索索观察ID3的搜搜索空间间和搜索索策略，，认识到到这个算算法的优优势和不不足假设空间间包含所所有的决决策树，，它是关关于现有有属性的的有限离离散值函函数的一一个完整整空间维护单一一的当前前假设（（不同于于第二章章的变型型空间候候选消除除算法））不进行回回溯，可可能收敛敛到局部部最优每一步使使用所有有的训练练样例，，不同于于基于单单独的训训练样例例递增作作出决定定，容错错性增强强12决策树学学习的归归纳偏置置ID3的的搜索策策略优先选择择较短的的树选择那些些信息增增益高的的属性离离根节点点较近的的树很难准确确刻画ID3的的归纳偏偏置近似的ID3的的归纳偏偏置较短的树树比较长长的树优优先近似在于于ID3得到局局部最优优，而不不一定是是全局最最优一个精确确具有这这个归纳纳偏置的的算法，，BFS-ID3更贴切近近似的归归纳偏置置较短的树树比较长长的树优优先，信信息增益益高的属属性更靠靠近根节节点的树树优先13限定偏置置和优选选偏置ID3和和候选消消除算法法的比较较ID3的的搜索范范围是一一个完整整的假设设空间，，但不彻彻底地搜搜索这个个空间候选消除除算法的的搜索范范围是不不完整的的假设空空间，但但彻底地地搜索这这个空间间ID3的的归纳偏偏置完全全是搜索索策略排排序假设设的结果果，来自自搜索策策略候选消除除算法完完全是假假设表示示的表达达能力的的结果，，来自对对搜索空空间的定定义14限定偏置置和优选选偏置优选偏置置ID3的的归纳偏偏置是对对某种假假设胜过过其他假假设的一一种优选选，对最最终可列列举的假假设没有有硬性限限制限定偏置置候选消除除算法的的偏置是是对待考考虑假设设的一种种限定通常优选选偏置比比限定偏偏置更符符合归纳纳学习的的需要优选偏置置和限定定偏置的的结合考虑第1章的例例子15为什么短短的假设设优先ID3的的归纳偏偏置的哲哲学基础础奥坎姆剃剃刀优先选择择拟合数数据的最最简单的的假设科学上的的例子物理学家家优先选选择行星星运动的的简单假假设简单假设设的数量量远比复复杂假设设的数量量少简单假设设对训练练样例的的针对性性更小，，更像是是泛化的的规律，，而不是是训练样样例的另另一种描描述16为什么短短的假设设优先奥坎姆剃剃刀的困困难我们反问问，使用用上页的的推理，，应该优优先选择择包含恰恰好17个叶子子节点和和11个个非叶子子节点的的决策树树？假设的规规模由学学习器内内部使用用的特定定表示决决定从生物进进化的观观点看内内部表示示和奥坎坎姆剃刀刀原则17决策树学学习的常常见问题题决策树学学习的实实际问题题确定决策策树增长长的深度度处理连续续值的属属性选择一个个适当的的属性筛筛选度量量标准处理属性性值不完完整的训训练数据据处理不同同代价的的属性提高计算算效率针对这些些问题，，ID3被扩展展成C4.518避免过度度拟合数数据过度拟合合对于一个个假设，，当存在在其他的的假设对对训练样样例的拟拟合比它它差，但但事实上上在实例例的整个个分布上上表现得得却更好好时，我我们说这这个假设设过度拟拟合训练练样例定义：给给定一个个假设空空间H，，一个假假设hH，如果果存在其其他的假假设h’’H，使得得在训练练样例上上h的错错误率比比h’小小，但在在整个实实例分布布上h’’的错误误率比h小，那那么就说说假设h过度拟拟合训练练数据。。图3-6的例子子19避免过度度拟合数数据（2）导致过度度拟合的的原因一种可能能原因是是训练样样例含有有随机错错误或噪噪声当训练数数据没有有噪声时时，过度度拟合也也有可能能发生，，特别是是当少量量的样例例被关联联到叶子子节点时时，很可可能出现现巧合的的规律性性，使得得一些属属性恰巧巧可以很很好地分分割样例例，但却却与实际际的目标标函数并并无关系系。20避免过度度拟合数数据（3）避免过度度拟合的的方法及早停止止树增长长后修剪法法两种方法法的特点点第一种方方法更直直观第一种方方法中，，精确地地估计何何时停止止树增长长很困难难第二种方方法被证证明在实实践中更更成功21避免过度度拟合数数据（4）避免过度度拟合的的关键使用什么么样的准准则来确确定最终终正确树树的规模模解决方法法使用与训训练样例例截然不不同的一一套分离离的样例例，来评评估通过过后修剪剪方法从从树上修修建节点点的效用用。使用所有有可用数数据进行行训练，，但进行行统计测测试来估估计扩展展（或修修剪）一一个特定定的节点点是否有有可能改改善在训训练集合合外的实实例上的的性能。。使用一个个明确的的标准来来衡量训训练样例例和决策策树的复复杂度，，当这个个编码的的长度最最小时停停止树增增长。22避免过度度拟合数数据（5）方法评述述第一种方方法是最最普通的的，常被被称为训训练和验验证集法法。可用数据据分成两两个样例例集合：：训练集合合，形成成学习到到的假设设验证集合合，评估估这个假假设在后后续数据据上的精精度方法的动动机：即即使学习习器可能能会被训训练集合合误导，，但验证证集合不不大可能能表现出出同样的的随机波波动验证集合合应该足足够大，，以便它它本身可可提供具具有统计计意义的的实例样样本。常见的做做法是，，样例的的三分之之二作训训练集合合，三分分之一作作验证集集合。23错误率降降低修剪剪将树上的的每一个个节点作作为修剪剪得候选选对象修剪步骤骤删除以此此节点为为根的子子树，使使它成为为叶结点点把和该节节点关联联的训练练样例的的最常见见分类赋赋给它反复修剪剪节点，，每次总总是选取取那些删删除后可可以最大大提高决决策树在在验证集集合上的的精度的的节点继续修剪剪，直到到进一步步的修剪剪是有害害的为止止数据分成成3个子子集训练样例例，形成成决策树树验证样例例，修剪剪决策树树测试样例例，精度度的无偏偏估计如果有大大量的数数据可供供使用，，那么使使用分离离的数据据集合来来引导修修剪24规则后后修剪剪从训练练集合合推导导出决决策树树，增增长决决策树树直到到尽可可能好好地拟拟合训训练数数据，，允许许过度度拟合合发生生将决策策树转转化为为等价价的规规则集集合，，方法法是为为从根根节点点到叶叶节点点的每每一条条路径径创建建一条条规则则通过删删除任任何能能导致致估计计精度度提高高的前前件来来修剪剪每一一条规规则按照修修剪过过的规规则的的估计计精度度对它它们进进行排排序，，并按按这样样的顺顺序应应用这这些规规则来来分类类后来来的实实例25规则后后修剪剪（2）例子图3-1的的最左左一条条路径径if(outlook=sunny)(Humidity=High)thenPlayTennis=No考虑删删除先先行词词(outlook=sunny)和(Humidity=High)选择使使估计计精度度有最最大提提升的的步骤骤考虑修修剪第第二个个前件件26规则后后修剪剪（3）规则精精度估估计方方法使用与与训练练集不不相交交的验验证集集基于训训练集集合本本身被C4.5使用用，使使用一一种保保守估估计来来弥补补训练练数据据有利利于当当前规规则的的估计计偏置置过程先计算算规则则在它它应用用的训训练样样例上上的精精度然后假假定此此估计计精度度为二二项式式分布布，并并计算算它的的标准准差对于一一个给给定的的置信信区间间，采采用下下界估估计作作为规规则性性能的的度量量评论对于大大的数数据集集，保保守预预测非非常接接近观观察精精度，，随着着数据据集合合的减减小，，离观观察精精度越越来越越远不是统统计有有效（（此概概念第第5章章介绍绍），，但是是实践践中发发现有有效27规则后后修剪剪（4）把决策策树转转化成成规则则集的的好处处可以区区分决决策节节点使使用的的不同同上下下文消除了了根节节点附附近的的属性性测试试和叶叶节点点附近近的属属性测测试的的区别别提高了了可读读性28合并连连续值值属性性ID3被限限制为为取离离散值值的属属性学习到到的决决策树树要预预测的的目标标属性性必须须是离离散的的树的决决策节节点的的属性性也必必须是是离散散的简单删删除上上面第第2个个限制制的方方法通过动态地地定义新的的离散值属属性来实现现，即先把把连续值属属性的值域域分割为离离散的区间间集合29合并连续值值属性（2）例子，Temperature应该定定义什么样样的基于阈阈值的布尔尔属性选择产生最最大信息增增益的阈值值按照连续属属性排列样样例，确定定目标分类类不同的相相邻实例产生一组候候选阈值，，它们的值值是相应的的A值之间间的中间值值可以证明产产生最大信信息增益的的c值位于于这样的边边界中（Fayyad1991）通过计算与与每个候选选阈值关联联的信息增增益评估这这些候选值值方法的扩展展连续的属性性分割成多多个区间，，而不是单单一阈值的的两个空间间30属性选择的的其他度量量标准信息增益度度量存在一一个内在偏偏置，偏向向具有较多多值的属性性避免方法，，其他度量量，比如增增益比率增益比率通通过加入一一个被称作作分裂信息息的项来惩惩罚多值属属性，分裂裂信息用来来衡量属性性分裂数据据的广度和和均匀性SplitInformation(S,A)=GainRatio(S,A)=分裂信息项项阻碍选择择值为均匀匀分布的属属性问题，当某某个SiS。解决方方法：采用用一些启发发式规则，，比如仅仅对增益高高过平均值值的属性应应用增益比比率测试31属性选择的的其他度量量标准（2）基于距离的的度量定义了数据据划分间的的一种距离离尺度计算每个属属性产生的的划分与理理想划分间间的距离选择最接近近完美划分分的属性LopezdeMantaras定义了这这个距离度度量，证明明了它不偏偏向有大量量值的属性性此外Mingers实验验，不同的的属性选择择度量对最最终精度的的影响小于于后修剪得得程度和方方法的影响响32缺少属性值值的训练样样例例子，医学学领域经常需要根根据此属性性值已知的的实例来估估计这个缺缺少的属性性值为了评估属属性A是否否是决策节节点n的最最佳测试属属性，要计计算决策树树在该节点点的信息增增益Gain(S,A)。假假定<x,c(x)>是S中中的一个训训练样例，，并且其属属性A的值值A(x)未知33缺少属性值值的训练样样例（2））处理缺少属属性值的一种策略是是赋给它节节点n的训训练样例中中该属性的的最常见值值另一种策略略是赋给它它节点n的的被分类为为c(x)的训练样样例中该属属性的最常常见值更复杂的策策略，为A的每