决策树算法应用

1、给定数据集S，试根据前7个样本构造ID3决策树模型，并预测第8个样本的类别？数据集SSampleABCS1a0b0c1S2a0b1c1S3a0b2c1S4a1b0c2S5a1b1c1S6a1b2c2S7a2b0c2S8a2b1 格式要求ID3决策树算法的计算题示例（蓝色字体部分属于分析过程，在提交时可以不写）：下列信息表包含5个属性: Warm_blooded，Feathers，Fur，Swims，Lay_eggs，其中类标号属性为Lay_eggs，请根据该信息表通过计算建立一棵决策树。No.Warm_bloodedFeathersFurSwimsLay_eggs111001200011311

2、001411001510010610100解：类标号属性Lay_eggs有2个不同的取值0和1，其中1有4个样本，0有2个样本，故对给定样本分类所需的期望信息为： I(s1,s2)=I(4,2)=-(4/6)log2(4/6) -(2/6)log2(2/6)=0.918接下来计算每个训练属性的信息增益：（先考虑Warm_blooded属性，显然，Warm_blooded=1有3个Lay_eggs=1的样本，2个Lay_eggs=0的样本；，Warm_blooded=0有1个Lay_eggs=1的样本，0个Lay_eggs=0的样本） 对于Warm_blooded=1，s11=3,s21=2，I

3、(s11,s21)=0.971。对于Warm_blooded=0，s12=1,s22=0，I(s12,s22)=0。所以 E(Warm_blooded)=(5/6) I(s11,s21)+(1/6) I(s12,s22)=0.809 Gain(Warm_blooded)= I(s1,s2)- E(Warm_blooded)=0.109对于Feathers =1，s11=3,s21=0，I(s11,s21)=0。对于Feathers =0，s12=1,s22=2，I(s12,s22)=0.918。所以 E(Feathers)=(3/6) I(s11,s21)+(3/6) I(s12,s22)=0

4、.459 Gain(Feathers)= I(s1,s2)- E(Feathers)=0.459对于Fur =1，s11=0,s21=1，I(s11,s21)=0。对于Fur =0，s12=4,s22=1，I(s12,s22)=0.722。所以 E(Fur)=(1/6) I(s11,s21)+(5/6) I(s12,s22)=0.602 Gain(Fur)= I(s1,s2)- E(Fur)=0.316对于Swims =1，s11=1,s21=1，I(s11,s21)=1。对于Swims =0，s12=3,s22=1，I(s12,s22)=0.811。所以 E(Swims)=(2/6) I(s

5、11,s21)+(4/6) I(s12,s22)=0.874 Gain(Swims)= I(s1,s2)- E(Swims)=0.044由于Feathers在属性中具有最高的信息增益，所以Feathers被选为测试属性，并以此创建一个结点，用Feathers标记，并对每个属性值引出一个分支，数据集被划分成两个子集。图1给出了Feathers结点及其分支。FeathersWarm_bloodedFurSwimsLay_eggs100110011001Warm_bloodedFurSwimsLay_eggs001110101100=1=0 图 1 Feathers结点及其分支 从图1可以看出，对于

6、Feathers=1的所有元组，其类标号均为1。所以，根据ID3决策树生成算法，由此得到一个叶子结点，类别标记为Lay_eggs=1。 对于Feathers=0的所有元组，类标号包含多个，计算其余训练属性的信息增益：首先，对给定样本分类所需的期望信息为： I(s1,s2)=I(1,2)=-(1/3)log2(1/3) -(2/3)log2(2/3)=0.918对于Warm_blooded=1，s11=0,s21=2，I(s11,s21)=0。对于Warm_blooded=0，s12=1,s22=0，I(s12,s22)=0。所以 E(Warm_blooded)=(2/3) I(s11,s21)

7、+(1/3) I(s12,s22)=0 Gain(Warm_blooded)= I(s1,s2)- E(Warm_blooded)=0.918对于Fur =1，s11=0,s21=1，I(s11,s21)=0。对于Fur =0，s12=1,s22=1，I(s12,s22)=1。所以 E(Fur)=(1/3) I(s11,s21)+(2/3) I(s12,s22)=0.667 Gain(Fur)= I(s1,s2)- E(Fur)=0.251对于Swims =1，s11=1,s21=1，I(s11,s21)=1。对于Swims =0，s12=0,s22=1，I(s12,s22)=0。所以 E(S

8、wims)=(2/3) I(s11,s21)+(1/3) I(s12,s22)=0.667 Gain(Swims)= I(s1,s2)- E(Swims)=0.251所以，对于Feathers=0的子树，Warm_blooded的信息增益最高，把Warm_blooded作为测试属性，根据其值1和0把该子树划分成两个分枝，得到如图2所示：FeathersWarm_bloodedFurSwimsLay_eggs100110011001=1=0FurSwimsLay_eggs010100FurSwimsLay_eggs011=1=0Warm_blooded 图 2 Warm_blooded结点及其分支从图2可以看出，经过此次划分，Warm