Algoritmo en línea para calcular la desviación absoluta

Question

Estoy tratando de calcular la desviación absoluta de un vector online, es decir, a medida que se recibe cada elemento en el vector, sin usar todo el vector. La desviación absoluta es la suma de la diferencia absoluta entre cada elemento en un vector y la media:

sé que la varianza de un vector se puede calcular de una manera tal. La variación es similar a la desviación absoluta, pero cada diferencia se eleva al cuadrado:

El algoritmo de línea de varianza es el siguiente:

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 

¿Existe un algoritmo para calcular absoluta ¿Desviación? No puedo formular una definición recursiva, ¡pero las cabezas más prudentes pueden prevalecer!

Answer 1

No creo que sea posible.

En la fórmula de varianza es posible separar los términos x y x , por lo que es suficiente hacer un seguimiento de esas sumas (yn). En la fórmula para la desviación absoluta esto no es posible.

Creo que lo mejor que se puede hacer (aparte de mantener todo el vector y calcular la desviación absoluta a pedido) es mantener una lista ordenada de elementos. Esto es O (log (n)) para cada elemento nuevo, pero después de agregar un elemento, el costo de recalcular la desviación absoluta es O (log (n)). Esto puede o no valer la pena, dependiendo de su aplicación.

Answer 2

La fórmula de varianza que das es UNA de las muchas que son posibles (puedo pensar en tres formas distintas de hacer ese cálculo) aunque no he verificado que la tuya sea correcta. Se ve razonablemente cerca de lo que recuerdo.

El problema es que el valor absoluto es en realidad más "no lineal" en cierto sentido que la suma de los cuadrados de las desviaciones. Esto evita que pueda hacer ese cálculo en forma recursiva en un bucle, al menos no sin retener todos los valores previos de x. Debe calcular la media general por adelantado para esa suma.

Editar: Veo que la versión beta está de acuerdo conmigo. SI guardó todos los puntos de datos anteriores, en una lista ordenada, podría calcular de manera eficiente la desviación deseada actualizada. Pero esto es contrario al espíritu de su solicitud.

Answer 3

Como la desviación absoluta entre xy la media se puede definir como la raíz cuadrada de la diferencia cuadrada, la adaptación es trivial si está satisfecho con una estimación coherente pero sesgada (lo que significa que el valor límite es infinito) :

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 

Esto es para el caso de la desviación absoluta media. Normalmente se usa el loco (desviación absoluta media), que es imposible de programar recursivamente. pero la desviación absoluta promedio es tan útil en la mayoría de los casos. Cuando hablamos de cientos de valores de distribuciones cercanas a la normal, ambos valores están muy cerca.

Si solo quiere la suma de las devaciones absolutas, la vida es aún más simple: simplemente devuelva M2.

Tenga en cuenta que AMBOS el algoritmo que usted dio y la adaptación trivial para la desviación absoluta son ligeramente parciales.

Una simulación en I para probar el algoritmo funciona de esta manera:

La línea roja es el verdadero valor, la línea de negro es el valor progresiva siguiendo el algoritmo descrito anteriormente.

Código:

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