BoxWhiskerChart画50万条WeightedData直接递归溢出，怎么降采样？

一、问题的真实边界：溢出发生在哪一层

先把现象描述准确。在 Wolfram Language 中执行类似 BoxWhiskerChart[WeightedData[vals, wts]] 的调用，当 vals 长度达到数十万，常见报错是 $RecursionLimit::reclim2 或 $IterationLimit::itlim，而不是 OutOfMemory。这个细节决定了诊断方向：问题出在求值策略而非数据体量本身。

从机制上看，WeightedData 是一个带权重的数据容器，其分位数计算需要把权重归一化为累积分布，再对目标概率做反解。当实现以模式匹配加递归方式逐段剥离数据时，递归深度与数据分段数同阶。默认 $RecursionLimit 为 1024（不同版本略有差异），一旦分段策略把 5×10⁵ 个点切成上千段递归处理，溢出几乎必然发生。笔者认为，这正是“数据量不大却报递归错”的典型症状：内存还远未耗尽，调用栈先撑破了。

需要区分三个层次：统计层（分位数、四分位距、须线端点如何定义）、求值层（符号表达式如何被重写与递归展开）、内存层（打包数组与符号列表的驻留差异）。多数网络讨论把三者混为一谈，给出的“增大 $RecursionLimit”方案只治标：把限制从 1024 提到 10⁵ 往往能让图出来，但求值时间呈超线性增长，且下一次样本翻倍又会复现。

本文评述：把递归溢出当作“参数没调好”是一种误诊。真正的工程信号是——绘图函数不应承担大规模统计聚合的职责。降采样的目标不是让图能画出来，而是让统计量的计算复杂度与样本量解耦。

一个可验证的判别方法是：先单独计算 Quantile[wd, 0.25] 与 Quartiles[wd]。若这两步已经触发递归限制，问题在统计层；若它们正常而绘图报错，问题在绘图的符号预处理。实践中前者更常见，因为绘图内部同样调用分位数逻辑，只是多包了一层。关于 Wolfram 语言求值顺序与递归限制的官方说明，可参考 $RecursionLimit 文档 与 WeightedData 文档。

二、加权箱线图的统计量定义与可加性分析

2.1 加权分位数的准确定义

设样本为 (xi, wi)，i = 1..n，权重非负且总和为 W。加权经验分布函数定义为 F(t) = (Σ wi · 1{xi ≤ t}) / W。加权 p 分位数是 inf{t : F(t) ≥ p}。这个定义本身是单调可加的：若把数据分成若干块，各块的加权累积和可以直接相加得到全局累积和。

但“可加”不等于“可分块独立求分位数再合并”。分位数不是线性统计量，Quantile(A∪B, p) ≠ f(Quantile(A,p), Quantile(B,p))。这是降采样设计中最容易踩的坑：把 50 万条切成 50 块、每块求四分位数再平均，得到的不是全局四分位数，误差在分布偏斜时可达数十个百分点。本文评述：正确的分块对象是排序后的加权累积分布或直方图桶计数，而不是分位数本身。

2.2 须线端点的两种语义

经典 Tukey 箱线图的须线延伸到“1.5 倍四分位距内的最远观测点”，即 [Q1 − 1.5·IQR, Q3 + 1.5·IQR] 区间内实际存在的极值。另一种常见实现直接画到该区间的边界（不裁剪到观测点）。两者在重尾分布下差异显著：前者须线长度依赖样本极值，后者只依赖分位数。

加权情形下这个歧义被放大。权重可以理解为“该观测值代表多少个重复样本”，于是须线端点应取加权意义下的极值——即累积权重跨过阈值处的观测值。Wolfram 的 BoxWhiskerChart 对 WeightedData 的处理在文档中并未逐条展开，工程上应以实测为准。笔者建议在降采样前先明确采用哪种语义，因为不同语义对降采样的敏感度完全不同：分位数语义对近似算法友好，极值语义则对尾部采样极其敏感。

这张表确立了全文的分析主线：降采样必须保留“可合并的充分统计量”，而不是保留“看起来像原数据”的子集。凡是能写成加权累积和形式的量，都可以精确降采样；凡依赖全局排序或尾部极值的量，只能近似或需要额外结构。后续三条路线正是围绕这条主线展开。

三、路线一：分块聚合的精确降采样

3.1 核心思路：把样本压成加权直方图

既然分位数依赖全局累积分布，而累积分布可以由直方图桶计数精确重建（在桶宽分辨率内），那么降采样的正确形态就是：把 50 万个点聚合成几千个桶的加权直方图，再在桶上计算分位数。桶的权重是该桶内所有点权重之和。这一过程对加权总和、加权均值是精确的；对分位数，误差上界由桶宽决定。

关键参数是桶数与桶边界策略。等宽桶实现简单但对方差大的数据分辨率不均；等频桶（每桶权重相近）能让分位数附近的桶更细。工程上推荐两阶段：先用等宽桶做粗分，再在 Q1、Q3 附近 ±0.1 分位范围内用等频桶细分。这样桶总数控制在 2000–5000，内存占用从 50 万×16 字节量级降到几十 KB，且分位数误差可压到 10⁻⁴ 相对量级。

(* 两阶段加权直方图降采样，示意代码 *)
coarseBins = 1024;
h1 = HistogramList[vals, coarseBins, "PDF"];
(* 用权重累加到桶 *)
bucketWeights = Total /@ BinLists[wts, {h1[[1]]}];
(* 在 Q1/Q3 邻域细分，此处省略边界重算 *)
fine = HistogramList[vals, 4096, "PDF"];
(* 在桶上做加权累积，反解分位数 *)
cum = Accumulate[bucketWeights]/Total[bucketWeights];
q1 = h1[[1, First@FirstPosition[cum, _?(# >= 0.25 &)]]];

需要强调：上面代码是示意，实际实现中 BinLists 对 50 万点仍会产生大量中间列表，反而可能触发内存问题。更稳妥的做法是用 UnitStep 或 Clip 把每个点映射到桶索引，再用 SparseArray 或 Total 按索引聚合，避免生成嵌套列表。本文评述：在 Wolfram 语言里，“向量化索引 + 稀疏累加”比“分组再计算”更省内存，这是由表达式求值模型决定的。

3.2 桶宽与误差的定量关系

设桶宽为 h，数据在桶内近似均匀，则分位数的最大误差不超过 h（在取值域上）。若关心相对误差，则需 h ≤ ε·|Qp|。对 50 万条、取值域跨度 10³ 的数据，4096 个等宽桶给出 h ≈ 0.24，在 Q1 约为 100 时相对误差约 0.24%。这个量级对箱线图可视化完全足够，因为像素级分辨率远低于此。

但须线端点若采用极值语义，桶聚合会丢失桶内极值。补救办法是在聚合时额外记录每桶的 Min 与 Max，以及对应权重。这样全局极值可由桶级极值再取极值精确恢复，代价是每桶多存两个数。这是一个典型的“充分统计量”设计：桶计数 + 桶内极值 + 桶内权重和，足以重建箱线图全部要素（在桶宽分辨率内）。

3.3 分块大小的经验公式

如果不想一次性构造直方图，而是流式分块处理，块大小 B 的选择要同时满足两个约束：单块求值不触发递归限制（B 远小于 $RecursionLimit 对应的分段数），且块数 n/B 不导致合并开销过大。经验上取 B ≈ 104，50 万条即 50 块，合并时只需对 50 个直方图做桶级相加，复杂度 O(块数 × 桶数)，完全可控。若数据有强时间局部性（如按时间排序的日志），分块还会天然保留局部结构，便于后续做分组箱线图。

四、路线二：加权分位数草图与误差上界

4.1 从 Greenwald-Khanna 到加权变体

Greenwald-Khanna（GK）草图是流式分位数估计的经典方法，核心是维护一组带误差界的元组 (v, g, Δ)，其中 v 是观测值，g 是自上次压缩以来的秩增量，Δ 是秩误差上界。空间复杂度 O((1/ε)·log(εn))，对 ε = 0.001、n = 5×105，草图规模约数千元组，远小于原始数据。

加权变体的处理方式有两种：一是把权重展开为重复计数（权重为整数时精确，但可能爆炸）；二是把 g 的增量改为权重增量，误差界相应按权重归一化。后者是工程上可行的路线，但需要重新推导压缩条件。本文评述：加权 GK 草图的公开实现较少，若团队没有精力做正确性验证，路线一（直方图聚合）在 50 万量级上更稳妥，因为它的误差来源单一且可解释。

4.2 t-digest 与加权累积

t-digest 通过限制每个质心（centroid）覆盖的累积权重比例来保证尾部精度，特别适合箱线图这种关心 Q1/Q3 与尾部的场景。其压缩参数 δ（compression）控制质心数量，典型取值 100–1000。加权版本直接把权重累加到质心权重，合并两个 digest 时按权重归并质心，天然支持分块并行。

误差方面，t-digest 在极端分位数（如 0.001 与 0.999）的相对误差通常优于 GK，但在中位数附近两者相当。对箱线图而言，Q1、Q3 属于中等分位，t-digest 的优势主要体现在须线端点若用分位数近似时的尾部稳定性。需要提醒：t-digest 的误差界是经验性的，缺乏 GK 那样的严格最坏情况保证。笔者认为，若图表用于对外报告且需可审计，应优先选择有确定性误差界的方案，或对近似结果做一次精确校验。

五、路线三：分层抽样与须线语义的取舍

如果目标不是精确复现统计量，而是“让图看起来对且计算快”，分层抽样是第三条路。做法是按某个协变量（如时间、类别、权重分位）分层，每层抽取固定数量样本，再合并。分层抽样的方差通常低于简单随机抽样，但前提是分层变量与目标统计量相关。若分层不当，反而引入偏差。

对加权数据，抽样必须尊重权重：高权重点应更高概率被抽中，或按权重做系统抽样。一个实用技巧是按权重累积和做等距抽样：计算权重前缀和，在 [0, W] 上取等距点，每个点落在哪个观测的权重区间就选哪个观测。这样抽出的子样本在加权意义下近似均匀，且保留了尾部高权重点。

但抽样路线的根本局限在于：它无法保证分位数的确定性误差界。同一份数据跑两次可能得到略有差异的 Q1。对交互式探索可以接受，对自动化报告则不合适。本文评述：三条路线应按用途分层——对外报告用直方图聚合（确定性）、交互探索用 t-digest（快）、统计推断用分层抽样（可算置信区间），而不是追求一条“万能”方案。

关于流式分位数算法的工程实现与复杂度对比，可参考 VLDB 2022 关于分位数摘要的综述；t-digest 原始论文与参考实现见 arXiv:1902.04080。

六、工程落地：参数、验证与常见陷阱

6.1 一条可复现的操作路径

把上述分析收敛成步骤，便于直接落地。以下步骤假设数据已在内存中为两个打包数组 vals 与 wts，长度 5×10⁵。

1. 确认溢出层：先单独跑 Quartiles[WeightedData[vals,wts]]，记录是否报递归错与耗时。
2. 构造桶索引：用 Rescale 把 vals 映射到 1..K 的整数索引，K 取 4096。
3. 稀疏累加：用 SparseArray 按索引累加权重，得到桶权重向量；同时用 GroupBy 或 MinMax 记录桶内极值。
4. 反解分位数：对桶权重做 Accumulate 归一化，用 FirstPosition 找跨过 0.25/0.5/0.75 的桶，线性插值得到分位数。
5. 构造须线：按选定语义，用桶内极值与分位数计算端点；若用极值语义，从桶级极值中取满足 1.5×IQR 条件的最远值。
6. 校验：在 1 万条的子样本上对比精确分位数与桶近似分位数，确认相对误差小于 0.5%。

第 2 步的索引映射要注意边界：Rescale 后取整可能产生 0 或 K+1，需用 Clip 截断。第 3 步的稀疏累加是性能关键：SparseArray[索引 → 权重] 再 Total 按位置合并，比 BinCounts 更省内存，因为后者会生成完整桶列表。关于 SparseArray 的用法可查阅 官方文档。

6.2 常见陷阱清单

第一个陷阱是把 $RecursionLimit 调大当作解决方案。调大后求值可能成功，但耗时随样本量超线性增长，且不同版本行为不一致，不可移植。第二个陷阱是先 RandomSample 再画图：简单随机抽样会丢失尾部高权重点，导致须线变短、离群点消失，视觉上“更干净”但统计上失真。第三个陷阱是对权重做归一化后忘记还原：分位数不受权重整体缩放影响，但须线若用绝对阈值则会受影响。

还有一个容易被忽略的点：WeightedData 的权重若含零或负值，分位数定义会退化。工程上应先过滤零权重，负权重在物理上无意义，应报错而非静默处理。这类数据清洗步骤应在降采样之前完成，否则桶聚合会把异常权重混入累积和，污染全部分位数。

七、对比、局限与前沿预判

三条路线的对比已在第四节表格中给出，这里补充适用边界的判断依据。直方图聚合的局限是分辨率与内存的权衡：桶数越多越精确，但桶数超过约 10⁵ 后，桶向量本身的内存与遍历开销开始接近原始数据，降采样失去意义。因此它适合“中等精度、确定性”的场景，不适合需要 10⁻⁶ 级分位数精度的科学计算。

草图方法的局限是实现复杂度与可解释性。GK 草图的误差界推导依赖秩的整数性，加权后需重新证明；t-digest 的压缩参数对结果有可感知影响，调参经验难以文档化。本文评述：在团队规模有限时，直方图聚合的“笨办法”往往比精巧草图更可靠，因为它的每一步都能用手算验证。

前沿方向上，可关注两类工作。其一是可合并摘要（mergeable summary）在分布式环境下的标准化，例如 Apache DataSketches 对 KLL、REQ 等草图的工程封装，其设计目标就是分块计算再合并，与本文主线一致。其二是可视化感知的近似：既然箱线图在屏幕上的像素分辨率有限，是否可以按“视觉误差”而非“统计误差”来分配采样预算？已有研究探讨按显示分辨率自适应降采样，笔者认为这是把统计近似与视觉感知结合的有价值方向，但目前公开的、针对加权箱线图的系统性工作仍然稀少。

需要坦率说明本文的局限：文中未给出在特定 Wolfram 版本上的完整基准测试数据，因为不同版本的求值优化差异较大，任何单一版本的耗时数字都可能误导。读者应以第六节的验证步骤在自己的环境中复现误差与耗时，而不是直接引用本文的定性结论作为性能承诺。

八、结论与展望

回到最初的问题：50 万条 WeightedData 触发递归溢出，根因是绘图函数在符号求值层对大规模数据做了深度递归，而非数据本身无法处理。解决办法不是调大递归限制，而是把统计聚合从绘图函数中剥离，用可合并的充分统计量替代原始样本。

三条路线中，分块直方图聚合在 50 万量级上提供了最好的确定性—复杂度平衡，推荐作为默认方案；加权草图适合流式或超大规模场景，但需承担实现与验证成本；分层抽样适合探索性分析与需要置信区间的推断场景。选择的关键是先明确须线语义与误差容忍度，再匹配方法。

展望来看，加权箱线图在大数据可视化中的核心矛盾不会消失：箱线图本质上是五数概括的压缩表示，而压缩必然损失信息。工程上的成熟标志，是能清楚说出“我损失了哪部分信息、损失了多少、为什么可以接受”。这比任何单一算法都更重要。