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 信息熵的计算

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

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

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：

1. 当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

2. 当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

3. 当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

4. H(D|temperature)=(4.0/14)* 0.8113+(4.0/14)* 1.0000+(6.0/14)* 0.9183=0.9111

humidity：

1. 当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

2. 当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

3. H(D|humidity)=(7.0/14)* 0.9852+(7.0/14)* 0.5917=0.7885

windy：

1. 当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

2. 当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

3. H(D|windy)=(8.0/14)* 0.8113+(6.0/14)* 1.0000=0.8922

1.4.5 信息增益

g(D,A)表示在条件A下对于目标变量D的信息增益。

1.4.6 信息增益的计算

根据上文介绍的信息熵(1.4.1节)、条件熵(1.4.3节)，计算所给数据集(1.4.2节)的信息增益如下所示。

2 决策树构建

2.1 ID3算法

• 构造根节点。具体构造方法如下图(2-1)所示。
  
• 构造D1。具体构造方法如下图(2-2)所示。
  
• 构造D2。具体构造方法如下图(2-3)所示。
  
  到此决策树已经构造完成。由于所给数据集构造的决策树较简单，相对于其他数据集可能并非如此，在构造复杂的决策树时，对每个子集重复上述方法，直到满足停止条件。

3 结语

如有错误请指正，禁止商用。