foil算法的可视化演示和领域定制

《foil算法的可视化演示和领域定制》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、FOIL算法的可视化演示和领域定制1FOIL算法综述FOIL由Quinlan于1989年开发，采用自上而下的算法。在一个既有正又有反的事实的训练集中，先找出一个只覆盖正例而不涉及反例的逻辑子句(clause)，然后把这个子句覆盖的事实从训练集中删除。如此直到训练集中没有正例为止。FOIL是较早的序列覆盖和learn-one-rule算法在一阶表示上的自然扩展。在FOIL与序列覆盖和learn-one-rule算法之间有两个最实质的不同，它来源于此算法对一阶规则处理的需求。形式化地讲，由FOIL学习的假设为一阶规则集，其中的规则类似于Horn子句，但有两个不同：首先由FOIL学习的规则比一般

2、的Horn子句更受限，因为文字不允许包含函数符号（这减小了假设空间搜索的复杂度）。其次，FOIL规则比Horn子句更有表征力，因为规则体中的文字也可为负文字。FOIL已被应用于多种问题领域。例如，它已用于学习快速排序算法Quicksort的递归定义，以及学习从合法棋盘状态中区分出非法状态。下面我们先介绍主要的一些相关知识和算法。1.1基本的决策树学习算法大多数已开发的决策树学习算法是一种核心算法的变体。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。这种方法是ID3算法（Quinlan1986）和后继的C4.5算法（Quinlan1993）的基础。下面将给出决策树学习的基本算法，大致相当

3、于ID3算法。基本的ID3算法通过自顶向下构造决策树来进行学习。构造过程是从“哪一个属性将在树的根结点被测试？”这个问题开始的。为了回答这个问题，使用统计测试来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性被选作树的根结点的测试。然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是，样例的该属性值对应的分支）之下。然后重复整个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。这形成了对合格决策树的贪婪搜索（greedysearch），也就是算法从不回溯重新考虑以前的选择。下表描述了该算法的一个简化版本——专门用来学习布尔值函数（即概念学

4、习）。表1-1专用于学习布尔函数的ID3算法概要ID3是一种自顶向下增长树的贪婪算法，在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都使用过了。ID3(Examples，Target_attribute，Attributes)Examples即训练样例集。Target_attribute是这棵树要预测的目标属性。Attributes是除目标属性外供学习到的决策树测试的属性列表。返回能正确分类给定Examples的决策树。l创建树的Root结点l如果Examples都为正，那么返回label=+的单结点树Rootl如果Examples都为反，那么

5、返回label=-的单结点树Rootl如果Attributes为空，那么返回单结点树Root，label=Examples中最普遍的Target_attribute值l否则lA←Attributes中分类Examples能力最好*的属性lRoot的决策属性←Al对于A的每个可能值vil在Root下加一个新的分支对应测试A=vil令为Examples中满足A属性值为vi的子集l如果为空l在这个新分支下加一个叶子结点，结点的label=Examples中最普遍的Target_attribute值l否则在这个新分支下加一个子树ID3（,Target_attribute,Attributes-{A

6、}）l结束l返回Root*根据公式的定义，具有最高信息增益（informationgain）的属性是最好的属性。1.2序列覆盖算法序列覆盖算法它的学习规则集的策略为：学习一个规则，移去它覆盖的数据，再重复这一过程。这样的算法被称为序列覆盖（sequentialcovering）算法。想象我们已有了一个子程序learn-one-rule，它的输入为一组正例和反例，然后输出单个规则，它能够覆盖许多正例，并且覆盖很少的反例。我们要求这一输出的规则有较高的精确度，但不必有较高的覆盖度。较高的精确度说明它所做出的预测应为正确的。可接受较低的覆盖度，表示它不必对每个训练样例都作出预测。有了这样一个学习

7、单个规则的learn-one-rule子程序，要学习规则集，一个明显的方法是在所有可用训练样例上执行learn-one-rule，再移去由其学到的规则覆盖的正例，再在剩余的训练样例上执行它以学习第二个规则。该过程可重复若干次，直到最后学习到析取规则集，它们共同覆盖正例，覆盖程度达到所希望的比例。算法被称为序列覆盖算法是因为它按次序学习到一组规则，它们共同覆盖了全部正例。最终的规则集可被排序，这样分类新实例时可先应用精度最