优化点： 在进行梯度提升的时，样本的梯度是不一样的，每次对大量足够小梯度的样本进行决策点寻找造成效率不高。

方法： 对梯度小的样本进行降采样。

具体：

对于每一次树的迭代，对样本梯度的绝对值进行倒序，前a*100%为梯度较高的样本。对剩余的(1-a)*%进行采样，假设采样样本占比为全体样本的 b*100%。

在计算information gain时对该类样本进行 (1-a)/b 倍的调整，以保持整体的稳定。

评价： 整体提升效果比较好。不是非常好的原因是每次迭代需要进行额外的计算。

优化点：大量的稀疏特征，特征下非常少的非0元素，如果每次增益计算都进行则占用许多计算量。

方法：把互斥的特征合并在一起，降低特征的维度。

具体：把features => bundles。  找到最优的即把特征合并到最低维度是NP-hard问题，即多项式时间无法解决。

两个方法

a. 构建features Graph，其中边的权重是两个特征冲突数量的个数，然后对节点根据degrees进行倒排。

对features进行合并，直到达到冲突阈值γ，建立新的bundle。

这种方法需要在训练前进行预处理，需要花费O(sqare(#feature)) 的时间。 当特征数量不是很多的时候是可以接受的。

b. 认为非零元素多的特征越容易产生冲突。直接对特征进行非零元素个数进行排序。然后进行合并。

bundles特征值：

多个feature合并到一个bundle后存在特征值问题。解决方法是，进行数据偏移。因为树模型不是基于距离的。

比如：bundle中包含a、b两个特征。a特征范围是[0,10)，b特征范围是[0,20)，那么把b特征值改为[10,30)，即10+原来的b。

评价：EFB有巨大的提升。