不均衡学习的抽样方法【原理介绍详细】

心已赠人 2022-05-14 08:48 1094阅读 0赞

通常情况下，在不均衡学习应用中使用抽样方法的**目的**就是为了**通过一些机制改善不均衡数据集，以期获得一个均衡的数据分布**。

研究表明，对于一些基分类器来说，与不均衡的数据集相比一个均衡的数据集可以提高全局的分类性能。数据层面的处理方法是处理不均衡数据分类问题的重要途径之一，它的实现方法主要分为**对多数类样本的欠抽样**和**对少数类样本的过抽样学习**两种。其主要思想是通过合理的删减或者增加一些样本来实现数据均衡的目的，进而降低数据不均衡给分类器带来的负面影响。

按照对样本数量的影响又可分为：

*  **过抽样**，即合理地增加少数类的样本
 *  **欠抽样**，即合理地删减多数类样本

--------------------

# 随机过抽样和欠抽样 #

## 随机过抽样 ##

随机过抽样是一种按照下面的描述从少数类中速记抽样生成子集合 E 的方法。

1.  首先在少数类 SminSmin 集合中**随机**选中一些少数类样本
2.  然后通过**复制**所选样本生成样本集合 E
3.  将它们**添加**到 SminSmin 中来扩大原始数据集从而得到新的少数类集合 Smin−newSmin−new

用这样方法，SminSmin 中的总样本数增加了 |E||E| 个新样本，且 Smin−newSmin−new 的类分布均衡度进行相应的调整，如此操作可以改变类分布平衡度从而达到所需水平。

--------------------

## 欠抽样 ##

欠抽样技术是将数据从原始数据集中移除。

1.  首先我们从 SmajSmaj 中随机地选取一些多数类样本 E
2.  将这些样本从 SmajSmaj 中移除，就有 |Smaj−new|=|Smaj|−|E||Smaj−new|=|Smaj|−|E|

--------------------

## 缺陷 ##

初看，过抽样和欠抽样技术在功能上似乎是等价的，因为它们都能改变原始数据集的样本容量且能够获得一个相同比例的平衡。

但是，这个共同点只是表面现象，这是因为这两种方法**都将会产生不同的降低分类器学习能力的负面效果**。

*  对于欠抽样算法，将多数类样本删除有可能会导致分类器**丢失有关多数类的重要信息**。
 *  对于过抽样算法，虽然只是简单地将复制后的数据添加到原始数据集中，且某些样本的多个实例都是“**并列的**”，但这样也可能会导致分类器学习出现**过拟合现象**，对于同一个样本的多个复本产生多个规则条例，这就使得**规则过于具体化**；虽然在这种情况下，分类器的训练精度会很高，但在位置样本的分类性能就会非常不理想。

--------------------

# informed 欠抽样 #

两个 informed 欠抽样算法：**EasyEnsemble** 和 **BalanceCascade** 算法，这两种方法克服了传统随机欠抽样方法导致的信息缺失的问题，且表现出较好的不均衡数据分类性能。

--------------------

## EasyEnsemble 和 BalanceCascade 算法介绍【接下来详细研究这俩方法】 ##

**1. EasyEnsemble 核心思想是：**

*  首先通过从多数类中**独立随机**抽取出若干子集
 *  将每个子集与少数类数据**联合**起来**训练**生成多个基分类器
 *  最终将这些基分类器**组合形成**一个集成学习系统

EasyEnsemble 算法被认为是**非监督学习算法**，因此它每次都独立利用可放回随机抽样机制来提取多数类样本

**2. BalanceCascade 核心思想是：**

*  使用之前已形成的集成分类器来为下一次训练选择多类样本
 *  然后再进行欠抽样

--------------------

## 最近邻规则（ENN） ##

因为随机欠抽样方法未考虑样本的分布情况，采样具有很大的随机性，可能会删除重要的多数类样本信息。针对以上的不足，Wilson 等人提出了一种**最近邻规则**(edited nearest neighbor: ENN)。

*  **基本思想**：**删除那些类别与其最近的三个近邻样本中的两个或两个以上的样本类别不同的样本**
 *  **缺点**：因为大多数的多数类样本的样本附近都是多数类，所以该方法所能**删除**的多数类样本十分**有限**。

--------------------

## 领域清理规则 (NCL) ##

Laur Ikkala J 等人在 ENN 的基础行提出了 **领域清理规则 (neighborhod cleaning rule: NCL)**。该算法的整体流程图如下所示：

![这里写图片描述][20160215005719410]

*  **主要思想**：针对训练样本集中的每个样本找出其三个最近邻样本，若该样本是多数类样本且其三个最近邻中有两个以上是少数类样本，则删除它；反之当该样本是少数类并且其三个最近邻中有两个以上是多数类样本，则去除近邻中的多数类样本。
 *  **缺陷**：未能考虑到在少数类样本中存在的噪声样本而且第二种方法删除的多数类样本大多属于边界样本，删除这些样本，对后续分类器的分类产生很大的不良影响。

--------------------

## K-近邻（KNN） ##

基于给定数据的分布特征，有四种 KNN 欠抽样方法：

**1. NearMiss-1**  
选择到最近的三个少数类样本平均距离最小的那些多数类样本

**2. NearMiss-2**  
选择到最远的三个少数类样本平均距离最小的那些多数类样本

**3. NearMiss-3**  
为每个少数类样本选择给定数目的最近多数类样本，目的是保证每个少数类样本都被一些多数类样本包围

**4. 最远距离**  
选择到最近的三个少数类样本平均距离最大的那些多数类样本

**Note**：实验结果表明 **NearMiss-2** 方法的不均衡分类性能最优

--------------------

# 数据生成的合成抽样方法 #

在合成抽样技术方面， Chawla NV 等人提出的 SMOTE 过抽样技术是一个强有力的方法。SMOTE 过抽样技术与传统的简单样本复制的过抽样方法不同，它是**利用少数类样本控制人工样本的生成与分布，实现数据集均衡的目的，而且该方法可以有效地解决由于决策区间较小导致的分类过拟合问题。**

SMOTE 算法是利用特征空间中现存少数类样本之间的相似性来建立人工数据的。特别是，对于子集 Smin⊂SSmin⊂S ，对于每一个样本 xi⊂Sminxi⊂Smin 使用 K-近邻法，其中 K 是某些制定的整数。

这里 K-近邻 被定义为考虑 SminSmin 中的 K 个元素本身与 xixi 的**欧氏距离**在 n 维特征空间 X 中表现为最小幅度值的样本。为了构建一个合成样本

1.  首先**随机选择**一个 K-近邻
2.  然后用在 \[0,1\] 之间的**随机数乘**以对应特征向量的差异
3.  最后再**加上** xixi

xnew=xi+(x̂ i−xi)∗δxnew=xi+(x^i−xi)∗δ

其中 xi⊂Sminxi⊂Smin 是当前少数类样本，x̂ ix^i 是 xixi 的一个 K-近邻（随机）：x̂ i⊂Sminx^i⊂Smin，且 δϵ\[0,1\]δϵ\[0,1\] 是一个随机数。因此，根据上式产生的合成样本是与所考虑的点 xixi 在同一条线段上，且 xixi 是随机选取的。

以下是 SMOTE 过程的一个例子，K=6

![这里写图片描述][20160215014428220]、、

可以看出 **SMOTE 算法是建立在相距较近的少数类样本之间的样本仍然是少数类的假设基础上的**。

**1. 总结**

*  对于少数类的每个样本寻找其同类样本中 k 个最近邻。其中，**k 通常是大于 1 的奇数**
 *  重复上述插值过程，使得新生成的训练数据集数据达到均衡，最后利用新的训练样本集进行训练

**2. 优点**

*  有助于简单打破过抽样所产生的关系
 *  使得分类器的学习能力得到显著提高

**3. 缺陷**

*  体现在**过分泛化**问题和**方差**

--------------------

# 自适应合成抽样方法 #

## Borderline-SMOTE 算法介绍 ##

在 SMOTE 算法中，**过度泛化问题主要归结于产生合成样本的方法**。特别是，**SMOTE 算法对于每个原少数类样本产生相同数量的合成数据样本，而没有考虑其邻近样本的分布特点，这就使得类间发生重复的可能性加大。**

从前面介绍的 SMOTE 算法原理，结合下图发现，SMOTE 算法产生新的人工少数类样本过程时，只是简单地在同类近邻之间插值，并没有考虑到少数类样本周围多数类样本的分布情况。如下图

![这里写图片描述][20160215102047091]

上图中，圆点 6 和 7 分布在多数类样本周围，它们和其他样本生成的人工少数类样本 1 和 2 离多数类样本最近，这就导致它们有可能被划分成多数类样本。因而从图中可以看出，SMOTE 算法的样本生成机制存在着一定**盲目性**

为了克服这个限制，多种不同的自适应抽样方法相继被提出，其中具有代表性的算法包括 **Borderline-SMOTE 算法** 和 **自适应合成抽样算法 (ADASYN)**。

--------------------

## Borderline-SMOTE 算法步骤 ##

对于这些自适应算法，我们最感兴趣的就是用于识别少数类种子样本的方法。在 Borderline-SMOTE 算法 中，识别少数类种子样本的过程如下：

1.  首先，对于每个 xi⊂Sminxi⊂Smin 确定一系列最近邻样本集，称该数据集为 Si:m−NNSi:m−NN，且 Si:m−NN⊂SSi:m−NN⊂S
2.  然后，对每个样本 xixi ，判断出最近邻样本集中属于多数类样本的个数，即：|Si:m−NN⋂Smaj||Si:m−NN⋂Smaj|
3.  最后，选择满足下面不等式的 xixi：m2<|Si:m−NN⋂Smaj|<mm2<|Si:m−NN⋂Smaj|<m

上式表明，只有最近邻样本集中多数类对于少数类的那些 xixi 才会被选中形成 **“危险集 (DANGER)”**。因此，DANGER 集中的样本代表少数类样本的边界（**最容易被错分的样本**）。**然后对 DANGER 集使用 SMOTE 算法来在边界附近产生人工合成少数类样本**

我们注意到，如果 |Si:m−NN⋂Smaj|=m|Si:m−NN⋂Smaj|=m，即： xixi 的所有 m 个最近邻样本都属于多类，像下图所示的样本 C

![这里写图片描述][20160215105722666]

那么，我们就认为样本 xixi 是**噪声且它不能生成合成样本**。上图也给出了一个样本的 Borderline-SMOTE 算法的过程。

比较图 3.3 和 3.4 ，我们发现 SMOTE 和 Borderline-SMOTE 算法最大的不同就是：**SMOTE 算法为每一个少数类样本生成合成样本，然而 Borderline-SMOTE 算法只为那些 “靠近” 边界的少数类样本生成合成样本**

--------------------

## Borderline-SMOTE 流程图 ##

如图，Borderline-SMOTE 算法具体描述如下：文中训练样本集为 T，少数类样本 F=\{f1,f2,...,fn\}F=\{f1,f2,...,fn\}

![这里写图片描述][20160215110714124]

--------------------

**（1） 步骤一**  
1. 计算少数类样本集 F 中每一个样本在训练样本集 T 中的 k 个最近邻  
2. 然后根据这 k 个最近邻对 F 中的样本进行归类：

*  假设这 k 个最近邻都是多数类样本，则我们将该样本定义为**噪声样本**，将它放在 N′N′ 集合中
 *  反之 k 个最近邻都是少数类样本则该**样本是远离分类边界**，将其放入 **S 集合**中
 *  最后 k 个最近邻既有多数类样本又有少数类样本，则认为是**边界样本**，放入 **B 集合**中

--------------------

**（2）步骤二**  
1. 设边界样本集 B=\{f1′,f2′,...,fb′\}B=\{f1′,f2′,...,fb′\}，计算 B 集合中的每一个样本 fi′,i=1,2,...,bfi′,i=1,2,...,b 在少数类样本 F 中的 **k′k′ 个最近邻** fijfij  
2. 随机选出 s(1<s<b)s(1<s<b) 个最近邻  
3. 计算出它们各自与该样本之间的全部属性的差值 dij：dij=fi′−fij，j=1,2,...,sdij：dij=fi′−fij，j=1,2,...,s  
4. 然后乘以一个随机数 rij，rij∈(0,1)rij，rij∈(0,1)（如果 fijfij 是 N′N′ 集合或 S集合中的样本，则 rij∈(0,0.5)rij∈(0,0.5)  
5. 最后生成的人工少数类样本为：hij=fi′+rij∗dij,j=1,2,...,shij=fi′+rij∗dij,j=1,2,...,s

--------------------

**（3）步骤三**  
重复步骤 2 过程，直到生成人工少数类样本的数目满足要求，达到均衡样本集的目的后，则算法结束

--------------------

# 利用数据清洗技术的抽样 #

数据清洗技术，例如：Tomek ，现已广泛应用于去除由于抽样技术引起的重复项。

*  **定义**：Tomek 线被定义为**相反类最近邻样本之间的一对连接**
 *  **符号约定**：给定一个样本对：(xi,xj)(xi,xj)，其中 xi∈Sminxi∈Smin ，且 xj∈Smajxj∈Smaj，记 d(xi,xj)d(xi,xj) 是样本 xixi 和 xjxj 之间的距离
 *  **公式表示**：如果不存在任何样本 xkxk，使得 d(xi,xk)<d(xi,xj)d(xi,xk)<d(xi,xj) 或 d(xj,xk)<d(xi,xj)d(xj,xk)<d(xi,xj)，那么样本对 (xi,xj)(xi,xj)被称为 Tomek 线

使用这种方法，如果两个样本来自 Tomek 线，那么他们中的一个样本要么是**噪声**要么它们都**邻近边界**。因此，在合成抽样之后，有人用 Tomek 线来清除类间不想要的重复样本，Tomek 线都被清除了，直到最近邻样本之间的样本对都来之同一类为止。

移除重复的样本，可以在训练集中建立良号定义的类簇，这反过来又可以为提高分类性能定义良好的分类准则。在这个领域中，典型的方法包括 **OSS 方法**、**简明近邻规则**、**Tomek线（CNN+Tomek）集成方法**、**基于编辑近邻（ENN）的近邻 清理规则（NCL）**、**SMOTE 和ENN 的集成（SMOTE+ENN）**以及 **SMOTE 与 Tomek 线的集成（SMOTE+Tomek）**。

![这里写图片描述][20160215141926271]![这里写图片描述][20160215142047116]

(a) 原数据集分布　　　　　　　　　　　　　　　　 (c) 被识别出的 Tomek 线  
(b) Post-SMOTE 数据集　　　　　　　　　　　　　(d) 移除 Tomek 线后的数据集

上图给出了将 SMOTE 和 Tomek 结合起来来清理重复数据点的典型过程。

*  图(a) 给出了一个人工不均衡数据集的原始集分布。注意存在于少数类和多类之间的原有重复点。
 *  图(b) 给出了使用 SMOTE 算法生成合成样本之后的数据集分布。可以看出，使用 SMOTE 算法是重复点增多
 *  图(c) 确定了 Tomek 线，用框表示
 *  图(d) 给出清理后的数据集

我们看出算法过程更好地定义了类簇，这有助于提高分类性能。

--------------------

## 实验分析 ##

为了说明不均衡数据集下对分类器算法性能的影响，我们利用 UCI 数据集中的 german、haberman 进行分析，其中取 german 数据集中类 1 作为多数类，类 2 位少数类。**SVM 算法**中 **C=1000**、**核函数为高斯核**、**参数为 10**、不均衡数据比取**10:1**，**15:1**，**20:1**，**25:1**，**30:1**，**35:1**，**40:1**，**45:1**

为了消除噪声的影响，我们采用 **10 次**交叉验证方法，每次验证循环 **20 次**，取其平均结果，试验中采用 **RU 随机欠抽样**，**SMOTE 过抽样**，**RU+SMOTE 算法**以及 **BSMOTE** 、**ADASYN 过抽样算法**进行分析比较。性能指标选择 **F-Measure** ， **G-Mean** 和 **AUC** 。

从实验结果不难看出，当 SVM 算法面对这些不均衡数据集分类时，出现严重便宜使得少数类的性能为最低 (0)，因此导致 F-Measure ， G-Mean 和 AUC 的性能指标为 0。而其他基于数据预处理的不均衡数据分类方法均能有效提高算法性能。最后，我们对这几个算法按照不均衡数据比例取其平均值，并将其结果进行对比。

最终总结出的结论是：针对不同的数据集分布特征，不同数据预处理方法的性能也大不相同，因此如何**根据具体的数据分布选择合适的数据预处理方法是解决不均衡数据分类问题的关键**。从结果中，我们还可以进一步看出，将**两种算法进行有效地结合**不失为一种解决该问题的好思路。

[20160215005719410]: /images/20220514/04ea859cd6cb407488ac28b2ecbb6043.png
[20160215014428220]: /images/20220514/1dc7a3392a5241b288765829780243c7.png
[20160215102047091]: /images/20220514/861a4ee5c4e54fcb9349218f12a6020a.png
[20160215105722666]: /images/20220514/d37556860ea24df290dc8adfaf21878f.png
[20160215110714124]: /images/20220514/fe694a004b1a498ba62d8b7a6a3f8a2d.png
[20160215141926271]: https://img-blog.csdn.net/20160215141926271
[20160215142047116]: /images/20220514/473e3b846f8944c59d937b129d68a9d8.png