摘要
lgb和xgb论文相比较为简单，本文仅对lgb的基本原理进行简要概括。
基于梯度的单边采样（gradient-based one-side sampling, GOSS）
lgb采用基于梯度的单边采样（GOSS）减少样本数量。GOSS首先按照样本的梯度大小对数据进行降序排序，选取前a%的大梯度样本，然后从剩余的小梯度样本中采样b%，为保持样本分布不变，对小梯度样本加权(1-a)/b。
互斥特征绑定（exclusive feature bundling, EFB）
对于高维稀疏数据，很多特征之间都是互斥的，也就是对于同一个样本，不同特征通常不会同时取非零值。这样的性质给可以几乎无损失地减少特征数量提供了可能性。
EFB包括两个步骤：特征分簇和特征合并。
特征分簇：将每个特征视为一个节点，在非互斥节点之间添加边，将特征bundle问题转换为图着色问题，算法如下：
1、将特征作为节点，特征之间的冲突（两个特征同时非0的样本数量）作为边的权重，构建图；
2、按照节点度对特征进行降序排序；
3、按顺序遍历特征，将其加入已有bundle（若加入后bundle的冲突数小于阈值）或为其创建新的bundle；
对该算法的一种改进是：按照特征中非零值的数量排序，而不是按照节点度进行排序，其他环节一致。
特征合并：通过增加偏移量的方式，将多个互斥特征合并到同一个特征，例如特征A的取值范围为(0,10)，特征B的取值范围为(0,20)，那么可以为特征B增加偏移量10，合并后B的取值范围为(10,30)，新特征的取值范围为(0,30)。
具体如下：
图着色代码
def matrix_graph(g, v_num): """生成二维矩阵""" return [[1 if col in g[row] else 0 for col in range(v_num)] for row in range(v_num)] def nodes_inorder_des(m, v_num): """将结点按度数降序排好""" deg = {} for v in range(v_num): deg[v] = m[v].count(1) return sorted(deg, key=deg.get, reverse=True) def graph_color(m, n, v_num): """将节点按照染色颜色划分""" painted = set() res = list() for v in n: if v not in painted: # 每次找未着色的点 group = list([v]) # 保存相同颜色的结点 painted.add(v) for v_other in range(v_num): if m[v][v_other] == 0 and v_other not in painted: # v与v_other不邻接 and 其邻接点没有被染色 if all(m[v_group][v_other] == 0 for v_group in # v_other与同组节点不邻接 group[1:]): # 拷贝group,保持不变性,并且从新加入节点开始比较 painted.add(v_other) group.append(v_other) res.append(group) if len(painted) == total_v_num: break return res if __name__ == ‘__main__‘: total_v_num = len(graph) matrix = matrix_graph(graph, total_v_num) nodes = nodes_inorder_des(matrix, total_v_num) res = graph_color(matrix, nodes, total_v_num) print(‘染色情况:‘, res) print(‘染色数:‘, len(res))
参考链接
https://www.microsoft.com/en-us/research/wp-content/uploads/2017/11/lightgbm.pdf
https://papers.nips.cc/paper/2017/hash/6449f44a102fde848669bdd9eb6b76fa-Abstract.html
https://www.zhihu.com/question/386159856/answer/1145984790
https://blog.csdn.net/qq_43658387/article/details/103129196
原文：https://www.cnblogs.com/zcsh/p/14757729.html