决策树

决策树

August 12, 2021

388 views

1105 words

什么是信息的不确定性？

就是信息熵

在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量，设 X 是一个取有限个值的离散随机变量，其概率分布为：

$$P(X=x_{i}) = p_{i}, i = 1, 2, ..., n$$.

则随机变量 X 的熵定义为：

$$H(X) = - \sum_{i=1}^{n}p_{i}logp_{i}$$

熵越大，则随机变量的不确定性越大。其中 $0 \leq H(P) \leq logn$.

$$H(X) <= H_{max}(X) = - \sum_{i=1}^{n} \frac{1}{n}log \frac{1}{n} = - log \frac{1}{n} = logn$$

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

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

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

信息增益算法：

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

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

计算数据集 D 的经验熵 H(D):
$$H(D) = - \sum_{k=1}^{K} \frac{|C_{k}|}{|D|}log\frac{|C_{k}|}{|D|} = -\sum_{k=1}^{K}p_{k}logp_{k}$$
计算特征 A 对数据集 D 的经验条件熵 H(D|A)
$$H(D|A) = -\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}H(D_{i}) = - \sum_{i=1}^{n}\frac{|D_{i}|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_{i}|}log\frac{|D_{ik}|}{|D_{i}|} = - \sum_{i=1}^{n}w_{k}\sum_{k=1}^{K}p_{k}logp_{k}$$
计算信息增益
$$g(D, A) = H(D) - H(D|A)$$

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

定义： 特征 A 对训练数据集 D 的信息增益比 $g_{R}(D, A)$ 定义为其信息增益 $g(D, A)$ 与训练数据集 D 的经验熵 $H(D)$ 之比:

$$g_{R}(D, A) = \frac{g(D, A)}{H_{A}(D)}$$

决策树的核心思想：以树结构为基础，每个节点对某特征进行判断，进入分支，知道到达叶节点。
决策树构造的核心思想：让信息熵快速下降，从而达到最少的判断次数获得标签。
判断信息熵下降速度的方法：信息增益。
构建决策树算法：ID3（信息增益）、C4.5（信息增益比）。
信息增益会导致节点偏向选取取值较多的特征的问题。
c4.5为什么使用信息增益比来选择特征？ - 夕小瑶的回答 - 知乎 https://www.zhihu.com/question/22928442/answer/440836807

常用的决策树算法：

ID3 : 最大信息增益 $g(D, A) = H(D) - H(D|A)$

C4.5 : 最大信息增益比 $g_{R}(D,A) = H(D) - H(D|A)$

CART : 最大基尼系数 $Gini(D) = 1 - \sum_{k=1}^{K}P_{k}^2$

基尼系数(Gini index)

$$Gini(p) = \sum_{k=1}^{K}p_{k}(1-p_{k}) = 1 - \sum_{k=1}^{K}p_{k}^2$$

Gini(D) 反应了从数据集 D 中随机抽取两个样本，其标记类别不一致的概率。特别地，如果是二分类问题，则 Gini(p) = 2p(1-p)
集合 D 在特征 A 的条件下分为 $D_{1}$ 和 $D_{2}$ 两部分，则集合 D 的基尼指数 Gini(D, A) 表示经过 A = a 划分后集合 D 的不确定性。定义为：

$$Gini(D, A) = \frac{|D_{1}|}{|D|}Gini(D_{1}) + \frac{|D_{2}|}{|D|}Gini(D_{2})$$