Decision Tree、Random Forest、AdaBoost、GBDT

原文地址：https://www.jianshu.com/p/d8ceeee66a6f

Decision Tree

基本思想在于每次分裂节点时选取一个特征使得划分后得到的数据集尽可能纯。

划分标准

信息增益(Information Gain)

信息增益 = 未划分数据集的信息熵 - 划分后子数据集的信息熵的数学期望值。
事件\(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}\]

增益比率(Gain Ratio)

按照信息增益来选择特征时总是会倾向于选择分支多的特征属性，这样子能够使得划分后每个子集的信息熵最小。比如，给每一个数据添加一个独一无二的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}\)，即加上了所有可能的分裂信息的均值。

基尼系数(Gini Index)

直观的说，基尼系数表示的是随机从节点中抽取两个样本，其对应的类别不一样的概率。
\[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)\]

常用的决策树类型

• ID3
  使用信息增益作为属性选择标准。
  需离散属性。如果是连续属性，将数据集\(D\)中元素按照此属性进行排序，则每2个相邻元素的中间点可以看成是潜在分裂点。从第一个潜在分裂点开始，分裂\(D\)并计算2个集合的期望信息，具有最小期望信息的点称为这个属性的最佳分裂点，其信息期望作为此属性的信息期望。ID3缺点在于其倾向于选择分支数量较多的特征变量，可能导致训练得到一个庞大且深度浅的树；另外，输入变量必须是分类变量，连续变量需要离散化。
• C4.5
  使用增益比率作为属性选择标准。
• CART
  分类：最小化基尼系数的均值，众数作为最终结果；
  回归：最小化平方差误差的均值，取均值作为最终结果。
  只能形成二叉树。

分裂相关性质

树分裂的终止条件

遍历完所有属性、新划分的数据集中只有一个类别。

分裂属性

• 属性是离散值且不要求生成二叉决策树，此时用属性的每一个划分作为一个分支；
• 属性是离散值且要求生成二叉决策树，此时使用属性划分的一个子集进行测试，按是否属于这两个子集分成了2个分支；
• 属性是连续值，此时确定一个值作为分裂点，按照值是否大于这个分裂点生成两个分支。

优缺点

• 优点：
  • 分类规则清晰，结果容易理解。
  • 计算量相对较小，实现速度快。
  • 非线性，非参数方法，谁跑效果都相对一样。
  • 不需要预选变量，可处理异常值、缺失值（使用替代分支）、不同量纲值等数据类型。
  • 同时可以处理分类变量和数值变量。但是可能决策树对于连续变量的划分并不合理，可以提前离散化。
  • 相对于Logistic Regression，可以处理多输出的问题。
  • 另外，决策树不需要做变量筛选，会自动筛选。可以做特征选择、特征组合。
• 缺点：
  • 最大的缺点就是很容易过拟合，导致实际预测的效果并不高。
  • 泛化能力太差，对于没有出现过的值几乎没有办法。
  • 若数据集类别不平衡，生成的树会存在偏见。
  • 不是很稳定，数据变一点，树就会发生变化。对异常值过于敏感， 很容易导致树的结构发生巨大的变化。
  • 不适合处理高维稀疏数据，不适合处理特征关联性较强的数据。

Random Forest

random forest是decision tree的bagging，并且在bagging的基础上更进一步。其核心思想就是双随机过程，随机有放回样本采样（行采样）和随机无放回特征采样（列采样）。列采样又分为全局列采样，即采后建树；局部列采样，每次节点分裂时采样。

基本流程

• 样本的随机
  从样本集中使用bootstrap随机选择\(N\)个样本。常\(N=\sqrt{N_{样本数}}\)。
• 特征的随机
  从所有属性中随机选择\(K\)个属性，选择最佳分割方式作为节点建立decision tree。常\(K=\sqrt{N_{属性数}}\)。
• 重复上述过程\(m\)次，建立了\(m\)棵树。
• \(m\)棵树投票表决，分类概率总和，可以平衡不平衡数据集的误差，回归平均值。

优缺点

• 优点
  • 在当前的很多数据集上，相对其他算法有着很大的优势，表现良好。
  • 能够处理很高维度的数据，并且不用做特征选择。
  • 在训练完后，它能够给出哪些特征比较重要。
  • 在创建随机森林的时候，对泛化误差使用的是无偏估计，模型泛化能力强，一定程度上能够避免过拟合。
  • 训练速度快，容易做成并行化方法。
  • 在训练过程中，能够检测到特征间的相互影响。
  • 实现比较简单。
    + 对于不平衡的数据集来说，它可以平衡误差。
  • 如果有很大一部分的特征遗失，仍可以维持准确度。
• 缺点:
  • 已经证明了在某些噪音较大的分类或回归问题上会过拟合。
  • 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的。

Random Forest用于特征选择

特征选择的目标有两个，一是找到与因变量高度相关的特征变量；二是选出数目较少的特征变量并且能够充分预测因变量的结果。

特征重要性

• 基尼系数
  特征\(i\)重要性=\(\frac{\sum_{N_{DT}}\sum_{M_i} Gini变化量(特征i)}{\sum_{j \in L}\sum_{N_{DT}}\sum_{M_j} Gini变化量(特征j)}\)
  其中，特征\(i\)出现的节点的集合记作\(M_i\)，特征\(j\)出现的节点的集合记作\(M_j\)，random forest中树的棵数记作\(N_{DT}\)，将属性集合记作\(L\)。
  • 存在的问题：
    对于存在关联的多个特征，其中任意一个都可以作为指示器或者说是优秀特征，并且一旦其中的某个特征被选中之后，其他特征的重要度就会急剧下降，因为不纯度已经被选中的那个特征降下来了，其他的特征就很难再降低那么多的不纯度了。这样一来，只有先被选中的那个特征重要度很高，其他关联特征的重要度往往较低。在理解数据时，就会造成误解，导致错误地认为先被选中的特征是很重要的，而其余的特征是不重要的，但实际上这些特征对响应变量的作用是十分接近的。
    特征随机选择方法稍微缓解了这个问题，但是总的来说并没有完全解决。
• OOB error
  将OOB数据代入训练好的RF中去计算结果，对比实际类别得ERROR1；对每个特征随机添加一定的噪声或者将当前特征随机打散，再次代入RF去计算得ERROR2；计算ERROR1与ERROR2之间的差值，差值越大，说明对应的特征越重要。

常用的步骤

1. 初步估计与排序

• 对随机森林中的特征变量按照特征重要性降序排序。
• 确定删除比例，从当前特征变量中剔除相应比例的不重要的特征，从而得到一个新的特征集。
• 用新的特征集建立新的随机森林，并计算特征集中每个特征的重要性，降序排序。
• 重复上述过程至剩下\(m\)个特征。

1. 根据1中得到的每个特征集及基于其建立的RF，计算OOB error，选择OOB error最小的特征集作为最后选定的特征集。

Adaptive Boosting(AdaBoost)

"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算法流程总结如下：

• 初始化：
  \(u^1=[\frac{1}{N},\frac{1}{N},\cdots,\frac{1}{N}]^T\)
• for t = 1,2,...,T
  1. 获得\(g_t\)：
     \(g_t \leftarrow \arg \min_{h\in H}(\sum_{n=1}^{N}u_n^t[y_n \neq h(x_n)])\)
  2. 更新\(u^t\)得\(u^{t+1}\)：
     \(\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=\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}\)
     对于\(u_n^{t+1}\),有
     \(if\ y_n=g_t(x_n),\ u_n^{t+1}=u_n^{t}/\diamondsuit_t\)
     \(if\ y_n\neq g_t(x_n),\ u_n^{t+1}=u_n^{t}*\diamondsuit_t\)
  3. 计算\(\alpha_t\)
     \(\alpha_t=\ln \diamondsuit_t\)
     \(G_t=\sum_{\tau=1}^t\alpha_{\tau} g_{\tau}\)
• return \(h=sign(G_T)\)

Gradient Boosted Decision Tree(GBDT)

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

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算法流程总结如下：

• 初始化：
  \(s_1=s_2=\cdots=s_N=0\)
• for t = 1,2,...,T
  1. \(g_t \leftarrow A\{(x_n,y_n-s_n)\}\)，如果模型\(A\)使用的是二次代价回归函数的话；
  2. 使用基于\(\{(g_t(x_n),y_n-s_n)\}\)的单一变量线性回归计算出\(\alpha_t\)值；
  3. 更新\(s_n\leftarrow s_n+\alpha_t g_t(x_n)\)
• return \(G(x)=\sum_{t=1}^T\alpha_t g_t(x)\)

Gradient Boosting for Regression

有一组数据\((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算法。另外在使用某些其他损失函数时，残差比起负梯度更容易受到异常值的影响。

Random Forest vs GBDT

相同

随机森林和GBDT都属于集成算法，base model都是决策树。

不同

随机森林

随机森林是决策树的bagging。
bagging通过重复对原训练数据集上进行有放回地采样生成的数据集用base model进行训练多次，然后，对于分类求众数，对于回归求平均作为最终结果。
可并行。
随机森林希望单个决策树偏差小、方差大，这样通过\(N\)个决策树的叠加可以减少方差，达到较好的结果。\(N\)越大，泛化能力越好。
随机森林里的树可以是分类树也可以是回归树。

GBDT

GBDT是决策树的boosting。
boosting通过在原训练数据集变化的版本上进行base model的训练，当前base model的训练是基于上一个base model的表现的，然后线性组合起这些base model。
是串行。
GBDT希望单个决策树能力只要好于随机即可，这样通过boosting后就可以降低偏差，达到较好的表现。
树越多，GBDT越可能过拟合。
GBDT的核心在于累加所有树的结果作为最终结果，而分类树的结果显然是没办法累加的，所以GBDT中的树都是回归树，不是分类树。