机器学习之——决策树构建原理

cnblogs 2024-08-26 08:13:00 阅读 88

0 前言

本文使用了大量的配图帮助读者理解。

1 理论基础

1.1 决策树的原型

决策树思想的来源非常朴素，程序设计中的条件分支结构就是if-then结构，最早的决策树就是利用这类结构分割数据的一种分类学习方法。

1.2 例子1

通过不同的限制条件来过滤样本进行决策。

1.3 例子二

有银行贷款数据如下图(1-1)所示，银行根据每个人的条件来决定是否给他(她)贷款，假如一个人没车没房没存款没老婆没工作，银行给他贷款的话猪都会飞了。

对于下图(1-2)来说，考虑一个问题，如何进行决策呢？哪种决策方案更好？是工作放在第一位还是年龄放在第一位？

针对以上问题，无法用直观思维解决，故需要数学原理为依靠。

1.4 决策树数学原理

1.4.1 信息熵

笔者使用下图(1-3)直观理解信息熵的含义。

信息熵越大，表示该随机变量的不确定性越高。对于均匀分布，信息熵达到最大值。

1.4.2 信息熵的计算

假设有以下数据(后文使用该数据集)，用于决策是否出去玩。

属性outlook表示户外天气。sunny晴天，overcast阴天，rainy雨天。
属性temperature表示温度，hot热，mild温暖，cool冷。
属性humidity表示湿度。high高，normal正常。
属性windy表示是否有风。not没有，yes有。
属性play表示是否出去玩。yes出去玩，no不出去玩。
li>

点击查看数据(CSV格式)

<code>id,outlook,temperature,humidity,windy,play

1,sunny,hot,high,not,no

2,sunny,hot,high,yes,no

3,overcast,hot,high,not,yes

4,rainy,mild,high,not,yes

5,rainy,cool,normal,not,yes

6,rainy,cool,normal,yes,no

7,overcast,cool,normal,yes,yes

8,sunny,mild,high,not,no

9,sunny,cool,normal,not,yes

10,rainy,mild,normal,not,yes

11,sunny,mild,normal,yes,yes

12,overcast,mild,high,yes,yes

13,overcast,hot,normal,not,yes

14,rainy,mild,high,yes,no

令该数据集为D，其中数据总样本14个，play=no有5个，play=yes有9个，p(play=no)=5/14，p(play=yes)=9/14，则数据集D的信息熵计算公式如下所示。

信息熵的计算公式为什么是这样？log函数如下图(1-4)所示，根据概率论，假设某事情p的发生概率>0且<1，即0<p<1，有-∞<log2(p)<0。当出现极端情况，例如p=0或1(p=0或1表示信息很确定,而信息熵是衡量变量不确定性)，则根据信息熵公式值为0，log2()函数所得出来的值是负的，需要再添加负号使信息熵变为正值。

1.4.3 条件熵

1.4.4 条件熵的计算

仍使用上文所给的游玩数据集(1.4.2节)。计算H(D|outlook)的条件熵。笔者将Outlook属性排序后如下图(1-5)所示。

对属性Outlook分析并计算如下。

其中相应的运算数据笔者已用相应的颜色标注。属性"Play=yes个数"表示当outlook=overcast条件下的数据中有几个play为yes的样本。属性"P(play=yes)"表示当outlook=overcast条件下play为yes的概率。

笔者分别计算temperature、humidity、windy的条件熵如下所示。

temperature：

当temperature=cool时,样本有4个,play=no有1个

当temperature=cool时,样本有4个,play=yes有3个

H(D|temperature=cool)=-(1.0/4.0)log2(1.0/4.0)-(3.0/4.0)log2(3.0/4.0)=0.8113

当temperature=hot时,样本有4个,play=no有2个
当temperature=hot时,样本有4个,play=yes有2个
H(D|temperature=hot)=-(2.0/4.0)log2(2.0/4.0)-(2.0/4.0)log2(2.0/4.0)=1.0000
当temperature=mild时,样本有6个,play=no有2个
当temperature=mild时,样本有6个,play=yes有4个
H(D|temperature=mild)=-(2.0/6.0)log2(2.0/6.0)-(4.0/6.0)log2(4.0/6.0)=0.9183
H(D|temperature)=(4.0/14)* 0.8113+(4.0/14)* 1.0000+(6.0/14)* 0.9183=0.9111

humidity：

当humidity=high时,样本有7个,play=no有4个
当humidity=high时,样本有7个,play=yes有3个
H(D|humidity=high)=-(4.0/7.0)log2(4.0/7.0)-(3.0/7.0)log2(3.0/7.0)=0.9852
当humidity=normal时,样本有7个,play=no有1个
当humidity=normal时,样本有7个,play=yes有6个
H(D|humidity=normal)=-(1.0/7.0)log2(1.0/7.0)-(6.0/7.0)log2(6.0/7.0)=0.5917
H(D|humidity)=(7.0/14)* 0.9852+(7.0/14)* 0.5917=0.7885

windy：

当windy=not时,样本有8个,play=no有2个
当windy=not时,样本有8个,play=yes有6个
H(D|windy=not)=-(2.0/8.0)log2(2.0/8.0)-(6.0/8.0)log2(6.0/8.0)=0.8113
当windy=yes时,样本有6个,play=no有3个
当windy=yes时,样本有6个,play=yes有3个
H(D|windy=yes)=-(3.0/6.0)log2(3.0/6.0)-(3.0/6.0)log2(3.0/6.0)=1.0000
H(D|windy)=(8.0/14)* 0.8113+(6.0/14)* 1.0000=0.8922