决策树（信息熵、信息增溢、GINI）的计算

ゝ一纸荒年。 2022-11-24 15:26 159阅读 0赞

如何构建决策树，我需要选择什么属性来度量，这里我们需要通过计算才能更好的构建一棵决策树。

【有以下二分类问题训练样本】

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">outlook</td> 
 <td style="vertical-align:middle;width:135px;">temperat</td> 
 <td style="vertical-align:middle;width:138px;">humidity</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">windy</td> 
 <td style="vertical-align:middle;width:185px;">play</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">sunny</td> 
 <td style="vertical-align:middle;width:135px;">hot</td> 
 <td style="vertical-align:middle;width:138px;">high</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">FALSE</td> 
 <td style="vertical-align:middle;width:185px;">no</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">sunny</td> 
 <td style="vertical-align:middle;width:135px;">hot</td> 
 <td style="vertical-align:middle;width:138px;">high</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">TRUE</td> 
 <td style="vertical-align:middle;width:185px;">no</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">overcast</td> 
 <td style="vertical-align:middle;width:135px;">hot</td> 
 <td style="vertical-align:middle;width:138px;">high</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">FALSE</td> 
 <td style="vertical-align:middle;width:185px;">yes</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">rainy</td> 
 <td style="vertical-align:middle;width:135px;">mild</td> 
 <td style="vertical-align:middle;width:138px;">high</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">FALSE</td> 
 <td style="vertical-align:middle;width:185px;">yes</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">rainy</td> 
 <td style="vertical-align:middle;width:135px;">cool</td> 
 <td style="vertical-align:middle;width:138px;">normal&nbsp;</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">FALSE</td> 
 <td style="vertical-align:middle;width:185px;">yes</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">rainy</td> 
 <td style="vertical-align:middle;width:135px;">cool</td> 
 <td style="vertical-align:middle;width:138px;">normal&nbsp;</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">TRUE</td> 
 <td style="vertical-align:middle;width:185px;">no</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">overcast</td> 
 <td style="vertical-align:middle;width:135px;">cool</td> 
 <td style="vertical-align:middle;width:138px;">normal&nbsp;</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">TRUE</td> 
 <td style="vertical-align:middle;width:185px;">yes</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">sunny</td> 
 <td style="vertical-align:middle;width:135px;">mild</td> 
 <td style="vertical-align:middle;width:138px;">high</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">FALSE</td> 
 <td style="vertical-align:middle;width:185px;">no</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">sunny</td> 
 <td style="vertical-align:middle;width:135px;">cool</td> 
 <td style="vertical-align:middle;width:138px;">normal&nbsp;</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">FALSE</td> 
 <td style="vertical-align:middle;width:185px;">yes</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">rainy</td> 
 <td style="vertical-align:middle;width:135px;">mild</td> 
 <td style="vertical-align:middle;width:138px;">normal&nbsp;</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">FALSE</td> 
 <td style="vertical-align:middle;width:185px;">yes</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">sunny</td> 
 <td style="vertical-align:middle;width:135px;">mild</td> 
 <td style="vertical-align:middle;width:138px;">normal&nbsp;</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">TRUE</td> 
 <td style="vertical-align:middle;width:185px;">yes</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">overcast</td> 
 <td style="vertical-align:middle;width:135px;">mild</td> 
 <td style="vertical-align:middle;width:138px;">high</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">TRUE</td> 
 <td style="vertical-align:middle;width:185px;">yes</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">overcast</td> 
 <td style="vertical-align:middle;width:135px;">hot</td> 
 <td style="vertical-align:middle;width:138px;">normal&nbsp;</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">FALSE</td> 
 <td style="vertical-align:middle;width:185px;">yes</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;width:137px;">rainy</td> 
 <td style="vertical-align:middle;width:135px;">mild</td> 
 <td style="vertical-align:middle;width:138px;">high</td> 
 <td style="text-align:left;vertical-align:middle;width:135px;">TRUE</td> 
 <td style="vertical-align:middle;width:185px;">no</td> 
 </tr> 
 </tbody> 
</table>

然后我们将这个表格细分，如下所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZjIwMTc_size_16_color_FFFFFF_t_70][]

【信息熵的计算】

**信息熵**：表示信息的不确定度

从给出的数据我们可以看到，这个表格是通过天气、温度、湿度、有风为特征来判断是否去打球。

所以我们根据没有任何天气提示的情况下可以知道这一天打球大的概率为**9/14**，不打球的概率为**5/14**.

通过下面信息熵的公式（下面公式中：p(i|t) 代表了节点 t 为分类 i 的概率）

![20200806171258598.png][]

可以知道信息熵为：Entropy(D)=  ![20200806171348198.png][]

【信息增溢的计算】

**信息增益**：信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是**父亲节点的信息熵减去所有子节点的信息熵**。

信息增溢的计算公式：![20200806171902817.png][]

PS:公式中 D 是父亲节点，Di 是子节点，Gain(D,a)中的 a 作为 D 节点的属性选择。

下面我们来求基于outlook的划分来求**Gain(outlook)**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZjIwMTc_size_16_color_FFFFFF_t_70 1][]

从图中我们知道outlook取值为sunny、overcast、rainy的概率分别为：5/14、4/14、5/14

outlook=sunny时，有2/5打球、3/5不打球，故entropy=![\-2/5][-2_5]![$\\log\_22/5$][log_22_5] ![\-3/5$\\log\_23/5$][-3_5_log_23_5] ![=][gif.latex_3D]0.971

outlook= overcast时，有4个打球，概率为1，故entropy=0

outlook=rainy时，有3/5打球，2/5不打球，故entropy=![\-2/5][-2_5]![$\\log\_22/5$][log_22_5] ![\-3/5$\\log\_23/5$][-3_5_log_23_5] ![=][gif.latex_3D]0.971

则Entropy(outlook)=5/14\*0.971+4/14\*0+5/14\*0.971=0.693

所以信息增溢Gain(outlook)=Entropy(D)-Entropy(outlook)=0.940-0.693=0.247

同理，按照上面的步骤依次可以求得

Gain(temperature)=0.029    Gain(humidity)=0.152   Gain(windy)=0.048

根据上面的信息熵我们可以得出Gain(outlook) >  Gain(humidity) >  Gain(windy) > Gain(temperature)

从上面的计算结果中可以看出，**信息熵越大，纯度越低。当集合中的所有样本均匀混合时，信息熵最大，纯度最低。**

【基尼系数GINI的计算】

GINI 公式：![20200806173956830.png][]

同样以上面的样本为例，计算步骤如下：

outlook取值为sunny、overcast、rainy的概率分别为：5/14、4/14、5/14

outlook=sunny时，有2/5打球、3/5不打球，故GINI=1-（![$(2/5)^2$+$(3/5)^2$][2_5_2_3_5_2]）=0.64

outlook= overcast时，有4个打球，概率为1，故GINI=0

outlook=rainy时，有3/5打球，2/5不打球，故GINI=1-（![$(2/5)^2$+$(3/5)^2$][2_5_2_3_5_2]）=0.64

则GINI(outlook)=5/14\*0.64+4/14\*0+5/14\*0.64=0.457

temperature取值为hot、mild、cool的概率分别为：4/14、6/14、4/14

temperature=hot 时，有1/2打球，1/2不打球，故GINI=1-![($(1/2)^2$+$(1/2)^2$)=][1_2_2_1_2_2]0.5

temperature=mild 时，有2/3打球，1/3不打球，故GINI=![1-(($(2/3)^2$)+($(1/3)^2$))=0.444][1-_2_3_2_1_3_2_0.444]

temperature=cool 时，有3/4打球，1/4不打球，故![GINI=1-(($(1/4)^2$)+(($(3/4)^2$)))=0.375][GINI_1-_1_4_2_3_4_2_0.375]

则GINI(temperature)=4/14\*0.5+6/14\*0.444+4/14\*0.375=0.440

humidty取值为high和normal的概率分别为：1/2、1/2

humidty=high 时，有3/7打球，4/7不打球，故![GINI=1-(($(3/7)^2$)+($(4/7)^2$))=0.500][GINI_1-_3_7_2_4_7_2_0.500]

humidty=normal时，有6/7打球，1/7不打球，故![GINI=1-(($(1/7)^2$)+($(6/7)^2$))=0.245][GINI_1-_1_7_2_6_7_2_0.245]

则GINI(humidty)=1/2\*0.500+1/2\*0.245=0.373

windy取值为false和true的概率分别为：4/7，3/7

windy=false 时，有3/4打球，1/4不打球，故![GINI=1-(($(3/4)^2$)+($(1/4)^2$))=0.375][GINI_1-_3_4_2_1_4_2_0.375]

windy=true 事，有1/2打球，1/2不打球，故![GINI=1-(($(1/2)^2$)+($(1/2)^2$))=0.500][GINI_1-_1_2_2_1_2_2_0.500]

则GINI(windy)=1/2\*0.500+1/2\*0.375=0.434

【相关参考资料】

1.决策树：[https://www.cnblogs.com/molieren/articles/10664954.html][https_www.cnblogs.com_molieren_articles_10664954.html]

2.机器学习经典算法（2）——决策树与随机森林：[https://www.bilibili.com/video/BV1Ps411V7px?p=3][https_www.bilibili.com_video_BV1Ps411V7px_p_3]

3.决策树零基础入门教程：[https://www.bilibili.com/video/BV1T7411b7DG?from=search&seid=6628949932489280159][https_www.bilibili.com_video_BV1T7411b7DG_from_search_seid_6628949932489280159]

4.决策树（信息熵—GINI）计算习题：[https://blog.csdn.net/wsp\_1138886114/article/details/80955528][https_blog.csdn.net_wsp_1138886114_article_details_80955528]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZjIwMTc_size_16_color_FFFFFF_t_70]: /images/20221124/deaf34c0a11c4db9a9401f3e8546b5fe.png
[20200806171258598.png]: /images/20221124/6a28216db8654ae092ec2ebccf02a1ac.png
[20200806171348198.png]: /images/20221124/397b7adcd9c0431aacc482cd78dfcc9e.png
[20200806171902817.png]: /images/20221124/8d05a6ee86e94a20aae8c938b3ac562a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZjIwMTc_size_16_color_FFFFFF_t_70 1]: /images/20221124/579750212bd042db96fa0d18aa16ce1a.png
[-2_5]: https://private.codecogs.com/gif.latex?-2/5
[log_22_5]: https://private.codecogs.com/gif.latex?%24%5Clog_22/5%24
[-3_5_log_23_5]: https://private.codecogs.com/gif.latex?-3/5%24%5Clog_23/5%24
[gif.latex_3D]: https://private.codecogs.com/gif.latex?%3D
[20200806173956830.png]: /images/20221124/91806ff95a6041b08cc382555bc4875d.png
[2_5_2_3_5_2]: https://private.codecogs.com/gif.latex?%24%282/5%29%5E2%24&plus;%24%283/5%29%5E2%24
[1_2_2_1_2_2]: https://private.codecogs.com/gif.latex?%28%24%281/2%29%5E2%24&plus;%24%281/2%29%5E2%24%29%3D
[1-_2_3_2_1_3_2_0.444]: https://private.codecogs.com/gif.latex?1-%28%28%24%282/3%29%5E2%24%29&plus;%28%24%281/3%29%5E2%24%29%29%3D0.444
[GINI_1-_1_4_2_3_4_2_0.375]: https://private.codecogs.com/gif.latex?GINI%3D1-%28%28%24%281/4%29%5E2%24%29&plus;%28%28%24%283/4%29%5E2%24%29%29%29%3D0.375
[GINI_1-_3_7_2_4_7_2_0.500]: https://private.codecogs.com/gif.latex?GINI%3D1-%28%28%24%283/7%29%5E2%24%29&plus;%28%24%284/7%29%5E2%24%29%29%3D0.500
[GINI_1-_1_7_2_6_7_2_0.245]: https://private.codecogs.com/gif.latex?GINI%3D1-%28%28%24%281/7%29%5E2%24%29&plus;%28%24%286/7%29%5E2%24%29%29%3D0.245
[GINI_1-_3_4_2_1_4_2_0.375]: https://private.codecogs.com/gif.latex?GINI%3D1-%28%28%24%283/4%29%5E2%24%29&plus;%28%24%281/4%29%5E2%24%29%29%3D0.375
[GINI_1-_1_2_2_1_2_2_0.500]: https://private.codecogs.com/gif.latex?GINI%3D1-%28%28%24%281/2%29%5E2%24%29&plus;%28%24%281/2%29%5E2%24%29%29%3D0.500
[https_www.cnblogs.com_molieren_articles_10664954.html]: https://www.cnblogs.com/molieren/articles/10664954.html
[https_www.bilibili.com_video_BV1Ps411V7px_p_3]: https://www.bilibili.com/video/BV1Ps411V7px?p=3
[https_www.bilibili.com_video_BV1T7411b7DG_from_search_seid_6628949932489280159]: https://www.bilibili.com/video/BV1T7411b7DG?from=search&seid=6628949932489280159
[https_blog.csdn.net_wsp_1138886114_article_details_80955528]: https://blog.csdn.net/wsp_1138886114/article/details/80955528