机器学习-学习规则集合.ppt

《机器学习-学习规则集合.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、机器学习第10章学习规则集合2003.12.181机器学习-学习规则集合作者：Mitchell译者：曾华军等讲者：陶晓鹏概述对学习到的假设，最具有表征力的和最能为人类所理解的表示方法之一是if-then规则的集合本章探索若干能学习这样的规则集合的算法其中，最重要的是学习包含变量的规则集合，或称一阶Horn子句集合由于一阶Horn子句集合可被解释为逻辑编程语言Prolog中的程序，学习的过程常被称为归纳逻辑编程本章考察了多种学习规则集合的途径，其中一种是基于机器定理证明器中演绎算子的逆转2003.12.182机器学习-学习规则集合作者：Mitchell译

2、者：曾华军等讲者：陶晓鹏简介在许多情况下，有必要学习一个由若干if-then规则共同定义的目标函数，比如决策树遗传算法本章我们讨论一组不同的算法，它们直接学习规则集合，与前面算法有两点关键的不同可学习包含变量的一阶规则集合（一阶子句的表达能力比命题规则要强得多）使用序列覆盖算法，一次学习一个规则，以递增的方式形成最终的规则集合2003.12.183机器学习-学习规则集合作者：Mitchell译者：曾华军等讲者：陶晓鹏简介（2）一阶规则集合的例子ifParent(x,y)thenAncestor(x,y)ifParent(x,z)Ancestor(z,

3、y)thenAncestor(x,y)这个规则集合很紧凑地描述了一个递归函数，它很难用决策树或其他命题的方法来表示Prolog程序就是一阶规则的集合，因此一个可以学习这种规则集合的通用算法，可被看作是从样例中自动推导出Prolog程序的算法一阶表示的学习系统在实践中的应用在质谱仪中学习哪一个化学药品能粘合碎片学习哪一个化学亚结构会产生诱导有机体突变的放射性物质学习有限单元网以分析物理结构中的应力2003.12.184机器学习-学习规则集合作者：Mitchell译者：曾华军等讲者：陶晓鹏内容安排先介绍能够学习命题规则集的算法（命题规则可看作不含变量的一阶

4、规则），算法搜寻假设空间学习析取规则集合将上面算法扩展到一阶规则讨论归纳逻辑的两种通用途径以及归纳和演绎推理的基本关系2003.12.185机器学习-学习规则集合作者：Mitchell译者：曾华军等讲者：陶晓鹏序列覆盖算法序列覆盖算法学习一个规则，移去它覆盖的数据，再重复这一过程假定已有一个子程序Learn-One-Rule，它的输入是一组正例和反例，输出是单个规则，它能够覆盖许多正例而覆盖很少的反例我们要求输出的规则有较高的精确度，但不必有较高的覆盖度2003.12.186机器学习-学习规则集合作者：Mitchell译者：曾华军等讲者：陶晓鹏序列覆盖

5、算法（2）序列覆盖算法的过程在所有可用训练样例上执行Learn-One-Rule再移去由其学到的规则覆盖的正例重复上面的过程，直到规则集覆盖正例达到希望的程度序列覆盖算法按次序学习到一组规则，它们共同覆盖了全部正例规则集中的规则可排序，分类新实例时可先应用精度最高的规则2003.12.187机器学习-学习规则集合作者：Mitchell译者：曾华军等讲者：陶晓鹏表10-1学习析取规则集的序列覆盖算法（CN2）Sequential-Covering(Target_attribute,Attributes,Examples,Threshold)Learned

6、_rules{}RuleLearn-One-Rule(Target_attribute,Attributes,Examples)当Performance(Rule,Examples)>ThresholdLearned_rulesLearned_rules+RuleExamplesExamples-{被Rule正确分类的样例}RuleLearn-One-Rule(Target_attribute,Attributes,Examples)Learned_rules按照在Examples上的Performance排序的Learned_rules返

7、回Learned_rules2003.12.188机器学习-学习规则集合作者：Mitchell译者：曾华军等讲者：陶晓鹏序列覆盖算法（3）序列覆盖算法将问题化简为一系列简单的问题，执行的是一种贪婪搜索，它不能保证找到能覆盖样例的最小或最佳规则集下面重点讨论Learn-One-Rule的设计，我们希望算法能够得到较高精度的规则集，但不必覆盖所有的正例2003.12.189机器学习-学习规则集合作者：Mitchell译者：曾华军等讲者：陶晓鹏一般到特殊的柱状搜索一种方法是，将假设空间搜索过程设计为与ID3算法中相似的方式，但在每一步只沿着最有希望的分支进行

8、，即产生最佳性能的属性-值对，而不是用增长子树的办法覆盖所选属性的所有可能值与ID3类似，可定