ID3决策树算法应用

给定数据集S，试根据前7个样本构造ID3决策树模型，并预测第8个样本的类别？

数据集S

格式要求

ID3决策树算法的计算题示例（蓝色字体部分属于分析过程，在提交时可以不写）：

下列信息表包含5个属性: Warm_blooded ，Feathers，Fur，Swims，Lay_eggs，其中类标号属性为Lay_eggs，请根据该信息表通过计算建立一棵决策树。

解：类标号属性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(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.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(s11,s21)+(4/6) I(s12,s22)=0.874 Gain(Swims)= I(s1,s2)- E(Swims)=0.044

由于Feathers在属性中具有最高的信息增益，所以Feathers被选为测试属性，并以此创建一个结点，用Feathers标记，并对每个属性值引出一个分支，数据集被划分成两个子集。图1给出了Feathers结点及其分支。

图 1 Feathers结点及其分支

从图1可以看出，对于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)+(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(Swims)=(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所示：

图 2 Warm_blooded结点及其分支

从图2可以看出，经过此次划分，Warm_blooded=1和Warm_blooded=0的分支的所有元组均只包含一个类标号，故ID3算法到此终止，得到的决策树如下：