《机器学习》第二章 示例学习（2/2）

第二章示例学习 示例学习的问题描述(见表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

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

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+}

则“信息增益” Gain (a=I(p, n-E(A) Gain(outlook =0.940-E(outlook =0. 246bits 3.决策树学习的常见问题 1)不合适属性( Inadequate attributes 两类例子具有相同属性值。没有任何属性可进一步扩展决策 树 哪类例子多,叶结点标为哪类 3)未知属性 ①“最通常值”办法 ②按比例将未知属性例子分配到各子集中: 属性A有值{A12,AV},A值等于A的例子数p和n,未知属性 值例子数分别为p和n,在生成决策树时A的例子数 pu'ratio

则“信息增益” Gain(A)=I(p,n)-E(A) Gain(outlook)=0.940-E(outlook)=0.246bits 3. 决策树学习的常见问题 1）不合适属性（Inadequate attributes) 两类例子具有相同属性值。没有任何属性可进一步扩展决策 树。 哪类例子多，叶结点标为哪类。 3）未知属性 ① “最通常值”办法 ② 按比例将未知属性例子分配到各子集中： 属性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为 公式。  jJ Li l i=1 

个例子e=满足选择子区=A当且仅当Ⅴ是Aj的 元素,即∈Aj;e满足一个公式当且仅当它满足该公式的每 个选择子;e满足一条规则当且仅当e满足该规则的至少 公式。 例子满足选择子(公式、规则)也称做选择子(公式、规 则)覆盖该例子。 例如:例子e矮,淡黄,兰>满足选择子[头发=淡黄∨红 色]和[眼睛=蓝色;满足公式[头发=淡黄∨红色][眼睛=蓝 色]

一个例子e=满足选择子[xj=Aj]当且仅当Vj是Aj的 元素，即Vj Aj; e满足一个公式当且仅当它满足该公式的每 一个选择子；e满足一条规则当且仅当e满足该规则的至少一 个公式。 例子满足选择子（公式、规则）也称做选择子（公式、规 则）覆盖该例子。 例如： 例子e= 满足选择子[头发=淡黄∨红 色]和 [眼睛=蓝色] ；满足公式[头发=淡黄∨红色] [眼睛=蓝 色]