目录
Paper Reading 是从个人角度进行的一些总结分享，受到个人关注点的侧重和实力所限，可能有理解不到位的地方。具体的细节还需要以原文的内容为准，博客中的图表若未另外说明则均来自原文。
| 论文概况 | 详细 |
|---|---|
| 标题 | 《SAFE: Scalable Automatic Feature Engineering Framework for Industrial Tasks》 |
| 作者 | Qitao Shi, Ya-Lin Zhangy, Longfei Li, Xinxing Yang, Meng Li, Jun Zhou |
| 发表会议 | IEEE International Conference on Data Engineering(ICDM) |
| 发表年份 | 2020 |
| 会议等级 | CCF-A |
| 论文代码 | 文中未公开 |
作者单位：
- Ant Financial Services Group {qitao.sqt, lyn.zyl, longyao.llf, xinxing.yangxx, lm168260, jun.zhoujung}@antfin.com
研究动机
机器学习方法的性能在很大程度上取决于特征的质量，生成良好的特征集是模型是否有高性能的关键步骤。因此大多数机器学习工程师都要花费大量的精力来获取有用的特征，这个过程费时且乏味。在实际工业任务中对机器学习的需求不断增长，在所有任务中执行手工特征工程变得不切实际，这促进了自动特征工程 AutoFE 的研究。一些 AutoFE 方法使用基于强化学习的策略，这类方法需要多次尝试，并且需要在每一轮中生成一个新的特征集并对其进行评估，这使得它们在工业任务中难以应用。也有一些基于迁移学习或基于元学习的方法，但是它们需要在各种数据集上进行大量的实验来训练，并且难以引入新的算子或增加父特征的数量。一些方法遵循生成选择过程来运行，但是它们通常是在特征生成阶段生成所有合法的特征，然后从中选择一个子集特征，因此时间和空间复杂度极高。实际业务数据的规模通常很庞大，对空间和时间复杂度的要求很高，同时算法要具备一定的灵活性和可扩展性来支持业务的变化。
文章贡献
本文提出了一种可扩展自动特征工程方法 SAFE，它包括特征生成阶段和特征选择阶段，具备较高的计算效率、可扩展性，能满足实际业务问题的要求。不同于使用算子枚举所有的生成特征，本文的特征生成阶段专注于挖掘原始特征对，以更高的概率生成更有效的新特征。在特征选择阶段，本文的方法考虑了单个特征的信息量、特征对的冗余性、树模型评估的特征重要性。通过实验证明，SAFE 算法在大量数据集和多个分类器上具有优势，与原始特征空间相比预测精度平均提高了6.50%。
本文方法
整体框架
SAFE 的整体工作流程如下伪代码所示，所提出的自动特征工程算法是一个迭代过程，每次迭代包括特征生成和特征选择两个阶段。由于特征空间是无限的，所以穷举搜索往往无效。即使操作符和迭代的数量有限，穷举搜索也可能导致组合爆炸。为了避免这个问题，本文使用 XGBoost 挖掘当前基本特征集 Xi 之间的关系，实现缩小特征组合的搜索空间。然后根据信息增益比对特征组合进行排序和过滤，将预定义的算子应用于具有高信息增益比的特征组合上，得到新的特征集 X~i。将基本特征 xi 与生成的特征 X~i 结合，得到候选特征集，表示为 X^i= Xi∪X~i。
由于特征集的数量仍然非常大，在此之后 SAFE 使用了高效的特征排序和选择方法。其基本思想是找到信息特征，去除冗余特征，然后对每个特征进行评分实现对特征的过滤。首先挑选出对标签影响较大的特征，然后利用 pearson 相关系数去除冗余特征，最后使用 XGBoost 根据使用该特性的所有分割的平均增益对其余特性进行评分。考虑到可扩展性和效率，SAFE 只选择得分最高的特征作为 Xi+1 进行下一次迭代。
特征生成
特征生成阶段的目标是利用现有的特征集 Xi 生成新的特征集 X~i，同时希望在保留有效特征的同时减少新生成的特征的数量。此时的训练集、验证集和测试集表示为 Ditrain、Divalid 和 Ditest，原始特征生成的搜索空间如公式(2)所示，其中 M 为原始特征的个数，Oi 为 i 元算子的集合。
搜索空间中的元素个数如公式(3)所示，其中 Akn 表示从 n 个元素的集合中获得 k 个元素的有序子集的方式的数量。
特征组合关系
该步骤的目的是缩小特征的搜索空间，并保留有信息的特征组合。首先在 Ditrain、Divalid 上训练一个 XGBoost。XGBoost 模型中的基学习器是如下图所示的回归树，此处称 {x(i)} 为拆分特征、{vi} 为对应的拆分值，不作为拆分特征的特征称为非拆分特征。叶子节点的父节点表示为 lj，从根节点到 li 的树的路径上的不同分裂特征可以表示为 pi，例如图中的 p1={x(1),X (2),X(3)} 和 p1={x(1),X (2),X(4)} XGBoost 模型中所有树的所有 k 条路径都可以表示为 P={p1,…,pk}。
SAFE 使用 XGBoost 主要基于两个基本假设：
- 对于一元算子，基于分裂特征生成的特征比基于非分裂特征生成的特征更有效；
- 对于其他算子，基于相同路径的分裂特征生成的新特征比基于不同路径的分裂特征生成的新特征效率更高，后者仍然比基于非分裂特征生成的新特征效率更高。
基于这两个基本假设，可以在这些路径上找到特征或特征组合进行特征生成。这种方式的搜索空间如下公式所示，其中 k 是路径的个数，Oi 表示 i 元算子的集合。
搜索空间中元素的最大个数如下公式所示，其中 pji 表示路径上的第 j 个特征。不同路径上的一些特征组合可能是相同的，所以实际的数量会比这个值小得多。
排序特征组合
为了进一步缩小特征生成的搜索空间，使用信息增益比对搜索空间中的特征和特征组合进行排序。取有 q 个元素的特征组合 {x(1),…,X(q)} 为例，目前已经知道它们产生划分的阈值组成的向量 V1,…,Vq，产生划分的特征和阈值可以将所有记录分成 Πqi=1(|Vi|+1) 个部分。
用这些部分的信息熵减去原始信息熵可以计算出信息增益比，该阶段算法的伪代码如下所示。
生成特征
使用信息增益比最高的 γ 个特征或特征组合生成 ∑Mi=1(γi×|Oi|) 个新特征X~i，其中 γi 表示具有 i 个特征的特征组合的个数。由于搜索和生成的特征数量远少于穷举搜索，因此可以在大型数据集上使用迭代特征生成策略。
特征选择
候选特征 X^i 由本次迭代中的基本特征 Xi 和生成的特征 X~i 组成，这些特征重要性可能不相等。为了高效地选择信息量更大的特征，采用了包含 3 个步骤的特征选择过程：
- 根据信息值去除预测能力较低的特征；
- 根据 pearson 相关系数去除冗余特征；
- 使用 XGBoost 对剩余的特征进行排序。
去除无信息特征
由于一些候选特征对目标影响很小或没有影响，所以第一步是去除预测能力低的特征，该阶段算法的伪代码如下伪代码所示。
信息值 IV 是衡量一个特征对目标的影响程度的指标，公式如下公式所示。其中 np 和 nn 分别表示所有正样本和负样本的个数，nip 和 nin表示第 i 个 bin 中正样本和负样本的数量。
下表是用于删除低预测能力的特征的经验法则，通常选择预测能力中等和较强的变量进行模型开发，本文取特征选择的阈值为 α=0.1。
去除冗余特征
此时的候选特征具有一定的预测能力，但有些特征是冗余的。此时只需要保留其中一个特征，该阶段算法的伪代码如下所示。
皮尔逊相关性用于表示两个特征线性相关的程度，绝对值为 1 表示两个特征完全线性相关，绝对值为 0 表示两个特征之间不存在线性关系。特征 x(i) 与 x(j) 之间的 Pearson 相关性计算公式如下，其中 x(i) 与 x(j) 表示特征 i 和特征 j 的所有元素的平均值。
通常使用下表的取值范围来判断变量的相对强度，此处将 pearson 相关的阈值 θ 设为 0.8，最后使用 XGBoost 根据所有分割的平均增益对剩余的候选特征进行排序
复杂度分析
SAFE 框架在挖掘特征组合关系和特征重要性排序阶段时，主要的复杂度来源于训练 XGBoost 的过程。它们的时间复杂度分别为 O(N·M·K1·D1 + N·M·logR) 和 O(N·M^BK2D2 + N·M^B· logR)，其中的符号的含义如下表所示。
| 符号 | 含义 |
|---|---|
| K1 和 K2 | 树的总数 |
| D1 和 D2 | 树的最大深度 |
| R | 每个块的最大样本数 |
| M^B | 去除冗余特征后的特征数 |
特征生成和去除无信息特征后的特征个数分别表示为 M^ 和 M^A，其他四个阶段的时间复杂度为：
| 算法步骤 | 时间复杂度 |
|---|---|
| 特征组合排序 | 2D1·K1·A2D1 个二进制特征组合，该阶段的复杂度为 O(2D1·K1·N·D12) |
| 特征生成 | 将生成 γ2× |
| 去除低信息特征 | 算法 3 的第三步和第四步的时间复杂度分别为O(N) 和 O(N)，总时间复杂度是 O(M^N) |
| 去除冗余特征 | 每个特征对计算一次 pearson 系数，Pearson 系数计算的时间复杂度为 O(N)，该阶段的总时间复杂度为 O(N(M^A)2) |
XGBoost 中的树通常并不深，所以可以将 D 视为常量并忽略它。对于数据量较大的实际数据集，logR < logN < M < M^C < M^B < M^A < M^ << N，M^=γ2|O2|, logR < K1,K2。所以 SAFE 的整体时间复杂度如下公式所示，可见可以通过控制 XGBoost 的树总数来控制生成的特征数量和算法的时间复杂度。
算法的时间复杂度和空间复杂度都很低，可以根据实际需要灵活调整。SAFE 算法对用户很友好，不需要像基于强化学习和迁移学习的方法那样学习繁琐的模型。超参数仅用于控制算法的复杂度，设置并不复杂。使用的 XGBoost 被公认为是一种具有良好并行性的算法，同时单个特征的信息值和每个特征对的 pearson 相关性也可以并行计算。
实验结果
数据集和实验设置
使用 12 个基准数据集上进行实验，基本信息如下表所示。
为了简单和通用性，在实验每个算法时只使用 +、−、x、÷ 四个基本的二元运算符。对比算法包括：原始特征(ORIG)、FCTree、TFC、Random(RAND) 和 SAFE-Important(IMP) 进行比较，使用 AUC 作为评价指标。
对比实验
在 AdaBoost、决策树(DT)，极度随机树(ET)、KNN、逻辑回归(LR)、多层感知器(MLP)、随机森林(RF)、线性核支持向量机(SVM)和 XGBoost 共 9 种最先进的分类算法上使用每个比较算法的生成特征，实验结果如下表所示，可见 SAFE 比其他比较算法具有明显的优势。
特征重要性比较
将 M 个原始特征与排名最高的生成特征组合成一个新的数据集，使用随机森林对特征重要性进行评分。实验结果如下图所示，可见 SAFE 生成的新特征(橙色)相对于原始特征(蓝色)更重要。
运行时间
下表列出了算法的实际执行时间，可以看出 SAFE 的运行效率很高。
特征稳定性
进一步比较每种算法生成的特征的稳定性，其基本思想是：当重复自动特征工程过程时，如果每次都生成相同的特征，则生成的特征更稳定。使用 Jensen-Shannon 散度(JSD)来评估不同自动特征工程算法生成的特征分布的稳定性，它是 Kullback-Leibler 散度(KLD)的一种变体，如下公式所示。
由于 TFC 的执行时间太长所以此处没有对其进行比较，实验结果如下表所示，可见生成的 SAFE 特征的稳定性具有一定的优势。
不同迭代次数的性能
将迭代轮数设置为 5，实验结果如下图所示。可见随着迭代的进行，性能可能会进一步提高，并在几轮之后变得稳定。在几轮之后可能没有发现新的有用的特征组合，因此特征不会更新，性能保持不变。
大规模数据集实验
在大规模的商业数据集上进行实验，数据集来自蚂蚁金服的欺诈检测任务，数据集信息如下表所示。
当数据集规模过大时，TFC 和 FCTree 两种方法的执行时间太长，所以它们不进行比较。实验结果如下表所示，可见 SAFE 可以持续提高性能，验证了所提出方法在实际工业任务中的有效性。
优点和创新点
个人认为，本文有如下一些优点和创新点可供参考学习：
- 很多 AutoFE 的工作都是使用 expand-and-reduce 的思想进行设计，这类方法通常会用一些特征生成算子枚举所有的生成特征，造成很大的搜索空间。本文的方法能够规避这个问题，使用了 XGBoost 来挖掘具有高信息量的特征组合，具备有效性的同时效率很高；
- 在第二阶段，SAFE 使用了 3 种不同的特征重要性指标对更高质量的特征按序提取，能够高效、有效地对特征进行选择；
- 本文对 SAFE 和一些已有的 AutoFE 的工作分析了计算复杂度，并做了大量的实验分析 SAFE 的性能，说服力强。