递增方式计算分位数大集的数据
https://stackoverflow.com/questions/2837311
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我需要计算的分位于一个大集的数据。
让我们假设我们可以得到的数据仅通过一些部分(即一个排的一个大型的矩阵)。计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];
我想找到一种方式获得的分位数没有将数据存储在一个中间可变的。最好的解决办法是以计数的一些参数的中期结果，为第一排，然后调整步骤，用于下一个行。
注：
- 这些数据集是真正的大(ca5000元素中的每一排)
- Q3可以估计，它不必是一个确切价值。
- 我呼吁部分的数据"行"，但是他们可以有不同的leghts!通常它变化不大(+/-几百个样品)，但它不同!
这个问题是相似的 "在线"(迭代)的算法，估算统计的中位数，模式，偏度，峰度, 但是我需要计算分位数.
还有几篇文章，在这个主题，即：
在尝试实施这些方针，我想知道，如果有可能的任何其他更快的方法计算的0.25/0.75分位数?
解决方案 5
灵感 这个答案 我创建了一个方法，该方法估计分位数相当好的。这是近似值足够接近我的目的。
这个想法是如下：的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);
其他提示
我第二个想法使用的桶。不要限制自己100桶-也可以使用1万美元。最棘手的部分是要拿你的水桶的范围使得一切都不会最终在一个桶。可能最好的方法来估计你的桶的范围内采取合理的随机样本数据，计算的10%和90%位数使用简单的排序的算法，然后产生大小相等的水桶来填补这一范围。它不是完美的，但是如果数据是不是从一个超奇怪的分发，它应当工作。
如果你不可以随机样品，你在更多的麻烦。你可以挑选一个最初存入桶的猜测基于预期数据分发，然后工作的同时，通过你的数据，如果任何桶(通常第一个或最后一桶)获取过多，开始了一个新的桶的范围内。
还有一个更近期的和更简单的算法为此提供了非常好的估计极端分位数.
基本的想法是，小箱是用来在极端的方式在这两个界限的大小的数据结构，并确保更高的精确度对于小型或大型q。算法可用几种语言和多的软件包。该MergingDigest版本不需要的动态分配...一旦MergingDigest化，没有进一步堆分配是必需的。
- 只是检索的数据，你真的需要--即，任何值(s)/正在使用作为关键的排序，不是其他一切与它相关联。
- 你也许可以使用托尼*霍尔的选择算法找到你的分位数的速度比排序的所有数据。
如果你的数据具有高斯分布，你可以估计分位数的标准偏差。我假设你的数据是不是高斯分布或者你只是以使用SD无论如何。
如果你可以穿过你的数据的两倍，我会做到以下几点：
- 第一个通过计算最大，分，SD和的意思。
- 第二通行证，划分的范围[min,max]成一些数量的水桶(例如100);做一样(意思-2*，意味着+2*SD)(用额外的一桶桶的异常值).然后通过运行数据的再折腾数字到这些桶。
- 最桶直到你在25%和75%的数据。如果你想获得额外的幻想，你可以插入之间的斗值。(I.e。如果你需要的10%的斗打你25分位数，假定的价值是10％的方式从低限到上限。)
这应该给你一个很好的线性时间的算法，作为最套不完全-不正当的数据。
