如何在不存储列表的情况下计算或近似列表的中位数

我正在尝试计算一组值的中位数,但我不想存储所有值,因为这可能会破坏内存需求.有没有一种计算或近似中位数的方法,而不存储和排序所有单个值？

理想情况下,我想编写我的代码,如下所示

var medianCalculator = new MedianCalculator();
foreach (var value in SourceData)
{
  medianCalculator.Add(value);
}
Console.WriteLine("The median is: {0}", medianCalculator.Median);

我只需要实际的MedianCalculator代码!

更新:有些人问我正在尝试计算中位数的值是否具有已知属性.答案是肯定的.一个值从约-25到-0.5以0.5为增量.另一个也是从-120到-60的0.5增量.我想这意味着我可以为每个值使用某种形式的直方图.

谢谢

缺口

1> David Z..：

---

如果值是离散的并且不同值的数量不是太高,您可以只计算每个值在直方图中出现的次数,然后从直方图计数中找出中位数(只需从顶部和底部加总计数)直到你到达中间的直方图).或者,如果它们是连续值,您可以将它们分配到箱中 - 这不会告诉您确切的中位数,但它会给您一个范围,如果您需要更精确地知道,您可以再次遍历列表,仅检查中央垃圾箱中的元素.

2> michael..：

---

有"补救"统计数据.它首先设置k个数组,每个长度为b.数据值被输入到第一个数组中,当它满时,计算中值并将其存储在下一个数组的第一个pos中,之后重新使用第一个数组.当第二个数组已满时,其值的中位数存储在第三个数组的第一个pos等等.你明白了:)

它简单而且非常健壮.参考在这里......

http://web.ipac.caltech.edu/staff/fmasci/home/astro_refs/Remedian.pdf

希望这可以帮助

迈克尔

3> Tyler Street..：

---

我使用这些增量/递归均值和中值估计值,它们都使用常量存储:

mean += eta * (sample - mean)
median += eta * sgn(sample - median)

其中eta是一个小的学习速率参数(例如0.001),而sgn()是signum函数,它返回{-1,0,1}中的一个.

这种类型的增量平均估计似乎在所有地方都被使用,例如在无监督的神经网络学习规则中,但中位数似乎不太常见,尽管其有益(对异常值的鲁棒性).似乎在许多应用中,中值版本可以用作平均估计量的替代.

我很想看到类似形式的增量模式估算器......

(注意:我在这里也发布了类似的主题:"在线"(迭代器)算法,用于估计统计中位数,模式,偏度,峰度？)

---

该中值估计不适用于非高斯分布.想象一下,只有两个数字的分布:x看n次,x + y看n + m次.如果m或y相对较大,则估计会中断.示例:您看到100 10m + 1次,然后是1 100k次.真实中位数= 100.估计中位数= 1.

4> Pall Melsted..：

---

这是一个你可能会尝试的疯狂方法.这是流式算法中的经典问题.规则是

你的内存有限,比如你想要的物品数量O(log n)在哪里n

您可以查看每个项目,然后做出决定然后在那里做什么,如果你存储它,它会花费内存,如果你扔掉它就会永远消失.

找到中位数的想法很简单.O(1 / a^2 * log(1 / p)) * log(n)从列表中随机抽取样本元素,您可以通过储层采样(参见上一个问题)来完成.现在只需使用经典方法从采样元素中返回中值.

保证是返回的项目的索引(1 +/- a) / 2至少是概率1-p.因此存在失败概率p,您可以通过抽取更多元素来选择它.并且它不会返回中位数或保证返回的项的值是接近中位数的位置,只是当您对列表进行排序时,返回的项将接近列表的一半.

此算法使用O(log n)额外的空间并以线性时间运行.

5> SPWorley..：

---

一般来说这很难处理,特别是处理已经排序的退化序列,或者在列表的"开始"处有一堆值,但列表的末尾具有不同范围的值.

制作直方图的基本思想是最有希望的.这使您可以累积分布信息并从中回答查询(如中位数).中位数将是近似值,因为您显然不存储所有值.存储空间是固定的,因此它可以按照您拥有的任何长度顺序工作.

但是,您不能仅仅根据前100个值构建直方图并连续使用该直方图.更改数据可能会使直方图无效.因此,您需要一个动态直方图,可以动态更改其范围和容器.

制作一个有N个箱子的结构.您将存储每个槽转换的X值(总共N + 1个值)以及bin的总体.

流式传输您的数据.记录前N + 1个值.如果流在此之前结束,那么很好,您已经加载了所有值,您可以找到确切的中位数并返回它.否则使用这些值来定义第一个直方图.只需对值进行排序并将其用作bin定义,每个bin的总体数为1.可以使用dupes(0个宽度的bin).

现在流入新值.对于每一个,二进制搜索以找到它所属的bin.在常见情况下,您只需增加该容器的数量并继续.如果您的样本超出直方图的边缘(最高或最低),只需扩展结束仓的范围以包含它.当您的流完成后,您可以通过找到其两侧具有相等总体的bin来找到中值样本值,并线性插值剩余的bin宽度.

但这还不够......你仍然需要将直方图ADAPT到数据流中.当一个bin过满时,你会丢失有关该bin子分布的信息.您可以通过基于某种启发式进行调整来解决这个问题...最容易和最强大的一个是如果一个bin达到某个特定的阈值总体(类似于10*v/N,其中v =到目前为止在流中看到的值的数量,并且N是垃圾箱的数量,你拆分垃圾桶.在bin的中点添加一个新值,给每个原始bin的人口一半.但是现在你有太多的垃圾箱,所以你需要删除一个垃圾箱.一个好的启发式方法是找到人口和宽度最小的bin.删除它并将其与其左或右邻居合并(无论哪个邻居本身具有最小的宽度和总体积.).完成!请注意,合并或拆分垃圾箱会丢失信息,但这是不可避免的..您只有固定存储空间.

这个算法非常好,因为它可以处理所有类型的输入流并提供良好的结果.如果您可以选择样本订单,那么最好随机抽样,因为这样可以最大限度地减少拆分和合并.

该算法还允许您查询任何百分位数,而不仅仅是中位数,因为您有完整的分布估计值.

我在很多地方使用这个方法在我自己的代码中,主要用于调试日志..你正在录制的一些统计数据有未知的分布.使用此算法,您无需提前猜测.

缺点是不相等的bin宽度意味着你必须对每个样本进行二进制搜索,因此你的网络算法是O(NlogN).