在线算法计算绝对偏差

Question

我试图在线计算向量的绝对偏差,也就是说,在接收向量中的每个项目时,不使用整个向量.绝对偏差是向量中每个项目与均值之间的绝对差值的总和:

我知道矢量的方差可以用这种方式计算.方差类似于绝对偏差,但每个差异是平方的:

方差的在线算法如下:

n = 0
mean = 0
M2 = 0

def calculate_online_variance(x):
    n = n + 1
    delta = x - mean
    mean = mean + delta/n
    M2 = M2 + delta*(x - mean)  # This expression uses the new value of mean
    variance_n = M2/n
    return variance_n

是否有这样的算法来计算绝对偏差？我自己不能制定一个递归定义,但更聪明的头可能会占上风!

Answer 1

由于x和均值之间的绝对偏差可以定义为平方差的平方根,如果您对一致但有偏差的估计(意味着无穷大的极限是预期值)感到满意,则自适应是微不足道的:

n = 0
mean = 0
M2 = 0

def calculate_online_avg_abs_dev(x):
    n = n + 1
    delta = x - mean
    mean = mean + delta/n
    M2 = M2 + sqrt(delta*(x - mean))  
    avg_abs_dev_n = M2/n 

这是针对平均绝对偏差的情况.通常使用mad(中位数绝对偏差),这是不可能递归编程的.但在大多数情况下,平均绝对偏差是有用的.当我们谈论接近正态分布的数百个值时,两个值都非常接近.

如果你只想要绝对偏差的总和,生活就更简单了:只需返回M2.

请注意这样一个事实,即您给出的算法和对绝对偏差的微不足道的适应性略有偏差.

R中的模拟证明算法以这种方式工作:

红线是真值,黑线是遵循上述算法的渐进值.

代码:

calculate_online_abs_dev <- function(x,n){
  M2=0
  mean=0
  out <- numeric(n)
  for(i in 1:n) {
      delta <- x[i] - mean
      mean <- mean + delta/i
      M2 = M2 + sqrt(delta*(x[i] - mean))
      out[i] <- M2/i

  }
  return(out)
}

set.seed(2010)
x <- rnorm(100)

Abs_Dev <- calculate_online_abs_dev(x,length(x))
True_Val <- sapply(1:length(x),function(i)sum(abs(x[1:i]-mean(x[1:i])))/i)

plot(1:length(x),Abs_Dev,type="l",xlab="number of values",lwd=2)
lines(1:length(x),True_Val,col="red",lty=2,lwd=2)
legend("bottomright",lty=c(1,2),col=c("black","red"),
  legend=c("Online Calc","True Value"))

Answer 2

我认为这是不可能的。

在方差公式中，可以将 x 和 x ²项分开，这样就足以跟踪这些总和（和 n）。在绝对偏差的公式中这是不可能的。

我认为最好的办法（除了保留整个向量并根据需要计算绝对偏差）是保留一个排序的元素列表。对于每个新元素，这是 O(log(n))，但是添加元素后，重新计算绝对偏差的成本是 O(log(n))。这可能值得也可能不值得，具体取决于您的应用程序。