表10-2 Learn-One-Rule的一种实现:一般到特殊柱状搜索 Learn-One-Rule(Target attribute, Attributes, Examples, k 初始化 Best hypothesis为最一般的假设φ 初始化 Candidate hypotheses为集合{ Best hypothesis} 当 Candidate hypotheses不空,做以下操作 生成下一个更特殊的候选假设 All constraints←-所有形式为av)的约束集合,其中,a为 Attributes的成员,v为出现 在当前 Examples集合中的a的值 New candidate hypotheses 对 Candidate hypotheses中每个h,循环 对AⅡ constraints中每个c,循环 通过加入约束c创建一个h的特化式 New candidate hypotheses中移去任意重复的、不一致的或非极大特殊化的假设 更新 Best hypothesis 对 New candidate hypotheses中所有h做以下操作 如果 Performance(h, Examples, Target attribute Performance( Best hypothesis, Examples, Target attri bute) 则 Best hypo 更新 Candidate hypotheses Candidate hypotheses← Candidate hypotheses中k个 Performance最佳成员 返回如下形式的一个规则 “如果 Best hypothesis”,则 prediction 其中, prediction为在与 Best hypothesis匹配的 Examples中最频繁的 200312argeψe軍习规则集合作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 11 表10-2 Learn-One-Rule的一种实现：一般到特殊柱状搜索 Learn-One-Rule(Target_attribute, Attributes, Examples, k) • 初始化Best_hypothesis为最一般的假设 • 初始化Candidate_hypotheses为集合{Best_hypothesis} • 当Candidate_hypotheses不空，做以下操作 – 生成下一个更特殊的候选假设 • All_constraints所有形式为(a=v)的约束集合，其中，a为Attributes的成员，v为出现 在当前Examples集合中的a的值 • New_candidate_hypotheses – 对Candidate_hypotheses中每个h，循环 » 对All_constraints中每个c，循环 通过加入约束c创建一个h的特化式 • New_candidate_hypotheses中移去任意重复的、不一致的或非极大特殊化的假设 – 更新Best_hypothesis • 对New_candidate_hypotheses中所有h做以下操作 – 如果 Performance(h,Examples,Target_attribute)>Performance(Best_hypothesis,Examples,Target_attri bute) 则Best_hypothesish – 更新Candidate_hypotheses • Candidate_hypothesesCandidate_hypotheses中k个Performance最佳成员 • 返回如下形式的一个规则 – “如果Best_hypothesis”，则prediction – 其中，prediction为在与Best_hypothesis匹配的Examples中最频繁的 Target_attribute值
表10-2 Learn-One-Rule的一种实现:一般到特殊柱状搜索 (2) Performance(h, Examples, Target attribute) h examples←与h匹配的 Examples子集 返回 entropy( n examples), Entropy是关 于 Target attribute.熵 2003.12.18机器学习学习规则集合作者: Mitchell译者:曾华军等讲者:陶晓鹏 12
2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 12 表10-2 Learn-One-Rule的一种实现：一般到特殊柱状搜索 （2） Performance(h, Examples, Target_attribute) • h_examples与h匹配的Examples子集 • 返回-Entropy(h_examples)，Entropy是关 于Target_attribute的熵
对表10-2的 Learn-One-Rule算法 的说明 算法主循环中考虑的每个假设都是属性-值约束的合取 每个合取假设对应于待学习规则的候选前件集合,它 由其覆盖的样例的熵来评估 搜索算法不断特化候选假设,直到得到一个极大特殊 假设,它包含所有可用的属性 ·规则的后件在算法的最后一步产生,在其前件确定后, 算法构造出的规则后件用于预测在前件所能覆盖的样 例中最常见的目标属性值 尽管使用了柱状搜索,贪婪搜索仍可能产生次优的规 则 2003.12.18机器学习学习规则集合作者: Mitchell译者:曾华军等讲者:陶晓鹏 13
2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 13 对表10-2的Learn-One-Rule算法 的说明 • 算法主循环中考虑的每个假设都是属性-值约束的合取 • 每个合取假设对应于待学习规则的候选前件集合，它 由其覆盖的样例的熵来评估 • 搜索算法不断特化候选假设，直到得到一个极大特殊 假设，它包含所有可用的属性 • 规则的后件在算法的最后一步产生，在其前件确定后， 算法构造出的规则后件用于预测在前件所能覆盖的样 例中最常见的目标属性值 • 尽管使用了柱状搜索，贪婪搜索仍可能产生次优的规 则
序列覆盖算法的几种变型 只学习覆盖正例的规则,对该规则没有覆盖的 实例默认地赋予其反例分类 正例在整个群体中所占比例很小,所以规则集只标 定正例的类别,而对其他样例默认分类为反例,这 样规则集更简洁易懂 这一方法对应于 Prolog中的失败否定策略,其中不 能证明为真的表达式都默认为假 需要修改 Learn-One-Rule算法 增加输入变量,指定感兴趣的目标值 Performance使用假设覆盖正例的比例 2003.12.18机器学习学习规则集合作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 14 序列覆盖算法的几种变型 • 只学习覆盖正例的规则，对该规则没有覆盖的 实例默认地赋予其反例分类 – 正例在整个群体中所占比例很小，所以规则集只标 定正例的类别，而对其他样例默认分类为反例，这 样规则集更简洁易懂 – 这一方法对应于Prolog中的失败否定策略，其中不 能证明为真的表达式都默认为假 – 需要修改Learn-One-Rule算法 • 增加输入变量，指定感兴趣的目标值 • Performance使用假设覆盖正例的比例
序列覆盖算法的几种变型(2) AQ算法 AQ明确地寻找覆盖特定目标值的规则,然后,对每 个目标值学习一个析取规则集 AQ算法学习单个规则的方法也不同于 Learn-One Rule,当它对每个规则执行一般到特殊柱状搜索时, 他围绕单个正例来进行 搜索中只考虑被某正例满足的属性,以得到逐渐特 殊的假设,每次学一个新规则时,它从那些未覆盖 的样例中也选择一个新的正例,以指引新析取项的 搜索 2003.12.18机器学习学习规则集合作者: Mitchell译者:曾华军等讲者:陶晓鹏 15
2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 15 序列覆盖算法的几种变型（2） • AQ算法 – AQ明确地寻找覆盖特定目标值的规则，然后，对每 个目标值学习一个析取规则集 – AQ算法学习单个规则的方法也不同于Learn-OneRule，当它对每个规则执行一般到特殊柱状搜索时， 他围绕单个正例来进行 – 搜索中只考虑被某正例满足的属性，以得到逐渐特 殊的假设，每次学一个新规则时，它从那些未覆盖 的样例中也选择一个新的正例，以指引新析取项的 搜索