3.3 人工采样技术

针对随机采样技术的缺点，人们陆续开发出了一些更为高级的采样算法，这类算法均或多或少地利用了样本的局部先验分布信息，并利用这些信息，通过人工干预的方式来移除少数类样本或添加人工合成的多数类样本，从而达到了提升分类性能的目的。在此，我们将此类算法统称为“人工采样技术”。下面将对此类技术中最具代表性的五种算法做展开介绍。

3.3.1 SMOTE采样法

SMOTE（synthetic minority oversampling technique）算法于2002年为Chawla等人所提出，主要用于解决ROS采样法易于陷入过适应的问题[5]。不同于ROS算法，SMOTE算法不再简单地复制少数类样本，而是通过一定策略生成大量新样本的方式来谋求训练样本集类分布的平衡。当然，为了保证样本原始分布不被严重破坏，必须确定某种规则来保证新生成样本的合理性。一般而言，抛除噪声的因素不谈，我们所常见的样本集在属性空间中往往都存在以下特性：某类样本往往趋于出现在同类样本附近，即同类样本的邻域区间当中。SMOTE算法即以上述经验为准则，在原有少数类样本的邻域空间中填充新样本。在SMOTE算法中，邻域空间的确定采用了最为简单的K近邻法，即首先在少数类样本中随机选择一个主样本x，然后在剩余全部少数类样本中找到它的K近邻样本，从中随机选取一个主近邻样本x′，进而在主样本x与其主近邻样本x′的连接线的某个随机位置上生成新样本。新样本的生成过程如图3-3所示。

从图3-3中不难看出，采用SMOTE算法所新生成的样本往往都出现在少数类的决策空间内，从而足以保证其合理性。此外，新生成的样本与原始样本不再是简单的覆盖关系，这就可以保证经SMOTE算法处理后的训练集可近似逼近原始少数类样本训练集的分布，从而在一定程度上避免后期所训练的分类器出现过适应的现象。SMOTE算法的基本流程如下。

算法3-3:SMOTE算法

输入：训练集S={（xi, yi）, i=1,2, …, N, yi∈{+, -}}；多数类样本数N-，少数类样本数N+，其中，N-+N+=N；不平衡比率IR=N-/N+；采样率SR；近邻参数K。

输出：过采样后的训练集S′={（xi, yi）, i=1,2, …, N+N+× SR, yi∈{+, -}}。

算法步骤：

1．从训练集S中取出全部多数类与少数类样本，组成多数类训练样本集S-及少数类训练样本集S+；

2．置新生成样本集SNew为空；

3.For i=1:N+×SR

3.1在1～N+之间随机选择一个数字，于S+中找到对应的主样本x；

3.2在S+中找到主样本x的K 近邻样本，并将其置于近邻样本集SNer中；

3.3在1～K之间随机选择一个数字，并在SNer中找到对应的主近邻样本x′；

3.4通过下式计算得到新少数类样本xnew:xnew=x+rand×（x′-x），其中，rand∈[0,1]；

3.5添加xnew至SNew, SNew=SNew∪xnew；

3.6置近邻样本集SNer为空；

End

4．得到过采样后的训练集S′=S∪SNew。

特别需要说明的是，近邻参数K在SMOTE算法中是最为重要的一个参数，其设置得合理与否将直接影响到最终的分类性能，通常情况下，K取值为5。此外，尽管SMOTE算法有诸多优点，但也存在三个不可回避的缺点：①由于涉及大量的近邻关系运算，其时间复杂度过高；②当少数类样本中含有较多噪声信息时，SMOTE算法会受其干扰，将噪声信息进一步传播，从而影响到分类的性能（见图3-4）; ③由于每轮主样本的选取是完全随机的，故当少数类样本数较少时，可能会造成各原始少数类样本被选作主样本的频次差较大，从而偏离原始的样本分布。

3.3.2 Borderline-SMOTE采样法

Han等人[6]注意到对分类面起决定作用的往往是那些处于分类边界上的样本，即处于类重叠区域或在这一区域附近的样本，因此，他们认为在全部少数类样本上运行SMOTE算法是没有必要的，只需要在边界区域生成新的少数类样本即可。他们所提出的改进算法为Borderline-SMOTE算法，即边界线SMOTE算法。

在Borderline-SMOTE算法中，少数类样本被归为以下互不相交的三类：①安全样本，即远离边界区域，且处于少数类决策区域的样本；②边界样本，即处于决策边界附近的样本；③噪声样本，即远离边界区域，且处于多数类决策区域的样本。Borderline-SMOTE算法给出了这三类样本的确定条件：首先，在整个训练集S上确定每个少数类样本（i=1,2, …, N+）的K近邻，其中，多数类近邻数记为Nmaj，若有：①Nmaj＜K/2，则表明该样本的少数类近邻多于多数类近邻，该样本为处于少数类决策区域的安全样本，可以移除；②K＞Nmaj≥K/2，则表明该样本的少数类近邻少于多数类近邻，该样本很可能处于决策边界附近，将其保留到一个命名为DANGER的样本集中；③Nmaj=K，则表明该样本的全部近邻样本均来自于多数类，极有可能处于多数类决策区域，应将其视为噪声样本，需移除。图3-5给出了上述三类样本的判别示例。

在经过上述判别操作后，仅对DANGER集中保留的少数类样本进行SMOTE操作即可，所生成的新样本均处于决策边界附近。特别地，Borderline-SMOTE算法有两个不同的版本，可分别将其命名为BSO1算法及BSO2算法，它们的具体流程分别描述如下。

算法3-4:BSO1算法

输入：训练集S={（xi, yi）, i=1,2, …, N, yi∈{+, -}}；多数类样本数N-，少数类样本数N+，其中，N-+N+=N；不平衡比率IR=N-/N+；采样率SR；近邻参数K。

输出：过采样后的训练集S′={（xi, yi）, i=1,2, …, N+N+× SR, yi∈{+, -}}。

算法步骤：

1．从训练集S中取出全部多数类与少数类样本，组成多数类训练样本集S-及少数类训练样本集S+；

2．置DANGER集为空；

3．置新生成样本集SNew为空；

4.For i=1:N+

4.1在S+中找到对应样本xi；

4.2在S中找到xi的K近邻，记录其多数类近邻数为N maj；

4.3若K＞N maj≥K/2，则将xi 加入DANGER，即DANGER=DANGER∪xi；

End

5.For i=1:N+×SR

5.1在DANGER集中随机选出一个主样本x；

5.2在S+中找到主样本x的K 近邻样本，并将其置于近邻样本集SNer中；

5.3在1～K之间随机选择一个数字，并在SNer中找到对应的主近邻样本x′；

5.4通过下式计算得到新少数类样本xnew:xnew=x+rand ×（x′-x），其中，rand∈[0,1]；

5.5添加xnew至SNew, SNew=SNew∪xnew；

5.6置近邻样本集SNer为空；

End

6．得到过采样后的训练集S′=S∪SNew。

算法3-5:BSO2算法

输入：训练集S={（xi, yi）, i=1,2, …, N, yi∈{+, -}}；多数类样本数N-，少数类样本数N+，其中，N-+N+=N；不平衡比率IR=N-/N+；采样率SR；近邻参数K。

输出：过采样后的训练集 S′={（xi, yi）, i=1,2, …, N+N+× SR, yi∈{+, -}}。

算法步骤：

1．从训练集S中取出全部多数类与少数类样本，组成多数类训练样本集S-及少数类训练样本集S+；

2．置DANGER集为空；

3．置新生成样本集SNew为空；

4.For i=1:N+

4.4在S+中找到对应样本xi；

4.5在S中找到xi的K近邻，记录其多数类近邻数为N maj；

4.6若K＞N maj≥K/2，则将xi 加入DANGER，即DANGER=DANGER∪xi；

End

5.For i=1:N+×SR

5.1在DANGER集中随机选出一个主样本x；

5.2在S中找到主样本x的K 近邻样本，并将其置于近邻样本集SNer中；

5.3在1～K之间随机选择一个数字，并在SNer中找到对应的主近邻样本x′；

5.4通过下式计算得到新少数类样本xnew:xnew=x+rand ×（x′-x），其中，rand∈[0,0.5]；

5.5添加xnew至SNew, SNew=SNew∪xnew；

5.6置近邻样本集SNer为空；

End

6．得到过采样后的训练集S′=S∪SNew。

从上述算法流程可以看出，BSO1算法与BSO2算法略有不同，前者继承了SMOTE算法的思想，在生成新样本时，仅利用了主样本的同类近邻信息，即仅在两个邻近的少数类样本间生成新样本，而后者则利用了整个训练集的邻域信息，即同时在多数类与少数类样本中寻找K近邻，为了防止新生成的样本过于靠近多数类决策区域，该算法将随机数设为[0,0.5]区间，从而可以保证新生成的样本更靠近主样本，而非主近邻样本。

Borderline-SMOTE算法有效地克服了SMOTE算法的第2个缺点，即可有效规避原始噪声信息在新样本集上的传播，从而在一定程度上提升了SMOTE算法的分类性能。但同时，由于在计算K近邻时，加入了全部多数类样本的信息，这也将不可避免地进一步增加了算法的时间开销。

3.3.3 ADA-SYN采样法

与Borderline-SMOTE算法相类似，ADA-SYN（adaptive synthetic sampling）算法也是一种改进的SMOTE算法。该算法为He等人[7]于2008年提出，其主要思想是充分利用样本的密度分布信息来确定各少数类样本用作主样本的频次，从而尽可能修正类别不平衡分布所产生的负面影响。

ADA-SYN算法首先要确定需生成的新少数类样本数，即N+×SR，然后在原始训练集S上找到每个少数类样本, i=1,2, …, N+的K近邻，其中，第i个少数类样本的多数类近邻数记为j，进而可通过下式确定每个少数类样本各自的比例参数Γi：

其中，Z为标准化因子，用以保证=1。在比例参数确定后，即可通过下式确定每个少数类样本被选作主样本的频次：

从式（3-1）和式（3-2）不难看出，与Borderline-SMOTE算法相似，ADA-SYN算法更关注那些位于决策边界附近的少数类样本，它们被选作主样本的频次远远高于那些位于少数类决策区域内的样本。当然，这也会进一步放大少数类噪声信息的传播强度。ADA-SYN算法的具体流程如下。

算法3-6:ADA-SYN算法

输入：训练集S={（xi, yi）, i=1,2, …, N, yi∈{+, -}}；多数类样本数N-，少数类样本数N+，其中，N-+N+=N；不平衡比率IR=N-/N+；采样率SR；近邻参数K。

输出：过采样后的训练集S′={（xi, yi）, i=1,2, …, N+N+× SR, yi∈{+, -}}。

算法步骤：

1．从训练集S中取出全部多数类与少数类样本，组成多数类训练样本集S-及少数类训练样本集S+；

2．置新生成样本集SNew为空；

3.For i=1:N+

3.1在S+中找到对应样本xi；

3.2在S中找到xi的K近邻，记录其多数类近邻数为N m aj；

3.3采用式（3-1）计算其比例参数Γi；

3.4采用式（3-2）计算其主样本频次gi；

End

4.For i=1:N+

4.1在S+中找到主样本xi；

For j=1:gi

4.2调用SMOTE算法生成主样本xi的新样本；

4.3添加至SNew, SNew=SNew∪；

End

End

5．得到过采样后的训练集S′=S∪SNew。

ADA-SYN算法的最大优点是可以自适应地确定每个少数类样本作为主样本的频次，并将关注点集中于少数类的边界区域。但是，该算法的抗噪性能较差，在一定程度上会放大少数类噪声信息的作用范围，从而致使分类质量下降。

3.3.4 OSS采样法

OSS（one-side selection，即单边选择法），是一种较为经典的降采样算法[8]。不同于RUS算法，OSS算法不会随机地移除样本，而是在充分评估每个样本所含信息量大小的基础上，再确定移除哪些样本。OSS算法采用了Tomek links[9]的概念来移除多数类样本。所谓Tomek links，即是指这样的一类样本对（xi, xj），其中xi来自少数类，而xj来自多数类，在样本空间中不存在第3个样本xk，使得d（xi, xk）＜d（xi, xj）或d（xj, xk）＜d（xi, xj）成立，即xi与xj来自不同类别，且二者互为最近邻。通常，被标记为Tomek links的样本要么处于边界附近，要么就是噪声样本。若能在降采样时，将多数类中噪声样本与边界样本移除，则可以有效地扩展少数类的决策区域，从而修正原本偏倚的样本分布。图3-6给出了一个不平衡样本集上的Tomek links挖掘实例。

从图3-6中不难看出，在移除Tomek links中的样本后，样本集中的边界及噪声信息能得到有效削弱，样本集将变得更为纯化。特别需要说明的是，在OSS算法中，仅移除Tomek links中的多数类样本，而将少数类样本完全保留。OSS算法流程如下。

算法3-7:OSS算法

输入：训练集S={（xi, yi）, i=1,2, …, N, yi∈{+, -}}；多数类样本数N-，少数类样本数N+，其中，N-+N+=N。

输出：降采样后的训练集S′。

算法步骤：

1．从训练集S中取出全部少数类样本与一个随机抽取的多数类样本组成训练子集C；

2．设置子集Q并置其为空；

3．设置子集L并置其为空；

4.For i=1:N

从原始训练集S中取出样本xi，并在训练子集C上以最近邻判别规则对其类别进行标注，若分类错误，则将其添加进子集Q，即Q=Q∪xi；

End

5．将Q子集添加入训练子集C，即C=Q∪C；

6．在子集C中找到所有的Tomek links，并将其中的多数类样本置于子集L中；

7．得到降采样后的训练集S′=C-L。

图3-7给出了上述算法流程的直观表达。

显然，不同于RUS算法，OSS算法能保留多数类中的绝大多数分类信息，进而保证后期分类器的训练质量。OSS算法与RUS算法的另一个不同点是：RUS的采样率是可控的，而OSS算法的采样率不可控。除OSS算法外，还有一些与之类似的数据清洗算法，如近邻清洗规则（neighborhood cleaning rule, NCL）算法[10]、SMOTE+Tomek算法[11]等也已被用于解决类别不平衡学习问题。

3.3.5 SBC采样法

Yen和Lee[12]考虑采用聚类的方法来降采样多数类样本，他们提出了基于聚类的采样法（sampling based on clustering, SBC）采样法。SBC采样法的理论依据在于：在多数类样本的聚集区域，应保留尽可能多的多数类样本，而在少数类样本的聚集区域，则应尽可能多地移除多数类样本。这一观点与我们的直观认识也是相吻合的。

具体而言，假设在原始训练集S上，多数类样本与少数类样本分别有N-与N+个，即IR=N-/N+，若在采样后，希望保留m×N+（IR≥m≥1）个多数类样本，则须首先统计每个类簇中的多数类与少数类样本数 与 ，其中，i∈{1,2, …, K}, K为聚类的类簇数，然后通过下式可计算每个类簇中应保留的多数类样本数：

显然，表示所有类簇的不平衡比率之和，其可被看作是一个标准化因子。对于第i个类簇，若其不平衡比率越高，则保留的多数类样本数也越多，反之，则保留的多数类样本数越少。此外，需考虑一种特殊情况，即当某个类簇中完全没有少数类样本出现时，则式（3-3）的结果将为无穷。为避免这种情况出现，SBC算法规定每个类簇中的最小取值为1。SBC算法的具体流程如下。

算法3-8:SBC算法

输入：训练集S={（xi, yi）, i=1,2, …, N, yi∈{+, -}}；多数类样本数N-，少数类样本数N+，其中，N-+N+=N，保留样本率m，类簇个数K。

输出：降采样后的训练集S′。

算法步骤：

1．调用聚类算法对原始训练集S进行聚类，得到K个互不相交的类簇；

2．计算每个类簇中的多数类与少数类样本数与，并采用式（3-3）计算得到各簇中应该保留的多数类样本个数j；

3．设置子集Q并置其为空；

4.For i=1:K

从第i个类簇中随机移除j个多数类样本，并将其移入子集Q中；

End

5．得到降采样后的训练集S′=S-Q。

图3-8为上述算法流程的一个示例，从该图可以更加直观地理解SBC算法的思想及流程，从中也不难看出SBC算法的优点，即可最大限度地保留多数类样本的原始局域分布信息，从而保证后期的分类器训练质量。

此外，在SBC算法中，还有几个需要关注的问题，一是应选取何种聚类算法，二是类簇数K 应如何确定。一般而言，聚类算法只需采用较为简单的K-means算法即可，而参数K的确定，则需具体问题具体分析，需要用户根据实际情况来进行设置。除SBC算法外，聚类技术也被用于开发相应的过采样算法，有兴趣的读者可阅读文献[13]。