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

西瓜數(shù)據(jù)集下載：傳送門

首先計算根節(jié)點的信息熵：

• 數(shù)據(jù)集分為好瓜、壞瓜，所以|y|=2
• 根結(jié)點包含17個訓(xùn)練樣例，其中好瓜共計8個樣例，所占比例為8/17
• 壞瓜共計9個樣例，所占比例為9/17

將數(shù)據(jù)帶入信息熵公式，即可得到根結(jié)點的信息熵：

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

以屬性色澤為例，其對應(yīng)3個數(shù)據(jù)子集：

• D1(色澤=青綠)，包含{1，4，6，10，13，17}共6個樣例，其中好瓜樣例為{1，4，6}，比例為3/6，壞瓜樣例為{10，13，17}，比例為3/6。將數(shù)據(jù)帶入信息熵計算公式即可得到該結(jié)點的信息熵：1.000
• D2(色澤=烏黑)，包含{2，3，7，8，9，15}共6個樣例，其中好瓜樣例為{2，3，7，8}，比例為4/6，壞瓜樣例為{9，15}，比例為2/6。將數(shù)據(jù)帶入信息熵計算公式即可得到該結(jié)點的信息熵：0.918
• D1(色澤=淺白)，包含{5，11，12，14，16}共5個樣例，其中好瓜樣例為{5}，比例為1/5，壞瓜樣例為{11，12，14，16}，比例為4/5。將數(shù)據(jù)帶入信息熵計算公式即可得到該結(jié)點的信息熵：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}$$

對比不同屬性，我們發(fā)現(xiàn)紋理屬性的信息增益最大，因此，紋理屬性被選為劃分屬性：清晰{1，2，3，4，5，6，8，10，15}、稍糊{7，9，13，14，17}、模糊{11，12，16}

下一步，我們再看紋理=清晰的節(jié)點分支，該節(jié)點包含的樣例集合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個屬性均取得了最大的信息增益，此時可任選其一作為劃分屬性。同理，對每個分支結(jié)點進行類似操作，即可得到最終的決策樹