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

Я пытаюсь вычислить абсолютное отклонение вектора online, то есть по мере поступления каждого элемента в векторе, без использования всего вектора. Абсолютное отклонение представляет собой сумму абсолютной разницы между каждым элементом вектора и средним значением:

$\sum_{i=0}^{n-1}{{abs%28\overline{x}%20-%20x_i}%29}$

Я знаю, что дисперсия вектора может быть рассчитана таким образом. Отклонение аналогично абсолютному отклонению, но каждая разница квадратична:

$\frac{\sum_{i=0}^{n-1}{{%28\overline{x}%20-%20x_i}%29}^2}{n}$

Онлайн-алгоритм для дисперсии выглядит следующим образом:

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

Есть ли такой алгоритм для вычисления абсолютного отклонения? Я не могу сформулировать рекурсивное определение сам, но более разумные головы могут преобладать!

Ответ 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"))

Ответ 2

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

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

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

Ответ 3

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

Проблема заключается в том, что абсолютное значение на самом деле более "нелинейное" в некотором смысле, чем сумма квадратов отклонений. Это не позволяет вам выполнять этот расчет в рекурсивной форме в цикле, по крайней мере, не сохраняя всех предыдущих значений x. Вы должны вычислить общее среднее заранее для этой суммы.

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