机器学习9：采样

目录：

一，采样概述：

二，常用的几种采样技术：

1，均匀采样：

2，逆变换采样 3，拒绝采样

4，重要性采样

5，马尔可夫蒙特卡洛采样法

6，贝叶斯网络的采样

7，不均衡样本集的重采样

7.1，基于数据的方法

7.1.1，SMOTE算法

7.2，基于算法的方法

三，蒙特卡洛求解定积分：

1，投影法

2，期望法

四，代码实现：

1，马尔可夫平稳收敛性验证

2，对Beta分布进行采样

一，采样概述：

采样本质上是对随机现象的模拟，根据给定的概率分布，来模拟产生一个对应的随机事件。采样可以让人们对随机事件及其产生过程有更直观的认识。

采样得到的样本集也可以看作是一种非参数模型，即用较少量的样本点（经验分布）来近似总体分布，并刻画总体分布中的不确定性。从这个角度来说，采样其实也是一种信息降维，可以起到简化问题的作用。

另外，利用重采样技术，可以在保持特定的信息下（目标信息不丢失），有意识地改变样本的分布，以更适应后续的模型训练和学习，例如利用重采样来处理分类模型的训练样本不均衡问题。

此外，很多模型由于结构复杂、含有隐变量等原因，导致对应的求解公式比较复杂，没有显式解析解，难以进行精确求解或推理。在这种情况下，可以利用采样方法进行随机模拟，从而对这些复杂模型进行近似求解或推理。这一般会转化为某些函数在特定分布下的积分或期望，或者是求某些随机变量或参数在给定数据下的后验分布等。

二，常用的几种采样技术：

1，均匀采样：

几乎所有的采样方法都是以均匀分布随机数作为基本操作。

均匀分布是指整个样本空间中的每一个样本点对应的概率（密度）都是相等的。根据样本空间是否连续，又分为离散均匀分布和连续均匀分布。均匀分布可以算作是最简单的概率分布。从均匀分布中进行采样，即生成均匀分布随机数，几乎是所有采样算法都需要用到的基本操作。

一般可采用线性同余法（Linear Congruential Generator）来生成离散均匀分布伪随机数，计算公式为：

也就是根据当前生成的随机数xt来进行适当变换，进而产生下一次的随机数xt+1。初始值x0称为随机种子。上式得到的是区间[0,m−1]上的随机整数，如果想要得到区间[0,1]上的连续均匀分布随机数，用xt除以m即可。上式是通过大气噪声来产生随机数。

2，逆变换采样：

对于一个随机变量，通常用概率密度函数来刻画该变量的概率分布特性。具体来说，给定随机变量的一个取值，可以根据概率密度函数来计算该值对应的概率（密度）。反过来，也可以根据概率密度函数提供的概率分布信息来生成随机变量的一个取值，这就是采样。因此，从某种意义上来说，采样是概率密度函数的逆向应用。通常根据待采样分布的具体特点来选择合适的采样策略。

如果待采样的目标分布的累积分布函数的逆函数无法求解或者不容易计算，则不适用于逆变换采样法。此时可以构造一个容易采样的参考分布，先对参考分布进行采样，然后对得到的样本进行一定的后处理操作，使得最终的样本服从目标分布。常见的拒绝采样（RejectionSampling）、重要性采样（Importance Sampling），就属于这类采样算法。

拒绝采样，又叫接受/拒绝采样（Accept-Reject Sampling）。对于目标分布p(x)，选取一个容易采样的参考分布q(x)，使得对于任意x都有p(x) <= M* q(x)。

在实际应用中，为了维持采样效率，有时很难寻找一个解析形式的q(x)，因此延伸出了自适应拒绝采样（Adaptive Rejection Sampling），在目标分布是对数凹函数时，用分段线性函数来覆盖目标分布的对数ln p(x)。

很多时候，采样的最终目的并不是为了得到样本，而是为了进行一些后续任务，如预测变量取值，这通常表现为一个求函数期望的形式。重要性采样就是用于计算函数f(x)在目标分布p(x)上的积分（函数期望）：

如果不需要计算函数积分，只想从目标分布p(x)中采样出若干样本，则可以用重要性重采样（Sampling-Importance Re-sampling，SIR），先在从参考分布q(x)中抽取N个样本 {xi }，然后按照它们对应的重要性权重{w(xi)}对这些样本进行重新采样（这是一个简单的针对有限离散分布的采样），最终得到的样本服从目标分布p(x)。

在实际应用中，如果是高维空间的随机向量，拒绝采样和重要性重采样经常难以寻找合适的参考分布，采样效率低下（样本的接受概率小或重要性权重低），此时可以考虑马尔可夫蒙特卡洛采样法，常见的有Metropolis-Hastings采样法和吉布斯采样法。

5，马尔可夫蒙特卡洛采样法：

MCMC采样法基本思想是：针对待采样的目标分布，构造一个马尔可夫链，使得该马尔可夫链的平稳分布就是目标分布；然后，从任何一个初始状态出发，沿着马尔可夫链进行状态转移，最终得到的状态转移序列会收敛到目标分布，由此可以得到目标分布的一系列样本。

MCMC采样法的核心点是构造合适的马尔可夫链，不同的马尔可夫链对应着不同的MCMC采样法，常见的有Metropolis-Hastings采样法和吉布斯采样法：

6，贝叶斯网络的采样：

概率图模型经常被用来描述多个随机变量的联合概率分布。贝叶斯网络，又称信念网络或有向无环图模型。它是一种概率图模型，利用有向无环图来刻画一组随机变量之间的条件概率分布关系。

下图是贝叶斯网络的一个经典例子，用来刻画Cloudy、Sprinkler、Rain、WetGrass等变量之间的条件分布关系。

对一个没有观测变量的贝叶斯网络进行采样，最简单的方法是祖先采样（AncestralSampling），它的核心思想是根据有向图的顺序，先对祖先节点进行采样，只有当某个节点的所有父节点都已完成采样，才对该节点进行采样。以场景描述中的图8.9为例，先对Cloudy变量进行采样，然后再对Sprinkler和Rain变量进行采样，最后对WetGrass变量采样，如图8.10所示（图中绿色表示变量取值为True，红色表示取值为False）：

7，不均衡样本集的重采样：

在训练二分类模型时，例如医疗诊断、网络入侵检测、信用卡反诈骗等，经常会遇到正负样本不均衡的问题。对于很多分类算法，如果直接采用不均衡的样本集来进行训练学习，会存在一些问题。例如，如果正负样本比例达到1∶99，则分类器简单地将所有样本都判为负样本就能达到99%的正确率，显然这并不是我们想要的，我们想让分类器在正样本和负样本上都有足够的准确率和召回率。

一般可以从两个角度来处理样本不均衡问题：

7.1，基于数据的方法：

最简单的处理不均衡样本集的方法是随机采样。采样一般分为过采样（Over-sampling）和欠采样（Under-sampling）。随机过采样是从少数类样本集Smin中随机重复抽取样本（有放回）以得到更多样本；随机欠采样则相反，从多数类样本集Smaj中随机选取较少的样本（有放回或无放回）。

直接的随机采样虽然可以使样本集变得均衡，但会带来一些问题，比如，过采样对少数类样本进行了多次复制，扩大了数据规模，增加了模型训练的复杂度，同时也容易造成过拟合；欠采样会丢弃一些样本，可能会损失部分有用信息，造成模型只学到了整体模式的一部分。

7.1.1，SMOTE算法：

为了解决上述问题，通常在过采样时并不是简单地复制样本，而是采用一些方法生成新的样本。例如，SMOTE算法对少数类样本集Smin中每个样本x，从它在Smin中的K近邻中随机选一个样本y，然后在x,y连线上随机选取一点作为新合成的样本（根据需要的过采样倍率重复上述过程若干次），如下图所示。这种合成新样本的过采样方法可以降低过拟合的风险。

SMOTE算法为每个少数类样本合成相同数量的新样本，这可能会增大类间重叠度，并且会生成一些不能提供有益信息的样本。为此出现Borderline-SMOTE、ADASYN等改进算法。Borderline-SMOTE只给那些处在分类边界上的少数类样本合成新样本，而ADASYN则给不同的少数类样本合成不同个数的新样本。此外，还可以采用一些数据清理方法（如基于TomekLinks）来进一步降低合成样本带来的类间重叠，以得到更加良定义（well-defined）的类簇，从而更好地训练分类器。

同样地，对于欠采样，可以采用InformedUndersampling来解决由于随机欠采样带来的数据丢失问题

7.2，基于算法的方法：

在样本不均衡时，也可以通过改变模型训练时的目标函数（如代价敏感学习中不同类别有不同的权重）来矫正这种不平衡性；当样本数目极其不均衡时，也可以将问题转化为单类学习（one-classlearning）、异常检测（anomaly detection）。

三，蒙特卡洛求解定积分：

1，投影法：

有一个函数f(x)，若要求它从a到b的定积分，其实就是求曲线下方的面积。这时我们可以用一个比较容易算得面积的矩型罩在函数的积分区间上（假设其面积为Area）。然后随机地向这个矩形框里面投点，其中落在函数f(x)下方的点为绿色，其它点为红色。然后统计绿色点的数量占所有点（红色+绿色）数量的比例为r，那么就可以据此估算出函数f(x)从a到b的定积分为Area乘以r

2，期望法：

期望法，也称为平均值法。用g*来近似求解出E(g)的期望：

四，代码实现：

1，马尔可夫平稳收敛性验证

2，对Beta分布进行采样：

# 1，马尔可夫平稳收敛性验证：
import numpy as np

transfer_matrix = np.array([[0.6,0.2,0.2],[0.3,0.4,0.3],[0,0.3,0.7]], dtype=np.float32)
start_matrix = np.array([[0.5, 0.2, 0.3]], dtype=np.float32)
for i in range(30):
    print(start_matrix)
    start_matrix = np.dot(start_matrix, transfer_matrix)


# 2，对Beta分布进行采样: 已知Beta分布的pdf(概率密度函数)
import numpy as np
import scipy.special as ss
import matplotlib.pyplot as plt

def beta_s(x, a, b):
    return x**(a-1)*(1-x)**(b-1)

def beta(x, a, b):  # Beta distribution的概率密度函数（pdf）
    return beta_s(x, a, b)/ss.beta(a, b)

def plot_mcmc(a, b):
    cur = np.random.rand()
    states = [cur]  # 取一个初始化的状态
    for i in range(10**5):
        next = np.random.rand()  # 选择一个新的 Proposal State
        u = np.random.rand()
        if u < np.min((beta_s(next, a, b)/beta_s(cur, a, b), 1)):
            states.append(next)
            cur = next
    x = np.arange(0, 1, .01)
    plt.figure(figsize=(10, 5))
    plt.plot(x, beta(x, a, b), lw=2, label='real dist: a={}, b={}'.format(a, b))
    plt.hist(states[-1000:], 25, normed=True, label='simu mcmc: a={}, b={}'.format(a, b))
    plt.show()

if __name__ == '__main__':
  plot_mcmc(0.1, 0.1)
  plot_mcmc(1, 1)
  plot_mcmc(2, 3)

Reference：

《百面机器学习》

https://www.jianshu.com/p/3fb6f4d39c60

https://www.jianshu.com/p/c602eaad78c1

https://www.jianshu.com/p/7ce411e3c377

https://www.cnblogs.com/astoninfer/p/9283702.html