机器学习知识点相关总结（二）——决策树相关
1.讲一下决策树和随机森林
决策树：是一种对实例进行分类的树形结构，由内部结点和叶节点组成。内部结点表示一个特征或属性，叶节点标识类别。在分类时，从根节点出发，对实例某一特征进行测试，分配到其子节点。如此递归对实例进行测试并分配，直到到达叶节点，分到叶节点的类中。
随机森林：尽管有剪枝等方法，一棵树的生成不如多棵树，解决决策树泛化能力弱的特点。在样本集中bootstrap随机选取n个样本（样本的随机）；在属性中随机选取K个属性（根号N），选择最佳分割属性作为结点建立决策树；重复两个步骤m次，得到m棵决策树。形成随机森林，通过投票表决决定数据属于哪一类。（最大深度不超过8层）
为什么随机森林要取三分之二的样本构建树？
因为每次采样方式为bootstrap方式（有放回的抽样），样本不被抽中的概率为1/e，大约为三分之一，所以每次大约有三分之二的样本被用于构建树。
随机森林没有剪枝的过程，因为前面随机采样的过程已经引入了随机性
2.讲一下GBDT的细节，写出GBDT的目标函数
提出：当损失函数是平方损失函数或者指数函数时，每一步的优化是很直观的；但对于一般的损失函数而言不太容易，梯度提升树就是对于这一问题提出的算法。最关键的是利用损失函数的负梯度作为残差的近似值来拟合决定下一个决策树。
梯度提升树，是一种迭代的决策树算法。Boosting策略的一种集成学习模型。
通过采用加法模型（基函数的线性组合），以及不断减少训练过程产生的残差来达到将数据分类或者回归的算法。通过多伦迭代，每轮迭代产生一个弱分类器，每个分类器在上一轮产生的残差基础上进行训练，通过降低偏差来不断提高分类器的精度。
核心：累加所有回归树的结果作为最终结果。每一棵树学习的是之前所有树结论的残差。
相对于决策树的优点：泛化性能更好。GBDT的最大好处在于，每一步的残差计算其实变相的增大了分错样本的权重，而已经分对的样本则都趋向于0。这样后面就更加专注于那些分错的样本。
GBDT与提升树的区别：残差的计算不同，提升树计算的是真正的残差，gbdt用当前模型的负梯度来拟合残差。
提升树Boosting Tree：
以决策树为基学习器，对分类问题用二叉分类树，回归问题用二叉回归树。
回归问题通过不断拟合残差得到新的树。
3.ID3、C4.5、CART的区别，写信息增益、信息增益率、基尼系数的公式
都是决策树学习常用的算法。
ID3在决策树的各个节点应用信息增益准则选择特性。选择信息增益最大的特征作为结点的特征，递归构建决策树。只有树的生成，容易产生过拟合。倾向于选择水平数量较多的变量，可能导致得到一个数量庞大但是较浅的树，且最后无法处理空值。
C4.5用信息增益比来选择特征。解决了信息增益偏向于选择取值较多的属性。
CART（分类与回归树模型）：对回归树用平方误差最小化准则，分类树用基尼指数最小化准则选择特征。
公式见统计学习方法p62，p69
4.树有几种剪枝的方式，各有什么优缺点
限制树的高度，叶子节点中的最少样本数量
极小化整体损失函数或代价函数
剪纸分为预剪枝和后剪枝，预剪枝是生成过程中，对每个节点在划分前先进行评估，若不能带来泛化性能的提升，则停止划分，将当前节点标记为叶节点。
预剪枝：使得决策树很多分支都没有展开，不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但是可能会给决策树带来欠拟合的风险。
后剪枝：泛化性能往往高于预剪枝，但是训练时间开销往往比较大。
5.Adaboost
是boosting的代表，必须串行化生成的集成学习方法。
工作机制：从初始训练集中学习一个基学习器；根据基学习器的分布对训练样本进行调整，使得分类错误的样本在后续受到更多关注（增加误分类样本的权重，降低正确分类样本的权重）；基于调整后的样本分布训练下一个基学习器；反复，直到基学习器数目达到T，最后进行加权结合。
如何将弱分类器组合成强分类器？
加权多数表决，具体的，加大分类错误率低的分类器的权值，使其在表决中起到较大作用。弱分类器被线性组合成一个强分类器。
只适用于二分类问题。
6.xgboost的gbdt的区别
xgboost加入了正则项，限制模型复杂度，用于避免过拟合，泛化性能更好；（对树的结构进行了正则化约束）
xgboost对损失函数进行了二阶泰勒展开，收敛速度更快，加快优化速度；（二阶导数有利于梯度下降的更快更准）
xgboost还支持线性分类器，线性分类器可以使用L1L2正则化，gbdt只支持cart；
在寻找最佳分割点时，实现了一种近贪心算法，加速和减小内存消耗，而且考虑了稀疏数据集的处理，可以为缺失值指定分支的默认方向；
xgboost支持并行处理
传统gbdt以CART作为基分类器，xgboost还支持线性分类器。
XGBoost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，XGBoost工具支持自定义损失函数，只要函数可一阶和二阶求导。使用牛顿法代替梯度下降法寻找最优解。
XGBoost在目标函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出分数的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是XGBoost优于传统GBDT的一个特性。
XGBoost考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率。（处理缺失值的方式：在训练过程中如果有缺失值，分别分到左右子树计算损失，分到损失比较小的那一边。如果预测时遇到缺失值，则被分到右子树）
（距离度量的相关模型对于缺失值比较敏感——kNN， SVM）
7.adaboost和gbdt区别
都是基于先前模型的表现进行调整。
不同的是ada通过提升错分数据的权重定位模型的不足，gbdt通过计算梯度定位模型的不足，因此gbdt可以使用更多种类的目标函数，儿当目标函数是均方误差时，计算损失函数的负梯度值在当前模型中相当于残差。
8.xgb，lgb，gbdt区别，为什么lgb速度更快
xgboost
lightgbm
gbdt
9.集成学习，boosting与bagging的原理以及异同点
集成学习基本思想：多个学习器组合成一个性能更好的学习器。
为什么有效？不同模型通常会在测试集上产生不同的误差，平均的，集成模型能至少与其任一成员保持一致，并且如果成员的误差是独立的，集成模型将显著比其他成员表现更好。
Bagging：对训练集进行采样，产生若干不同的子集，再从每一个子集中学习一个基学习器。是并行式集成学习方法的代表，在预测输出进行结合时，对于分类问题采用简单投票法，对于回归问题采用简单平均法。基于并行策略，基学习器之间不存在依赖关系，训练每个基学习器只使用到一部分样本（随机森林，dropout策略）。（自助采样法:有放回的采样）
Boosting提升方法：从某个基学习器出发学习一系列基学习器，然后组合成一个强分类器。（改变训练数据的概率分布，针对不同的训练数据分布调用弱学习算法学习一系列弱分类器）。基于串行策略，新的学习器需要依赖旧的学习器生成。每次学习都会用到全部的样本（adaboost，gbdt，提升树）。
10. 树模型的特征选择中除了信息增益、信息增益比、基尼指数这三个外，还有哪些？
根据树的模型不同来选择，ID3,C4.5，CART
回归树可以用均方误差减少量，xgboost用到自定义函数的增益值。
11.为什么使用决策树作为基学习器？
决策树的表达能力和泛化能力，可以通过剪枝快速调整
决策树可以方便地将样本权重整合到训练过程中（适用于boosting）
决策树是一种不稳定的学习器（不稳定是指样本的扰动会对决策树的结果产生较大的影响，适用于bagging）
为什么不稳定的学习器更适合作为基学习器？
不稳定的学习器容易受到样本分布的影响，很好地引入了随机性，有助于在集成学习中提升模型的泛化能力。
还有那些模型也适合用作基学习器?
神经网络，也属于不稳定的学习器。此外，通过调整神经元的数量，网络深度，连接方式初始权重也能很好引入随机性和改变模型的表达能力和泛化能力。
Bagging方法可以使用线性分类器吗？
Bagging不推荐，因为线性分类器属于稳定的学习器，对数据不敏感；甚至可能因为bagging的采样，导致在训练中难以收敛，增大集成分类器的偏差。
Boosting方法可以，boosting主要听过减低偏差的方式来提升性能，xgboost中就支持以线性分类器作为基学习器。
12.lightGBM 微软
针对xgboost的缺点：每轮迭代时都需要遍历整个训练集很多次，预排序算法时间空间开销大
lightgbm特点：
基于histogram（柱状图）的决策树算法：先把连续的浮点特征值离散成k个整数，构造一个宽度为k的直方图，遍历数据时，根据离散化的值作为索引在直方图中累计统计量。根据直方图的离散值，遍历寻找最优分割点。
带深度限制的leaf-wise叶子生长策略：每次从当前所有叶子中，寻找分裂增益最大的一个叶子然后分裂。分裂次数相同的情况下，可以降低更多的误差，达到更好的精度。但可能会长出较深的决策树，容易过拟合。增加最大层数限制。
（level-wise不加区分地对待同一层的叶子，可以同时分裂同一层的叶子，但是很多叶子分裂增益很小，造成没必要的开销。）
13.树模型与LR模型的对比
树模型收敛的更快，且通常误差比lr比较小
线性模型是所有特征给予一个权重相加得到一个新的值，树模型是一个一个特征进行处理
样本中存在缺失值时，可以选择LR模型
逻辑回归只能找到线性分割，树模型可以找到非线性分割（树模型拟合出来的函数其实是分区间的阶梯函数）。
14.xgboost为什么使用二阶泰勒展开？
二阶导数有利于梯度下降更快更准确。使用泰勒展开去的函数做自变量的二阶导数形式，可以在不选定损失函数的情况下，仅仅依靠输入的值就可以进行椰子分裂优化计算，本质上把损失函数的选取和模型算法的优化分开了。这种去耦合增加了xgboost的适用性，使得他按需选择损失函数，即可用于分类，也可以用于回归。
Xgboost如何寻找最优特征？
在训练过程中给出各个特征的增益评分，最大增益的特征会被选出来作为分裂依据，从而记忆了每个特征对在模型训练时的重要性。
样本是无放回的，每轮计算样本不重复