前言

参考：

《统计学习》—李航（蓝皮）
部分来自网络的内容（主要是liaohuiqiang的博客

决策树

模型

决策树可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。

从根节点出发
每个“内部结点”一个数据特征
每个分支结点对应于该特征“测试”的一种可能结果（及该属性的某个取值）
每个“叶结点”对应于一个“预测结果”

决策树的核心思想是分而治之
决策树学习通常包括3个步骤：特征选择，决策树生成，剪枝

if-then规则

决策树路径或其对应的if-then规则集合具有一个重要的性质，互斥并且完备，也就是说，每一个实例都被一条路径或一条规则所覆盖，而且仅被一条路径或者一条规则覆盖。

空间划分与概率分布

决策树将特征空间划分为互不相交的单元，并在每个单元定义一个类的概率分布。决策树的一条路径对应于划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成，即 $P(Y|X)$ ，叶结点（单元）上的条件概率往往偏向某一类。
决策的过程.jpg

决策学习与预测过程

学习：决策树学习本质上是从训练数据集中归纳出一组分类规则，找到一棵“与训练数据矛盾较小，同时具有很好的泛化能力”的树。
停止条件为
1. 当前结点包含的样本完全属于同一类别，此时直接将该节点标记为叶结点，并设为相应类别（最好情况）
2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分，这是将该结点标记为叶结点，并将其设为该节点所含样本最多的类别
3. 当前结点包含的样本集合为空，不能划分，这时应将该结点标记为叶结点，并将其类别设为父节点中所含样本最多的类别
  
  树中具体存储的信息将在下方提到
预测：将测试示例从根节点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶节点

特征选择

特征选择在于选取对训练数据具有分类能力的特征。（当然最好是特征较为明显的），如果利用一个特征进行分类的结果与随机分类的结果没有很大区别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的影响不大。

通常，特征选择的准则是信息增益或信息增益比。

熵

熵度量的是随机变量的不确定性。熵越大，不确定性越大，遵循热力学第二定律
在信息论中

信息熵是指到底是哪种情况不确定（宏观）
概率是指某个事情的某个可能情况的确定性（微观）
信息是指一个观察者确定一个宏观态是哪个微观态时需要的物理量；信息是相对的，是相对于观察者已经对该事件的了解程度而言的
数据是信息+噪音

信息量为
::: align-center
$H(x_i)=\log\frac{1}{p_i}=-\log p_i$

:::
而熵表示为
::: align-center
$H(X)=\sum_{i=1}^np_iH(x_i)=-\sum_{i=1}^np_i\log p_i$

:::
规定 $p_i=0$ 时 $H(X)=0$
通常对数以2或e为底，则熵的单位为比特（bit）或纳特（nat）。

e.g.从ABCD四个选项中获得C是正确的，则获得的信息量为 $\log_2 4=2\space bit$ ，此时熵为 $\sum_{i=1}^4\frac{1}{4}\times 2=2$ （事实上，在事件为等概率分布时，熵就等于单个事件的信息量，因为概率和求和部分相互抵消了）

熵只依赖于X的分布，而与X的取值无关，所以 $H(x)$ 也记作 $H(p)$
例如在二项分布下，熵与概率分布的关系为
熵与二项分布之间的关系.jpg

当 $p=0,1$ 时， $H(p)=0$ ，随机变量完全没有不确定性
当 $p=0.5$ 时， $H(p)=0.5+0.5=1$ ，随机变量的不确定性最大

条件熵

条件熵 $H(Y|X)$ 表示在已知随机变量X的条件下随机变量Y的不确定性。
::: align-center
$H(Y|X)=\sum_{i=1}^n p_iH(Y|X=x_i)$

:::

经验熵与经验条件熵

当概率由数据估计（特别是极大似然估计，见上篇朴素贝叶斯文章）时，所对应的熵与条件熵分别称为经验熵与经验条件熵。

信息增益与信息增益比（重要）

信息增益

信息增益表示得知特征A的信息而使类D的信息的不确定性减少的程度。信息增益大的特征分类能力强。

设 $|C_k|$ 为表示类别的集合 $C_k$ 的基数（元素个数），同样的，设 $|D|$ 为样本容量，
另设特征A有n个不同的取值 $\{a_1,a_2,\cdots,a_n\}$ ，根据此取值将A划分为n个互不相交子集 $D_1,D_2,\cdots,D_n$ ， $|D_i|$ 为子集的个数， $D_{ik}=D_i\cap C_k$ ，

则
::: align-center
$g(D,A)=H(D)-H(D|A)$

:::
其中
::: align-center
$H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|}$

:::
且
::: align-center
$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_2\frac{|D_{ik}|}{|D_i|}$

:::

信息增益比

以信息增益划分，存在“偏向于选择取值较多的特征”的问题，用信息增益比可以校正这一问题。
::: align-center
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$

:::
其中 $H_A(D)$ 为训练集D关于特征A的值的熵
::: align-center
$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}$

:::

e.g.
决策树信息增益实战.jpg
此时 $g(D,A_3)$ 最大，选择它作为特征，有房子的最终的类别全部为是，故此分支结点可设为叶结点，而没有房子的类别有是有否，需要以这些剩下的样本为新的训练集进一步递归

决策树生成

ID3和C4.5

决策树生成的经典算法有ID3和C4.5。
ID3：ID3的核心是在各个结点上应用“信息增益”准则选择特征。

从根结点出发，选择信息增益最大的特征作为结点特征，由该特征的不同取值建立子结点，对子结点递归调用以上方法。直到所有特征的信息增益均很小（设一个阈值 $\epsilon$ ）或没有特征可选为止。

C4.5：对ID3算法进行了改进，生成过程中用信息增益比来选择特征。

决策树的剪枝

剪枝

学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树（过拟合）。解决办法是考虑决策树的复杂度，对已生成的树进行简化，这一过程称为剪枝（Pruning）。

具体地，从树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。

决策树的剪枝往往通过极小化决策树整体的损失函数来实现。

决策树的损失函数

设树的叶结点个数为 $|T|$ ， $t$ 是树 $T$ 的叶结点，该叶结点有 $N_t$ 个样本，其中属于 $k$ 类的样本有 $N_{tk}$ 个, $H_t(T)$ 为叶结点的经验熵，则损失函数为
::: align-center
$C_\alpha(T)=C(T)+\alpha|T|$

:::
易知 $\alpha|T|$ 是正则化项， $\alpha\ge 0$ 为参数，较大的 $\alpha$ 促使较简单模型的选择，较小的 $\alpha$ 促使较复杂模型的选择

$C(T)$ 为模型的训练误差，为
::: align-center
$C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=\sum_{t=1}^{|T|}N_t[-\sum_{k=1}^K\frac{N_{tk}}{N_t}\log\frac{N_{tk}}{N_t}]$

:::
化简后为
::: align-center
$C(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}\log\frac{N_{tk}}{N_t}$

:::

具体剪枝方法为：

计算每个节点的经验熵
递归从叶结点向上回缩
设树回缩前回缩后的树分别为 $T_B$ 和 $T_A$ ，若 $C_{\alpha}(T_A)\le C_{\alpha}(T_B)$ ，则执行剪枝，将双亲结点作为新的叶结点
返回2.，直到不能继续，最后得到整体损失函数最小的决策树

CART算法

注：此部分暂未整理完全，更为详细的内容请参考蓝皮书

简介

CART（Classification And Regression Tree，分类与回归树）是应用广泛的决策树学习方法，既可用于分类，也可用于回归。

CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。CART算法分为两步：

决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。
决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

回归任务

模型

假设已将输入空间划分为 $M$ 个单元 $R_1,R_2,\cdots,R_M$ ，并且在每个单元 $R_m$ 有一个固定的输出值 $c_m$ ，于是回归树模型可表示为：
::: align-center
$f(x)=\sum_{m=1}^M c_mI(x\in R_m)$

:::

策略

可以用平方误差 $\sum_{x_i\in R_m}(y_i-f(x_i))^2$ 来表示训练误差，用最小化平方误差来求解，而单元 $R_m$ 上的 $c_m$ 最优值 $\hat{c_m}$ 是 $R_m$ 上所有输入实例 $x_i$ 对应的输出 $y_i$ 的均值，即
::: align-center
$\hat{c_m}=ave(y_i|x_i\in R_m)$

:::

通过不同的划分得到不同的 $\hat{c_m}$
得到二叉树
衡量平方误差，筛选出最小的作为子树
递归，直到达到某个设定阈值停止

算法

采用启发式方法
选择 $j$ 个变量 $x^{(j)}$ 和它的取值 $s$ ，作为切分变量和切分点,并定义两个区域 $R_1,R_2$
::: align-center
$R_1(j,s)=\{x|x^{(j)}\le s\},R_2(j,s)=\{x|x^{(j)}>s\}$

:::
然后求解最优求 $(j,s)$ ，即求解
::: align-center
$\min_{j,s}[\min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$

:::
其中在单个单元上的 $c_m$ 最优解为 $\hat{c_m}$ ，我们通过计算上式得到全局上最优的 $(j,s)$

之后在 $R_1,R_2$ 上递归，直到满足停止条件，这样得到的回归树通常称最小二乘回归树

分类任务

CART算法的分类树使用基尼系数来确定最优特征
在分类问题中，假设有 $K$ 个类，属于 $k$ 类的概率为 $p_k$ ，则概率分布的基尼指数定义为
::: align-center
$Gini(p)=\sum_{k=1}^K p_k(1-p_k)=1-\sum_{k=1}^K p_k^2$

:::
特别地，对于二分类任务 $Gini(p)=2p(1-p)$
对于给定的样本集合 $D$ ，基尼指数为
::: align-center
$Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2$

:::
如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分，则在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为
::: align-center
$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$

:::
Gini值越大，样本集合的不确定性也越大（与熵类似），因此每次选择Gini小的特征来划分。

注：基尼指数只涉及平方计算，相较于设计对数计算的信息增益/信息增益比来说，它在大规模数据上的计算效率更高，但与此同时牺牲了一部分的平衡性。

在之后按照分类算法创建叶结点，其余内容与上面类似

简单练习（回归任务）

决策树练习.jpg
这里我们只计算第一步

解：
可知要确定变量 $x^{(j)}$ （这里只有一个 $x$ ，就无需再通过计算信息增益/信息增益比/基尼指数确定）和它的取值 $s$ ，作为切分变量和切分点,并定义两个区域 $R_1,R_2$
::: align-center
$R_1(j,s)=\{x|x^{(j)}\le s\},R_2(j,s)=\{x|x^{(j)}>s\}$