决策树最优属性选择

本文以西瓜数据集为例演示决策树使用信息增益选择最优划分属性的过程

西瓜数据集下载：传送门

首先计算根节点的信息熵：

• 数据集分为好瓜、坏瓜，所以|y|=2
• 根结点包含17个训练样例，其中好瓜共计8个样例，所占比例为8/17
• 坏瓜共计9个样例，所占比例为9/17

将数据带入信息熵公式，即可得到根结点的信息熵：

$$Ent(D)=-\left(\frac{8}{17}{\log }_2\frac{8}{17}+\frac{9}{17}{\log }_2\frac{9}{17}\right)=0.998$$

以属性色泽为例，其对应3个数据子集：

• D1(色泽=青绿)，包含{1，4，6，10，13，17}共6个样例，其中好瓜样例为{1，4，6}，比例为3/6，坏瓜样例为{10，13，17}，比例为3/6。将数据带入信息熵计算公式即可得到该结点的信息熵：1.000
• D2(色泽=乌黑)，包含{2，3，7，8，9，15}共6个样例，其中好瓜样例为{2，3，7，8}，比例为4/6，坏瓜样例为{9，15}，比例为2/6。将数据带入信息熵计算公式即可得到该结点的信息熵：0.918
• D1(色泽=浅白)，包含{5，11，12，14，16}共5个样例，其中好瓜样例为{5}，比例为1/5，坏瓜样例为{11，12，14，16}，比例为4/5。将数据带入信息熵计算公式即可得到该结点的信息熵：0.722

则计算色泽属性的信息增益为：

$$\begin{gathered} Gain(D,色泽)=Ent(D)-\sum _{v=1}^3\frac{|D^v|}{|D|}Ent(D) \\ =0.998-\left(\frac{6}{17}\ast 1.000+\frac{6}{17}\ast 0.918+\frac{5}{17}\ast 0.722\right)=0.109 \end{gathered}$$

同样的方法，计算其他属性的信息增益为：
$$\begin{gathered} Gain(D,根蒂)=0.143 \\ Gain(D,敲声)=0.141 \\ Gain(D,纹理)=0.381 \\ Gain(D,脐部)=0.289 \\ Gain(D,触感)=0.006 \end{gathered}$$

对比不同属性，我们发现纹理属性的信息增益最大，因此，纹理属性被选为划分属性：清晰{1，2，3，4，5，6，8，10，15}、稍糊{7，9，13，14，17}、模糊{11，12，16}

下一步，我们再看纹理=清晰的节点分支，该节点包含的样例集合D1中有编号为{1，2，3，4，5，6，8，10，15}共计9个样例，此时可用属性集合为{色泽，根蒂，敲声，脐部，触感}，纹理不会再作为划分属性，我们以同样的方式再计算各属性的信息增益为：

$$\begin{gathered} Gain(D,色泽)=0.043 \\ Gain(D,根蒂)=0.458 \\ Gain(D,敲声)=0.331 \\ Gain(D,脐部)=0.458 \\ Gain(D,触感)=0.458 \end{gathered}$$

从上图可以看出根蒂、脐部、触感3个属性均取得了最大的信息增益，此时可任选其一作为划分属性。同理，对每个分支结点进行类似操作，即可得到最终的决策树