题目

基于信息增益，对下述数据集进行决策树构建，描述过程

一个关于配眼镜的一个决策分类所需要的数据，数据集包含4属性：age, astigmatism, trear-prod-rate为输入特征，contact-lenses为决策属性。

属性集A={AGE,AST,TEA}A=\{AGE,AST,TEA\}A={AGE,AST,TEA}，类别为$CON$。计算根节点的信息熵
$$Ent(D)=-(\frac{2}{12}{\log }_2\frac{2}{12}+\frac{3}{12}{\log }_2\frac{3}{12}+\frac{7}{12}{\log }_2\frac{7}{12})=1.384$$
计算每个属性的信息熵和信息增益，记$p(soft)=p_1,p(hard)=p_2,p(none)=p_3$，

1. $AGE$

   有三个可能取值{young,pre−pre,pre}\{young,pre-pre,pre\}{young,pre−pre,pre}，对应下标$1,2,3$
   D1={1,2,3}p1=13, p2=13, p3=13Ent(D1)=−(13log⁡213+13log⁡213+13log⁡213)=1.585D2={4,5,6,7,8}p1=15, p2=15, p3=35Ent(D2)=−(15log⁡215+15log⁡215+35log⁡235)=1.371D3={9,10,11,12}p1=0, p2=14, p3=34Ent(D3)=−(14log⁡214+34log⁡234)=0.811Gain(D,AGE)=Ent(D)−∑v=13∣Dv∣∣D∣Ent(Dv)=1.384−312×1.585−512×1.371−412×0.811=0.146 \begin{aligned} &D^1=\{1,2,3\} \quad p_1=\frac{1}{3},\ p_2=\frac{1}{3},\ p_3=\frac{1}{3} \quad Ent(D^1)=-(\frac{1}{3}\log_2{\frac{1}{3}}+\frac{1}{3}\log_2{\frac{1}{3}}+\frac{1}{3}\log_2{\frac{1}{3}})=1.585 \\ &D^2=\{4,5,6,7,8\} \quad p_1=\frac{1}{5},\ p_2=\frac{1}{5},\ p_3=\frac{3}{5} \quad Ent(D^2)=-(\frac{1}{5}\log_2{\frac{1}{5}}+\frac{1}{5}\log_2{\frac{1}{5}}+\frac{3}{5}\log_2{\frac{3}{5}})=1.371 \\ &D^3=\{9,10,11,12\} \quad p_1=0,\ p_2=\frac{1}{4},\ p_3=\frac{3}{4} \quad Ent(D^3)=-(\frac{1}{4}\log_2{\frac{1}{4}}+\frac{3}{4}\log_2{\frac{3}{4}})=0.811 \\ &Gain(D,AGE)=Ent(D)-\sum_{v=1}^3 \frac{|D^v|}{|D|}Ent(D^v)=1.384-\frac{3}{12}\times 1.585-\frac{5}{12}\times 1.371-\frac{4}{12}\times 0.811=0.146 \end{aligned} ​D1={1,2,3}p1​=31​, p2​=31​, p3​=31​Ent(D1)=−(31​log2​31​+31​log2​31​+31​log2​31​)=1.585D2={4,5,6,7,8}p1​=51​, p2​=51​, p3​=53​Ent(D2)=−(51​log2​51​+51​log2​51​+53​log2​53​)=1.371D3={9,10,11,12}p1​=0, p2​=41​, p3​=43​Ent(D3)=−(41​log2​41​+43​log2​43​)=0.811Gain(D,AGE)=Ent(D)−v=1∑3​∣D∣∣Dv∣​Ent(Dv)=1.384−123​×1.585−125​×1.371−124​×0.811=0.146​

2. $AST$

   有两个可能取值{yes,no}\{yes,no\}{yes,no}，对应下标$1,2$
   D1={2,3,6,7,8,11,12}p1=0, p2=37, p3=47Ent(D1)=−(37log⁡237+47log⁡247)=0.985D2={1,4,5,9,10}p1=25, p2=0, p3=35Ent(D2)=−(25log⁡225+35log⁡235)=0.971Gain(D,AST)=Ent(D)−∑v=12∣Dv∣∣D∣Ent(Dv)=1.384−712×0.985−512×0.971=0.405 \begin{aligned} &D^1=\{2,3,6,7,8,11,12\} \quad p_1=0,\ p_2=\frac{3}{7},\ p_3=\frac{4}{7} \quad Ent(D^1)=-(\frac{3}{7}\log_2{\frac{3}{7}}+\frac{4}{7}\log_2{\frac{4}{7}})=0.985 \\ &D^2=\{1,4,5,9,10\} \quad p_1=\frac{2}{5},\ p_2=0,\ p_3=\frac{3}{5} \quad Ent(D^2)=-(\frac{2}{5}\log_2{\frac{2}{5}}+\frac{3}{5}\log_2{\frac{3}{5}})=0.971 \\ &Gain(D,AST)=Ent(D)-\sum_{v=1}^2 \frac{|D^v|}{|D|}Ent(D^v)=1.384-\frac{7}{12}\times 0.985-\frac{5}{12}\times 0.971=0.405 \end{aligned} ​D1={2,3,6,7,8,11,12}p1​=0, p2​=73​, p3​=74​Ent(D1)=−(73​log2​73​+74​log2​74​)=0.985D2={1,4,5,9,10}p1​=52​, p2​=0, p3​=53​Ent(D2)=−(52​log2​52​+53​log2​53​)=0.971Gain(D,AST)=Ent(D)−v=1∑2​∣D∣∣Dv∣​Ent(Dv)=1.384−127​×0.985−125​×0.971=0.405​

3. $TEA$

   有两个可能的取值{normal,reduced}\{normal,reduced\}{normal,reduced}，对应下标$1,2$
   D1={1,3,5,6,7,8,10,12}p1=28, p2=38, p3=38Ent(D1)=−(28log⁡228+38log⁡238+38log⁡238)=1.561D2={2,4,9,11}p1=0, p2=0, p3=1Ent(D2)=−(1log⁡21)=0Gain(D,TEA)=Ent(D)−∑v=12∣Dv∣∣D∣Ent(Dv)=1.384−812×1.561−512×0=0.343 \begin{aligned} &D^1=\{1,3,5,6,7,8,10,12\} \quad p_1=\frac{2}{8},\ p_2=\frac{3}{8},\ p_3=\frac{3}{8} \quad Ent(D^1)=-(\frac{2}{8}\log_2{\frac{2}{8}}+\frac{3}{8}\log_2{\frac{3}{8}}+\frac{3}{8}\log_2{\frac{3}{8}})=1.561 \\ &D^2=\{2,4,9,11\} \quad p_1=0,\ p_2=0,\ p_3=1 \quad Ent(D^2)=-(1\log_2{1})=0 \\ &Gain(D,TEA)=Ent(D)-\sum_{v=1}^2 \frac{|D^v|}{|D|}Ent(D^v)=1.384-\frac{8}{12}\times 1.561-\frac{5}{12}\times 0=0.343 \end{aligned} ​D1={1,3,5,6,7,8,10,12}p1​=82​, p2​=83​, p3​=83​Ent(D1)=−(82​log2​82​+83​log2​83​+83​log2​83​)=1.561D2={2,4,9,11}p1​=0, p2​=0, p3​=1Ent(D2)=−(1log2​1)=0Gain(D,TEA)=Ent(D)−v=1∑2​∣D∣∣Dv∣​Ent(Dv)=1.384−128​×1.561−125​×0=0.343​

于是，$Gain(D,AST)$最大，选它为划分属性，

对左分支节点划分，可用属性集A={AGE,TEA}A=\{AGE,TEA\}A={AGE,TEA}，类别为$CON$。该节点的信息熵$Ent(D^1)=0.985$。计算每个属性的信息熵和信息增益，记$p(soft)=p_1,p(hard)=p_2,p(none)=p_3$，

1. $AGE$

   有三个可能取值{young,pre−pre,pre}\{young,pre-pre,pre\}{young,pre−pre,pre}，对应下标$1,2,3$
   D11={2,3}p1=0, p2=12, p3=12Ent(D11)=−(12log⁡212+12log⁡212)=1.000D12={6,7,8}p1=0, p2=13, p3=23Ent(D12)=−(13log⁡213+23log⁡223)=0.918D13={11,12}p1=0, p2=12, p3=12Ent(D13)=−(12log⁡212+12log⁡212)=1.000Gain(D1,AGE)=Ent(D)−∑v=13∣D1v∣∣D1∣Ent(D1v)=0.985−27×1.000−37×0.918−27×1.000=0.020 \begin{aligned} &D^{11}=\{2,3\} \quad p_1=0,\ p_2=\frac{1}{2},\ p_3=\frac{1}{2} \quad Ent(D^{11})=-(\frac{1}{2}\log_2{\frac{1}{2}}+\frac{1}{2}\log_2{\frac{1}{2}})=1.000 \\ &D^{12}=\{6,7,8\} \quad p_1=0,\ p_2=\frac{1}{3},\ p_3=\frac{2}{3} \quad Ent(D^{12})=-(\frac{1}{3}\log_2{\frac{1}{3}}+\frac{2}{3}\log_2{\frac{2}{3}})=0.918 \\ &D^{13}=\{11,12\} \quad p_1=0,\ p_2=\frac{1}{2},\ p_3=\frac{1}{2} \quad Ent(D^{13})=-(\frac{1}{2}\log_2{\frac{1}{2}}+\frac{1}{2}\log_2{\frac{1}{2}})=1.000 \\ &Gain(D^1,AGE)=Ent(D)-\sum_{v=1}^3 \frac{|D^{1v}|}{|D^1|}Ent(D^{1v})=0.985-\frac{2}{7}\times 1.000-\frac{3}{7}\times 0.918-\frac{2}{7}\times 1.000=0.020 \end{aligned} ​D11={2,3}p1​=0, p2​=21​, p3​=21​Ent(D11)=−(21​log2​21​+21​log2​21​)=1.000D12={6,7,8}p1​=0, p2​=31​, p3​=32​Ent(D12)=−(31​log2​31​+32​log2​32​)=0.918D13={11,12}p1​=0, p2​=21​, p3​=21​Ent(D13)=−(21​log2​21​+21​log2​21​)=1.000Gain(D1,AGE)=Ent(D)−v=1∑3​∣D1∣∣D1v∣​Ent(D1v)=0.985−72​×1.000−73​×0.918−72​×1.000=0.020​

2. $TEA$

   有两个可能的取值{normal,reduced}\{normal,reduced\}{normal,reduced}，对应下标$1,2$
   D11={3,6,7,8,12}p1=0, p2=35, p3=25Ent(D1)=−(35log⁡235+25log⁡225)=0.971D12={2,11}p1=0, p2=0, p3=1Ent(D2)=−(1log⁡21)=0Gain(D1,TEA)=Ent(D1)−∑v=12∣D1v∣∣D1∣Ent(D1v)=0.985−57×0.971−27×0=0.291 \begin{aligned} &D^{11}=\{3,6,7,8,12\} \quad p_1=0,\ p_2=\frac{3}{5},\ p_3=\frac{2}{5} \quad Ent(D^1)=-(\frac{3}{5}\log_2{\frac{3}{5}}+\frac{2}{5}\log_2{\frac{2}{5}})=0.971 \\ &D^{12}=\{2,11\} \quad p_1=0,\ p_2=0,\ p_3=1 \quad Ent(D^2)=-(1\log_2{1})=0 \\ &Gain(D^1,TEA)=Ent(D^1)-\sum_{v=1}^2 \frac{|D^{1v}|}{|D^1|}Ent(D^{1v})=0.985-\frac{5}{7}\times 0.971-\frac{2}{7}\times 0=0.291 \end{aligned} ​D11={3,6,7,8,12}p1​=0, p2​=53​, p3​=52​Ent(D1)=−(53​log2​53​+52​log2​52​)=0.971D12={2,11}p1​=0, p2​=0, p3​=1Ent(D2)=−(1log2​1)=0Gain(D1,TEA)=Ent(D1)−v=1∑2​∣D1∣∣D1v∣​Ent(D1v)=0.985−75​×0.971−72​×0=0.291​

于是，$Gain(D^1,TEA)$最大，选它为划分属性，

继续对左分支节点划分，可用属性集A={AGE}A=\{AGE\}A={AGE}，类别为$CON$。选它为划分属性，得到$D^{111},D^{112},D^{113}$，此时属性集合为空，将这三个节点设为叶子节点，其中$D^{112}$中$p_2=\frac{1}{3},p_3=\frac{2}{3}$，因此将$D^{112}$对应叶子节点标注为$none$类别，其余两个节点中只有一个样本，将叶子节点标记为对应样本类别，返回。考察$D^{12}$，包含样本均属同一类别$none$，则将$D^{12}$标记为$none$。

回到一层，对一层右分支节点划分，可用属性集A={AGE,TEA}A=\{AGE,TEA\}A={AGE,TEA}，类别为$CON$。该节点的信息熵$Ent(D^1)=0.971$。计算每个属性的信息熵和信息增益，记$p(soft)=p_1,p(hard)=p_2,p(none)=p_3$，

1. $AGE$

   有三个可能取值{young,pre−pre,pre}\{young,pre-pre,pre\}{young,pre−pre,pre}，对应下标$1,2,3$
   D21={1}p1=1, p2=0, p3=0Ent(D11)=−(1log⁡21)=0.000D22={4,5}p1=0, p2=12, p3=12Ent(D12)=−(12log⁡212+12log⁡212)=1.000D23={9,10}p1=0, p2=0, p3=1Ent(D13)=−(1log⁡21)=0.000Gain(D2,AGE)=Ent(D2)−∑v=13∣D2v∣∣D2∣Ent(D2v)=0.971−15×0.000−25×1.000−25×0.000=0.571 \begin{aligned} &D^{21}=\{1\} \quad p_1=1,\ p_2=0,\ p_3=0 \quad Ent(D^{11})=-(1\log_2 1)=0.000 \\ &D^{22}=\{4,5\} \quad p_1=0,\ p_2=\frac{1}{2},\ p_3=\frac{1}{2} \quad Ent(D^{12})=-(\frac{1}{2}\log_2{\frac{1}{2}}+\frac{1}{2}\log_2{\frac{1}{2}})=1.000 \\ &D^{23}=\{9,10\} \quad p_1=0,\ p_2=0,\ p_3=1 \quad Ent(D^{13})=-(1\log_2{1})=0.000 \\ &Gain(D^2,AGE)=Ent(D^2)-\sum_{v=1}^3 \frac{|D^{2v}|}{|D^2|}Ent(D^{2v})=0.971-\frac{1}{5}\times 0.000-\frac{2}{5}\times 1.000-\frac{2}{5}\times 0.000=0.571 \end{aligned} ​D21={1}p1​=1, p2​=0, p3​=0Ent(D11)=−(1log2​1)=0.000D22={4,5}p1​=0, p2​=21​, p3​=21​Ent(D12)=−(21​log2​21​+21​log2​21​)=1.000D23={9,10}p1​=0, p2​=0, p3​=1Ent(D13)=−(1log2​1)=0.000Gain(D2,AGE)=Ent(D2)−v=1∑3​∣D2∣∣D2v∣​Ent(D2v)=0.971−51​×0.000−52​×1.000−52​×0.000=0.571​

2. $TEA$

   有两个可能的取值{normal,reduced}\{normal,reduced\}{normal,reduced}，对应下标$1,2$
   D21={1,5,10}p1=23, p2=0, p3=13Ent(D1)=−(23log⁡223+13log⁡213)=0.918D22={4,9}p1=0, p2=0, p3=1Ent(D2)=−(1log⁡21)=0Gain(D2,TEA)=Ent(D2)−∑v=12∣D2v∣∣D2∣Ent(D2v)=0.971−35×0.918=0.420 \begin{aligned} &D^{21}=\{1,5,10\} \quad p_1=\frac{2}{3},\ p_2=0,\ p_3=\frac{1}{3} \quad Ent(D^1)=-(\frac{2}{3}\log_2{\frac{2}{3}}+\frac{1}{3}\log_2{\frac{1}{3}})=0.918 \\ &D^{22}=\{4,9\} \quad p_1=0,\ p_2=0,\ p_3=1 \quad Ent(D^2)=-(1\log_2{1})=0 \\ &Gain(D^2,TEA)=Ent(D^2)-\sum_{v=1}^2 \frac{|D^{2v}|}{|D^2|}Ent(D^{2v})=0.971-\frac{3}{5}\times 0.918=0.420 \end{aligned} ​D21={1,5,10}p1​=32​, p2​=0, p3​=31​Ent(D1)=−(32​log2​32​+31​log2​31​)=0.918D22={4,9}p1​=0, p2​=0, p3​=1Ent(D2)=−(1log2​1)=0Gain(D2,TEA)=Ent(D2)−v=1∑2​∣D2∣∣D2v∣​Ent(D2v)=0.971−53​×0.918=0.420​

于是，$Gain(D^2,AGE)$最大，选它为划分属性，

考察$D^{21}$，由于只有一个样本，所以直接将$D^{21}$设置为叶子节点，标记为$soft$，返回到$D^{22}$.此时可用的属性集A={TEA}A=\{TEA\}A={TEA}，选它为划分属性，此时属性集为空，将这两个节点设置为叶子节点，这两个叶子节点中都只有一个样本，于是标记为对应样本类别，返回。考察$D^{23}$，其中样本全部属于类别$none$，所以直接将$D^{23}$设置为叶子节点，标记为$none$。最终得到决策树