信息增益生成决策树

首先查看数据集

我们用这个数据集来构造决策树，判断一个新的西瓜是否为好瓜。

决策树的构造

计算数据集的信息熵

首先观察数据集$D$D，发现数据集$D$D中有好瓜和坏瓜两个类别，其中好瓜占比$p_1=\frac {8}{17}$p1​=178​，坏瓜占比$p_2=\frac {9}{17}$p2​=179​,计算出数据集$D$D的信息熵为
$Ent(D)=-\sum_{k=1}^{2}p_klog_2p_k=-(\frac{8}{17}log_2\frac{8}{17}+\frac{9}{17}log_2\frac{9}{17})=0.998$Ent(D)=−k=1∑2​pk​log2​pk​=−(178​log2​178​+179​log2​179​)=0.998

计算各个属性的信息增益

观察数据集可以发现，西瓜的属性有色泽、根蒂、敲声、纹理、脐部、触感，首先对色泽计算信息增益。

西瓜的色泽有青绿、乌黑和浅白三种情况，青绿记做$D^1$D1，乌黑记做$D^2$D2，浅白记做$D^3$D3;
对于$D^1$D1,其中正例占$\frac{3}{6}$63​,对于$D^2$D2,正例占$\frac{3}{6}$63​,分别计算它们的信息熵
$Ent(D^1)=-(\frac{3}{6}log_2\frac{3}{6}+\frac{3}{6}log_2\frac{3}{6})=1.000,$Ent(D1)=−(63​log2​63​+63​log2​63​)=1.000,
$Ent(D^2)=-(\frac{4}{6}log_2\frac{4}{6}+\frac{2}{6}log_2\frac{2}{6})=0.918,$Ent(D2)=−(64​log2​64​+62​log2​62​)=0.918,
$Ent(D^3=-\frac{1}{5}log_2\frac{1}{5}+\frac{4}{5}log_2\frac{4}{5})=0.722.$Ent(D3=−51​log2​51​+54​log2​54​)=0.722.
计算色泽的信息增益
$\begin{aligned} Gain(D,色泽) &=Ent(D)-\sum_{v=1}^{v=3}\frac{|D_v|}{|D|}Ent(D_v)\\ &=0.998-(\frac{6}{17}*1.000+\frac{6}{17}*0.918+\frac{5}{17}*0.722)\\ &=0.109 \end{aligned}$Gain(D,色泽)​=Ent(D)−v=1∑v=3​∣D∣∣Dv​∣​Ent(Dv​)=0.998−(176​∗1.000+176​∗0.918+175​∗0.722)=0.109​
用同样的方法可以计算出
$\begin{aligned} &Gain(D,根蒂)=0.143;Gain(D,敲声)=0.141;\\&Gain(D,纹理)=0.381;Gain(D,脐部)=0.289;\\&Gain(D,触感)=0.006 \end{aligned}$​Gain(D,根蒂)=0.143;Gain(D,敲声)=0.141;Gain(D,纹理)=0.381;Gain(D,脐部)=0.289;Gain(D,触感)=0.006​
其中纹理的信息增益最大，于是选择纹理作为数据集$D$D的划分标准，构造第一级的决策树

决策树算法对每一个分支结点继续进行划分，方法和上一步相同，最后生成的决策树如下