[人工智能]DataWhale-202110 树模型与集成学习（第一次）

信息论的基础

正如文档里面所说的一样，树具有一定的天然分支结构，在机器学习中有分类与回归两大问题，而分类问题中，树的分支结构起到一定的关键作用，首先引入的是节点纯度的概念

节点纯度

节点纯度反映的是节点样本标签的不确定性，当一个节点纯度较低的时候，说明分类的不确定性较高，而节点纯度较高的时候，代表着我们能够把握这个节点的具体信息，确定性较高

不确定性函数$H(P)$

$$H(p_1,...,p_n)=?C\sum _{i=1}^n{p}_i\log p_i$$
其中满足信息熵条件是：

1. $H$关于$p_i$是连续函数。
2. 若$p_1=...=p_n$，则$H$关于$n$单调递增。
3. 若将某一个$p_i$拆分为$p_{i1}$和$p_{i2}$，即$p_{i1}+p_{i2}=p_i$，则
   $$H(p_1,...,p_{i?1},p_{i+1},...,p_n,p_{i1},p_{i2})=H(p_1,...,p_n)+p_{i}H(\frac{p_{i1}}{p_i},\frac{p_{i2}}{p_i})$$

对于定义在有限状态集合 { y 1 , . . . , y K } \{y_1,...,y_K\} {y1?,...,yK?}上的离散变量而言，对应信息熵的最大值在离散均匀分布时取到，最小值在单点分布时取到。此时，离散信息熵为
$$H(Y)=?\sum _{k=1}^{K}p(y_k){\log }_{2}p(y_k)$$

决策树分裂

在决策树的分裂过程中，我们不但需要考察本节点的不确定性或纯度，而且还要考察子节点的平均不确定性或平均纯度来决定是否进行分裂。自然定义出条件熵$H(Y|X)$为
$${\mathbb{E}}_X[{\mathbb{E}}_{Y|X}[?{\log }_{2}p(Y|X)]]$$
设随机变量$X$所有可能的取值为 { x 1 , . . . , x M } \{x_1,...,x_M\} {x1?,...,xM?}，上式可展开为
$$?\sum _{m=1}^{M}p(x_m)\sum _{k=1}^{K}p(y_k|X=x_m){\log }_{2}p(y_k|X=x_m)$$

信息增益

有了信息熵与条件熵的基础，我们便可以定义出信息增益这一个概念，即通俗理解为节点分裂后带来了多少的不确定性的降低或纯度的提高，即公式如下所示，
$$G(Y,X)=H(Y)?H(Y|X)$$

分类树的节点分裂

对于每个节点进行分裂决策时，我们会抽出max_features个特征进行遍历以比较信息增益的大小。特征的类别可以分为三种情况讨论：类别特征、数值特征和含缺失值的特征。

• 类别特征
• 数值特征
• 含缺失值特征

深度优先增长于最佳增益增长

深度优先生长采用深度优先搜索的方法：若当前节点存在未搜索过的子节点，则当前节点跳转到子节点进行分裂决策；若当前节点为叶节点，则调转到上一层节点，直到根节点不存在未搜索过的子节点为止。对上图而言，当前节点为2号，它的两个子节点4号和5号都没有被搜索过，因此下一步则选择两个节点中的一个进行跳转。当决策树使用最佳增益生长时，每次总是选择会带来最大相对信息增益的节点进行分裂，直到叶节点的最大数量达到max_left_nodes。

CART树

CART（Classification And Regression Tree）是一棵二叉树，它既能处理分类问题，又能够处理回归问题。，对于回归问题来说，每一个叶节点输出的是样本标签的均值，而在每次回归树分裂过程中，我们希望不同的子节点之间差异变大，而每个子节点内部的差异较小，因此我们将熵与条件熵使用新的概念进行替换

均方误差（熵）平均绝对误差（条件熵）

设节点$N$的样本标签为$y_1^{(D)},...,y_N^{(D)}$，左右子节点的样本个数分别为$y_1^{(L)},...,y_{N_R}^{(L)}$和$y_1^{(R)},...,y_{N_R}^{(R)}$，记${\bar{y}}^{(D)}=\frac{1}{N}{\sum }_{i=1}^N{y}_i^{(D)}$、${\bar{y}}^{(L)}=\frac{1}{N_L}{\sum }_{i=1}^{N_L}{y}_i^{(L)}$和${\bar{y}}^{(R)}=\frac{1}{N_R}{\sum }_{i=1}^{N_R}{y}_i^{(R)}$分别为节点$N$的样本标签均值、左子节点的样本标签均值和右子节点的样本标签均值，再记${\tilde{y}}^{(D)}$、${\tilde{y}}^{(L)}$和${\tilde{y}}^{(R)}$分别为节点$N$的样本标签中位数、左子节点的样本标签中位数和右子节点的样本标签中位数。
$$G^{MSE}(Y,X)=\frac{1}{N}\sum _{i=1}^N(y_i^{(D)}?{\bar{y}}^{(D)}{)}^2?\frac{N_L}{N}\frac{1}{N_L}\sum _{i=1}^{N_L}(y_i^{(L)}?{\bar{y}}^{(L)}{)}^2?\frac{N_R}{N}\frac{1}{N_R}\sum _{i=1}^{N_R}(y_i^{(R)}?{\bar{y}}^{(R)}{)}^2$$
$$G^{MAE}(Y,X)=\frac{1}{N}\sum _{i=1}^N|y_i^{(D)}?{\tilde{y}}^{(D)}|?\frac{N_L}{N}\frac{1}{N_L}\sum _{i=1}^{N_L}|y_i^{(L)}?{\tilde{y}}^{(L)}|?\frac{N_R}{N}\sum _{i=1}^{N_R}\frac{1}{N_R}|y_i^{(R)}?{\tilde{y}}^{(R)}|$$
而CART树中将熵采用一阶泰勒展开，用熵的线性近似定义基尼系数(Gini)
$$\begin{array}{rl}\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(Y)& ={\mathbb{E}}_Y[1?p(Y)]\\ & =\sum _{k=1}^K\tilde{p}(y_k)(1?\tilde{p}(y_k))\\ & =1?\sum _{k=1}^K{\tilde{p}}^2(y_k)\end{array}$$
条件基尼系数
$$\begin{array}{rl}\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(Y|X)& ={\mathbb{E}}_X[{\mathbb{E}}_{Y|X}1?p(Y|X)]\\ & =\sum _{m=1}^M\tilde{p}(x_m)\sum _{k=1}^K[\tilde{p}(y_k|x_m)(1?\tilde{p}(y_k|x_m))]\\ & =\sum _{m=1}^M\tilde{p}(x_m)[1?\sum _{k=1}^K{\tilde{p}}^2(y_k|x_m)]\end{array}$$
自然而然的定义一个关于基尼系数的信息增益为
$$G(Y,X)=\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(Y)?\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(Y|X)$$

决策树剪枝

在sklearn的CART实现中，一共有6个控制预剪枝策略的参数，它们分别是最大树深度max_depth、节点分裂的最小样本数min_samples_split、叶节点最小样本数min_samples_leaf、节点样本权重和与所有样本权重和之比的最小比例min_weight_fraction_leaf、最大叶节点总数max_leaf_nodes以及之前提到的分裂阈值min_impurity_decrease。

知识回顾

第一题

ID3算法，最佳特征根据“最大信息熵增益”来选取，本质上是一种贪心算法，每次进行分叉选取的特征，C4.5算法，在ID3算法下容易过拟合，所以引入C4.5算法，能够作为分裂信息的惩罚项惩罚特征，CART算法在进行分类任务时，采用基尼系数选择最好的特征，当是回归任务，最小方差的分类依据

第二题

信息增益衡量的是节点分裂后，带来了多少的不确定性的降低或纯度的提高，衡量了不确定的增长幅度

第三题

随机的参数，能够限制了训练集和验证集的数据

第四题

处理连续值（转发）

C4.5既可以处理离散型属性，也可以处理连续性属性。在选择某节点上的分枝属性时，对于离散型描述属性，C4.5的处理方法与ID3相同。对于连续分布的特征，其处理方法是：

先把连续属性转换为离散属性再进行处理。虽然本质上属性的取值是连续的，但对于有限的采样数据它是离散的，如果有N条样本，那么我们有N-1种离散化的方法：<=vj的分到左子树，>vj的分到右子树。计算这N-1种情况下最大的信息增益率。另外，对于连续属性先进行排序（升序），只有在决策属性（即分类发生了变化）发生改变的地方才需要切开，这可以显著减少运算量。经证明，在决定连续特征的分界点时采用增益这个指标（因为若采用增益率，splittedinfo影响分裂点信息度量准确性，若某分界点恰好将连续特征分成数目相等的两部分时其抑制作用最大），而选择属性的时候才使用增益率这个指标能选择出最佳分类特征。
在C4.5中，对连续属性的处理如下：

1.  对特征的取值进行升序排序
   

2.  两个特征取值之间的中点作为可能的分裂点，将数据集分成两部分，计算每个可能的分裂点的信息增益（InforGain）。优化算法就是只计算分类属性发生改变的那些特征取值。
   

3.  选择修正后信息增益(InforGain)最大的分裂点作为该特征的最佳分裂点
   

4.  计算最佳分裂点的信息增益率（Gain Ratio）作为特征的Gain Ratio。注意，此处需对最佳分裂点的信息增益进行修正：减去log2(N-1)/|D|（N是连续特征的取值个数，D是训练数据数目，此修正的原因在于：当离散属性和连续属性并存时，C4.5算法倾向于选择连续特征做最佳树分裂点）
   

处理缺失值

个人觉得可以对缺失值采用随机森林进行填充，或者对缺失的列进行一定的丢弃

第五题

基尼系数用来计算不纯度的大小，在CART中引入是因为计算对数函数log代价较大，因此对log在$p=1$处利用泰勒一阶展开式，方便后续计算

第六题

预剪枝：在分裂之前就进行计算，可以有效降低过拟合风险，后剪枝，在分裂后进行计算，减掉过拟合的分裂，但是效果不如预剪枝

【1】处理连续值的文章
【2】处理缺失值文章