在线算法计算绝对偏差 [英] Online algorithm for calculating absolute deviation

问题描述

我想要计算的向量在线的绝对偏差，也就是，如在矢量的每个项目被接收时，不使用整个矢量。绝对偏差是每个项之间在载体和的绝对差的平均值的总和：

I'm trying to calculate the absolute deviation of a vector online, that is, as each item in the vector is received, without using the entire vector. The absolute deviation is the sum of the absolute difference between each item in a vector and the mean:

我知道，一个向量的方差可以以这样的方式来计算。方差是类似于绝对偏差，但每个差被平方：

I know that the variance of a vector can be calculated in such a manner. Variance is similar to absolute deviation, but each difference is squared:

在线算法变化如下：

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

有没有这样的算法，计算绝对偏差？我不能制定一个递归定义自己，但聪明的磁头可能prevail！

Is there such an algorithm for calculating absolute deviance? I cannot formulate a recursive definition myself, but wiser heads may prevail!

推荐答案

为X与平均值之间的绝对偏差可以被定义为平方差的平方根，适应是平凡的，如果你是幸福的一致，但偏估计（意为限制到无限远的预期值）：

As the absolute deviation between x and the mean can be defined as the square root of the squared difference, the adaptation is trivial if you are happy with a consistent but biased estimate (meaning the limit to infinity is the expected value) :

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 

这是对的平均绝对偏差的情况下。通常情况下，狂被使用（中位数绝对偏差），这是不可能的递归编程。但平均绝对偏差是在大多数情况下是有用的。当我们谈论数百值从贴近正态分布，这两个值非常接近。

This is for the case of the average absolute deviation. Normally the mad is used (median absolute deviation), which is impossible to program recursively. but the average absolute deviation is as useful in most cases. When we're talking about hundreds of values from close-to-normal distributions, both values are very close.

如果你只是想绝对devations的总和，生活更简单：只需返回M2

If you just want the sum of the absolute devations, life is even simpler: just return M2.

要知道的事实，无论你给的算法和琐碎调整为绝对偏差略有偏差。

Be aware of the fact that BOTH the algorithm you gave and the trivial adaptation for the absolute deviation are slightly biased.

在研发的模拟，证明该算法是这样的：

A simulation in R to prove the algorithm works this way :

红线是真值，黑线是渐进值按照上述算法。

The red line is the true value, the black line is the progressive value following the algorithm outlined above.

code：

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"))

这篇关于在线算法计算绝对偏差的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！