Py学习  »  机器学习算法

机器学习算法之LightGBM

biaodianfu • 5 年前 • 764 次点击  

上一篇文章介绍了一个梯度提升决策树模型XGBoost,这篇文章我们继续学习一下GBDT模型的另一个进化版本:LightGBM。LigthGBM是boosting集合模型中的新进成员,由微软提供,它和XGBoost一样是对GBDT的高效实现,原理上它和GBDT及XGBoost类似,都采用损失函数的负梯度作为当前决策树的残差近似值,去拟合新的决策树。

LightGBM在很多方面会比XGBoost表现的更为优秀。它有以下优势:

  • 更快的训练效率
  • 低内存使用
  • 更高的准确率
  • 支持并行化学习
  • 可处理大规模数据
  • 支持直接使用category特征

从下图实验数据可以看出, LightGBM比XGBoost快将近10倍,内存占用率大约为XGBoost的1/6,并且准确率也有提升。

看完这些惊人的实验结果以后,对下面两个问题产生了疑惑:XGBoost已经十分完美了,为什么还要追求速度更快、内存使用更小的模型?对GBDT算法进行改进和提升的技术细节是什么?

提出LightGBM的动机

常用的机器学习算法,例如神经网络等算法,都可以以mini-batch的方式训练,训练数据的大小不会受到内存限制。而GBDT在每一次迭代的时候,都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小;如果不装进内存,反复地读写训练数据又会消耗非常大的时间。尤其面对工业级海量的数据,普通的GBDT算法是不能满足其需求的。

LightGBM提出的主要原因就是为了解决GBDT在海量数据遇到的问题,让GBDT可以更好更快地用于工业实践。

XGBoost的优缺点

精确贪心算法

每轮迭代时,都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小;如果不装进内存,反复地读写训练数据又会消耗非常大的时间。

优点:

  • 可以找到精确的划分条件

缺点:

  • 计算量巨大
  • 内存占用巨大
  • 易产生过拟合

Level-wise迭代方式

预排序方法(pre-sorted):首先,空间消耗大。这样的算法需要保存数据的特征值,还保存了特征排序的结果(例如排序后的索引,为了后续快速的计算分割点),这里需要消耗训练数据两倍的内存。其次时间上也有较大的开销,在遍历每一个分割点的时候,都需要进行分裂增益的计算,消耗的代价大。

优点:

  • 可以使用多线程
  • 可以加速精确贪心算法

缺点:

  • 效率低下,可能产生不必要的叶结点

对cache优化不友好

在预排序后,特征对梯度的访问是一种随机访问,并且不同的特征访问的顺序不一样,无法对cache进行优化。同时,在每一层长树的时候,需要随机访问一个行索引到叶子索引的数组,并且不同特征访问的顺序也不一样,也会造成较大的cache miss。

LightGBM在哪些地方进行了优化?

以上与其说是XGBoost的不足,倒不如说是LightGBM作者们构建新算法时着重瞄准的点。解决了什么问题,那么原来模型没解决就成了原模型的缺点。

概括来说,lightGBM主要有以下特点:

  • 基于Histogram的决策树算法
  • 带深度限制的Leaf-wise的叶子生长策略
  • 直方图做差加速
  • 直接支持类别特征(Categorical Feature)
  • Cache命中率优化
  • 基于直方图的稀疏特征优化
  • 多线程优化

决策树算法

XGBoost使用的是pre-sorted算法,能够更精确的找到数据分隔点。

  • 首先,对所有特征按数值进行预排序。
  • 其次,在每次的样本分割时,用O(# data)的代价找到每个特征的最优分割点。
  • 最后,找到最后的特征以及分割点,将数据分裂成左右两个子节点。

这种pre-sorting算法能够准确找到分裂点,但是在空间和时间上有很大的开销。

  • 由于需要对特征进行预排序并且需要保存排序后的索引值(为了后续快速的计算分裂点),因此内存需要训练数据的两倍。
  • 在遍历每一个分割点的时候,都需要进行分裂增益的计算,消耗的代价大。

LightGBM使用的是histogram算法,占用的内存更低,数据分隔的复杂度更低。其思想是将连续的浮点特征离散成k个离散值,并构造宽度为k的Histogram。然后遍历训练数据,统计每个离散值在直方图中的累计统计量。在进行特征选择时,只需要根据直方图的离散值,遍历寻找最优的分割点。

使用直方图算法有很多优点。首先最明显就是内存消耗的降低,直方图算法不仅不需要额外存储预排序的结果,而且可以只保存特征离散化后的值,而这个值一般用8位整型存储就足够了,内存消耗可以降低为原来的1/8。

然后在计算上的代价也大幅降低,预排序算法每遍历一个特征值就需要计算一次分裂的增益,而直方图算法只需要计算k次(k可以认为是常数),时间复杂度从O(#data*#feature)优化到O(k*#features)。

Histogram algorithm

Histogram algorithm应该翻译为直方图算法,直方图算法的思想也很简单,首先将连续的浮点数据转换为bin数据,具体过程是首先确定对于每一个特征需要多少的桶bin,然后均分,将属于该桶的样本数据更新为bin的值,最后用直方图表示。(看起来很高大上,其实就是直方图统计,最后我们将大规模的数据放在了直方图中)

直方图算法有几个需要注意的地方:

  • 使用bin替代原始数据相当于增加了正则化;
  • 使用bin意味着很多数据的细节特征被放弃了,相似的数据可能被划分到相同的桶中,这样的数据之间的差异就消失了;
  • bin数量选择决定了正则化的程度,bin越少惩罚越严重,欠拟合风险越高。

直方图算法需要注意的地方:

  • 构建直方图时不需要对数据进行排序(比XGBoost快),因为预先设定了bin的范围;
  • 直方图除了保存划分阈值和当前bin内样本数以外还保存了当前bin内所有样本的一阶梯度和(一阶梯度和的平方的均值等价于均方损失);
  • 阈值的选取是按照直方图从小到大遍历,使用了上面的一阶梯度和,目的是得到划分之后△loss最大的特征及阈值。

Histogram 算法的优缺点:

  • Histogram算法并不是完美的。由于特征被离散化后,找到的并不是很精确的分割点,所以会对结果产生影响。但在实际的数据集上表明,离散化的分裂点对最终的精度影响并不大,甚至会好一些。原因在于decision tree本身就是一个弱学习器,采用Histogram算法会起到正则化的效果,有效地防止模型的过拟合。
  • 时间上的开销由原来的O(#data * #features)降到O(k * #features)。由于离散化,#bin远小于#data,因此时间上有很大的提升。

Histogram算法还可以进一步加速。一个叶子节点的Histogram可以直接由父节点的Histogram和兄弟节点的Histogram做差得到。一般情况下,构造Histogram需要遍历该叶子上的所有数据,通过该方法,只需要遍历Histogram的k个捅。速度提升了一倍。

决策树生长策略

在Histogram算法之上,LightGBM进行进一步的优化。首先它抛弃了大多数GBDT工具使用的按层生长 (level-wise)的决策树生长策略,而使用了带有深度限制的按叶子生长 (leaf-wise)算法。

XGBoost采用的是按层生长level(depth)-wise生长策略,能够同时分裂同一层的叶子,从而进行多线程优化,不容易过拟合;但不加区分的对待同一层的叶子,带来了很多没必要的开销。因为实际上很多叶子的分裂增益较低,没必要进行搜索和分裂。

LightGBM采用leaf-wise生长策略,每次从当前所有叶子中找到分裂增益最大(一般也是数据量最大)的一个叶子,然后分裂,如此循环。因此同Level-wise相比,在分裂次数相同的情况下,Leaf-wise可以降低更多的误差,得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树,产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制,在保证高效率的同时防止过拟合。

直方图差加速

LightGBM另一个优化是Histogram(直方图)做差加速。一个容易观察到的现象:一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图,需要遍历该叶子上的所有数据,但直方图做差仅需遍历直方图的k个桶。利用这个方法,LightGBM可以在构造一个叶子的直方图后,可以用非常微小的代价得到它兄弟叶子的直方图,在速度上可以提升一倍。

直接支持类别特征

实际上大多数机器学习工具都无法直接支持类别特征,一般需要把类别特征,转化one-hotting特征,降低了空间和时间的效率。而类别特征的使用是在实践中很常用的。基于这个考虑,LightGBM优化了对类别特征的支持,可以直接输入类别特征,不需要额外的0/1展开。并在决策树算法上增加了类别特征的决策规则。

one-hot编码是处理类别特征的一个通用方法,然而在树模型中,这可能并不一定是一个好的方法,尤其当类别特征中类别个数很多的情况下。主要的问题是:

  • 可能无法在这个类别特征上进行切分(即浪费了这个特征)。使用one-hot编码的话,意味着在每一个决策节点上只能使用one vs rest(例如是不是狗,是不是猫等)的切分方式。当类别值很多时,每个类别上的数据可能会比较少,这时候切分会产生不平衡,这意味着切分增益也会很小(比较直观的理解是,不平衡的切分和不切分没有区别)。
  • 会影响决策树的学习。因为就算可以在这个类别特征进行切分,也会把数据切分到很多零碎的小空间上,如图1左边所示。而决策树学习时利用的是统计信息,在这些数据量小的空间上,统计信息不准确,学习会变差。但如果使用下图右边的分裂方式,数据会被切分到两个比较大的空间,进一步的学习也会更好。

下图右边叶子节点的含义是X=A或者X=C放到左孩子,其余放到右孩子。

LightGBM处理分类特征大致流程:

为了解决one-hot编码处理类别特征的不足。LightGBM采用了Many vs many的切分方式,实现了类别特征的最优切分。用LightGBM可以直接输入类别特征,并产生上图右边的效果。在1个k维的类别特征中寻找最优切分,朴素的枚举算法的复杂度是O(2^k),而LightGBM采用了如 On Grouping For Maximum Homogeneity的方法实现了 O(k\log k)的算法。

算法流程下图所示:在枚举分割点之前,先把直方图按每个类别的均值进行排序;然后按照均值的结果依次枚举最优分割点。从下图可以看到,Sum(y)/Count(y)为类别的均值。当然,这个方法很容易过拟合,所以在LGBM中加入了很多对这个方法的约束和正则化。

下图是一个简单的对比实验,可以看到该最优方法在AUC上提升了1.5个点,并且时间只多了20%。

下面具体来讲下在代码中如何求解类别特征的最优切分的流程:

  • 离散特征建立直方图的过程:统计该特征下每一种离散值出现的次数,并从高到低排序,并过滤掉出现次数较少的特征值, 然后为每一个特征值,建立一个bin容器, 对于在bin容器内出现次数较少的特征值直接过滤掉,不建立bin容器。
  • 计算分裂阈值的过程:
    • 先看该特征下划分出的bin容器的个数,如果bin容器的数量小于4,直接使用one vs other方式, 逐个扫描每一个bin容器,找出最佳分裂点;
    • 对于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集合。
    • 对于连续特征,划分阈值只有一个,对于离散值可能会有多个划分阈值,每一个划分阈值对应着一个bin容器编号,当使用离散特征进行分裂时,只要数据样本对应的bin容器编号在这些阈值对应的bin集合之中,这条数据就加入分裂后的左子树,否则加入分裂后的右子树。

直接支持高效并行

LightGBM原生支持并行学习,目前支持特征并行和数据并行的两种。特征并行的主要思想是在不同机器在不同的特征集合上分别寻找最优的分割点,然后在机器间同步最优的分割点。数据并行则是让不同的机器先在本地构造直方图,然后进行全局的合并,最后在合并的直方图上面寻找最优分割点。

LightGBM针对这两种并行方法都做了优化,在特征并行算法中,通过在本地保存全部数据避免对数据切分结果的通信;在数据并行中使用分散规约(Reduce scatter)把直方图合并的任务分摊到不同的机器,降低通信和计算,并利用直方图做差,进一步减少了一半的通信量。

基于投票的数据并行则进一步优化数据并行中的通信代价,使通信代价变成常数级别。在数据量很大的时候,使用投票并行可以得到非常好的加速效果。

 

更具体的内容可以看NIPS2016的文章:A Communication-Efficient Parallel Algorithm for Decision Tree

网络通信优化

XGBoost由于采用pre-sorted算法,通信代价非常大,所以在并行的时候也是采用histogram算法;LightGBM采用的histogram算法通信代价小,通过使用集合通信算法,能够实现并行计算的线性加速。

LightGBM原理

论文地址:LightGBM A Highly Efficient Gradient Boosting

提升树是利用加模型与前向分布算法实现学习的优化过程,它有一些高效实现,如XGBoost, pGBRT,GBDT(Gradient Boosting Decision Tree)等。其中GBDT采用负梯度作为划分的指标(信息增益),XGBoost则利用到二阶导数。他们共同的不足是,计算信息增益需要扫描所有样本,从而找到最优划分点。在面对大量数据或者特征维度很高时,它们的效率和扩展性很难使人满意。解决这个问题的直接方法就是减少特征量和数据量而且不影响精确度,有部分工作根据数据权重采样来加速booisting的过程,但由于GBDT没有样本权重不能应用。

微软开源的LightGBM(基于GBDT的)则很好的解决这些问题,它主要包含两个算法:

单边梯度采样,Gradient-based One-Side Sampling(GOSS)

GOSS(从减少样本角度):排除大部分小梯度的样本,仅用剩下的样本计算信息增益。GBDT虽然没有数据权重,但每个数据实例有不同的梯度,根据计算信息增益的定义,梯度大的实例对信息增益有更大的影响,因此在下采样时,我们应该尽量保留梯度大的样本(预先设定阈值,或者最高百分位间),随机去掉梯度小的样本。我们证明此措施在相同的采样率下比随机采样获得更准确的结果,尤其是在信息增益范围较大时。

互斥特征绑定,Exclusive Feature Bundling(EFB)

  • EFB(从减少特征角度):捆绑互斥特征,也就是他们很少同时取非零值(也就是用一个合成特征代替)。通常真是应用中,虽然特征量比较多,但是由于特征空间十分稀疏,是否可以设计一种无损的方法来减少有效特征呢?特别在稀疏特征空间上,许多特征几乎是互斥的(例如许多特征不会同时为非零值,像one-hot),我们可以捆绑互斥的特征。最后,我们将捆绑问题归约到图着色问题,通过贪心算法求得近似解。

结合使用 GOSS 和 EFB 的 GBDT 算法就是 LightGBM。

Gradient-based One-Side Sampling(GOSS)

GOSS是一种在减少数据量和保证精度上平衡的算法。GOSS是通过区分不同梯度的实例,保留较大梯度实例同时对较小梯度随机采样的方式减少计算量,从而达到提升效率的目的。

算法描述

AdaBoost中,样本权重是数据实例重要性的指标。然而在GBDT中没有原始样本权重,不能应用权重采样。幸运的事,我们观察到GBDT中每个数据都有不同的梯度值,对采样十分有用,即实例的梯度小,实例训练误差也就较小,已经被学习得很好了,直接想法就是丢掉这部分梯度小的数据。然而这样做会改变数据的分布,将会影响训练的模型的精确度,为了避免此问题,我们提出了GOSS。

GOSS保留所有的梯度较大的实例,在梯度小的实例上使用随机采样。为了抵消对数据分布的影响,计算信息增益的时候,GOSS对小梯度的数据引入常量乘数。GOSS首先根据数据的梯度绝对值排序,选取top a个实例。然后在剩余的数据中随机采样b个实例。接着计算信息增益时为采样出的小梯度数据乘以(1-a)/b,这样算法就会更关注训练不足的实例,而不会过多改变原数据集的分布。

理论分析

GBDT使用决策树,来学习获得一个将输入空间映射到梯度空间的函数。假设训练集有n个实例{x_1,...,x_n},特征维度为s。每次梯度迭时,模型数据变量的损失函数的负梯度方向表示为{g_1,...,g_n},决策树通过最优切分点(最大信息增益点)将数据分到各个节点。GBDT通过分割后的方差衡量信息增益。

定义:O表示某个固定节点的训练集,分割特征j的分割点d定义为:

    \[V_{j|O}(d) = \frac{1}{n_O} ( \frac{ ( \sum_{ \{x_i \in O: x_{ij} \le d \} } g_i )^2 }{n^j_{l|O}(d)} +  \frac{ ( \sum_{ \{x_i \in O: x_{ij} > d \} } g_i )^2 }{n^j_{r|O}(d)} )\]

其中,n_O = \sum I[x_i  \in O], n^j_{l|O} = \sum  I[x_i  \in O: x_i \ge d ], n^j_{r|O} = \sum  I[x_i  \in O: x_i > d ]

遍历每个特征的每个分裂点,找到d^*_j = argmax_d V_j(d)并计算最大的信息增益V_j(d^*_j) ,然后,将数据根据特征j^*的分裂点d^*_j将数据分到左右子节点。

在GOSS中,

  • 首先根据数据的梯度将训练降序排序。
  • 保留top a个数据实例,作为数据子集A。
  • 对于剩下的数据的实例,随机采样获得大小为b的数据子集B。
  • 最后我们通过以下方程估计信息增益:

(1)   \[\tilde{V}_j (d) = \frac{1}{n} ( \frac{ ( \sum_{ {x_i \in A: x_{ij} \le d } } g_i  + \frac{1-a}{b}\sum_{ {x_i \in B: x_{ij} \le d } } g_i )^2 }{n^j{l}(d)} + \frac{ ( \sum_{ {x_i \in A: x{ij} > d } } g_i  + \frac{1-a}{b}\sum_{ {x_i \in B: x{ij} > d } } g_i )^2 }{n^j_{r}(d)} ) \]

此处GOSS通过较小的数据集估计信息增益\tilde{V}{j}(d)将大大地减小计算量。更重要的,我们接下来理论表明GOSS不会丢失许多训练精度,胜过随机采样,理论的证明在附加材料。

我们定义GOSS近似误差为:

    \[\varepsilon(d) = |\tilde{V}_j(d) - V_j(d) |\]

    \[\bar{g}_l^j(d)=\frac{\sum_{x_i \in (A \cup A^c)_l} |g_i|}{n_l^j(d)}\]

概率至少是1- \delta1,有:

(2)   \[\varepsilon(d) \le C_{a, b}^2 \ln (1/\delta) * \max\{ \frac{1}{n_l^j(d)} , \frac{1}{n_r^j(d)} \} + 2*D*C_{a,b} \sqrt{ \frac{\ln(1/\delta)}{n}} \]

其中C_{a,b}=\frac{1-a}{\sqrt{b}} \max_{x \in A^c}{|g_i|}, D=\max(\bar{g}_l^j(d), \bar{g}_r^j(d))

根据上述理论,我们得出以下结论:

  • GOSS的渐近逼近比率O(\frac{1}{n_l^j(d)}+ \frac{1}{n_r^j(d)} + \frac{1}{\sqrt{n}}) 。如果数据分割不是极不平衡(例如 n_l^j(d) \ge O(\sqrt{n})n_r^j \ge O(\sqrt{n})),那么不等式(2)中近似误差将由第二项主导,当n趋于无穷(数据量很大时),O(\sqrt{n})将趋于0,即数据量越大,误差越小,精度越高。
  • 随机采样是GOSS在a=0的一种情况。多数情况下,GOSS性能优于随机采样,即以下情况:C_{0, \beta} > C_{a, \beta-a},即\frac{\alpha_a}{\sqrt{\beta}} > \frac{1-a}{\sqrt{\beta-a}},其中\alpha_a = \max_{x_i \in A \cup A^c} |g_i| / \max_{x_i \in A^c} |g_i|

下面分析GOSS的泛化性。考虑GOSS泛化误差\varepsilon_{gen}^{GOSS}(d) = |\tilde{V}_j(d) - V_*(d)| ,这是GOSS抽样的的实例计算出的方差增益与实际样本方差增益之间的差距。变换为 \varepsilon_{gen}^{GOSS}(d) = |\tilde{V}_j(d) - V_j(d)|+ |V_j(d) - V_*(d)| \triangleq \varepsilon_{GOSS}(d)+ \varepsilon_{gen}(d),因此,在GOSS准确的情况下,GOSS泛化误差近似于全量的真实数据。另一方面,采样将增加基学习器的多样性(因为每次采样获得的数据可能会不同),这将提高泛化性。

Exclusive Feature Bundling(EFB)

EFB是通过特征捆绑的方式减少特征维度(其实是降维技术)的方式,来提升计算效率。通常被捆绑的特征都是互斥的(一个特征值为零,一个特征值不为零),这样两个特征捆绑起来才不会丢失信息。如果两个特征并不是完全互斥(部分情况下两个特征都是非零值),可以用一个指标对特征不互斥程度进行衡量,称之为冲突比率,当这个值较小时,我们可以选择把不完全互斥的两个特征捆绑,而不影响最后的精度。

EBF的算法步骤如下:

  • 将特征按照非零值的个数进行排序
  • 计算不同特征之间的冲突比率
  • 遍历每个特征并尝试合并特征,使冲突比率最小化

高位的数据通常是稀疏的,这种稀疏性启发我们设计一种无损地方法来减少特征的维度。特别的,稀疏特征空间中,许多特征是互斥的,例如他们从不同时为非零值。我们可以绑定互斥的特征为单一特征,通过仔细设计特征臊面算法,我们从特征捆绑中构建了与单个特征相同的特征直方图。这种方式的间直方图时间复杂度从O(#data * #feature)降到O(#data * #bundle),由于#bundle << # feature,我们能够极大地加速GBDT的训练过程而且损失精度。

有两个问题:

  • 怎么判定那些特征应该绑在一起(build bundled)?
  • 怎么把特征绑为一个(merge feature)?

bundle(什么样的特征被绑定)?

**理论1:**将特征分割为较小量的互斥特征群是NP难的。

证明:将图着色问题归约为此问题,而图着色是NP难的,所以此问题就是NP难的。

给定图着色实例G=(V, E)。以G的关联矩阵的每一行为特征,得到我们问题的一个实例有|V|个特征。 很容易看到,在我们的问题中,一个独特的特征包与一组具有相同颜色的顶点相对应,反之亦然。

理论1说明多项式时间中求解这个NP难问题不可行。为了寻找好的近似算法,我们将最优捆绑问题归结为图着色问题,如果两个特征之间不是相互排斥,那么我们用一个边将他们连接,然后用合理的贪婪算法(具有恒定的近似比)用于图着色来做特征捆绑。 此外,我们注意到通常有很多特征,尽管不是100%相互排斥的,也很少同时取非零值。 如果我们的算法可以允许一小部分的冲突,我们可以得到更少的特征包,进一步提高计算效率。经过简单的计算,随机污染小部分特征值将影响精度最多 O([(1 - \gamma)n]^{-2/3})\gamma是每个绑定中的最大冲突比率,当其相对较小时,能够完成精度和效率之间的平衡。

**算法3:**基于上面的讨论,我们设计了算法3,伪代码见下图,具体算法:

  • 建立一个图,每个点代表特征,每个边有权重,其权重和特征之间总体冲突相关。
  • 按照降序排列图中的度数来排序特征。
  • 检查排序之后的每个特征,对他进行特征绑定或者建立新的绑定使得操作之后的总体冲突最小。

算法3的时间复杂度是O(#feature^2),训练之前只处理一次,其时间复杂度在特征不是特别多的情况下是可以接受的,但难以应对百万维的特征。为了继续提高效率,我们提出了一个更加高效的无图的排序策略:将特征按照非零值个数排序,这和使用图节点的度排序相似,因为更多的非零值通常会导致冲突,新算法在算法3基础上改变了排序策略。

merging features(特征合并)

如何合并同一个bundle的特征来降低训练时间复杂度。关键在于原始特征值可以从bundle中区分出来。鉴于直方图算法存储离散值而不是连续特征值,我们通过将互斥特征放在不同的箱中来构建bundle。这可以通过将偏移量添加到特征原始值中实现,例如,假设bundle中有两个特征,原始特征A取值[0, 10],B取值[0, 20]。我们添加偏移量10到B中,因此B取值[10, 30]。通过这种做法,就可以安全地将A、B特征合并,使用一个取值[0, 30]的特征取代AB。算法见算法4,

EFB算法能够将许多互斥的特征变为低维稠密的特征,就能够有效的避免不必要0值特征的计算。实际,通过用表记录数据中的非零值,来忽略零值特征,达到优化基础的直方图算法。通过扫描表中的数据,建直方图的时间复杂度将从O(#data)降到O(#non_zero_data)。当然,这种方法在构建树过程中需要而额外的内存和计算开销来维持预特征表。我们在lightGBM中将此优化作为基本函数,因为当bundles是稀疏的时候,这个优化与EFB不冲突(可以用于EFB)。

参考链接:blog.csdn.net/shine199308…

如何使用LightGBM

所有的参数含义,参考:http://lightgbm.apachecn.org/#/docs/6

调参过程:

  • num_leaves。LightGBM使用的是leaf-wise的算法,因此在调节树的复杂程度时,使用的是num_leaves而不是max_depth。大致换算关系:num\_leaves = 2^{(max\_depth)}
  • 样本分布非平衡数据集:可以param[‘is_unbalance’]=’true’
  • Bagging参数:bagging_fraction+bagging_freq(必须同时设置)、feature_fraction。bagging_fraction可以使bagging的更快的运行出结果,feature_fraction设置在每次迭代中使用特征的比例
  • min_data_in_leaf、min_sum_hessian_in_leaf:调大它的值可以防止过拟合,它的值通常设置的比较大。

更详细介绍,见:www.huaxiaozhuan.com/%E5%B7%A5%E…

sklearn接口形式的LightGBM示例

import lightgbm as lgb
from sklearn.metrics import mean_squared_error
from sklearn.model_selection import GridSearchCV
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
 
# 加载数据
iris = load_iris()
data = iris.data
target = iris.target
X_train, X_test, y_train, y_test = train_test_split(data, target, test_size=0.2)
 
# 创建模型,训练模型
gbm = lgb.LGBMRegressor(objective='regression', num_leaves=31, learning_rate=0.05, n_estimators=20)
gbm.fit(X_train, y_train, eval_set=[(X_test, y_test)], eval_metric='l1', early_stopping_rounds=5)
 
# 测试机预测
y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration_)
 
# 模型评估
print('The rmse of prediction is:', mean_squared_error(y_test, y_pred) ** 0.5)
 
# feature importances
print('Feature importances:', list(gbm.feature_importances_))
 
# 网格搜索,参数优化
estimator = lgb.LGBMRegressor(num_leaves=31)
param_grid = {
    'learning_rate': [0.01, 0.1, 1],
    'n_estimators': [20, 40]
}
gbm = GridSearchCV(estimator, param_grid)
gbm.fit(X_train, y_train)
print('Best parameters found by grid search are:', gbm.best_params_)

原生形式使用lightgbm

import lightgbm as lgb
from sklearn.metrics import mean_squared_error
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
 
iris = load_iris()
data = iris.data
target = iris.target
X_train, X_test, y_train, y_test = train_test_split(data, target, test_size=0.2)
 
# 创建成lgb特征的数据集格式
lgb_train = lgb.Dataset(X_train, y_train)
lgb_eval = lgb.Dataset(X_test, y_test, reference=lgb_train)
 
# 将参数写成字典下形式
params = {
    'task': 'train',
    'boosting_type': 'gbdt',  # 设置提升类型
    'objective': 'regression',  # 目标函数
    'metric': {'l2', 'auc'},  # 评估函数
    'num_leaves': 31,  # 叶子节点数
    'learning_rate': 0.05,  # 学习速率
    'feature_fraction': 0.9,  # 建树的特征选择比例
    'bagging_fraction': 0.8,  # 建树的样本采样比例
    'bagging_freq': 5,  # k 意味着每 k 次迭代执行bagging
    'verbose': 1  # <0 显示致命的, =0 显示错误 (警告), >0 显示信息
}
 
# 训练 cv and train
gbm = lgb.train(params, lgb_train, num_boost_round=20, valid_sets=lgb_eval, early_stopping_rounds=5)
 
# 保存模型到文件
gbm.save_model('model.txt')
 
# 预测数据集
y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration)
 
# 评估模型
print('The rmse of prediction is:', mean_squared_error(y_test, y_pred) ** 0.5)

参数速查

xgb lgb xgb.sklearn lgb.sklearn
booster=’gbtree’ boosting=’gbdt’ booster=’gbtree’ boosting_type=’gbdt’
objective=’binary:logistic’ application=’binary’ objective=’binary:logistic’ objective=’binary’
max_depth=7 num_leaves=2**7 max_depth=7 num_leaves=2**7
eta=0.1 learning_rate=0.1 learning_rate=0.1 learning_rate=0.1
num_boost_round=10 num_boost_round=10 n_estimators=10 n_estimators=10
gamma=0 min_split_gain=0.0 gamma=0 min_split_gain=0.0
min_child_weight=5 min_child_weight=5 min_child_weight=5 min_child_weight=5
subsample=1 bagging_fraction=1 subsample=1.0 subsample=1.0
colsample_bytree=1.0 feature_fraction=1 colsample_bytree=1.0 colsample_bytree=1.0
alpha=0 lambda_l1=0 reg_alpha=0.0 reg_alpha=0.0
lambda=1 lambda_l2=0 reg_lambda=1 reg_lambda=0.0
scale_pos_weight=1 scale_pos_weight=1 scale_pos_weight=1 scale_pos_weight=1
seed bagging_seed feature_fraction_seed random_state=888 random_state=888
nthread num_threads n_jobs=4 n_jobs=4
evals valid_sets eval_set eval_set
eval_metric metric eval_metric eval_metric
early_stopping_rounds early_stopping_rounds early_stopping_rounds early_stopping_rounds
verbose_eval verbose_eval verbose verbose

参考链接:bacterous.github.io/2018/09/13/…

更多参考

打赏作者 微信支付标点符 wechat qrcode 支付宝标点符 alipay qrcode
Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/29926
 
764 次点击