Lightgbm原理、参数详解及python实例
预备知识：GDBT
1)对所有特征都按照特征的数值进⾏预排序。
fengyu2)在遍历分割点的时候⽤O(#data)的代价找到⼀个特征上的最好分割点。
3)找到⼀个特征的分割点后，将数据分裂成左右⼦节点。
crv是什么意思LightGBM
LightGBM是个快速的，分布式的，⾼性能的基于决策树算法的梯度提升框架。可⽤于排序，分类，回归以及很多其他的机器学习任务中。
情人节为什么送巧克力●训练时样本点的采样优化：保留梯度较⼤的样本
●特征维度的优化：互斥特征绑定与合并
●决策树⽣成：特征分割，⽣长策略
●直接处理类别特征：统计类别数量
优点：
1、 更快的训练速度和更⾼的效率：GOSS算法，EFB算法、基于直⽅图的算法；
2、 降低内存使⽤：使⽤离散的箱⼦(bins)保存并替换连续值
3、 精度更⾼：leaf-wi分裂⽅法，同时使⽤max-depth 参数防⽌过拟合
4、 ⽀持并⾏和GPU学习
itouch游戏
5、 能够处理⼤规模数据
使⽤GOSS算法和EFB算法的梯度提升树（GBDT）称之为LightGBM。
bbc
在更⾼的处理效率和较低的内存前提下，不降低精度
⼀、原理
1.单边梯度采样算法（Grandient-bad One-Side Sampling，GOSS）
核⼼作⽤：训练集样本采样优化
扫帚拼音1）保留梯度较⼤的样本；
2） 对梯度较⼩的样本进⾏随机抽样；
3）在计算增益时，对梯度较⼩的样本增加权重系数.
算法描述：
输⼊：训练数据，迭代步数d，⼤梯度数据的采样率a，⼩梯度数据的采样率b，损失函数和若学习器
的类型（⼀般为决策树）；输出：训练好的强学习器；
（1）根据样本点的梯度的绝对值进⾏降序排序；
gatherer
（2）对排序后的结果选取前a*100%的样本⽣成⼀个⼤梯度样本点的⼦集；
adele 21（3）对剩下的样本集合（1-a）100%的样本，随机的选取b（1-a）*100%个样本点，⽣成⼀个⼩梯度样本点的集合；
（4）将⼤梯度样本和采样的⼩梯度样本合并；
（5）使⽤上述的采样的样本，学习⼀个新的弱学习器；
（6）在新的弱学习器中，计算增益时将⼩梯度样本乘上⼀个权重系数（1-a)/b；
（7）不断地重复（1）~（6）步骤直到达到规定的迭代次数或者收敛为⽌。
2.Exclusive Feature Bundling 算法(EFB)
核⼼作⽤：特征抽取，将互斥特征（⼀个特征值为零,⼀个特征值不为零）绑定在⼀起，从⽽减少特征维度。
小的英文
算法3：确定哪些特征被捆绑；
算法4：怎样合并被捆绑特征
算法3描述：
输⼊：特征F，最⼤冲突数K，图G；
输出：特征捆绑集合bundles；
（1）构造⼀个边带有权重的图，其权值对应于特征之间的总冲突；
（2）通过特征在图中的度来降序排序特征；
（3）检查有序列表中的每个特征，并将其分配给具有⼩冲突的现有bundling（由控制），或创建新bundling。
更⾼效EBF的算法步骤如下：
1）将特征按照⾮零值的个数进⾏排序
2）计算不同特征之间的冲突⽐率
3）遍历每个特征并尝试合并特征（Histogram算法），使冲突⽐率最⼩化
参考⽂献：/qq_24519677/article/details/82811215
3.直⽅图算法（Histogram算法）
3.1 核⼼思想：
将连续的特征值离散化成K个整数（bin数据），构造宽度为K的直⽅图，遍历训练数据，统计每个离散值在直⽅图中的累积统计量。在选取特征的分裂点的时候，只需要遍历排序直⽅图的离散值。
● 使⽤bin替代原始数据相当于增加了正则化；
● 使⽤bin很多数据的细节特征被放弃，相似的数据可能被划分到⼀起，数据之间的差异消失；
thank you 什么意思
● bin数量的选择决定了正则化的程度，K越少惩罚越严重，⽋拟合风险越⾼
3.2 直⽅图加速
⼀个叶⼦的直⽅图可以由它的⽗亲节点的直⽅图与它兄弟的直⽅图做差得到。通常构造直⽅图，需要遍历该叶⼦上的所有数据，但直⽅图做差仅需遍历直⽅图的k个桶。
3.3 合并被绑定特征
将bundle内不同的特征加上⼀个偏移常量，使不同特征的值分布到bundle的不同bin内。例如：特征A的取值范围为[0,10)，特征B的原始取值范围为[0，20)，对特征B的取值上加⼀个偏置常量10，将其取值范围变为[10,30)，这样就可以将特征A和B绑定在⼀起了。
4、决策树⽣长策略
level_wi：多线程优化，控制模型复杂度，不易过拟合。
leaf-wi：计算代价较⼩，更精确，易过拟合（map_depth）。
LightGBM采⽤leaf-wi⽣长策略，每次从当前所有叶⼦中找到分裂增益最⼤（⼀般也是数据量最⼤）的⼀个叶⼦，然后分裂，如此循环。因此同Level-wi相⽐，在分裂次数相同的情况下，Leaf-wi可以降低更多的误差，得到更好的精度。Leaf-wi的缺点是可能会长出⽐较深的决策树，产⽣过拟合。因此LightGBM在Leaf-wi之上增加了⼀个map_depth的限制，在保证⾼效率的同时防⽌过拟合。
5.直接处理类别特征
详细流程：
1、离散特征建⽴直⽅图的过程
统计该特征下每⼀种**离散值出现的次数，并从⾼到低排序，**并过滤掉出现次数较少的特征值, 然后为每⼀个特征值，建⽴⼀个bin容器, 对于在bin容器内出现次数较少的特征值直接过滤掉，不建⽴bin容器。
2、计算分裂阈值的过程：
2.1 先看该特征下划分出的bin容器的个数，如果bin容器的数量⼩于4，直接使⽤one vs other⽅式, 逐个扫描每⼀个bin容器，找出最佳分裂点;
2.2 对于bin容器较多的情况, 先进⾏过滤，只让⼦集合较⼤的bin容器参加划分阈值计算, 对每⼀个符合条件的bin容器进⾏公式计算(公式如下: 该bin容器下所有样本的⼀阶梯度之和 / 该bin容器下所有样本的⼆阶梯度之和 + 正则项(参数cat_smooth)，这⾥为什么不是label的均值呢？其实上例中只是为了便于理解，只针对了学习⼀棵树且是回归问题的情况， 这时候⼀阶导数是Y, ⼆阶导数是1)，得到⼀个值，根据该值对bin容器从⼩到⼤进⾏排序，然后分从左到右、从右到左进⾏搜索，得到最优分裂阈值。但是有⼀点，没有搜索所有的bin容器，⽽是设定了⼀个搜索bin容器数量的上限值，程序中设定是32，即参数max_num_cat。
LightGBM中对离散特征实⾏的是many vs many 策略，这32个bin中最优划分的阈值的左边或者右边所有的bin容器就是⼀个many集合，⽽其他的bin容器就是另⼀个many集合。
2.3 对于连续特征，划分阈值只有⼀个，对于离散值可能会有多个划分阈值，每⼀个划分阈值对应着⼀个bin容器编号，当使⽤离散特征进⾏分裂时，只要数据样本对应的bin容器编号在这些阈值对应的bin集合之中，这条数据就加⼊分裂后的左⼦树，否则加⼊分裂后的右⼦树。
