网站营销工作流程,建设机械网站资讯,vi设计公司网站,几百块钱可以做网站吗XGBoost的目标函数详见[机器学习]XGBoost#xff08;2#xff09;——目标函数#xff08;公式详解#xff09;
确定树的结构
之前在关于目标函数的计算中#xff0c;均假设树的结构是确定的#xff0c;但实际上#xff0c;当划分条件不同时#xff0c;叶子节点包含的…XGBoost的目标函数详见[机器学习]XGBoost2——目标函数公式详解
确定树的结构
之前在关于目标函数的计算中均假设树的结构是确定的但实际上当划分条件不同时叶子节点包含的样本不同计算的 H j H_j Hj 和 G j G_j Gj不同每个叶子节点的W值也就不同 每一棵树都有属于自己最优的 O b j ∗ Obj^* Obj∗因此要找一种最优的划分方式即要找出使得 O b j ∗ Obj^* Obj∗最小的树作为基学习器的决策树
穷举法计算所有可能的组合情况然后选出最小的 O b j ∗ Obj^* Obj∗ 缺点在实际应用中穷举所有可能的分裂点通常是不可行的因为计算成本太高。精确贪心算法每次选择最优的分裂点
XGBoost用的是精确贪心算法
精确贪心算法
在XGBoost中用精确贪心算法在构建决策树的过程中选择最优的分裂点。这种方法旨在找到能够最大化目标函数增益的分裂点从而提高模型的预测性能。
核心思想
贪心选择:在每一步分裂决策中算法不是寻找全局最优解而是做出局部最优选择。这意味着在当前步骤中选择能够最大程度降低目标函数损失函数和正则化项之和的分裂点。精确计算:对于每个可能的分裂点精确计算分裂后的增益。增益是通过比较分裂前后的目标函数值来计算的即增益等于分裂前的目标函数值减去分裂后所有子节点目标函数值的总和。递归分裂:一旦选择了最优分裂点算法将递归地对每个子节点重复分裂过程直到满足停止条件如达到最大树深度、增益小于阈值或子节点中的样本数小于某个阈值。
算法步骤 初始化开始时所有样本都在根节点。初始化目标函数 Obj 为所有样本的损失之和。 计算增益对于每个可能的分裂点计算分裂后的增益。增益是通过比较分裂前后的目标函数值来计算的即增益 父节点的目标函数值 - 子节点的目标函数值之和。 对于每个子节点 j目标函数 Obj_j 可以表示为 O b j j γ 0.5 ∗ ( G j 2 / ( H j λ ) ) Obj_j γ 0.5 * (G_j^2 / (H_j λ)) Objjγ0.5∗(Gj2/(Hjλ)) 其中 G j G_j Gj 是子节点上所有样本梯度的和 H j H_j Hj 是Hessian的和这两个都是可以计算的。增益 Gain 可以表示为 G a i n O b j p a r e n t − [ O b j l e f t O b j r i g h t ] Gain Obj_{parent} - [Obj_{left} Obj_{right}] GainObjparent−[ObjleftObjright] 其中 O b j p a r e n t Obj_{parent} Objparent 是父节点的目标函数值 O b j l e f t Obj_{left} Objleft 和 O b j r i g h t Obj_{right} Objright 是分裂后左右子节点的目标函数值。 选择最佳分裂在所有可能的分裂点中选择增益最大的分裂点作为最优分裂。这个分裂点将被用来将当前节点分裂为两个子节点。 更新目标函数使用最优分裂点分裂节点后更新目标函数。计算每个子节点上的 G j G_j Gj和 H j H_j Hj并更新 O b j Obj Obj。 递归构建对每个新创建的子节点重复步骤2-4直到满足停止条件如达到最大深度或增益小于阈值。
什么时候停止划分 最大增益小于一个很小的数如果进一步划分带来的增益小于预设的最小增益阈值min_split_gain则不会进行分裂。这个阈值用于控制只有当分裂能够显著提高模型性能时才会进行分裂。 叶子节点包含样本个数小于等于1如果一个叶子节点中的样本数量小于或等于1那么这个叶子节点将不再进一步划分。这是为了防止树的过拟合因为单个样本的分裂不会提供泛化能力。 达到最大树深度如果树的深度已经达到预设的最大深度max_depth则停止进一步划分。
算法伪代码 输入参数
I当前节点的所有样本实例。d特征的维度即数据集中特征的数量。
初始化
gain初始化为0用来存储在所有可能的分裂中找到的最大增益值。G所有样本梯度的总和。H所有样本Hessian的总和。
算法步骤 遍历所有特征对于每个特征 k从1到特征总数 m执行以下操作。 初始化左右子树的梯度和Hessian和 G L G_L GL 和 H L H_L HL 分别初始化为0用来存储左子树的梯度和和Hessian和。 对样本按特征值排序将样本集 I 按照特征 k 的值进行排序。 注意不同特征会划分出不同的样本集所以每次排序都要重新排。当特征非常多时排序操作非常耗时 计算左右子树的统计量遍历排序后的样本逐步构建左子树的统计量GL 和 HL同时计算右子树的统计量GR G - GL 和 HR H - HL。 计算分裂增益使用公式计算当前分裂点的增益 score score G L 2 H L λ G R 2 H R λ − G 2 H λ \text{score} \frac{G_L^2}{H_L \lambda} \frac{G_R^2}{H_R \lambda} - \frac{G^2}{H \lambda} scoreHLλGL2HRλGR2−HλG2 如果当前分裂点的增益大于之前记录的最大增益 gain则更新 gain。 选择最佳分裂在所有特征和所有可能的分裂点中选择增益最大的分裂点作为最终的分裂点。
输出
具有最大增益的分裂点这将用于构建决策树的节点分裂。
算法优化——近似算法
针对不同特征会划分出不同的样本集所以每次排序都要重新排的问题进行优化以牺牲精度为代价
压缩特征采样特征值
压缩特征——列采样
按树随机采样Tree-wise Subsampling: 在构建每棵树之前从所有特征中随机选择一部分特征进行考虑。例如一共有X1……X10个特征选3个特征X1X5X7之后每次计算都只用这三个特征
优点
减少每棵树的计算量因为每次分裂只考虑一部分特征可能的分裂点减少gain值的个数减少。有助于防止过拟合因为模型不会对所有特征都过于敏感。
缺点
固定随机选择的特征可能会忽略一些对模型预测性能有重要影响的特征导致模型无法充分利用所有特征信息。每次都只用X1X5X7可能忽略其他特征的信息
按层随机采样Level-wise Subsampling: 在构建树的每个层级时都重新对特征进行采样。例如一共有X1……X10个特征第一层根节点选3个特征X1X5X7之后每次计算都重新选三个特征第二层左节点用X2X3X4第二层右节点用X1X8X10……
优点
减少每棵树的计算量因为每次分裂只考虑一部分特征可能的分裂点减少gain值的个数减少。确保每一层的分裂都有新的随机特征选择增加了模型的多样性。通常比按树随机采样更复杂但可能提供更好的性能。
分桶采样特征值
在构建树的每个层级时对特征的值进行采样而不是使用全部特征值。例如对于每个特征 X i将其值域分成 k 组从每个特征的 k 组中随机选择一个值这样总共选择了 k 个特征值。
优点
减少每个特征的计算量因为每个特征的计算只考虑一部分特征值 H j H_j Hj和 G j G_j Gj计算量变小。
注意
不是随机选取是先分桶再从每个桶里选一个代表理想化假设特征值均匀分布每个桶里的特征值数量应该尽量接近但实际并不是这样的因此用加权分位法
加权分位法 收集梯度和Hessian对于每个特征收集所有样本的梯度 g i g_i gi 和Hessian h i h_i hi 计算权重样本权重通常与梯度和Hessian有关。在XGBoost中样本权重可以是Hessian的函数表示。 排序根据样本权重对特征的所有可能值进行排序。具有更高权重的样本在排序中会有更大的影响力。 计算分位数在排序后的特征值上根据预设的桶数量由参数 max_bin 控制计算分位数。这些分位数将用作桶的边界。 分桶使用计算出的分位数将特征值域分割成若干个桶。每个桶代表特征值的一个区间。 选择代表值从每个桶中选择一个代表值这个值将用于构建模型。在XGBoost中这个值通常是桶中所有样本梯度和的加权平均值。
策略
全局策略 分一次桶以后每次都按这个分法来分局部策略 每次都重新分一次桶
缺失值处理 Sparsity-aware Split Finding
实际场景拿到的数据是很稀疏的有大量缺失值因此需要处理缺失值
穷举法为所有组合计算增益选最大的贪心法把每个缺失值分别放到左边和右边计算gain比较两个gain的大小这样要计算2*缺失值个数次论文采用的方法把所有缺失值当成整体看待都同时放到左边计算一个gain再把所有缺失值放到右边计算一个gain比较两个gain的大小然后把所有缺失值样本全部放到gain大的那边。这样只用计算2次
注意加权分位法中缺失值不参与排序和分桶
学习率 shrinkage
目的为了防止过拟合
