是否存在类Welford在线方差算法的四分位距（IQR）在线计算方法？

问题概述 #

简短版 #

Welford在线算法可在无需存储所有数据的场景（如内存受限系统）中，动态维护方差的计算值。那是否存在类似的四分位距（IQR）在线算法，不用保留全部历史数据就能获取中间50%数据的范围？

详细版 #

在内存受限场景下，维护数据的动态平均值非常简单：

• Double sum
• Int64 count
  由此可计算均值：
• mean = sum / count
  这种方式可收集数小时甚至数年的观测数据，仅占用16字节内存。

Welford方差算法 #

通常计算方差或标准差时，必须保留所有读数，因为需要对所有历史读数计算reading-mean：

Double sumOfSquaredError = 0;
foreach (Double reading in Readings)
   sumOfSquaredError += Math.Square(reading - mean);
Double variance = sumOfSquaredError / count

长期运行下数据量可达TB级，远不止16字节内存。

因此Welford提出的在线算法极具价值，它可在单次遍历中计算数据流的方差：

能够单次遍历、仅检查每个值*x_i*一次来计算方差十分实用；例如在数据收集时无足够存储空间保存所有值，或内存访问成本高于计算成本的场景。

添加新值到动态方差的算法如下：

void addValue(Double newValue) {
   Double oldMean = sum / count;
   sum += newValue;
   count += 1;
   Double newMean = sum / count;

   if (count > 1)
      variance = ((count-2)*variance + (newValue-oldMean)*(newValue-newMean)) / (count-1);
   else
      variance = 0;
}

四分位距（IQR）的在线算法？ #

四分位距（IQR）是另一种衡量数据离散程度的方法，用于表示中间50%数据的范围：

基于此通常可绘制IQR箱线图：

我们至少需要获取Q1和Q3的值。

是否无需保留所有记录数据即可计算四分位距？
换言之：

是否存在类似Welford在线方差算法的四分位距在线算法？

参考资料：Knuth《半数值算法》 #

Welford算法可在Knuth的第二卷《半数值算法》中找到相关说明：

（以防有人认为这与计算机科学或编程无关）

相关研究成果 #

• Stackoverflow：通用时间序列的简单在线异常检测算法
• Stats：通用时间序列的简单在线异常检测算法
• 《数据流的在线异常检测》（IDEAS '11：第15届国际数据库工程与应用研讨会论文集，2011年9月，第88–96页）
• Stats：金融时间序列中的鲁棒异常检测
• Stats：在线异常检测
• 《数据流中基于距离的异常检测》（《VLDB Endowment》第9卷第12期，2016年8月，第1089–1100页）
• 《数据流上的在线异常检测》（Hongyin Cui，硕士论文，2005年）

内容的提问来源于stack exchange，提问作者Ian Boyd