Quantogram - 使用直方图近似计算分位数

用于估计流式数据分位数的库

Quantogram接受一个浮点数（f64）流，可选权重，并估计所需的分位数，如中位数，同时提供其他常见度量，如计数、最小值、最大值、平均值和众数。调用者可以通过从该范围内选择所需的绝对相对误差来权衡存储和精度。

• 最低精度 = 17.2%
• 默认精度 = 1.0%
• 最高精度 = 0.034%

安装

将以下内容添加到您的Cargo.toml中

[dependencies]
quantogram = "0.4"

然后您就可以使用了。

该库需要Rust的2021版，但只是为了能够对zw-fast-quantile库进行基准测试，该库需要该版本。如果您需要2018版，可以从源代码构建并删除与ZW相关的基准测试。

发行说明

查看变更日志以获取更改：变更日志

使用方法

默认配置对于大多数使用都足够，并承诺1%的最坏情况错误率。

默认Quantogram与无权重样本

此示例创建一个默认的Quantogram，添加一些样本，并计算计数、最小值、最大值、平均值、中位数和第三四分位数（75%分位数）。它还删除了一些样本并重复计算中位数。

    use quantogram::Quantogram;
    let mut q = Quantogram::new();
    q.add(10.0);
    q.add(40.0);
    q.add(20.0);
    q.add(30.0);
    q.add(50.0);

    assert_eq!(q.count(), 5);
    assert_eq!(q.min().unwrap(), 10.0);
    assert_eq!(q.max().unwrap(), 50.0);
    assert_eq!(q.mean().unwrap(), 30.0);
    assert_eq!(q.median().unwrap(), 30.0);
    assert_eq!(q.quantile(0.75).unwrap(), 40.0);

    q.remove(10.0);
    q.remove(20.0);
    assert_eq!(q.median().unwrap(), 40.0);

使用QuantogramBuilder设置精度

此示例使用QuantogramBuilder创建一个Quantogram，将其精度设置为0.5%，批量添加样本列表，并计算中位数。

    use quantogram::{QuantogramBuilder,Quantogram};
    let mut q = QuantogramBuilder::new()
                .with_error(0.005)
                .build();
    let data = vec![10.0,40.0,20.0,30.0,50.0];
    q.add_unweighted_samples(data.iter());
    assert_eq!(q.median().unwrap(), 30.0);

处理加权样本

此示例首先添加无权重样本（权重为1），然后添加一个重量很大的零样本。

    use quantogram::{Quantogram};
    let mut q = Quantogram::new();
    let data = vec![1.0,2.0,3.0,4.0,5.0,95.0,96.0,97.0,98.0,99.0];
    q.add_unweighted_samples(data.iter());
    q.add_weighted(0.0, 6.0);
    assert_eq!(q.median().unwrap(), 2.0); 

处理数据中的间隔

如果在目标分位数所在的位置数据存在较大差距，则对差距上下方的值进行平均以获得分位数是合适的。中位数（median）和分位数（quantile）方法不会尝试这样做，但fussy_quantile方法会这样做。例如，以下序列有偶数个元素，所以中位数应该是两个中间值5和95的平均值，得到50，这个数字与集合中的任何值都相差甚远。

 Samples = { 1,2,3,4,5,95,96,97,98,99 }

    use quantogram::{Quantogram};
    let mut q = Quantogram::new();
    let data = vec![1.0,2.0,3.0,4.0,5.0,95.0,96.0,97.0,98.0,99.0];
    q.add_unweighted_samples(data.iter());
    assert_eq!(q.fussy_quantile(0.5, 2.0).unwrap(), 50.0); 

可配置内存使用

最高精度所需的存储上限是最低精度的500倍，默认精度的29倍。可以选择上述范围内的任何误差率值。

存储受每个值为2的幂的值范围被分成多少个直方图桶的影响。桶数少则结果粗糙，桶数多则结果细腻。存储与选择的桶数成正比。

增长因子表示每个桶的宽度比前一个桶呈指数增加。

例如，如果bins是35，则growth是1.02，error是1%。

要减半误差率，需要将桶数加倍（以及加倍存储）。

最大存储需求大约是这个（设置一些结构中的配置属性和跳过字典带来的开销）

storage = (2 x 8-byte floats) x (2 x 254 x (bins + 1) + 7)
        ≈ 8 kb x (bins + 1)

2 x 254表示正负值各有2个，254表示64位浮点数支持的最小和最大幅度数之间的2的幂的个数。桶数加1是因为有两个直方图，一个是只收集最近2的幂的计数的粗糙直方图，另一个是将每个2的幂分成bins个单独计数的细腻直方图。

然而，如果样本从未超过一百万，并且只记录到小数点后三位，上面的公式中的254可以减少到31。

最大存储需求范围从2个桶的25 KB到1000个桶的8.2 MB。对于默认的35个桶和1%的精度，存储最大约为300 KB。然而，如果只添加从一到一百万的正整数，这会降低到17 KB。将精度降低到5%，所需的内存减少到3.5 KB。因此，您在调整结构以实现目标时具有很大的灵活性。（更少的桶和更低的精度也会导致性能更快。）

功能

任何分位数。一些算法在开始收集数据之前要求您选择目标分位数。此结构允许查询任何分位数，且不需要配置以针对任何特定的phi范围。

极端分位数。一些算法在处理极端分位数（接近零或一的值）时精度会降低，并可能通过增加存储来补偿。《Quantogram》的精度保证适用于phi的所有值，即所需的分位数。此外，其存储需求不会为适应极端分位数而改变。

加权样本。样本可以是均匀加权的（权重=1）或分配单独的权重，以便可以计算加权中位数和加权分位数。

删除样本。可以删除样本，并且分位数将更新以反映这一点。

警告：如果删除了最小值或最大值，则后续对最小值或最大值的请求（直到添加新的极端样本）可能会返回错误值。

描述性统计。《Quantogram》提供以下基本统计信息

• 最小值
• 最大值
• 平均值
• 中位数
• 方差
• 标准差
• 分位数
• q1, q3（第一四分位数和第三四分位数）
• 众数
• hsm（半样本众数）
• 计数

备注:

1. 标准差（stddev）计算的是总体标准差，而不是样本标准差。
2. 如果只收集整数值，则众数将被四舍五入到最接近的整数。
3. 如果使用范围在 [-63,63] 内的整数值，则众数会得到良好的结果。
4. 如果收集到非整数值或此范围外的整数，则非均匀直方图分箱宽度的效应会扭曲众数，导致结果并非您所期望。分箱大小呈指数变化，因此众数将类似于样本对数的众数。这会使众数倾向于较大的值，因为较大的数字是较大分箱的一部分。
5. 大多数与使用直方图估计众数（如 Sturges 定则 和 Scott 定则）相关的经验法则使用的分箱计数远低于 Quantogram 所使用。可能最好通过合并多个相邻分箱来重新分箱，以便计算众数。
6. 作为众数的替代方案，尝试使用 半样本众数，Quantogram::hsm。它将 Robertson-Cryer（1974） 的广义 半样本众数估计器 应用于直方图数据，而不是原始样本。它已从 David Bickel 的算法推广，以应用于加权的样本。半样本众数擅长忽略异常值和污染。
7. 作为实现的 半样本众数（hsm）的性能比二次性能差（可能是 O(N² Log N)）。为了补偿这一点，已添加了一个缓存，它通常会在之前计算的众数附近的数据子集上重新计算 hsm。
   • 如果添加了此邻近区域内的新值，则将执行部分重新计算。如果 Quantogram 使用增长为 1.02 的桶（用于 1% 量化误差），则默认的 70 个桶的邻近区域覆盖范围 [1/2 x mode, 2 x mode]。如果分布有一个明确的峰值，则此核心区域通常包括新添加的样本并允许优化。
   • 如果新值位于邻近区域之外，则它们不太可能移动众数。在强制进行完整重新计算之前，允许重复使用之前计算出的众数而无需重新计算约一打样本。
   • 如果桶的数量增长过多或总权重的变化过大，则将执行完整重新计算。
   • 如果桶的数量少于 64 个，则执行完整重新计算。这可以在缓存启动之前确保数据中产生适当的准确众数。

离散度测量

实现了这些附加统计数据，它们是离散度的测量

• 范围（最小值和最大值之间的范围）
• iqr（四分位距：Q3 - Q1）
• quartile_deviation（半四分位距，iqr 的一半）
• coeff_of_range（（max - min）/（max + min））
• coeff_of_quartile_dev（（Q3 - Q1）/（Q3 + Q1））
• coeff_of_stddev（标准差除以均值）
• 变异系数

逆分位数。使用 quantile_at 函数查找给定值所在的分位数。

异常值。无穷大和 NAN 被单独计数，并且不参与分位数计算。可以查询此类值的比例。

溢出和下溢。如果无穷小值不感兴趣，下溢值可以改为将小于阈值的值视为零。同样，可以设置一个上限阈值，所有大于该阈值的值都视为无穷大（正或负）。

通过压缩记录值的动态范围，所需的存储空间更少，性能得到提升。

整数特殊处理。只要只将整数（没有分数部分的样本）添加到集合中，请求的量位数将四舍五入到最接近的整数。

稀疏桶的精确值。如果只向某个桶添加了一个值，而不是使用该桶下限和上限之间的中点值，则将使用精确的样本值。

版本 0.3.0 中的更改：如果重复添加相同的值，并且所有值都与这个准确的样本值匹配，则将保留准确的样本。将该桶的第一个不同值添加到该桶将导致使用桶的中点值。

量化算法分类

测量数据流（如中位数）的百分位数是许多应用中的基本统计数据。您可以选择

1. 准确且快速，存储要求适中，限于密集值范围，如整数
2. 准确且慢，存储要求高
3. 近似，具有概率保证的准确性、快速和低存储要求
4. 近似，具有固定保证的准确性、快速和适中存储要求

密集直方图。第一个是理想的，但适用性有限。通常使用列表作为密集直方图实现，每个桶对应一个整数值。如果所有样本都是介于零和10,000之间的整数（或者是在没有超过10,000条线的均匀网格上的浮点数），那么这是最佳选择，既容易实现又高效。

排序列表。第二个包括原始方法，即收集所有数据到一个列表中，然后排序以获取百分位数。为了加快速度，可以使用 quickselect 以避免对所有数据进行排序。这种方法不适用于流数据，因为存储要求很大。

概率算法。第三类包括（如 Count Min Sketch 的变体）保证在一定的概率下有给定的准确性。一个流行的中位数估计器称为 中位数的中位数。如果你知道将有 N 项，你可以使用 蓄水池抽样 来维护一个数据样本集，并取该样本的中位数。然而，你的百分位数越极端，你必须保留的子集就越大。使用这些算法，你通常可以得到一个好的估计，但总有可能得到一个坏的估计。另外，对于相同的数据集，你可能会得到不同的结果；答案不是确定的。

稀疏直方图。当必须处理大量不同的样本时，稀疏直方图可以用来减少与密集直方图相比的存储要求。存储的减少被更大的存储、检索和更新开销所抵消。可以使用一些巧妙的平衡树结构来实现这一点，但其中一些实现起来很复杂。你用于确定桶大小的策略会影响结果准确性。如果使用对数大小的桶，你可以保证最坏情况的绝对相对误差不会超过所需值。《Quantogram》属于这一类别。它是确定性的，并对最坏情况的准确性有精确的保证，而不是概率性的。

量化设计

摘要存储在三个级别，这使得算法可以快速定位到一个小范围的桶，其中从最小数到当前数的累积权重与所需的百分位数相匹配。

• 顶层：负数、零、正数、NANs、+/- 无穷大的总权重
• 中间层：粗计数，一个用于负数，一个用于正数，取最近的2的幂次方
• 底层：所有有限值的细计数

粗计数和细计数存储在skip maps（基于skip list构建的字典）中。它们是一个树形结构的索引，指向一个链表，其中键按顺序存储。这使得搜索、插入、更新和有序迭代变得很快。

通过使用中间层的粗计数，可以累加权重以接近分位数，并发现哪个2的幂次方范围包含分位数。然后skip map的过滤迭代器提供了快速访问细字典中该值范围的途径。

快速散列。算法的一个重要部分是如何散列样本以找到其在粗层和细层中的键。在粗层中，使用frexp获取数字的2的幂次方和符号，使用内建的数学函数而不是数学库的log。在细层中，将剩余的尾数输入到一个近似对数函数中，以获取箱号。这个近似对数使用三阶的Padé近似，其速度是数学库log的两倍。

性能

考察了两种用例，一种以插入为主，另一种以分位数计算为主。

插入密集型。向一个原始列表和一个Quantogram添加了一百万个随机值，然后取一个中位数。在发布模式下，Quantogram所需时间是原始的2.2倍，但存储量显著降低。实际上只使用了577个箱，这比原始算法使用的空间少1/866。

在插入密集型场景中，原始算法的优势明显，因为插入是它的强项，而分位数计算需要排序，但只执行一次。

分位数密集型。向一个原始列表和一个Quantogram添加了20,000个随机值，每次插入后取一个中位数。在发布模式下，Quantogram比原始方法快65倍。随着样本数量的增加，这个比率应该会进一步提高。

分析显示，大部分时间都花在了对SkipMap的操作上。

与其他Crates的比较

quantiles Crate实现了Cormode, Korn, Muthukrishnan和Srivastava的论文“Effective Computation of Biased Quantiles over Data Streams”中算法的实现。

zw-fast-quantile crate实现了张王快速近似分位数算法。

> cargo bench
...

test bench_insert_010000_qg   ... bench:   1,480,556 ns/iter (+/- 180,118)
test bench_insert_010000_ckms ... bench:   7,382,904 ns/iter (+/- 641,343)
test bench_insert_010000_zw   ... bench:     411,049 ns/iter (+/- 37,984)

test bench_insert_050000_qg   ... bench:   6,046,822 ns/iter (+/- 539,280)
test bench_insert_050000_ckms ... bench: 111,633,379 ns/iter (+/- 7,329,546)
test bench_insert_050000_zw   ... bench:   2,650,721 ns/iter (+/- 254,070)

test bench_insert_100000_qg   ... bench:  12,428,788 ns/iter (+/- 3,226,464)
test bench_insert_100000_ckms ... bench: 319,816,711 ns/iter (+/- 28,905,190)
test bench_insert_100000_zw   ... bench:   5,482,642 ns/iter (+/- 818,317)

test bench_median_001000_qg   ... bench:     495,842 ns/iter (+/- 95,352)
test bench_median_001000_ckms ... bench:     925,006 ns/iter (+/- 85,291)
test bench_median_001000_zw   ... bench:   3,809,463 ns/iter (+/- 638,667)

test bench_median_010000_qg   ... bench:   3,432,471 ns/iter (+/- 537,084)
test bench_median_010000_ckms ... bench:  37,458,360 ns/iter (+/- 4,065,758)
test bench_median_010000_zw   ... bench: 402,043,003 ns/iter (+/- 23,352,903)

test bench_median_050000_qg   ... bench:  15,898,549 ns/iter (+/- 1,154,243)
test bench_median_050000_ckms ... bench: 491,125,737 ns/iter (+/- 18,854,159)
test bench_median_050000_zw   ... bench: 7,775,610,481 ns/iter (+/- 361,052,767)

test bench_median_100000_qg   ... bench:  32,615,356 ns/iter (+/- 6,294,536)
test bench_median_200000_qg   ... bench:  64,630,098 ns/iter (+/- 8,511,129)