一、决策树（类型、节点特征选择的算法原理、优缺点、随机森林算法产生的背景）
1、分类树和回归树
由目标变量是离散的还是连续的来决定的；目标变量是离散的，选择分类树；反之（目标变量是连续的，但自变量可以是分类的或数值的），选择回归树；
树的类型不同，节点分裂的算法和预测的算法也不一样；
分类树会使用基于信息熵或者gini指数的算法来划分节点，然后用每个节点的类别情况投票决定预测样本的分类；回归树会使用最大均方误差来划分节点，然后用每个节点中样本的均值作为测试样本的预测值；
2、决策树的算法：ID3、C4.5和CART
CART(Classify and regresion tree)算法既可以生成分类树，也可以生成回归树，但它生成的是二叉树；既可以处理连续变量也可以处理离散变量；对于分类树使用gini不纯度来决定划分节点，对于回归树使用最小误差准则来划分节点；CART的树特点是可以不断生长，需要进行剪枝；
思想：递归地将输入空间分割成矩形
优点：可以进行变量选择，可以克服missing data，可以处理混合预测
缺点：不稳定
ID3是用信息增益来决定划分节点，只能处理离散变量；ID3会对特征取值较多的特征有所偏好（比如ID号），但这是没有意义的；
C4.5是用信息增益率来决定划分节点，可以处理连续值（用二分法进行离散化）；可以处理缺省值；而且C4.5克服了ID3一个重要缺点，它对于取值较多的特征有一个惩罚抑制；或者说它对取值较少的特征有所偏好；但它的算法性能较低；可以与ID3结合优势互补来进行一些效果和性能的优化；
3、决策树是如何选择分裂节点的？
MeanDecreaseAccuracy 和 MeanDecreaseGini
因为用”平均精度下降”衡量特征重要性时，是通过随机扰动每个变量（特征）值来看其整体最后的预测误差的，也就是说，除了被扰动的那个特征外，剩余的特征没有变化，用这种方法造成的最终结果的预测误差来衡量这个被扰动特征的重要性；
GINI指数是衡量节点特征纯度的指标，”gini值平均降低量表示所有树的变量分割节点平均减小的不纯度”；gini指数是决策树节点分割中除了信息熵以外的另一个衡量特征重要性的指标；它表示数据集在增加了特征A的作用之后，gini指数的增益值最大，所以选择A属性作为分裂节点；
二、随机森林
1、为什么叫”随机”？
随机森林里的每一棵决策树的建立，不仅对样本进行有放回（bootstrap）的随机抽样，还对特征进行随机抽样；（即”行”抽样，和”列”抽样，是否回放，是可以设定的）
从原始输入的N个样本中每次抽取k个样本作为特征子集，建立m棵分类决策树；抽多少次就建多少棵决策树；
每次抽样样本的size和原始输入样本的大小相同，因为是放回抽样，所以有可能抽到重复的；这可以保证有重复样本被不同决策树分类，这样就可以对不同决策树的分类能力做个评价。
特征的随机抽样是指，在建每棵树进行每个节点分裂的时候，都随机抽一部分特征，然后在这随机抽的部分特征里面，用决策树的特征选择的方法（比如信息增益，或信息增益率）来决定使用最优的特征来作为分裂节点的；
2、随机森林算法的优缺点
优点：
（1）分类结果准确性高：
使用多棵决策树的投票结果来决定随机森林分类器最终的分类判定结果；
所谓”林子大了，什么鸟都有”。由于建立的多棵决策树中，有不少是随机的效果不好的决策树，但也有少数非常优秀的决策树，在对每个样本的投票结果中，不好的树它们的投票是接近随机的，所以他们的投票被相互抵消；最后剩下”优秀”的决策树的投票结果决定了随机森林分类器的最终输出结果，这样的结果提高了准确性的同时，也提高了模型的泛化能力；（The more random, the more robust.）
随机森林算法的”妙处”恰恰在于”随机”大法的强大，上面说的每个节点都从随机选的部分特征里面选best split的方法或许会使得某些表现”好”的特征被多棵树选中，最终导致有的树很像（虽然它们的训练样本不一样），这样就不够”随机”了，所以有的使用者会在branching的时候（也就是选择划分节点的特征的时候）再加一个随机的处理过程，这样增加算法的稳定性；
（2）自带特征筛选机制：
因为”随机化”增加了RF算法的包容性，它可以更方便地处理高维特征而不需要预先进行特征筛选；相反，它可以是进行特征筛选步骤的一种手段；
3、随机森林是如何衡量特征的重要性的？
在随机森林中某个特征X的重要性的 计算方法如下：
（2） 随机地对袋外数据OOB所有样本的特征X加入噪声干扰(就可以随机的改变样本在特征X处的值),再次计算它的袋外数据误差,记为 errOOB2.
（3）假设随机森林中有Ntree棵树,那么对于 特征X的重要性=∑(errOOB2-errOOB1)/Ntree,之所以可以用这个表达式来作为相应特征的重要性的度量值是因为：若给某个特征随机加入噪声之后,袋外的准确率大幅度降低,则说明这个特征对于样本的分类结果影响很大,也就是说它的重要程度比较高。
参考：http://www.cnblogs.com/justcxtoworld/p/3447231.html
所以可以认为这个特征重要性的衡量是考虑了特征之间的相互作用；跟tf-idf或者t-test，chi-square-test这些单变量分析的方法有很大不同；但这个优化是在权重值的计算层面的，并没有对特征进行什么改造；
但是又不像LDA、word2vec那样，考虑了上下文的语义关系以及情感分析（即没有考虑近义词和由于和其他重要词组合而出现的情感的褒贬），RF的特征选择是无序的bagging考虑的方法（不考虑词出现的先后顺序和语义层面的关系）；
RF的特征筛选并没有对特征进行组合加工或者其他变换（这点不如逻辑回归），同时没有加入近义词的考虑；因此在特征工程上面，这里还有很多优化的空间。详细参见后续的文章。
4、与其他集成分类器的区别和共同点（bagging,Adaboosting,GBDT）？
随机森林与以决策树作为基本分类器的bagging算法相比，其相同点是两者都使用bootstrap的方法对样本进行有放回的抽样；
但不同之处在于随机森林除了对样本进行随机抽样，还对特征进行随机抽样；而bagging算法的特点是它里面可以用不同的方法来构建分类器，不仅仅局限于决策树；
5、随机森林是如何衡量每棵树在最终决策时的权重的？
权重树随机森林算法，采用决策树在其袋外数据上的AUC衡量决策树的分类能力，根据每棵树的分类能力对树分配其在最终决策时的权重，采用权重集成方法对决策树进行组合。
三、具体实现过程
具体实现过程如下：
（1）原始训练集为N，应用bootstrap法有放回地随机抽取k个新的自助样本集，并由此构建k棵分类树，每次未被抽到的样本组成了k个袋外数据；
（2）设有mall个变量，则在每一棵树的每个节点处随机抽取mtry个变量(mtry<< mall)，然后在mtry中选择（用节点划分的方法）一个最具有分类能力的变量，变量分类的阈值通过检查每一个分类点确定；
（3）每棵树最大限度地生长, 不做任何修剪；
（4）将生成的多棵分类树组成随机森林，用随机森林分类器对新的数据进行判别与分类，分类结果按树分类器的投票多少而定。
参考：http://www.jianshu.com/p/c4bcb2505360
四、GBDT
1、回归树、提升树和梯度提升树
（1）回归树
gbdt中的树是回归树，不是决策树，用来做回归预测，调整后也可以用于分类；
回归树分支时穷举每一个feature的每一个阈值寻找最好的分割点，衡量好坏的标准不是最大熵，而是最小化平方误差；
（2）提升树
迭代多棵回归树来共同决策；
参考：http://www.jianshu.com/p/005a4e6ac775
2、boosting和bagging算法的区别
随机森林将多棵决策树的结果进行加权后得到最终的结果，对不同的样本的重要性并没有区分，对不同的树的训练结果也没有做进一步的优化提升，是一种bagging的思想。
GBDT则是基于boosting的思想。
boosting算法是在迭代的每一步构建弱学习器来弥补原有模型的不足。
其中，adaboost通过给被已有模型预测错误的样本更高的权重，使得先前被学习错误的样本可以在后续的训练中得到更高的关注来弥补原有模型的不足；gradient boost则是通过每次迭代的时候构建一个沿梯度下降最快的方向的学习器来弥补模型的不足。
经典的AdaBoost算法只能处理采用指数损失函数的二分类学习任务，而梯度提升方法通过设置不同的可微损失函数可以处理各类学习任务（多分类、回归、Ranking等），应用范围大大扩展。
另一方面，AdaBoost算法对异常点（outlier）比较敏感，而梯度提升算法通过引入bagging思想、加入正则项等方法能够有效地抵御训练数据中的噪音，具有更好的健壮性。
参考：http://www.jianshu.com/p/005a4e6ac775
3、GBDT构造新特征（组合特征）的思想
参考：http://breezedeus.github.io/2014/11/19/breezedeus-feature-mining-gbdt.html#fnref:fbgbdt
4、GBDT是如何衡量特征的重要性的
计算所有的非叶子节点在分裂时加权不纯度的减少，减少得越多说明特征越重要。
不纯度的减少实际上就是该节点此次分裂的收益，因此我们也可以这样理解，节点分裂时收益越大，该节点对应的特征的重要度越高。
5、GBDT的学习算法：
- 算法每次迭代生成一颗新的决策树
- 在每次迭代开始之前，计算损失函数在每个训练样本点的一阶导数g i和二阶导数h i
- 通过贪心策略生成新的决策树，通过等式(7)计算每个叶节点对应的预测值 w ∗j =−G j/(H j +λ). (7)
- 把新生成的决策树f t (x )添加到模型中：y ̂ t i =y ̂ t −1 i +f t (x i )
参考文章：http://blog.csdn.net/yangxudong/article/details/53872141
通常在第四步，我们把模型更新公式替换为：y ̂ t i =y ̂ t −1 i +ϵf t (x i )，其中ϵ称之为步长或者学习率。增加ϵ因子的目的是为了避免模型过拟合。
五、随机森林和GBDT的比较
1、随机森林和GBDT分别在什么情况下容易过拟合？
从生成树的方式的角度看，随机森林是通过随机抽取样本和特征来建立决策树的，因此当数据中有较多缺失值的时候，随机森林的结果容易发生过拟合；而GBDT基于错误样本来建立提升树，当样本中有异常值outlier的时候，GBDT容易发生过拟合；
2、在分布式实现上，随机森林和GBDT哪个的实现更困难？
随机森林的分布式实现更简单，因为在随机森林中每棵树建立的时候与其他的树是独立的，而GBDT每棵树的建立需要依赖于上一层的结果。
Original: https://blog.csdn.net/sinat_23971513/article/details/121655168
Author: sljwy
Title: 用随机森林分类器和GBDT进行特征筛选
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/530692/
转载文章受原作者版权保护。转载请注明原作者出处！