XGBoost利用正则化学习目标来构建构成其集成模型的决策树。分裂查找算法是这个树构建过程的一个主要组成部分。对于构建中的树中的每个候选节点,算法必须确定最佳特征以及该特征的最佳分裂点,以划分数据。“最佳”分裂被定义为使目标函数值减小量最大的分裂,这通常被称为增益。XGBoost采用几种策略来查找分裂,最基本的一种是精确贪心算法。之所以称之为“精确”,是因为它详细评估了当前节点中实例的每个特征的每个可能分裂点。之所以称之为“贪心”,是因为它在每个节点上做出局部最优选择,选择增益最大的分裂,而不考虑对树中后续分裂的影响。分裂质量的量化:增益计算回顾步骤 $t$ 的XGBoost目标函数,它包含复杂度惩罚项:$$ 目标函数^{(t)} \approx \sum_{i=1}^{n} [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t) $$其中 $g_i$ 和 $h_i$ 是损失函数在步骤 $t-1$ 时关于实例 $i$ 预测值的一阶和二阶梯度。 $f_t(x_i)$ 是新树对实例 $i$ 的预测值,而 $\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2$ 是正则化项,其中 $T$ 是叶子数量,$w_j$ 是叶子 $j$ 的权重。对于固定的树结构,包含实例集 $I_j$ 的叶子 $j$ 的最佳权重 $w_j^*$ 为:$$ w_j^* = - \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} $$且此树结构对应的最佳目标函数值为:$$ 目标函数^* = - \frac{1}{2} \sum_{j=1}^{T} \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma T $$我们定义 $G_j = \sum_{i \in I_j} g_i$ 和 $H_j = \sum_{i \in I_j} h_i$。目标函数变为:$$ 目标函数^* = - \frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T $$现在,考虑将包含实例 $I$ 的叶子(节点)分裂为两个子节点:一个包含实例 $I_L$ 的左子节点,和一个包含实例 $I_R$ 的右子节点,使得 $I = I_L \cup I_R$。这个分裂的增益是父节点(如果它保持为叶子)的目标函数值减去两个新子叶子的目标函数值之和。如果节点 $I$ 不分裂(保持为单个叶子),则目标函数值为: $目标函数_{nosplit} = - \frac{1}{2} \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} + \gamma$如果节点被分裂为 $I_L$ 和 $I_R$,则目标函数值为: $目标函数_{split} = - \frac{1}{2} \left( \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} \right) + 2\gamma$增益定义为 $Gain = 目标函数_{nosplit} - 目标函数_{split}$。然而,XGBoost文献通常对增益的定义略有不同,它只关注目标函数第一部分的改进,并减去添加一个叶子的惩罚项 $\gamma$(因为分裂用两个叶子替换了一个叶子,增加了复杂度):$$ Gain = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} \right] - \gamma $$这个公式是精确贪心算法使用的主要计算。只有当结果增益为正(或大于最小阈值参数 min_split_loss,在API中也称为 gamma)时,分裂才被认为是有效的。项 $\gamma$ 作为正则化参数,通过设定进行分裂所需的最小增益来控制复杂度。精确贪心算法步骤算法为每个节点执行以下操作:初始化 max_gain = 0。对于从 $1$ 到 $d$ 的每个特征 $k$(特征数量): a. 令 $I$ 为当前节点中的实例集。 b. 计算总梯度 $G = \sum_{i \in I} g_i$ 和海森 $H = \sum_{i \in I} h_i$。 c. 根据特征 $k$ 的值对 $I$ 中的实例进行排序。 d. 初始化 $G_L = 0$, $H_L = 0$。 e. 从左到右遍历已排序的实例 $i$: i. 更新 $G_L = G_L + g_i$, $H_L = H_L + h_i$。 ii. 计算 $G_R = G - G_L$, $H_R = H - H_L$。 iii. 考虑当前实例 $i$ 和下一个实例之间的潜在分裂点(或者通常使用唯一的排序特征值作为潜在分裂点)。 iv. 使用以下公式计算此潜在分裂的增益: $Gain = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{G^2}{H + \lambda} \right] - \gamma$ v. 如果 $Gain > max_gain$,则更新 $max_gain = Gain$ 并存储当前特征 $k$ 和分裂点作为迄今为止找到的最佳分裂。如果 $max_gain > 0$(或 $max_gain \ge \text{min_split_loss}$),则使用找到的最佳特征和分裂点来分裂节点。否则,将节点声明为叶子。下图说明了为单个特征找到最佳分裂点的过程:digraph ExactGreedy { rankdir=LR; node [shape=box, style=rounded, fontname="sans-serif", fontsize=10]; edge [fontname="sans-serif", fontsize=10]; subgraph cluster_feature { label = "对于特征 k"; bgcolor="#e9ecef"; style=filled; Start [label="实例 I 到达节点"]; Sort [label="按特征 k 值\n排序实例 I"]; Loop [label="遍历潜在分裂点 j"]; CalcSums [label="计算分裂 j 的\nGL, HL, GR, HR"]; CalcGain [label="计算增益(j)"]; CheckGain [label="增益(j) > 当前最大增益?", shape=diamond]; UpdateMax [label="更新最大增益\n存储特征 k, 分裂 j"]; NextSplit [label="下一个分裂点"]; Start -> Sort; Sort -> Loop; Loop -> CalcSums; CalcSums -> CalcGain; CalcGain -> CheckGain; CheckGain -> UpdateMax [label=" 是"]; CheckGain -> NextSplit [label=" 否"]; UpdateMax -> NextSplit; NextSplit -> Loop [label=" 更多分裂?"]; } Loop -> EndLoop [label=" 无更多分裂"]; EndLoop [label="特征 k 已评估"]; EndLoop -> NextFeature [label="更多特征?"]; NextFeature [label="处理下一个特征", shape=diamond]; NextFeature -> Start [label=" 是"]; FinalSplit [label="找到节点分裂点 / \n 成为叶子"]; NextFeature -> FinalSplit [label=" 无更多特征"]; }单个特征的精确贪心算法的迭代过程。实例被排序,每个潜在分裂点根据增益计算进行评估。所有特征中的最佳分裂决定了节点的后续。计算考量精确贪心算法中主要的计算瓶颈是在每个节点上对特征值进行排序。如果有 $n$ 个实例到达一个节点,并且有 $d$ 个特征:对于每个特征,排序需要 $O(n \log n)$ 时间。排序后,扫描已排序的实例以找到最佳分裂点需要 $O(n)$ 时间。对所有 $d$ 个特征执行此操作,每个节点的复杂度大约为 $O(d \times n \log n)$。尽管很全面,但这种枚举在处理以下情况时可能会变得计算量大:大量实例 ($n$)。大量特征 ($d$)。深度树(其中过程重复多次)。这种计算成本促使了近似分裂查找算法的开发,我们将在下一节讨论这些算法。它们以牺牲找到绝对最佳分裂的一些准确性为代价,换取计算效率的显著提升,使XGBoost对非常大的数据集变得实用。精确贪心算法是XGBoost中树构建的根本。它的优点在于对基于正则化目标函数的局部最优分裂进行详尽搜索。了解此过程对于理解XGBoost如何构建高效的树以及为什么有时需要近似算法等替代方法很重要。