大数据量情况下计算分位数的增量式方法

Question

我需要为一组大量的数据计算分位数。

假设我们只能通过某些部分（例如大矩阵的一行）获取数据。要计算Q3分位数，需要获取所有数据部分并将其存储在某个地方，然后对其进行排序并计算分位数：

List<double> allData = new List<double>();
// This is only an example; the portions of data are not really rows of some matrix
foreach(var row in matrix) 
{
    allData.AddRange(row);
}

allData.Sort();
double p = 0.75 * allData.Count;
int idQ3 = (int)Math.Ceiling(p) - 1;
double Q3 = allData[idQ3];

我希望找到一种在不使用中间变量存储数据的情况下获取分位数的方法。最好的解决方案是计算第一行的一些中间结果参数，然后逐步调整下一行。

注意：

这些数据集非常大(每行约5000个元素)。

Q3可以估计，不必是精确值。

我将数据的部分称为“行”，但它们的长度可能不同!通常变化不大(±几百个样本)，但会有所变化!

这个问题类似于“在线”(迭代器)算法用于估计统计中位数、模式、偏度和峰度, 但我需要计算分位数。

此外，这个主题中还有一些文章，例如: 一个近似中位数选择问题的有效算法 大规模跟踪的增量分位数估计 在尝试实现这些方法之前，我想知道是否还有其他更快的计算0.25/0.75分位数的方法?

- Gacek

---

你想搜索用于分位数计算的在线/流式算法。很多文献都是基于数据库研究的动机。 - Ron

请查看此线程：http://stats.stackexchange.com/questions/7959/algorithm-to-dynamically-monitor-quantiles/70905 - Quartz

Answer 1

我赞同使用桶的想法。不要将自己限制在100个桶内，最好使用100万个。关键是选择桶的范围，以避免所有数据都落入单个桶中。估算桶的范围可能的最佳方法是对数据进行合理的随机抽样，使用简单排序算法计算10%和90%分位数，然后生成等大小的桶以填充该范围。虽然这不是完美的，但如果您的数据不是来自超级奇怪的分布，它应该可以工作。

如果您无法进行随机抽样，则会更麻烦。您可以根据预期的数据分布选择初始桶猜测，然后在处理数据时，如果任何一个桶（通常是第一个或最后一个桶）过度填满，请重新选择新的桶范围。

- Keith Randall

Answer 2

有一个更新的、更简单的算法可以提供非常好的极值分位数估计。

基本思想是在极值处使用较小的箱子，既限制了数据结构的大小，又保证了小或大 q 的更高精度。该算法可用于多种语言和许多软件包中。MergingDigest 版本不需要动态分配...一旦 MergingDigest 实例化，就不需要进一步的堆分配。

请参阅 https://github.com/tdunning/t-digest

- Ted Dunning

Answer 3

受这个答案的启发，我创建了一个相当不错的估计分位数的方法。对于我的目的来说，这是足够接近的近似值。

思路如下：0.75分位数实际上是所有高于全局中位数的值的中位数。同样地，0.25分位数是所有低于全局中位数的值的中位数。

因此，如果我们可以近似中位数，我们可以以类似的方式近似分位数。

double median = 0;
double q1 = 0;
double q3 = 0;
double eta = 0.005;

foreach( var value in listOfValues) // or stream, or any other large set of data...
{
    median += eta * Math.Sign(p.Int - median);
}
// Second pass. We know the median, so we can count the quantiles.
foreach(var value in listOfValues)
{ 
    if(p.Int < median)
        q1 += eta*Math.Sign(p.Int - q1);
    else
        q3 += eta*Math.Sign(p.Int - q3);
}

备注：

• 如果您的数据分布很奇怪，您需要使用更大的eta来适应这些奇怪的数据。但是准确性会降低。
• 如果分布很奇怪，但您知道集合的总大小（即N），则可以通过以下方式调整eta参数：在开始时将eta设置为接近某个大值（例如0.2）。随着循环的进行，降低eta的值，以便在接近集合末尾时，eta将接近于0（例如，在循环中计算它：eta = 0.2 - 0.2*(i/N);

- Gacek

Answer 4

q-digest是一种近似的在线算法，可以让您计算分位数：http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf

这里有一个实现：

https://github.com/airlift/airlift/blob/master/stats/src/main/java/io/airlift/stats/QuantileDigest.java

- Haozhun

Answer 5

1. 只检索您真正需要的数据--即用作排序键的任何值，而不是与其关联的其他所有内容。
2. 您可以使用Tony Hoare的选择算法来更快地找到您的分位数，而不是对所有数据进行排序。

- Jerry Coffin

Answer 6

如果你的数据符合高斯分布，那么你可以从标准偏差中估计分位数。我假设你的数据不符合高斯分布，否则你只需使用标准偏差。

如果你可以通过两次数据传递，我建议你执行以下操作：

• 第一步，计算最大值、最小值、标准偏差和平均值。
• 第二步，将范围[min，max]划分为某些桶（例如100个）; 对于(mean-2*SD, mean+2*SD)也做同样的操作（对于异常值有额外的桶）。然后再次运行数据，将数字丢入这些桶中。
• 计算桶的数量，直到你到达数据的25％和75％。如果你想要变得更加精密，可以在桶值之间进行插值。（例如，如果您需要10％的桶以达到25个分位数，请假定该值是从低边界到上边界的距离的10％）

这应该给你一个相当不错的线性时间算法，适用于大多数非完全反常的数据集。

- Rex Kerr