层层递进,决策树模型

结构

  • 决策树原理

    • 决策理论
    • 学习过程
  • 特征选择与决策树生成

    • 熵模型:信息与信息熵
    • 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 的不同取值进行分类,比如我们把书籍按文科和理工科分成两个书架,尽管这两堆内部依然是随机的,我们还是能根据这个信息更好地判断书籍的分布位置,但这也简化了我们的问题,使得不确定性下降。

附近学校 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
订阅评论
提醒
guest
1 评论
最久
最新 最赞
内联反馈
查看所有评论
trackback

[…] ML6. 层层递进,决策树模型 | 知乎 | bilibili […]