1. 简单介绍一下XGB
2.XGBoost为什么使用泰勒二阶展开?为什么用二阶信息不用一阶?
3.XGBoost在什么地方做的剪枝,怎么做的?
4.XGBoost如何分布式?特征分布式和数据分布式?各有什么存在的问题?
5.XGBoost里处理缺失值的方法?
6.XGBoost有那些优化?
7.XGBoost如何寻找最优特征?是又放回还是无放回的呢?
8.GBDT和XGBoost的区别是什么?
9.lightgbm和xgboost有什么区别?他们的loss一样么?算法层面有什么区别?
10.比较一下LR和GBDT?GBDT在什么情况下比逻辑回归算法要差?
11.RF和GBDT的区别;RF怎么解决的过拟合问题;
12.怎么理解决策树、xgboost能处理缺失值?而有的模型(svm)对缺失值比较敏感?
13.随机森林是怎样避免ID3算法信息增益的缺点的?
14.gbdt对标量特征要不要onehot编码?
15.CART为什么选择基尼系数作为特征选择标准 ?
16.如何解决类别不平衡问题?
17.GBDT 如何用于分类 ?
1. 简单介绍一下XGB?
Xgboost由很多分类和回归树组成,采用boosting集成学习,集成学习是指用某种策略将多个分类器预测的结果集成起来,作为最终的预测结果,有boost和bagging两种方法(boosting 各分类器之间有依赖关系,bagging各分类器之间没有依赖关系,可并行),boosting分为两种,一种是AdaBoost(自适应增强)(前一个分类器分错/分对的样本的权值会得到加强/降低,加权后的全体样本再次被用来训练下一个基本分类器),一种是GBDT,GBDT的每一次计算都为了减少上一次的残差,进而在负梯度的方向上建立一个新的模型,而XGB采用的就是GBDT的形式,XGB的本质上还是一个GBDT,但是在速度和效率都发挥到了极致。XGB和GBDT比较大的不同就是目标函数的定义,XGB使用泰勒展开来近似目标函数
目标函数分为两个部分:误差函数(logistic损失函数、平方损失函数)和正则化项(定义模型的复杂度)
(叶子结点尽量少,节点数值w不极端)
将目标函数化简之后,目标函数只依赖于一阶导数g和二阶导数h
(将目标函数和正则化项结合化简,对w进行求导,求出最优w,代入目标函数中)
这个分数越小,代表树的结构越好
在构建树的过程中,XGBoost使用贪心+二次优化,从树深度0开始,每一个节点都遍历所有的特征,对每个特征进行分割,选取增益最好的那个特征,增益的计算使用了优化后object中的部分,并且引入了叶子节点的惩罚项。
2.XGBoost为什么使用泰勒二阶展开?为什么用二阶信息不用一阶?
(1)由于之前求最优解的过程只是对平方损失函数进行的,一阶残差,二阶常数,当损失函数是其它函数时,展开就没有这种形式了,为了能够有个统一的形式,使用泰勒二阶展开。为了统一损失函数求导的形式以支持自定义损失函数
(2)二阶信息本身能够让梯度收敛的更快更准确(优化算法中牛顿法证实)可以简单认为一阶导数引导梯度方向,二阶导数引导梯度方向如何变化。
3.XGBoost在什么地方做的剪枝,怎么做的?
(1)目标函数时,使用叶子的数目和w l2模的平方,控制模型的复杂度
(2)在分裂节点的计算增益中,定义了一个阈值,当增益大于阈值才分裂
XGBoost 先从顶到底建立树直到最大深度,再从底到顶反向检查是否有不满足分裂条件的结点,进行剪枝。
4.XGBoost如何分布式?特征分布式和数据分布式?各有什么存在的问题?
XGBoost在训练之前,预先对数据按列进行排序,然后保存block结构。(1)特征分布式/特征间并行:由于将数据按列存储,可以同时访问所有列,那么可以对所有属性同时执行split finding算法,从而并行化split finding(切分点寻找);(2)数据分布式/特征内并行:可以用多个block(Multiple blocks)分别存储不同的样本集,多个block可以并行计算。
问题:(1)不能从本质上减少计算量;(2)通讯代价高。
5.XGBoost里处理缺失值的方法?
xgboost模型却能够处理缺失值,也就是说模型允许缺失值存在。论文中关于缺失值的处理与稀疏矩阵的处理看作一样。在分裂节点的时候不会对缺失值遍历,减少开销。会分别将缺失值分配到左节点和右节点两种情形,计算增益后悬着增益大的方向进行分裂。如果训练期间没有缺失值,预测时候有,自动将缺失值划分到右子树。
6.XGBoost有那些优化?
1、步长,和GBDT一样,XGB也可以加入步长,防止过拟合
2、行、列抽样
3、列排序优化
分裂的时候需要对当前特征进行排序,只需要在初始化时定义一个n*m的矩阵,以后可以通过索引的方式进行
4、缓存优化
原因:使用block结构的缺点:取梯度的时候是通过索引来获得的,非连续的内存访问,使得CPU cache缓存命中率低,影响算法效率
使用缓存预取,每个线程分配一个连续的buffer,读取梯度信息并存入Buffer中(实现了非连续到连续的转化)
5、(近似算法)特征选择优化
贪心算法,当数据量很大的时候,不能全部放入内存,使用近似算法
(1) 如何选取候选切分点Sk={sk1,sk2,⋯skl}呢?
(2) 什么时候进行候选切分点的选取?
可以采用分位数,(简单分位数,采用几分位就将数据平均分为几份)XGB使用二阶导h加权分位数
为什么是h不是g?
采样方式分为两个,一个global模式,一个local模式。
Global模式:每颗树生成前采一次样
Local模式:每次split之后都进行一次采样
7.XGBoost如何寻找最优特征?是又放回还是无放回的呢?
XGBoost在训练的过程中给出各个特征的评分,从而表明每个特征对模型训练的重要性.。XGB属于boosting集成学习方法,样本是不放回的,每轮计算样本不重复。另外,XGB支持子采样,每轮计算不使用全部样本,减少过拟合。XGB支持列采样,提高计算速度又减少过拟合。
8.GBDT和XGBoost的区别是什么?
xgboost类似于gbdt的优化版,不论是精度还是效率上都有了提升。与gbdt相比,具体的优点有:
1.损失函数是用泰勒展式二项逼近,而不是像gbdt里的就是一阶导数
2.对树的结构进行了正则化约束,防止模型过度复杂,降低了过拟合的可能性
3.节点分裂的方式不同,gbdt是用的平方差,xgboost是经过优化推导后的
9.lightgbm和xgboost有什么区别?他们的loss一样么?算法层面有什么区别?
1、 XGB采用level-wise的分裂策略,LGB采用leaf-wise的策略,XGB对每一层所有节点做无差别分裂,但是可能有些节点增益非常小,对结果影响不大,带来不必要的开销。Leaf-wise是在所有叶子节点中选取分裂收益最大的节点进行的,但是很容易出现过拟合问题,所以需要对最大深度做限制
2、 XGB使用近似算法,LGB使用基于立方图的决策算法,histogram算法在内存和计算代价上都有不小的优势。
内存上:
直方图算法的内存消耗为(#data* #features * 1Bytes)(因为对特征分桶后只需保存特征离散化之后的值) xgboost的exact算法内存消耗为:(2 * #data * #features* 4Bytes),因为xgboost既要保存原始feature的值,也要保存这个值的顺序索引,这些值需要32位的浮点数来保存。
计算上:
预排序算法在选择好分裂特征计算分裂收益时,需要遍历所有样本的特征值,时间为(#data), 直方图只需要遍历桶就行,时间为(#data)
3、LGB可以使用直方图做差加速,一个节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到,从而加速计算
4、XGBoost无法直接输入类别型变量,因此需要事先对类别型变量进行编码(例如独热编码);LightGBM可以直接处理类别型变量。
5、但实际上xgboost的近似直方图算法也类似于lightgbm这里的直方图算法,为什么xgboost的近似算法比lightgbm还是慢很多呢?
xgboost在每一层都动态构建直方图, 因为xgboost的直方图算法不是针对某个特定的feature,而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图,而lightgbm中对每个特征都有一个直方图,所以构建一次直方图就够了。
6、LightGBM 与 XGboost 的并行策略
特征并行
LGB特征并行的前提是每个worker留有一份完整的数据集,但是每个worker仅在特征子集上进行最佳切分点的寻找;worker之间需要相互通信,通过比对损失来确定最佳切分点;然后将这个最佳切分点的位置进行全局广播,每个worker进行切分即可。
XGB的特征并行与LGB的最大不同在于XGB每个worker节点中仅有部分的列数据,也就是垂直切分,每个worker寻找局部最佳切分点,worker之间相互通信,然后在具有最佳切分点的worker上进行节点分裂,再由这个节点广播一下被切分到左右节点的样本索引号,其他worker才能开始分裂。
二者的区别就导致了LGB中worker间通信成本明显降低,只需通信一个特征分裂点即可,而XGB中要广播样本索引。
数据并行
当数据量很大,特征相对较少时,可采用数据并行策略。LGB中先对数据水平切分,每个worker上的数据先建立起局部的直方图,然后合并成全局的直方图,采用直方图相减的方式,先计算样本量少的节点的样本索引,然后直接相减得到另一子节点的样本索引,这个直方图算法使得worker间的通信成本降低一倍,因为只用通信以此样本量少的节点。XGB中的数据并行也是水平切分,然后单个worker建立局部直方图,再合并为全局,不同在于根据全局直方图进行各个worker上的节点分裂时会单独计算子节点的样本索引,因此效率贼慢,每个worker间的通信量也就变得很大。
投票并行(LGB)
当数据量和维度都很大时,选用投票并行,该方法是数据并行的一个改进。数据并行中的合并直方图的代价相对较大,尤其是当特征维度很大时。
大致思想是:每个worker首先会找到本地的一些优秀的特征,然后进行全局投票,根据投票结果,选择top的特征进行直方图的合并,再寻求全局的最优分割点。
10. 比较一下LR和GBDT?GBDT在什么情况下比逻辑回归算法要差?
1、LR是线性模型,具有很好的解释性,很容易并行化,处理亿条训练数据不是问题,但是学习能力有限,需要大量的特征工程;GBDT可以处理线性和非线性的数据,具有天然优势进行特征组合
2、LR可以很好的利用正则化解决稀疏性问题(lr 等线性模型的正则项是对权重的惩罚,也就是 W1一旦过大,惩罚就会很大,进一步压缩 W1的值,使他不至于过大,而树模型则不一样,树模型的惩罚项通常为叶子节点数和深度等,而我们都知道,对于上面这种 case,树只需要一个节点就可以完美分割9990和10个样本,惩罚项极其之小)
11.RF和GBDT的区别;RF怎么解决的过拟合问题;
相同点:都是由多棵树组成,最终的结果都是由多棵树一起决定。
不同点:
组成随机森林的树可以分类树也可以是回归树,而GBDT只由回归树组成
组成随机森林的树可以并行生成,而GBDT是串行生成
随机森林的结果是多数表决表决的,而GBDT则是多棵树累加之和
随机森林对异常值不敏感,而GBDT对异常值比较敏感
随机森林是减少模型的方差,而GBDT是减少模型的偏差
随机森林不需要进行特征归一化,而GBDT则需要进行特征归一化
12. 怎么理解决策树、xgboost能处理缺失值?而有的模型(svm)对缺失值比较敏感?
https://www.zhihu.com/question/58230411
决策树(随机森林)(1)使用对应类别中位数(数值)和出现次数最多的数(描述型变量)代替(2)也是中位数和出现次数最多的数进行替换,引入了权重(替换数据和其它数据的相似度计算)
第二种效果好,但是费时,所以一般工具包不提供补全功能,影响工具包效率
XGB上面有
涉及到距离度量的模型,当缺失值处理不当会导致效果很差(KNN,SVM)
数据量很小,用朴素贝叶斯
数据量适中或者较大,用树模型,优先 xgboost
数据量较大,也可以用神经网络
避免使用距离度量相关的模型,如KNN和SVM
13. 随机森林是怎样避免ID3算法信息增益的缺点的?
首先说下信息增益的过程,决策树算法本质上就是要找出每一列的最佳划分以及不同列划分的先后顺序及排布。信息增益的缺点是比较偏向选择取值多的属性。而gini系数每次都是二分,所以跟属性多少没有关系。
14. gbdt对标量特征要不要onehot编码?
我们已知的处理category特征的方法细分有3类。
(1) 转化成数值型
比如[“low”,“middle”,“high”],映射成[1,2,3],某种程度上是合理的,因为确实有大小关系。
再比如[‘red’,‘green’,‘blue’],映射成 [1,2,3],就不太合理
(2) 直接作为category特征
比如颜色的feature,就是有[‘red’,‘green’,‘blue’]三种取值,那么在Mart中做分裂时,是用 (属于“red”) / (不属于“red”) 来进行划分并计算对应的gain,这和连续值的做法有明显区别。
(3) 使用one-hot encoding
扩展成3个feature,[f_red, f_green, f_blue],每个feature的取值是{0,1},在Mart中分裂时当做连续特征来做,因此分裂值可以是0.5,对于某个sample,如果它的f_red是1,那么其它2位feature必然是0,因此在f_red上分裂,等价于2中用 (属于“red”) / (不属于“red”) 来分裂。
综上,从效果的角度来讲,2和3是等价的,所不同的是2的feature空间更小。微软在lightGBM的文档里也说了,category特征可以直接输入,不需要one-hot编码,准确度差不多,速度快8倍。而sklearn的tree方法在接口上不支持category输入,所以只能用one-hot编码。
15. CART为什么选择基尼系数作为特征选择标准 ?
基尼指数的意义是从数据集D中随机抽取两个样本类别标识不一致的概率。基尼指数越小,数据集的纯度越高。相比于信息增益,信息增益比等作为特征选择方法,基尼指数省略了对数计算,运算量比较小,也比较容易理解。
16. 如何解决类别不平衡问题?
1、 对大类进行欠采样(减少数据,或者分成不同数据集,使用多个模型),对小类进行过采样(重复使用数据)
2、 阈值调整,将默认的0.5调整成 较少类别/(较少+较多)
3、 设置不同的学习率,大类权值小,小类权值大
4、 使用一些对样本分布不敏感的评价指标F1、AUC等
5、 可以尝试不同的算法,决策树(对不平衡数据表现不错),集成算法
6、 可以对模型进行惩罚,增加正则项
7、 如果小类很小,可将问题转化为异常点检测
17. GBDT 如何用于分类 ?
https://www.cnblogs.com/always-fight/p/9400346.html
GBDT无论用于分类还是回归一直使用的CART回归树。假设样本X总共有K = 3类[0,1,0],针对样本X每个可能的类都训练一个分类回归树,每轮训练中同时训练K = 3课树,对于每棵树预测值
使用softmax来产生概率
————————————————