6机器学习.ppt

* * 第6章 机器学习 6．6 归纳学习 4 结构归纳学习及示例 2．结构归纳学习的方法 （2）限定过程 当一个概括可能使关于一类事物的结构描述范围扩大时，就必须使用限定规则加以限定 限定过程说明了如何使用限定规则，其步骤： ① 将归纳模型与输入实例进行匹配，使归纳模型具有相应的组成部分 ② 考察归纳模型与“近似样品”是否有单一的差别 如果有差别，则检查是否“归纳模型”中或者“近似样品”中包含着某种链，而另一个中没有： a. 如果“归纳模型”中有某链，而“近似样品”中没有，则将此链标为“必需的链” b. 如果“近似样品”中有某链，而“归纳模型”中没有，则此链为“不能有的链” c. 如果“归纳模型”与“近似样品”无差别，则不考虑该“近似样品” * * 第6章 机器学习 6．6 归纳学习 4 结构归纳学习及示例 2．结构归纳学习的方法 （3）W算法 W算法是由温斯顿(Winston)提出的构造性归纳学习算法，其步骤： ① 令第一个输入示例（必须为正例）为初始归纳模型 ② 对其它样本 a. 若样本是一个“正例”，则调用“概括过程”； b. 若样本是一个“近似样品”，则调用“限定过程” * * 第6章 机器学习 6．6 归纳学习 4 结构归纳学习及示例 2．结构归纳学习的方法 【例6．3】“拱”的概念学习过程 “拱”的示例样本： * * 第6章 机器学习 6．6 归纳学习 4 结构归纳学习及示例 2．结构归纳学习的方法 【例6．3】“拱”的概念学习过程 ① 由第一个示例样品（正例）（a），可以建立起初始归纳模型： * * 第6章 机器学习 6．6 归纳学习 4 结构归纳学习及示例 2．结构归纳学习的方法 【例6．3】“拱”的概念学习过程 ② 比较第一个近似样品（反例）（c），它之所以不成为“拱”，是因为支撑顶木的两边相互接触了，因而，必须在归纳模型中加入“限定”（“不能相接触”），于是，可得修正的语义网络： * * 第6章 机器学习 6．6 归纳学习 4 结构归纳学习及示例 2．结构归纳学习的方法 【例6．3】“拱”的概念学习过程 ③现在比较第二个近似样品（反例）（d），该近似样品是因为没有被支撑的顶木，而不成为“拱”，根据限定过程，强调“必须支撑”链，有： * * 第6章 机器学习 6．6 归纳学习 4 结构归纳学习及示例 2．结构归纳学习的方法 【例6．3】“拱”的概念学习过程 ④ 比较归纳模型与最后一个示例样本（正例）（b），两者都是“拱”，但是它们有区别，一个的顶木是长方块，一个的顶木是三角块 可以用概括过程使关于“拱”的归纳模型的取值范围扩充到更一般的情形 于是，得到关于积木世界中“拱”的概念：由两块不相接触的积木块支撑着一个长方块或三角块的几何图形 * * 第6章 机器学习 6．6 归纳学习 5 基于决策树的归纳学习方法 发现概念描述空间的一种特别有效的方法是形成决策树，然后进行学习 基于决策树的归纳学习算法ID3 ID3可以发现决策树形式的分类规则，并将所有对象分成两类 它的每个叶子带有类名；每个上层结点所规定的属性的分支对应于该属性每个可能值 ID3采用信息论方法，减少对象分类的测试期望值 属性选择是基于可能性假设，即决策树的复杂性与消息传递的信息量有关 ID3检查所有的候选属性，选择增益最大的属性A作为根结点，形成树（递归地形成决策树） * * 第6章 机器学习 6．6 归纳学习 5 基于决策树的归纳学习方法 ID3算法可以被概括如下： ① 选择给定训练示例的随机子集（称为窗口） ② 重复 · 形成一条规则解释当前窗口 · 从其余示例中寻找该规则的例外 · 由当前窗口和规则例外生成新的窗口 直到该规则没有例外为止 ID3采用两种不同的策略建立新窗口： 一种策略是保留旧窗口中全部例子，增加由用户规定的例外数，这就逐渐扩大窗口 第二种策略是标识当前窗口中的关键对象，其余的用例外取代，保持窗口规模是一个常数 可能不收敛 * 决策树是一种由节点和边构成的用来描述分类过程的层次数据结构。 根节点：表示分类的开始 叶节点：表示一个实例的结束 中间节点：表示相应实例中的某一属性 边代表：某一属性可能的属性值 路径：从根节点到叶节点的每一条路径都代表一个具体的实例，并且同一路径上的所有属性之间为合取关系