结构
-
决策树原理
- 决策理论
- 学习过程
-
特征选择与决策树生成
- 熵模型：信息与信息熵
- 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，结合我们朴素的生活观念，以下那句话带给我们的信息量最大？
- 「D一定是错误答案。」
- 「每个选项的概率是均等的。」
- 「正确答案是 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 的不同取值进行分类，比如我们把书籍按文科和理工科分成两个书架，尽管这两堆内部依然是随机的，我们还是能根据这个信息更好地判断书籍的分布位置，但这也简化了我们的问题，使得不确定性下降。
| 买 | 附近学校 x1 | 价格 x2 | 面积 x3 |
|---|---|---|---|
| 买 | 好 | 超过预算 | 适合 |
| 不买 | 不好 | 符合预算 | 太小 |
| …… | …… | …… | …… |
附近学校好，买的人有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
