（1）reject sampling

（2）欠采样/过采样

（3）SMOTE

一、reject sampling(拒绝采样)

    为了得到一个分布的样本，我们通过某种机制得到了很多的初步样本，然后其中一部分初步样本会被作为有效的样本（即要抽取的分布的样本），一部分初步样本会被认为是无效样本舍弃掉。这个算法的基本思想是：我们需要对一个分布f(x)进行采样，但是却很难直接进行采样，所以我们想通过另外一个容易采样的分布g(x)的样本，用某种机制去除掉一些样本，从而使得剩下的样本就是来自于所求分布f(x)的样本。

    它有几个条件：1）对于任何一个x，有f(x) <= M * g(x)；

                            2）g(x)容易采样

                           3）g(x)最好在形状上比较接近f(x)。

    具体的采样过程如下：

    1. 对于g(x)进行采样得到一个样本xi, xi ~ g(x)

    2. 对于均匀分布采样 ui ~ U(a,b)

    3. 如果ui <= f(x) / [M * g(x)]，那么认为xi是有效的样本；否则舍弃该样本

    4. 反复重复步骤1~3，直到所需样本达到要求为止

    g(x)称为建议分布，g(x)不一定什么时候都比f(x)大，因为g(x)是一个分布，积分之和等于1，f(x)也是。构建g(x)的时候可以使用f(x)乘以一个常数，即上面的M，这样f(x)会比g(x)小。在这条线上坐均匀分布的采样，红的就拒绝，绿的就接受。如果g(x)选择不好的时候，接受率很差。

     假如有一个随机数生成器只能生成0,1,2，怎么使得采样的值在[0,27]之间是均匀的。答案见本文最后面。

二、欠采样/过采样

    比如有两组样本如上图所示，一组正向样本如圆圈，样本数非常多；另一组如方框，样本数非常少。比如银行中有风险的样本是非常少的，大部分都是正常的样本。这样训练的模型因为数据倾斜导致模型不准。再举一例，比如样本中正向样本占99.9%，负向样本占0.1%，则模型预期值可能全部都是正向的，已经准确率已经达到了99.9%，模型有时候也会偷懒的。

    为了使数据不要出现倾斜，我们采用欠采样或者过采样的方式。

    欠采样就是保持右边的不变，左右只取右边相同个数的样本，即两边都是4个。这样会使得样本特别少，模型不准确。另一种方式相反，就是左边保持不变，右边数量增加到20个同左边相同（右边样本每个复制5个出来），或者右边的每个权重提高5倍。但是过采样会导致过拟合现象，比如：

    中间标红的花朵型就是过拟合导致的，我们希望是蓝色圆形，边缘是平滑的。

三、SMOTE

    SMOTE全程synthetic Minority Oversampling Technique即合成少数过采样技术，它是基于随机过采样算法的一种改进方案。由于随机过采样才去简单复制样本的策略来增加少数类样本，这样容易产生模型过拟合的问题提，即使得模型学习到的信息过于特别而不够泛化。SMOTE算法的思想是对少数类样本进行分析并根据少数类样本人工合成新样本添加到数据集中，具体算法流程如下：

    1. 对于少数类中每一个样本x，以欧式举例为标准计算它到少数类样本集Smin中所有样本的举例，得到其k近邻。

    2. 根据样本不平衡比例设置一个采样比例以确定采样倍率N，对于每一个少数类样本x，从其k近邻中随机选择若干个样本，假设选择的近邻为Xn

    3. 对于每一个随机选出的近邻Xn，分别与原样本按照如下的公式构建新的样本

，即在x与Xn的中间某一个位置选一个样本

四、答案

可以做成4位，每位分别是0,1,2的三进制数。

[012] [012] [012] [012]，最大数2222为2*27 + 2*9 + 2*3 + 2 = 90  > 27，此时可以采用拒绝采样，大于27的一律拒绝掉，这样就可以在[0,27]范围内通过012随机数机采样到均匀分布了。