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

论文概况	详细
标题	《PCTBagging: From inner ensembles to ensembles. A trade-off between discriminating capacity and interpretability》
作者	Igor Ibarguren, Jesús M. Pérez, Javier Muguerza, Olatz Arbelaitz, Ainhoa Yera
发表期刊	Information Sciences
发表年份	2022
期刊等级	中科院 SCI 期刊分区(2022年12月最新升级版）1区、CCF-B
论文代码	http://www.aldapa.eus/res/weka-pctbagging/

作者单位：

Ikerlan Technology Research Centre, Basque Research and Technology Alliance (BRTA), 20500 Arrasate-Mondragón, Spain
Department of Computer Architecture and Technology, University of the Basque Country (UPV/EHU), Manuel Lardizabal 1, 20018 Donostia, Spain

研究动机

分类是机器学习中非常常见的问题，在很多领域理解模型如何完成分类是非常重要的，但并不是所有的分类算法都具有可解释性。一种被广泛使用的具有解释能力的分类算法是决策树，改进决策树算法结果的典型方法是集成算法，但集成后的模型往往也不可解释。合并树构建(consolidated tree construction, CTC)算法也是一种改进，它不仅提高了 C4.5 的识别能力，而且创建的分类器具有更高的鲁棒性。然而与 Bagging 算法相比，CTC 的分类性能较差。

文章贡献

针对 CTC 分类性能较差和 Bagging 的可解释性较差的问题，本文提出了一种结合 CTC 和 Bagging 的算法 PCTBagging。首先构建一棵不完整的 CTC，CTC 的规模由超参数合并比来确定，接着使用 Bagging 完成后续的树结构的生成。将 PCTBagging 的结果与 Bagging、CTC 和 C4.5 的进行比较，从实验结果可见 PCTBagging 在保持 CTC 的可解释结构的同时，实现了与 Bagging 相似的分类能力。

合并树构建

合并树构建(Consolidated Trees Construction, CTC)是一种不同于 Boosting 和 Bagging 的方法，CTC 从原始训练集中提取多个训练子样本，并基于每个子样本构建的树之间的相同部分构建单个树。该方法的核心在于确定 CTC 使用哪个变量在当前节点进行分割，这个的决定是根据不同子样本构建的树使用的特征进行投票得出的。一旦决定了用于分割树的特征，所有的树都强制使用该特征进行分割，该过程迭代重复直到满足停止条件。
下图展示了 CTC 的构建过程，首先使用定义的重采样方法获取多个数据子集，然后按照预定的顺序逐个节点构建。每个非叶节点以以下方式构建：

每个子样本在各自的树确定当前节点用于拆分的特征，例如图中是 (B,F,…,B)；
根据预定的规则决定是否拆分，如果决定创建一个叶节点，则跳到下一个要处理的节点继续创建；
统计每个子样本对应的树选择的特征的票数，例如图中使用特征 B 的数据子集最多。当投票数量足够多时，这个变量将被用来分割合并节点。如果该变量没有足够的投票，则将该节点合并为叶节点，跳到下一个要处理的节点继续创建；
确定使用的特征的分割规则，每个数据子集建立的树都是用该分割规则进行分裂。

本文方法

本文提出的合并树套袋(PCTBagging)算法是一种将 CTC 和 Bagging 的混合方法，在保持 CTC 的可解释性的同时利用 Bagging 增强分类的性能。PCTBagging 首先使用重采样对原始训练样本创建多个数据子集，接着利用这些子集创建了一个部分开放的 CTC 树，进而再基于 Bagging 得到 CTC 树多个副本。PCTBagging 通过在不同的百分点处停止合并树构建的过程，使用的方法是先构建完整的 CTC 树并确定此时内部节点的数量，然后选择其中的一个合并百分比来停止构建合并树，删除剩余的结点并开始 Bagging。100% 表示没有内部节点被移除(接近 CTC)，0% 表示没有内部节点被保留(接近 Bagging)。整合不同百分比的 PCTBagging 的方式是对内部节点包含的实例数量进行排序，从最小的节点开始删除，通过将内部节点转换为叶节点。算法的伪代码如下所示：

下图展示了一个例子，在第一张图片中显示了一个完整的合并树，其中内部节点使用阴影标记。选择固定 60% 的节点创建 PCTBagging，图中合并树有 10 个内部节点，因此将删除粗边描出的 4 个节点。接着使用开始时创建的多个数据子集在当前 CTC 结构中按 C4.5 的结构继续构造，这个步骤类似于 Bagging 的过程。由此产生的 PCTBagging 如第二张图所示，新生成的树保持了原始 CTC(阴影内部节点)60% 的结构，其余的树独立于相应的样本发展，但是由于每个数据子集都不同因此继续生长的 C4.5 也具有不同的结构。

PCTBagging 保持了 CTC 的可解释性，并部分利用了 Bagging 提高了分类能力，合并百分比决定了可解释的模型占多少部分。

实验结果

数据集和实验设置

数据集使用 KEEL知识库种的 96 个数据集，这些数据集的概况如下表所示，实验采用 5 次五折交叉验证，评价指标为 AUC。模型所提供解释的复杂性以决策树内部节点的数量来计算，在 PCTBagging 分类器中只考虑 CTC 的部分，计算成本被定义为训练所花费的时间。

通过预实验确定 CTC 使用 99% 覆盖率的平衡子样本来确定每个数据集的样本数量，下表显示了所有数据集所需样本数量的摘要。

每种算法分别采用四种重采样策略和两种确定样本数量的方法进行评估，下表显示了使用的重采样策略的缩写。

重采样方法的选择

下表显示了 96 个数据集中 Bagging 的 AUC 的平均值，以及每种重采样策略的 Friedman 检验结果，可见最好的采样策略是使用固定 50 个平衡样本。

比较所有可能的贝叶斯有符号秩检验结果下图所示，可见性能最差的重采样策略是 boot_cov，bal_N_S 与 boot_N_S 和 bal_cov 较为接近(rope)。

在计算成本方面 bal_N_S 比 boot_N_S 开销小，平均执行时间分别为 1567.35 ms 和 7381.91 ms，并且在 AUC 下具有相似的性能。下表显示了将贝叶斯有符号秩检验应用于这两种类型的重采样方法的时间对比结果，表明使用 bal_N_S 更快的概率为 93%。

下表的结果表明 CTC 的最佳重采样策略是使用 99% 覆盖率决定的样本数量的平衡子样本，平均 AUC 和 Friedman 检验的结论相同。

从图下根据 Bergman-Hommel 可以看出，使用由 99% 覆盖率决定的样本数量的平衡子样本获得的 AUC 值明显优于其他三种策略。

综上所述，对于 bagging 使用固定的 50 个平衡样本，对于 CTC 由 99% 的覆盖率值为每个数据集使用不同数量的平衡样本。下图展示了 PCTBagging 使用两种重采样策略获得的 AUC 值，可见 PCTBagging 使用和 Bagging 相同的重采样方法性能更高。

下图为对 PCTBagging 的 AUC 进行贝叶斯符号秩检验的结果，表明对于相同的合并百分比两种重采样策略是等效的。当百分比为 100% 并且使用相同样本时，CTC 和 PCTBagging 标记之间的差距是显著的。

对比结果

下图显示了 Friedman 检验确定的差异情况，每种算法使用了最合适的重采样方法。从结果可见 Bagging 和 PCTBagging 10%、20% 之间的差异不显著，PCTBagging 30% 之后的表现已经明显比 Bagging 差。在 60% 和 100% 之间的 PCTBaggings 没有差异，CTC 的性能比所有 PCTBagging 都差。

下图展示了根据上图得到的贝叶斯符号秩检验结果，只有在合并率为 10% 时 Bagging 与 PCTBagging 相似,从 20% 开始 Bagging 效果较好。合并率 60%~100% 之间的所有 PCTBaggings 的性能都较为相似。

下图展示了 96 个数据集的 Balanced accuracy 和 sensitivity 指标，Balanced accuracy 方面 CTC 效果更好，PCTBagging 的性能相当于 Bagging。sensitivity 上的结论和 AUC 的结果相似。

结构复杂性

下图显示了 CTC、11 个 PCTBagging 和 C4.5 的内部节点数量，结果表明 PCTBagging 的节点数量和合并百分比之间几乎呈线性关系。

下图显示了 Friedman 检验确定的差异情况，70% ~ 100% 的 PCTBagging 和 CTC 无明显差异，0%~30% 的 PCTBagging 和 Bagging 无明显差异。两大分类器集之间存在显著差异:合并百分比高于50%(包括CTC)的分类器与合并百分比低于50%的分类器。

下图显示了贝叶斯检验的结果，表明具有较低合并百分比的 PCTBagging 结构更简单的概率超过 95%。CTC 比 PCTBagging 100% 的结构更简单，相当于 PCTBaggin 90%，并且有 52% 的概率比 PCTBagging 80% 更复杂。

当比较相同合并百分比的内部节点数量和两种重新采样策略时，下图展示了贝叶斯检验的结果。结果表明用两种类型的样本构建的分类器是等价的，对于 0% 的合并百分比概率为 100%。

计算开销

构建分类器所需的平均时间的结果如下图所示，使用 50 个平衡样本比确定覆盖范围要花费更多的时间。

下图基于两种重采样的成对贝叶斯符号秩检验，对于高于 80% 的所有合并百分比，基于覆盖率的 PCTBagging 的构建时间较低。C4.5 是最快的，集成方法中 Bagging 是最快的，其次是 CTC。

下图显示以训练时间为度量标准的 Friedman 检验结果，可见 CTC 比其他算法都要快得多，PCTBagging 100% 是第二快的算法。而 Bagging 虽然排名第三但比其他任何 PCTBagging 都快得多，除 PCTBagging 60% 外 Bagging 明显快于任何 PCTBagging，其余 PCTBagging 之间的差异不显著。

下图所示的贝叶斯检验结果可见，CTC 的训练时间的成本明显低于其他算法的概率大于 83%，PCTBagging 100% 的计算开销也较小。

合并比的确定

下表为一个具体示例的所有度量和算法的值。如果性能是最重要的考虑因素，Bagging 可以获得最佳的分类性能，PCTBagging 的两个最低合并百分比实现的性能并不明显比 Bagging，牺牲一定的 AUC 可以允许用户保留最多 20% 的合并树的可理解结构。也可以将合并比提高到 40%-50%，这样虽然会牺牲一些分类能力，但会获得相当大的可解释性。如果可解释性是必要的，PCTBagging 是 CTC 的另一种替代方案。在合并百分比为 100% 时，PCTBagging 提供了相同的可理解性，但准确性明显更好。