3) Overfitting(过适合) Effect of Reduced-Error Pruning 0.9 0.85 0.8 0.75 0.7 0.6 On training data On test data On test data(during pruning)---- 0102030405060708090100 Size of tree(number of nodes)
3) Overfitting(过适合)
Reduced-Error Pruning Split data into training and validation set Do until further pruning is harmful: 1. Evaluate impact on validation set of pruning each possible node (plus those below it) 2. Greedily remove the one that most improves validation set accuracy produces smallest version of most accurate subtree · What if data is limited?
4.其他属性选择标准: the gain criterion tends to favor attributes with many values a be an attribute with values al. a2.. av a be an attribute formed from a by splitting one of the values into two gain(a)>=gain(a) “信息增益比” gain(A)/IV(a) Iv(A)=-∑ n log2 pi+ ni Pit ni i=l p+n p+n
4. 其他属性选择标准： the gain criterion tends to favor attributes with many values. A be an attribute with values A1, A2, ... Av A' be an attribute formed from A by splitting one of the values into two. gain(A') >= gain(A) “信息增益比
表21 例子号高度头发眼睛类别 淡黄 矮高高高矮高高矮 淡黄 兰兰兰褐 十+ 2345678 红镇黑黑黑 淡黄 兰褐褐 [头发=淡黄∨红色][眼睛=蓝色]→ [头发=黑色][眼睛=褐色→
表2.1 例子号 高度 头发 眼睛 类别 1 矮 淡黄 兰 + 2 高 淡黄 兰 + 3 高 红 兰 + 4 高 淡黄 褐 – 5 矮 黑 兰 – 6 高 黑 兰 – 7 高 黑 褐 – 8 矮 淡黄 褐 – [头发=淡黄∨红色][眼睛=蓝色] → + [头发=黑色] ∨[眼睛=褐色] → –
第三章规则学习算法 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
个例子e=V1,…Vn>满足选择子=A当且仅当Ⅴ是Aj的 元素,即V∈Aj;e满足一个公式当且仅当它满足该公式的 每一个选择子;e满足一条规则当且仅当e满足该规则的至 少一个公式。 例子满足选择子(公式、规则)也称做选择子(公式、规 则)覆盖该例子。 例如:例子e矮,淡黄,兰>满足选择子[头发=淡黄∨红 色]和[眼睛=蓝色];满足公式[头发=淡黄∨红色][眼睛= 蓝色]。 定义3:普化( generalize):减少规则的约束,使其覆盖更多的 训练例子叫普化
一个例子e=满足选择子[xj=Aj]当且仅当Vj是Aj的 元素，即Vj Aj; e满足一个公式当且仅当它满足该公式的 每一个选择子；e满足一条规则当且仅当e满足该规则的至 少一个公式。 例子满足选择子（公式、规则）也称做选择子（公式、规 则）覆盖该例子。 例如： 例子e= 满足选择子[头发=淡黄∨红 色]和 [眼睛=蓝色] ；满足公式[头发=淡黄∨红色] [眼睛= 蓝色] 。 定义3：普化(generalize) :减少规则的约束，使其覆盖更多的 训练例子叫普化
定义4:特化( (specialize):增加规则的约束,使其覆盖训练例 子较少叫特化。 定义5:一致:只覆盖正例不覆盖反例的规则被称为是一致 的 定义6:完备:覆盖所有正例的规则被称为是完备的
定义4：特化(specialize) : 增加规则的约束，使其覆盖训练例 子较少叫特化。 定义5：一致：只覆盖正例不覆盖反例的规则被称为是一致 的。 定义6：完备：覆盖所有正例的规则被称为是完备的
2.GS算法: GS算法 输入:例子集; 输出:规则; 原则:(a)从所有属性中选出覆盖正例最多的属性; (b)在覆盖正例数相同的情况下,优先选择只覆盖正 例不覆盖反例的属性值; 设PE,NE是正例,反例的集合。PENE是临时正,反例集。 CPX表示公式,F表示规则(概念描述) (1)F←true 2)PE←PE,NE←NE,CPX←true; 3)按上述(a)(b)两规则选出一个属性值V。,设V。为第j个属 性的取值,建立选择子[Xj=V]并加入公式中, CPX←CPX∧[Xj=V0 (4)如果X=V覆盖NE中的反例,转(5) 否则F← FVCPX,转(6)
2. GS算法： GS算法 输入： 例子集； 输出： 规则； 原则： （a) 从所有属性中选出覆盖正例最多的属性； (b) 在覆盖正例数相同的情况下，优先选择只覆盖正 例不覆盖反例的属性值； 设PE,NE是正例，反例的集合。 PE’,NE’是临时正，反例集。 CPX表示公式，F表示规则（概念描述）。 (1) F←true; (2) PE’ ←PE, NE’ ←NE, CPX←true; (3) 按上述(a) (b)两规则选出一个属性值V 0 , 设V 0 为第j0个属 性的取值，建立选择子[Xj0=V0 ]并加入公式中， CPX←CPX∧ [Xj0=V0 ] (4) 如果[Xj0=V0 ]覆盖NE’中的反例，转(5); 否则 F←F∨CPX, 转(6);
(5)重新构造PE和NE,PE含有原来PE中被Xj0V0]覆盖的例子, NE'含有原来NE中被Ⅹj0=V0覆盖的例子,转(3) (6) PE+PEPE,如果PE=,停止,否则转2 GS算法举例: 例子集见表23 学习结果: ESR-normallausculationbublelike] 肺炎 TX-ray=spotJESR=normal 3AQ算法: l)普化( generalize 2)特化( specialize 3)一致 4)完备
(5) 重新构造PE’和NE’, PE’含有原来PE’中被[Xj0=V0]覆盖的例子， NE’含有原来NE’中被[Xj0=V0]覆盖的例子，转（3）； (6) PE←PE\PE’,如果PE= ,停止，否则转(2); GS算法举例： 例子集见表2.3 学习结果： [ESR=normal][Ausculation=bublelike] [X-ray=spot][ESR=normal] 3.AQ算法： 1) 普化(generalize) : 2) 特化(specialize) : 3) 一致 4) 完备 肺炎
表2.3肺炎与肺结核两组病历 no Fever CoughX-ray ESR Ausculat high heavy Flack Normal Bubblelike 肺炎|2 mediu heavyFlack Normal Bubblelike 345 slight Spot Normal Dry-peep high mediu Flack NormalBubblelike mediu slight Flack Normal Bubblelike absent slight Strip Normal 肺结2hig gh heavy Hole Fast Dry-peep 核 345 slight Strip Normal Normal absent slight Spot Fast Dry-peep low mediu flack fasts Normal
no Fever Cough X-ray ESR Ausculat. 1 high heavy Flack Normal Bubblelike 肺炎 2 mediu heavy Flack Normal Bubblelike 3 low slight Spot Normal Dry-peep 4 high mediu Flack Normal Bubblelike 5 mediu slight Flack Normal Bubblelike 1 absent slight Strip Normal Normal 肺结 2 high heavy Hole Fast Dry-peep 核 3 low slight Strip Normal Normal 4 absent slight Spot Fast Dry-peep 5 low mediu flack fasts Normal 表2..3 肺炎与肺结核两组病历