2.4 分裂节点查找算法

XGBoost分裂节点查找算法详解

引言

XGBoost (Extreme Gradient Boosting) 是一种高效且广泛使用的梯度提升决策树 (GBDT) 算法。其在各种机器学习竞赛和实际应用中都表现出色，这得益于其在算法和系统上的多项优化。在XGBoost的众多优化中，高效的分裂节点查找算法是其核心竞争力之一。分裂节点查找算法的目标是在每个节点上找到最优的分裂特征和分裂点，以最大化树的生长收益，并最终构建出性能卓越的模型。

2.4 分裂节点查找算法

在树模型中，每个节点的分裂都旨在将数据划分为更纯净的子集，从而提高模型的预测能力。分裂节点查找算法的任务就是在给定的节点上，遍历所有可能的特征和分裂点，找到最佳的分裂方案。对于连续特征，分裂点通常是特征值；对于离散特征，分裂点可以是特征值的子集。

XGBoost为了高效地进行分裂节点查找，并应对不同规模和特性的数据集，提供了多种算法选择。下面我们将逐一介绍。

2.4.1 精确贪心算法 (Exact Greedy Algorithm)

精确贪心算法是最直接且理论上最优的分裂节点查找方法。它在所有可能的特征和分裂点上进行穷举搜索，计算每种分裂方案的增益 (Gain)，并选择增益最大的分裂方案作为当前节点的最优分裂。

算法原理

对于树的每个节点，精确贪心算法会执行以下步骤：

1. 遍历所有特征 (feature)：对于数据集中的每个特征。

2. 遍历所有可能的分裂点 (split point)：对于当前特征，遍历所有可能的取值作为分裂点。对于连续特征，通常考虑排序后相邻特征值的均值作为候选分裂点。

3. 计算分裂增益 (Gain Calculation)：对于每个特征和分裂点组合，将数据划分为左右子节点，并计算分裂后的增益。增益的计算通常基于目标函数的变化，例如XGBoost中使用的结构分数 (Structure Score) 的增益。

4. 选择最优分裂 (Best Split)：选择增益最大的特征和分裂点作为当前节点的最优分裂方案。

增益计算 (Gain Calculation)

XGBoost的目标函数包含损失函数和正则化项。分裂增益的计算基于目标函数的减少量。假设我们考虑一个节点的分裂，分裂前节点的目标函数值为 L_{parent}，分裂成左右子节点后的目标函数值分别为 L_{left} 和 L_{right}。则分裂增益 (Gain) 可以定义为：

Gain = L_{parent} - (L_{left} + L_{right})

在XGBoost的具体实现中，增益通常基于结构分数的变化来计算，并考虑正则化项。更具体地，XGBoost使用二阶泰勒展开近似损失函数，并定义了结构分数来衡量树的结构好坏。分裂增益的计算公式会涉及到一阶梯度和二阶梯度统计量。

算法流程 (Graph TD)

代码实践 (Python + XGBoost)

在XGBoost中，默认情况下，如果 tree_method 参数设置为 exact 或 hist (对于小数据集，hist 模式也会回退到精确贪心算法)，则会使用精确贪心算法。

import xgboost as xgb
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
# 1. 生成模拟数据
X, y = make_classification(n_samples=1000, n_features=20, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# 2. 定义 XGBoost 参数
params = {
    'objective': 'binary:logistic',
    'eval_metric': 'logloss',
    'tree_method': 'exact' # 显式指定使用精确贪心算法 (或者不指定，小数据集默认使用)
}
# 3. 创建 DMatrix 数据格式
dtrain = xgb.DMatrix(X_train, label=y_train)
dtest = xgb.DMatrix(X_test, label=y_test)
# 4. 训练模型
num_rounds = 100
model = xgb.train(params, dtrain, num_rounds)
# 5. 模型预测
y_pred_prob = model.predict(dtest)
y_pred = [1 if p > 0.5 else 0 for p in y_pred_prob]
# 6. 模型评估 (示例，可以添加更详细的评估指标)
from sklearn.metrics import accuracy_score
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy}")
​

内容详解

• 优点：精确贪心算法能够找到理论上的最优分裂点，从而在小数据集上获得更高的精度。

• 缺点：计算复杂度高。对于连续特征和大数据集，遍历所有可能的特征和分裂点会非常耗时，效率较低。时间复杂度通常为 O(n \cdot d \cdot m \cdot \log n)，其中 n 是样本数量, d 是特征数量, m 是候选分裂点数量 (对于连续特征近似于 n)。

• 适用场景：精确贪心算法适用于小数据集或者特征维度较低的场景，在这些场景下，计算成本可接受，且能保证模型的精度。

2.4.2 近似贪心算法 (Approximate Greedy Algorithm)

为了解决精确贪心算法在大数据集上的效率瓶颈，XGBoost引入了近似贪心算法。近似贪心算法不再精确地遍历所有可能的分裂点，而是先对特征值进行分桶 (bucketing) 或者分位数划分 (quantile sketch)，然后仅考虑桶边界或者分位数点作为候选分裂点。这样大大减少了候选分裂点的数量，从而提高了分裂节点查找的效率。

XGBoost支持两种近似贪心算法变体：全局近似 (Global Proposal) 和 局部近似 (Local Proposal)。

2.4.2.1 全局近似算法 (Global Proposal)

全局近似算法在树构建的初始阶段，对每个特征预先计算一组候选分裂点，并在后续的树节点分裂中重复使用这些候选点。这些候选点通常是基于特征的分位数 (quantiles) 来选择的。

算法步骤

1. 候选点生成 (Proposal)：对于每个特征，通过分位数 sketch 算法 (例如，GK-algorithm 或 SpaceSaving) 近似计算特征的分位数。选择一组分位数点作为该特征的候选分裂点。这一步在树构建之前完成，每个特征的候选点集合在整棵树的构建过程中保持不变。

2. 分裂点查找 (Split Finding)：在树的每个节点分裂时，对于每个特征，仅需遍历预先计算好的候选分裂点集合，计算分裂增益，并选择最优分裂。

算法流程 (Graph TD - 全局近似)

2.4.2.2 局部近似算法 (Local Proposal)

局部近似算法与全局近似算法的主要区别在于候选分裂点的生成时机。局部近似算法在每次节点分裂时，都重新计算候选分裂点。这意味着每个节点都会根据其自身的数据分布，动态生成候选分裂点。

算法步骤

1. 候选点生成 (Proposal)：在树的每个节点分裂时，对于当前节点的数据，对每个特征通过分位数 sketch 算法计算分位数，并选择一组分位数点作为该节点上该特征的候选分裂点。

2. 分裂点查找 (Split Finding)：与全局近似算法类似，遍历当前节点上每个特征的候选分裂点集合，计算分裂增益，并选择最优分裂。

算法流程 (Graph TD - 局部近似)

代码实践 (Python + XGBoost - 近似贪心算法)

在XGBoost中，可以通过设置 tree_method 参数为 approx 或 hist (对于大数据集，hist 通常使用近似算法) 来使用近似贪心算法。 还可以使用 sketch_eps 参数来控制分位数 sketch 的精度，从而影响候选分裂点的数量。sketch_eps 的值越小，分位数计算越精确，候选点越多，但计算成本也越高。

import xgboost as xgb
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
# 1. 生成模拟数据 (大数据集，例如 n_samples=10000)
X, y = make_classification(n_samples=10000, n_features=20, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# 2. 定义 XGBoost 参数
params = {
    'objective': 'binary:logistic',
    'eval_metric': 'logloss',
    'tree_method': 'approx', # 使用近似贪心算法
    'sketch_eps': 0.03 # 分位数 sketch 精度，值越小精度越高，候选点越多
}
# 3. 创建 DMatrix 数据格式
dtrain = xgb.DMatrix(X_train, label=y_train)
dtest = xgb.DMatrix(X_test, label=y_test)
# 4. 训练模型
num_rounds = 100
model = xgb.train(params, dtrain, num_rounds)
# 5. 模型预测和评估 (同精确贪心算法代码示例)
# ... (省略重复代码) ...
​

内容详解

• 全局近似 vs. 局部近似：

  • 全局近似：候选点生成一次，复用多次。计算成本更低，效率更高，但可能因为候选点不够精细而导致精度略有损失。适用于非常大的数据集。

  • 局部近似：每个节点都重新生成候选点。候选点更贴合当前节点的数据分布，精度更高，但计算成本也略高于全局近似。在精度和效率之间取得了较好的平衡。

• 分位数 Sketch：分位数 sketch 算法 (如 GK-algorithm) 可以在近似常数空间和时间复杂度内，近似计算数据流的分位数。XGBoost使用分位数 sketch 来高效地生成候选分裂点。sketch_eps 参数控制了分位数 sketch 的精度，影响候选点的数量。

• 优点：近似贪心算法显著降低了分裂节点查找的计算复杂度，尤其是在大数据集和连续特征场景下，大大提高了训练效率。

• 缺点：相比精确贪心算法，近似算法可能会损失一定的精度，尤其是在候选点数量较少的情况下。

• 适用场景：近似贪心算法适用于大数据集和计算资源有限的场景。全局近似更适合超大数据集，对效率要求更高的场景；局部近似在精度和效率之间取得了较好的平衡，适用范围更广。

2.4.3 稀疏感知分裂算法 (Sparsity-aware Split Finding)

在实际应用中，数据集中常常存在稀疏性，例如缺失值、One-Hot 编码导致的零值等。传统的决策树算法在处理稀疏数据时效率较低，并且可能影响模型精度。XGBoost针对稀疏数据，专门设计了稀疏感知分裂算法。

算法原理

稀疏感知分裂算法的核心思想是在分裂节点查找过程中，考虑到数据中的缺失值或稀疏值。对于每个节点，算法会学习出一个默认分裂方向 (default direction)。当遇到缺失值或者稀疏值时，数据会被分配到默认方向的子节点。

算法步骤

1. 遍历所有特征和分裂点：与精确贪心算法类似，遍历所有特征和候选分裂点。

2. 尝试默认方向：对于每个特征和分裂点，算法尝试两种默认方向：

   • 默认方向为左子树：所有缺失值或稀疏值数据都分配到左子树，其余数据根据分裂点分配到左右子树。

   • 默认方向为右子树：所有缺失值或稀疏值数据都分配到右子树，其余数据根据分裂点分配到左右子树。

3. 计算分裂增益：对于每种默认方向，计算分裂增益。

4. 选择最优分裂和默认方向：选择增益最大的分裂点和默认方向作为当前节点的最优分裂方案。

算法流程 (Graph TD - 稀疏感知)

代码实践 (Python + XGBoost - 稀疏感知)

XGBoost 默认就启用了稀疏感知分裂算法。当数据中存在缺失值 (例如 NaN) 或稀疏格式数据时，算法会自动应用稀疏感知策略。可以通过控制输入数据的格式 (例如，使用稀疏矩阵) 来显式地触发稀疏感知算法。

import xgboost as xgb
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
import numpy as np
import scipy.sparse as sp
# 1. 生成模拟稀疏数据 (例如，添加缺失值)
X, y = make_classification(n_samples=1000, n_features=20, random_state=42)
X[np.random.rand(*X.shape) < 0.2] = np.nan # 引入 20% 缺失值
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# 2. 定义 XGBoost 参数 (无需特殊参数，默认启用稀疏感知)
params = {
    'objective': 'binary:logistic',
    'eval_metric': 'logloss'
}
# 3. 创建 DMatrix 数据格式 (XGBoost 可以自动处理 NaN)
dtrain = xgb.DMatrix(X_train, label=y_train)
dtest = xgb.DMatrix(X_test, label=y_test)
# 4. 训练模型
num_rounds = 100
model = xgb.train(params, dtrain, num_rounds)
# 5. 模型预测和评估 (同前代码示例)
# ... (省略重复代码) ...
# 示例：使用稀疏矩阵 (scipy.sparse)
X_sparse = sp.csr_matrix(X) # 将 numpy array 转换为稀疏矩阵
X_train_sparse, X_test_sparse, y_train_sparse, y_test_sparse = train_test_split(X_sparse, y, test_size=0.2, random_state=42)
dtrain_sparse = xgb.DMatrix(X_train_sparse, label=y_train_sparse)
dtest_sparse = xgb.DMatrix(X_test_sparse, label=y_test_sparse)
model_sparse = xgb.train(params, dtrain_sparse, num_rounds)
​

内容详解

• 默认方向：稀疏感知算法为每个节点学习一个默认方向 (左或右)。当遇到缺失值或稀疏值时，数据样本会被分配到这个默认方向的子节点。默认方向的选择是在分裂节点查找过程中，通过比较不同默认方向的分裂增益来确定的。

• 处理缺失值：稀疏感知算法能够有效地处理缺失值，无需预先进行缺失值填充。算法自动学习最优的缺失值处理策略，提高了模型的鲁棒性和泛化能力。

• 处理稀疏数据：对于One-Hot 编码等产生的稀疏数据，稀疏感知算法可以避免不必要的计算，提高效率。

• 优点：能够有效处理稀疏数据 (包括缺失值和稀疏特征)，提高模型在稀疏数据上的精度和效率。

• 缺点：相比于不考虑稀疏性的算法，稀疏感知算法略微增加了计算复杂度，因为需要尝试两种默认方向。

• 适用场景：稀疏感知算法适用于数据集中存在大量缺失值或稀疏特征的场景，例如，用户行为数据、文本数据、生物信息数据等。

总结与对比

XGBoost提供了多种分裂节点查找算法，以适应不同规模和特性的数据集：

在实际应用中，算法的选择需要根据数据集的规模、特征类型、稀疏程度以及对精度和效率的要求进行权衡。对于小数据集，精确贪心算法通常是首选；对于大数据集，近似贪心算法 (全局或局部) 更为实用；对于稀疏数据集，稀疏感知分裂算法能够显著提升模型性能。XGBoost的灵活性在于允许用户根据具体情况选择合适的分裂节点查找算法，从而在各种场景下都能获得优秀的性能。

未来展望

随着数据规模的持续增长和应用场景的不断拓展，对高效且精确的分裂节点查找算法的需求也越来越高。未来的研究方向可能包括：

• 更高效的近似算法：探索更高效的分位数 sketch 算法，或者设计新的近似策略，进一步降低计算成本，同时尽量减少精度损失。

• 自适应分裂算法：根据数据集的特性和节点的数据分布，自适应地选择不同的分裂策略，例如，在数据分布密集的区域使用更精细的分裂，在稀疏区域使用更粗略的分裂。

• 硬件加速：利用GPU、FPGA等硬件加速分裂节点查找过程，进一步提高XGBoost的训练速度。

总结

2.4.1 精确贪心算法 (Exact Greedy Algorithm)

XGBoost 分裂节点查找算法：2.4.1 精确贪心算法 (Exact Greedy Algorithm) 详解

1. 引言

XGBoost (Extreme Gradient Boosting) 是一种高效且广泛应用梯度提升算法，在机器学习领域占据着举足轻重的地位。其卓越的性能很大程度上归功于其精巧的设计，包括高效的分裂节点查找算法。在 XGBoost 的算法框架中，如何有效地找到最佳分裂点，是构建高质量决策树的关键步骤。

在 XGBoost 的官方文档或相关技术资料中，通常会将分裂节点查找算法归类在 "2.4 分裂节点查找算法" 这一章节下。而在 "2.4.1 精确贪心算法 (Exact Greedy Algorithm)" 则是最基础、也是最重要的分裂查找方法之一。理解精确贪心算法，是深入学习 XGBoost 更高级分裂算法（如近似贪心算法）的基础。

2. 精确贪心算法 (Exact Greedy Algorithm) 原理

精确贪心算法，顾名思义，是一种精确且贪心的分裂节点查找策略。

• 精确性: 它会穷举所有可能的特征和所有可能的特征值分割点，来计算分裂后的增益 (Gain)。

• 贪心性: 在每次分裂时，它都选择当前最优的分裂点，即增益最大的分裂点，而并不考虑这次分裂是否会在全局上达到最优。这种局部最优的选择策略被称为贪心。

算法核心思想:

对于树的每一个节点，精确贪心算法会遍历所有特征的所有可能取值，计算以每个特征值作为分裂点时的增益 (Gain)。然后，选择增益最大的特征和分裂点进行分裂。这个过程会递归地进行下去，直到满足预设的停止条件（例如，树的最大深度、节点样本数阈值等）。

算法步骤概括:

1. 遍历节点: 从树的根节点开始，递归地处理每一个待分裂的节点。

2. 遍历特征: 对于当前节点，遍历所有特征。

3. 遍历分裂点: 对于每个特征，遍历该特征所有可能的取值作为分裂点。

4. 计算增益 (Gain): 对于每个分裂点，计算分裂后的增益。增益的计算通常基于目标函数，例如，回归问题中可以是平方误差的减少，分类问题中可以是基尼系数或交叉熵的减少。XGBoost 使用自定义的目标函数和正则化项来计算增益。

5. 选择最佳分裂: 在所有特征和所有分裂点中，选择增益最大的分裂点作为当前节点的最优分裂。

6. 分裂节点: 根据选定的最佳分裂点，将当前节点分裂成两个子节点。

7. 递归分裂: 对子节点重复步骤 1-6，直到满足停止条件。

增益 (Gain) 的计算

增益 (Gain) 是衡量分裂好坏的关键指标。在 XGBoost 中，增益的计算涉及到目标函数和正则化项。 假设我们有一个节点 I，要考虑将其分裂成两个子节点 L (左子节点) 和 R (右子节点)。 分裂前的目标函数值为 Obj(I)，分裂后的目标函数值是 Obj(L) + Obj(R)。 则分裂带来的增益 Gain 可以定义为：

Gain = Obj(I) - (Obj(L) + Obj(R)) - 正则化项
​

XGBoost 的目标函数通常包含损失函数和正则化项。损失函数衡量模型的预测值与真实值之间的差距，正则化项用于防止过拟合，控制模型的复杂度。 在计算增益时，正则化项的变化也会被考虑进来。

更具体的增益计算公式 (以 XGBoost 目标函数为例):

XGBoost 的目标函数在泰勒二阶展开后，可以表示为：

Obj =  ∑ [g_i * f_t(x_i) + 1/2 * h_i * f_t(x_i)^2] + Ω(f_t) + constant
​

其中，g_i 和 h_i 分别是损失函数一阶导数和二阶导数，f_t(x_i) 是第 t 棵树的预测值，Ω(f_t) 是树的复杂度正则化项。

对于一个节点分裂，增益的计算公式可以简化为：

Gain = G_L^2 / (H_L + λ) + G_R^2 / (H_R + λ) - G^2 / (H + λ) - γ
​

• G = ∑g_i (节点 I 所有样本的一阶导数之和)

• H = ∑h_i (节点 I 所有样本的二阶导数之和)

• G_L = ∑g_i (左子节点 L 所有样本的一阶导数之和)

• H_L = ∑h_i (左子节点 L 所有样本的二阶导数之和)

• G_R = ∑g_i (右子节点 R 所有样本的一阶导数之和)

• H_R = ∑h_i (右子节点 R 所有样本的二阶导数之和)

• λ 和 γ 是正则化参数。λ 用于 L2 正则化，γ 是剪枝系数，用于控制树的复杂度。

这个公式的核心思想是：分裂后的节点目标函数值之和应该尽可能地小于分裂前的节点目标函数值，并且要考虑到正则化项的惩罚。

精确贪心算法的优点:

• 精度高: 由于遍历了所有可能的分割点，因此可以找到理论上的最优分裂，从而构建出精度较高的决策树。

• 原理简单: 算法逻辑直观易懂，易于实现。

精确贪心算法的缺点:

• 计算量大: 当数据集较大，特征维度较高，且特征取值较多时，需要遍历所有可能的分割点，计算量非常大，效率较低。尤其是在分布式环境下，数据量巨大，精确贪心算法的效率瓶颈会更加明显。

• 容易过拟合: 在某些情况下，过于精确地寻找最优分裂点可能会导致模型在训练集上过拟合，泛化能力下降。

3. 精确贪心算法 (Exact Greedy Algorithm) 代码实践 (Python + NumPy)

为了更好地理解精确贪心算法，我们用 Python 和 NumPy 实现一个简化的版本。 为了突出核心逻辑，我们这里简化了 XGBoost 的目标函数和正则化项，使用简单的平方误差作为损失函数，并且不考虑正则化。

代码示例：

import numpy as np
def calculate_gain(y, y_pred, split_index):
    """
    计算分裂增益 (简化版本，使用平方误差损失)
    Args:
        y: 真实值 (NumPy array)
        y_pred: 当前节点的预测值 (NumPy array)
        split_index: 分裂点索引 (将数据分为左右两部分)
    Returns:
        gain: 分裂增益
    """
    if len(y) <= 1:  # 节点样本数太少，无法分裂
        return -np.inf
    y_left = y[:split_index]
    y_right = y[split_index:]
    y_pred_left = y_pred[:split_index]
    y_pred_right = y_pred[split_index:]
    if len(y_left) == 0 or len(y_right) == 0: # 分裂后子节点为空，无效分裂
        return -np.inf
    # 计算平方误差损失
    loss_parent = np.sum((y - y_pred)**2)
    loss_left = np.sum((y_left - np.mean(y_left))**2) # 简化预测值为均值
    loss_right = np.sum((y_right - np.mean(y_right))**2) # 简化预测值为均值
    gain = loss_parent - (loss_left + loss_right)
    return gain
def find_best_split(X, y, y_pred, feature_index):
    """
    为指定特征寻找最佳分裂点
    Args:
        X: 特征矩阵 (NumPy array)
        y: 真实值 (NumPy array)
        y_pred: 当前节点的预测值 (NumPy array)
        feature_index: 当前考虑的特征索引
    Returns:
        best_split_value: 最佳分裂点的值
        max_gain: 最大增益
    """
    feature_values = np.unique(X[:, feature_index]) # 获取特征的唯一值
    best_split_value = None
    max_gain = -np.inf
    for split_value in feature_values:
        split_index = np.where(X[:, feature_index] <= split_value)[0] # 获取分裂点的索引
        current_gain = calculate_gain(y, y_pred, len(split_index))
        if current_gain > max_gain:
            max_gain = current_gain
            best_split_value = split_value
    return best_split_value, max_gain
def exact_greedy_algorithm(X, y):
    """
    简化的精确贪心算法 (单层分裂，只找根节点最佳分裂)
    Args:
        X: 特征矩阵 (NumPy array)
        y: 真实值 (NumPy array)
    Returns:
        best_feature_index: 最佳分裂特征的索引
        best_split_value: 最佳分裂点的值
        max_gain: 最大增益
    """
    num_features = X.shape[1]
    best_feature_index = None
    best_split_value = None
    max_gain = -np.inf
    y_pred_root = np.mean(y) * np.ones_like(y) # 根节点初始预测值为均值
    for feature_index in range(num_features):
        split_value, gain = find_best_split(X, y, y_pred_root, feature_index)
        if gain > max_gain:
            max_gain = gain
            best_feature_index = feature_index
            best_split_value = split_value
    return best_feature_index, best_split_value, max_gain
# 示例数据
X = np.array([
    [1, 2],
    [2, 3],
    [3, 4],
    [4, 5],
    [5, 6],
    [6, 7],
    [7, 8],
    [8, 9],
    [9, 10],
    [10, 11]
])
y = np.array([10, 12, 14, 16, 18, 20, 22, 24, 26, 28])
# 运行精确贪心算法
best_feature_index, best_split_value, max_gain = exact_greedy_algorithm(X, y)
print(f"最佳分裂特征索引: {best_feature_index}")
print(f"最佳分裂点值: {best_split_value}")
print(f"最大增益: {max_gain}")
​

代码解释:

1. calculate_gain(y, y_pred, split_index): 这个函数计算分裂增益。为了简化，我们使用了平方误差损失，并且假设叶子节点的预测值是该节点样本真实值的均值。 实际 XGBoost 中，增益计算会更复杂，涉及到目标函数的一阶和二阶导数以及正则化项。

2. find_best_split(X, y, y_pred, feature_index): 这个函数针对指定的特征，遍历所有可能的特征值作为分裂点，调用 calculate_gain 函数计算增益，并找到最佳分裂点和最大增益。

3. exact_greedy_algorithm(X, y): 这是简化的精确贪心算法主函数。它遍历所有特征，调用 find_best_split 函数找到每个特征的最佳分裂点和增益，最终选择增益最大的特征和分裂点作为根节点的最佳分裂。

运行结果示例:

最佳分裂特征索引: 0
最佳分裂点值: 5
最大增益: 200.0
​

这个结果表明，对于示例数据，使用第一个特征 (索引为 0) 并在值 5 处分裂可以获得最大的增益。

代码局限性:

• 简化目标函数: 代码中使用了简化的平方误差损失，没有使用 XGBoost 实际使用的目标函数和正则化项。

• 单层分裂: 代码只实现了根节点的分裂，没有递归地构建完整的决策树。

• 效率较低: 即使是简化版本，当数据量较大时，效率仍然较低。

尽管存在局限性，这个代码示例仍然能够帮助理解精确贪心算法的核心思想和实现步骤。

4. Mermaid 图表可视化算法流程

为了更直观地理解精确贪心算法的流程，我们使用 Mermaid 的 graph TD 图表进行可视化。

图表解释:

• A (开始 - 根节点): 算法从树的根节点开始。

• B (遍历所有特征): 对于当前节点，算法遍历所有特征。

• C (遍历特征的所有分裂点): 对于每个特征，算法遍历该特征所有可能的取值作为分裂点。

• D (计算增益 (Gain)): 对于每个分裂点，计算分裂后的增益。 C1 & C2 详细展示了增益计算的步骤。

• E (比较增益并选择最佳分裂): 比较所有分裂点的增益，选择增益最大的分裂点作为当前节点的最优分裂。 E1 说明了最佳分裂的选择标准。

• F (分裂节点): 根据选定的最佳分裂点，将当前节点分裂成两个子节点。 F1 描述了节点分裂的具体操作。

• G (是否满足停止条件?): 判断是否满足预设的停止条件 (例如，树的最大深度、节点样本数阈值等)。 G1 列举了一些常见的停止条件。

  • 否 (No): 如果不满足停止条件，则返回步骤 B，继续对子节点进行分裂。

  • 是 (Yes): 如果满足停止条件，则算法结束，树构建完成。

• H (结束 - 树构建完成): 算法结束，决策树构建完成。

这个 Mermaid 图表清晰地展示了精确贪心算法的循环迭代过程和关键步骤，有助于读者更好地理解算法的执行流程。

5. 总结与展望

精确贪心算法是 XGBoost 中最基础的分裂节点查找算法。它通过穷举所有可能的特征和分裂点，精确地找到局部最优的分裂，从而构建出高精度的决策树。 然而，其计算效率较低是其主要的缺点。

为了解决精确贪心算法的效率问题，XGBoost 引入了更高效的分裂算法，例如：

• 近似贪心算法 (Approximate Greedy Algorithm): 通过分桶 (binning) 等方法，将连续特征值离散化，从而减少需要遍历的分裂点数量，提高算法效率。 这也是 XGBoost 2.4 分裂节点查找算法领域中 2.4.2 节的内容。

• 直方图算法 (Histogram Algorithm): 通过构建特征值的直方图，加速分裂点的查找和增益计算。

在实际应用中，XGBoost 通常会根据数据集的大小和特征类型，自动选择合适的算法。 对于大数据集和高维特征，近似贪心算法和直方图算法往往是更高效的选择。 而精确贪心算法更多地被用作理解分裂算法的基础，以及在小数据集上的应用。

理解精确贪心算法，对于深入学习 XGBoost 以及其他梯度提升算法至关重要。 掌握其原理和实现细节，能够帮助我们更好地理解模型的行为，并为模型调优和改进提供理论基础。

未来展望:

随着数据规模的持续增长，对高效分裂算法的需求也越来越高。 未来的研究方向可能包括：

• 更高效的近似算法: 探索更有效的近似方法，在保证精度的前提下，进一步提高算法效率。

• 硬件加速: 利用 GPU 等硬件加速技术，提升分裂算法的计算速度。

• 自适应分裂算法: 根据数据集的特点，自动选择最优的分裂算法，以达到效率和精度的最佳平衡。

总而言之，精确贪心算法作为 XGBoost 分裂节点查找算法的基石，其重要性不言而喻。 深入理解并掌握这一算法，将有助于我们更好地理解和应用 XGBoost，并在机器学习领域取得更大的成就。

2.4.2 近似贪心算法 (Approximate Greedy Algorithm)

以下是关于XGBoost近似贪心算法的详细文章：

XGBoost分裂节点查找算法：2.4.2 近似贪心算法 (Approximate Greedy Algorithm) 详解

引言

在梯度提升树（Gradient Boosting Tree, GBT）算法族中，XGBoost 以其高效性、灵活性和强大的性能而著称。构建决策树是 GBT 的核心步骤，而分裂节点查找算法则是构建决策树的关键环节，它直接影响着模型的训练速度和最终的预测精度。

2.4 分裂节点查找算法概述

在决策树的构建过程中，分裂节点查找算法的目标是找到最佳的分裂点，将节点的数据集划分为两个子节点，从而最大程度地降低损失函数，提升模型的预测能力。

XGBoost 主要提供了两种类型的分裂节点查找算法：

• 2.4.1 精确贪心算法 (Exact Greedy Algorithm): 也称为“全局扫描”算法，它会枚举所有可能的分裂点，并计算每个分裂点的增益，选择增益最大的分裂点作为最佳分裂点。精确贪心算法能够保证找到理论上的最优分裂点，但当数据量巨大或特征维度很高时，计算成本会非常高昂，难以应用于实际场景。

• 2.4.2 近似贪心算法 (Approximate Greedy Algorithm): 为了解决精确贪心算法在大数据场景下的效率瓶颈，XGBoost 引入了近似贪心算法。该算法不再枚举所有可能的分裂点，而是通过分桶 (Bucketing) 的方法，将连续特征值离散化到有限个桶 (bin) 中，然后仅考虑桶边界作为候选分裂点。这样大大减少了候选分裂点的数量，从而显著提升了算法的效率。

2.4.2 近似贪心算法 (Approximate Greedy Algorithm) 详解

近似贪心算法的核心思想是减少分裂点搜索空间，在保证一定精度的前提下，大幅度提升算法的运行速度。其主要步骤可以概括为：

1. 特征分桶 (Feature Bucketing / Quantile Sketch): 对于每个特征，算法会根据特征值的分布，将其划分为若干个桶 (bin)。常用的分桶方法是分位数略图 (Quantile Sketch) 算法，例如 Weighted Quantile Sketch。分位数略图能够在近似保持特征值分布信息的前提下，高效地选取桶边界。

2. 候选分裂点生成: 将每个桶的边界值作为候选分裂点。对于连续特征，桶边界可以是桶的最小值、最大值或中间值。

3. 候选分裂点评估: 对于每个候选分裂点，计算其分裂增益 (Split Gain)。分裂增益的计算方式与精确贪心算法类似，通常基于损失函数的下降量。XGBoost 使用的增益计算公式考虑了正则化项，以防止过拟合。

4. 最佳分裂点选择: 从所有候选分裂点中，选择分裂增益最大的分裂点作为当前节点的最优分裂点。

算法流程图 (Mermaid Graph)

详细步骤解析

1. 特征分桶 (Feature Bucketing / Quantile Sketch)

• 目的: 降低连续特征分裂点的数量，提高算法效率。

• 方法: 使用分位数略图算法，例如 Weighted Quantile Sketch。

• 原理: 分位数略图是一种数据概要表示方法，它能够在内存有限的情况下，近似地估计数据的分位数分布。在 XGBoost 中，Weighted Quantile Sketch 考虑了样本的权重 (例如二阶梯度)，更准确地反映了数据的重要性。

• 分桶策略: XGBoost 提供了两种分桶策略：

  • Global (全局分桶): 在树构建的初始阶段，对每个特征进行一次全局分桶。所有树的构建都使用相同的桶划分。这种方法计算量较小，但可能不够精细，尤其是在树的深度增加时。

  • Local (局部/按层分桶): 在每个节点分裂时，重新进行特征分桶。这种方法更加精细，能够更好地适应数据的局部特征分布，但计算成本更高。

• 参数控制: max_bin 参数控制每个特征的最大桶数。sketch_eps 参数控制分位数略图的近似精度，sketch_eps 越小，精度越高，桶边界越接近真实分位数，但计算成本也会增加。

2. 候选分裂点生成

• 桶边界作为候选点: 对于每个特征，将分桶后的桶边界值作为候选分裂点。例如，如果一个特征被划分为 10 个桶，则会有 9 个桶边界，这些边界值都将作为该特征的候选分裂点。

• 减少搜索空间: 相比于精确贪心算法枚举所有可能的特征值作为分裂点，近似贪心算法只考虑桶边界，大大减少了候选分裂点的数量。

3. 候选分裂点评估

• 分裂增益计算: 对于每个候选分裂点，需要计算其分裂增益。XGBoost 使用的增益计算公式如下 (简化版本)：

  Gain = G_parent^2 / (H_parent + lambda) - (G_left^2 / (H_left + lambda) + G_right^2 / (H_right + lambda)) - gamma
  ​

  其中：

  • G 和 H 分别是节点样本的一阶梯度和二阶梯度之和。

  • lambda 是 L2 正则化系数。

  • gamma 是树的复杂度惩罚系数。

  • parent, left, right 分别表示父节点、左子节点和右子节点。

• 高效的增益计算: XGBoost 使用了高效的数据结构 (例如稀疏感知的数据结构) 和算法优化 (例如预排序) 来加速分裂增益的计算过程。

4. 最佳分裂点选择

• 最大增益原则: 遍历所有候选分裂点，选择分裂增益最大的分裂点作为当前节点的最优分裂点。

• 节点分裂: 根据选择的最佳分裂点，将当前节点的数据集划分为左右两个子节点。

近似贪心算法的优势与劣势

优势:

• 效率提升: 通过分桶和减少候选分裂点，显著降低了算法的计算复杂度，尤其是在处理大规模数据集和高维特征时，效率提升非常明显。

• 内存占用降低: 分桶操作降低了存储特征值所需的内存空间。

• 可扩展性: 近似贪心算法更易于并行化和分布式计算，适用于处理超大规模数据集。

• 处理缺失值: 近似算法在分桶过程中可以自然地处理缺失值，例如将缺失值放入单独的桶中。

劣势:

• 精度损失: 由于只考虑桶边界作为候选分裂点，近似贪心算法可能会错过理论上的最优分裂点，导致一定的精度损失。精度损失的大小取决于分桶的粒度 (max_bin 参数) 和近似精度 (sketch_eps 参数)。

• 参数调优: 引入了额外的参数 (例如 max_bin, sketch_eps)，需要进行参数调优以平衡效率和精度。

代码实践 (Python + XGBoost)

以下代码示例展示了如何在 XGBoost 中使用近似贪心算法，并演示了相关参数的设置。

import xgboost as xgb
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
# 1. 生成模拟数据集
X, y = make_classification(n_samples=10000, n_features=20, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# 2. 定义 XGBoost 参数
params = {
    'objective': 'binary:logistic',
    'eval_metric': 'logloss',
    'tree_method': 'approx',  # 指定使用近似贪心算法
    'max_depth': 5,
    'learning_rate': 0.1,
    'subsample': 0.8,
    'colsample_bytree': 0.8,
    'min_child_weight': 1,
    'gamma': 0,
    'lambda': 1,
    'alpha': 0,
    'seed': 42,
    # 近似贪心算法相关参数
    'max_bin': 256,      # 最大桶数，默认 256
    'sketch_eps': 0.03,  # 分位数略图的近似精度，默认 0.03
}
# 3. 创建 DMatrix 数据格式
dtrain = xgb.DMatrix(X_train, label=y_train)
dtest = xgb.DMatrix(X_test, label=y_test)
# 4. 训练模型
model = xgb.train(params, dtrain, num_boost_round=100)
# 5. 预测
y_pred_proba = model.predict(dtest)
y_pred = (y_pred_proba > 0.5).astype(int)
# 6. 评估模型
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.4f}")
# 7. 探索参数的影响 (示例)
# 尝试调整 max_bin 和 sketch_eps 参数，观察对模型性能和训练时间的影响
params_high_bin = params.copy()
params_high_bin['max_bin'] = 512  # 增加桶数
params_low_eps = params.copy()
params_low_eps['sketch_eps'] = 0.1  # 降低近似精度
# ... (重复训练和评估，比较不同参数下的结果)
​

代码解释:

• tree_method='approx': 关键参数，显式指定 XGBoost 使用近似贪心算法。

• max_bin: 控制每个特征的最大桶数。增加 max_bin 可以提高分桶的粒度，更接近精确贪心算法，但会增加计算成本。默认值为 256。

• sketch_eps: 控制分位数略图的近似精度。减小 sketch_eps 可以提高精度，桶边界更接近真实分位数，但也会增加计算成本。默认值为 0.03。

• 参数调优: 可以通过实验调整 max_bin 和 sketch_eps 参数，找到在效率和精度之间的最佳平衡点。通常情况下，默认值已经能够提供较好的性能。

内容总结

近似贪心算法是 XGBoost 为了解决大规模数据集和高维特征场景下的效率问题而提出的重要算法。它通过特征分桶和分位数略图技术，有效地减少了候选分裂点的数量，显著提升了训练速度，并降低了内存占用。虽然近似贪心算法可能会带来一定的精度损失，但在实际应用中，通过合理的参数调优，通常可以在效率和精度之间取得良好的平衡。

结论

理解和掌握 XGBoost 的近似贪心算法对于提升模型训练效率，处理大规模数据至关重要。在面临大数据挑战时，合理选择和配置近似贪心算法及其相关参数，能够帮助我们更高效地构建强大的 XGBoost 模型。在实际应用中，需要根据具体的数据规模、计算资源和精度要求，权衡选择精确贪心算法和近似贪心算法，并进行相应的参数调优，以达到最佳的性能表现。近似贪心算法是 XGBoost 能够在众多机器学习算法中脱颖而出的关键技术之一，也是其在大数据领域广泛应用的重要支撑。

2.4.3 加权分位数略图 (Weighted Quantile Sketch)

XGBoost分裂节点查找算法之 2.4.3 加权分位数略图 (Weighted Quantile Sketch) 详解与实践

1. 引言：高效分裂节点查找的重要性

在梯度提升树（Gradient Boosting Tree, GBDT）算法族中，XGBoost以其卓越的性能和效率著称。构建高效的决策树是XGBoost成功的关键，而分裂节点查找则是构建决策树的核心环节。分裂节点查找的目标是从特征的所有可能取值中，找到最佳的分裂点，使得分裂后的子节点能够最大程度地降低损失函数。

对于连续型特征，遍历所有可能的取值进行分裂点评估的计算成本非常高，尤其是在数据量巨大和特征维度较高的情况下。为了解决这个问题，XGBoost引入了近似分裂节点查找算法，其中加权分位数略图（Weighted Quantile Sketch, WQS）是至关重要且高效的技术之一。

2. 分裂节点查找算法背景

在深入WQS之前，我们先简要回顾一下XGBoost中分裂节点查找算法的整体背景。XGBoost支持两种主要的分裂节点查找算法：

• 精确贪心算法 (Exact Greedy Algorithm): 枚举所有可能的特征分裂点，计算增益，选择最优分裂点。虽然精确，但在数据量大时效率极低。

• 近似贪心算法 (Approximate Greedy Algorithm): 为了提高效率，XGBoost引入近似算法。近似算法不再遍历所有可能的特征值，而是根据特征值的分布，选取少量的候选分裂点进行评估。

近似贪心算法又细分为两种模式：

• 全局近似 (Global Approximate): 在树构建的初始阶段，对每个特征预先计算一组候选分裂点（分位数），并在后续的树节点分裂中重复使用这组候选点。

• 局部近似 (Local Approximate): 在每次节点分裂时，重新计算当前节点的特征值分布，并基于此计算候选分裂点。

WQS主要服务于全局近似算法，用于高效地构建特征值的分位数略图，从而快速生成候选分裂点集合。

3. 分位数与分位数略图 (Quantile and Quantile Sketch)

3.1 分位数的概念

分位数 (Quantile) 是统计学中常用的概念，用于描述数据集的分布情况。例如，p-分位数是指将数据集排序后，位于 p% 位置的值。常见的有中位数 (0.5-分位数)、四分位数 (0.25, 0.5, 0.75-分位数) 等。

在分裂节点查找中，分位数可以作为候选分裂点的良好来源。直观上，将特征值按照分位数划分，可以大致将数据划分为不同区间，这些区间的边界点可以作为潜在的有效分裂点。

3.2 分位数略图 (Quantile Sketch) 的必要性

直接计算精确的分位数仍然需要对数据进行排序，当数据量非常大时，排序的开销依然不可忽视。此外，在分布式计算环境中，对海量数据进行全局排序和分位数计算更加复杂。

为了在效率和精度之间取得平衡，人们提出了分位数略图 (Quantile Sketch) 的概念。分位数略图是一种紧凑的数据概要表示，它可以在占用少量内存的情况下，近似地估计数据集的分位数。

分位数略图的核心思想是牺牲一定的精度来换取空间和时间的效率。它不需要存储所有的数据点，而是通过某种数据结构和算法，维护数据的概要信息，并能根据这些概要信息快速估计分位数。

4. 加权分位数略图 (Weighted Quantile Sketch) 的原理与算法

4.1 为什么需要加权分位数略图？

XGBoost在训练过程中，每个样本实例都带有权重。这个权重在GBDT的上下文中通常是损失函数关于模型预测值的二阶导数（Hessian 值）。在分裂节点查找时，我们需要考虑样本权重的影响。

普通的标准分位数略图 (例如 GK-Sketch, t-Digest 等) 主要针对无权重的均匀数据流设计。直接将标准分位数略图应用于XGBoost，忽略样本权重，可能会导致分裂点选择的偏差，从而影响模型性能。

因此，XGBoost 采用了 加权分位数略图 (Weighted Quantile Sketch)，专门用于处理带有权重的样本数据，更准确地估计加权数据的分位数。

4.2 加权分位数略图的核心思想

WQS的核心思想是在构建分位数略图时，不仅考虑特征值本身，还要考虑每个特征值对应的样本权重。WQS的目标是近似估计累积权重分布的分位数，而不是简单的特征值分布的分位数。

4.3 WQS 算法步骤详解

XGBoost使用的WQS算法，可以理解为一种基于数据压缩的分位数略图。其主要步骤如下：

1. 初始化略图 (Sketch Initialization):

   • 创建一个空的数据结构来存储略图。略图通常由一组 四元组 (value, weight, rank_min, rank_max) 构成。

   • value: 特征值。

   • weight: 与特征值关联的权重（例如 Hessian 值）。

   • rank_min: 特征值 value 在略图中可能的最小排序位置（基于累积权重）。

   • rank_max: 特征值 value 在略图中可能的最大排序位置（基于累积权重）。

   初始时，略图为空。

2. 数据点插入 (Data Point Insertion):

   • 当新的数据点 (feature_value, weight) 到达时，将其插入到略图中。

   • 对于第一个插入的数据点:

     • 创建四元组: (feature_value, weight, 0, weight).

     • rank_min 初始化为 0，rank_max 初始化为 weight。

   • 对于后续插入的数据点:

     • 找到略图中特征值大于等于 feature_value 的第一个四元组（按照特征值排序）。

     • 如果找到，则更新该四元组及其之后所有四元组的 rank_min 和 rank_max 值。

     • 如果没有找到，则说明 feature_value 是目前略图中最大的，更新最后一个四元组的 rank_max 值。

     • 将新的四元组 (feature_value, weight, previous_rank_max, previous_rank_max + weight) 插入到略图中，并保持略图按照特征值排序。其中 previous_rank_max 是插入位置之前四元组的 rank_max 值，如果是第一个元素则为0。

3. 略图压缩 (Sketch Compression / Reduction):

   • 随着数据点的不断插入，略图的大小会不断增长，占用更多内存。为了控制略图的大小，需要定期进行压缩操作。

   • 压缩的目的是在保证精度损失可接受的前提下，减少略图中四元组的数量。

   • 压缩策略: XGBoost的WQS采用一种基于最大误差的压缩策略。

     • 计算略图中相邻两个四元组 (v_i, w_i, r_min_i, r_max_i) 和 (v_{i+1}, w_{i+1}, r_min_{i+1}, r_max_{i+1}) 的潜在误差 (potential error)。

     • 潜在误差的计算方式通常与 rank_max_{i+1} - r_min_i 或类似的指标有关，目的是衡量合并这两个四元组可能造成的最大排序位置误差。

     • 遍历略图中的所有相邻四元组，找到潜在误差最小的一对。

     • 如果最小潜在误差小于某个阈值（例如，总权重的 ε 倍，ε 是一个预设的精度参数），则将这两个四元组合并。

     • 合并操作: 合并两个四元组 (v_i, w_i, r_min_i, r_max_i) 和 (v_{i+1}, w_{i+1}, r_min_{i+1}, r_max_{i+1}) 通常保留其中一个（例如，权重较大的那个）或取平均值，并更新其 rank_min 和 rank_max 值，使其能够尽可能准确地代表合并前两个四元组的权重分布信息。更简单的合并方式是直接移除其中一个四元组（例如，权重较小的那个）。XGBoost 的 WQS 具体合并策略可能需要参考其源代码。

     • 重复压缩过程，直到略图的大小满足要求或无法进一步压缩。

   • 压缩频率: 压缩操作可以在每插入一定数量的数据点后进行，或者当略图大小超过某个阈值时触发。

4. 分位数查询 (Quantile Query):

   • 当需要查询 p-分位数时（例如，用于生成候选分裂点），WQS可以根据略图中存储的四元组信息，近似估计 p-分位数。

   • 查询过程:

     • 计算目标累积权重: target_rank = p * total_weight，其中 total_weight 是所有样本权重的总和。

     • 遍历略图中的四元组，累加 weight 值。

     • 当累积权重 首次超过 target_rank 时，当前四元组的 value 值可以作为近似的 p-分位数。

     • 更精确的查询可能需要进行插值或其他更复杂的计算，但基本思想是根据累积权重来定位分位数。

4.4 WQS 的优势

• 高效性: WQS不需要存储所有数据点，只需要维护一个相对较小的略图。插入和查询操作都比较高效，尤其是在数据流式处理场景下。

• 内存效率: 略图的大小可以控制，内存占用较低，适合处理大规模数据集。

• 权重支持: WQS 能够有效地处理带权重的样本数据，更准确地估计加权数据的分位数，适用于 XGBoost 等需要考虑样本权重的算法。

• 近似精度可控: 通过调整压缩策略和精度参数 ε，可以在精度和效率之间进行权衡。

4.5 WQS 的局限性

• 近似精度: WQS 是一种近似算法，分位数估计结果并非完全精确。精度受到略图大小和压缩策略的影响。

• 参数调优: WQS 的性能受到精度参数 ε 等参数的影响，需要根据具体应用场景进行调优。

• 实现复杂度: WQS 的实现相对标准分位数计算略为复杂，需要仔细设计数据结构和压缩策略。

5. 代码实践：Python 实现加权分位数略图 (简化版)

为了更好地理解WQS的原理，我们用Python实现一个简化的加权分位数略图。为了代码简洁，我们这里实现一个基本的插入和查询功能，并采用一种简单的压缩策略。

import numpy as np
class WeightedQuantileSketch:
    def __init__(self, epsilon=0.01):
        self.epsilon = epsilon  # 精度参数
        self.sketch = []  # 存储四元组 (value, weight, rank_min, rank_max)
        self.total_weight = 0
    def insert(self, value, weight):
        if not self.sketch: # 初始情况
            self.sketch.append([value, weight, 0, weight])
        else:
            rank_before_insert = 0
            insert_index = len(self.sketch)
            for i in range(len(self.sketch)):
                if self.sketch[i][0] >= value:
                    insert_index = i
                    break
                rank_before_insert = self.sketch[i][3] # 前一个四元组的 rank_max
            self.sketch.insert(insert_index, [value, weight, rank_before_insert, rank_before_insert + weight])
            # 更新插入点之后四元组的 rank_min 和 rank_max
            for i in range(insert_index + 1, len(self.sketch)):
                self.sketch[i][2] += weight
                self.sketch[i][3] += weight
        self.total_weight += weight
        self.compress() # 插入后尝试压缩
    def compress(self):
        if len(self.sketch) <= 1:
            return
        compressed_sketch = [self.sketch[0]] # 保留第一个元素
        for i in range(1, len(self.sketch) - 1): # 遍历中间元素
            prev_tuple = compressed_sketch[-1]
            current_tuple = self.sketch[i]
            next_tuple = self.sketch[i+1]
            error = next_tuple[3] - prev_tuple[2] - current_tuple[1] # 简化误差计算
            if error > self.epsilon * self.total_weight: # 如果误差超过阈值，则保留当前元素
                compressed_sketch.append(current_tuple)
        compressed_sketch.append(self.sketch[-1]) # 保留最后一个元素
        self.sketch = compressed_sketch
    def query(self, p):
        target_rank = p * self.total_weight
        cumulative_weight = 0
        for tuple_data in self.sketch:
            cumulative_weight += tuple_data[1]
            if cumulative_weight >= target_rank:
                return tuple_data[0] # 返回近似分位数
        return self.sketch[-1][0] # 极端情况，返回最大值
# 示例使用
wqs = WeightedQuantileSketch(epsilon=0.05)
data_values = [10, 5, 8, 12, 3, 9, 15, 6, 11, 7]
data_weights = [2, 1, 3, 2, 1, 2, 3, 1, 2, 1]
for value, weight in zip(data_values, data_weights):
    wqs.insert(value, weight)
print("Sketch after insertion:")
for tuple_data in wqs.sketch:
    print(tuple_data)
print("\nApproximate 0.5-quantile:", wqs.query(0.5)) # 中位数
print("Approximate 0.9-quantile:", wqs.query(0.9)) # 90% 分位数
​

代码解释:

• WeightedQuantileSketch 类实现了加权分位数略图。

• __init__ 初始化精度参数 epsilon 和空的略图 sketch。

• insert(value, weight) 方法插入数据点，维护四元组，并调用 compress 进行压缩。

• compress() 方法实现了简化的压缩策略，基于误差阈值合并相邻四元组。

• query(p) 方法查询 p-分位数，遍历略图并根据累积权重定位近似分位数。

• 示例代码演示了如何使用 WeightedQuantileSketch 插入数据并查询分位数。

注意: 这只是一个简化的实现，用于演示WQS的基本原理。XGBoost中实际使用的WQS实现可能更复杂，包含更精细的压缩策略和误差控制机制。实际应用中，建议参考XGBoost的源代码或使用成熟的WQS库。

6. Mermaid Graph TD 图：WQS 算法流程可视化

使用 Mermaid 绘制 WQS 算法流程的 Graph TD 图，更直观地展示算法步骤：

Graph TD 图解释:

• 数据插入流程: 从数据点到达开始，经过插入、更新 rank 值、压缩等步骤。

• 分位数查询流程: 从分位数查询请求开始，计算目标累积权重，遍历略图，最终返回近似分位数。

• 图中清晰地展示了 WQS 算法的主要流程和步骤。

7. WQS 在 XGBoost 中的应用

在 XGBoost 的近似贪心分裂节点查找算法中，WQS 主要用于以下步骤：

1. 构建候选分裂点集合: 对于每个特征，XGBoost 使用 WQS 近似计算特征值的若干个分位数（例如，ε-分位数）。这些分位数被作为该特征的候选分裂点。

2. 评估候选分裂点: 对于每个候选分裂点，计算分裂后的增益 (Gain)。

3. 选择最佳分裂点: 从所有候选分裂点中，选择增益最大的分裂点作为当前节点的最优分裂点。

WQS 的应用使得 XGBoost 可以在不遍历所有特征值的情况下，高效地找到近似最优的分裂点，从而大大加速了树的构建过程，尤其是在处理大规模数据集时。

8. 总结与展望

加权分位数略图 (Weighted Quantile Sketch) 是 XGBoost 中一项重要的技术，它在近似贪心分裂节点查找算法中发挥着关键作用。WQS 能够高效地处理带权重的样本数据，近似计算特征值的分位数，并生成高质量的候选分裂点集合。

通过使用 WQS，XGBoost 在保证模型性能的同时，显著提高了训练效率，使其能够更好地应对大规模机器学习任务的挑战。

未来，随着数据规模的持续增长和计算环境的不断演进，分位数略图技术仍然具有重要的研究价值和应用前景。例如，可以探索更高效的压缩策略、更精确的误差控制机制，以及与其他近似算法的结合，进一步提升机器学习算法的效率和可扩展性。

希望本文能够帮助您深入理解 XGBoost 中加权分位数略图的原理、算法和应用，并能启发您在实际项目中灵活运用相关技术。