泽民博客 ☰ Menu

sampling 采样


研究表明，对于一些基分类器来说，与不均衡的数据集相比一个均衡的数据集可以提高全局的分类性能。数据层面的处理方法是处理不均衡数据分类问题的重要途径之一，它的实现方法主要分为对多数类样本的欠抽样和对少数类样本的过抽样学习两种。其主要思想是通过合理的删减或者增加一些样本来实现数据均衡的目的，进而降低数据不均衡给分类器带来的负面影响。
按照对样本数量的影响又可分为：
过抽样，即合理地增加少数类的样本
欠抽样，即合理地删减多数类样本
随机过抽样和欠抽样
随机过抽样
随机过抽样是一种按照下面的描述从少数类中速记抽样生成子集合 E 的方法。
首先在少数类 Smin 集合中随机选中一些少数类样本
然后通过复制所选样本生成样本集合 E
将它们添加到 Smin 中来扩大原始数据集从而得到新的少数类集合 Smin−new
用这样方法，Smin 中的总样本数增加了 |E| 个新样本，且 Smin−new 的类分布均衡度进行相应的调整，如此操作可以改变类分布平衡度从而达到所需水平。
欠抽样
欠抽样技术是将数据从原始数据集中移除。
首先我们从 Smaj 中随机地选取一些多数类样本 E
将这些样本从 Smaj 中移除，就有 |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)。该算法的整体流程图如下所示：



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



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

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

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

  4. 最远距离
    选择到最近的三个少数类样本平均距离最大的那些多数类样本
    Note：实验结果表明 NearMiss-2 方法的不均衡分类性能最优
    数据生成的合成抽样方法
    在合成抽样技术方面， Chawla NV 等人提出的 SMOTE 过抽样技术是一个强有力的方法。SMOTE 过抽样技术与传统的简单样本复制的过抽样方法不同，它是利用少数类样本控制人工样本的生成与分布，实现数据集均衡的目的，而且该方法可以有效地解决由于决策区间较小导致的分类过拟合问题。
    SMOTE 算法是利用特征空间中现存少数类样本之间的相似性来建立人工数据的。特别是，对于子集 Smin⊂S ，对于每一个样本 xi⊂Smin 使用 K-近邻法，其中 K 是某些制定的整数。
    这里 K-近邻 被定义为考虑 Smin 中的 K 个元素本身与 xi 的欧氏距离在 n 维特征空间 X 中表现为最小幅度值的样本。为了构建一个合成样本
    首先随机选择一个 K-近邻
    然后用在 [0,1] 之间的随机数乘以对应特征向量的差异
    最后再加上 xi
    xnew=xi+(x^i−xi)∗δ
    其中 xi⊂Smin 是当前少数类样本，x^i 是 xi 的一个 K-近邻（随机）：x^i⊂Smin，且 δϵ[0,1] 是一个随机数。因此，根据上式产生的合成样本是与所考虑的点 xi 在同一条线段上，且 xi 是随机选取的。
    以下是 SMOTE 过程的一个例子，K=6
    、、
    可以看出 SMOTE 算法是建立在相距较近的少数类样本之间的样本仍然是少数类的假设基础上的。

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

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

  7. 缺陷
    体现在过分泛化问题和方差
    自适应合成抽样方法
    Borderline-SMOTE 算法介绍
    在 SMOTE 算法中，过度泛化问题主要归结于产生合成样本的方法。特别是，SMOTE 算法对于每个原少数类样本产生相同数量的合成数据样本，而没有考虑其邻近样本的分布特点，这就使得类间发生重复的可能性加大。
    从前面介绍的 SMOTE 算法原理，结合下图发现，SMOTE 算法产生新的人工少数类样本过程时，只是简单地在同类近邻之间插值，并没有考虑到少数类样本周围多数类样本的分布情况。如下图



上图中，圆点 6 和 7 分布在多数类样本周围，它们和其他样本生成的人工少数类样本 1 和 2 离多数类样本最近，这就导致它们有可能被划分成多数类样本。因而从图中可以看出，SMOTE 算法的样本生成机制存在着一定盲目性
为了克服这个限制，多种不同的自适应抽样方法相继被提出，其中具有代表性的算法包括 Borderline-SMOTE 算法 和 自适应合成抽样算法 (ADASYN)。
Borderline-SMOTE 算法步骤
对于这些自适应算法，我们最感兴趣的就是用于识别少数类种子样本的方法。在 Borderline-SMOTE 算法 中，识别少数类种子样本的过程如下：
首先，对于每个 xi⊂Smin 确定一系列最近邻样本集，称该数据集为 Si:m−NN，且 Si:m−NN⊂S
然后，对每个样本 xi ，判断出最近邻样本集中属于多数类样本的个数，即：|Si:m−NN⋂Smaj|
最后，选择满足下面不等式的 xi：m2<|Si:m−NN⋂Smaj|<m
上式表明，只有最近邻样本集中多数类对于少数类的那些 xi 才会被选中形成 “危险集 (DANGER)”。因此，DANGER 集中的样本代表少数类样本的边界（最容易被错分的样本）。然后对 DANGER 集使用 SMOTE 算法来在边界附近产生人工合成少数类样本
我们注意到，如果 |Si:m−NN⋂Smaj|=m，即： xi 的所有 m 个最近邻样本都属于多类，像下图所示的样本 C



那么，我们就认为样本 xi 是噪声且它不能生成合成样本。上图也给出了一个样本的 Borderline-SMOTE 算法的过程。
比较图 3.3 和 3.4 ，我们发现 SMOTE 和 Borderline-SMOTE 算法最大的不同就是：SMOTE 算法为每一个少数类样本生成合成样本，然而 Borderline-SMOTE 算法只为那些 “靠近” 边界的少数类样本生成合成样本
Borderline-SMOTE 流程图
如图，Borderline-SMOTE 算法具体描述如下：文中训练样本集为 T，少数类样本 F={f1,f2,…,fn}



（1） 步骤一



  1. 计算少数类样本集 F 中每一个样本在训练样本集 T 中的 k 个最近邻

  2. 然后根据这 k 个最近邻对 F 中的样本进行归类：
    假设这 k 个最近邻都是多数类样本，则我们将该样本定义为噪声样本，将它放在 N′ 集合中
    反之 k 个最近邻都是少数类样本则该样本是远离分类边界，将其放入 S 集合中
    最后 k 个最近邻既有多数类样本又有少数类样本，则认为是边界样本，放入 B 集合中
    （2）步骤二

  3. 设边界样本集 B={f1′,f2′,…,fb′}，计算 B 集合中的每一个样本 fi′,i=1,2,…,b 在少数类样本 F 中的 k′ 个最近邻 fij

  4. 随机选出 s(1<s<b) 个最近邻

  5. 计算出它们各自与该样本之间的全部属性的差值 dij：dij=fi′−fij，j=1,2,…,s

  6. 然后乘以一个随机数 rij，rij∈(0,1)（如果 fij 是 N′ 集合或 S集合中的样本，则 rij∈(0,0.5)

  7. 最后生成的人工少数类样本为：hij=fi′+rij∗dij,j=1,2,…,s
    （3）步骤三
    重复步骤 2 过程，直到生成人工少数类样本的数目满足要求，达到均衡样本集的目的后，则算法结束
    利用数据清洗技术的抽样
    数据清洗技术，例如：Tomek ，现已广泛应用于去除由于抽样技术引起的重复项。
    定义：Tomek 线被定义为相反类最近邻样本之间的一对连接
    符号约定：给定一个样本对：(xi,xj)，其中 xi∈Smin ，且 xj∈Smaj，记 d(xi,xj) 是样本 xi 和 xj 之间的距离
    公式表示：如果不存在任何样本 xk，使得 d(xi,xk)<d(xi,xj) 或 d(xj,xk)<d(xi,xj)，那么样本对 (xi,xj) 被称为 Tomek 线
    使用这种方法，如果两个样本来自 Tomek 线，那么他们中的一个样本要么是噪声要么它们都邻近边界。因此，在合成抽样之后，有人用 Tomek 线来清除类间不想要的重复样本，Tomek 线都被清除了，直到最近邻样本之间的样本对都来之同一类为止。
    移除重复的样本，可以在训练集中建立良号定义的类簇，这反过来又可以为提高分类性能定义良好的分类准则。在这个领域中，典型的方法包括 OSS 方法、简明近邻规则、Tomek线（CNN+Tomek）集成方法、基于编辑近邻（ENN）的近邻 清理规则（NCL）、SMOTE 和ENN 的集成（SMOTE+ENN）以及 SMOTE 与 Tomek 线的集成（SMOTE+Tomek）。


Category algorithm