文章目录

概述

基本推导和理论还是以看李航老师的《统计学习方法》为主。
各种算法的原理，推荐理解到可以手撕的程度。
以下为通过网络资源搜集整理的一些问题及答案，准备的有些仓促，没能记录所有资料的来源（侵删）

决策树笔记

https://download.csdn.net/download/yolohohohoho/10973332

随机森林优缺点

随机森林优点
1、在当前的很多数据集上，相对其他算法有着很大的优势，表现良好
2、它能够处理很高维度（feature很多）的数据，并且不用做特征选择
3、在训练完后，它能够给出哪些feature比较重要
4、 在创建随机森林的时候，对generlization error使用的是无偏估计，模型泛化能力强
5、训练速度快，容易做成并行化方法，训练时树与树之间是相互独立的
6、 在训练过程中，能够检测到feature间的互相影响
7、 实现比较简单
8、 对于不平衡的数据集来说，它可以平衡误差。
1）每棵树都选择部分样本及部分特征，一定程度避免过拟合；
2）每棵树随机选择样本并随机选择特征，使得具有很好的抗噪能力，性能稳定；
对缺失值不敏感，如果有很大一部分的特征遗失，仍可以维持准确度
随机森林有out of bag，不需要单独换分交叉验证集
。
随机森林缺点：
1） 参数较复杂；
2） 模型训练和预测都比较慢。
3) 不适合小样本，只适合大样本。

GBDT的原理， 如何做分类和回归

首先明确一点，gbdt 无论用于分类还是回归一直都是使用的CART 回归树。不会因为我们所选择的任务是分类任务就选用分类树，这里面的核心是因为gbdt 每轮的训练是在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值 。这个要求每轮迭代的时候，弱分类器的输出的结果相减是有意义的。残差相减是有意义的。
如果选用的弱分类器是分类树，类别相减是没有意义的。上一轮输出的是样本 x 属于 A类，本一轮训练输出的是样本 x 属于 B类。 A 和 B 很多时候甚至都没有比较的意义，A 类- B类是没有意义的。
我们仿照多分类的逻辑回归 ，使用softmax 来产生概率

GBDT分类树拟合的是什么

利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树。GBDT 每轮迭代的时候，都去拟合损失函数在当前模型下的负梯度。

GBDT+ LR 是怎么做的

主要思想：GBDT 每棵树的路径直接作为 LR 输入特征使用。
https://blog.csdn.net/lilyth_lilyth/article/details/48032119
https://www.deeplearn.me/1797.html

CART分类回归树和ID3以及C4.5有什么区别

ID3最大信息熵增益”选取当前最佳的特征来分割数据. 采用的信息增益度量存在一个缺点，它一般会优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益?(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大).

C4.5中是用信息增益比率(gain ratio)来作为选择分支的准则。信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的Feature。除此之外，C4.5还弥补了ID3中不能处理特征属性值连续的问题。但是，对连续属性值需要扫描排序，会使C4.5性能下降

CART回归树用平方误差最小化准则，分类树用基尼指数最小化准则

决策树的优点和缺点
  • 优点：
  1. 决策树算法中学习简单的决策规则建立决策树模型的过程非常容易理解，
  2. 决策树模型可以可视化，非常直观
  3. 应用范围广，可用于分类和回归，而且非常容易做多类别的分类
  4. 能够处理数值型和连续的样本特征
  • 缺点：
  1. 很容易在训练数据中生成复杂的树结构，造成过拟合（overfitting）。剪枝可以缓解过拟合的负作用，常用方法是限制树的高度、叶子节点中的最少样本数量。
  2. 学习一棵最优的决策树被认为是NP-Complete问题。实际中的决策树是基于启发式的贪心算法建立的，这种算法不能保证建立全局最优的决策树。Random Forest 引入随机能缓解这个问题
RF, GBDT, XGBOOST, XGB的区别

GBDT和随机森林的相同点：
1、都是由多棵树组成
2、最终的结果都是由多棵树一起决定
GBDT和随机森林的不同点：
1、组成随机森林的树可以是分类树，也可以是回归树；而GBDT只由回归树组成
2、组成随机森林的树可以并行生成；而GBDT只能是串行生成
3、对于最终的输出结果而言，随机森林采用多数投票等；而GBDT则是将所有结果累加起来，或者加权累加起来
4、随机森林对异常值不敏感，GBDT对异常值非常敏感
5、随机森林对训练集一视同仁，GBDT是基于权值的弱分类器的集成
6、随机森林是通过减少模型方差提高性能，GBDT是通过减少模型偏差提高性能

Xgboost是GB算法的高效实现，xgboost中的基学习器除了可以是CART（gbtree）也可以是线性分类器（gblinear）。
　　(1). xgboost在目标函数中显示的加上了正则化项，基学习为CART时，正则化项与树的叶子节点的数量T和叶子节点的值有关。
　　(2). GB中使用Loss Function对f(x)的一阶导数计算出伪残差用于学习生成fm(x)，xgboost不仅使用到了一阶导数，还使用二阶导数。
　　(3). 上面提到CART回归树中寻找最佳分割点的衡量标准是最小化均方差，xgboost寻找分割点的标准是最大化，lambda，gamma与正则化项相关。
参见https://blog.csdn.net/timcompp/article/details/61919851

改变随机森林的训练样本数据量，是否会影响到随机森林学习到的模型的复杂度

https://zhuanlan.zhihu.com/p/29114739
默认参数下模型复杂度是：O(MNlog(N)) ， 其中 M 是树的数目， N 是样本数。
其中 M 是树的数目， N 是样本数。可以通过设置以下参数来降低模型复杂度： min_samples_split , min_samples_leaf , max_leaf_nodes 和 max_depth 。

Time complexity for building a complete unpruned decision tree is O( v * n log(n) ), where n is the number of records and v is the number of variables/attributes.
Since we would only use mtry variables at each node the complexity to build one tree would be O( mtry * n log(n) )
Now for building a random forest with ntree number of trees, the complexity would be O( ntree * mtry * nlog(n) ) say you restrict the maximum depth of your tree to be “d” then the complexity calculations can be simplified to: O( ntree * mtry * d * n)
Note. The above calculations are ignoring the complexity involved for random selection of variables that needs to be done at each node. I believe this would add an additional O( v * d * ntree)

树集成模型有哪几种形式？

bagging和boosting

随机森林的随机体现在哪方面

  • 在机器学习中，随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。随机森林的随机性体现在每颗树的训练样本是随机的，树中每个节点的分裂属性集合也是随机选择确定的。有了这2个随机的保证，随机森林就不会产生过拟合的现象了。

  • random forest 确实是一个不会overfitting的模型。主要依靠了其中三个随机过程，即产生决策树的样本是随机生成，构建决策树的特征值是随机选取，树产生过程中裂变的时候是选择N个最佳方向中的随机一个裂变的。当随机森林产生的树的数目趋近无穷的时候，理论上根据大数定理可以证明训练误差与测试误差是收敛到一起的。

    https://www.applysquare.com/topic-cn/TKfPL4L4y/

决策树处理连续值的方法。

二分法切分点

决策树如何防止过拟合，过拟合的标志有哪些？

Early Stopping
• 限制树的深度：当达到设置好的最大深度的时候结束；
• 分类误差法：当继续展开无法得到可观的分类误差减小，结束；
• 叶子节点最小数据量限制：一个结点的数据量过小，结束
early stopping的缺点：以异或为例，说明只有分到最后才能达到理想效果，但是early stopping过早结束。

Pruning剪枝；

训练集误差越来越小，true error却先变小后变大，我们就说发生了过拟合（overfitting）
测试机误差大