标签：采样覆盖 decision 样本 three CTD 算法 CCA method

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

论文概况	详细
标题	《A three-way decision ensemble method for imbalanced data oversampling》
作者	Yuan Ting Yan, Zeng Bao Wu, Xiu Quan Du, Jie Chen, Shu Zhao, Yan Ping Zhang
发表期刊	IEEE Transactions on Knowledge and Data Engineering（TKDE）
发表年份	2019
期刊等级	中科院 SCI 期刊分区(2022年12月最新升级版）2 区，CCF-B
论文代码	未公开

研究动机

在许多实际应用中都存在数据不平衡的问题，传统的分类方法倾向于提高所有样本的识别率，而对少数类样本的识别率容易被忽略。目前对不平衡数据分类的研究大致可以分为算法和数据集两个方面，前者倾向于设计更高效的分类算法，后者倾向于如何从原始的不平衡数据集中生成平衡数据集。合成少数派过采样技术(SMOTE)是最具代表性的过采样技术之一，它可以有效地解决随机过采样的过拟合问题。但是 SMOTE 也存在一些缺点：

SMOTE 为每个少数样本生成相同数量的合成样本，忽略了最近邻居的分布；
SMOTE 可能会生成重叠样本和不相交样本，增加了下游分类的难度。

文章贡献

针对 SMOTE 的缺点，本文提出了一种基于建设性覆盖算法(CCA)的三向决策抽样方法(CTD)。CTD 首先使用 CCA 构造不平衡数据的覆盖，然后选择少数样本的覆盖并根据覆盖的密度划分为三个区域。最后根据覆盖分布规律得到相应的阈值 α 和 β，选择关键样本进行SMOTE过采样。考虑到 CCA 随机选择覆盖中心所带来的不确定性，本文进一步提出了一种基于 CTD 的集成模型 CTDE 提高算法的效率。通过在多个不平衡数据集上的实验表明，该方法优于对比方法，通过构建基于关键样本选择的三向决策集成也使模型的性能得到了有效提高。

预备知识

构造覆盖算法

构造覆盖算法(CCA)可以看作是一个 3 层神经网络，核心思想是：找到一条规则覆盖尽可能多的正例，排斥尽可能多的反例。CCA 主要包括 3 个层次：

输入层：共 n 个神经元，每个神经元对应于样本的一个维度，这层的神经元仅起到输入作用；
隐藏层：共 s 个神经元，隐层神经元的数量一开始为 0，随着 CCA 构造的覆盖的增加而单调增加，直到覆盖所有的样本。可以表示为覆盖集 C={C₁¹, …cn_n1¹, c₁², …C_n2², …C₁^m, …C_m^nm}。其中 c_jⁱ 表示第 i 类的第 j 个覆盖，代表隐藏层中的一个神经元;
输出层：共 m 个神经元，第 t 个神经元的输入是一组具有相同类标号的覆盖，第 t 个神经元的输出是对应的类标签 Ot。

CCA 是一种监督学习算法，首先需要将数据归一化到 [0,1]。第二步将样本以n+1的速度将样品投影到球面空间S_n+1中，如下公式所示，其中R≥max{|x|, x∈x}。

第三步将构建隐藏神经元，随机选择 X 中的一个样本 xk 作为覆盖中心作为隐藏层神经元的权值 w 之一。CCA 用内积代替欧氏距离来计算样本间的距离，公式如下所示，则可以得到与 w 对应的 θ(覆盖半径)的计算方法。

接着分别计算出最大内积(最小距离)和最小内积(最大距离):

接着计算覆盖半径，得到一个神经元(w,θ)，其中包含一组与 xk 具有相同标签的样本。该覆盖面内的样本将被标注为“learned”。

然后移除 (w,θ) 中的样本，并重复步骤构造覆盖，直到所有样本都从空间 S_n+1 中移除。如果一个样本被覆盖，则它就不参与下一轮的覆盖构建过程，这样减少了算法的计算时间。

三向决策

在双向决策中只考虑接受或拒绝两种情况，但在实际应用中往往会因为信息的不准确或不完整而无法接受或拒绝。三向决策理论的提出为粗糙集的三个领域提供合理的语义解释，粗糙集模型的正域、负域和边界域可以解释为三种决策的结果：接受、拒绝和未承诺。
在不失一般性的前提下，设 Ω={S,¬S}为状态集，其中 S 与 ¬S 互补。动作集 A=(aP,aB,aN)。aP、aB、aN 分别表示将对象决定为正域 (POS(X))，负域NEG(X)、边界域(BND(X))的动作。不同状态下动作的损失函数矩阵如下表所示，λPP、λBP、λNP 分别表示动作为 aP、aB、aN、状态为 S 时的损失函数值，λPN、λBN、λNN 分别表示动作为 aP、aB、aN 状态为 ¬S 时的损失函数值。

根据损失函数矩阵和推导过程，可以得到 DTRS 决策规则：

本文方法

基于 CCA 的三向决策模型

少数类中的不同样本对过采样性能的影响不同，通常少数类的边界样本比中心样本更关键，然而现有的过采样方法可能过度关注了边界样本。在选择少数样本进行非平衡数据过采样时，样本可分为三类:

少数类中聚集效应明显的样本，对模型性能影响较小；
少数类中的噪声样本或孤立样本，它们远离少数类样本且有聚集效应。选取这些样本不能提高模型性能，还会对模型性能产生负面影响；
不属于上述两类的少数样本，对提高少数类的识别能力起关键作用，其关键在于分类边界的划定。

上述三种少数样本可以和三向决策模型的三个域产生关联，第一类、第二类和第三类分别对应于三方决策的正域(POS)、负域(NEG)和边界域(BND)。

为方便起见，假设不平衡数据集有两类(少数和多数)样本，C0=(c₁⁰, c₂⁰, …c_n0⁰) 和 C1=(c₁₁¹, c₂₁¹, …c_n1¹) 分别代表少数类和多数类的全部覆盖。
设 c_t⁰ 为 C0 的第 t 层，则 C0 的密度可定义为如下公式，其中 R_t⁰ 表示 c_t⁰ 的半径，|c_t⁰| 表示 c_t⁰ 的基数。

则可以进一步得到少数类的正定域(POS)、负域(NEG)定义、边界域(BND)的定义如下:

首先在不平衡数据集上应用 CCA，然后可以根据上述定义得到少数样本的三个域(POS,NEG,BND)。对于 3 个域中的样本，分别做以下处理：

POS 域中的少数样本具有明显的聚集效应，CTD 中不选择这些样本进行过采样；
NEG 域中的少数样品具有较高的离散度，CTD 将它们视为噪声样本，不进行过采样；
BND 域中使用 SMOTE 采样可以提高分类器在数据集上的性能。

CTD 集成

CCA 通过随机选择覆盖中心来构建覆盖，因此不同的 CCA 初始化会导致 BND 区域的样本集不同。例如下图所示的例子，在图(a)中 CCA 选择 A 和 D 作为覆盖中心构建两个覆盖，样本 A、B、C 属于第一个覆盖，样本 D、E、F 属于另一个覆盖，两个覆盖的样本被划分为 BND 区域。但是从图(b)中可以看出，CCA 选择 C、E 作为覆盖中心，然后分别用 A 和 C、D 和 E 构建两个覆盖，然后将这两个覆盖划分为 BND 区域，样品 B 和 F属于 CTD 中划分为 NEG 区域的两个覆盖。

根据这个特点可以得到不同的过采样合成样本，可以增加下游分类器的多样性。本文进一步提出了一种三向决策集成方法(CTDE)来提高 CTD 的性能，也就是在原始不平衡数据集上进行 T 次 CCA(随机选择覆盖中心)得到 TBND 域，然后应用 SMOTE 得到每个 BND 域的平衡数据集。之后分别对 T 个平衡数据集应用基学习算法得到 T 个分类器，最后采用多数投票将 T 分类器集成。

实验结果

数据集

实验部分采用 Precision、Recall、F-measure、G-mean、Accuracy、AUC 作为评价标准。数据集方面使用了 10 个不平衡的数据集，这些不平衡数据集的详细信息如下表所示。

实验设置

CTDE 的性能对参数(α,β)敏感，取值会影响后续的过采样结果，因此对于不同的数据集应该采用不同的设置。将过采样后分类器的 AUC 值作为选择(α,β)的准则，不同数据集上的设置如下表所示。

数据集对应的 POS、BND、NEG 域内样本的平均数量如下所示，这是十次交叉验证的平均结果。

集成时的基分类器训练次数 T 也是重要的参数，本文将训练次数 T 从 2 次以 2 为间隔增加到 50 次，对每个 T 值进行 50 次重复取平均结果。下图是不同的 T 与前五个数据集上的测试误差之间的关系，可以看出 5 个数据集上的误差都随着T单调减小。

根据实验结果，得到每个数据集的最佳 T 值如下表所示。

因为应用了 SMOTE，考虑到数据集不平衡程度的差异，下表给出了 10 个数据集上 SMOTE 的采样率。

与过采样的比较

实验采用 C4.5 决策树作为基分类器，将该算法与 SMOTE、Borderline-SMOTE(BSMO)、MWMOTE(MWMO)、ADASYN(ASYN) 和 SMOTE+Tomeklink(SM-T)等几种过采样方法进行了比较，并给出了 10 次交叉验证 10 次的平均结果。
下表展示了 CTD 与在 POS 域的少数样本上进行 SMOTE 的方法的结果，最后一行给出了每个评估指标在 10 个数据集上的平均结果。可以看出 CTD 在大多数数据集上都有更好的性能，总体而言 CTD 方法的性能优于 POS 过采样方法。

下面多张表给出了 7 种算法在 10 个数据集上的结果，总而言之从平均结果来看，本文的 CTDE 方法比比较算法取得了更好的结果。

下表给出了 CTD 算法与其他算法的性能排名，与其他六种算法相比 CTD 在各个评估指标上的性能都处于前列。实验结果表明，CTD 可以作为非平衡数据过采样的一种可用的方法。

进一步研究 CTD 和 CTDE 在每个数据集上的性能，下图展示了以数据集 B0b 为例的比较结果。与 CTD 相比，CTDE 在所有指标上都有性能改进。

显著性检验

下表给出了 CTD 与其余 6 种算法之间的显著性检验的 p 值，从结果可以看出 CTD 与 6 种比较方法的差异约为 1/3。由于 CCA 的随机性和数据集的数据分布复杂导致检测到难以学习的样本，因此进一步提出 CTDE 方法来解决这一问题。

下表给出了 CTDE 与其余 7 种算法之间的显著性检验的 p 值。总而言之 CTED 在 Recall、G-mean、Accuracy 与其他算法相比有显著差异，和 CTD 之间也存在显著差异。可见 CTDE 可以作为处理不平衡数据过采样的一种替代方法，验证了三向集成模型的有效性。

优点和创新点

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

通过对少数类的不同特点的样本进行分析，将样本分为 3 个域并分析了哪个域做过采样更为重要，并将这个结论与三向决策理论进行结合；
利用了 CCA 算法，通过构造出不同的覆盖来进行 3 个域的划分，与三向决策理论的联系非常紧密；
针对随机初始化带来的随机性，本文进而通过集成的方式加以利用，具有较强的说服力。

标签：采样,覆盖,decision,样本,three,CTD,算法,CCA,method
From： https://www.cnblogs.com/linfangnan/p/17529182.html

Paper Reading: A three-way decision ensemble method for imbalanced data oversampling