Paper Reading 是从个人角度进行的一些总结分享，受到个人关注点的侧重和实力所限，可能有理解不到位的地方。具体的细节还需要以原文的内容为准，博客中的图表若未另外说明则均来自原文。

论文概况	详细
标题	《ControlBurn-Feature Selection by Sparse Forests》
作者	Brian Liu, Miaolan Xie, Madeleine Udell
发表会议	ACM SIGKDD Conference on Knowledge Discovery and Data Mining(KDD)
发表年份	2021
会议等级	CCF-A
论文代码	https://github.com/udellgroup/controlburn

作者单位：
Cornell UniversityIthaca, New York, USA

研究动机

基于树结构的继承特征选择的通常能取得好的性能，它的原理是对各个特征进行打分后排序，根据顺序选出最重要的特征。但是当一组特征有较高的相关性时，往往整个特征组都会被选择，此时就忽视了独立存在的重要特征。例如图中的示例，在左边的图是泰坦尼克号数据集上用 RF 得出的特征重要性排名，RF 认为 age、sex 和 pclass 是最重要的特征。作者通过添加人工合成的特征 height、weight、femur 和 tibia 来修改原数据集，这几个特征和 age、sex 高度相关，重新实验后 weight 和 height 这两个合成噪音特征被认为是更重要的，同时重新实验后 pclass 高于 age。

实验表明，当数据集中存在大量相关特征时，重要的特征的影响力可能比实际小得多。如果使用的是简单的特征选择方法，它可能会选择整个组、忽略整个组或从组中选择错误的特征。

文章贡献

针对存在大量相关特征时重要特征的影响被削弱的问题，本文设计了一种通过稀疏森林来消除相关偏差的特征选择算法 ControlBurn。首先使用套袋和提升等方法生成森林，然后通过一个平衡特征稀疏性和预测性能的组 LASSO 惩罚目标为每棵树选择稀疏权值，从而减少树的数量。与 Wrapper 特征选择方法不同，ControlBurn 只需要一次训练迭代即可运行。通过实验说明，当应用于具有相关特征的数据集时，ControlBurn 优于传统的特征选择算法。

本文方法

整体流程

对于一个 m 行 p 列的特征矩阵和 m 行的标签 y，建立一个包含 n 棵决策树的森林进行预测，其中每棵决策树 ti 输出一个预测向量 ai。令一个 p 列的 binary 型向量 gi 作为指示向量，当 gij=1 时如果 j∈{1,…,p} 则对决策树 ti 生成一个分割。固定正则化参数 λ>0，引入 n 行非负变量 w 来表示森林中每棵树的权重，wi=0 的树不使用所以可以被剪枝。设以 ai 为列的 m 行 n 列的矩阵 A，则 n 位 Aw 为权重 w 的树对实例的预测，p 位 Gw 表示森林中每个特征的总权重。
为了得到一个预测能力强的特征稀疏森林 Gw，需要为预测问题定义一个损失函数 L(A,w,y)。受到 LASSO 的启发，损失函数的目标是在每棵权重 w≥0 的上将损失与稀疏正则化一起最小化，有如下公式所示:

该公式可以等价于如下的形式，其中 ui 是树 i 中使用的特征数。该目标鼓励使用稀疏模型，正则化代价会随着集成中使用的特征数量的增加而增加。

通过上面的公式可以得到优化后的 w，集成时只使用权值 w>0 的树，w=0 的树被省略。如果 (Gw)j 不为零，则可以称特征 j 在集成中被选中。和 LASSO 回归在选择的特征上重新调整最小二乘回归模型以减少最终模型的偏差的思想类似，本文算法最后是在选择的特征上拟合新的树集成模型。

森林生成

传统的方法通常不具备较高的多样性，例如当树的深度够深时可能会包含所有的特征。此时对于任何输入 λ，唯一的稀疏解 w*=0 表示所有的特征全部使用或全部不使用。因此本文设计了两种森林的生成方法，这些方法与该系列最优的算法性能接近。

增量深度套袋

该方法通过增加树的深度 d 来增加森林多样性，深度为 d 的树最多可以使用 d²−1 个特征，只有一个超参数 d^max 表示即树的最大生长深度。由于 Bagging 方法能防止过拟合，所以该超参数越大越好，允许 d^max=p。

在当前深度中每次向集合添加新树时都会记录训练损失，当训练损失收敛时算法增加深度 d 并开始添加更深的树。如果集合中最差的 N 棵树的损失都低于 ε，就可以认为损失达到了收敛，实验时通常取 N= 5 和 ε=10^-3。

增量深度套袋提升

该方法使用包外误差(OOB)自动确定树的最大深度，使用 bagging 作为梯度增强的基础学习器，在不牺牲精度的前提下增加多样性。

每次迭代生长的树的数量取决于集合的训练误差收敛的速度，每次增强都会增加树的深度并更新伪残差，通过设置如下公式所示的 ei 完成。

设 δ 为提升迭代之间 OOB 的阈值，当 δ<0 时算法终止。

下图为 UCI 数据集中 abalone 的运行结果，散点图显示了 OOB 随着提升迭代次数增加的变化趋势，可见在第六次提升迭代时终止。线形图显示了测试误差随提升迭代次数的变化情况，在第七次提升迭代时测试最小，与终止时的迭代次数接近。

ControlBurn 使用增量深度套袋提升比增量深度套袋更好，OOB 早停规则不仅不需要超参数，也可以限制森林的大小，减少了优化步骤的计算时间。

优化变量

特征分组

在某些问题中，可能需要将特征选择限制为每次选择一组特征，而不是单个特征。原先的定义是 ui 为树 ti 使用的特征数量，现在按照如下公式重新定义 ui，其中 ck 是特征组 k 的成本，Tk 是树 i 使用的特征组的集合。

非齐次特征成本

在某些问题中，选择一个特征的成本可能与选择另一个特征的成本有显著不同，也可以将这种非同质特性成本纳入框架中。将 ui 按照以下公式进行重新定义，其中 cj 是特征 j 的成本，Ti 是树 i 使用的一组特征。

Sketching

ControlBurn 的优化与数据中的样本数量成线性关系，可以对 X 进行 Sketching 来改进运行时间。设 S∈R^s×m 是采样的 Sketching 矩阵，可以将优化问题修改为如下公式。

实验结果

ControlBurn 的设置

ControlBurn 使用增量深度套袋增强生成森林，优化时使用逻辑损失作为损失函数 L。优化后删除权重为 0 的特征，在剩余特征上运行随机森林算法，整体流程如下伪代码所示。

正则化参数 λ 控制 ControlBurn 选择的特征数量，实验使用二分法来找到产生所需特征数量 k 的 λ 值。本文的目标是产生一个可解释的模型，由于含有较多特征时模型会难以解释，因此在实验中要求 k≤k^max:=10。从一个足够大的 λ 值开始(k=0)，初始化 k′=1 表示希望 ControlBurn 选择的功能的数量。对 λ=λ/2 进行二等分后运行算法得到 k，如果 k＜k′ 则更新 λ=λ/2，否则如果 k>k′ 则更新 λ=λ+λ/2，如果 k=k′ 则更新 k′=k′+1。重复上述步骤，直到 k′>kmax 时得到 λ。

实验设置

通过预实验确定 ControlBurn 优于 filter 方法，而 Wrapper 算法因为每次评估新的特征子集时都必须对模型进行重新训练，ControlBurn 只需要一次训练迭代就可以实现特征选择。下图展示了对 PMLB 数据集进行了 1000 行的子采样后 ControlBurn 和 RFE 之间的计算时间。

接下来的实验主要和基于随机森林的特征选择方法对比，也就是先拟合随机森林分类器，按 MDI 特征重要性分数排序的特征，对比的指标为 AUC-ROC。

半合成数据集实验

选择 UCI 的 Chess 数据集，采用随机森林 MDI 重要性决定的 3 个最重要的特征，添加 σ=0.1 的高斯噪声来创建有噪声的副本。重复这一过程将有重要的特征复制 3、5、7 次，分别增加 9、15、21 个高度相关的特征。MDI 特征重要性在相关特征组中被稀释，降低了相关组中任何特征的“重要性”等级。
实验结果如下图所示，可见 ControlBurn 在原始数据上与随机森林几乎相同，随着相关特征数量的增加，ControlBurn 的性能明显优于随机森林。说明即使存在一组强相关的特征，ControlBurn 也可以有效地选择特征。

基准数据集实验

在 PMLB 中的所有 43 个二分类数据集上进行实验，使用 ControlBurn 和随机森林选择 k 个特征，并记录训练后的随机森林间的 ROC-AUC 差异。实验结果如下图所示，可见 ControlBurn 在大多数这些数据集上与随机森林相似，平均表现比随机森林基线好。

真实数据集实验

下图中展示了 ControlBurn 与随机森林的对比情况，在 Adult income 数据集中选择 k=3 个特征时 ControlBurn 的性能比随机森林好得多；在 Audit 数据集中对于任何 k 的取值，ControlBurn 的性能都优于随机森林；在基因表达数据集中，在不同的 k 上 ControlBurn 都优于随机森林。

下图显示了 Adult income 数据集中按 MDI 重要性排名的前 20 个特征的相关热度图，ControlBurn 选择的前 3 个特征以粗体显示。可以看出高相关性的特征会稀释重要的特征，而 ControlBurn 收到的影响较小，随机森林则会忽略这些特征。

无信息连续特征的偏差

MDI 特征重要性偏向于具有更多潜在分裂的特征，会导致连续特征的重要性被夸大。使用 ControlBurn 来选择相关的特征子集，并通过 MDI 重要性计算模型中无信息特征的特征等级。结果如下图所示，可见当选择完整的特征集时，无信息的特征通常出现在顶级特征排名中。当增加 λ 并选择更少的特征时，无信息特征会降级，ControlBurn 减轻了来自无信息连续特征的偏见。