原文地址：https://www.jianshu.com/p/d8ceeee66a6f
基本思想在于每次分裂节点时选取一个特征使得划分后得到的数据集尽可能纯。
信息增益 = 未划分数据集的信息熵 - 划分后子数据集的信息熵的数学期望值。
事件\(x_i\)的信息量\(=-logP(x_i)\)，信息熵就是信息量的期望值，记作\(H(x)\)，即\(H(x)=-\sum_{i=1}^{n}P(x_i)logP(x_i)\)。
假设未划分数据集中共有\(C\)类，划分为了\(K\)份，则\[\begin{aligned}
Gain&=H-\overline{H_{splited}} \&=(-\sum_{i=1}^{C}P(i)logP(i))-\sum_{i=1}^K P(D_i)H(D_i))\&=(-\sum_{i=1}^{C}P(i)logP(i))-\sum_{i=1}^K \frac{len(D_i)}{len(D)} H(D_i))
\end{aligned}\]
按照信息增益来选择特征时总是会倾向于选择分支多的特征属性，这样子能够使得划分后每个子集的信息熵最小。比如，给每一个数据添加一个独一无二的id值特征，则按照id值进行分类是获得信息增益最大的。这样子，每个子集的信息熵为0，但是这样的分类毫无任何意义，无任何泛化能力。为了克服信息增益的弱泛化能力的缺陷，引入了分裂信息，即
\[SplitInfo=-\sum_{i=1}^K \frac{len(D_i)}{len(D)} P(\frac{len(D_i)}{len(D)})\]
可以看出来，数据分得越多，分裂信息也就越大。那么，
\[GainRatio=\frac{Gain}{SplitInfo}\]
为防止\(SplitInfo\)趋于0，有时需要在分母上添加一个平滑函数。分母由\(SplitInfo\)变为\(SplitInfo+\overline{SplitInfo}\)，即加上了所有可能的分裂信息的均值。
直观的说，基尼系数表示的是随机从节点中抽取两个样本，其对应的类别不一样的概率。
\[I_G(D)=1-\sum_{i=1}^{C}P(i)^2\]
\[I_G^{Splited}(D)=\sum_{j=1}^{K}P(D_j)I_G(D_j)\]
\[\Delta I_G^{Splited}(D)=I_G(D)-I_G^{Splited}(D)\]
遍历完所有属性、新划分的数据集中只有一个类别。
random forest是decision tree的bagging，并且在bagging的基础上更进一步。其核心思想就是双随机过程，随机有放回样本采样（行采样）和随机无放回特征采样（列采样）。列采样又分为全局列采样，即采后建树；局部列采样，每次节点分裂时采样。
特征选择的目标有两个，一是找到与因变量高度相关的特征变量；二是选出数目较少的特征变量并且能够充分预测因变量的结果。
"boosting"意为通过将一些表现一般，可能仅仅略好于随机猜测的模型通过特定方法进行组合后来获得一个表现较好的模型。
"adaptive"意为在训练过程中，每个新的模型都会基于前一个模型的表现结果进行调整。
\(y\in \{-1,+1\}\)
\[g_t \leftarrow \arg\min_{h\in H}(\sum_{n=1}^{N}u_n^t[y_n \neq h(x_n)])\]
\[g_{t+1} \leftarrow \arg\min_{h\in H}(\sum_{n=1}^{N}u_n^{t+1}[y_n \neq h(x_n)])\]
如果\(g_t\)在\(u^{t+1}\)下表现得不好，那么返回的\(g_{t+1}\)就不会是\(g_t\)，便可以认为\(g_{t+1}\)和\(g_t\)不同。
因此，构建\(u^{t+1}\)使得在\(u^{t+1}\)下\(g_t\)的表现近似于随机猜，即
\[\frac{\sum_{n=1}^N u_n^{t+1}[y_n\neq g_t(x_n)]}{\sum_{n=1}^N u_n^{t+1}}=\frac{1}{2}\]
即\(\sum_{n=1}^N u_n^{t+1}[y_n=g_t(x_n)]=\sum_{n=1}^N u_n^{t+1}[y_n\neq g_t(x_n)]\)。
因此，分正确的\(u_n^{t+1}=u_n^t*g_t在u_n^t下的分类错误率\)，分错误的\(u_n^{t+1}=u_n^t*g_t在u_n^t下的分类正确率\)。
记\(g_t\)在\(u_n^t\)下的分类错误率为\(\epsilon\)，即\[\epsilon=\frac{\sum_{n=1}^N u_n^{t}[y_n\neq g_t(x_n)]}{\sum_{n=1}^N u_n^{t}}\]
定义缩放因子\(\diamondsuit_t\)，即\[\diamondsuit_t=\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}\]
那么，
\[incorrect\leftarrow incorrect*\diamondsuit_t, correct\leftarrow correct/\diamondsuit_t\]
可解释为放大错误点，缩小正确点。
因此，AdaBoost算法流程总结如下：
\[\begin{aligned}
u_n^{t+1}&=u_n^{t}\cdot\diamondsuit_t^{-y_n g_t(x_n)}\&=u_n^{t}\cdot\exp(-\alpha_ty_ng_t(x_n))
\end{aligned}\]
\[\begin{aligned}
u_n^{T+1}&=u_n^1\prod_{t=1}^{T}\exp(-\alpha_t y_n g_t (x_n))\&=\frac{1}{N}\exp(-y_n\sum_{t=1}^{T}\alpha_t g_t (x_n))
\end{aligned}\]
\[linear\ score\ s=\sum_{t=1}^{T}\alpha_t g_t(x), \ G(x)=sign(s)\]
\[\begin{aligned}
\sum_{n=1}^N u_n^{T+1}&=\sum_{n=1}^N \frac{1}{N}\exp(-y_n\sum_{t=1}^{T}\alpha_t g_t (x_n)) \&=\sum_{n=1}^N \frac{1}{N}\exp(-y_n s_n)
\end{aligned}\]
可以看出来，AdaBoost采用的是指数损失函数。每一次迭代更新模型的过程可以看成是求使得
\[\min_{\eta}\ \min_{h}\frac{1}{N}\sum_{n=1}^N \exp(-y_n\sum_{\tau=1}^{t-1}\alpha_{\tau} g_{\tau} (x_n)+\eta h(x_n))\]
最小的\(h\)和\(\eta\)，进行推导后可以发现\(h\)为AdaBoost中的\(g_t\)，\(\eta\)为对应的\(\alpha_t\)。
Gradient Boosting与base model为决策树的结合即为GBDT模型。由于决策树是非线性的，并且随着深度的加深，非线性越来越强，基于决策树的GBDT也是非线性的。
AdaBoost是Gradient Boosting的一个特例，或者说Gradient Boosting是对AdaBoost进行了推广。
Gradient Boosting抽象地说，模型的训练过程是对于任意可导目标函数的优化过程。通过反复地选择一个指向负梯度方向的函数。该算法可以被看做是在函数空间里对目标函数进行了优化。Gradient Boosting在每一次模型迭代中求解使得\[\min_{\eta}\ \min_{h}\frac{1}{N}\sum_{n=1}^N err(\sum_{\tau=1}^{t-1}\alpha_{\tau} g_{\tau} (x_n)+\eta h(x_n), y_n)\]最小的\(h\)和\(\eta\)作为对应的\(g_t\)和\(\alpha_t\)。
和AdaBoost一样，Gradient Boosting也是重复选择一个表现一般的模型，并且每次都基于先前模型的表现进行调整。不同的是，AdaBoost是通过提升错分数据点的权重来定位模型的不足而Gradient Boosting是通过计算梯度来定位模型的不足。因此，相比AdaBoost，Gradient Boosting可以使用更多种类的目标函数。
因此，Gradient Boosting算法流程总结如下：
有一组数据\((x_1,y_1),\cdots,(x_N,y_N)\)和一个基础模型\(F\)，想最小化\(F(x_i)\)和真实值\(y_i\)之间的二次代价函数。\(\forall i \in [1,N]\)，称\(h_i=y_i-F(x_i)\)为关于\(x_i\)的残差，可以训练一个回归树\(h\)来拟合\(\{(x_i,y_i-F(x_i))\}\)，这样就得到了一个更好的模型\(F+h\)，重复这一个过程，最终得到了一个让人满意的模型。
这里使用回归树去拟合残差，其实就是用回归树去拟合负梯度。当loss不为square loss时，残差不一定等于负梯度！我们实际上是在通过梯度下降法对模型参数进行更新，这样理解的好处在于我们可以将这个算法推广到其他的损失函数上去。回归不一定适用平方代价，平方代价的优点在于便于理解和实现，缺点在于对于异常值的鲁棒性较差。有时候会选择其他的代价函数，如absolute loss，即\(y-F\)或者huber loss，即
\(if\ |y-F|\leq \delta,\ 则\frac{1}{2}(y-F)^2;\ if\ |y-F|> \delta,\ 则\delta(|y-F|-\frac{\delta}{2})。\)
梯度下降法的思想使得我们可以非常轻易地改用不同的损失函数设计Gradient Boosting算法。另外在使用某些其他损失函数时，残差比起负梯度更容易受到异常值的影响。
随机森林和GBDT都属于集成算法，base model都是决策树。
随机森林是决策树的bagging。
bagging通过重复对原训练数据集上进行有放回地采样生成的数据集用base model进行训练多次，然后，对于分类求众数，对于回归求平均作为最终结果。
可并行。
随机森林希望单个决策树偏差小、方差大，这样通过\(N\)个决策树的叠加可以减少方差，达到较好的结果。\(N\)越大，泛化能力越好。
随机森林里的树可以是分类树也可以是回归树。
GBDT是决策树的boosting。
boosting通过在原训练数据集变化的版本上进行base model的训练，当前base model的训练是基于上一个base model的表现的，然后线性组合起这些base model。
是串行。
GBDT希望单个决策树能力只要好于随机即可，这样通过boosting后就可以降低偏差，达到较好的表现。
树越多，GBDT越可能过拟合。
GBDT的核心在于累加所有树的结果作为最终结果，而分类树的结果显然是没办法累加的，所以GBDT中的树都是回归树，不是分类树。
Decision Tree、Random Forest、AdaBoost、GBDT
原文：https://www.cnblogs.com/cherrychenlee/p/10807010.html