LightGBM基本原理与EFB降维方法

LightGBM原理与实践

• 高阶集成学习算法

  在学习了一系列梯度提升树的改进算法后，接下来，我们将进入到更加前沿的集成学习算法中，即LightGBM算法（全称为Light Gradient Boosting Machine，以下简称LGBM算法）和CatBoost算法（全称为Categorical Boosting）的学习中。和XGBoost算法（以下简称XGB算法）类似，这两个算法也是GBDT的改进算法，并且由于这两个算法诞生时间更晚，因此相比之下，LGBM和CatBoost拥有更多功能上的优化，以便应对更加复杂的当前机器学习应用情况。例如，相比XGB，LGBM有更高效的计算效率和更低的内存占用，并且面对高维数据，LGBM算法拥有更好的过拟合特性，这使得在建模数据量日趋增加的今天，LGBM会更适合作为前期探索性建模的模型（Baseline模型），并且在具体建模效果上，对比XGB也是不遑多让。而CatBoost算法同样在训练效率上比XGB更快，并且更加自动化——在特征衍生和超参数优化已经成为机器学习模型训练标配的今天，CatBoost能够（一定程度上）实现对输入的特征进行自动特征衍生和对超参数进行自动超参数优化。不难看出，LGBM和CatBoost是诞生于新应用环境中的新型集成学习算法，而对LGBM和CatBoost算法的学习，也成为了当今算法工程师的必修课。

  不过同样需要说明的是，尽管LGBM和CatBoost算法对比XGB有诸多方面的优化，但这并不代表这两种算法相比XGB具有全方位的效果优势。在真实的实战应用，XGB（甚至是随机森林）仍然具有非常高的实践价值，很多时候我们需要尝试多种不同类型的算法，才能获得一个更好的结果。并且，由RF、XGB、LGBM、CatBoost属于“强而不同”的算法，这会导致这些模型结果会非常适合进行更进一步的模型融合，以达到更好的效果，因此在大多数追求极致建模效果的场景下，这些模型都需要训练，并得到一个尽可能好的结果，然后再进行融合。

而相比其他集成学习算法，例如Bagging、AdaBoost等，RF、XGB、LGBM和CatB可以说是有全方位的效果优势，因此，除非是某些特殊场景，否则一般不会优先考虑使用这些算法。

• LightGBM算法简介

  LightGBM 是一种高效的 Gradient Boosting 算法，由 Microsoft Research Asia 团队开发，早期为Microsoft内部处理海量高维数据的专用算法，并于2017年由Guolin Ke, Qi Meng, Thomas Finley等人通过论文形式正式发布。如果说XGB为GBDT类算法在提升计算精度上做出了里程碑式的突破，那么LGBM则是在计算效率和内存优化上提出了开创性的解决方案，一举将GBDT类算法计算效率提高了近20倍、并且计算内存占用减少了80%，这也最终使得GBDT类算法、这一机器学习领域目前最高精度的预测类算法，能够真正应用于海量数据的建模预测。以下是官网给出的XGB、基于直方图优化的XGB和LGBM算法的在相同计算任务下计算时间的对比：

而在内存占用方面，LGBM算法的优势也同样非常明显，以下是相同计算任务下不同算法的内存占用对比：

XGBoost_hist 是在 LightGBM 提出之后，针对 XGBoost 的一种优化。XGBoost_hist 是 XGBoost 的一种变体，使用了直方图近似的技术。XGBoost_hist是受到了 LightGBM 的启发，LightGBM 则是第一个广泛使用直方图近似技术的梯度提升决策树算法。课程中将详细介绍这种直方图优化算法。

而与此同时，LGBM能够保持和XGB几乎一样的预测精度，相同计算任务三种算法计算准确率如下：

不难发现，预测精准而计算过程高效，这也是Light一词的核心精髓，并且经过这么多年的实践验证，可以说目前来看，LightGBM已然成为处理海量数据最高效、最通用的机器学习算法。

• LightGBM算法相关论文

  对于新兴机器学习算法，最权威的介绍材料毫无疑问就是提出者发布的相关论文，这里我们重点推荐开发团队在2017年提出LGBM原理论文以及2019年由Essam Al Daoud提出的算法性能对比论文，两篇论文介绍及地址如下：

  LightGBM: A Highly Efficient Gradient Boosting Decision Tree (2017)
  作者：Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu
  该论文是 LightGBM 的最初论文，详细阐述了 LightGBM 算法的设计思想、技术特点和实验结果。

  Comparison between XGBoost, LightGBM and CatBoost using a home credit dataset (2019)
  作者：Essam Al Daoud
  该论文详细对比了LGBM、XGB和CatB三个模型在信用卡数据上的性能差异，并提出了不同模型的超参数优化基本思路。

在后续的LGBM算法原理讲解中，我们也将大量借鉴这些论文中的原理介绍相关内容和性能验证方法。

上述论文可通过点击课件中蓝色链接在线观看，或查看课件网盘中的PDF版本论文。

• LightGBM官方文档与开源项目地址

  此外官方说明文档和Github项目说明也是必不可少的学习材料。对于LightGBM来说，论文中隐藏了大量细节，这些都需要我们通过查阅官方说明文档和项目源码来进行补充。因此在后续的教学过程中，我们也将大量参考或者回归到这些全文说明文档中进行讲解和介绍，具体地址如下：

  LightGBM的官方文档：https://lightgbm.readthedocs.io/en/v3.3.5/index.html

  LightGBM的GitHub地址：https://github.com/microsoft/LightGBM

最后，需要导入本节课程需要用到的第三方库：

# 科学计算模块
import numpy as np
import pandas as pd

# 绘图模块
import matplotlib as mpl
import matplotlib.pyplot as plt

# Scikit-Learn相关模块
# 评估器类
from sklearn.preprocessing import StandardScaler
from sklearn.preprocessing import PolynomialFeatures
from sklearn.linear_model import LogisticRegression
from sklearn.pipeline import make_pipeline
from sklearn.model_selection import GridSearchCV
from sklearn.tree import DecisionTreeClassifier

# 实用函数
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# 数据准备
from sklearn.datasets import load_iris

---

Ch.1 LightGBM基本原理与EFB降维方法

• LightGBM原理简介

  LightGBM（Light Gradient Boosting Machine，以下简称LGBM）是一个基于梯度提升决策树（Gradient Boosted Decision Trees，GBDT）的高效、可扩展的机器学习算法，作为GBDT框架的算法的一员，并且作为XGB算法的后来者，LGBM非常好综合了包括XGB在内的此前GBDT算法框架内各算法的一系列优势，并在此基础上做了一系列更进一步的优化。LGBM算法提出的核心目的是为了解决GBDT算法框架在处理海量数据时计算效率低下的问题，而从实践效果来看，LGBM也确实做到了这点——LGBM以牺牲极小的计算精度为代价，将GBDT的计算效率提升了近20倍！这也最终使得LGBM算法是第一个真正意义上能处理海量数据的GBDT框架算法。并且，尽管计算精度存在“选择性的牺牲”，但LGBM的实际建模效果也能达到几乎和XGB同等水平，而且由于LGBM“选择性的牺牲精度”从另一个角度来看其实就是抑制模型过拟合，因此在很多场景下，LGBM的算法效果甚至会好于XGB。种种实践证明，LGBM是一个拥有超高计算效率的同时、又能够保持超高精度的算法，是目前机器学习领域当之无愧的顶级算法之一。

  而LGBM是如何做效率和精度“两手抓”的呢？简而言之就是LGBM充分借鉴了XGB提出的一系列提升精度的优化策略，同时在此基础之上进一步提出了一系列的数据压缩和决策树建模流程的优化策略。尽管在算法的数学原理层面LGBM并没有翻越XGB创建的理论高峰，但其提出的一系列优化策略也同样是极具开创性的，其中数据压缩方法能够让实际训练的数据量在大幅压缩的同时仍然保持较为完整的信息，而决策树建模流程方面的优化，则是在XGB提出的直方图优化算法基础上进行了大幅优化，不仅能够加速决策树建模速度，同时也能非常好的处理经过压缩后的数据，从而最终大幅提升每棵树的训练效率（甚至在LGBM提出的一段时间后，新版XGB也采用了LGBM类似的直方图算法来加速建模效率）。并且最重要的是，有理论能够证明，哪怕LGBM实际建模是基于压缩后的数据进行训练，但其预测精度受到的影响也是微乎其微。

  当然，除了算法原理层面的优化方法外，LGBM还提出了非常多针对于实际计算过程的优化，例如Voting Parallel（投票特征并行）方法、特征多线程并行处理方法、GPU加速方法和分布式计算等，这些方法进一步提升了LGBM实际建模效率，并且一定程度拓宽了算法的使用场景。并且需要注意的是，所谓的计算效率优化，不仅体现在计算时间的大幅缩短，同时得益于LGBM所提出的一系列数据压缩技术，使得实际建模时数据内存占用也大幅减少。

  总的来说，LGBM算法可以看成是迭代过程几乎全盘借鉴XGB、而在数据压缩方法和决策树训练方法上有大量创新的算法，因此在原理相关内容我们将分为两部分进行讲解，第一部分我们重点介绍LGBM创新性提出的一系列方法，第二部分再来探讨LGBM损失函数求解流程。考虑到LGBM的推导流程和XGB几乎完全一样，原理部分的讲解的重点将会是LGBM创新性提出的一系列数据压缩和优化策略。

XGB几乎可以说是GBDT类算法的原理层面的里程碑，开创性的提出了拟合二阶泰勒展开的思路，并据此设计了全套关键数学表达式，包括包含Hessian值得伪残差、分裂增益计算公式化和叶节点权重计算公式。而后继的LGBM和CatBoost，在损失函数求解过程几乎没有再提出超出XGB理论框架的内容，而是在数据预处理和决策树训练方法上提出了进一步优化方法。这点甚至也可以从LGBM原论文中看出，在LGBM原始论文中几乎没有任何关于损失函数求解的说明，通篇几乎都在强调数据压缩方法和决策树优化流程的有效性，我们也是通过查阅官方文档和源码才得知LGBM的具体迭代流程。因此，从这个角度来说，XGB是迄今为止GBDT类算法框架的理论最高峰。

• LightGBM的数据压缩策略

  LightGBM建模过程总共会进行三方面的数据压缩，根据实际建模顺序，会现在全样本上连续变量分箱（连续变量离散化），然后同时带入离散特征和离散后的连续变量进行离散特征捆绑（合并）降维，最终在每次构建一颗树之前进行样本下采样。其中连续变量的分箱就是非常简单的等宽分箱，并且具体箱体的数量可以通过超参数进行人工调节；而离散特征的降维，则是采用了一种所谓的互斥特征捆绑（Exclusive Feature Bundling, EFB）算法，该算法也是由LGBM首次提出，该方法的灵感来源于独热编码的逆向过程，通过把互斥的特征捆绑到一起来实现降维，这种方法能够很好的克服传统降维方法带来的信息大量损耗的问题，并且需要注意的是，输入EFB进行降维的特征，即包括原始离散特征，也包括第一阶段连续变量离散化之后的特征；在这一系列数据压缩之后，LGBM在每次迭代（也就是每次训练一颗决策树模型）的时候，还会围绕训练数据集进行下采样，此时的下采样不是简单的随机抽样，而是一种名为基于梯度的单边采样（Gradient-based One-Side Sampling, GOSS）的方法，和EFB类似，这种方法能够大幅压缩数据，但同时又不会导致信息的大量损失。不难发现，最终输入到每颗决策树进行训练的数据，实际上是经过大幅压缩后的数据，这也是LGBM计算高效的根本原因之一。

• LightGBM决策树建模优化方法

  而进入到具体的决策树训练环节，总的来说LGBM采用的决策树建模优化方法有两个，其一是直方图优化算法，这种方法本质上是通过直方图的形式更加高效简洁的表示每次分裂前后数据节点的核心信息，并且父节点和子节点也可以通过直方图减法计算直接算得，从而加速数据集分裂的计算过程:

直方图优化算法看似简单，实际上计算过程非常复杂，后面我们会通过一个手写的例子来进行详细讲解。

其二则是leaf wise tree growth的叶子节点优先的决策树生长策略，这其实是一种树生长的模式，对于其他大多数决策树算法和集成算法来说，树都是一次生长一层，也就是所谓的Level-wise tree growth（深度优先的生长策略），生长过程如下。

而LGBM则允许决策树生长过程优先按照节点进行分裂，即允许决策树“有偏”的生长，也就是所谓的leaf wise tree growth的叶子节点优先的决策树生长策略，具体生长过程如下：

根据LGBM论文的论述，但从Level-wise tree growth远离层面，这种方法其实是有利有弊，其优势在于能够大幅提升每颗树的收敛速度，从总体来看相当于是提升了每次迭代效率；而问题则在于会每棵树的计算过程会变得更加复杂，并且存在一定的过拟合风险。不过对于LGBM来说，这些问题都能够被很好的克服，比如计算过程复杂的问题可以通过数据压缩来对冲，而过拟合风险则可以通过限制最大树深度来解决，因此总的来看Level-wise tree growth就是最适合LGBM的决策树生长策略。

  接下来，我们就这些技术逐一来进行介绍，并借助一个精心设计的手动实现的例子，来串联起LGBM在进行Boosting迭代前的全部数据计算流程，借此深化大家对本部分内容的理解。

1.连续变量分箱

• 等宽分箱基本概念回顾

  首先是连续变量分箱。LGBM采用的连续变量分箱方法就是简单的等宽分箱，和我们在特征工程部份介绍的等宽分箱方法无异：首先计算连续变量的取值范围，然后人工输入的max_bin超参数，进行数量为max_bin等宽度的区间划分，并把连续变量的值划归到一个个箱体内部。例如某连续变量取值范围为[0, 10]，max_bin=2，则两个等宽的区间划分为bin0=[0, 5)和bin1=[5, 10]，并且如果某连续变量取值为1，则经过分箱后会被标记为bin0（或者0），如果某各连续变量取值为10，则分箱后会被标记为bin1（或者1）。至此，就将连续变量转化为了离散变量。具体手动实现过程和sklearn实现过程可以回顾特征工程Part 2中的内容介绍。

这里需要注意，XGB也会对连续变量进行分箱，但XGB的分箱是分位数分箱，而不是等宽分箱。

• 手动示例

  接下来，我们通过一个手动实现的例子来说明这一过程，需要注意的是，这个手动创建数据集将贯穿本节的各部分内容。数据集基本情况如下：

np.random.seed(11)

x1 = np.array([1.2, 2.9, 2.6, 3.3, 2.0, 2.5, 1.4, 2.1, 1.7, 3.0])
x2 = np.array([4.7, 5.5, 3.9, 6.2, 3.5, 4.5, 5.1, 2.7, 4.1, 3.8])
x3 = np.random.randint(0, 2, 10)
x4 = np.random.randint(0, 2, 10)
y = np.array([1, 0, 1, 0, 1, 1, 0, 0, 1, 1])
data = pd.DataFrame({'x1':x1, 'x2':x2, 'x3':x3, 'x4':x4, 'y':y})
data

	x1	x2	x3	x4	y
0	1.2	4.7	1	0	1
1	2.9	5.5	1	0	0
2	2.6	3.9	0	1	1
3	3.3	6.2	1	0	0
4	2.0	3.5	1	0	1
5	2.5	4.5	1	1	1
6	1.4	5.1	1	0	0
7	2.1	2.7	0	1	0
8	1.7	4.1	1	0	1
9	3.0	3.8	1	1	1

数据集总共包含10条数据，其中x1和x2是连续特征，x3和x4是离散特征，y是标签，该数据集是各二分类数据集。

  接下来，我们对其中的连续变量进行分箱，这里我们设置max_bin=2，即进行两个箱体的等宽分箱。具体实现过程及分箱结果如下：

from sklearn.preprocessing import KBinsDiscretizer
# 采用sklearn中的评估器


# 将 x1 和 x2 分别进行等宽分箱，分成 2 个箱子
n_bins = 2
strategy = 'uniform'

# 实例化两个分箱的评估器
kbins_x1 = KBinsDiscretizer(n_bins=n_bins, encode='ordinal', strategy=strategy)
kbins_x2 = KBinsDiscretizer(n_bins=n_bins, encode='ordinal', strategy=strategy)

# 然后在两个连续变量x1，x2的基础上来进行一个两个箱子的等宽分箱
x1_binned = kbins_x1.fit_transform(data['x1'].values.reshape(-1, 1))
x2_binned = kbins_x2.fit_transform(data['x2'].values.reshape(-1, 1))

# 将分箱后的结果保存到原始数据集中
data['x1_binned'] = x1_binned
data['x2_binned'] = x2_binned

print(data)

    x1   x2  x3  x4  y  x1_binned  x2_binned
0  1.2  4.7   1   0  1        0.0        1.0
1  2.9  5.5   1   0  0        1.0        1.0
2  2.6  3.9   0   1  1        1.0        0.0
3  3.3  6.2   1   0  0        1.0        1.0
4  2.0  3.5   1   0  1        0.0        0.0
5  2.5  4.5   1   1  1        1.0        1.0
6  1.4  5.1   1   0  0        0.0        1.0
7  2.1  2.7   0   1  0        0.0        0.0
8  1.7  4.1   1   0  1        0.0        0.0
9  3.0  3.8   1   1  1        1.0        0.0

至此，我们就完成了LGBM的第一阶段数据处理——连续变量的分箱处理。

2.互斥特征捆绑（Exclusive Feature Bundling，EFB）

  接下来则是围绕这些离散特征进行降维。LGBM采用了一种名为互斥特征捆绑（Exclusive Feature Bundling，EFB）的降维方法，这种方法在LGBM论文LightGBM: A Highly Efficient Gradient Boosting Decision Tree (2017)中首次提出，不同于第一阶段的简单的等宽分箱，EFB实际计算过程非常复杂，我们这里从EFB方法提出背景、计算原理和手动示例三个方面对其进行介绍。

2.1 EFB算法简介与基本流程

• EFB算法提出背景

  根据LightGBM: A Highly Efficient Gradient Boosting Decision Tree (2017)论文描述，原始的GBDT在进行每颗树的训练时，需要带入全部数据来进行信息增益的计算，从而寻找到决策树生长过程中的最佳切分点，这个过程也就是所谓的扫描全部数据来决定切分点的过程。这个过程尽管非常精准，但计算复杂度非常高（直接和特征数量及样本数量成正比），在进行海量数据建模训练的时候会耗费大量的算力和时间。因此，为了能够更好的应对海量数据的模型训练，样本采样和特征降维是非常必要的。但传统的方法在这方面往往效果不佳，例如简单的欠采样（样本随机抽样）可能会造成模型训练过程非常不稳定，而PCA降维则只适用于处理冗余特征，当每个特征都具有相当信息体量时强行进行降维则会导致信息大量丢失。为了解决这个问题，LGBM开创性的提出了基于梯度的单边采样方法（GOSS）进行样本数量的压缩，提出了互斥特征捆绑方法（EFB）来进行特征压缩。不同于以往的方法，GOSS和EFB能够非常好的兼顾预测精度与计算效率。此外，对连续变量进行离散化也是非常有效的数据压缩的手段，LGBM在XGB提出的直方图优化的基础上，进一步提出了一种改进策略，和GOSS和EFB类似，这种LGBM直方图优化方法同样能够在大幅提高计算效率的同时保证预测精度。

• 简化后的EFB计算流程

  而具体到EFB降维算法，其实是受到独热编码启发，设计的类似于独热编码逆向过程的一种算法。例如一组数据情况如下，独热编码是从左往右的计算过程，把一列展开为多列，而EFB则是从右往左进行计算，将多列压缩为一列：

具体独热编码的相关内容，可回顾特征工程Part 2数据重编码部分内容。

当两个变量无法同时取到相同的非零值时，我们说这两个变量是互斥的。

  那既然是独热编码的逆向计算，我们就需要首先讨论为什么LGBM不需要独热编码。我们知道，独热编码本质上是对离散特征更加细粒度的信息呈现，在某些场景下能够提升模型效果。当然更重要的是独热编码能够非常好的用于表示离散变量，对于大多数无法区分连续变量和离散变量的机器学习算法来说，通过独热编码重编码的数据将能够非常方便进行例如离散变量之间的距离计算等操作。但是这些独热编码的优势对于LGBM来说并不存在。首先LGBM带入模型计算的全部变量都是离散变量（连续变量也会被离散化），其次独热编码带来的更细粒度的信息呈现也不会进一步提升模型效果（对于大多数集成学习算法来说都是如此），当然更重要的是，LGBM的算法设计就是为了处理海量高维数据，独热编码只会进一步造成维度灾难。因此，LGBM不仅不需要进行独热编码，还需要进行独热编码的逆操作来进行特征降维。当然，我们这里只是借用独热编码的计算过程帮大家理解EFB的降维过程，在实际计算过程中，EFB的降维的目标并不是把独热编码之后的特征再转换回来，而是找到那些原始状态下就存在类似上图中x1和x2这种关系的特征，来将其合成为一个特征。这里我们注意观察，上图中x1和x2两个特征存在一种这样的关系——任何一条样本都不会同时在x1和x2上取值非0，在EFB原理的定义中，这种关系的特征又被称作互斥特征，而互斥特征其实是可以合成一个特征的，比如上图中的x，这个合成的过程并不会有任何的信息损失，而合成的过程又被称作特征捆绑。这也就是所谓的互斥特征捆绑算法。

  我们这里再看一个互斥特征捆绑的例子，比如如下x3和x4，也是互斥的，此时我们可以将x3和x4捆绑为一个新的x_b1特征，新特征中可以用0、1、2来表示x3和x4的不同组合，从而在不损失信息的情况下，进行了降维。

  当然，这只是一个简化后的示例，真实的EFB特征降维情况会非常复杂，并不是简单的将多个离散变量的不同取值组合进行重新赋值，这个例子只是用于帮大家建立对EFB的感性的认识，接下来我们就围绕原论文中提出的EFB算法来进行更加严谨的算法流程介绍。

2.2 EFB算法基本原理

• 放宽互斥的条件：冲突比例（conflict_rate）概念介绍

在同一个样本上，二者有相同非零取值时称为冲突。比如我取1，你也取1，此时我们俩的取值就冲突了。如果我们俩之间冲突了，那么自然我们俩之间就不互斥了。（因为有相同非零取值）所以互斥的条件是，没有任何一条样本是冲突的。

  真实数据的EFB计算过程会非常复杂，首先是关于“互斥”关系的定义，EFB并不是只压缩完全互斥的特征，而是非常灵活的定义了一个冲突比例（又称非互斥比例），这个比例用于表示两个特征中冲突（即非互斥、同时取非零值）的取值占比，来衡量两个特征互斥程度。当然，冲突比例越大说明互斥程度越低。例如对于如下数据集，总共包含四条数据，其中只有第四条数据是同时取得了非零值，因此只有一条数据是冲突的，其他数据都是互斥的，因此冲突比例为1/4=0.25：（冲突比例=冲突样本数 / 非全零样本总数）

特征1	特征2
0	1
1	0
0	0
1	1

同时，LGBM提供了一个名为max_conflict_rate的超参数，用于表示最大冲突比例，当两个特征的冲突比例小于我们设置的最大冲突比例（max_conflict_rate）时，我们就认为这两个特征并不冲突，而是互斥的，是可以进行捆绑的。例如假设我们设置max_conflict_rate=0.3，则上述两个特征可以进行捆绑，而如果我们设置max_conflict_rate=0.2，则上面两个特征超过了我们认为冲突的阈值，因此这两个特征是冲突的，而不是互斥的，是不能进行进一步捆绑的。很明显，max_conflict_rate设置的越小，对互斥的要求就越高，特征就越不容易被捆绑，模型计算量就越大、精度也越高，而如果max_conflict_rate设置的很大，则更多的特征会被捆绑，模型计算速度会更快，但精度也会降低。

• 借助图着色(Graph Coloring Problem)问题来解决特征捆绑流程问题

  通过最大冲突比例的概念引入，相当于是放宽的互斥的条件，或者说给是否互斥添加了一个可以量化计算的阈值。而真正开始进行特征捆绑的时候，面对海量特征，LGBM是如何进行EFB计算的呢？实际上LGBM会将特征捆绑问题视作（或者说是转化为）一个图着色的问题(Graph Coloring Problem)。图着色问题一种经典的组合优化问题，其问题描述为：给定一个无向图，如何用尽量少的颜色对图中的每个顶点进行着色，使得相邻的顶点颜色不同。这里的“颜色”可以是任意一种符号或编号，只要保证相邻的顶点颜色不同即可。在EFB计算过程中，会将不同特征视作图上的一个个点，若特征之间存在冲突，则用一条无向边进行连接，边的权重就是冲突比例，而如果两个特征互斥，则彼此没有边进行相连。而在将特征及其冲突情况用图进行展示后，即可进一步进行图着色——即在相邻的点颜色不同的前提条件下，用尽可能少的颜色对图上的点进行着色，既然相互冲突的特征都有边进行相连，那么相同颜色的点其实就是互斥的特征，接下来我们仅需把相同颜色的特征进行合并即可。

因为这里是使用尽可能少的颜色来对图进行着色，而相邻的点颜色均不同。所以不相邻的点颜色一定相同。而此时不相邻的点又是互斥的点，所以只需把相同颜色的点提取出来，这些点就是互斥的点，再对它们进行特征合并即可。

  当然，这个过程听起来较为抽象，我们这里还是以上面的data数据集为例，来展示一个借助图着色来进行特征捆绑的完整过程。

2.3 EFB算法计算流程

• 计算冲突比例矩阵

因为我们面临的是海量数据，所以我们需要去计算每一个特征和其他所有特征的冲突比例是多少。所以这里我们需要去计算一个冲突矩阵。

  经过连续变量离散化，现在我们的data数据就已经变成了四个离散特征的数据集，四个离散特征分别为：‘x1_binned’、‘x2_binned’、‘x3’、‘x4’：

data

	x1	x2	x3	x4	y	x1_binned	x2_binned
0	1.2	4.7	1	0	1	0.0	1.0
1	2.9	5.5	1	0	0	1.0	1.0
2	2.6	3.9	0	1	1	1.0	0.0
3	3.3	6.2	1	0	0	1.0	1.0
4	2.0	3.5	1	0	1	0.0	0.0
5	2.5	4.5	1	1	1	1.0	1.0
6	1.4	5.1	1	0	0	0.0	1.0
7	2.1	2.7	0	1	0	0.0	0.0
8	1.7	4.1	1	0	1	0.0	0.0
9	3.0	3.8	1	1	1	1.0	0.0

data[['x1_binned', 'x2_binned', 'x3', 'x4']]

	x1_binned	x2_binned	x3	x4
0	0.0	1.0	1	0
1	1.0	1.0	1	0
2	1.0	0.0	0	1
3	1.0	1.0	1	0
4	0.0	0.0	1	0
5	1.0	1.0	1	1
6	0.0	1.0	1	0
7	0.0	0.0	0	1
8	0.0	0.0	1	0
9	1.0	0.0	1	1

然后我们需要计算这四个特征彼此之间的冲突比例，我们可以通过定义如下函数来完成计算。该函数定义了多个特征彼此之间冲突比例矩阵的计算过程，这里的冲突比例矩阵就类似于相关系数矩阵，用于表示多个特征彼此之间冲突比例：

def conflict_ratio_matrix(data):
    """
    冲突比例计算函数
    
    :param data: 计算冲突比例的dataframe
    :return:冲突比例矩阵
    """
    if isinstance(data, pd.DataFrame):
        data = data.values

    num_features = data.shape[1]
    # 创建空特征比例矩阵
    conflict_matrix = np.zeros((num_features, num_features))

    # 两层循环挑选两个特征
    for i in range(num_features):
        for j in range(i+1, num_features):
            # 计算特征冲突特征总数
            conflict_count = np.sum((data[:, i] != 0) & (data[:, j] != 0))
            # 计算不为0的特征总数
            total_count = np.sum((data[:, i] != 0) | (data[:, j] != 0))
            # 计算冲突比例
            conflict_ratio = conflict_count / total_count
            conflict_matrix[i, j] = conflict_ratio
            conflict_matrix[j, i] = conflict_ratio

    return conflict_matrix

然后尝试带入四个离散变量，进行冲突比例的计算：

conflict_ratio_matrix(data[['x1_binned', 'x2_binned', 'x3', 'x4']])

array([[0.        , 0.42857143, 0.44444444, 0.5       ],
       [0.42857143, 0.        , 0.625     , 0.125     ],
       [0.44444444, 0.625     , 0.        , 0.2       ],
       [0.5       , 0.125     , 0.2       , 0.        ]])

冲突比例矩阵是一个对角线元素为0的对称矩阵

其中，矩阵中的第(i, j)个元素代表第i个特征和第j个特征的冲突比例，例如(1, 2)=0.42857表示第一个特征和第二个特征冲突比例为0.42857。能够看出，这四个特征中并不存在没有冲突（即互斥）的特征，只能看到2、4和3、4特征冲突比例较小：

data[['x1_binned', 'x2_binned', 'x3', 'x4']]

	x1_binned	x2_binned	x3	x4
0	0.0	1.0	1	0
1	1.0	1.0	1	0
2	1.0	0.0	0	1
3	1.0	1.0	1	0
4	0.0	0.0	1	0
5	1.0	1.0	1	1
6	0.0	1.0	1	0
7	0.0	0.0	0	1
8	0.0	0.0	1	0
9	1.0	0.0	1	1

• 图展示与着色

  然后我们将冲突比例矩阵转化为如下所示的图，即不同的点代表着不同的特征，而如果两个特征存在冲突，则两个点之间构建一条无向边，边的权重就是冲突比例：

当然，关于是否互斥，其实可以通过max_conflict_rate进行调节，我们假设max_conflict_rate=0.3，则上图中x3和x4、x2_binned和x4的冲突比例小于0.3，所以这两组特征是互斥的，我们可以将连接这两组特征的边删除，删除后的图如下：

这里需要注意，这里我们设置的max_conflict_rate=0.3只是用于当前例子展示所用。真实情况下max_conflict_rate的取值建议设置为0.1或者更小的数，以确保模型精度。相关超参数取值推荐会在本章课程的最后进行讨论。

在完成图转化之后，接下来我们将特征捆绑问题视作一个图着色的问题，即需要用最少的颜色对图上的四个点进行着色，并要求相邻的点（彼此有线段连接的点）颜色不同。

  具体着色的流程是会先从度（边的个数，也被成为degree）更大的点进行着色，例如上图中的四个点的degree如图所示，很明显x1_binned的度最大，然后是x2_binned和x3，这里我们先将x1_binned着色为红色（颜色可以随机选取），然后由于x3和x2_binned彼此相连，并且都和x1_binned相连，因此x3和x2_binned颜色不能相同，且不能和x1_binned相同，因此这里分别给x3和x2_binned着色为黄色和绿色，最后是x4，由于x4和x1_binned相连，所以x4不能用红色，而x4和x3、x2_binned没有相连，并且为了图上出现的颜色尽可能少，所以x4可以用绿色或者黄色，考虑到x4和x2_binned冲突比例较小，互斥程度较大，因此可以给x4使用绿色，最后着色结果如上图所示。

• 特征捆绑过程

  最后，我们把相同着色的点（特征）进行捆绑。捆绑过程并不复杂，核心是需要对特征取值进行合理转化。而具体的转化过程中，LGBM会根据主特征的最大取值设置一个offset值，然后对合并进来特征的非零值加上这个offset值，然后再让这两个特征取值相加。例如data数据集中，我们将x4并入x2_binned中，则offset=1

data['x2_binned']

0    1.0
1    1.0
2    0.0
3    1.0
4    0.0
5    1.0
6    1.0
7    0.0
8    0.0
9    0.0
Name: x2_binned, dtype: float64

然后对x4的非零值+offset，并构成新的特征’x2_binned&x4’具体计算过程如下：

arr = np.array(data['x4'])
arr[arr != 0] += 1
arr

array([0, 0, 2, 0, 0, 2, 0, 2, 0, 2])

data['x2_binned&x4'] = arr + data['x2_binned']
data

	x1	x2	x3	x4	y	x1_binned	x2_binned	x2_binned&x4
0	1.2	4.7	1	0	1	0.0	1.0	1.0
1	2.9	5.5	1	0	0	1.0	1.0	1.0
2	2.6	3.9	0	1	1	1.0	0.0	2.0
3	3.3	6.2	1	0	0	1.0	1.0	1.0
4	2.0	3.5	1	0	1	0.0	0.0	0.0
5	2.5	4.5	1	1	1	1.0	1.0	3.0
6	1.4	5.1	1	0	0	0.0	1.0	1.0
7	2.1	2.7	0	1	0	0.0	0.0	2.0
8	1.7	4.1	1	0	1	0.0	0.0	0.0
9	3.0	3.8	1	1	1	1.0	0.0	2.0

至此，我们就在data这个简化的数据集上完成了EFB特征捆绑过程，经过连续变量分箱和特征捆绑，实际上接下来带入进行模型训练的特征就只有x1_binned、x2_binned&x4和x3这三个特征：

data[['x1_binned', 'x2_binned&x4', 'x3']]

	x1_binned	x2_binned&x4	x3
0	0.0	1.0	1
1	1.0	1.0	1
2	1.0	2.0	0
3	1.0	1.0	1
4	0.0	0.0	1
5	1.0	3.0	1
6	0.0	1.0	1
7	0.0	2.0	0
8	0.0	0.0	1
9	1.0	2.0	1

为了方便我们后续调用，我们将data进行本地保存：

data.to_csv('data.csv')

  至此，我们就完整介绍了LGBM算法在建模前的特征压缩部分算法的原理及其实践过程。下一小节我们将继续介绍每次建树前的GOSS采样、LGBM决策树训练方法与直方图优化算法。