Онлайн алгоритм для расчета абсолютного отклонения

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 

Это для случая среднего абсолютного отклонения.Обычно используется безумный (медиана абсолютного отклонения), который невозможно программировать рекурсивно.но среднее абсолютное отклонение также полезно в большинстве случаев.Когда мы говорим о сотнях значений из распределений, близких к нормальным, оба значения очень близки.

Если вы просто хотите получить сумму абсолютных отклонений, жизнь станет еще проще: просто верните 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. Вы должны заранее рассчитать общее среднее значение для этой суммы.

Редактировать: Я вижу, что бета-версия согласна со мной. ЕСЛИ вы сохранили все предыдущие точки данных в отсортированном списке, вы можете эффективно рассчитать обновленное желаемое отклонение. Но это противоречит духу вашей просьбы.

Answer 3

Я не думаю, что это возможно.

В формуле для дисперсии можно разделить термины x и x ² , чтобы их было достаточно для отслеживания этих сумм.(и н).В формуле для абсолютного отклонения это невозможно.

Я думаю, что лучшее, что можно сделать (кроме сохранения целого вектора и вычисления абсолютного отклонения по требованию), это сохранить отсортированный список элементов.Это O (log (n)) для каждого нового элемента, но после добавления элемента стоимость пересчета абсолютного отклонения составляет O (log (n)).Это может или не может быть целесообразным, в зависимости от вашего приложения.