问题一：
我对 LightGBM关于树扩展方式的描述感到困惑。
他们说：
大多数决策树学习算法逐级（深度）地生长树，如下图所示：
问题1：以这种方式实现哪些“大多数”算法？据我所知，C4.5 和 CART 使用 DFS。XGBoost 使用 BFS。哪些其他算法或包使用 BFS 来构建决策树？
问题 2：
LightGBM 状态：
LightGBM 逐叶（最佳优先）生长树。它将选择具有最大 delta 损失的叶子来生长。当生长相同的叶子时，leaf-wise 算法可以比 level-wise 算法减少更多的损失。
问题 2：说水平生长的树对所有叶子都有相同的深度是否正确？
问题 3：如果问题 2 不正确，那么在遍历结束时，水平生长和叶生长的树看起来是一样的（没有修剪等）。这是一个正确的说法吗？
问题4：如果问题3正确，“leaf-wise algorithm比level-wise algorithm减少更多损失”如何？它与后修剪算法有关吗？
如果你生长完整的树，最佳优先（叶子）和深度优先（层次）将产生相同的树。不同之处在于树的展开顺序。由于我们通常不会将树木生长到最大深度，因此顺序很重要：应用早期停止标准和修剪方法可能会导致非常不同的树木。因为 Leaf-wise 根据它们对全局损失的贡献来选择拆分，而不仅仅是沿特定分支的损失，它通常（并非总是）会比 level-wise “更快”地学习低错误树。即，对于少数节点，叶子方式的性能可能会优于水平方式。随着您添加更多节点，无需停止或修剪，它们将收敛到相同的性能，因为它们最终将真正构建相同的树。
参考：
石河（2007）。最佳优先决策树学习（论文，理学硕士 (MSc)）。怀卡托大学，新西兰汉密尔顿。取自https://hdl.handle.net/10289/2317
编辑：关于你的第一个问题，C4.5 和 CART 都是深度优先的例子，而不是最好的例子。以下是上述参考资料中的一些相关内容：
1.2.1 标准决策树
标准算法，例如 C4.5 (Quinlan, 1993) 和 CART (Breiman et al., 1984)，用于决策树的自上而下归纳，使用分治策略在每个步骤中以深度优先顺序扩展节点。通常，在决策树的每个节点上，测试只涉及单个属性，并且将属性值与常数进行比较。标准决策树的基本思想是，首先，选择一个属性放置在根节点，并根据一些标准（例如信息或基尼指数）为该属性创建一些分支。然后，将训练实例拆分为子集，每个子集用于从根节点扩展的每个分支。子集的数量与分支的数量相同。然后，对选定的分支重复此步骤，仅使用实际到达它的那些实例。一个固定的顺序用于扩展节点（通常，左到右）。如果在任何时候一个节点上的所有实例都具有相同的类标签，称为纯节点，则分裂停止并且该节点成为终端节点。这个构建过程一直持续到所有节点都是纯的。然后是修剪过程以减少过度拟合（参见第 1.3 节）。
1.2.2 最佳优先决策树
另一种可能性，到目前为止似乎只在提升算法的背景下进行了评估（Friedman 等人，2000），即以最佳优先顺序而不是固定顺序扩展节点。此方法在每个步骤中将“最佳”拆分节点添加到树中。“最佳”节点是在所有可用于分裂的节点中最大程度地减少杂质的节点（即未标记为终端节点）。尽管这会产生与标准深度优先扩展相同的完全成熟的树，但它使我们能够研究使用交叉验证来选择扩展数量的新树修剪方法。预剪枝和后剪枝都可以以这种方式进行，这样可以在它们之间进行公平比较（参见第 1.3 节）。
最佳优先决策树以类似于标准深度优先决策树的分而治之的方式构建。如何构建最佳优先树的基本思想如下。首先，选择一个属性放置在根节点，并根据一些标准为这个属性做一些分支。然后，将训练实例拆分为子集，每个子集用于从根节点扩展的每个分支。在本文中只考虑二叉决策树，因此分支的数量正好是两个。然后，对选定的分支重复此步骤，仅使用实际到达它的那些实例。在每个步骤中，我们从所有可用于扩展的子集中选择“最佳”子集。这个构建过程一直持续到所有节点都是纯节点或达到特定数量的扩展。图1。图 1 显示了假设的二叉最佳优先树和假设的二叉深度优先树之间的拆分顺序差异。请注意，可以为最佳优先树选择其他顺序，而在深度优先的情况下顺序始终相同。