第二章示例学习 示例学习的问题描述(见表21表22) 二.决策树学习(ID3算法) 1.学习效果的衡量标准(示例学习的优化问题) 2.ID3算法: 输入:例子集(正例、反例); 输出:决策树 从树的根结点开始,每次都用“最好的属性”划分结点,直 到所有结点只含一类例子为止。 3.信息增益 结点node例子集C,p个正例n个反例结点node的“信息熵
第二章 示例学习 一. 示例学习的问题描述(见表2.1,表2.2) 二. 决策树学习(ID3算法) 1. 学习效果的衡量标准(示例学习的优化问题) 2. ID3算法: 输入:例子集(正例、反例); 输出:决策树 从树的根结点开始,每次都用“最好的属性”划分结点,直 到所有结点只含一类例子为止。 3. 信息增益 结点nodei 例子集C, p个正例 n个反例 结点nodei的“信息熵
表21 例子号高度头发眼睛类别 淡黄 矮高高高矮高高矮 淡黄 兰兰兰褐 十+ 2345678 红镇黑黑黑 淡黄 兰褐褐 [头发=淡黄∨红色]眼睛=蓝色]→ 头发一黑色∨[眼睛=褐色]→
例子号 高度 头发 眼睛 类别 1 矮 淡黄 兰 + 2 高 淡黄 兰 + 3 高 红 兰 + 4 高 淡黄 褐 – 5 矮 黑 兰 – 6 高 黑 兰 – 7 高 黑 褐 – 8 矮 淡黄 褐 – [头发=淡黄∨红色][眼睛=蓝色] → + [头发=黑色] ∨[眼睛=褐色] → – 表2.1
表22 Day Outlook Temperature Humidity Wind Class sunny hot High False N sunny hot High True N oⅤ vercast hot High False P 23456789 rain ild mI High False P rain Normal False P rain co0 Normal True N overcast cool Normal True P Sunny mild High False N Sunny cool normal false p
表2.2 Day Outlook Temperature Humidity Wind Class 1 sunny hot High False N 2 sunny hot High True N 3 overcast hot High False P 4 rain mild High False P 5 rain cool Normal False P 6 rain cool Normal True N 7 overcast cool Normal True P 8 sunny mild High False N 9 sunny cool normal false p
10 Rain Mild Normal False 11Sunny Mild Normal True 12 OvercastMild High True 13 Hot Normal False PPPPN 14 rain Mild High True
10 Rain Mild Normal False P 11 Sunny Mild Normal True P 12 Overcast Mild High True P 13 Overcast Hot Normal False P 14 rain Mild High True N
outlook sunny rain overcast 1-,2-:8,9+,11+} 37+,12+,13} 456,10,14} humidity Windy high normal true se 1-2.8-}{9+,1+ {6,14 {4+,5+,10+} P
outlook sunny overcast rain humidity p windy high normal N P true false N P {1…14} {1-,2-,8-,9+,11+} {3+ ,7+ ,12+ ,13+} {4+ ,5+ ,6- ,10+ ,14-} {1-,2-,8-} {9+,11+} {6- ,14-} {4+ ,5+ ,10+}
I(p, n)=-p 82 p+n -+n login+n 根结点P=9n=4 1(5)=log14log14 =0.940bts A是例子的一个属性,有V个值{a1ay},用A扩展 nodei结点 把C分成V个子集C1…CV},Ci对应a1(i=1,2,…V)。Ci含有p个 正例,n个反例。“期望信息熵”为 E(4)=∑B+P,n) p+n 属性 outlook,有三个值,{ sunny, overcast, rain,用 outlook扩展根 结点得到三个子集{C1,C2C3}C1={12,8 ,9,11+},C2={3,7,12,13},C3={4,5:6;,10,14} 2,3)=0.971 P2=4,n2=0I(4,0)=0 P3=3,n3=2I(3,2)=0.971 E(outlook)=,,l(P1,n1)+,I(P2,n2)+,I(P3,n3) 0.694 bits
根结点:P=9,n=4 A是例子的一个属性,有V个值{a1 , …av}, 用A扩展nodei结点 把C分成V个子集{C1 , …Cv}, Ci对应ai (i=1,2, …V)。 Ci含有pi个 正例,ni个反例。 “期望信息熵”为 属性outlook,有三个值,{sunny,overcast,rain},用outlook扩展根 结点得到三个子集{C1 ,C2 ,C3}。C1={1- ,2- ,8- ,9+ ,11+},C2={3+ ,7+ ,12+ ,13+}, C3={4+ ,5+ ,6- ,10+ ,14-} P1=2, n1=3 I(2,3)=0.971 P2=4, n2=0 I(4,0)=0 P3=3, n3=2 I(3,2)=0.971 p n n p n n p n p p n p I p n + + − + + = − log2 log2 ( , ) 0.940 bits 14 5 14 5 14 9 14 9 (9,5) log2 log2 I = − − = = + + = v i i i i i I p n p n p n E A 1 ( ) ( , ) 0.694 bits ( , ) 14 5 ( , ) 14 4 ( , ) 14 5 ( ) 1 1 2 2 3 3 = E outlook = I p n + I p n + I p n
则“信息增益” Gain (a=I(p, n-E(A) Gain(outlook=0.940-Eoutlook =0. 246bits 3.举例 4.决策树学习的常见问题 1)不相关属性( irrelevant attributes) 属性A把例子集分成v个子集{C1Cv},Ci含有Pi个正例、n1 个反例。 2)不合适属性( Inadequate attributes 两类例子具有相同属性值。没有任何属性可进一步扩展决策 树。哪类例子多,叶结点标为哪类 3)未知属性 ①决策树方法:把未知属性作为“类”,原来的类作为“属 性 ②“最通常值”办法
则“信息增益” Gain(A)=I(p,n)-E(A) Gain(outlook)=0.940-E(outlook)=0.246bits 3. 举例 4. 决策树学习的常见问题 1)不相关属性(irrelevant attributes) 属性A把例子集分成v个子集{C1 ,…Cv},Ci含有Pi个正例、ni 个反例。 2) 不合适属性(Inadequate attributes) 两类例子具有相同属性值。没有任何属性可进一步扩展决策 树。哪类例子多,叶结点标为哪类。 3)未知属性 ① 决策树方法: 把未知属性作为“类”,原来的类作为“属 性” ② “最通常值”办法
③ Bayesian方法 ④按比例将未知属性例子分配到各子集中: 属性A有值{A1,A},A值等于A的例子数p和n,未知属性 值例子数分别为p和n,在生成决策树时A的例子数 P:+p, ratIo
③ Bayesian 方法 ④ 按比例将未知属性例子分配到各子集中: 属性A有值{A1 ,…,Av}, A值等于Ai的例子数pi和ni,未知属性 值例子数分别为pu和nu , 在生成决策树时Ai的例子数 Pi+pu·ratio
temperature cool mild hot k outlook Sunny rain Sunny rain over over true false WINe windy humidity n humidity true ue false se normal norm windy outlook
temperature outlook outlook windy p p windy windy p humidity N humidity N p p N windy p outlook p cool mild hot sunny over rain true false true false sunny over rain true false high normal high norm true false sunnyover rain
三.聚集算法 1.基本概念: 定义1(例子).设E=D1XD2×…×Dn是n维有穷向量空间, 其中D是有穷离散符号集。E中的元素e=(V1,V2…,Vn)简 记为叫做例子。其中j∈D 例如:对表2.1 D1={高,矮};D2={淡黄,红,黑};D3={兰,褐} E=D1×D,×D 例子e=(矮,淡黄,兰) 定义2。选择子是形为x=A的关系语句,其中x为第j个属性, A≤D;公式(或项)是选择子的合取式,即⌒[x=Aj, 其中J∈{1,…,n};规则是公式的析取式,即L其中Li为 公式
三. 聚集算法 1. 基本概念: 定义1 (例子). 设E=D1×D2 ×… ×Dn 是n维有穷向量空间, 其中 Dj是有穷离散符号集。E中的元素e=(V1 ,V2 , …,Vn)简 记为叫做例子。其中Vj∈Dj。 例如:对表2.1 D1={高,矮};D2={淡黄,红,黑};D3={兰,褐} E=D1 × D2 × D3 例子 e=(矮,淡黄,兰) 定义2。选择子是形为[xj=Aj ]的关系语句,其中xj为第j个属性, Aj Dj; 公式(或项)是选择子的合取式,即 [xj=Aj], 其中 J {1, …,n}; 规则是公式的析取式,即 ,其中Li为 公式。 jJ Li l i=1