机器学习之集成学习

主要总结机器学习中常用的集成方法：boosting，bagging，stacking，这一部分最为重要，在面试的过程中也总是答不好，这里多花点时间将其相关的方面全部总结一遍。

DT

决策树是一个树结构（可以是二叉树或非二叉树），适用于分类和回归，其方法是把特征空间划分成一系列矩阵，然后给每个矩阵赋值一个常数。
决策树的关键步骤是分裂属性，即在某个节点处按照某一特征属性的不同划分成不同的分支，其目标是让各个分裂子集尽可能的纯净(属于同一类别)；其关键是选择属性的度量准则
训练数据时，通过损失函数最小化原则构建决策树模型
决策树学习通常包括3个步骤：特征选择，决策树生成，决策树修剪
优点：模型具有可读性，分类速度快
缺点：容易过拟合，学习决策树是NP难题，数据集不平衡容易导致树模型产生偏差
实际使用技巧：

• 对于拥有大量特征的数据决策树会出现过拟合的现象。获得一个合适的样本比例的特征十分重要，因为在高维空间只有少量的样本的树是十分容易过拟合的。
• 考虑事先进行降维，使树更好的找到具有分辨性的特征
• 为防止决策树偏向主导类，可以通过从每个类中抽取相等数量的样本来进行类平衡

信息熵

熵表示随机变量不确定性的度量
设X是一个有限状态的离散型随机变量，其概率分布为:

$$P(X = x_i) = p_i,\ i=1,2,\cdots,n$$

则随机变量X的熵定义为

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

熵越大，则随机变量的不确定性越大。

条件熵
随机变量X给定的条件下，随机变量Y的条件熵H(Y|X)定义为：

$$H(Y|X) = \sum_{i=1}^{n}p_i H(Y|X=x_i)$$

其中，$p_i = P(X = x_i)$。

信息增益
信息增益表示的是：得知特征X的信息而使得类Y的信息的不确定性减少的程度。
具体定义如下：
特征A对训练数据集D的信息增益g(D,A)定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

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

一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息(mutual information).

ID3

熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。
信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性a来进行划分所获得的 “纯度提升” 越大 。也就是说，用属性a来划分训练集，得到的结果中纯度比较高。

ID3的缺点：

• 只能处理分类属性的数据，不能处理连续的数据
• 划分过程会由于子集规模过小而造成统计特征不充分而停止
• ID3在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息
• 没有考虑过拟合的问题
• 对缺失值的情况没有考虑

C4.5

C4.5克服了ID3仅仅能够处理离散属性的分类问题，以及信息增益偏向选择值较多特征的问题，使用信息增益比来选择特征，同时C4.5也引入了剪枝，以及对缺失值的处理(这一部分参考6)
这里着重说一下C4.5的以下这几个改进

• 处理连续属性：
  将某个连续型特征的值按从小到大排序，比如为a1,a2,…,am，这样就有m-1个划分点，对这m-1个划分点进行信息增益计算，找到最好的特征点，其过程如同CART。
• 信息增益比：
  信息增益趋向于选择值较多的特征的问题，这个很容易理解，信息熵衡量的是被分类后其混乱程度，如同聚类一样，同样数量的样本，聚的簇越多，簇内的样本当然就越紧密了(熵小)，这里加了一个惩罚项，簇越多，值越大(是在同等情况下)，公式如下： $$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$ 其中 $H_A(D)=-\sum_{i=1}^{n}{\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}}$， n 是特征 A 取值的个数

决策树C4.5算法的不足

• 决策树非常容易过拟合，但剪枝的算法有很多种，C4.5的剪枝策略有优化的空间，一般剪枝有两种思路，一种是预剪枝，即在生成决策树的时候就决定是否剪枝，另一种是后剪枝，即先生成决策树，再通过交叉验证来剪枝(CART中的剪枝就是采用后剪枝+交叉验证)
• C4.5生成的是多叉树，即一个父节点可以有多个节点，而计算机中一般来说二叉树模型比多叉数运算高效
• C4.5只能用于分类
• C4.5分裂策略使用了熵模型，里面有大量耗时的对数运算，如果是连续值，还有大量的排序运算

CART

CART与ID3，C4.5不同之处在于CART生成的树必须是二叉树，其全称是分类与回归树(classification and regression tree)，既可以用于分类问题，又可以用于回归问题。
CART对C4.5进行了改进，其分类模型对比于C4.5:
其中在分裂策略上，C4.5使用熵模型，涉及大量的对数运算，而CART分类树算法使用基尼指数代替信息增益比，基尼系数代表了模型的纯度，基尼指数越小，模型越纯净。
假设有 K 个类别，样本点属于第k类的概率为$p_k$,则概率分布的基尼指数定义为：

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

在树的构建上，除了度量方式使用基尼指数外，与C4.5最大的区别就是CART使用二叉树，对于连续特征来说是一样的，但是对于离散特征而言就不同，比如被选中的特征A有三个类别A1,A2,A3，C4.5会在该节点下分裂为三个子树，但是CART采用的是不停的二分，比如上面的例子，CART会考虑将A分为{A1}和{A2,A3},{A1,A2}和{A3},{A1,A3}三种情况，然后分别对这三种情况找出基尼系数最小的组合来建立二叉树[这一点，在统计学习方法上和博客（参考7）上有出入，不知道是不是我理解有误]
统计学习方法中这样讲到：
如果样本集合D根据特征A是否取某一可能值a被分割为$D_1$和$D_2$两部分，则在特征A的条件下，集合D的基尼指数定义为：

$$Gini(D,A)=\frac{D_1}{D}Gini(D_1)+\frac{D_2}{D}Gini(D_2)$$

按上面的例子，统计学习方法其实是做了一个二分，是线性的（即是A1和不是A1的，是A2和不是A2的，是A3和不是A3的），而该博客中提到的是组合，这种复杂度就比较高了。
有一个疑问：上面讲到二叉树模型比多叉树模型运行高效，但是构建二叉树的时间复杂度比多叉树要大很多，应该是多了一个循环，具体优势我觉得应该是构建后的查询的优势吧。

回归树
使用平方误差最小化准则来选择特征并进行划分，又叫做最小二乘回归树，假设已将输入空间划分为 M 个单元$R_1,R_2,...,R_M$，即 M 个特征，并且在每个单元$R_m$上有一个固定的输出值$c_m$，于是回归树可以表示为:

$$f(x)=\sum_{m=1}^{M}c_{m}I(x\in R_m)$$

处理连续特征的方法同CART分类树，只是在分裂的度量方式上有所改变：
当输入空间的划分确定时，可以用平方误差$\sum_{x_i \in R_m}(y_i - f(x_i))^2$来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优值。
选择最优切分特征 j 和切分点 s ,具体做法为:

$$\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}]$$

首先遍历特征 j ,对固定的切分特征 j 扫描切分点 s ,选择使上式达到最小值的对 (j,s)

剪枝

剪枝算法用来防止决策树过拟合，提高泛化能力，剪枝分为预剪枝和后剪枝。
预剪枝是指在决策树的生成过程中，对每个节点在划分前先进行评估，若当前的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点。
后剪枝是指先从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点，能带来泛化性能的提升，则将该子树替换为叶节点。
那么怎么来判断是否带来泛化性能的提升呢？最简单的就是留出法，即预留一部分数据作为验证集来进行性能评估

决策树的损失函数如下：

$$C_{\alpha}(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|\\ H_t(T)=-\sum_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$$

其中树T的叶子节点个数为|T|，t是树T的叶子节点，该叶节点有$N_t$个样本点，其中k类样本点有$N_{tk}$个，k=1，2，..,K，$H_t(T)$为叶节点t上的经验熵，$\alpha>=0$为参数

剪枝过程如下：

• 从生成算法的决策树$T_0$底端开始不断剪枝，直到$T_0$的根节点，形成一个子树序列$\{T_0,T_1,...,T_n\}$
  具体过程：对于固定的$\alpha$，一定存在使损失函数最小的子树，将其表示为$T_{\alpha}$，也就是说不断的增加$\alpha$，就会得到一系列的最优子树，直到$\alpha$大到根节点组成的单节点树最优为止[详见统计学习方法]
• 通过交叉验证法在独立的数据集上对子序列进行测试，从中选择最优子树

决策树小结

优点：

• 简单直观
• 基本不需要预处理，不需要提前归一化
• 使用决策树预测的代价是$O(log_2m)$
• 既可以处理离散值，也可以处理连续值
• 可以处理多维度输出的分类问题
• 可以通过交叉验证来选择模型，提高模型的泛化能力

缺点：

• 非常容易过拟合[剪枝]
• 受样本点的影响比较大[通过集成学习]
• 容易陷入局部最优[通过集成学习]
• 比较复杂的关系决策树学习不到，比如异或[使用神经网络]
• 样本不平衡会严重影响决策树生成[可以通过调节样本权重]

Boosting

先从训练集中用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前的弱学习器1学习误差率高的训练样本点的权重变高，使得这些样本点在后面的弱学习器中能够得到足够的重视，在调整权重后重新训练弱学习期2，如此重复进行，直到弱学习器达到事先指定的数目t，最后将这t个弱学习器通过集合策略进行整合，得到最终的强学习器。
boosting的思想用如下公式表示：

$$F_m(x)=f_0+\alpha_1f_1(x)+...+\alpha_mf_m(x)$$

AdaBoost

AdaBoost的核心是修改样本的权重，让学习器更看重权重大的样本
提升方法面临两个问题：

• 在每一轮，如何改变训练数据的概率分布或者权值分布。
• 如何将弱分类器组合成强分类器。

AdaBoost 的做法：

• 提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类的样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮弱分类器的关注；(这一点有点像样本不平衡的解决方案)
• 采用加权多数表决。具体的，加大分类错误率低的分类器的权值，使其在表决中起较大作用，减少分类误差率大的弱分类器的权值，使其在表决中起较小作用。

由上可以知道AdaBoost是一个加法模型：

$$f(x) = \sum_{m=1}^{M}\alpha_{m}G_{m}(x)$$

其中 $G_{m}(x)$为基学习器，$\alpha_{m}$为系数。
在第m步的时候，目标是最小化指定的损失函数$L(y,f(x))$，即 :

$$\min\limits_{(\alpha_{m}\,,\,G_{m})}\sum\limits_{i=1}^{N}L(y_{i}, \,\sum\limits_{m=1}^{M}\alpha_{m}G_{m}(x_{i})) \qquad$$

其中$(x_{1},y_{1}),(x_{2},y_{2}),\cdots(x_{N},y_{N})$为训练数据集，也就是说我们要学习的是$\alpha_{m}$和$G_m$，我们学习第m个基学习器的时候，前m-1个学习器是固定的，也就是说不再改变，这里体现了Boosting方法的一个好处，即更好的复用性，比如说数据改变了，或者其他之类的，不用在从新训练前面的模型，而是往后添加模型即可[这是我的理解，可能有误]
AdaBoost的损失函数是指数损失函数，形式如下：

$$​ L(y,\,f(x)) = e^{-yf(x)}$$

即我们现在的目标是在指数函数最小的情况下求得 $\alpha_{m}$和 $G_{m}(x)$ 。

$$​ (\alpha_{m},G_{m}(x)) = \mathop{\arg\min}\limits_{(\alpha,G)}\sum\limits_{i=1}^{N}e^{-y_{i}f_{m}(x_{i})} = \mathop{\arg\min}\limits_{(\alpha,G)}\sum\limits_{i=1}^{N}e^{-y_{i}(f_{m-1}(x_{i}) + \alpha G(x_{i}))}$$

令 $w_{i}^{(m)} = e^{-y_{i}f_{m-1}(x_{i})}$，由于 $w_i^{(m)}$不依赖于 $\alpha$ 和 $G(x)$ ，所以可认为其是第m步训练之前赋予每个样本的权重。
这里的$G(x)$是一个基本分类器，这里我们假设是二分类：

$$G_m(x):X->\{-1,+1\}$$

于是前面的式子就变为了：

$$\sum\limits_{i=1}^{N}w_{i}^{(m)}e^{-y_i\alpha G(x_i)} = e^{-\alpha}\sum\limits_{y_{i}=G(x_{i})}w_{i}^{(m)} + e^{\alpha}\sum\limits_{y_i \neq G(x_i)}w_i^{(m)} \\ ​ = (e^{\alpha} - e^{-\alpha})\sum\limits_{i=1}^Nw_i^{(m)}\mathbb{I}(y_i \neq G(x_i)) + e^{-\alpha}\sum\limits_{i=1}^Nw_i^{(m)}$$

也就是说让误分类对应的$w_i^{(m)}$变小【这一部分的严格证明参考统计学习方法和参考11】，那么下一轮更新w即可。
由

$$w_{i}^{(m+1)} = e^{-y_{i}f_{m}(x_{i})} = e^{-y_{i}(f_{m-1}(x_{i}) + \alpha G(x_{i}))} = e^{-y_if_{m-1}(x_i)}e^{-y_i\alpha_mG_m(x_i)} = w_i^{(m)}e^{-y_i\alpha_mG_m(x_i)}$$

可以看到对于$\alpha_m>0$，若$y_i = G_m(x_i)$ ，则 $w_i^{(m+1)} = w_i^{(m)}e^{-\alpha_m}$ ，表明前一轮被正确分类样本的权值会减小； 若 $y_i \neq G_m(x_i)$ ，则 $w_i^{(m+1)} = w_i^{(m)}e^{\alpha_m}$，表明前一轮误分类样本的权值会增大。

AdaBoost算法流程

输入： 训练数据集 $T = \left \{(x_1,y_1), (x_2,y_2), \cdots (x_N,y_N)\right \} ， y\in\left\{-1,+1 \right\}$ ， 基学习器 $G_m(x)$ ，训练轮数M

1. 初始化权值分布：$w_i^{(1)} = \frac{1}{N}\:, \;\;\;\; i=1,2,3, \cdots N$

2. for m=1 to M:
   (a) 使用带有权值分布的训练集学习得到基学习器$G_m(x)$:

   $$​ G_m(x) = \mathop{\arg\min}\limits_{G(x)}\sum\limits_{i=1}^Nw_i^{(m)}\mathbb{I}(y_i \neq G(x_i))$$

   (b) 计算 $G_m(x)$在训练集上的误差率：

   $$​ \epsilon_m = \frac{\sum\limits_{i=1}^Nw_i^{(m)}\mathbb{I}(y_i \neq G_m(x_i))}{\sum\limits_{i=1}^Nw_i^{(m)}}$$

   (c) 计算 $G_m(x)$ 的系数：$\alpha_m = \frac{1}{2}ln\frac{1-\epsilon_m}{\epsilon_m}$
   (d) 更新样本权重分布：$w_{i}^{(m+1)} = \frac{w_i^{(m)}e^{-y_i\alpha_mG_m(x_i)}}{Z^{(m)}}\; ,\qquad i=1,2,3\cdots N$
   　　其中$Z^{(m)}$ 是规范化因子， $Z^{(m)} = \sum_{i=1}^Nw^{(m)}ie^{-y_i\alpha_mG_m(x_i)}$，以确保所有的 $w_i^{(m+1)}$ 构成一个分布。

3. 输出最终模型： $G(x) = sign\left[\sum_{m=1}^M\alpha_mG_m(x) \right]$

上面摘抄自10，但是一大段废话，其实只需要知道：AdaBoost中新生成的学习器和前面的学习器的区别在于样本的权重被改变了，而这个权重改变公式如下（以指数损失为例）：

$$w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)) \\ w_{m+1,i}=\left\{\begin{matrix} \frac{w_{mi}}{Z_m}e^{-a_m} &G_{m}(x_i)=y_i \\ \frac{w_{mi}}{Z_m}e^{a_m} &G_m(x_i)\neq y_i \end{matrix}\right.\\$$

对于上述公式只需要知道两点：

• 其中$\alpha_m$表示的是第m个基学习器在整个加法模型的占比，这个值表示的是模型正确判断样本的权重和，即模型越准确，该值越高，改值参看前面部分。
• 其改变权重的核心思想是，如果根据前面的权重学习到的模型将该样本误判了，下一个模型增加该样本的权重，否则，降低该样本的权重，具体的$G_{m}(x_i)=y_i$乘以的是一个小于1的数，$G_m(x_i)\neq y_i$乘以的是一个大于1的数，而这个数到底有多么的大于1或者小于1，要看该模型对样本判断的正确率

这里我们可以知道基学习器学习的样本是带权重的，由上，如果是回归问题，仍然按照这个思路(以指数损失为例)，同样希望当前模型误判的样本权重在下一轮变大，反之变小，只不过不再是通过$y_iG_m(x_i)$来判断，因为该值不能说明问题，不过我们可以使用$|y_i-G_m(x_i)|$来判断，也就是说基学习器预测的结果和当前结果差距越大，那么我们就越增大这个样本的权重，那么更新方式就可以是如下公式：

$$w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(\alpha_m|y_i-G_m(x_i)|)$$

当然上面这个思路只是我自己想的，实际上更新过程如下：
计算训练集上的最大误差：

$$E_k=\max|y_i-G_k(x_i|\,\,\,\,i=1,2,...,m$$

计算每个样本的相对误差(以线性误差为例)：

$$e_{ki}=\frac{|y_i-G_k(x_i)|}{E_k}$$

计算回归误差率：

$$e_k=\sum_{i=1}^{m}w_{ki}e_{ki}$$

计算弱学习器的系数：

$$\alpha_k=\frac{e_k}{1-e_k}$$

权重更新：

$$w_{k+1,i}=\frac{w_{ki}}{Z_k}\alpha_{k}^{1-e_{ki}}$$

具体参见11

如此AdaBoost就讲完了，回想一下Boosting方法的思路，和梯度下降法非常像，比如我们想知道最优的w，先初始化一个$w_0$，然后通过求解损失函数的w的梯度，加上学习率，如下：

$$w=w-\alpha \,\,dw$$

来一步步逼近w的最优值，再来看AdaBoost方法，第一个基学习器通过权重得到了对样本的一个预测值，对权重使用第一个学习器进行更新，将误判的权重变高，这样第二个学习器就更加重视该样本，就比如最优值是1（样本的标签），第一个学习器将样本预测为-1，模型的结果为$-a_1*1$，由于第二个学习器足够重视该样本，这个样本在第二个学习器中就被预测为1，那么整个模型的预测值就是$-a_1+a_2$，也就是向最优值1移动，符合梯度下降的思想，也是Boosting所体现的核心思想。

缺点：对异常数据敏感

GBDT

GBDT的核心：通过梯度下降获得最优值
GBDT主要由三个概念组成：Regression Decision Tree，Gradient Boosting，和Shrinkage
回归树在前面已经讲到，这里主要涉及的是梯度提升和shrinkage
以一个问题来讲梯度提升的思想：
给定如下一个问题：

$$arg \min_x f(x)$$

一般的优化方法是使用梯度下降法，即如下过程：

1. 给定一个起点$x_0$
2. 对i=1,2,..,K分别做如下迭代： $$x_i=x_{i-1}+\gamma_{i-1}*g_{i-1}\\ g_{i-1}=-\frac{\partial f}{\partial x}|_{x=x_{i-1}}\,\,,\,\,表示f在x_{i-1}点的梯度$$
3. 直到$|g_{i-1}|$足够小，或者$|x_i-x_{i-1}|$足够小停止

整个优化过程用加法表示如下：

$$x_k=x_0+\gamma_1*g_1+\gamma_2*g_2+...+\gamma_k*g_k$$

Gradient Boosting就是由此而来。
再来看GBDT的迭代过程，假设前一轮迭代过程得到的强学习器是$f_{t-1}(x)$，损失函数是$L(y,f_{t-1}(x))$，本轮的目标就是找到一个CART回归树模型的弱学习器$h_{t}(x)$，让本轮的损失函数$L(y,f_t(x))=L(y,f_{t-1}(x)+h_t(x))$最小。将$h_t(x)$类比成$g_t$，按照上述思路，就不难理解梯度提升的思想了。
梯度提升算法流程如下：
输入：训练数据$(x_1,y_1),(x_2,y_2),...,(x_N,y_N)$，可微损失函数$L(y,F(x))$，基本回归算法，迭代次数M
输出：训练数据对应的回归模型$F_M(x)$
算法步骤：
第一步：初始化$F_0(x)$为常量：

$$F_0(x)=arg \min_{\rho}\sum_{i=1}^{N}L(y_i,\rho)$$

这里比如L选择平方损失函数，上式变为：

$$arg \min_{\rho}\sum_{i=1}^{N}\frac{1}{2}(y_i-\rho)^2$$

求导，令导函数等于0，得到极值：

$$\sum_{i=1}^N(y_i-\rho)=0\\ F_0(x)=\rho=\frac{1}{N}\sum_{i=1}^Ny_i$$

第二步：令$m=1,2,...,M$，按下面步骤求解$F_m(x)$:

1. 计算“伪残差”： $$r_{m,i}=-[\frac{\partial L(y_i,F(x_i))}{\partial F(x)}]_{F(x)=F_{m-1}(x)}\,\,,\,\,i=1,2,..,N$$
2. 使用基本回归算法拟合数据$(x_1,r_{m,1}),(x_2,r_{m,2}),..,(x_N,r_{m,N})$，得到$h_m(x)$
3. 计算$\rho_m$: $$\rho_m=arg \min_{\rho}\sum_{i=1}^{N}L(y_i,F_{m-1}(x_i)+\rho h_m(x))$$ 提一句：这里拟合的是梯度，但是梯度前面是需要加上学习率的，这里的$\rho$就是学习率，通过线性搜索使损失函数最小来得到最优的学习率
4. 更新$F_m$为： $$F_{m}(x)=F_{m-1}(x)+\rho_mh_m(x)$$

第三步：训练数据对应的回归模型即为$F_M(x)$

对于GBDT而言，只是将基回归树设定为CART回归树了，具体如下：
输入：训练数据$(x_1,y_1),(x_2,y_2),...,(x_N,y_N)$，可微损失函数$L(y,F(x))$，迭代次数M
输出：训练数据对应的$F_M(x)$
算法步骤：
第一步：初始化$F_0(x)$为常量：

$$F_0(x)=arg \min_{\rho}\sum_{i=1}^{N}L(y_i,\rho)$$

第二步：令$m=1,2,...,M$，按下面步骤求解$F_m(x)$:

1. 计算“伪残差”： $$r_{m,i}=-[\frac{\partial L(y_i,F(x_i))}{\partial F(x)}]_{F(x)=F_{m-1}(x)}\,\,,\,\,i=1,2,..,N$$
2. 使用CART回归树拟合数据$(x_1,r_{m,1}),(x_2,r_{m,2}),...,(x_N,r_{m,N})$，得到第m棵树的叶子节点区域$R_{m,j}$，其中$j=1,2,...,J_m$
3. 对$j=1,2,..,J_m$计算： $$\rho_{m,j}=arg \min_{\rho}\sum_{x_i \in R_{m,j}}L(y_i,F_{m-1}(x_i)+\rho)$$ 这里的$\rho_{m,j}=\rho_mc_{m,j}$，其中CART回归树为$h_m(x)=\sum_{j=1}^{J_m}c_{m,j}I(x \in R_{m,j})$
4. 更新$F_m$为： $$F_m(x)=F_{m-1}(x)+\sum_{j=1}^{J_m}\rho_{m,j}I(x \in R_{m,j})$$

第三步：训练数据对应的回归模型即为$F_M(x)$

Shrinkage的主要目的是避免过拟合，即每次走一小步逐渐逼近结果的效果要比每次迈一大步逼近结果的方式更容易避免过拟合。

GBDT分类问题

1. GBDT分类没有直接求解概率值，而是通过一步步迭代，让模型的概率值与真实的概率值(1/0)越来越接近
2. 做分类的时候，仍然用的是CART回归树，并且每一轮的y标签都会发生变化，只不过在每一轮模型得到y’后，用log似然函数的时候的y使用的是原始的y(即1/0)
3. 对于二分类，CART回归树不变，但是对于多分类，比如K分类，迭代M次，那么就构造了K*M棵CART回归树，比如对于第i次迭代，需要构造K个回归树，每棵树都是一个二分类(结果分布在0到1之间)

GBDT常见的损失函数
分类问题一般有两种损失函数

1. 对数损失函数： $$L(y,f(x))=log(1+exp(−yf(x)))$$
2. 指数损失函数： $$L(y,f(x))=exp(−yf(x))$$

回归算法常用的损失函数：

1. 均方差 $$L(y,f(x))=(y−f(x))2$$
2. 绝对损失 $$L(y,f(x))=|y−f(x)|$$
3. Huber损失 $$L(y,f(x))= \left\{\begin{matrix} \frac{1}{2}(y−f(x))^2 & |y−f(x)|≤δ\\ δ(|y−f(x)|−\frac{δ}{2})& |y−f(x)|>δ \end{matrix}\right.$$

AdaBoost与GBDT

1. AdaBoost和GBDT在损失函数这一块不一样的地方是，AdaBoost目标是找到一个可以使当前损失函数最小的弱分类器，即让偏导数等于0求解即可，而GBDT里面的损失函数如果是指数损失，可以直接求解，但是其他的，就只能用梯度下降来求解

GBDT和RF

1. 异常点少的样本集GBDT表现更加优秀，异常点多的样本集，随机森林表现更好

树模型的并行化
待。。。

XGBoost

XGBoost是GBDT的一种高效实现
先解释一下泰勒公式：用函数在某点的信息描述其附近的取值，其初衷是用多项式来近似表示函数在某点周围的情况，定理如下：
设 n 是一个正整数。如果定义在一个包含 a 的区间上的函数 f 在 a 点处 n+1 次可导，那么对于这个区间上的任意 x，都有：

$${\displaystyle f(x)=f(a)+\frac {f'(a)}{1!}(x-a)+\frac {f^{(2)}(a)}{2!}(x-a)^{2}+\cdots +\frac {f^{(n)}(a)}{n!}(x-a)^{n}+R_{n}(x).}$$

其中的多项式称为函数在a 处的泰勒展开式，剩余的$\displaystyle R_{n}(x)$是泰勒公式的余项，是$\displaystyle (x-a)^{n}$的高阶无穷小。

XGBoost模型在第t步，对$x_i$的预测为：

$$\hat{y}_i^t= \hat{y}_i^{t-1} + f_t(x_i)$$

其中 $f_t(x_i)$ 就是我们这次需要加入的新模型，即需要拟合的模型，此时，目标函数就可以写成：

$$\begin{split} Obj^{(t)} &= \sum_{i=1}^nl(y_i, \hat{y}_i^t) + \sum_{i=i}^t \Omega(f_i) \\ &= \sum_{i=1}^n l\left(y_i, \hat{y}_i^{t-1} + f_t(x_i) \right) + \Omega(f_t) + constant \end{split}\tag{1}$$

即此时最优化目标函数，就相当于求得了$f_t(x_i)$（也就是当前树模型），其中的$\Omega(f_t)$为树模型的正则项，表示如下：

$$\Omega(f_t)=\gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2$$

其中$w_j$表示叶子节点对应的取值，T表示叶子节点的个数

由泰勒级数我们将$f(x+\Delta x)$在x处二阶展开，如下：

$$f(x+\Delta x)\approx f(x)+f'(x)\Delta x +\frac{1}{2}f^{''}(x)\Delta x^2$$

将$\Delta x$当成$f_t(x)$，目标函数就变为如下式子：

$$Obj^{(t)} = \sum_{i=1}^n \left[ l(y_i, \hat{y}_i^{t-1}) + g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) + constant$$

其中$g_{i}$ 为损失函数的一阶导，$h_{i}$为损失函数的二阶导，注意这里的导是对 $\hat{y}_i^{t-1}$求导.
上面的式子对比与GBDT还是很明显的，利用了梯度的二阶导。
用$w_{q(x)}$表示树模型$f_t(x)$，其中q(x)是一个映射，将样本指向对应叶子节点，而$w_j$表示对应的叶子节点的值
假设$I_j=\{ i \vert q(x_i)=j \}$为第 j 个叶子节点的样本集合，根据上面的一些变换可以写成：

$$\begin{split} Obj^{(t)} &\approx \sum_{i=1}^n \left[ g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) \\ &= \sum_{i=1}^n \left[ g_iw_{q(x_i)} + \frac12h_iw_{q(x_i)}^2 \right] + \gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2 \\ &= \sum_{j=1}^T \left[(\sum_{i \in I_j}g_i)w_j + \frac12(\sum_{i \in I_j}h_i + \lambda)w_j^2 \right] + \gamma T \end{split}$$

由于一个叶子结点有多个样本存在，因此才有了$\sum_{i \in I_j}g_i$和 $\sum_{i \in I_j}h_i$这两项。
定义 $G_j=\sum_{i \in I_j}g_i ， H_j=\sum_{i \in I_j}h_i$，则上式可以写成：

$$Obj^{(t)} = \sum_{j=1}^T \left[G_jw_j + \frac12(H_j + \lambda)w_j^2 \right] + \gamma T$$

树的结构是固定的，即我们已经知道了每个叶子结点有哪些样本，所以 G_j 和 H_j 是确定的，但 w 不确定（ w 其实就是我们需要预测的值），那么令目标函数一阶导为0，则可以求得叶子结点 j 对应的值：

$$w_j^*=-\frac{G_j}{H_j+\lambda}$$

注意前面用泰勒级数只是引入了损失函数L的二阶导数信息，也就是说将损失函数简化成该表达式，那么让损失函数最小化，很显然进行求导就可以得到最小值，求导让导函数等于0：

$$w_j^*=-\frac{G_j}{H_j+\lambda}$$

目标函数的值可以化简为：

$$Obj = -\frac12 \sum_{j=1}^T \frac{G_j^2}{H_j+\lambda} + \gamma T$$

关于如何构建基学习器和原始的GBDT有点区别，具体过程如下：
a、从深度为0的树开始，对每个叶节点枚举所有的可用特征
b、 针对每个特征，把属于该节点的训练样本根据该特征值升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的最大收益（采用最佳分裂点时的收益）
c、 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，把该节点生长出左右两个新的叶节点，并为每个新节点关联对应的样本集
d、回到第1步，递归执行到满足特定条件为止
那么如何计算上面的收益呢，很简单，仍然紧扣目标函数就可以了。假设我们在某一节点上二分裂成两个节点，分别是左（L）右（R），则分列前的目标函数是$-\frac12 [\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}] + \gamma$，分裂后则是$-\frac12 [ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda}] +2\gamma$ ，则对于目标函数来说，分裂后的收益是（这里假设是最小化目标函数，所以用分裂前-分裂后）：

$$Gain=\frac12 \left[ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma$$

关于为什么xgboost使用二阶导的原因：

1. 引入二阶导就相当于引入了加速度信息。
2. 我觉得使用二阶导只是为了模拟出一个损失函数的近似形式，因为到最后还是使用的一阶求导。

lightgbm

有时间就看看

bagging

bagging原理就是给定T个弱学习器，假设有m个训练样本，用来训练这T个弱学习器的样本是从这m个训练样本中有放回的选取m个样本(这就是bootstrap采样)进行训练，最后对这T个弱学习器采取结合策略来合并，对于弱学习器，一般使用决策树。对于合并多个弱学习器采用的方法：如果是分类问题，通常采用简单的投票法，得到最多票数的类别或者之一作为最终模型的输出；对于回归问题，通常使用简单的平均法，对T个弱学习器的得到的回归结果进行算术平均作为最终模型的输出。
讲一下bootstrap采样：因为是有放回的采样，所以之前采样到的样本放回后有可能继续被采样到，这里每个样本被采样到的概率是$\frac{1}{m}$，不被采样到的概率是$1-\frac{1}{m}$。那么m次采样都没有被采样到的概率是$(1-\frac{1}{m})^m$，这里如果m趋近与无穷大，这个结果趋近于$\frac{1}{e}=0.368$，即bagging每轮随机采样的过程中，训练数据集中大约有36.8%的数据没有被采样到，这些数据被称为袋外数据，由于这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。
这里讲到由于Bagging算法每次都进行采样来训练模型，因此泛化能力很强，对降低模型的方差有作用，而对模型的拟合程度会差，即模型的偏差会大一些
这里要理解上面的这句话，需要知道模型的方差，偏差，过拟合，欠拟合等概念

讲解几个概念：
偏差(bias)：学习算法的期望预测与真实结果的偏离程度，刻画了学习算法本身的拟合能力
方差(variance)：刻画的是同样大小的训练集的变动所导致学习性能的变化，刻画了数据扰动所造成的影响
欠拟合：模型的偏差过大，没有找出更多的特征
过拟合：模型的方差过大，特征过多
继续看上面的这个图，高偏差低方差的情况就是模型过于简单，需要寻找更多的特征来拟合模型；高偏差高方差就是模型不但对不同的数据集不稳定而且对真实数据预测不准，这个应该很少发生；低偏差高方差就是说预期的结果都落在真实结果的周围，过拟合

RF

。。。

n问

1. xgboost原理，怎么防止过拟合
2. Boosting和bagging在不同情况下的选择
3. gbdt的适用场景
4. xgb，rf，lr优缺点及应用场景
5. 决策树怎么剪枝
6. lightgbm优势
7. xgboost+lr的优势
8. gbdt如何进行分类

stacking

。。。

参考

1. 机器学习中的Bias(偏差)，Error(误差)，和Variance(方差)有什么区别和联系
2. 集成学习原理小结
3. 一文读懂集成学习
4. Bagging与随机森林算法原理小结
5. 决策树
6. 决策树算法原理上
7. 决策树算法原理下
8. 机器学习面试干货精讲(1)
9. GBDT
10. 集成学习之Boosting-AdaBoost原理
11. 集成学习之AdaBoost算法原理小结
12. GBDT理论知识总结
13. Greedy Function Approximation A Gradient Boosting Machine
14. 泰勒公式
15. GBDT算法原理深入理解
16. 通俗易懂理解-GBDT算法原理
17. xgboost原理