内容简介

在数据爆棚的今天，如何快速、准确、有效地进行大数据分析和建模，是各行各业都在持续研究的课题。针对庞大的数据集，一般会通过一定的采样，以达到对整体数据的推断。采样算法的种类繁多，例如简单随机采样，系统采样，分层采样以及聚类采样等。接下来本文就带大家回顾一下几类常见的采样算法，并介绍 Spark Dataframe 或 HiveQL 的实现方式。
Sampling-Methods

采样算法

简单随机采样

简单随机采样 (Simple Random Sampling) 是一种概率型抽样，即随机从整体数据集N中选取n个元素作为代表性特征。通常简单随机采样的过程也可分为有放回式和无放回式2种。虽然该采样效率高且复杂性低，但在样本较小或置信度较低时不能消除数据偏差导致的样本分布不均匀。
$$
P(x) = n/N
$$

系统采样

系统采样 (Systematic Sampling) 按照一定计算规律（如时间周期，数量间隔等特征），从数据集中“均匀”采样以达到减少样本偏差的效果。常用于信号与线性系统，如按照时间周期采样。
$$
f(n) = f(n + T)
$$

分层采样

Stratified-Sampling

分层采样 (Stratified Sampling) 先根据数据集中某一个或几个特征进行分层（每层数据意义或类型不同），再按照一定比例从每层中随机抽取样本，最终合并成一个样本集。分层采样可以更好的捕捉每层数据间的差异，减少数据偏差对整体样本的影响，更加精确高效。
$$
S = \sum_{i = 1}^{i \leq N} si
$$

  • N 样本总量
  • S 样本总合
  • i 层数 (总层数必须<=样本总量)
  • si 第i层样本数 (若样本总数一定，第i层样本数 *si = (Ni / N) * S*, Ni为第i层数据量)

聚类采样

Cluster-Sampling

聚类采样 (Cluster Sampling)，先将数据集中元素分组聚类构建成有总体代表性的样本组，再随机选择一个或者多个样本组作为样本集。聚类采样与分层采样不同之处在于，聚类所区分出的类别，每组都可以一定性的代表整体，无需分别对每组再进行采样和汇总，直接完整选取几组即可。
$$
S = k * s
$$

  • S 样本总合
  • k 族类个数
  • s 每个族类数量大小

在选择合适业务场景的采样算法后，样本容量的确定也理性的思考。其中以下3种问题需要在采样中尽量避免：

  1. 样本总量过小
  2. 幸存者偏差
  3. 概率偏见

选择合理的样本容量时，可以参考以下方案：

  1. 通过置信度，置信区间，总体数量，计算样本数。
  2. 通过置信度，总体数量，样本数量，采样比例，计算置信区间。

本文结尾处将提供在线计算器，以便于简化计算。

置信度 (Confidential Level)：指总体参数值落在样本统计值某一区内的概率，一般用1-α表示。
置信区间(Confidential Interval)：指在某一置信度下，样本统计值与总体参数值间误差范围。置信区间越大，置信水平越高。
边际误差 (Margin of Error)：边际误差描述结果与实际总体值相差的百分比。例如 95% 的置信区间与 5% 的边际误差代表统计数据在 95% 的时间内统计数据与实际值偏差在 5% 以内。

实现方案

简单随机采样

通过Spark实现随机采样较为简单，使用Dataset自带API即可：

1
2
3
4
def sample(fraction: Double): Dataset[T]
def sample(fraction: Double, seed: Long): Dataset[T]
def sample(withReplacement: Boolean, fraction: Double): Dataset[T]
def sample(withReplacement: Boolean, fraction: Double, seed: Long): Dataset[T]
  • fraction: 范围在 0.0 到 1.0 之间，从原始数据集中提取大致百分比的样本数，非精确。
  • seed： 如传值相同，则同数据集，多次采样结果相同。
  • withReplacement：是否放回；如可放会，则样本集中可能出现完全相同记录。

在Apache Hive中，有2种方式可以实现随机采样，但不一定100%与Spark中效果一致。

首先可以选择 TABLESAMPLE 函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
-- 随机选取 N 行 (每个InputSplit)
SELECT id, col1, col2, dat3
FROM db.your_table 
TABLESAMPLE(10 ROWS);

-- 随机选取 N % 数据 
SELECT id, col1, col2, dat3
FROM db.your_table 
TABLESAMPLE(20 PERCENT);

-- 随机选取 N Mb 数据 (B, K, M, G)
SELECT id, col1, col2, dat3 
FROM db.your_table 
TABLESAMPLE(30M);

需要注意，TABLESAMPLE 为数据块采样，传递百分比是基于整个数据块大小，非数据总行数；而传递具体行数，则是在加载数据时，将其应用在每个 InputSplit 上 (InputSplit是MapReduce中的概念，可参考此文章)。可通过set hive.sample.seednumber 改变随机区块。

其次，也使用普通Hive SQLQuery，利用 DISTRIBUTE BY 和 SORT BY 搭配 RAND() 函数进行精确限定数据量的随机采样。

1
2
3
4
5
6
7
8
9
10
SELECT id, col1, col2, dat3 
FROM db.your_table 
DISTRIBUTE BY RAND() 
SORT BY RAND() 
LIMIT 10;
-- 若 distribute by & sort by column 相同，则可以直接使用cluster by
SELECT id, col1, col2, dat3 
FROM db.your_table 
CLUSTER BY RAND() 
LIMIT 10;
  • rand() 函数同样有支持 **seed **的重载版 rand(int seed)，传递相同数值则每次采样结果一致。

注意：全表随机采样时尽量不要使用 ORDER BY！否则将对全表排序，耗时较高 (ORDER BY只有一个Reducer负责处理)。

分层采样

实现无放回式分层采样，可以借助 Spark DataFrameStatFunctions 中 sampleBy 方法。

1
def sampleBy[T] (col: String, fractions: Map[T, Double], seed: Long): DataFrame
  • col：数据集中被用于分层的列。
  • fractions：每层采样比例，Key为目标类别，Value为对应比例 (0.0 ~ 1.0)。需先对数据类别和量级有大致了解，才可以均衡样本。
  • seed：如传值相同，则同数据集，多次采样结果相同。

在 Apache Hive 中，可以利用 Window Function 搭配 row_number() 和 rand() 实现。例如以下按照 layer 分层，再随机取每层 10% 数据：

1
2
3
4
5
6
7
8
9
WITH stratify_and_rand AS (
    SELECT id, col1, col2, dat3, layer,
        COUNT(*) OVER ( PARTITION BY layer ) AS layer_cnt,
        ROW_NUMBER() OVER ( PARTITION BY layer ORDER BY RAND() ) AS layer_rnk
    FROM db.your_table
)
SELECT id, col1, col2, dat3, layer
FROM stratify_and_rand
WHERE layer_rnk <= layer_cnt * 0.1;

上述方式也支持限制总样本数，通过 layer_cnt / total * sample_size.

其他

由于篇幅因素，本文不再一一描述其他采样算法，但最后值得一提的是，Hive支持一种独特的分桶采样。

1
2
3
SELECT id, col1, col2, dat3 
FROM  db.your_table 
TABLESAMPLE (BUCKET x OUT OF y [ON id])

上述语句用意为将 id 随机分配到y个桶中，并返回每个桶中x行数据。

如果将上述分桶采样运用于已分桶的表 (建表时运用CLUSTERED BY) 且采样字段和分桶字段匹配， 则 TABLESAMPLE 仅扫描表中所需的哈希分区，避免全表扫描。

技术总结

使用Spark Dataframe自带API和HiveQL均可以分别实现包括随机采样、分层采样、系统采样、聚类采样在内不同种采样算法。不过，在Spark中，既可以调用自带API，又可以灵活搭配Spark SQL，扩展性上往往高于普通Hive SQL。在实际业务场景中，尤其当面临更复杂的数据和采样算法，还需要权衡集成难度、计算效率、计算成本等多方因素以做出最佳选择。

参考文献

  1. 采样算法简介：https://www.mathsisfun.com/data/sampling.html

  2. Hive Sampling：https://cwiki.apache.org/confluence/display/Hive/LanguageManual+Sampling

  3. 采样比例计算器： https://www.calculator.net/sample-size-calculator.html

  4. 聚类采样分析：https://stattrek.com/survey-research/cluster-sampling-analysis

  5. 正态分布：https://www.scribbr.com/statistics/normal-distribution

  6. 泊松分布：https://www.scribbr.com/statistics/poisson-distribution

  7. Z-Table：https://cdn.scribbr.com/wp-content/uploads/2023/02/z-table-Scribbr.pdf