XGBoost算法-确定树的结构

我们在求解上面的w和obj的过程中，都是假定我们的树结构是确定的，因为当我们改变树中划分条件的时候，每个叶子节点对应的样本有可能是不一样的，我们的G和H也是不一样的，得到的最优w和最优obj肯定也是不一样的。

到底哪一棵回归树的划分方式是最优的呢？很明显，obj最小的回归树肯定是最合理的，所以我们需要找出导致obj最小的那颗回归树。

穷举法

首先我们能想到的就是把所有的可能性都枚举一遍，都计算一遍，分别求出最小obj，然后找出最好的树结构【划分方式】，但是没有啥实用价值，运算量太大【叶子节点数量也要穷举】。

精确贪心算法大致过程

树模型的学习策略，整体的思想就是分步+贪婪

首先我们将一棵树看做是一个个节点分裂而来的过程，第一步我们有一个根节点，根节点要做分裂，之后继续，每一步都对应一个节点的分裂，所以我们每次仅需要关心一个节点怎么分裂就可以了。

如何对一个节点进行划分？

假设一个节点进行划分前，含有5个样本ABCDE，经过某一个划分条件后，会将其落入左右两个节点，比如左节点AB，右节点CDE。对于一个节点而言，其中每一个样本对应的gi和hi我们都是知道的，那么也就意味着，每一个节点的Gi和Hi我们都是可以计算出来的。所以这个节点对应的最优的w和最小obj我们也是可以直接计算出来的。

因为最开始只有一个节点，所以T = 1，可以写成：

那么同样的道理，我们在分裂之后，左节点AB和右节点CDE每个样本的gi和hi也是知道的，Gi和Hi，以及w和obj也是可以计算出来的，分裂前和分裂后的obj都可以计算出来的。并且划分条件不同的时候，我们会得到不同的树结构，得到不同的分裂后的obj。

那么左右两次我们应该取哪个数结构作为根节点分裂的方式呢？我们可以利用增益gain判断，采用不同的算法，增益是不同的。ID3算法就是采用信息增益作为衡量指标，分类树采用的是基尼指数作为衡量指标。

不同的分裂方式会给我们带来不同的增益，在不同的算法中，使用衡量指标不同。

xgboost算法中，衡量指标直接利用前后obj的差值作为衡量指标，用obj前-obj后，当增益越大，表示损失下降的越多，表示当前的划分就越好。

所以我们需要计算每一种分裂方式的增益，从其中选出一个增益最大的数结构作为下一次分裂方式。

公式代入后，可以计算为【计算每一种分裂方式的gain，找出最大的gain】

每一步取最大，这种方式就是贪婪【贪心】的思想，后续的节点分裂同上。

那么什么时候就么有必要继续分裂了呢？

• 当最大的max gain 小于等于0【或者其他值】，表示损失已经几乎不再下降，没有必要继续分裂
• 当叶子节点个数包含样本个数小于等于1个的时候，分裂也没有意义了
• 限制叶子节点的个数，防止过拟合

精确贪心算法具体代码实现

我们看下具体的代码实现部分

其中：

• input中的I表示的本次要分裂节点中的样本集合
• input中的d表示特征的维度，有多少个特征
• 初始化的时候，gain为0，我们需要计算当前节点的G和H是多少
• for循环中，k=1表示第一个特征，k=2表示第二个特征

• • 当选用第一个特征作为划分条件的时候k=1
  • 令GL=0，HL=0
  • 然后到了第二层循环，针对特征一重新排序

• • • j表示每一个样本
    • 当我们确定1作为划分条件的时候，分裂后左侧就会有BD，右侧就会有AEC

• • • • 每一个样本都对应自己的gi和hi
      • 我们就可以计算出GL和GR、HL和HR
      • 进而可以计算出Gain

• • • 当我们确定2作为划分条件时候，分裂后左侧有BDAE，右侧有C
    • 。。。

• • 当选用第二个特征作为划分条件时候。。。。

• 从上面所有的gain中找出最大的gain

综上：先遍历每一个特征，然后对特征进行排序。当特征非常多的时候，或者某一个特征内部枚举值非常多的时候，排序操作是非常耗费时间，有么有办法进行优化呢？精确贪心算法可以得到较为精确的计算，但是非常耗费时间。

优化思路

• 压缩特征个数；
• 对应每一个特征，减少特征值的数量，采样；
• 提高了速度，精确性是有减弱的