我相信xgboost 论文在这一点上有点不够精确，但我会分享我对他们所描述内容的解释。这种理解不是基于阅读代码，所以对它持保留态度，并希望有一个更勇敢的灵魂对这个答案提出更好的观点（我发现这是因为我在阅读论文后也有它）。

讨论选择分割点的近似算法的导言说

. . . 拆分查找算法枚举所有特征上所有可能的拆分"

然后继续说这种详尽的搜索对于大型数据集是不可行的，并且与分布式训练也不能很好地交互，因此需要一个近似算法。该算法在附录中进行了详细描述，它（我相信）专门用于查找给定特征的候选分割点的算法。

他们对如何使用这种近似算法的描述说

综上所述，该算法首先根据特征分布的百分位数提出候选分裂点（具体标准将在 3.3 节中给出）。然后，该算法将连续特征映射到由这些候选点分割的桶中，聚合统计信息并根据聚合统计信息在提案中找到最佳解决方案。

我相信这意味着为数据集中的每个特征提出候选分割，并且检查所有这些候选分割以找到最佳分割。这意味着寻找分割的方法实际上是算法的一种近似形式，它检查每一个特征和每一个分割以找到最好的，但近似只发生在为每个特征提出的分割水平上。仍然检查每个功能。

完整的算法在xgboost论文中进行了概述，该论文还提供了以下摘要：

我们在 Alg. 中总结了一个近似框架，类似于过去文献中提出的想法。2.综上所述，该算法首先根据特征分布的百分位数提出候选分裂点（具体标准将在3.3节给出）。然后，该算法将连续特征映射到由这些候选点分割的桶中，聚合统计信息并根据聚合统计信息在提案中找到最佳解决方案。

由于它是从一组建议的解决方案中找到最佳解决方案（特征和拆分），我们可以推断它（大约）优化了某些指标，并且特征和拆分的选择不是随机的。论文中提供了更完整的信息。

还值得注意的是，随机森林并不是简单地随机选择特征——对于每个分割，随机森林选择一个特征子集，然后从随机子集中选择最好的分割。

XgBoost 的分割算法是预先排序的和直方图（这是乔尔在他的回答中描述的）。如果您使用这些关键字进行搜索，您会更好地理解它们。另外，我的理解是，为了找出最佳分割，Xgboost 使用从目标函数的导数获得的方程对分割候选进行评分。