哪些网站做品牌折扣的,什么是软件开发工程师,网站要挂工商标识怎么做,网络营销主要学些什么文章目录 一、GBDT (Gradient Boosting Decision Tree) 梯度提升决策树1.1 回归树1.2 梯度提升树1.3 Shrinkage1.4 调参1.5 GBDT的适用范围1.6 优缺点 二、XGBoost (eXtreme Gradient Boosting)2.1 损失函数2.2 正则项2.3 打分函数计算2.4 分裂节点2.5 算法过程2.6 参数详解2.7… 文章目录 一、GBDT (Gradient Boosting Decision Tree) 梯度提升决策树1.1 回归树1.2 梯度提升树1.3 Shrinkage1.4 调参1.5 GBDT的适用范围1.6 优缺点 二、XGBoost (eXtreme Gradient Boosting)2.1 损失函数2.2 正则项2.3 打分函数计算2.4 分裂节点2.5 算法过程2.6 参数详解2.7 XGBoost VS GBDT 三、LightGBM3.1 LightGBM原理3.2 Lightgbm的一些其它特性 一、GBDT (Gradient Boosting Decision Tree) 梯度提升决策树
GBDT是一种迭代的决策树算法是一种基于boosting增强策略的加法模型,由多棵决策树组成。每次迭代都学习一棵CART树来拟合之前 t − 1 t − 1 t−1 棵树的预测结果与训练样本真实值的残差最终所有树的结论累加起来做最终答案。GBDT在被提出之初就和SVM一起被认为是泛化能力较强的算法。
XGBoost对GBDT进行了一系列优化比如损失函数进行了二阶泰勒展开、目标函数加入正则项、支持并行和默认缺失值处理等在可扩展性和训练速度上有了巨大的提升但其核心思想没有大的变化。
GBDT主要由三个概念组成
Regression Decision Tree即DT)Gradient Boosting即GB)Shrinkage缩减
1.1 回归树
回归树总体流程类似于分类树区别在于回归树的每一个节点都会得到一个预测值。以年龄为例该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点但衡量最好的标准不再是最大熵而是最小化平方误差来找到最可靠的分枝依据。
关于回归树具体可参考CART中对回归树的介绍决策树之CART分类回归树详解 1.2 梯度提升树
提升树是迭代多棵回归树来共同决策。当采用平方误差损失函数时每一棵回归树学习的是之前所有树的结论和残差拟合得到一个当前的残差回归树。残差的意义如公式残差 真实值 - 预测值。 GBDT的核心就在于每一棵树学的是之前所有树结论和的残差这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁但第一棵树的预测年龄是12岁差了6岁即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习如果第二棵树真的能把A分到6岁的叶子节点那累加两棵树的结论就是A的真实年龄如果第二棵树的结论是5岁则A仍然存在1岁的残差第三棵树里A的年龄就变成1岁继续学。 举个例子训练一个提升树模型来预测年龄。简单起见训练集只有4个人A,B,C,D他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练会得到如下图1所示结果 现在我们使用GBDT来训练由于数据太少我们限定叶子节点最多有两个即每棵树都只有一个分枝并且限定只学两棵树。我们会得到如下图2所示结果 在第一棵树分枝和图1一样由于A,B年龄较为相近C,D年龄较为相近他们被分为两拨每拨用平均年龄作为预测值。A,B,C,D的残差分别为-1,1-1,1。然后我们拿残差替代A,B,C,D的原值到第二棵树去学习如果我们的预测值和它们的残差相等则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了。第二棵树只有两个值1和-1直接分成两个节点。此时所有人的残差都是0即每个人都得到了真实的预测值。
A: 14岁高一学生购物较少经常提问题预测年龄A 15 – 1 14 B: 16岁高三学生购物较少经常回答问题预测年龄B 15 1 16 C: 24岁应届毕业生购物较多经常提问题预测年龄C 25 – 1 24 D: 26岁工作两年员工购物较多经常回答问题预测年龄D 25 1 26 为什么要用梯度提升决策树 我们发现图1为了达到100%精度使用了3个feature上网时长、时段、网购金额其中分枝“上网时长1.1h” 很显然已经过拟合了。用上网时间是不是1.1小时来判断所有人的年龄很显然是有悖常识的相对来说图2的boosting虽然用了两棵树但其实只用了2个feature就搞定了后一个feature是问答比例显然图2的依据更靠谱 Boosting的最大好处在于每一步的残差计算其实变相地增大了分错instance的权重而已经分对的instance则都趋向于0。这样后面的树就能越来越专注那些前面被分错的instance。 那么哪里体现了Gradient呢其实回到第一棵树结束时无论此时的cost function是什么是均方差还是均差只要它以误差作为衡量标准残差向量(-1, 1, -1, 1)都是它的全局最优方向这就是Gradient。 1.3 Shrinkage
Shrinkage(缩减)认为每次走一小步逐步逼近的结果要比每次迈一大步逼近结果更加容易避免过拟合。即它不完全信任每一个棵残差树它认为每棵树只学到了真理的一小部分累加的时候只累加一小部分通过多学几棵树弥补不足。即
没用Shrinkage时yi表示第i棵树上y的预测值 y(1~i)表示前i棵树y的综合预测值
y(i1) 残差(y1~yi) 其中 残差(y1~yi) y真实值 - y(1 ~ i)
y(1 ~ i) SUM(y1, ..., yi)Shrinkage不改变第一个方程只把第二个方程改为
y(1 ~ i) y(1 ~ i-1) step * yi即Shrinkage仍然以残差作为学习目标但对于残差学习出来的结果只累加一小部分step*残差逐步逼近目标。step一般都比较小如0.01~0.001注意该step非gradient的step导致各个树的残差是渐变的而不是陡变的。直觉上这也很好理解不像直接用残差一步修复误差而是只修复一点点其实就是把大步切成了很多小步。
本质上Shrinkage为每棵树设置了一个weight累加时要乘以这个weight但和Gradient并没有关系。这个weight就是step。就像Adaboost一样Shrinkage能减少过拟合发生也是经验证明的目前还没有看到从理论的证明。
1.4 调参
树的个数 100~10000叶子的深度 3~8学习速率 0.01~1叶子上最大节点树 20训练采样比例 0.5~1训练特征采样比例 sqrt(num)
1.5 GBDT的适用范围
该版本GBDT几乎可用于所有回归问题线性/非线性相对logistic regression仅能用于线性回归GBDT的适用面非常广。亦可用于二分类问题设定阈值大于阈值为正例反之为负例。
1.6 优缺点
(1) 优点
精度高能处理非线性数据能处理多特征类型适合低维稠密数据
(2) 缺点
并行麻烦因为上下两颗树有联系多分类的时候 复杂度很大
二、XGBoost (eXtreme Gradient Boosting)
2.1 损失函数
XGBOOST预测函数可表示为
我们使用分部加法可将此式变换为
其中K代表迭代K轮方程左侧为预测值。映射fk如下(其中w为叶子节点的得分q(xi)代表样本值xi 通过函数q(xi)映射到某个叶子节点)
目标函数误差函数正则化 所以目标函数就可变化为 由前面的公式我们知道 我们可以使用泰勒二阶展开 注红色箭头指向的l为损失函数红色方框为正则项包括L1、L2红色圆圈为常数项。xgboost利用泰勒展开做一个近似。最终的目标函数只依赖于每个数据点的在误差函数上的一阶导数和二阶导数。 2.2 正则项
接下来我们使用L2构建正则化函数
xgboost树的复杂度包含了两个部分 (1) 叶子节点的个数T (2) 叶子节点的得分w的L2正则相当于针对每个叶结点的得分增加L2平滑目的是为了避免过拟合
考虑到正则项表达式为
我们可以把之前的目标函数进行如下变形 其中g是一阶导数h是二阶导数。 I j I_j Ij被定义为每个叶节点j上面样本下标的集合 q(xi)要表达的是每个样本值xi 都能通过函数q(xi)映射到树上的某个叶子节点从而通过这个定义把两种累加统一到了一起。
接着我们可以定义 最终公式可以化简为 通过对 w j w_j wj 求导等于0可以得到 然后把 w j w_j wj 最优解代入得到
2.3 打分函数计算
Obj代表了当我们指定一个树的结构的时候我们在目标上面最多减少多少。我们可以把它叫做 结构分数(structure score)。结构分数值越小代表这个树的结构越好。
2.4 分裂节点
对于一个叶子节点如何进行分裂xgboost作者在其原始论文中给出了两种分裂节点的方法 1 枚举所有不同树结构的贪心法 不断地枚举不同树的结构然后利用打分函数来寻找出一个最优结构的树接着加入到模型中不断重复这样的操作。利用枚举法来得到最优树结构集合其结构很复杂所以通常选择贪心法。从树深度0开始每一节点都遍历所有的特征比如年龄、性别等等然后对于某个特征先按照该特征里的值进行排序然后线性扫描该特征进而确定最好的分割点最后对所有特征进行分割后我们选择所谓的增益Gain最高的那个特征。 在之前求出的目标函数表达式中G/(Hλ) 表示着每一个叶子节点对当前模型损失的贡献程度融合一下得到Gain的计算表达式如下所示 其中GL为原叶节点左儿子的误差函数一阶导数之和GL为原叶节点右儿子的误差函数一阶导数之和。 例如分裂点a 但由于又引进了一个新的量复杂度代价所以增益衡量是否引进行的分裂还有一些问题我们可以设置一个阀值小于于阀值不引入新的分裂大于阀值引入新的分裂。
2.5 算法过程
不断地进行特征分裂来生成一棵树。每次添加一棵树其实是学习一个新函数去拟合上次预测的残差。
注 W q ( x ) W_{q(x)} Wq(x)为叶子节点q的分数对应了所有K棵回归树的集合而f(x)为其中一棵回归树。 当我们训练完成得到k棵树我们要预测一个样本的分数其实就是根据这个样本的特征在每棵树中会落到对应的一个叶子节点每个叶子节点就对应一个分数。 最后只需要将每棵树对应的分数加起来就是该样本的预测值。
2.6 参数详解
(1) General Parameters常规参数
booster [defaultgbtree]基分类器。gbtree: tree-based models; gblinear: linear modelssilent [default0]:设置成1则没有运行信息输出最好是设置为0.nthread [default to maximum number of threads available if not set]线程数
(2) Booster Parameters模型参数
eta [default0.3]: shrinkage参数用于更新叶子节点权重时乘以该系数避免步长过大。参数值越大越可能无法收敛。把学习率eta设置得小一些小学习率可以使得后面的学习更加仔细。min_child_weight [default1]:这个参数默认是 1是每个叶子里面h的和至少是多少对正负样本不均衡时的0-1分类而言假设h 在0.01附近min_child_weight为1 意味着叶子节点中最少需要包含100个样本。这个参数非常影响结果控制叶子节点中二阶导的和的最小值该参数值越小越容易overfitting。max_depth [default6]: 每颗树的最大深度树高越深越容易过拟合。max_leaf_nodes: 最大叶结点数与max_depth作用有点重合。gamma [default0]后剪枝时用于控制是否后剪枝的参数。max_delta_step [default0]这个参数在更新步骤中起作用如果取0表示没有约束如果取正值则使得更新步骤更加保守。可以防止做太大的更新步子使更新更加平缓。subsample [default1]样本随机采样较低的值使得算法更加保守防止过拟合但是太小的值也会造成欠拟合。colsample_bytree [default1]列采样对每棵树的生成用的特征进行列采样。一般设置为0.5-1lambda [default1]控制模型复杂度的权重值的L2正则化项参数参数越大模型越不容易过拟合。alpha [default0]:控制模型复杂程度的权重值的 L1 正则项参数参数值越大模型越不容易过拟合。scale_pos_weight [default1]如果取值大于0的话在类别样本不平衡的情况下有助于快速收敛。
(3) Learning Task Parameters学习任务参数 objective [defaultreg:linear]定义最小化损失函数类型常用参数 binary: logistic – logistic regression for binary classification, returns predicted probability (not class)multi: softmax – multiclass classification using the softmax objective, returns predicted class (not probabilities) . You also need to set an additional num_class (number of classes) parameter defining the number of unique classesmulti: softprob – same as softmax, but returns predicted probability of each data point belonging to each class. eval_metric [default according to objective]The metric to be used for validation data. The default values are rmse for regression and error for classification. Typical values are: rmse – root mean square errormae – mean absolute errorlogloss – negative log-likelihooderror – Binary classification error rate (0.5 threshold)merror – Multiclass classification error ratemlogloss – Multiclass loglossauc: Area under the curve seed [default0] The random number seed. 随机种子用于产生可复现的结果
2.7 XGBoost VS GBDT
(1) 传统GBDT以CART作为基分类器xgboost还支持线性分类器这个时候xgboost相当于带L1和L2正则化项的logistic回归分类问题或者线性回归回归问题。
(2) 传统GBDT在优化时只用到一阶导数信息xgboost则对代价函数进行了二阶泰勒展开同时用到了一阶和二阶导数。顺便提一下xgboost工具支持自定义代价函数只要函数可一阶和二阶求导。
(3) xgboost在代价函数里加入了正则项用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲正则项降低了模型的variance使学习出来的模型更加简单防止过拟合这也是xgboost优于传统GBDT的一个特性。
(4) Shrinkage缩减相当于学习速率xgboost中的eta。xgboost在进行完一次迭代后会将叶子节点的权重乘上该系数主要是为了削弱每棵树的影响让后面有更大的学习空间。实际应用中一般把eta设置得小一点然后迭代次数设置得大一点。补充传统GBDT的实现也有学习速率
(5) 列抽样column subsampling。xgboost借鉴了随机森林的做法支持列抽样不仅能降低过拟合还能减少计算这也是xgboost异于传统gbdt的一个特性。
(6) 对缺失值的处理。对于特征的值有缺失的样本xgboost可以自动学习出它的分裂方向。
(7) xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的注意xgboost的并行不是tree粒度的并行xgboost也是一次迭代完才能进行下一次迭代的第t次迭代的代价函数里包含了前面t-1次迭代的预测值。xgboost的并行是在特征粒度上的。我们知道决策树的学习最耗时的一个步骤就是对特征的值进行排序因为要确定最佳分割点。xgboost在训练之前预先对数据进行了排序然后保存为block结构后面的迭代中重复地使用这个结构大大减小计算量。这个block结构也使得并行成为了可能。在进行节点的分裂时需要计算每个特征的增益最终选增益最大的那个特征去做分裂那么各个特征的增益计算就可以开多线程进行。
(8) 可并行的近似直方图算法。树节点在进行分裂时我们需要计算每个特征的每个分割点对应的增益即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下贪心算法效率就会变得很低所以xgboost还提出了一种可并行的近似直方图算法用于高效地生成候选的分割点。
三、LightGBM
3.1 LightGBM原理
传统的boosting算法如GBDT和XGBoost已经有相当好的效率但在效率和可扩展性上不能满足现在的需求主要的原因就是传统的boosting算法需要对每一个特征都要扫描所有的样本点来选择最好的切分点这是非常的耗时。
为了解决这种在大样本高维度数据的环境下耗时的问题Lightgbm使用了如下两种解决办法
GOSSGradient-based One-Side Sampling, 基于梯度的单边采样。不是使用所用的样本点来计算梯度而是对样本进行采样来计算梯度。EFBExclusive Feature Bundling 互斥特征捆绑。不是使用所有的特征来进行扫描获得最佳的切分点而是将某些特征进行捆绑在一起来降低特征的维度使得寻找最佳切分点的消耗减少。 这样大大的降低的处理样本的时间复杂度但在精度上通过大量的实验证明在某些数据集上使用Lightgbm并不损失精度甚至有时还会提升精度。
3.2 Lightgbm的一些其它特性
(1) Leaf-wise的决策树生长策略 大部分决策树的学习算法通过 level-wise 策略生长树即一次分裂同一层的叶子不加区分的对待同一层的叶子。而实际上很多叶子的分裂增益较低没必要进行分裂带来了没必要的开销。如下图
LightGBM 通过 leaf-wise 策略来生长树。每次从当前所有叶子中找到分裂增益最大的一个叶子然后分裂如此循环。因此同Level-wise相比在分裂次数相同的情况下Leaf-wise可以降低更多的误差得到更好的精度。但是当样本量较小的时候leaf-wise 可能会造成过拟合。所以LightGBM 可以利用额外的参数max_depth来限制树的深度并避免过拟合。
(2) 类别特征值的最优分割 对于类别型的数据我们通常将类别特征转化为one-hot编码。 然而对于学习树来说这不是个好的解决方案。原因是对于一个基数较大的类别特征学习树会生长的非常不平衡并且需要非常深的深度才能来达到较好的准确率。
(3)Lightgbm中的并行学习
(3.1) 特征并行
传统的特征并行算法: 旨在于在并行化决策树中的寻找最佳切分点主要流程如下
垂直切分数据不同的Worker有不同的特征集在本地特征集寻找最佳切分点 {特征阈值}在各个机器之间进行通信拿出自己的最佳切分点然后从所有的最佳切分点中推举出一个最好的切分点作为全局的切分点以最佳划分方法对数据进行划分并将数据划分结果传递给其他Worker其他Worker对接受到的数据进一步划分。 传统的特征并行方法主要不足:存在计算上的局限传统特征并行无法加速特征切分时间复杂度为 。 因此当数据量很大的时候难以加速。需要对划分的结果进行通信整合其额外的时间复杂度约为。一个数据一个字节
LightGBM中的特征并行: 不再垂直划分数据即每个Worker都持有全部数据。 因此LighetGBM中没有数据划分结果之间通信的开销各个Worker都知道如何划分数据。 而且样本量也不会变得更大所以使每个机器都持有全部数据是合理的。
LightGBM 中特征并行的流程如下
每个Worker都在本地特征集上寻找最佳划分点特征阈值本地进行各个划分的通信整合并得到最佳划分执行最佳划分。
然而该特征并行算法在数据量很大时仍然存在计算上的局限。因此建议在数据量很大时使用数据并行。
(3.2) 数据并行 传统的数据并行算法
水平划分数据Worker以本地数据构建本地直方图将所有Worker的本地直方图整合成全局整合图在全局直方图中寻找最佳切分然后执行此切分。
传统数据并行的不足高通讯开销。
LightGBM中的数据并行 通过减少数据并行过程中的通讯开销来减少数据并行的开销
不同于传统数据并行算法中的整合所有本地直方图以形成全局直方图的方式LightGBM 使用Reduce scatter的方式对不同Worker的不同特征不重叠的进行整合。 然后Worker从本地整合直方图中寻找最佳划分并同步到全局的最佳划分中。如上面提到的LightGBM 通过直方图做差法加速训练。 基于此我们可以进行单叶子的直方图通讯并且在相邻直方图上使用做差法。
