2015微信网站,网络安全行业前景,大连公司注册,海淀搜索引擎优化seo树模型集成学习
集成学习主要有两个思想#xff0c;分别是bagging和boosting。树模型的集成模型都是使用树作为基模型#xff0c;最常用的cart树#xff0c;常见的集成模型有RandomForest、GBDT、Xgboost、Lightgbm、Catboost。
概要介绍
RandomForest
随机森林(Random …树模型集成学习
集成学习主要有两个思想分别是bagging和boosting。树模型的集成模型都是使用树作为基模型最常用的cart树常见的集成模型有RandomForest、GBDT、Xgboost、Lightgbm、Catboost。
概要介绍
RandomForest
随机森林(Random Forest,RF)是Bagging的一个扩展变体。RF在以决策树为基学习器构建Bagging集成的基础上进一步在决策树的训练过程中引入了随机属性选择。既然模型叫做随机森林森林我们可以理解为是多棵树的集合就是森林随机主要有两个点进行有放回的采样
每次建树特征个数随机选择每次建树样本个数随机选择
随机森林中基学习器的多样性不仅来自样本扰动还来自属性扰动这就使得最终集成得泛化性能可通过个体学习器之间差异度得增加而进一步提升。使得模型更加鲁棒。
GBDT
GBDT使用的是加法模型和前向分布算法而AdaBoost算法是前向分布加法算法的特例前向分布算法是加法模型当基函数为基本分类器时该加法模型等价于Adaboost的最终分类器。 GBDT也是迭代使用了前向分布算法但是弱学习器限定了只能使用CART回归树模型同时迭代思路和Adaboost也有所不同。在GBDT的迭代中假设我们前一轮迭代得到的强学习器是, 损失函数是, 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器让本轮的损失函数最小。也就是说本轮迭代找到决策树要让样本的损失尽量变得更小。GBDT本轮迭代只需拟合当前模型的残差。
Xgboost
Xgboost是gbdt的改进或者说是梯度提升树的一种Xgb可以说是工程上的最佳实践模型简单的说xgbgbdt二阶梯度信息随机特征和样本选择特征百分位值加速空值特征自动划分。还有必要的正则项和最优特征选择时的并行计算等。
Lightgbm
首先GBDT是一个非常流行的机器学习算法另外基于GBDT实现的XGBoost也被广泛使用。但是当面对高纬度和大数据量时其效率和可扩展性很难满足要求。主要的原因是对于每个特征我们需要浏览所有的数据去计算每个可能分裂点的信息增益真是非常耗时的。基于此提出了两大技术Gradient-based One-Side Sampling (GOSS) and Exclusive Feature Bundling (EFB).
## catboost CatBoost Category Boosting. 2017年7月21日俄罗斯Yandex开源CatBoost亮点是在模型中可直接使用Categorical特征并减少了tuning的参数。
核心公式 gbdt的前向分布公式 f m ( x ) f m − 1 ( x ) β m b ( x ; γ m ) (1) f_m(x)f_{m-1}(x)\beta_m b(x;\gamma_m) \tag{1} fm(x)fm−1(x)βmb(x;γm)(1) gbdt的第m轮的扶梯度公式 − [ ∂ L ( y , f ( x i ) ) ∂ f ( x i ) ] f ( x ) f m − 1 ( x ) (2) -\left[ \frac{\partial L(y,f(x_i))}{\partial f(x_i)} \right]_{f(x)f_{m-1}(x)} \tag{2} −[∂f(xi)∂L(y,f(xi))]f(x)fm−1(x)(2) gbdt格式化损失函数 L ( y , f m ( x ) ) L ( y , f m − 1 ( x ) β m b ( x ; γ m ) ) (3) L(y,f_m(x))L(y,f_{m-1}(x)\beta_m b(x;\gamma_m)) \tag{3} L(y,fm(x))L(y,fm−1(x)βmb(x;γm))(3) 泰勒展开式 若函数fx在包含x0的某个闭区间[a,b]上具有n阶导数且在开区间a,b上具有n1阶导数则对闭区间[a,b]上任意一点x成立下式 f ( x ) f ( x 0 ) f ′ ( x 0 ) ( x − x 0 ) f ′ ′ ( x 0 ) 2 ! ( x − x 0 ) 2 . . . f ( n ) ( x 0 ) n ! ( x − x 0 ) n R n ( x ) (4) f(x)f(x_0)f(x_0)(x-x_0)\frac{f(x0)}{2!}(x-x_0)^2 ... \frac{f^{(n)}(x_0)}{n!}(x-x_0)^nR_n(x) \tag{4} f(x)f(x0)f′(x0)(x−x0)2!f′′(x0)(x−x0)2...n!f(n)(x0)(x−x0)nRn(x)(4) f ( x Δ x ) f ( x ) f ′ ( x ) Δ x 1 2 ! f ′ ′ ( x ) Δ x 2 . . . 1 n ! f ( n ) ( x ) Δ x n R n ( x ) (5) f(x\Delta x)f(x)f(x)\Delta x \frac{1}{2!}f(x)\Delta x^2...\frac{1}{n!}f^{(n)}(x)\Delta x^nR_n(x) \tag{5} f(xΔx)f(x)f′(x)Δx2!1f′′(x)Δx2...n!1f(n)(x)ΔxnRn(x)(5) 其中 R n ( x ) R_n(x) Rn(x)是 ( x − x 0 ) n 的高阶无穷小 . (x-x_0)^n的高阶无穷小. (x−x0)n的高阶无穷小. xgboost的目标公式(t轮迭代) o b j ( t ) ∑ i 1 n l ( y i , y ^ i t ) ∑ i 1 t Ω ( f i ) (6) obj^{(t)}\sum_{i1}^{n}l(y_i,\hat{y}_i^t)\sum_{i1}^{t}\Omega(f_i) \tag{6} obj(t)i1∑nl(yi,y^it)i1∑tΩ(fi)(6) ∑ i 1 n l ( y , y ^ i ( t − 1 ) f t ( x i ) ) Ω ( f t ) c o n s t a n t (7) \sum_{i1}^{n}l(y,\hat y_{i}^{(t-1)}f_t(x_i))\Omega(f_t)constant \tag{7} i1∑nl(y,y^i(t−1)ft(xi))Ω(ft)constant(7) xgboost损失函数的泰勒二阶展开 l ( t ) ≂ ∑ i 1 n [ l ( y i , y ^ ( t − 1 ) ) g i f t ( x i ) 1 2 h i f t 2 ( x i ) ] Ω ( f t ) (8) l^{(t)} \eqsim \sum_{i1}^{n}[l(y_i,\hat y ^{(t-1)})g_i f_t(x_i) \frac{1}{2}h_i f_t^2(x_i)]\Omega(f_t) \tag{8} l(t)≂i1∑n[l(yi,y^(t−1))gift(xi)21hift2(xi)]Ω(ft)(8) 其中 l ( y i , y ^ ( t − 1 ) ) l(y_i,\hat y ^{(t-1)}) l(yi,y^(t−1))是常数 g i ∂ y ^ ( t − 1 ) l ( y i , y ^ ( t − 1 ) ) g_i\partial_{\hat{y}^{(t-1)}}l(y_i, \hat{y}^{(t-1)}) gi∂y^(t−1)l(yi,y^(t−1)), h i ∂ y ^ ( t − 1 ) 2 l ( y i , y ^ ( t − 1 ) ) h_i\partial_{\hat{y}^{(t-1)}}^2l(y_i, \hat{y}^{(t-1)}) hi∂y^(t−1)2l(yi,y^(t−1)). 常数对目标函数的优化不相关于是可以将目标函数转化为如下: l ( t ) ∑ i 1 n [ g i f t ( x i ) 1 2 h i f t 2 ( x i ) ] Ω ( f t ) (9) l^{(t)} \sum_{i1}^{n}[g_i f_t(x_i) \frac{1}{2}h_i f_t^2(x_i)]\Omega(f_t) \tag{9} l(t)i1∑n[gift(xi)21hift2(xi)]Ω(ft)(9) ∑ i 1 n [ g i f t ( x i ) 1 2 h i f t 2 ( x i ) ] λ T 1 2 ∑ j 1 T ω j 2 (10) \sum_{i1}^{n}[g_i f_t(x_i) \frac{1}{2}h_i f_t^2(x_i)]\lambda T\frac{1}{2}\sum_{j1}^{T}\omega_j^2 \tag{10} i1∑n[gift(xi)21hift2(xi)]λT21j1∑Tωj2(10) ∑ j 1 T [ ( ∑ i ∈ I j g i ) ω j 1 2 ( ∑ i ∈ I j h i ) ω j 2 ] λ T 1 2 ∑ i 1 T ω j 2 (11) \sum_{j1}^{T}[(\sum_{i \in I_j}g_i) \omega_j \frac{1}{2}(\sum_{i \in I_j}h_i) \omega_j^2] \lambda T \frac{1}{2}\sum_{i1}^{T} \omega_j^2 \tag{11} j1∑T[(i∈Ij∑gi)ωj21(i∈Ij∑hi)ωj2]λT21i1∑Tωj2(11) ∑ i 1 n [ g i f t ( x i ) 1 2 h i f t 2 ( x i ) ] λ T 1 2 ∑ j 1 T ω j 2 (12) \sum_{i1}^{n}[g_i f_t(x_i) \frac{1}{2}h_i f_t^2(x_i)]\lambda T\frac{1}{2}\sum_{j1}^{T}\omega_j^2 \tag{12} i1∑n[gift(xi)21hift2(xi)]λT21j1∑Tωj2(12) ∑ j 1 T [ ( ∑ i ∈ I j g i ) ω j 1 2 ( ∑ i ∈ I j h i λ ) ω j 2 ] λ T (13) \sum_{j1}^{T}[(\sum_{i \in I_j}g_i) \omega_j \frac{1}{2}(\sum_{i \in I_j}h_i\lambda) \omega_j^2] \lambda T \tag{13} j1∑T[(i∈Ij∑gi)ωj21(i∈Ij∑hiλ)ωj2]λT(13) 求上式最小化的参数对 ω \omega ω求导数并另其等于0得到下式: ∂ l ( t ) ∂ ω j 0 (14) \frac{\partial l^{(t)}}{\partial \omega_j}0 \tag{14} ∂ωj∂l(t)0(14) ∑ i ∈ I j ( ∑ i ∈ I j h i λ ) ω j 0 (15) \sum_{i \in I_j}(\sum_{i \in I_j}h_i \lambda) \omega_j0 \tag{15} i∈Ij∑(i∈Ij∑hiλ)ωj0(15) ω j ∗ − ∑ i ∈ I j g i ∑ i ∈ I j h i λ (16) \omega_j^*-\frac{\sum_{i \in I_j}g_i}{\sum_{i \in I_j}h_i \lambda} \tag{16} ωj∗−∑i∈Ijhiλ∑i∈Ijgi(16) 将上式带入损失函数得到最小损失 l ^ ( t ) ( q ) − 1 2 ∑ j 1 T ( ∑ i ∈ I j g i ) 2 ∑ i ∈ I j h i λ γ T (17) \hat{l}^{(t)}(q)-\frac{1}{2}\sum_{j1}^{T}\frac{(\sum_{i \in I_j}g_i)^2}{\sum_{i \in I_j}h_i \lambda}\gamma T \tag{17} l^(t)(q)−21j1∑T∑i∈Ijhiλ(∑i∈Ijgi)2γT(17) 根据公式(17)可以作为特征分裂的指标.计算公式如下(这个值越大越好): L s p l i t 1 2 [ ∑ i ∈ I L g i ) 2 ∑ i ∈ I L h i λ ∑ i ∈ I R g i ) 2 ∑ i ∈ I R h i λ − ∑ i ∈ I g i ) 2 ∑ i ∈ I h i λ ] − λ (18) L_{split}\frac{1}{2} \left[ \frac{\sum_{i \in I_L}g_i)^2}{\sum_{i \in I_L}h_i\lambda} \frac{\sum_{i \in I_R}g_i)^2}{\sum_{i \in I_R}h_i\lambda} - \frac{\sum_{i \in I}g_i)^2}{\sum_{i \in I}h_i\lambda} \right ] - \lambda \tag{18} Lsplit21[∑i∈ILhiλ∑i∈ILgi)2∑i∈IRhiλ∑i∈IRgi)2−∑i∈Ihiλ∑i∈Igi)2]−λ(18)
算法十问
随机森林为什么能够更鲁棒 由于随机森林使用了使用了行采样和列采样技术是的每棵树不容易过拟合并且是基于树的集成算法由于使用了采用数据是的每棵树的差别较大在进行embedding的时候可以更好的降低模型的方差整体而言是的RF是一个鲁棒的模型。 RF分类和回归问题如何预测y值 RF是一个加权平均的模型是进行分类问题的时候使用的个k个树的投票策略多数服从少数。在回归的使用是使用的k个树的平均。可以看出来rf的训练和预测过程都可以进行并行处理。 相同数据量训练RF和gbdt谁可以更快谁对异常值不敏感 gbdt是前向加法模型由于第i棵树需要用到前i-1树的残差所有在再整个建立过程是串行处理的RF整体是bagging算法的一种是k个树的加权平均k棵树可以并行处理因此可能得到更快的速度。需要指出在gbdt的原始算法中没有使用行列的随机采样相反rf使用了随机采样。 由于gbdt当前的误差会延续给下一棵树而RF每次都是独立的随机采样随机森林对异常值不敏感GBDT对异常值非常敏感。 解释一个什么是gb什么是dt即为什么叫做gbdt gbdt(Gradient Boosting Decision Tree),dt是指Decision Tree表示使用决策树作为基学习器使用的cart树gb表示梯度提升因为在传统的gbdt中在第i轮的迭代中使用前i-1的梯度作为当前残差进行拟合。 gbdt为什么用负梯度代表残差 上文公式(3)是gbdt的损失函数对公式(3)进行在 f m − 1 ( x ) 处进行 f_{m-1}(x)处进行 fm−1(x)处进行泰勒的一阶展开: L ( y , f m ( x ) ) L ( y , f m − 1 ( x ) β m b ( x ; γ m ) ) L(y,f_m(x))L(y,f_{m-1}(x)\beta_m b(x;\gamma_m)) L(y,fm(x))L(y,fm−1(x)βmb(x;γm)) L ( y , f m − 1 ( x ) ) ∂ L ( y , f m − 1 ( x ) ) ∂ f m − 1 ( x ) ( f m ( x ) − f m − 1 ( x ) ) L(y,f_{m-1}(x))\frac{\partial L(y, f_{m-1}(x))}{\partial f_{m-1}(x)}(f_{m}(x)-f_{m-1}(x)) L(y,fm−1(x))∂fm−1(x)∂L(y,fm−1(x))(fm(x)−fm−1(x)) L ( y , f m − 1 ( x ) ) ∂ L ( y , f m − 1 ( x ) ) ∂ f m − 1 ( x ) ( β m b ( x ; γ m ) ) (19) L(y,f_{m-1}(x))\frac{\partial L(y, f_{m-1}(x))}{\partial f_{m-1}(x)}(\beta_m b(x;\gamma_m)) \tag{19} L(y,fm−1(x))∂fm−1(x)∂L(y,fm−1(x))(βmb(x;γm))(19) 从我们的目标是损失函数最小化使公式(19)最小化由于 L ( y , f m − 1 ( x ) ) L(y,f_{m-1}(x)) L(y,fm−1(x))是个常数所以我们的损失函数最小化可以转化为: a r g m i n ( β m , γ m ) m i n ∂ L ( y , f m − 1 ( x ) ) ∂ f m − 1 ( x ) ( β m b ( x ; γ m ) ) (20) argmin_{(\beta_m,\gamma_m)}min \frac{\partial L(y, f_{m-1}(x))}{\partial f_{m-1}(x)}(\beta_m b(x;\gamma_m)) \tag{20} argmin(βm,γm)min∂fm−1(x)∂L(y,fm−1(x))(βmb(x;γm))(20) 将上述式子的两项都看做是向量为了是相乘之后最小一定是向量之间的异号,因此得到: ( β m b ( x ; γ m ) ) − ∂ L ( y , f m − 1 ( x ) ) ∂ f m − 1 ( x ) (21) (\beta_m b(x;\gamma_m)) - \frac{\partial L(y, f_{m-1}(x))}{\partial f_{m-1}(x)} \tag{21} (βmb(x;γm))−∂fm−1(x)∂L(y,fm−1(x))(21) 从公式(20)可以看出第m棵树使用前m-1的负梯度作为残差所有每次都是拟合的负梯度. gbdt是训练过程如何选择特征 gbdt使用基学习器是CART树CART树是二叉树每次使用yes or no进行特征选择数值连续特征使用的最小均方误差离散值使用的gini指数。在每次划分特征的时候会遍历所有可能的划分点找到最有的特征分裂点这是用为什么gbdt会比rf慢的主要原因之一。 gbdt应用在多分类问题 gbdt 每轮的训练是在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值 。这个要求每轮迭代的时候弱分类器的输出的结果相减是有意义的。残差相减是有意义的。对于多分类任务GDBT的做法是采用一对多的策略也就是说对每个类别训练M个分类器。假设有K个类别那么训练完之后总共有M*K颗树。两层循环的顺序不能改变。也就是说K个类别都拟合完第一颗树之后才开始拟合第二颗树不允许先把某一个类别的M颗树学习完再学习另外一个类别。 RF和GBDT的区别 GBDT是采用boosing方法降低偏差RF采用的是baggging方法降低方差。其中GBDT中的核心是通过用分类器如CART、RF拟合损失函数梯度而损失函数的定义就决定了在子区域内各个步长其中就是期望输出与分类器预测输出的查即bias而RF的核心就是自采样样本随机和属性随机所有样本中随机选择K个子样本选择最优属性来划分样本数相同下的不同训练集产生的各个分类器即数据的扰动导致模型学习性能的变化即variance。 Xgboost相对gbdt做了哪些改进 传统GBDT以CART作为基分类器xgboost还支持线性分类器这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归分类问题或者线性回归回归问题。传统GBDT在优化时只用到一阶导数信息xgboost则对代价函数进行了二阶泰勒展开同时用到了一阶和二阶导数。顺便提一下xgboost工具支持自定义代价函数只要函数可一阶和二阶求导。xgboost在代价函数里加入了正则项用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲正则项降低了模型的variance使学习出来的模型更加简单防止过拟合这也是xgboost优于传统GBDT的一个特性。列抽样column subsampling。xgboost借鉴了随机森林的做法支持列抽样不仅能降低过拟合还能减少计算这也是xgboost异于传统gbdt的一个特性。 对缺失值的处理。对于特征的值有缺失的样本xgboost可以自动学习出它的分裂方向。xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的注意xgboost的并行不是tree粒度的并行xgboost也是一次迭代完才能进行下一次迭代的第t次迭代的代价函数里包含了前面t-1次迭代的预测值。xgboost的并行是在特征粒度上的。我们知道决策树的学习最耗时的一个步骤就是对特征的值进行排序因为要确定最佳分割点xgboost在训练之前预先对数据进行了排序然后保存为block结构后面的迭代中重复地使用这个结构大大减小计算量。这个block结构也使得并行成为了可能在进行节点的分裂时需要计算每个特征的增益最终选增益最大的那个特征去做分裂那么各个特征的增益计算就可以开多线程进行。可并行的近似直方图算法。树节点在进行分裂时我们需要计算每个特征的每个分割点对应的增益即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下贪心算法效率就会变得很低所以xgboost还提出了一种可并行的近似直方图算法用于高效地生成候选的分割点。 xgb如何在计算特征时加速的 xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的注意xgboost的并行不是tree粒度的并行xgboost也是一次迭代完才能进行下一次迭代的第t次迭代的代价函数里包含了前面t-1次迭代的预测值。xgboost的并行是在特征粒度上的。我们知道决策树的学习最耗时的一个步骤就是对特征的值进行排序因为要确定最佳分割点xgboost在训练之前预先对数据进行了排序然后保存为block结构后面的迭代中重复地使用这个结构大大减小计算量。这个block结构也使得并行成为了可能在进行节点的分裂时需要计算每个特征的增益最终选增益最大的那个特征去做分裂那么各个特征的增益计算就可以开多线程进行。可并行的近似直方图算法。树节点在进行分裂时我们需要计算每个特征的每个分割点对应的增益即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下贪心算法效率就会变得很低所以xgboost还提出了一种可并行的近似直方图算法用于高效地生成候选的分割点。 xgb为什么使用二阶梯度信息为什么不使用三阶或者更高梯度信息 xgb之所以使用二阶梯度信息是因为从泰勒展开式来看gbdt使用的一阶梯度的泰勒展开式丢失了很多的信息使用二阶可以使损失函数更加准确。从泰勒展开的角度来看展开的次数越多越能更精准的表示损失函数的值但是如果我们使用二阶梯度就要要求损失函数二阶可导如果使用n阶展开就要求损失函数n阶可导但是有很多损失函数不是n阶可导的比如均方误差因此使用二阶梯度信息是一个泰勒展开和损失函数选择的折中。 lgb相对xgb做了哪些改进 直方图算法LightGBM提供一种数据类型的封装相对Numpy,Pandas,Array等数据对象而言节省了内存的使用原因在于他只需要保存离散的直方图LightGBM里默认的训练决策树时使用直方图算法XGBoost里现在也提供了这一选项不过默认的方法是对特征预排序直方图算法是一种牺牲了一定的切分准确性而换取训练速度以及节省内存空间消耗的算法.在训练决策树计算切分点的增益时预排序需要对每个样本的切分位置计算所以时间复杂度是O(#data)而LightGBM则是计算将样本离散化为直方图后的直方图切割位置的增益即可时间复杂度为O(#bins),时间效率上大大提高了(初始构造直方图是需要一次O(#data)的时间复杂度不过这里只涉及到加和操作).直方图做差进一步提高效率计算某一节点的叶节点的直方图可以通过将该节点的直方图与另一子节点的直方图做差得到所以每次分裂只需计算分裂后样本数较少的子节点的直方图然后通过做差的方式获得另一个子节点的直方图进一步提高效率节省内存,将连续数据离散化为直方图的形式对于数据量较小的情形可以使用小型的数据类型来保存训练数据 不必像预排序一样保留额外的对特征值进行预排序的信息 减少了并行训练的通信代价.稀疏特征优化、直接支持类别特征、网络通信优化 比较一下catboost、lgb和xgb XGBoost、LightGBM和CatBoost都是目前经典的SOTAstate of the artBoosting算法都可以归类到梯度提升决策树算法系列。三个模型都是以决策树为支撑的集成学习框架其中XGBoost是对原始版本的GBDT算法的改进而LightGBM和CatBoost则是在XGBoost基础上做了进一步的优化在精度和速度上都有各自的优点。 三个模型树的构造方式有所不同XGBoost使用按层生长level-wise的决策树构建策略LightGBM则是使用按叶子生长leaf-wise的构建策略而CatBoost使用了对称树结构其决策树都是完全二叉树。对于类别特征的处理。XGBoost本身不具备自动处理类别特征的能力对于数据中的类别特征需要我们手动处理变换成数值后才能输入到模型中LightGBM中则需要指定类别特征名称算法即可对其自动进行处理CatBoost以处理类别特征而闻名通过目标变量统计等特征编码方式也能实现类别特征的高效处理。 如果将所有数据复制一倍放入训练数据集RF和GBDT分别有什么表现 RF可能出现过拟合? GBDT没有任何改变?(请思考) gbdt如何防止过拟合由于gbdt是前向加法模型前面的树往往起到决定性的作用如何改进这个问题 一般使用缩减因子对每棵树进行降权可以使用带有dropout的GBDT算法dart树随机丢弃生成的决策树然后再从剩下的决策树集中迭代优化提升树。 GBDT与Boosting区别较大它的每一次计算都是为了减少上一次的残差而为了消除残差可以在残差减小的梯度方向上建立模型; 在GradientBoost中每个新的模型的建立是为了使得之前的模型的残差往梯度下降的方法。 面试真题
RF和GBDT能够并行吗?写一个gbdt的损失函数?为什么要拟合负梯度?xgboost如何进行参数更新的?xgboost为什么使用二阶梯度信息?gbdt对异常值敏感吗?为什么?
