信息增益 离散属性a的取值：{al,a2,,a) D:D中在a上取值=a的样本集合 以属性a对数据集D进行划分所获得的信息增益为： Gain(D,d)-Ebmt(D)-∑ Ent(D) 划分前的信息熵 划分后的信息熵 第)个分支的权重， 样本越多越重要 ID3算法中使用
$ % a # Dv: D a = av # . a . D ,) (#$ #! #! & v # -, ++-* ID3' "
划分选择-信息增益 ▣以属性“色泽”为例，其对应的3个属性子集分别为D1(色泽= 青绿)，D2(色泽=乌黑)，D3(色泽=浅白) 口子集D1包含编号为{1,4,6,10,13,17的6个样例，其中正例占 p1=音，反例占p2=,D?D3同理，3个结点的信息熵为： Ent(D)=-(倍log28+若1og2)=1.000 Emt(D2)=-(借1og2君+暑1og2) =0.918 Ent(D3)=-(号log25+号1og2)=0.722 口属性“色泽”的信息增益为 caiD色泽)=Em(D,-立 Ent(D） 0.998-(×1.000+×0.918+5×0.722) =0.109
- p ( # 3 ) (( = *&) (( =+) (( = ") p ) ' # - ! % # , p ( # $
一个例子（续） 口类似的，其他属性的信息增益为 Gain(D,根蒂)=0.143 Gain(D,敲声)=0.141 Gain(D,纹理)=0.381 Gain(D,脐部)=0.289 Gain(D,触感)=0.006 ▣显然，属性“纹理”的信息增益最大，其被选为划分属性 纹理=？ 清晰 稍糊 模糊 {1,23,4,5,6,8,10,15 {7,9,13,14,17} {11,12,16}
( ) p p =? {1,2,3,4,5,6,8,10,15} {7,9,13,14,17} {11,12,16}
一个例子（续） 对每个分支结点做进一步划分，最终得到决策树 纹理=？ 清晰 稍糊 模糊 根蒂=？ 触感=？ 坏瓜 蜷缩 稍蜷 硬挺 硬滑 软粘 好瓜 色泽=？ 坏瓜 坏瓜 好瓜 青绿 乌黑 浅白 好瓜 触感=？ 好瓜 硬滑 软粘 好瓜 坏瓜
( ) " =? =? =? !=? !=?
增益率(gain ratio) 信息增益：对可取值数目较多的属性有所偏好 有明显弱点，例如：考虑将“编号”作为一个属性（各个分支纯度最大！） Gain(D,a) 增益率：Gain_ratio(D,a)= 增益率对可取值数目 IV(a) 越小的属性有所偏好！ 共中Nd-立2 IV(a):属性a的固有值(ntrinsic Value),属性a的可能取值数目越多( 即V越大)，则V(a)的值通常就越大（增益率就越小）. 启发式： 先从候选划分属性中找出信息增益高于平均水平的， 再从中选取增益率最高的。（增益和增益率之间折中） C4.5算法中使用 C4.5算法中使用
6(D)-$#VEL)C05=7+ =:;4@(I)HJ. G% - 05 ' (DA) , a a # (Intrinsic Value)05 a C$I#VEK) ( ! V K*)( IV(a) CN1/K*$!( (DA (gain ratio) C4.5F?,B &"3) M 05,8:6(DO.2'>2C( ,M#(DA<OC$$!) C4.5& " $! % (#