2020机器学习决策树(2)

作者: zidea | 来源:发表于2020-03-16 19:50 被阅读0次

2020机器学习决策树(2)
[机器学习]决策树
6.machine_learning_Decision_Tree
机器学习 | 决策树及若干基础问题
ID3、C4.5、CART决策树生成算法总结
机器学习之决策树（Decision Tree）及其Python
机器学习笔记（6）：决策树
python决策树（二叉树、树）的可视化
决策树算法
2020机器学习决策树(3)

machine_learning.jpg

上一次分享给出决策树划分几种算法，如下。

信息增益
$Gain(D,C) = Ent(D) - Ent(D|C) = Ent(D) - \sum_{i=1}^n \frac{N(D_i)}{N} Ent(D_i)$
信息增益率
$Gain(D,C) = Ent(D) - Ent(D|C) = Ent(D) - \sum_{i=1}^n \frac{N(D_i)}{N} Ent(D_i)$

但是为什么这样按特征对数据划分就可以达到分类或回归的效果呢? 今天我们就尝试来回答这个问题。
我们对数据了解程度决定了我们是否可以对数据进行分类和预测。数据对于我们是一些信息，在决策树我们是通过一些列方法让我们更了解这些数据，也就是数据提供给我们更多信息。

所以我们通过对数据某个特征对数据进行划分来不断了解数据，我们同过了解数据特征，更加了解数据。我们可以根据特征对数据进行划分，降低我们对数据不确定性。数据的不确定性是通过信息熵可以衡量。降低数据信息熵就等同于降低数据不确定性。那么我们将要尽快了解数据，就要找到可以让信息熵下降最快的特征作为我们划分数据的依据。

今天我们会首先介绍信息熵，接下来介绍在给定条件(就是已知什么条件下）数据下的条件熵。衡量连个对同一个数据不同概率分布之间的距离(差异性)的交叉熵。这些都是为证明互信息的公式。互信息就是信息增益，也就是我们今天主要分享的内容。

entropy_venn.png

图中很直观表示了互信息 $I(X,Y)$ 和条件熵 $H(X|Y$ 以及联合熵 $H(X,Y)$ 他们之间关系。

信息熵

熵概念最早是在物理热力学中提出概念后来也被在统计学中使用，表示提出了信息熵的概念，用以度量信息的不确定性。以及信息熵关系。我们先说介绍一下事件，什么是事件呢?例如太阳从东方升起就是一个事件、老板告诉你升职了也是一个事件。这些事件发生都是有一定概率的，例如太阳升起的概率是 100%，而老板告诉你升职却是一个小概率事件。然后这些事件也是带有一定信息量，如果你告诉朋友太阳会从东方升起，朋友会感觉你无聊，没话找话。因为这个这个事件对于他的信息量几乎为 0。

然后用概率表示事件发生可能性，我们用熵来衡量信息量大小。通过上面例子我们已经了解到信息熵越大则概率越小，概率为 1 时信息熵为 0。好现在我们先给出熵计算公式，然后再给出合理解释为什么熵公式长成这个样子
$H(p) = -\sum_{i=1}^N p_i \log p_i$
计算均匀分布信息熵
$p_i = \frac{1}{N} \, i \in \{1,2,\dots,N\}$
$H(p) = - \sum_{i=1}^N \frac{1}{N} \log \frac{1}{N} = \log \frac{1}{N}$

条件熵

之前已经学习过条件概率， $P(Y|X)$ 就是在 X 事件发生前提下，发生 Y 事件的概率。那么什么是条件熵呢?这里用 $H(Y|X)$ 来表示在 X 发生前提下，Y 的信息熵的值，
$\begin{aligned} H(Y|X) = H(Y,X) - H(X) \\ =- \sum_{x,y}p(x,y)\log p(x,y) - \left(- \sum_{x}p(x) \log p(x)\right) \\ =- \sum_{x,y}p(x,y)\log p(x,y) + \sum_{x}p(x) \log p(x) \\ = - \sum_{x,y}p(x,y)\log p(x,y) + \sum_x \left( \sum_y p(x,y) \log p(x) \right) \\ = - \sum_{x,y}p(x,y)\log p(x,y) - \left( - \sum_{x,y} p(x,y) \log p(x) \right)\\ = - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)}\\ = - \sum_{x,y} p(x,y) \log p(y|x) \end{aligned} \tag{1}$
通过推导我们得出 $H(Y|X) = -\sum_{x,y} p(x,y) \log p(y|x)$ ,这里我们可能会感觉有点不舒服就是，如果根据信息熵定义应该是 $H(Y|X) = - \sum_{x,y} p(y|x) \log p(y|x)$

相对熵

相对熵，又称互熵、交叉熵，鉴别信息，Kullback 熵或则 Kullback_Leible 散度。我们假设有 $p(x)$ 和 $q(x)$ 分别是 X 中取值的两个概率分布，则 p 相对于 q 的相对熵为

$D(p||q) = \sum_x p(x) \log \frac{p(x)}{q(x)} = E_{p(x)} \log \frac{p(x)}{q(x)}$

在 p 概率分布上求 $\log \frac{p(x)}{q(x)}$ 的期望。那么相对熵也就是可以衡量两个概率分布 $p(x)$ 和 $q(x)$ 之间的距离。我们知道KL散度可以用于进行分类问题。

互信息

上面介绍相对熵就是为了介绍互信息，两个随机变量 X,Y 的互信息，定义为 X,Y 的联合分布和独立分布乘积的相对熵。
$I(X,Y) = D(P(X,Y) || P(X)P(Y))$
$I(X,Y) = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x),p(y)}$
如果两个随机变量 $p(x)$ 和 $p(y)$ 是相互独立那么，就是 $\frac{p(x,y)}{p(x),p(y)} = 1$ 也就是 $I(X,Y) = 0$ 如果两个随机变量的互信息为 0 就是说明两个随机变量是相互独立，反之就是大于 0。

有了互信息我们想证明一件事
$\begin{aligned} H(Y) - I(X,Y) = - \sum_y p(y) \log p(y) - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} \\ = -\sum_y \left( \sum_x p(x,y) \right)\log p(y) - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} \\ - \sum_{x,y} p(x,y) \log p(y) - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)}\\ - \sum_{x,y} p(x,y) \log \frac{p(y)p(x,y)}{p(x)p(y)}\\ - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)} \\ H(Y|X) \end{aligned} \tag{2}$

$H(Y) - I(X,Y) = H(Y|X) \tag{3}$

$H(Y) - I(X,Y) = H(Y|X)$

之前介绍条件熵、还是相交熵或是互信息都是为了证明下面结论做准备，根据条件熵有了下面结论 $(1)$
$H(Y|X) = H(X,Y) - H(X)$
通过上面证明
$H(Y|X) = H(Y) - I(X,Y)$

我们对上上面式子交互 X 和 Y 来得到对偶式
$\begin{aligned} H(X|Y) = H(X,Y) - H(Y)\\ H(X|Y) = H(X) - I(X,Y) \end{aligned}$

$\begin{aligned} I(X,Y) = H(X) - H(X|Y) \\ H(X|Y) = H(X,Y) - H(Y)\\ \end{aligned}$

$I(X,Y) = H(X) + H(Y) - H(X,Y)$

$\begin{aligned} I(X,Y) = H(X) - (H(X,Y) - H(Y)) \\ I(X,Y) = H(X) - H(X|Y)\\ \end{aligned}$

因为 $I(X,Y)$ 所以 $H(X) \ge H(X|Y)$

$I(X,Y) = H(X) + H(Y) - H(X,Y)$

最后希望大家关注我们微信公众号

wechat.jpeg

2020机器学习决策树(2)
上一次分享给出决策树划分几种算法，如下。信息增益信息增益率但是为什么这样按特征对数据划分就可以达到分类或回归...
[机器学习]决策树
决策树 @(技术博客)[机器学习, 决策树, python] 学习决策树首先要搞清楚决策树是什么（what），在弄...
6.machine_learning_Decision_Tree
1 机器学习决策树 1.1机器学习中的决策树模型 ① 树模型不用做scaling ② 树模型不太需要做离散化 ③ ...
机器学习 | 决策树及若干基础问题
决策树 1.构造决策树学习决策树就是学习一系列if/else问题，是我们能够以最快的速度得到正确答案。在机器学习...
ID3、C4.5、CART决策树生成算法总结
简介决策树模型是最常见的机器学习方法之一，也是入门机器学习必须掌握的知识。决策树模型呈现树形结构，在分类问题中，...
机器学习之决策树（Decision Tree）及其Python
机器学习之决策树（Decision Tree）及其Python代码实现
机器学习笔记（6）：决策树
本文来自之前在Udacity上自学机器学习的系列笔记。这是第6篇，介绍了监督学习中的决策树模型。决策树决策树是...
python决策树（二叉树、树）的可视化
问题描述在我学习机器学习实战-决策树部分，欲可视化决策树结构。最终可视化结果：解决方案决策树由嵌套字典组成，...
决策树算法
决策树决策树也是经常使用的数据挖掘算法，其不用了解机器学习的知识，就能搞明白决策树是如何工作的。决策树算法能够...
2020机器学习决策树(3)
CART 表示均值 j 选择 x 某一个的维度 L 是距离函数 s 表示选取的分割位置我们在变量 x 的 j...