人工智能课件-决策树学习.pptVIP

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