朴素贝叶斯学完了，但是其公式还存在一点点问题：因为公式的分母有可能为0。怎么解决呢？看本篇要讲的模型-决策树

以挑苹果为例，从颜色、硬度、香味得出结论判定苹果的好坏

颜色

硬度

香味

结论

0

红色

硬

香

好苹果

1

红色

硬

无味

好苹果

2

红色

软

无味

坏苹果

3

绿色

硬

香

好苹果

4

绿色

硬

无味

坏苹果

5

绿色

软

无味

坏苹果

根据分类可以画出树状结构

看下图信用预测的例子

最顶端的叫根结点，所有样本的预测都是从根节点开始的。每一个圆形节点表示判断，每个节点只对样本的某个属性进行判断；矩形节点是标记节点，走到矩形节点表示判断结束，将矩形节点中的标签作为对应的预测结果

那么怎么构建决策树呢，是样本中按顺序把每个特征依次比较判断吗？

如果苹果的样本还有一个特征叫形状，再建立球形和立方形两个分支，显然所有的样本都会到球形分支里面去，这样的判断没有进行有效地划分

此外根据某个特征X，10个苹果中9个会进入A分支，1个进入B分支。而根据另一个特征Y，5个进入A分支，5个进入B分支，显然特征Y要好

决策树模型建立步骤

1.目前来看，决策树的预测阶段，每进来一个样本，根据判断节点实际情况，对对应的特征进行判断，直到走到标记节点

2.如何构建决策树？两种方式：1.按顺序对每一个特征进行判断；2.每个判断节点都尽可能让一半进入A分支，另一半进入B分支。显然，第二种方式比第一种方式更高效

信息熵

还是以上面举的挑苹果的例子来解释信息熵：1.每走一步，我们都在确定苹果的好坏；2.在根节点时，我们对苹果的好坏一无所知；3.经过对颜色的判断后，如果是红色，我们明白好坏的概率是1/2；4.如果苹果红色的前提下又硬，我们100%确定它是好苹果。此时不确定性坍塌为0；5.这是一个减少不确定的过程

信息熵就是减少信息的不确定性的过程(讲到过程，想到了之前微分的概念：求导的过程就是微分)。在信息论与概率统计中，熵是表示随机变量不确定性的度量，设X是一个去有限个值的离散随机变量，其概率分布为

P(X = ) = , i = 1,2,...n

则随机变量X的熵定义为 H(X) =

熵越大，则随机变量的不确定性越大，其中0 H(P)log n

注：1.log不标注的情况下底数默认为2

2.log n的由来见下图

例 有10个苹果，1个好苹果A，9个坏苹果B。熵的计算如下：

如果是5个好苹果5个坏苹果，熵是多少呢？

1个好苹果9个坏苹果时，我们可以认为大部分都是坏苹果。内部并不混乱，确定性很大，熵就小

5个坏苹果5个好苹果时，里面就有点乱了，我们并不太能确定随机的一个苹果是好苹果还是坏苹果，熵就大

信息熵

1.在根节点的最初，先假设信息熵为最大，表示对于这个苹果一无所知

2.到叶节点时假设信息熵为0，表示我们非常确定

3.我们希望尽可能少的次数就能判断出苹果的好坏。就就是希望每个判断节点都能让信息熵下降地快一点

信息增益

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度

特征A对训练集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即 g(D|A) = H(D) - [H(| A) + H(| A)

好的模型选择，信息增益肯定是大于0的

信息增益算法

输入：训练数据集D和特征A

输出：特征A对训练数据集D的信息增益g(D,A)

1)计算数据集D的经验熵H(D)

2)计算特征A对数据集D的经验条件熵H(D|A)

3)计算信息增益

g(D,A) = H(D) - H(D|A)

例

ID

年龄

有工作

有自己的房子

信贷情况

类别

1

青年

否

否

一般

否

2

青年

否

否

好

否

3

青年

是

否

好

是

4

青年

是

是

一般

是

5

青年

否

否

一般

否

6

中年

否

否

一般

否

7

中年

否

否

好

否

8

中年

是

是

好

是

9

中年

否

是

非常好

是

10

中年

否

是

非常好

是

11

老年

否

是

非常好

是

12

老年

否

是

好

是

13

老年

是

否

好

是

14

老年

是

否

非常好

是

15

老年

否

否

一般

否

对上表所给的训练数据集D，根据信息增益准则选择最优特征。首先计算经验熵H(D)

计算结果表明，“有自己的房子”的这个特征的信息增益最大

信息增益比

如果以信息增益为划分依据，存在偏向选择取值较多的特征，信息增益比是对这一问题进行矫正

什么是信息增益比呢？ 特征A对训练数据集D的信息增益比(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的经验熵H(D)之比：

决策树的构建

决策树的构建包括ID3算法和C4.5算法。两种算法的区别就在于ID3算法用信息增益选择最大特征，C4.5算法用信息增益比选择最大特征

ID3算法：输入：训练数据集D，特征A，阈值；

输出：决策树T

（1）若D中所有实例属于同一类,则T为单结点树，并将作为该节点的类标记，返回T；

（2）若A = ，则T为单节点树，并将D中实例数最大的类 作为该结点的类标记，返回T；

（3）否则，计算A中各特征对D的信息增益，选择信息增益最大的特征;

（4）如果的信息增益小于阈值，则置T为单结点树，并将D中实例数最大的类作为该结点的类标记，返回T；

（5）否则，对的每一个可能值,依=将D分割为若干个非空子集，将中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；

（6）对第i个子结点，以为训练集，以 A - {}为特征集，递归地调用步骤(1)和步骤(5)，得到子树，返回

C4.5算法：

ID3算法：输入：训练数据集D，特征A，阈值；

输出：决策树T

（1）若D中所有实例属于同一类,则T为单结点树，并将作为该节点的类标记，返回T；

（2）若A = ，则T为单节点树，并将D中实例数最大的类 作为该结点的类标记，返回T；

（3）否则，计算A中各特征对D的信息增益比，选择信息增益最大的特征;

（4）如果的信息增益小于阈值，则置T为单结点树，并将D中实例数最大的类作为该结点的类标记，返回T；

（5）否则，对的每一个可能值,依=将D分割为若干个非空子集，将中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；

（6）对第i个子结点，以为训练集，以 A - {}为特征集，递归地调用步骤(1)和步骤(5)，得到子树，返回

总结

1.决策树的核心思想：以树结构为基础，每个节点对某特征进行判断，进入分支，直到到达叶结点

2.决策树构造的核心思想：让信息熵快速下降，从而达到最少的判断次数获得标签

3.判断信息熵下降速度的方法：信息增益/信息增益比

4.构建决策树算法：ID3(使用信息增益)、C4.5(使用信息增益比)

5.信息增益会导致节点偏向选取取值较多的特征问题

视频学习链接：

#头条创作挑战赛#