作者单位：

1. Tecnologico de Monterrey, School of Engineering and Science, Atizapán de Zaragoza, Estado de México 52926, Mexico
2. Altair Management Consultants, Calle de José Ortega y Gasset 22-24, 5th floor, 28006 Madrid, Spain

研究动机

决策树(DT)是一种高可解释性、分类性能好、计算速度快的分类器，最常用的 DT 类型是单变量决策树(UDT)。提高 UDT 分类性能的一种方法是允许 DT 在分割节点的条件下使用多个特征，这种方法有三种类型的树：多元决策树(MDTs)、模型树(MTs)、功能树(FTs)，但许多算法在处理多类和类不平衡问题时存在缺点。

文章贡献

本文提出了一种类不平衡问题的功能树(FT4cip)，该模型使用了考虑类不平衡的分割评估函数 Twoing，以及使用了一种优化 AUC 的新型剪枝算法。同时对多变量分割使用特征选择，进一步提高分类性能和可解释性。通过大量的实验分析证明，FT4cip 在 AUC 上的分类性能优于 LMT 和 Gama。接着对几种算法进行元分析，显示了 FT4cip 比 LMT 和 Gama 具有更好性能的问题类型。最后根据对分类性能的影响对算法的不同进行排序，证明所采取的设计决策是合理的。

预备知识

UDT 每次使用一个特征来递归地划分对象，从而在特征空间中产生与轴平行的超平面。但是当来自不同类的对象可能被单个非轴平行分割时，UDT 会进行次优分割。下图显示了 MDT(MHLDT)、MT(LMT)和 FT(Gama) 用于分类 iris 的示例。MDT 允许在非叶节点中合并多个特性进行划分，MT 通过在每个叶子中使用分类器(例如逻辑回归)来决定落在叶结点中样本的类别，从而实现叶子节点中的特征组合。FT 是 MDT 和 MT 的综合版本，它允许在非叶节点和叶节点中进行特征组合。

本文方法

算法流程和符号定义

本文提出的 FT4cip 模型的流程如下伪代码所示：

结点分裂

结点分裂的方法使用了多类别 Fisher 线性判别(MFLD)和顺序前向选择(SFS)，先使用 SFS 选择特征子集，然后使用 MFLD 生成线性候选分裂。
和其他算法的区别在于，LMT 只使用单变量分裂，Gama 使用多变量分裂，本文的 FT4cip 使用单变量拆分或具有少量特征的多变量拆分。

分裂评估函数

分裂的评估函数用于在 Nt 对分割 S 进行评估，本文选择能考虑类别的不平衡的 Twoing 函数。Twoing 函数的定义如下:

函数的中符号及其含义如下表所示：

最大化 Twoing 函数在本质上就是对 |pc,L−pc,R| 进行最大化，可以使分配给每个子节点的样本数量相似。对于每个类，无论每个类有多少个样本，|pc,L−pc,R| 的取值范围都是相同的 [0,1]，这使得 Twoing 对类不平衡具有鲁棒性。
和其他算法的区别在于，LMT 和 Gama 使用信息增益作为一个分裂的评估函数。

终止条件

由于终止条件对分类性能没有显著影响，因此使用较为简单的策略，即只有当节点是纯节点时停止分裂。和其他算法的区别在于，LMT 和 Gama 的终止条件设置的很复杂。

叶结点分类器

叶结点使用逻辑回归给样本分配标签，使用 LogitBoost 算法为根节点构建逻辑回归模型，子节点仅使用节点中的样本运行 LogitBoost 的增量迭代来完善父节点的逻辑模型。叶结点分类器和 LMT 的设置一样。

剪枝

使用优化 AUC 的 CostComplexity 对模型进行剪枝，成本复杂性需要优化一个描述树的大小和错误分类率 α 之间权衡的参数。本文的实现方法是在训练集中使用五折交叉验证，通过最小化平均错分率来选择 α 值。

标称特性

对于标称特征生成分裂的问题，本文使用值和补码进行二进制拆分，与所选特征的值匹配的对象都将进入左节点，反之进入右节点。和其他算法的区别在于 LMT 使用多路分割，这样可能会生成多个子节点。

实验结果

数据集和实验设置

使用 110 个 UCI 数据集进行实验，数据集的详细信息如下表所示。

使用五折交叉验证作为验证方式，评价指标使用 AUC，使用贝叶斯有符号秩检验作为统计检验的方法。将数据集划分为五折时使用了分布最优平衡 SCV(DOB-SCV)，该方法能在每折保持尽可能相似的数据分布。
对比算法是 LMT 和多种 MDT，进行元分析时根据类数量、特征数量、样本数量和不平衡度将数据集分为两组。根据下面的直方图展示的统计结果，使用 1000 个实例的值，20 个特征，类不平衡程度 2 作为数据集分组的分界点。

LMT 和 MDTs 的比较

首先将最新的模型树 LMT 与多种 MDT 算法在 57 个数据集上进行比较，其中作者使用的 MDT 算法中只有 15 个算法可以处理所有数据集。贝叶斯符号秩检验结果如下表所示，因为 LMT 优于任何 MDT 的概率大于 0.81，并且任何 MDT 优于 LMT 的概率小于 0.05，所以得出 LMT 优于被比较的所有 MDT 算法的结论。

FT4cip 和 LMT、Gama 的比较

由于 LMT 优于所有 MDTs，因此只需要将 FT4cip 与 LMT、Gama 比较即可。下图展示了 110 个数据库中 FT4cip、Gama、LMT 的 AUC 分布，可见
FT4cip 在中位 AUC 具有最好的分类性能。

下图展示了 FT4cip 与 LMT 的贝叶斯有符号秩检验比较结果，可以以 0.977 的概率得出结论 FT4cip实际上比LMT更好，LMT 优于 FT4cip 的概率小于0.001。

下图展示了 FT4cip 与 Gama 的贝叶斯有符号秩检验比较结果，FT4cip 在 27.7% 的情况喜爱优于 Gama，在其余 72.3% 的情况与 Gama 相当。

分类性能元分析

下图展示了分类器在二分类、多分类数据集的性能，可见 Gama 或 LMT 优于 FT4cip 的概率小于 0.001，FT4cip 优于其他方法的最低概率为 0.192，FT4cip 在二分类和多分类数据集上都优于 LMT 和 Gama。

下图展示了分类器在少于 20 个、多于 20 个特征的数据集中的性能，Gama 或 LMT 优于 FT4cip 的概率都小于 0.001。FT4cip 在多于 20 个特征时优于 LMT 和 Gama，在少于 20 个特征时 FT4cip 相当于 Gama 且优于 LMT。

下图展示了分类器在少于 1000 个、多于 1000 个样本的数据集中的性能，Gama 或 LMT 优于 FT4cip 的概率都小于 0.001。FT4cip 在多于 1000 个样本时优于 LMT 和 Gama，少于 1000 个样本时 FT4cip 与 Gama 相当且优于 LMT。

下图展示了分类器在不同不平衡比的数据集中的性能，Gama 或 LMT 优于 FT4cip 的概率都小于 0.001。当存在低类不平衡时 FT4cip 等效于 LMT 和 Gama，当存在高类不均衡时 FT4cip 优于 LMT 和 Gama。

下表展示了元分析的汇总结果，可见 FT4cip 优于或等效于 LMT 和 Gama。

消融实验

删除 FT4cip 中的各个组件得到 FT4cip 的变体，然后对修改版本进行排名，通过它们在排名中的下降程度来评估每个组件的重要性。下图为这些变体的排名，和 baseline 上优于它们的概率。根据结果可知从最重要到最不重要的依次为：使用适当的修剪方法、使用逻辑回归模型、使用线性多元分裂、使用适当的分裂评估度量、使用简单的停止条件、对标称特征使用二元分裂。

训练时间

下面两张图分别展示了 FT4cip、LMT、Gama 的训练、测试时间分布，Gama 的训练时间最短，FT4cip 最耗时。FT4cip 的运行时间与使用更复杂的停止条件、使用多路分割和使用精度优化成本-复杂性修剪的变体之间几乎没有区别，剪枝是最耗时的步骤。

优点和创新点

个人认为，本文有如下一些优点和创新点可供参考学习：

1. 和传统的单变量模型不同，本文研究的 DT 使用多变量和分类器作为树的节点，具有更强的拟合能力；
2. FT4cip 对决策树在多个方面都进行了优化，可以为后续对决策树本身的优化提供一些方向和思路；
3. 实验数据丰富有力，在 110 个数据集上进行了实验，并从多个不同的方面对模型的性能进行分析。

本栏目推荐文章
• AtCoder Beginner Contest 335 G Discrete Logarithm Problems
• CF1006E Military Problem 题解
• P4137 Rmq Problem / mex
• gurobipy: Gurobi Optimizer is a mathematical optimization software library for solving mixed-integer linear and quadratic optimization problems
• koa2 使用koa-body引入报错 koaBody is not a function
• http://www.nfls.com.cn:20035/contest/1878/problem/5
• 关于函数式接口中常用的Supplier、Consumer、predicate、Function的总结以及其使用场景
• JavaScirpt | String Function (三)
• CF1917D Yet Another Inversions Problem 题解
• The Biggest Water Problem

classification functional imbalance problems Readingclassification functional imbalance problems classification classifiers hundreds problems classification multiclass function optional ioexception problem reading java imbalance class-imbalance imbalance value 915f tree 题解imbalance binary 1902 class-imbalance undersampling exploratory imbalance classification