9

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

假设我们只能通过某些部分（即大矩阵的一行）获取数据。要计算 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 分位数？

4

6 回答 6

1

我赞同使用水桶的想法。不要将自己限制在 100 个桶内——不妨使用 100 万个。棘手的部分是选择你的桶范围，这样所有东西都不会在一个桶中结束。估计存储桶范围的最佳方法可能是对数据进行合理的随机抽样，使用简单的排序算法计算 10% 和 90% 的分位数，然后生成相等大小的存储桶来填充该范围。它并不完美，但如果您的数据不是来自超奇怪的分布，它应该可以工作。

如果你不能做随机样本，那你的麻烦就更大了。您可以根据预期的数据分布选择初始分桶猜测，然后在处理您的数据时，如果任何存储桶（通常是第一个或最后一个存储桶）过满，请使用新的存储桶范围重新开始。

于 2010-05-15T00:01:41.927 回答
1

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

基本思想是在极端情况下使用较小的 bin，既限制了数据结构的大小，又保证了小或大 q 的更高准确性。该算法有多种语言和许多软件包。MergingDigest 版本不需要动态分配……一旦 MergingDigest 被实例化，就不需要进一步的堆分配。

见https://github.com/tdunning/t-digest

于 2017-02-27T09:43:04.863 回答
0

如果您的数据具有高斯分布，您可以根据标准差估计分位数。我假设你的数据不是高斯分布的，或者你只是在使用 SD。

如果您可以两次传递您的数据，我会执行以下操作：

  • 第一遍，计算最大值、最小值、SD 和平均值。
  • 第二遍，将范围 [min,max] 分成若干个桶（例如 100）；对 (mean - 2*SD,mean + 2*SD) 做同样的事情（对于异常值有额外的桶）。然后再次遍历数据，将数字扔到这些桶中。
  • 计数存储桶，直到您获得 25% 和 75% 的数据。如果你想获得额外的花哨，你可以在桶值之间进行插值。（即，如果您需要 10% 的存储桶来达到您的第 25 个分位数，则假设该值是从下限到上限的 10%。）

这应该为您提供一个非常好的线性时间算法，该算法适用于大多数非完全反常的数据集。

于 2010-05-14T21:18:11.910 回答
0
  1. 只检索您真正需要的数据——即，任何值被用作排序的键，而不是与之相关的所有其他值。
  2. 您可能可以使用 Tony Hoare 的 Select 算法来比对所有数据进行排序更快地找到分位数。
于 2010-05-14T20:26:10.790 回答
0

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

这个想法如下：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当循环通过时，当你几乎到达集合的末尾时，降低 so 的值，eta将几乎等于 0（例如，在循环中这样计算它：eta = 0.2 - 0.2*(i/N);
于 2010-05-25T14:45:37.100 回答
0

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

于 2015-10-21T16:22:04.370 回答