增量计算大量数据的分位数的方法

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分位数？

Answer 1

受这个答案的启发，我创建了一种可以很好地估计分位数的方法。对于我的目的来说，它是足够接近的近似值。

这个想法如下：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）。随着循环的进行，降低 so 的值，eta当几乎到达集合末尾时， theeta将几乎等于 0（例如，在循环中这样计算：eta = 0.2 - 0.2*(i/N);