本文以西瓜數據集為例演示決策樹使用信息增益選擇最優劃分屬性的過程

西瓜數據集下載：傳送門

首先計算根節點的信息熵：

• 數據集分為好瓜、壞瓜，所以|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}?1.000+\frac{6}{17}?0.918+\frac{5}{17}?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個屬性均取得了最大的信息增益，此時可任選其一作為劃分屬性。同理，對每個分支結點進行類似操作，即可得到最終的決策樹