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)简 记为<V>叫做例子。其中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>叫做例子。其中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