集成模型（4）lightGBM 主要原理及其python 实现
lightGBM 主要原理及其python 实现
前⾔：lightGBM主要流程和XgBoost⽐较相似，都是GBDT的⼀种改进，相对于XgBoost⽽⾔lightGBM则解决了⼤样本⾼纬度环境下耗时的问题。以及本⽂的实现代码主要⽤于算法核⼼的理解，⽂中不对的的地⽅也欢迎指正。
1主要原理
如前⾯所说，lightGBM在⽬标函数的优化上⾯和XgBoost的⼀样，都是使⽤到了⼆阶导数信息，优化过程可见前⼀篇博客，不同之处在于对⼤样本⾼纬度进⾏了优化改进，⽂本主要介绍改进部分。主要的改进思想：既然样本数量太多，特征维度太⾼，那么就对样本进⾏采样以及特征降维。lightGBM论⽂的作者分别提出了GOSS（Gradient-based One-Side Sampleing，基于梯度的单边采样）以及
EFB（Exclusive Feature Bundling，互斥特征绑定），除了这些lightGBM还做出了其他的优化，例如基于leaf-wise的决策树⽣长策略以及类别特征的最优分割。
1.1GOSS ，基于梯度的单边采样
基于梯度的单边采样的核⼼思想就是将样本按照⼀阶导数的绝对值⼤⼩进⾏降序排序，然后选出最⼤的a%个样本。为什么选择梯度绝对值最⼤的呢？因为对于损失函数⽽⾔，⽬标损失函数的优化通过⼀阶导数等于0到最优解，⽽梯度绝对值最⼤说明当前该样本的预测值对应的损失也就不是最优，误差也就最⼤。因此选出梯度最⼤的a%个样本相当于对上⼀轮错分或者误差严重的样本进⾏着重训练，这和
AdaBoost在每⼀轮给每个错分样本增加权重的思想⽐较类似，只是这⾥并没有显⽰的给每个样本指定⼀个权重。不过除了选择最⼤的a%个样本之外，还会从剩余的（1-a%）个样本中随机选取b%个样本，并对每个样本的梯度放⼤(1-a%)/b%倍，也就是⽤局部去代替整体，相当于现在⽤⼀个样本去代替原来的(1-a%)/b%个样本，当基学习器内部节点进⾏分裂时这(1-a%)/b%个样本作为整体被划分到左⼦节点或右⼦节点，这么做的⽬的就是不去改变原本数据的分布，⼜能加快模型速度。
算法流程：
输⼊：训练数据，迭代步数d（也就是基学习器数量），⼤梯度数据的采样率a%，⼩梯度数据的采样率b%，损失函数l以及弱学习器；输出：训练好的强学习器
1. 使⽤前d-1轮训练好模型的预测值，计算样本点梯度，并根据提到杜绝对之进⾏降序排序；
2. 对排序后的接过去前a%个样本⽣成⼀个⼤梯度样本的集合；
3. 对剩余（1-a%）的样本随机选取（1-a%）b%个样本，⽣成⼩梯度样本点的集合
4. 将⼤梯度样本和随机采样的⼩梯度样本合并；
5. 将⼩梯度样本的梯度值以及⼆阶导数值扩⼤(1-a%)/b%倍；
6. 使⽤合并的样本集合及梯度和⼆阶导数等信息学习⼀个新的基学习器；
7. 不断重复1-6，直到迭代终⽌。
1.2EFB ，互斥特征绑定
这⼀部分主要了解什么时互斥特征以及如何绑定？
（1）⾸先需要先定义什么样的特征称为互斥特征，例如所有样本在特征a和b上⾯的取值都不同时为⾮零值，则称a和b为互斥特征。下⾯的例⼦中a和b就是互斥特征，a和c就不互斥。
a  b  c
0  0  1  4
1  2  0  0
2  3  0  5
3  4  0  0
4  0  0  0
5  0  3  3
6  0  0  0
∂y
i ^(d −1)∂l (y ,)i y
i ^(d −1)
但是实际算法中我们通常会允许⼩部分的冲突。
伪代码如下：
在这⾥插⼊图⽚描述
⾸先构建⼀个带权重的图，每个点代表特征，权重对应特征之间的总冲突；bundles是所有绑定的集合，每个绑定的冲突都⼩于K；needNew就是指当前特征是否需要⽣成⼀个新的绑定还是加⼊现有的绑定。
（2）合并互斥特征，就是将互斥的特征绑定到⼀起，成为⼀个特征，就达到了降维的⽬的。并且为了合并后不同特征能够区分开来，通常会加上⼀个偏移量，例如上⾯例⼦中特征a的范围是[0,4]，b的范围是[0.3]，就可以先将b加上⼀个偏移量5变为[5,8]，这样特征a和b合并之后仍能区分出a，b，且合并后特征的取值范围就变成了[0,8]。
伪代码如下：
在这⾥插⼊图⽚描述
此外在进⾏上⾯互斥特征判断以及绑定之前，通常会将连续值的特征离散化，离散化后的划分点减少加快了速度，虽然离散化后到的划分点可能并不是精确的划分点，但是因为基学习器本⾝就是弱学习器，因此是否精确并不太重要，并且不精确的划分也甚⾄能达到正则化的效果，即使单个基学习器的效果不好，但是在boosting的框架下影响也不⼤。
1.3Leaf-wise的决策树⽣长策略
⼀般决策树都是通过level-wise的策略来⽣长树，不加区分的对待同⼀层的叶⼦，只要满⾜条件（叶节点最⼩样本数量、分裂最⼩增益等）就进⾏分裂，然⽽实际上很多节点的分裂增益较低没被必要分裂，带来了没必要的开销（虽然可以设置节点分裂的最⼩增益，但是这个最⼩增益也是针对于全局的，设置的太⼩很多没必要的节点就会分裂导致，太⼤⼜会导致⽋拟合）。
在这⾥插⼊图⽚描述
⽽lightGBM通过leaf-wise策略⽣长树，每次从当前所有叶⼦节点（并不是当前层的所有叶⼦节点）中到分裂增益最⼤的叶⼦进⾏分裂，和level-wise相⽐，在分裂相同次数的情况下leaf-wie的层数更深，可以降低更多的误差，但样本少时，leaf-wise可能也会造成过拟合，可以通过设置树的最⼤深度来避免。
在这⾥插⼊图⽚描述
1.4类别特征的最优分割
lightGBM对于类别特征的处理其实和cart树对于类别特征的处理差不多，都是将其分为两个⼦集，⽽不是像经典决策树那样对类别特征的所有取值都进⾏划分。lightGBM具体的做法是对类别特征的取值先进⾏排序（根据sum_gradient/sum_hessian，sum_gradient是所有在该类别特征上取某个值的样本
的⼀阶导数和，sum_hessian同理是⼆阶导数和），然后根据排序后的类别取值⼀次寻最优的划分点。
2总结
以上就是lightGBM中主要的特性。
1. lightGBM和XgBoost相⽐，不同之处在于，增加的样本采样以及特征降维，同时决策树的⽣长略也变成了leaf-wise，对于类别特征
也进⾏了单独的处理。
2. 和XgBoost的相同之处就是整体的学习过程是类似的，都是损失函数进⾏泰勒展开到⼆阶。
3. lightGBM还专门加⼊了对缺失值的处理，我这⾥没有细看了。
不过我还是有⼏个疑问的地⽅没有解决：⾸先就是每个绑定内部的所有特征的冲突计算，如果多个特征在同⼀个样本的位置发⽣冲突是计算⼀次还是多次？（代码实现中我是只计算了⼀次）然后就是类别特征参不参与特征绑定，如果参与了绑定，那么类别特征的最优分割就不存在该特征了，还是说会加⼊⼀个判断，如果绑定了对该类别特征就不进⾏最优分割？（下⾯的实现中我并没有实现类别特征的单独处理）
3.python实现
3.1基学习器的实现
import pandas as pd
import numpy as np
import pygraphviz as pgv
splitwise
'''构建回归树，节点分裂准则和叶节点输出值都是根据loss函数确定'''
#计算当前划分下的增益
def cal_Gain(G_L,G_R,H_L,H_R,reg_alpha,reg_lambda):
return(G_L**2/(H_L+reg_lambda)+G_R**2/(H_R+reg_lambda)-(G_L+G_R)**2/((H_L+H_R)+reg_lambda))/2-reg_alpha
#选择最优划分特征以及划分点
def select_best_feature(data:pd.DataFrame,G_H,reg_alpha=0,reg_lambda=1):
features = list()
best_feat =''#最优划分特征
best_split =-1#最优划分点
max_gain =-1#最优划分特征及划分点对应的增益
G_sum = np.sum(G_H[0]['gradient_sum'])#未划分前所有样本的⼀阶导之和
G_sum = np.sum(G_H[0]['gradient_sum'])#未划分前所有样本的⼀阶导之和
H_sum = np.sum(G_H[0]['hessian_sum'])#未划分前所有样本的⼆阶导之和
for i,feat in enumerate(features):
G_H_df = G_H[i]
split_vals = np.array(G_H_df.iloc[:,0])[1:-1]
for val in split_vals:
#根据特征的取值进⾏划分
index = G_H_df.iloc[:,0]<val
G_l = np.sum(G_H_df.loc[index,'gradient_sum'])#以该点作为划分点得到的左⼦树的⼀阶导数之和
H_l = np.sum(G_H_df.loc[index,'hessian_sum'])
cur_gain = cal_Gain(G_l,G_sum-G_l,H_l,H_sum-H_l,reg_alpha,reg_lambda)#计算增益
if cur_gain>max_gain:
max_gain = cur_gain
best_feat = feat
best_split = val
return best_feat, best_split,max_gain
#返回叶节点最优的输出值，即最⼩化损失函数loss
def cal_best_w(gradient,hessian,reg_lambda):
return-np.sum(gradient)/(np.sum(hessian)+reg_lambda)
#⽣成每个特征对应的直⽅图，对每个特征的每个bin计算⼀阶导数之和、⼆阶导数之和，⽤于计算节点分裂的增益
def histogram(data:pd.DataFrame, gradient, hessian):
features = list()
tmp_df = py()
tmp_df['gradient']= gradient
tmp_df['hessian']= hessian
G_H =[]
for i,feat in enumerate(features):
#统计每个特征离散后的每个离散值取值的所有样本的⼀阶导数之和、⼆阶导数之和
gp = upby(feat).agg({'gradient':['sum'],'hessian':['sum']})
gp = gp.reset_index()
G_H.append(gp)
return G_H
#直⽅图做差
def histogram_speed(G_H, G_H_l):
G_H_r =[]
for i in np.arange(len(G_H)):
G_H_df=  G_H[i]
G_H_l_df = G_H_l[i]
G_H_r_df = G_py()
for i,val in enumerate(G_H_l_df.iloc[:,0]):
index =(G_H_r_df.iloc[:,0]== val)
G_H_r_df.loc[index,'gradient_sum']-= G_H_l_df.loc[i,'gradient_sum']
G_H_r_df.loc[index,'hessian_sum']-= G_H_l_df.loc[i,'hessian_sum']
G_H_r.append(G_H_r_df)
return G_H_r
#基于leaf-wise构建回归树
def build_treeRegressor(data:pd.DataFrame,G_H,gradient,hessian,num_leaves=8,max_depth=3,min_samples_leaf=1,                        gamma=0,reg_alpha=0,reg_lambda=0):
'''
:param data：训练集
:param G_H: 数组，包含每个特征的直⽅图统计量
:param gradient: np.array, 样本的⼀阶导数
:param hessian: np.array, 样本的⼆阶导数
:param num_leaves: 树的最⼤叶节点数⽬
:param max_depth: 树的最⼤层数
:param min_samples_leaf: 叶节点最⼩样本数
:param gamma: 分割所需要达到的最⼩增益
:param reg_alpha: L1正则化参数
:param reg_lambda: L2正则化参数
:return: 树模型
'''
tree_leaves =[]
tree_leaves.append({'data': data,'G_H': G_H,'gradient': gradient,'hessian': hessian,'cal':[],
tree_leaves.append({'data': data,'G_H': G_H,'gradient': gradient,'hessian': hessian,'cal':[],
'depth':0,'isSplit':True,'val':cal_best_w(gradient,hessian,reg_lambda)})
while(len(tree_leaves)<num_leaves):
best_feat =''
best_split =-1
max_gain =-1
best_leaf_index =-1
# print('while')
for i,leaf in enumerate(tree_leaves):
#先检查叶节点
if leaf['isSplit']==False:
continue
# print('for')
data_leaf = leaf['data']
G_H_leaf = leaf['G_H']
leaf_feat, leaf_split, leaf_gain = select_best_feature(data_leaf, G_H_leaf, reg_alpha, reg_lambda) # 如果分割后产⽣的增益⼩于阈值，则不分割
if leaf_gain < gamma:
tree_leaves[i]['isSplit']=False
continue
L_tree_index = data_leaf[leaf_feat]< leaf_split
R_tree_index = data_leaf[leaf_feat]>= leaf_split
# 如果分割后左⼦树或右⼦树样本数量⼩于叶节点最⼩样本数量则停⽌分割
if len(L_tree_index)< min_samples_leaf or len(R_tree_index)< min_samples_leaf:
tree_leaves[i]['isSplit']=False
continue
if leaf_gain>max_gain:
best_leaf_index = i
max_gain = leaf_gain
best_feat = leaf_feat
best_split = leaf_split
#如果不到可以划分的叶节点，则停⽌
if best_leaf_index ==-1:
break
# print(best_leaf_index)
best_leaf = tree_leaves[best_leaf_index]
gradient_leaf = best_leaf['gradient']
hessian_leaf = best_leaf['hessian']
#cal_process保存的是到达这个节点所需要进⾏的c操作
cal_process_l = best_leaf['cal'].copy()
cal_process_r = best_leaf['cal'].copy()
cal_process_l.append((best_feat,best_split,'l'))
cal_process_r.append((best_feat,best_split,'r'))
# 计算左右⼦树的⼀阶导数和⼆阶导数的直⽅图
L_tree_index = best_leaf['data'][best_feat]< best_split
R_tree_index = best_leaf['data'][best_feat]>= best_split
G_H_l = histogram(best_leaf['data'][L_tree_index], gradient_leaf[L_tree_index], hessian_leaf[L_tree_index])        G_H_r = histogram_speed(best_leaf['G_H'], G_H_l)
isSplit =True
# 当达到数的最⼤深度时，停⽌分裂
if best_leaf['depth']+1>=max_depth:
isSplit =False
tree_leaves.append({'data': best_leaf['data'][L_tree_index],'G_H': G_H_l,
'gradient': gradient_leaf[L_tree_index],'hessian': hessian_leaf[L_tree_index],
'cal':cal_process_l,'depth':best_leaf['depth']+1,'isSplit':isSplit,
'val':cal_best_w(gradient_leaf[L_tree_index],hessian_leaf[L_tree_index],reg_lambda)})
tree_leaves.append({'data': best_leaf['data'][R_tree_index],'G_H': G_H_r,
'gradient': gradient_leaf[R_tree_index],'hessian': hessian_leaf[R_tree_index],
'cal':cal_process_r,'depth':best_leaf['depth']+1,'isSplit':isSplit,
'val':cal_best_w(gradient_leaf[R_tree_index],hessian_leaf[R_tree_index],reg_lambda)})
tree_leaves.pop(best_leaf_index)
return tree_leaves
def predict(tree_leaves:[], data: pd.DataFrame):

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。