|
切分算法（切分点的选取）
占用的内存更低，只保存特征离散化后的值，而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8
LightGBM直接支持类别特征
决策树生长策略不同
? ? ? ?XGBoost采用的是带深度限制的level-wise生长策略。level-wise过一次数据可以能够同时分裂同一层的叶子，容易进行多线程优化，不容易过拟合；但不加区分的对待同一层叶子，带来了很多没必要的开销（实际上很多叶子的分裂增益较低，没必要进行搜索和分裂）
? ? ? ?LightGBM采用leaf-wise生长策略，每次从当前所有叶子中找到分裂增益最大（数据量最大）的一个叶子，进行分裂，如此循环；但会生长出比较深的决策树，产生过拟合（因此LightGBM在leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合）
原始的GBDT算法基于经验损失函数的负梯度来构造新的决策树，
只是在决策树构建完成后再进行剪枝。而XGBoost在决策树构建阶段就
加入了正则项，即
XGBoost需要从所有的树结构中找出一个最优的树结构，这是一个NP-hard问题，因此在实际中通常采用贪心算法来构建一个次优的树结构，基本思想是从根节点开始，每次对一个叶子节点进行分裂，针对每一种可能的分裂，根据特定的准则选取最优的分裂。不同的决策树算法采用不同的准则，如IC3算法采用信息增益，C4.5算法为了克服信息增益中容易偏向取值较多的特征而采用信息增益比，CART算法使用基尼指数和平方误差，XGBoost也有特定的准则来选取最优分裂。
?
GBDT 虽然是个强力的模型，但却有着一个致命的缺陷，不能用类似 mini batch 的方式来训练，需要对数据进行无数次的遍历。如果想要速度，就需要把数据都预加载在内存中，但这样数据就会受限于内存的大小；如果想要训练更多的数据，就要使用外存版本的决策树算法。虽然外存算法也有较多优化，SSD 也在普及，但在频繁的 IO 下，速度还是比较慢的。
为了能让 GBDT 高效地用上更多的数据，我们把思路转向了分布式 GBDT， 然后就有了 LightGBM。设计的思路主要是两点，1. 单个机器在不牺牲速度的情况下，尽可能多地用上更多的数据；2.
多机并行的时候，通信的代价尽可能地低，并且在计算上可以做到线性加速。
基于这两个需求，LightGBM 选择了基于 histogram 的决策树算法。相比于另一个主流的算法 pre-sorted（如 xgboost 中的 exact 算法），histogram 在内存消耗和计算代价上都有不少优势。
- Pre-sorted 算法需要的内存约是训练数据的两倍(2 * #data * #features
* 4Bytes)，它需要用32位浮点来保存 feature value，并且对每一列特征，都需要一个额外的排好序的索引，这也需要32位的存储空间。对于 histogram 算法，则只需要(#data
* #features * 1Bytes)的内存消耗，仅为 pre-sorted算法的1/8。因为 histogram 算法仅需要存储 feature bin value (离散化后的数值)，不需要原始的 feature value，也不用排序，而 bin value 用 uint8_t (256 bins) 的类型一般也就足够了。
|