第9章-预测建模：分类和回归.pptVIP

五邑大学信息学院　　何国辉 1. 信息增益（续） 计算信息增益的思路： 首先计算不考虑任何输入变量的情况下，要确定T中任一样本所属类别需要的信息Info(T); 计算引入每个输入变量X后，要确定T中任一样本所属类别需要的信息Info（X，T）； 计算两者的差Info(T)-Info（X，T），此即为变量X的信息增益，记为Gain（X,T）。 1. 信息增益（续） 计算熵Info(T) 如果不考虑任何输入变量，而将训练集T中的所有样本仅按照响应变量Y的值分到m个不相交的类别C1、C2、...、Cm的话，要确定任一样本所属的类别需要的信息为： m Info (T)＝－Σi=1 (|Ci| /|T|).log2(|Ci| /|T|)) 以2为底的原因是：信息按二进制位编码 1. 信息增益（续） 计算熵Info（X，T） 如果考虑某个输入变量X，将训练集T按照X的值划分为n个子集T1、T2、...、Tn的话，要确定T中任一样本所属的类别需要的信息为： 其中： 注：Sj为Tj中属于类别Cj的样本子集。 n Info (X，T)＝－Σi=1 (|Ti| /|T|).Info(Ti) m Info (Ti)＝－Σj=1 (|Sj| /|Ti|).log2(|Sj| /|Ti|) 1. 信息增益（续） 计算增益Gain（X,T） Gain（X,T）=Info（T）-Info（X，T） 所有变量的信息增益计算完后，可以根据信息增益的大小多所有输入变量进行排序，优先使用信息增益大的变量。 1. 信息增益（续） 举例：本例将如下表数据作为训练集。 1. 信息增益（续） 类1 假 96 C 类1 假 80 C 类1 假 80 C 类2 真 70 C 类2 真 80 C 类1 假 75 B 类1 真 65 B 类1 假 78 B 类1 真 90 B 类1 假 70 A 类2 假 95 A 类2 假 85 A 类2 真 90 A 类1 真 70 A 属性4 属性3 属性2 属性1 数据库T： 训练例子的简单平面数据库 1. 信息增益（续） 其中：有9个样本属于类1，有5个样本属于类2。因此分区前的熵为： Info(T)＝ -9/14.log2(9/14) -5/14.log2(5/14) = 0.940比特 1. 信息增益（续） 根据属性1把初始样本集分区成3个子集（检验x1表示从3个值A，B或C中选择其一）后，得出结果： Infox1(T)＝5/14（-2/5 log2(2/5) -3/5 log2(3/5) ） + 4/14（-4/4 log2(4/4) -0/4 log2(0/4) ） + 5/14（-3/5 log2(3/5) -2/5 log2(2/5) ） =0.694比特 通过检验x1获得的信息增益是： Gain(x1) = 0.940 – 0.694 = 0.246比特 1. 信息增益（续） 类似地，根据属性3检验x2表示从真或假两个值选择其一），类似地有： Info x2(T)＝6/14（-3/6 log2(3/6) -3/6 log2(3/6) ） + 8/14（-6/8 log2(6/8) -2/8 log2(2/8) ） =0.892比特 通过检验x2获得的信息增益是： Gain(x2) = 0.940 – 0.892 = 0.048比特 1. 信息增益（续） 依次类推，计算出其它属性获得的增益。 通过获得的两个增益比较，按照增益准则，将选择x1作为分区数据库T的最初检验（作为根节点创建）。 为了求得最优检验还必须分析关于属性2的检验，它是连续取值的数值型属性。 ID3算法无法解决数值型属性，需要通过其改进型--C4.5算法。 1. 信息增益（续） T1 检验X1: 属性1=？ 类1 假 70 类2 假 95 类2 假 85 类2 真 90 类1 真 70 类 属性3 属性2 类1 假 75 类1 真 65 类1 假 78 类1 真 90 类 属性3 属性2 类1 假 96 类1 假 80 类1 假 80 类2 真 70 类2 真 80 类 属性3 属性2 T2 T3 A B C 叶结点 根据属性1进行数据集划分 1. 信息增益（续） 在得到前面的第一次划分以后，再分别对划分后的T1、T2、T3三个子集继续分裂。 其中T2对应的数据子集都属于同一个类别类1，无需继续分裂。 1. 信息增益（续） 结合C4.5算法后，得到的决策树。 X1: 属性1 X4: 属性2 X5: 属性