第2章(示例学习).ppt

定理2.1 公式L覆盖公式A又覆盖公式B，当且仅当它覆盖A B。 定理2.2 一个例子集合被一个一致的规则所覆盖，则这些例子的合并也是一致的。 x1 x2 x3 x4 公式L {0,3} {0,1} {1,3} 1 1 1 1 1 2 0 2 2 2 3 3 1 2 2 4 4 0 3 3 NE (a) 公式L(L=[X1=0 3][X2=0 1][X3=1 3]) 与反例矩阵NE X1 X2 X3 X4 公式 1 * * * * 2 2 * * * 2 * 4 * * * L的扩张矩阵EM(L)箭头经过的路对应于公式[X1?1,4][X3?2]=[X1=0,2,3][X3=0,1,3] [算法AE9] (1) 从正例集PE中选择一个种子e. F?e, path?? ,CPE? ?. (2) 做F的扩张矩阵EM(F)。如果有必选元素则放入path中，同时删去NE中该必选元素出现的行（反例），如果NE空则终止；如非空则删去PE和CPE中出现该必选元素的对应行，重复执行直至EM(F)中不存在必选元素为止。 (3)如果PE非空，检查PE中的每一正例，看它与F的合并是否是一致公式；如不是则从PE中删去该正例；若是则保留一个覆盖正例数目最多的一个合并取代F, 将PE中被F覆盖的正例放入CPE中，重复步骤(2)和(3),直至PE变空。 (4) 如果PE空而CPE非空，则检查CPE中的每一个正例，看它与F合并后是否为一致公式，若不是则从CPE中删去该正例； 若是则生成合并公式，保留一个覆盖最多正例的合并取代F,从CPE中删去被新的F覆盖的正例，重复(2),(4)直至CPE 变空。 (5) 此时PE和CPE均空，但NE非空，做EM(F). 将其中含有最多非死元素的列中的非死元素放入path中，并从NE中删去含这些非死元素的行，重复这一过程，直到NE变空。将path转变为相应的公式。 [应用举例] 将表2.7的第一个反例1,0,1改为1,0,2 选择第一个正例 做种子，F? ,path ??, CPE ??. (2) 做F的扩张矩阵EM(F), 如下图(a) X1 X2 X3 公式F 0 0 0 1 1 * 2 2 * ? * 3 1 1 * 4 1 1 2 5 * * ? (a) X1 X2 X3 公式F {0,1} {0,2} {0} 1 * * ② (b) path ?path∪ {l22,l53}, (3) 将路径转变为公式[x2≠ 1][x3 ≠1] 删去路径对应的反例， 因PE与CPE中没有该必选元素出现，所以PE与CPE不动 (4) PE非空，做F ? F ⊕ ( )={0},{0},{0}, F是一致的。做F ? F ⊕ ( )={0,1},{0,2},{0}, F是一致的。继续合并F ? F ⊕ ( )={0,1},{0,2},{0}, F是一致的。继续合并F ? F ⊕ ( )={0,1},{0,2},{0,2}, F是不一致的。从PE中删除 ,保留覆盖最多正例的F ={0,1},{0,2},{0}。CPE={ , , }做EM(F),如图(b)所示 Path={l22,l53,l13},将Path转变为公式 [x2≠ 1][x3 ≠1,2]=[x2=0,2][x3=0] 公式与CPE中例子一致。 第二轮： 对 执行上面过程。 参考文献： 1. Induction of Decision Trees, Machine Learning 1: 81-106, 1986. 2. Machine learning: An Artificial Intelligence Approach Edited by R.S. Michalski P39-135. 3. 归纳学习—算法，理论，应用 洪家荣 P.1-33 * 第二章 示例学习 示例学习的问题描述（见表2.1,表2.2） 二. 决策树学习（ID3算法） ID3算法： 输入：例子集（正例、反例）； 输出：决策树 从树的根结点开始，每次都用“最好的属性”划分结点，直到所有结点只含一类例子为止。 例子号 高度 头发 眼睛 类别 1 矮 淡黄 兰 + 2 高 淡黄 兰 + 3 高 红 兰 + 4 高 淡黄 褐 – 5 矮 黑 兰 – 6 高 黑 兰 – 7 高 黑 褐 – 8 矮 淡黄 褐 – [头发=淡黄∨红色][眼睛=蓝色] → + [头发=黑色] ∨[眼睛=褐色] → – 表2.1 表2.2 Day Outlook Temperature Humidity W