LightGBM Exclusive Feature Bundling

互斥特征合并（Exclusive Feature Bundling）

高维的数据通常是稀疏的，这种特征空间的稀疏性给我们提供了一种设计一种接近无损地降维的可能性。特别的，在稀疏特征空间中，许多特征是互斥的，换句话说，大部分特征不会同时取非0值，例如One-hot之后的类别特征他们从不同时为非0值。我们可以合并互斥的特征为单一特征（我们将这个过程称为Exclusive Feature Bundle）.通过仔细设计特征扫描算法，我们从合并特征中构建出与单个特征相同的特征直方图。通过这种方式，直方图构建算法的时间复杂度从O(ND)O(ND)，降到O(N×bundle)O(N×bundle)，其中NN为样本点数目，DD为特征维度。通常，bundle << DD，我们能够在不损失精度的情况下极大地加速GBDT的训练。

那么接下来有两个问题需要处理：

• 需要合并哪些特征
• 如何合并这些特征

Greedy Bundling

找出最优的 bundle 组合数是一个 NP 问题，LightGBM通过将原问题转化为”图着色”问题进行贪心近似解决。

首先创建一个图G(V,E)G(V,E)，其中VV就是特征，为图中的节点，EE为GG中的边，将不是相互独立的特征用一条边连接起来，边的权重就是两个相连接的特征的总冲突值，这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点（特征）。具体算法过程如下：

Merge Exclusive Features

该过程主要是关键在于原始特征值可以从bundle中区分出来，即绑定几个特征在同一个bundle里需要保证绑定前的原始特征的值在bundle中能够被识别，考虑到直方图算法将连续的值保存为离散的bin，我们可以使得不同特征的值分到bundle中的不同bin中，这可以通过在特征值中加一个偏置常量来解决，比如，我们在bundle中绑定了两个特征A和B，A特征的原始取值为区间[0,10)，B特征的原始取值为区间[0,20），我们可以在B特征的取值上加一个偏置常量10，将其取值范围变为[10,30），这样就可以放心的融合特征A和B了，因为在树模型中对于每一个特征都会计算分裂节点的，也就是通过将他们的取值范围限定在不同的bin中，在分裂时可以将不同特征很好的分裂到树的不同分支中去。具体算法如下：