ID3算法举例 表3-2 继续这个过程,直到满足以下两个条件中的 所有的属性已经被这条路经包括 与这个节点关联的所有训练样例都具有相同的目 标属性值 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 11 ID3算法举例 • 表3-2 – … – 继续这个过程，直到满足以下两个条件中的 一个 • 所有的属性已经被这条路经包括 • 与这个节点关联的所有训练样例都具有相同的目 标属性值
决策树学习中的假设空间搜索 观察ID3的搜索空间和搜索策略,认识到 这个算法的优势和不足 假设空间包含所有的决策树,它是关于现有 属性的有限离散值函数的一个完整空间 维护单一的当前假设(不同于第二章的变型 空间候选消除算法) 不进行回溯,可能收敛到局部最优 每一步使用所有的训练样例,不同于基于单 独的训练样例递增作岀决定,容错性增强 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏 12
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 12 决策树学习中的假设空间搜索 • 观察ID3的搜索空间和搜索策略，认识到 这个算法的优势和不足 – 假设空间包含所有的决策树，它是关于现有 属性的有限离散值函数的一个完整空间 – 维护单一的当前假设（不同于第二章的变型 空间候选消除算法） – 不进行回溯，可能收敛到局部最优 – 每一步使用所有的训练样例，不同于基于单 独的训练样例递增作出决定，容错性增强
决策树学习的归纳偏置 D3的搜索策略 优先选择较短的树 选择那些信息增益高的属性离根节点较近的树 很难准确刻画ⅠD3的归纳偏置 近似的3的归纳偏置 较短的树比较长的树优先 近似在于ID3得到局部最优,而不一定是全局最优 一个精确具有这个归纳偏置的算法,BFS-ID3 更贴切近似的归纳偏置 较短的树比较长的树优先,信息增益高的属性更靠 2031J近根卓的树犹先者曾华军等作者:Mhe讲者:陶晓鹏 13
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 13 决策树学习的归纳偏置 • ID3的搜索策略 – 优先选择较短的树 – 选择那些信息增益高的属性离根节点较近的树 – 很难准确刻画ID3的归纳偏置 • 近似的ID3的归纳偏置 – 较短的树比较长的树优先 – 近似在于ID3得到局部最优，而不一定是全局最优 – 一个精确具有这个归纳偏置的算法，BFS-ID3 • 更贴切近似的归纳偏置 – 较短的树比较长的树优先，信息增益高的属性更靠 近根节点的树优先