机器学习之类别不平衡问题：从数据集角度处理不平衡问题（二）

上一篇我们介绍了常用的过采样的方法,本篇主要介绍常用的欠采样的方法 。

1、 欠 采样

与过采样相反，所谓欠采样，就是减少少数类的样本量。如下图所示，欠采样的方法主要分成两类：原型生成 (prototype generation) 与原型选择 (prototype selection) ，每类下面又有其他的方法，具体如下。

1.1、原型生成(prototype generation)

原型生成方法将会根据原始数据集重新生成一个数据集，新生成的数据集的样本量小于原始数据集的样本量，且新生成的数据集的样本不在原始数据集中（不是原始数据集的子集）。也就是说，原型生成的方法得到的数据集是生成得到的，而不是从原始样本中进行选择。最常见的原型生成算法是通过聚类来实现，例如用 k-means 算法得到聚类中心之后，根据聚类中心来生成新的样本。 这种算法能够较为高效的减少样本数量，但是对于原始数据重叠度较高的情况下，该种方法可能将会不适用，因为聚类算法生成的类簇可能会是不准确的。

1.2、原型选择(prototype selection)

与原型生成不同，原型选择是直接从原始数据集中进行抽取。即新生成的数据集样本量小于原始数据集的样本量，新生成的数据集的样本。抽取的方法可以分为两类 : (i) 可控的下采样技术 (controlled under-sampling techniques) ； (ii) 基于数据清洗方法的下采样技术 (the cleaning under-sampling techniques) 。

1.2.1 Controlled under-sampling techniques

1.2.1.1 Random UnderSampler

随机欠采样 的思想 就是从多数类样本中随机选取一些 样本直接 剔除掉。这种方法的缺点 十分明显， 被剔除的样本可能包含着一些重要信息， 导致 学习出来的模型效果不好。 与随机过采样一样，随机欠采样丢弃了大量了数据，也会导致模型过拟合。

1.2.1.2 NearMiss

NearMiss 作为 随机欠采样 的改进，它主要为了缓解随机欠采样中的信息丢失问题，通过启发式的规则从多数类样本中选择具有代表性的样本进行训练，主要有以下三种：

NearMiss-1 ：对于每个多数类样本，计算与每个少数类样本的距离，选择最近的 k 个少数类样本并计算这 k 个少数类样本的平均距离，保留平均距离最小的多数类样本。

如下图， “ + ”代表多数类，“ - ”代表少数类，我们取 k=3 ，计算多数类中的两个具体样本的距离。通过计算发现，绿线的距离比红线的距离小，也就是说绿线对应的样本到 最近的 3 个少数类样本 的距离比红线对应的样本小，因此我们选择绿线对应的多数类样本。

NearMiss-2 ：对于每个多数类样本，计算与每个少数类样本的距离，选择最远的 k 个少数类样本并计算这 k 个少数类样本的平均距离，保留平均距离最小的多数类样本。

同样，我们取 k=3 ，计算多数类中的两个具体样本的距离。通过计算发现，绿线的距离比红线的距离小，即绿线对应的样本到 最远的 3 个少数类样本 的距离比红线对应的样本小，因此我们选择绿线对应的多数类样本。

NearMiss-3 ：首先对于每个少数类样本，计算与每个多数类的距离，保留距离最近的 m 个多数类样本；接着对于保留的多数类样本，计算与每个少数类样本的距离，选择最近的 k 个少数类样本并计算这 k 个少数类样本的平均距离，保留平均距离最小的多数类样本。如下图，其中我们取 m=k=3 ，首先计算得到保留的多数类样本（ Short-listed samples ，绿圈），然后在这些样本中，计算与每个少数类样本的距离，选择最近的 3 个少数类样本并计算这 3 个少数类样本的平均距离，保留平均距离最大的多数类样本。

通过上述介绍可以发现， NearMiss-1 与 NearMiss-2 方法仅一字之差，但是造成的结果却大不相同， NearMiss-1 使用的是最近的 k 个少数类样本的平均距离，即根据局部的样本进行选择；而 NearMiss-2 使用的则是最远的 k 个少数类样本的平均距离，所使用的样本则是整体的，全局的。由于 NearMiss-1 使用的只是局部样本的信息，容易受到噪声的影响。 NearMiss-3 因为在前期进行了多数类样本保留，对于噪声点具有一定的鲁棒性。

下面通过人工构造一个不每一个少数类样本附近都有足够多的多数类样本平衡数据集（与过采用中使用的数据集相同）来对比不同过采样方法的效果：

上面四幅图表示的分别是不同类别间距的情况下，各种过采样方法的结果。其中 class_sep=1.0 表示的是类与类之间没有重叠的情况， class_sep=0.1 表示的是各类之间几乎重叠，从原图中可以明显的看出。

从图中可以看出，经过欠采样后，在类别间隔较大的情况下， NearMiss-2 能较好反映原始数据的分布情况，其次则是 NearMiss-3 ， NearMiss-1 易受到噪声的影响，导致最终得到的分布与原始数据的分布差异较大；而在类别间隔较小时， NearMiss-3 的效果可能会优于 NearMiss-2 。

1.2.2 Cleaning under-sampling techniques

此类方法主要是基于某种规则针对重叠数据进行数据清洗，与 可控的下采样技术 (controlled under-sampling techniques) 最大的区别在于，这种方法不允许指定每个类别中的样本数量。

1.2.2.1 Tomek ’ s links

Tomek 是一种最常用的数据清洗技术，现已广泛应用于去除由采样引起的重复项。 TomekLinks 表示不同类别之间距离最近的一对样本，即这两个样本互为最近邻且属于不同的类别。如果某两个样本形成了 TomekLinks ，则这两个样本其中之一是噪声点，或者两个样本都是位于边界附近。通过去除形成 TomekLinks 的样本点，就能到达去除重叠样本的目的，最终使得互为最近邻的样本都属于同一类，从而更好地进行分类。

上图中 (a) 为原始数据集， (b) 为经过 SMOTE 算法过采样后的数据， (c) 中虚线框住的样本点表示的是 TomekLinks ， (d) 则是移除 TomekLinks 后的结果图。可以发现从 (b) 到 (d) 去除了许多样本，减少了类别之间的样本重叠情况（其实这就是 SMOTETomek ）。

1.2.2.2 Edited Nearest Neighbours（ ENN ）

Edited Nearest Neighbours 正如其名，是应用最近邻算法来编辑 (edit) 数据集。对于每一个多数类样本，只有在其 k 个近邻点有超过一半（或者全部）与该样本点本身属于同一个类，此时这个多数类样本才会被保留在数据集中。

ENN 的一种简单的改进是 Repeated Edited Nearest Neighbours 算法，该算法只是重复基础的 ENN 算法多次。

1.2.2.3 Condensed nearest neighbors and derived algorithms

此类方法主要是基于 KNN 来进行欠采样，同时会结合 TomekLinks 和 ENN 来改进算法。 Condensed Nearest Neighbour 顾名思义，这种方法是使用最近邻来进行迭代 , 来判断一个样本是应该保留还是剔除 , 具体的实现步骤如下 :

i). 定义集合 C 为所有的少数类样本

ii). 选择一个多数类样本 ( 需要下采样 ) 加入集合 C ，该类的其他样本放入集合 S

iii). 使用集合 S 训练一个 1-NN 的分类器，对集合 S 中的样本进行分类

iv). 将集合 S 中错分的样本加入集合 C

v). 重复上述过程，直到没有样本再加入到集合 C ；

通过上述步骤可以看出，这种方法对噪声十分敏感。这种方法的一个改进是 OneSided Selection ，该方法使用 TomekLinks 来剔除多类样本，相对 1-NN 而言对噪声不太敏感。 Neighbourhood Cleaning Rule 则主要关注如何清洗数据而不是筛选它们。

这类数据清洗的方法进行欠采样能够去除的样本点十分有限，而且无法控制样本数量，因为实际上多数类样本周围的样本基本上也都是多数量。在实际应用的效果上也差强人意，该类方法往往会与过采样方法结合使用，来去除过采样中过多的增加的样本点。

本篇主要介绍了欠采样方法来处理不平衡问题，介绍了常用的一些欠采样的方法，详细对比了 NearMiss 的三种规则以及优缺点。另外在数据清洗方法中（ Cleaning under-sampling techniques ）的 TomekLinks 和 Edited Nearest Neighbours （ ENN ）虽然本身在欠采样上的所能达到的效果有限，但是它们可以与过采样方法尤其是 SMOTE 方法结合来处理不平衡数据集。在下一篇文章中，将介绍过采样与欠采样结合的方法以及基于集成学习的处理不平衡数据集的方法。