Sampling：Uniform、Reservoir 与 Stratified Sampling 教程

SamplingUniform、Reservoir 与 Stratified Sampling 教程在统计学、机器学习和大数据处理中我们经常无法或没有必要使用全部数据。这时就需要从总体中抽取一部分具有代表性的数据进行分析这个过程称为Sampling采样。本文重点介绍三种经典采样技术Uniform SamplingReservoir SamplingStratified Sampling1. Population 与 SamplePopulation总体指我们真正关心的全部数据。例如某大学全部学生 某网站一天产生的全部访问日志 某工厂一年生产的全部产品Sample样本则是从 Population 中抽取出来的一部分数据。例如Population: 20000 名学生 ↓ Sampling ↓ Sample: 500 名学生Sampling 的目标不是单纯减少数据而是让较小的 Sample 尽可能代表较大的 Population。2. 为什么需要 Sampling常见原因包括2.1 数据规模太大例如100,000,000 条日志直接处理全部数据可能带来计算成本高 内存占用大 训练速度慢因此可以先抽取一部分样本进行分析或模型实验。2.2 数据持续不断到来例如实时日志 传感器数据 网络流量 消息队列这种数据可能没有明确终点因此不能等全部数据到齐后再采样。2.3 总体内部存在不同群体例如普通用户 90% 高级用户 9% VIP 用户 1%如果直接随机抽样小类别可能抽得太少因此需要分层采样。3. Uniform SamplingUniform Sampling 可以理解为总体中的每个元素具有相同的被选中机会。假设总体大小为 N需要抽取 k 个不重复样本则任意元素进入样本的概率为P(xi∈S)kNP(x_i\in S)\frac{k}{N}P(xi​∈S)Nk​4. Uniform Sampling 的直观理解假设有 100 名学生现在随机抽取 10 人。如果使用 Uniform Sampling那么学生 1 学生 2 ... 学生 100每个人都有同样的机会被选中。因此可以简单理解为所有数据放在一起 ↓ 公平随机抽取5. 放回采样与不放回采样5.1 Without Replacement不放回采样。A B C D E如果已经抽到 C则 C 不会再次被选中。例如C A E不会出现C C A5.2 With Replacement放回采样。每次抽取完成后元素重新回到总体因此同一个元素可能被多次抽中。例如C A C这种方式常见于BootstrapBaggingRandom Forest6. Python 实现 Uniform Sampling使用 NumPyimportnumpyasnp populationnp.arange(1,101)samplenp.random.choice(population,size10,replaceFalse)print(sample)其中replaceFalse表示不放回采样。如果设置replaceTrue则表示放回采样。也可以使用 Python 标准库importrandom populationlist(range(1,101))samplerandom.sample(population,10)print(sample)7. Uniform Sampling 的优点和问题优点简单直观实现容易每个元素机会相同适合总体可完整访问 总体规模已知 数据分布不是特别不平衡问题在于它不能保证每个子群体都被充分采样。例如Class A: 9500 Class B: 500抽取 100 个样本时理论上 B 类大约有 5 个但实际可能只有 1 个甚至 0 个。8. Reservoir SamplingReservoir Sampling 通常翻译为蓄水池采样它解决的问题是当数据以 Stream 形式不断到来而且不知道最终总量 N 时如何始终保留 k 个等概率随机样本例如日志不断进入 1 2 3 4 5 ... ?我们不知道最终会有多少条数据但仍希望保存一个固定大小的随机样本集合。9. Reservoir Sampling 的基本过程假设需要保存k 5个样本。数据流1 2 3 4 5 6 7 8 ...首先直接保存前 5 个Reservoir [1, 2, 3, 4, 5]对于之后第 i 个元素在 1 到 i 之间随机生成一个整数 j如果 j k则用当前元素替换 Reservoir 中的一个元素否则丢弃当前元素。例如当前 Reservoir: [1, 2, 3, 4, 5] 第 6 个元素到来: 6 随机得到: j 3因为3 5所以替换第 3 个位置[1, 2, 6, 4, 5]10. Reservoir Sampling 的伪代码reservoir first k items for i k1 ... N: j random integer in [1, i] if j k: replace one reservoir item它最重要的性质是P(xi∈Reservoir)kNP(x_i\in Reservoir)\frac{k}{N}P(xi​∈Reservoir)Nk​也就是说即使数据以流式方式到来最终每个元素被保留的概率仍然相同。11. Reservoir Sampling 为什么节省内存如果一共有 N 条数据普通方法可能需要O(N)O(N)O(N)空间。Reservoir Sampling 只保存 k 条数据因此空间复杂度为O(k)O(k)O(k)当N 非常大 k 很小时这个优势非常明显。12. Python 实现 Reservoir Samplingimportrandomdefreservoir_sampling(stream,k):reservoir[]fori,iteminenumerate(stream):ifik:reservoir.append(item)else:jrandom.randint(0,i)ifjk:reservoir[j]itemreturnreservoir使用streamrange(1,1000001)samplereservoir_sampling(stream,10)print(sample)即使输入有 1,000,000 条数据也只需要维护 10 个样本。13. Reservoir Sampling 的适用场景适合Streaming DataOnline Learning实时服务器日志传感器数据网络流量Kafka 等消息流无法提前知道数据总量无法保存完整数据集可以简单记忆Reservoir Sampling 数据不断来 不知道 N 只保留固定 k 个样本14. Stratified SamplingStratified Sampling 通常翻译为分层采样其核心思想是先把 Population 按重要属性划分成多个 Stratum再分别从每个 Stratum 中采样。例如A 类60% B 类30% C 类10%如果要抽 100 个样本可以按相同比例抽取A: 60 B: 30 C: 1015. Stratum 是什么Stratum 表示一个分层后的子群体。例如大学生总体可以按照Freshman Sophomore Junior Senior进行分层。也可以按照地区 收入水平 用户等级 产品类别 疾病类型进行分层。关键在于分层变量应该与研究目标相关。16. Proportional Stratified Sampling最常见的方法是按总体比例采样。假设Population 10000其中Class A 7000 Class B 2000 Class C 1000需要抽取Sample 1000则A 700 B 200 C 100一般公式为nhnNhNn_hn\frac{N_h}{N}nh​nNNh​​其中N表示总体大小。Nh表示第 h 层总体大小。n表示总样本数。nh表示第 h 层应该抽取的样本数。17. 为什么 Stratified Sampling 很重要假设一个数据集Normal: 99% Fraud : 1%如果随机抽取 100 条数据Fraud 理论上只有 1 条甚至可能一条都没有。这会导致少数类别无法被充分分析Stratified Sampling 可以保证重要的小类别进入 Sample。因此它非常适合Fraud Detection医疗数据Credit Risk用户分群分类机器学习任务18. Stratified Sampling 与 Train/Test Split假设数据Class 0: 800 Class 1: 200如果普通随机划分训练集和测试集中的比例可能发生明显变化。使用 Stratified Split 后可以尽量保持Train: 80% Class 0 20% Class 1 Test: 80% Class 0 20% Class 1在 scikit-learn 中fromsklearn.model_selectionimporttrain_test_split X_train,X_test,y_train,y_testtrain_test_split(X,y,test_size0.2,stratifyy,random_state42)关键参数stratifyy表示保持目标类别比例。19. pandas 中的 Stratified Sampling假设 DataFrame 中存在class列sample(df.groupby(class,group_keysFalse).apply(lambdax:x.sample(frac0.1)))意思是每个 class 分别抽取 10%。这样可以较好地保持类别比例。20. Uniform 与 Stratified 的区别假设总体A: 90% B: 10%Uniform Sampling全部数据混在一起随机抽结果可能是A: 93% B: 7%Stratified Sampling先按 A/B 分组 再分别抽取结果更容易保持A: 90% B: 10%21. 三种 Sampling 方法对比方法是否需要知道总体大小是否适合 Streaming是否保持群体比例典型用途Uniform Sampling通常需要否否普通随机抽样Reservoir Sampling不需要是否流式数据Stratified Sampling通常需要通常否是类别不平衡22. 三种方法的直觉记忆Uniform Sampling所有数据站在一起 ↓ 随机抽重点Equal ProbabilityReservoir Sampling数据不断从门口经过 ↓ 只能保留 k 个 ↓ 不断随机替换重点Streaming Unknown NStratified Sampling先分组 ↓ A组 B组 C组 ↓ 每组分别抽重点Preserve Groups23. Sampling Bias无论使用什么采样方法都需要避免Sampling Bias采样偏差Sampling Bias 指采样方式本身导致某些数据更容易进入样本。例如想调查居民运动习惯但只在健身房进行问卷调查。那么结果会系统性偏向喜欢运动的人。因此Random并不自动意味着Representative采样设计本身仍然非常重要。24. Sampling 在 Machine Learning 中的应用Sampling 几乎贯穿整个机器学习流程。Train/Test SplitDataset ↓ Sampling ↓ Train / TestMini-batch SGDDataset ↓ 抽取 Batch ↓ 计算 GradientRandom Forest使用Bootstrap Sampling Feature SamplingImbalanced Learning常见Under-sampling Over-sampling Stratified Sampling25. 综合例子假设一个网站每天产生10,000,000条访问日志。用户类型Free 90% Premium 9% Enterprise 1%如果只是做普通随机分析Uniform Sampling比较合适。如果日志持续实时进入而且不能完整保存Reservoir Sampling更合适。如果重点研究不同用户等级Stratified Sampling更合适。26. 最终总结Sampling 的目标是用更小的 Sample 尽可能代表更大的 Population。三种方法分别解决不同问题。Uniform Sampling 所有人一起随机抽Reservoir Sampling 数据不断来边走边抽Stratified Sampling 先分组再分别抽最值得记住的是Uniform → Equal Probability Reservoir → Streaming Unknown N Stratified → Preserve Group Structure