标签：Tri 剪枝 gt based lt optimization TOOCEP xt 决策树

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

论文概况	详细
标题	《Tri-objective optimization-based cascade ensemble pruning for deep forest》
作者	Junzhong Ji, Junwei Li
发表期刊	Pattern Recognition
发表年份	2023
期刊等级	中科院 SCI 期刊分区(2023年12月最新升级版）1 区，CCF-B
论文代码	文中未公开

作者单位：
Faculty of Information Technology, Beijing University of Technology, Beijing Artificial Intelligence Institute, Beijing Municipal Key Laboratory of Multimedia and Intelligent Software Technology, Beijing, 100124 China

研究动机

集成学习是一种针对给定任务训练并组合多个基学习器的机器学习方法，但是生成和组合这些基础学习器不可避免地会导致存储需求和预测时间成本的增加。因此有许多集成剪枝算法被提出，这些算法选择原始集成的最优基分类器子集进行预测，以简化得到剪枝后的集成学习器。这些算法通常先通过排序、聚类、优化等方法搜索训练好的学习器的最优子集，然后剔除不在最优子集中的冗余学习器，在不牺牲集成预测性能的前提下，有效节省了集成的存储空间，加快了集成的预测速度。
Deep forest 与一般的集成系统只结合一层或两层基础学习器来生成最终预测不同，它在多层级联森林结构中训练和组合决策树。可见深度森林的分类性能是以高存储要求和高预测时间成本为代价的，随着级联层数的增加，这些问题将变得越来越严重。因此如何进行合理的剪枝，对于深度森林的进一步开发和规模化应用尤为重要。

文章贡献

针对深度森林中基分类器数量过多带来的时空开销，本文中提出了一种基于三目标优化的深度森林级联集成修剪算法 TOOCEP，该算法在级联森林的每一层学习最优决策树子集，并去除不在最优子集中的决策树。具体而言本文首先提出了一种基于三目标优化的单层剪枝方法 TOOSLP，通过同时优化精度、独立多样性和耦合多样性三个目标对其单层森林进行剪枝。前两个目标是单层森林本身的准确性和多样性，第三个目标用于处理被修剪的层与其前一层之间的耦合关系。在 TOOSLP 方法的基础上，提出了层叠集成剪枝框架对深层森林进行逐层剪枝。通过在 15 个 UCI 数据集上对该算法进行评估，实验结果表明 TOOCEP 在准确率和剪枝率方面优于几种最先进的方法，显著减少了深度森林的存储空间，加快了深度森林的预测速度。

本文方法

本文提出的 TOOCEP 算法架构如下图所示，左侧为深度森林结构，右侧为 TOOCEP 整体剪枝过程。模型主要针对每个级联层执行三目标优化的单层剪枝 TOOSLP，以寻找最优剪枝解 L^t。TOOSLP 主要有四个步骤：

TOOSLP 采用二元染色体 l^t 对 g^t(x^t) 中的决策树子集进行编码作为候选解，lt 的每一位表示 gt(xt) 中的决策树是否属于该子集；
定义精度 acc(l^t)、独立多样性 dI(l^t) 和耦合多样性 d^C(l^t) 三个目标函数，对候选解进行评价；
基于 NSGA-III 框架，采用选择、交叉、突变三种基本进化算子进行三目标优化，得到一组 pareto 最优前解；
从 Pareto 最优解集中挑选出 Accuracy 最高的解作为最终解 L^t，并对 g^t(x^t) 中不需要的决策树进行解码去除。

染色体编码

第 t 层的 TOOSLP 的剪枝方案表示从 g^t(x^t) 中选择决策树子集的方案，未被选择的决策树将从 g^t(x^t) 中删除，本文采用二元染色体 l^t 来编码 g^t(x^t) 的候选剪枝解。

l^t 的长度等于 g^t(x^t) 中决策树的个数，l^t_i=1 表示保留 h^t_i(x^t) 的第 i 棵决策树，l^t_i=0 表示删除这棵决策树。下图为 g^t(x^t) 根据 l^t 进行剪枝的过程，g^t(x^t, l^t)表示剪枝后的 g^t(x^t)。将 g^t(x^t, l^t) 的输出向量记为 f^t(x^t, l^t)，将 G(x) 进行剪枝记为 G∈(x)=(g¹(x¹, l¹), g²(x², l²), ···, g^t(x^t, l^t))。

适应度函数评估

在进化过程中采用适应度函数对染色体进行评价，TOOSLP 中使用的适应度函数包括准确率、独立多样性和耦合多样性。适应度函数如下公式所示，其中 l^t 是定义的候选解，Ω 表示 g^t(x^t) 的所有可能子集的集合。

第一个目标 acc(l^t) 表示保留决策树的预测精度，可以使用如下公式描述。假设存在一个验证数据集 S_va=(x_v, y_v)^V_v=1，vote(g^t(x^t_v, l^t))是一个投票函数。vote 首先对 g^t(x^t_v, l^t) 中保留的决策树的预测结果进行汇总，取汇总值最大的类作为 g^t(x^t_v, l^t) 的最终预测。I(·) 是一个指标函数，I(true)=1、I(false)=0。

第二个目标是最大化 g^t(x^t, l^t) 的独立多样性，即 g^t(x^t, l^t) 中保留决策树的多样性。假设 h^t_i(x^t) 和 h^t_j(x^t) 是两棵保留决策树，它们的多样性可以通过称为 q 统计量的成对多样性度量来计算，如下公式所示。

Z^ab 定义如下表所示，其中 Z¹¹ 表示被 h^t_i(x^t) 和 h^t_j(x^t) 正确分类的验证样本个数，V=Z⁰⁰+Z⁰¹+Z¹⁰+Z¹¹。Q^t_i,j 的取值范围为 -1~1，其值越大表示两棵决策树越相似，则多样性越小。

g^t(x^t, l^t) 的独立多样性可以通过对保留的决策树之间的所有成对多样性取平均值来计算，如下公式所示，其中 |l^t| 表示 l^t 中值为 1 的元素个数。d^I(l^t)的范围是 0~1，独立多样性越大，在 g^t(x^t, l^t) 中保留的表现多样的决策树越多。

第三个目标是耦合多样性，由于相邻层之间通过增强向量 f^t-1(x^t-1) 存在一些耦合关系，因此 g^t(x^t) 和 g^t-1(x^t-1) 之间的多样性也需要考虑。使用 g^t(x^t, l^t) 和g^t-1(x^t-1, l^t-1) 中保留的决策树之间的平均输出多样性来表示 g^t(x^t, l^t) 的耦合多样性，如下公式所示。

理论上 d^C(l^t) 的取值范围是 0~1，但实际上有些值并不会出现，例如以下两个极端情况。实际上 d^C(l^t) 的实际最大值很少大于 0.5，取值范围大致是 0~0.5 之间，该值越大说明 g^t(x^t, l^t) 与 g^t-1(x^t-1, l^t-1) 之间的差异越大。

假设 d^C(l^t)=0，此时 g^t(x^t, l^t) 中所有选择的决策树的输出与 g^t-1(x^t-1, l^t-1) 的输出完全相同。此时 g^t(x^t, l^t) 既不能学习到额外的有用信息，也不能提高 deep forest 的预测精度，其存在是没有意义的。
假设 d^C(l^t)=1，此时 g^t(x^t, l^t) 完全独立于 g^t-1(x^t-1, l^t-1)。此时增强向量对 g^t(x^t, l^t) 没有影响，不符合 deep forest 的设计思想。

基于上述三个适应度函数，可以评估 Ω 中的任意染色体，并采用三目标进化算法同时优化三个目标。

进化过程

三目标进化算法从生成初始种群开始，迭代搜索能够同时最大化 TOOSLP 三个目标函数的 pareto 最优解。设 P^t_w=(l^t,1, …, l^t,n, …, l^t,N) 表示第 t 层进化的亲本种群，l^t,n 为第 n 个体染色体，N 为群体大小。其中 O^t_w 表示第 w 代的子代种群，MaxGeneration 表示 TOOSLP 的最大代数，进化过程的主要步骤如下伪代码所示。

进化过程中选择、交叉和突变是三种核心的进化操作。此算法的选择算子为二进制锦标赛选择，首先从 P^t_w 中随机选择 N/2 条染色体，然后将目标函数最优的染色体加入到 O^t_w 中。重复这一过程，直到 O^t_w 的大小为 N。
交叉算子使用的是单点交叉，一个交叉操作的示例如下图所示，确定交叉点然后围绕该点交换两条染色体的位。

突变操作用于修改染色体中的位以产生新的染色体，一个突变操作的示例如下图所示，染色体的每一个位都有相同的可能发生改变。

最终解选择

经过进化过程，可以得到一组 pareto 最优前沿解，从多目标优化的角度来看，该集合中的所有解同等重要。但是，TOOSLP 只需要根据一个解对 g^t(x^t) 进行剪枝，本文选取集合中精度最大的解作为最终解 L^t，L^t∈P^t_{MaxGeneration}。

级联剪枝框架

级联集成剪枝框架 TOOCEP 采用上述的 TOOSLP 方法对深度森林进行逐层剪枝，整体的伪代码如下图所示，主要有三个关键步骤：

利用 g^t-1(x^t-1, l^t-1) 和 g^t(x^t) 对验证数据集进行预测；
Q^t_i,j 和 Q^t_{i,gt−1(x^(t−1), l^(t-1))} 分别预先计算并存储在 φ^I,t 和 φ^C,t 中；
利用 TOOSLP 方法求出 g^t(x^t) 的最优剪枝解 L^t，从 g^t(x^t) 中移除未被 L^t 选中的决策树。

实验结果

数据集和实验设置

数据集使用了 UCI 的 15 个数据集，这些数据集的基本信息如下表所示。在实验中使用五折交叉验证，对于一折的训练集、验证集和测试集的样本比例为 6:2:2，所有实验均进行 30 次独立实验。

训练集用于训练初始的 casForest G(x)，验证集用于 TOOCEP 算法寻找最优剪枝解 L^t，测试集用于测试剪枝算法的剪枝性能。casForest 使用标准级联结构，其中每个级联层包含。G(x) 的集合大小由 K、M 和 T 决定，其中 T 是在训练过程中自动确定的，因此可以通过控制每个森林中决策树的数量 M 来改变 G(x) 的集合大小。一些具体的参数设置如下表所示：

参数设置	说明
G(x)	casForest
Unit(k)	2 个 RF 和 2 个 ETs(K=4)
M	默认设置为 100，实验 2 设置为 50~150
进化算法	NSGA-III
种群规模 N	100
MaxGeneration	10000
交叉概率	0.9
突变概率	0.1

实验使用原始的深度森林作为 Baseline，与许多现有算法进行了广泛的比较，如下表所示。除了 PDF 和 VEGA，其余算法都是为一般集成模型设计的，因此采用这些方法对 casForest 的 Unit 进行修剪，而不是直接对 casForest 进行修剪。

对比算法类型	算法
基于顺序的剪枝算法	kappa、reduce error、MDEP、PDF
基于聚类的剪枝算法	ESJSCSS
基于优化的算法	PEP、NSE、VEGA

使用 Accuracy 和剪枝率来评价剪枝方法的性能，其中剪枝率是指被剪除的基分类器的比值，即 (num(G(x))−num(G'(x)))/num(G(x))，其中 num(G(x)) 为 G(x) 中的决策树个数。由于集成模型的存储空间和预测速度取决于集合中分类器的数量，因此剪枝率越大，剪枝模型所需的存储空间和预测时间越少。实验中 TOOCEP、PEP、NSE、VEGA 的剪枝率是自动确定的，而其他五种比较算法的剪枝率需要参数设置。为了公平比较，在所有的对比实验中，这五种方法的剪枝率都是经过参数学习后选择的最优值。

三目标优化的效果

本文用精度、独立多样性和耦合多样性来评价 TOOSLP 的解，以精度为基本目标对这些目标进行重组，以此验证独立多样性和耦合多样性的有效性。

TOOCEP 变体	说明
TOOCEP_(acc)	acc(l^t) 一个优化目标
TOOCEP_(acc+d^C)	acc(l^t) 和 d^C(l^t) 两个优化目标
TOOCEP_(acc+d^I)	acc(l^t) 和 d^I(l^t) 两个优化目标
TOOCEP	acc(l^t)、d^I(l^t)和 d^C(l^t) 三个优化目标

这四种组合在 Vehicle、Sonar、WDBC 3 个数据集上的平均精度如下表所示，可以看到这四种组合的平均精度高于不进行剪枝。以准确度为唯一目标时，TOOCEP_(acc) 平均准确度分别比基线有一些提高，当第二种目标加入时剪枝算法的平均精度没有明显提高。将这两种多样性都进行考虑时，TOOCEP 的平均准确率高于其他三种组合。这表明仅考虑一种优化目标不能很好地提高 TOOCEP 的准确性，对于 casForest 这样的多层级联结构，这两种多样性是相辅相成、不可缺少的。独立多样性反映了位于同一层的决策树的多样性，耦合多样性反映了位于不同层的决策树的多样性。

30 次运行的不同目标组合的精度分布如下箱型图所示，可见基线模型的精度分布在较低水平，TOOCEP_(acc)、TOOCEP_(acc+d^C 和 TOOCEP_(acc+d^I) 的精度处于中等水平，TOOCEP 的精度始终处于最高水平。

下图显示了 Vehicle、Sonar、WDBC 3 个数据集上的不同目标组合的剪枝率，基线的剪枝率为 0。TOOCEP 实现了比其他三种组合更高的剪枝率，表明这两种多样性目标有助于减少级联森林的总体规模。独立多样性比耦合多样性起着更重要的作用，这可能是因为同一层中的决策树是在相同的输入 xt 上构建的，并且更有可能产生类似的决策树，TOOCEP 中使用的独立多样性和耦合多样性是互补和不可或缺的。

不同集成规模的算法比较

此处基于 Vehicle 数据集比较了 TOOCEP 与其他 8 种算法在不同集成规模下的性能，将 K 的值设置为与其他实验相同，并设置每个 forest 中包含的决策树的个数 M 不同，以改变级联森林的原始的规模大小。下表展示了 M=50、75、100、125、150 时比较算法的平均准确率，当 M=75、100、150 时 TOOCEP 的精度最高，当原始集成规模增加时，剪枝模型的准确率略有波动，这表明基分类器数量的增加并不一定能提高集合的准确率。从结果可见 TOOCEP 排名第一，其次是reduce error 和 ESJSCSS，kappa 排在最后。

下表展示了 M=50、75、100、125、150 时比较算法的平均剪枝率，由于 kappa 剪枝、reduce error、MDEP、ESJSCSS、PDF 的剪枝率是由参数决定的，所以这些方法的剪枝率的标准差均为 0。当 M=100、125、150 时 TOOCEP 的剪枝率最高，PEP、NSE、VEGA、TOOCEP 的剪枝率普遍较高且波动较小，而其他方法的剪枝率变化较大。结果表明，与基于排序和聚类的剪枝算法相比，基于优化的剪枝速率基本不受集合大小的影响。

TOOCEP 在准确率和剪枝率上都取得了良好的效果，这表明本文提出的 TOOCEP 在不同的集成规模下都表现良好。

算法在不同数据集上的比较

将 TOOCEP 与 15 个不同数据集上的 8 种比较算法进行了比较，下表展示了这些算法在 15 个数据集上的平均准确率，从实验结果可见对于平均精度，TOOCEP 在 15 个数据集中的 5 个数据集上达到了最高精度，其他方法中最多只有 3 个数据集达到了最高精度。

下表展示了这些算法在 15 个数据集上的平均剪枝率，可见 TOOCEP 具有压倒性的优势，在 15 个数据集中的 12 个上表现最好。大部分 TOOCEP 的剪枝率都在 75% 以上，即原始深度森林中决策树的保留率不到 1/4。

使用假设检验评估实验结果，结果如下面两张图所示，其中横轴表示平均排名，纵轴表示方法。可以看到 TOOCEP 在准确率和剪枝率上排名第一，而且 TOOCEP 对剪枝率的投影与其他 7 种比较算法(PEP 除外)没有重叠，表明 TOOCEP 的剪枝率明显优于这 7 种比较算法。

接着可视化了四种基于优化的算法在 Vehicle、Sonar 和 WDBC上的分层修剪率，结果如下图所示，从结果可见本文算法在三个数据集上基本都获得了最高的各层剪枝率。随着级联层数 t 的增加，TOOCEP 算法的剪枝率也会增加，这是因为 TOOCEP 的耦合多样性目标反映了位于不同层的决策树的多样性。当级联层的数量增加时，TOOCEP 可以识别更多冗余的决策树。

TOOCEP 算法的主要动机之一是通过减少决策树数量来简化深度森林，从而缓解繁重的存储需求和较高的预测时间成本。因此对于 TOOCEP 来说，剪枝率更有利于减少深林的储存空间，提高预测速度。为了更清晰地描述 TOOCEP 的优势，此处验证了剪枝算法在减少存储空间和提高深度森林预测速度方面的效果。实验结果如下面两张表所示，可见本文方法在降低深层森林的存储和预测时间成本方面取得了优异的效果。