第二章(示例学习)解读.ppt

2. 信息增益 Gain(A)=I(p,n)-E(A) 其中，p、n是结点node的正、反例个数。A要扩展结点node的属性， pi、 ni是C 被A划分成的V个子集{C1, …Cv}的正、反例个数。 属性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-} 定理2.1 公式L覆盖公式A又覆盖公式B，当且仅当它覆盖A B。 定理2.2 一个例子集合被一个一致的规则所覆盖，则这些例子的合并也是一致的。 * 第二章 示例学习 示例学习的问题描述（见表2.1,表2.2） 二. 决策树学习（ID3算法） ID3算法： 输入：例子集（正例、反例）； 输出：决策树 从树的根结点开始，每次都用“最好的属性”划分结点，直到所有结点只含一类例子为止。 – 褐 淡黄 矮 8 – 褐 黑 高 7 – 兰 黑 高 6 – 兰 黑 矮 5 – 褐 淡黄 高 4 + 兰 红 高 3 + 兰 淡黄 高 2 + 兰 淡黄 矮 1 类别 眼睛 头发 高度 例子号 [头发=淡黄∨红色][眼睛=蓝色] → + [头发=黑色] ∨[眼睛=褐色] → – 表2.1 表2.2 p false normal cool sunny 9 N False High mild sunny 8 P True Normal cool overcast 7 N True Normal cool rain 6 P False Normal cool rain 5 P False High mild rain 4 P False High hot overcast 3 N True High hot sunny 2 N False High hot sunny 1 Class Wind Humidity Temperature Outlook Day N True High Mild rain 14 P False Normal Hot Overcast 13 P True High Mild Overcast 12 P True Normal Mild Sunny 11 P False Normal Mild Rain 10 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+} 根结点:P=9,n=5 Gain(outlook)=0.940-E(outlook)=0.246bits gain(temperature) = 0.029 bits gain(humidity) = 0.151 bits gain(windy) = 0.048 bits 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 3. 决策树学习的常见问题 1）不相关属性(irrelevant attributes) 属性A有v个属性值，A的第I个属性值对应Pi个正例、ni个反例。 2) 不充足属性（Inadequate attributes) 两类例子具有相同属性值。没有任何属性可进一步扩展决策树。哪类例子多，叶结点标为哪类。 3）未知属性值 ① “最通常值”办法 ② 决策树方法: 把未知属性作为“类”，原来的类作为“属性” ③ Bayesian 方法 ④ 按比例将未知属性值例子分配到各子集中： 属性A有v个值{A1,…,Av}, A值等于Ai的例子数pi和ni，未知属性值例子数分别为pu和nu, 在生成决策树时Ai的例子数 Pi+pu·ratio ni+nu·ratio 4. 属性选择标准 5. Overfitting(过适合) 三. 规则学习算法 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=(矮，淡黄，兰）