结构

• 决策树原理

  • 决策理论
  • 学习过程

• 特征选择与决策树生成

  • 熵模型：信息与信息熵
  • ID3 算法：信息增益
  • C4.5 算法：信息增益比
  • CART 算法：基尼系数
  • 决策树剪枝

决策树原理

来自人的决策经验

决策树类似我们人的决策过程。比如买北京学区房。就读学校是什么？预算？面积？

x = {x_1, x_2, \dots,x_n}

决策树算法利用树形结构，使用层层递进提问得到最终的分类。通过上面的问题，我们就构建了一套买房的策略。

• 每个非叶节点表示一个特征属性测试。
• 每个分支代表这个特征属性在某个值域（分类）上的输出。
• 每个叶子节点存放一个类别。
• 每个节点包含的样本集合通过属性测试被划分到子节点中，根节点包含样本全集。

学习过程

决策树包含根节点、内部节点和叶节点，其根节点包含样本全集，内部节点对应特征属性测试，叶节点则代表决策结果。

由于决策树是基于特征对实例进行分类的，因而其学习的本质是从训练数据集中归纳出一组用于分类的 if-else 规则。在学习的过程中，这组规则集合既要在训练数据上降低经验误差，也要具备良好的泛化能力（降低泛化误差）。

决策树模型的学习过程包括三个步骤：特征选择、决策树生成、决策树剪枝。

特征选择与决策树生成

熵模型：信息与信息熵

特征选择决定了使用哪些特征来划分特征空间。训练集中，每个样本的属性可能有很多个，在分类结果中起到的作用也有大有小。因此特征选择作用在于筛选出与分类结果相关性较高，也就是分类能力较强的特征。理想的特征选择是在每次划分之后，分支节点所包含的样本都尽可能属于同一个类别。

在特征选择中通常使用的准则是信息增益。信息增益描述的是在已知特征后对数据分类不确定性的减少程度，因而特征的信息增益越大，得到的分类结果的不确定度越低，特征也就具有越强的分类能力。根据信息增益准则选择特征的过程，就是自顶向下进行划分，在每次划分时计算每个特征的信息增益并选取最大值的过程。信息增益的计算涉及信源熵和条件熵的公式。

如果事件 X 发生的概率是 p(X)，这个事件的自信息量的定义为

\mathrm{H}(X) = -log_2(p(X))

什么是信息，如何度量信息？

选择题有选项 A/B/C/D，结合我们朴素的生活观念，以下那句话带给我们的信息量最大？

1. 「D一定是错误答案。」
2. 「每个选项的概率是均等的。」
3. 「正确答案是 A 。」

可以知道越大概率的事情发生了产生的信息量越小。

参考 YJango 的视频

度量质量需要一个物体的质量作为单位，自然地，我们也想到用一件事（随机变量）的不确定性作为另一件事的单位。

比如一枚硬币的可能性是 2，也就是两种不确定性，每种情况发生的概率是 1/2。

为了可比性，3 枚硬币的不确定性应该是一枚硬币不确定性的三倍，而 3 枚硬币的不确定性是 8。为了方便我们比较，我们选择用对数运算。

log_2(2^3) = 3

所以 3 枚硬币的不确定性，若以一枚硬币的不确定性（当选择的参照物有两个等概率事件）作为单位，它的信息熵是 3 bit 。

那么选择题的 ABCD 选项在我们不知道任何提示的情况下（ ABCD 是四种等可能事件），信息熵是 2 bit （当选择的参照物有两个等概率事件）：

p_A = \frac{1}{4}\\
p_B = \frac{1}{4}\\
p_C = \frac{1}{4}\\
p_D = \frac{1}{4}\\
h = log_2(4) = 2 \mathrm{bit}\\

我们也可以说，用两个硬币可以猜出选择题答案。X 事件发生的信息熵：

\mathrm{H}(X) = log_2(\text{等概率事件个数}) = \text{相对于两个等概率事件的信息熵}

如果告诉你正确答案有 1/2 概率是 A，则概率分别为：

p_A = \frac{1}{2}\\
p_B = \frac{1}{6}\\
p_C = \frac{1}{6}\\
p_D = \frac{1}{6}\\

那么我们怎么计算信息熵，自然的我们可以用概率期望的方法

\mathrm{H}(X) = p_A(log_2(?)) + p_B(log_2(?)) + p_C(log_2(?)) + p_D(log_2(?))

那等概率事件数量怎么算？概率的倒数就是等概率事件的个数：

\begin{aligned}
\mathrm{H}(\text{正确答案有 1/2 概率是 A}) &=p_A(log_2(1/p_A)) + p_B(log_2(1/p_B)) + p_C(log_2(1/p_C)) + p_D(log_2(1/p_D)) \\
&= \frac{1}{2} \times 1 + \frac{1}{6} \times (2.58) + \frac{1}{6} \times (2.58)+ \frac{1}{6} \times (2.58) \\
&= 1.79
\end{aligned}

因此我们可以得到 X 事件发生的信息熵的公式：

\mathrm{H}(X) = \sum_i^np_ilog_2(1/p_i) = -\sum_i^np_ilog_2(p_i)

那么「正确答案是 A 」信息熵是？

\begin{aligned}
\mathrm{H}(\text{正确答案是 A}) &= -\sum_i^np_ilog_2(p_i) \\
&= -1 \times 0 + 0 + 0 +0 \\
&= 0
\end{aligned}

同时，我们知道由「正确答案在ABCD之中」到被告知「正确答案有 1/2 概率是 A」的信息量是：

2 - 1.79 = 0.21 \mathrm{bit}

那么「正确答案是 A 」的信息量是？

获取信息就是消除信息熵（不确定性）

信息量 = 信息熵（不确定性）减少量

https://zhuanlan.zhihu.com/p/26486223

条件熵

熵：表示随机变量的不确定性。

条件熵：在一个条件下，随机变量的不确定性。

信息增益：熵 – 条件熵。表示在一个条件下，信息不确定性减少的程度。

在概率论中有条件概率的概念，将条件概率扩展到信息论中，就可以得到条件熵。如果两个随机变量之间具有相关性，那么在已知其中一个随机变量 X 的情况下，另一个随机变量 Y 的信息熵就会减小。

条件熵 H(Y|X) 表示的是在已知随机变量 X 的条件下另一个随机变量 Y 的不确定性，也就是在给定 X 时，根据 Y 的条件概率计算出的熵再对 X 求解数学期望：

\begin{aligned}

H(Y \mid X) 
&=\sum_{i=1}^{n} p\left(x_{i}\right) H\left(Y \mid X=x_{i}\right) \\
&=-\sum_{i=1}^{n} p\left(x_{i}\right) \sum_{j=1}^{m} p\left(y_{j} \mid x_{i}\right) \log _{2} p\left(y_{j} \mid x_{i}\right) \\
&=-\sum_{i=1}^{n} \sum_{j=1}^{m} p\left(x_{i}, y_{j}\right) \log _{2} p\left(y_{j} \mid x_{i}\right)

\end{aligned}

相对于按照 X 的不同取值进行分类，比如我们把书籍按文科和理工科分成两个书架，尽管这两堆内部依然是随机的，我们还是能根据这个信息更好地判断书籍的分布位置，但这也简化了我们的问题，使得不确定性下降。

附近学校好，买的人有5个，不买的个数为6个；

附近学校不好，买的人有1个，不买的个数为8个；

条件熵为：

\begin{aligned}
&H(Y|X = \text{附近学校好}) = -\frac{5}{11}log_2(\frac{5}{11}) -\frac{6}{11}log_2(\frac{6}{11}) = 0.99 
\\
&H(Y|X=\text{附近学校不好}) =  -\frac{1}{9}log_2(\frac{1}{9}) -\frac{8}{9}log_2(\frac{8}{9}) = 0.5\\
\\
&P(X = \text{附近学校好}) =   \frac{11}{20}\\
&P(X =\text{附近学校不好}) = \frac{9}{20}
\\ \\
&H(Y|X) =   \frac{11}{20} \times  0.99  +  \frac{9}{20} \times 0.5 = 0.77
\end{aligned}

买的人有 6 个，不买的 14 个。于是我们知道信息熵为：

H(Y) = -\frac{6}{20}log_2(\frac{6}{20}) -\frac{14}{20}log_2(\frac{14}{20}) = 0.88

信息增益 = 信息熵 – 条件熵

H(D) = H(Y) - H(Y|X)

于是得出信息增益是：

H(D_1) = 0.88 - 0.77 = 0.11