序列覆盖算法 ·序列覆盖算法 学习一个规则,移去它覆盖的数据,再重复这一过 程 假定已有一个子程序 Learn-One-Rule,它的输 入是一组正例和反例,输出是单个规则,它能 够覆盖许多正例而覆盖很少的反例 我们要求输出的规则有较高的精确度,但不必 有较高的覆盖度 2003.12.18机器学习学习规则集合作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 6 序列覆盖算法 • 序列覆盖算法 – 学习一个规则，移去它覆盖的数据，再重复这一过 程 • 假定已有一个子程序Learn-One-Rule，它的输 入是一组正例和反例，输出是单个规则，它能 够覆盖许多正例而覆盖很少的反例 • 我们要求输出的规则有较高的精确度，但不必 有较高的覆盖度
序列覆盖算法(2) 序列覆盖算法的过程 在所有可用训练样例上执行Lean-One-Rule 再移去由其学到的规则覆盖的正例 重复上面的过程,直到规则集覆盖正例达到希望的 程度 序列覆盖算法按次序学习到一组规则,它们共 同覆盖了全部正例 规则集中的规则可排序,分类新实例时可先应 用精度最高的规则 2003.12.18机器学习学习规则集合作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 7 序列覆盖算法（2） • 序列覆盖算法的过程 – 在所有可用训练样例上执行Learn-One-Rule – 再移去由其学到的规则覆盖的正例 – 重复上面的过程，直到规则集覆盖正例达到希望的 程度 • 序列覆盖算法按次序学习到一组规则，它们共 同覆盖了全部正例 • 规则集中的规则可排序，分类新实例时可先应 用精度最高的规则
表10-1学习析取规则集的序列 覆盖算法(CN2) Sequential-Covering(Target attribute, Attributes, Examples Threshold) Learned rulest RuletLearn-One-Rule Target attribute, Attributes Examples Performance(Rule, Examples)>Threshold Learned rules< Learned rules+ rule Examples∈ Examples-{被Rule正确分类的样例} Rulet-Learn-One- Rule(Target attribute, Attributes, Examples) Learned rules∈按照在 Examples上的 Performance排序的 earned rules 返 回 Learned rules 2003.12.18机器学习-学习规则集合作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 8 表10-1 学习析取规则集的序列 覆盖算法（CN2） Sequential-Covering(Target_attribute, Attributes, Examples, Threshold) • Learned_rules{} • RuleLearn-One-Rule(Target_attribute, Attributes, Examples) • 当Performance(Rule, Examples)>Threshold – Learned_rulesLearned_rules+Rule – ExamplesExamples-{被Rule正确分类的样例} – RuleLearn-One-Rule(Target_attribute, Attributes, Examples) • Learned_rules按照在Examples上的Performance排序的 Learned_rules • 返回Learned_rules
序列覆盖算法(3) 序列覆盖算法将问题化简为一系列简单 的问题,执行的是一种贪婪搜索,它不 能保证找到能覆盖样例的最小或最佳规 则集 下面重点讨论 Learn- One-Rule的设计,我 们希望算法能够得到较高精度的规则集, 但不必覆盖所有的正例 2003.12.18机器学习学习规则集合作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 9 序列覆盖算法（3） • 序列覆盖算法将问题化简为一系列简单 的问题，执行的是一种贪婪搜索，它不 能保证找到能覆盖样例的最小或最佳规 则集 • 下面重点讨论Learn-One-Rule的设计，我 们希望算法能够得到较高精度的规则集， 但不必覆盖所有的正例
般到特殊的柱状搜索 种方法是,将假设空间搜索过程设计为与ID3算法中 相似的方式,但在每一步只沿着最有希望的分支进行, 即产生最佳性能的属性-值对,而不是用增长子树的办 法覆盖所选属性的所有可能值 ·与ID3类似,可定义最佳分支,它覆盖的样例有最低的 熵 与其他贪婪算法一样,上面算法的缺陷是,它的每 步都可能做出次优的选择 用柱状搜索来减小风险,即每一步保留k个最佳候选分 支,每一步对k个候选分支进行处理,然后再将结果集 削减至k个最可能成员 2003.12.18机器学习学习规则集合作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 10 一般到特殊的柱状搜索 • 一种方法是，将假设空间搜索过程设计为与ID3算法中 相似的方式，但在每一步只沿着最有希望的分支进行， 即产生最佳性能的属性-值对，而不是用增长子树的办 法覆盖所选属性的所有可能值 • 与ID3类似，可定义最佳分支，它覆盖的样例有最低的 熵 • 与其他贪婪算法一样，上面算法的缺陷是，它的每一 步都可能做出次优的选择 • 用柱状搜索来减小风险，即每一步保留k个最佳候选分 支，每一步对k个候选分支进行处理，然后再将结果集 削减至k个最可能成员