样本选择是数据预处理中非常重要的一个环节，主要是从海量数据中识别和选择相关性高的数据作为机器学习模型输入。

样本选择概述

　　样本选择的目的是从完整训练集 $T$ 中选择一个子集 $S\subset T$，子集 $S$ 不再包含冗余样本，如下图所示。最理想的样本选择结果是，选择了最少量的训练集 $S$，而模型效果依然不会变差，即满足 $P(\text{Algo}_S) = P(\text{Algo}_T)$，其中，$P$ 表示模型评估函数，Algo 表示机器学习模型。

样本选择流程图

　　做样本选择主要有以下三点好处：

  1. 当数据量过大时，程序有时候会耗费大量计算资源和计算时间，有时候甚至不能正常运行。减小数据量能够缩减模型的运算时间，使某些因为数据量过大无法应用机器学习模型的问题变得可能。
  2. 全部的数据集包含丰富的信息，但是一个具体的问题，通常只需要选取一部分问题相关的信息，相关性太低的数据对解决特定问题可能没有帮助。
  3. 数据中几乎不可避免地会有噪声数据，这些噪声可能是系统原因导致数据有错误、重复等。通过去除噪声能提高训练集的数据质量，改善模型效果。

　　样本选择有很多方法：

  1. 数据去噪
  2. 数据采样（Sampling）
  3. 不依赖采样的样本选择方法，通过搜索整个数据集或利用算法来实现样本选择
    • 原型选择（Prototype Selection, PS）
    • 训练集选择（Training Set Selection, TSS)

数据去噪

　　数据中含有噪声数据几乎是不可避免的问题。噪声的存在会导致数据质量变低，影响模型的效果，但通过在训练集中引入噪声数据也能起到提升模型健壮性的作用。因此，包含噪声数据的问题是非常复杂的，特别是当选择的模型对噪声敏感的时候，问题会更严重。要进行去噪操作，对噪声进行识别是十分关键的一个步骤。识别出了噪声之后，可以采取直接过滤或者修改噪声数据等多种做法。

　　噪声在监督学习问题中影响明显，会改变特征和标注之间的关系，影响到特征提取；并且有噪声训练集和无噪声训练集得到的模型也会有差异。为此，提高模型健壮性，会使得模型对噪声数据不那么敏感。当需要处理噪声数据的时候，通常会权衡模型的健壮性和模型的效果。

　　噪声数据可能是特征值不对，比如特征值缺失、超出特征值域范围等；也可能是标注不对，比如二分类正样本标注成负样本。数据去噪很多是检测和去除训练数据中标注带噪声的实例，去除这样的噪声数据对实验结论是有帮助的；而去除特征带噪声的数据在很多地方表明效果反而变差，由此可见噪声特征带有的一定信息能够用于构建模型，比如特征缺失时，可以认为没有特征也是一个特征，这也能描述一定的信息。

　　针对误标注实例有很多成功的处理方案，最常见的有集成过滤法（Ensemble Filter, EF）、交叉验证委员会过滤法（Cross-validated Committees Filter, CVCF）和迭代分割过滤法（Iterative- Partitioning Filter, IPF）这三种方法，这些方法都是基于融合或者投票的思想进行数据过滤的。

　　除了这些过滤方法外，其实还会考虑就业务的本身性质做一些数据过滤工作，比如清洗爬虫数据和不具代表性样本等。再如过滤掉无效曝光数据，根据用户最后一次点击行为的位置，过滤掉最后一次点击之后的展示，可以认为用户没有看到，也可以保留最后一次点击之后的少数几个曝光。

采样

采样是一个完善的统计技术，从整体选择一部分来进行推论。采样能够克服高维特征以及大量数据导致的问题，有助于降低成本，缩短时间甚至提升效果，在不平衡分类问题中还能帮助平衡样本比例。进行采样时最关心采样方法和采样比例。

通常，考虑样本对总体的估计值不超出边际误差的情况下是能够计算出样本量的。如下面的概率不等式：

\[P\left(\left|e-e_{0}\right| \geqslant \epsilon\right) \leqslant \delta\]

对于给定的 $\epsilon$ 和 $\delta$, 能够计算出采样大小 $n$。其中，$e$ 代表样本的估计，通常是样本大小 $n$ 的函数；$e_0$ 代表真实的样本；$\epsilon$ 是置信度；$1-\delta$ 是置信区间。然而，$e_0$ 一般都是未知的，通常会先从样本中采样一个小的有 $m$ 条样本的数据集，对 $e_0$进行估计，之后再计算对应的 $n$ 值。如果 $n\ge m$，然后再从余下的样本集中选取额外的 $nーm$ 条样本；如果 $n\le m$，那么就将 $m$ 条样本作为采样结果。

一个好的样本子集应该具有无偏性（Unbiasedness 和很小的样本方差（Sampling Variance）其中无偏性指的是对样本的期望等于全体样本期望，即 $E(e)=e_0$。样本方差是衡量样本估计值和真实值的偏差，即 $Var(e) = E[e-E(e)]^2$, 小方差能保证估计值不会产生太大偏差。

现有的采样方法有很多，下文简单介绍 5 种采样方法。

  • 无放回简单随机抽样（Simple Random Sample Without Replacement）它从含 N 条样本的数据集 T 中采样 s (s≤N）条样本，每条样本被采到的概率相等且都为 $\frac{1}{N}$
  • 有放回简单抽样（Simple Random Sample With Replacement）。它和无放回简单随机抽样类似，不同的是每次从数据集 T 中抽取一条样本后，还将这条样本放回到数据集 T 中，因此每条样本可能多次被选中。
  • 平衡采样（Balanced Sample）。它根据目标变量进行采样，依据预定义的比例对样本进行重新组合，在不平衡分类问题中有十分成功的应用。不平衡分类问题指分类任务中不同类别的数据量差异巨大，通常会对小数据量的类别进行上采样，或者对大数据量的类别进行下采样。比如一份二分类样本有 100 条正样本、10000 条负样本，采样目标是使正负样本比例为 1:10, 那么上采样就是对正样本复制 10 遍，负采样就是对负样本随机删除部分样本留下 1000 条；ADASYN 和 SMOTE 算法是上采样里两个比较常用的方法。
  • 整群采样（Cluster Sample）。它先将数据集ア中的数据分组成 G 个互斥的簇，然后再从 G 个簇中简单随机采样 s (s≤G）个簇作为样本集，这个方法是分两个阶段完成采样的。
  • 分层采样（Stratified Sample）。数据集 T 划分成不同的层，然后在每层内部进行简单随机抽样，最后汇总成样本集合 S。该方法也常用于不平衡分类问题中，和平衡采样非常相关。该方法分别对每个类别进行采样，能使每个类别在样本集 S 中的分布和数据集 7 中的分布更为一致。比如对平衡采样中的二分类数据进行分层采样，目的是采样 90%数据，分层采样以采样率 09 分别对正负样本采样，能保证正负比例还是 1:100; 如果对全部 10100 条样本采样 90%，可能出现正样本 10 条、负样本 9080 条的情况。

原型选择和训练集选择

原型选择是基于实例的方法，在样本选择过程中不需要训练模型，而是选取相似度或距离度

量指标来找到分类精度和数据量最佳的训练集，多数采用 KNN 算法。训练集选择则是构建预测模型来进行样本选择的方法的统称，比如决策树、ANN 和 SVM 等算法。原型选择和训练集选择两大类别的样本选择方法有很多，然而没有一种方法能够通用。

原型选择有很多分类标准，根据从数据集 T 中选择样本集 S 的方向可以分为以下 5 类。

口增量法。开始时令 S=の，然后逐条遍历数据集 T 中的每条样本，如果满足条件则加入 S 中。口递減法。和增量法相反，开始时令 S=T，然后逐条査找待过滤的样本从 S 中删除。ロ批量法。和递减法类似，批量法先判断一批数据的每条数据是否应该删除，然后再将这批数据中全部满足删除条件的样本一起删除。

口混合法。预先选定一部分样本 S≠の，然后迭代地增加或删除满足对应条件的样本。ロ固定法。是混合法的一个子方法，但最终选择的样本数是固定的。

原型选择也可以类似特征选择，根据选择样本的策略进行分类。

口包装器。根据模型的目标函数，一般是模型预测结果来进行样本选择。口过滤器。样本的选择标准不基于模型。

还可以根据选择的样本，原型选择相关算法可分为如下三类。

ロ Condensation。保留决策边界处样本

ロ Edition。删除边界的异常点，使得边界更平滑。

ロ Hybrid。尝试找到最小的样本集 S，能够保持甚至提升测试集上的泛化精度。

大量原型选择算法都可以根据上述分类标准进行划分。在此就不针对具体的算法展开介绍了。

References

  1. 《美团机器学习》