决策树

• 学习流程

  • 关键在于每次划分到叶节点时，可能子集中仍包含多个类别的样本，此时选择最多样本的类别作为叶节点标记

  

划分选择

如何选择最优划分属性，使决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”（Purity）越来越高

信息增益

Information Gain

• 信息熵（Information Entropy）

  度量样本集合纯度

  $$\mathrm{Ent}(D)=-\sum _{k=1}^{|\mathcal{Y}|}{p}_k{\log }_2{p}_k$$
  其中，$p_k$表示当前样本集合$D$中第$k$类样本所占的比例。$Ent(D)$的值越小，则$D$的纯度越高（$Ent(D)$最小值为0，最大值为$lo{g}_2|\mathcal{Y}|$）

• 信息增益（Information Gain）

  属性$a$对样本集$D$进行划分所获得的信息增益

  $$\mathrm{Gain}(D,a)=\mathrm{Ent}(D)-\sum _{v=1}^V\frac{\left|D^v\right|}{|D|}\mathrm{Ent}\left(D^v\right)$$
  $V$表示属性$a$划分产生的分支节点数

  • 一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此可以根据信息增益来选择划分属性：

    $$a_{\ast }=\underset{a\in A}{\mathrm{argmax}}\mathrm{Gain}(D,a)$$

  • ID3决策树算法就是以信息增益为准则来选择划分属性

增益率（Gain Ratio）

C4.5决策树使用增益率选择划分属性

$${\mathrm{Gain}}_{\mathrm{ratio}}(D,a)=\frac{\mathrm{Gain}(D,a)}{\mathrm{IV}(a)}$$

$$\mathrm{IV}(a)=-\sum _{v=1}^V\frac{\left|D^v\right|}{|D|}{\log }_2\frac{\left|D^v\right|}{|D|}$$
$IV(a)$称为属性$a$的固有值（Intrinsic Value），属性$a$的可能取值数目越多，则$IV(a)$的值通常会越大

• 信息增益准则对可取值数目较多的属性有所偏好，但增益率准则却对可取值数目较少的属性有所偏好。因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是先从划分候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

基尼指数（Gini Index）

CART（Classification and Regression Tree）决策树使用基尼指数来选择划分属性

• 数据集D的纯度可用基尼值来度量

  • 基尼值反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此$Gini(D)$越小，则数据集D的纯度越高

  $$\begin{array}{rl}\mathrm{Gini}(D)& =\sum _{k=1}^{|\mathcal{Y}|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}\\ & =1-\sum _{k=1}^{|\mathcal{Y}|}{p}_k^2\end{array}$$

  • 基尼指数定义

  $$\text{Gini\_index}(D,a)=\sum _{v=1}^V\frac{\left|D^v\right|}{|D|}\mathrm{Gini}\left(D^v\right)$$

  • 选择基尼指数最小的作为划分属性

  $$a_{\ast }=\underset{a\in A}{\mathrm{argmin}}\mathrm{Gini}\_\mathrm{index}(D,a)$$

剪枝处理（Pruning）

缓解过拟合

泛化性能在验证集上评估

• 预剪枝（Prepruning）

  在决策树生成过程中，在节点划分前先进行估计，若当前节点划分不能带来泛化性能提升，则停止划分并将当前节点标记为叶节点

  • 虽然在一定程度上降低了过拟合的风险，显著减少决策树的训练时间开销和测试时间开销，但也可能会导致泛化性能下降，带来欠拟合的风险

• 后剪枝（Postpruning）

  先生成一棵完整的决策树，自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点能提升泛化性能，则将该子树替换为叶节点

  • 后剪枝一般比预剪枝保留更多的分支，一般情况下后剪枝欠拟合的风险较小，泛化性能往往优于预剪枝决策树。但后剪枝是在完全生成决策树后进行的，并且要自底向上遍历非叶节点，因此训练时间开销比未剪枝和预剪枝决策树都要大得多

连续与缺失值

• 连续值处理

  二分法（C4.5采用的策略）

  • 假设某属性a在样本集D中有n个取值，将它们从小到大排列，以如下公式考虑划分点的选择

    $$T_a=\left\{\frac{a^i+a^{i+1}}{2}\mid 1⩽i⩽n-1\right\}$$
    即把属性a紧邻的两个取值的中位点当作划分点

  • 与离散值不同的是，我们需要依次考虑每个划分点，依次计算在每个划分点之下的各种系数，如信息增益、基尼指数等，而后取最大值（因为连续值考虑的是二叉分支，而离散值直接考虑了多叉分支，所以对于连续值不能一次性考虑所有划分点，需要针对每一个划分点依次考虑）

    Gain⁡(D,a)=max⁡t∈TaGain⁡(D,a,t)=max⁡t∈TaEnt⁡(D)−∑λ∈{−,+}∣Dtλ∣∣D∣Ent⁡(Dtλ) \begin{aligned} \operatorname{Gain}(D, a) &=\max _{t \in T_{a}} \operatorname{Gain}(D, a, t) \\ &=\max _{t \in T_{a}} \operatorname{Ent}(D)-\sum_{\lambda \in\{-,+\}} \frac{\left|D_{t}^{\lambda}\right|}{|D|} \operatorname{Ent}\left(D_{t}^{\lambda}\right) \end{aligned} Gain(D,a)​=t∈Ta​max​Gain(D,a,t)=t∈Ta​max​Ent(D)−λ∈{−,+}∑​∣D∣​Dtλ​​​Ent(Dtλ​)​

  • 与离散属性不同，连续属性还可作为后代结点的划分属性（只不过该属性的划分点不能再用了而已）

• 缺失值处理

  总体思想是利用完整无缺失值的样本的分布来预测整体带有缺失值的数据集的分布

  C4.5采取了这种解决方案

  • $D$：训练集；$\tilde{D}$：$D$在属性$a$中没有缺失值的样本；${\tilde{D}}^v$：$\tilde{D}$中在属性$a$上取值为$a^v$的样本子集；${\tilde{D}}_k$：表示$\tilde{D}$中属于第$k$类的样本子集；假定为每个样本赋予一个初始权重$w_x$

    $$\begin{array}{rl}\rho & =\frac{{\sum }_{\mathbf{x}\in \tilde{D}}{w}_{\mathbf{x}}}{{\sum }_{\mathbf{x}\in D}{w}_{\mathbf{x}}}\\ {\tilde{p}}_k& =\frac{{\sum }_{\mathbf{x}\in {\tilde{D}}_k}{w}_{\mathbf{x}}}{{\sum }_{\mathbf{x}\in \tilde{D}}{w}_{\mathbf{x}}}(1⩽k⩽|\mathcal{Y}|),\\ {\tilde{r}}_v& =\frac{{\sum }_{\mathbf{x}\in {\tilde{D}}^v}{w}_{\mathbf{x}}}{{\sum }_{\mathbf{x}\in \bar{D}}{w}_{\mathbf{x}}}(1⩽v⩽V)\end{array}$$
    对于属性$a$，$\rho$表示无缺失值样本所占的比例，${\tilde{p}}_k$表示无缺失值样本中第$k$类所占的比例，${\tilde{r}}_v$表示无缺失值样本中在属性$a$上取值$a^v$的样本所占的比例

  • 基于上述定义，推广信息增益：

    $$\begin{array}{rl}\mathrm{Gain}(D,a)& =\rho \times \mathrm{Gain}(\tilde{D},a)\\ & =\rho \times \left(\mathrm{Ent}(\tilde{D})-\sum _{v=1}^V{\tilde{r}}_v\mathrm{Ent}\left({\tilde{D}}^v\right)\right)\end{array}$$

    $$\mathrm{Ent}(\tilde{D})=-\sum _{k=1}^{|\mathcal{Y}|}{\tilde{p}}_k{\log }_2{\tilde{p}}_k$$

  • 若样本$x$在划分属性$a$上的取值已知，则将$x$划入与其取值对应的子节点，且权值保持为$w_x$；若未知，则将其同时划入所有子节点，且权值分别调整为${\tilde{r}}_v\cdot w_x$

多变量决策树

Multivariate Decision Tree

• 将每个属性$a$视为坐标空间的一个坐标轴，$n$个属性就可描述成$n$维空间中的一个点，而非叶节点可描述成坐标空间中的分类边界，单变量决策树（Univariate Decision Tree）的决策边界与坐标轴平行

  

• 多变量决策树非叶节点不再仅针对某个属性，而是各种属性的线性组合