Algoritmo online per calcolare la deviazione assoluta

Question

Sto provando a calcolare la deviazione assoluta di un vettore online, vale a dire, poiché ogni elemento nel vettore è ricevuto, senza utilizzare l'intero vettore. La deviazione assoluta è la somma della differenza assoluta tra ogni elemento in un vettore e la media:

So che la varianza di un vettore può essere calcolato in modo tale. Varianza è simile alla deviazione assoluta, ma ogni differenza è squadrato:

L'algoritmo online per la varianza è il seguente:

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 

Esiste un tale algoritmo di calcolo assoluto devianza? Non posso formulare una definizione ricorsiva da solo, ma i capi più saggi possono prevalere!

Answer 1

Non credo sia possibile.

Nella formula per la varianza è possibile separare i termini x e x , in modo che sia sufficiente tenere traccia di tali somme (e n). Nella formula per la deviazione assoluta questo non è possibile.

Penso che il meglio che si può fare (oltre a mantenere l'intero vettore e calcolare la deviazione assoluta su richiesta) è mantenere un elenco ordinato di elementi. Questo è O (log (n)) per ogni nuovo elemento, ma dopo aver aggiunto un elemento il costo del ricalcolo della deviazione assoluta è O (log (n)). Questo può o non può essere utile, a seconda dell'applicazione.

Answer 2

La formula per la varianza che date è UNO dei molti che sono possibili (posso pensare a tre modi distinti di fare quel calcolo) anche se non ho verificato che il vostro sia corretto. Sembra abbastanza vicino a ciò che ricordo.

Il problema è che il valore assoluto è in realtà più "non lineare" in un certo senso rispetto alla somma dei quadrati delle deviazioni. Questo ti impedisce di essere in grado di fare quel calcolo in una forma ricorsiva in un ciclo, almeno non senza mantenere tutti i valori precedenti di x. È necessario calcolare la media complessiva in anticipo per tale somma.

Modifica: vedo che la beta è d'accordo con me. Se si sono salvati tutti i punti di dati precedenti, in un elenco ordinato, è possibile calcolare in modo efficiente la deviazione desiderata aggiornata. Ma questo è in contrasto con lo spirito della tua richiesta.

Answer 3

Poiché la deviazione assoluta tra xe la media può essere definita come la radice quadrata della differenza quadratica, l'adattamento è banale se si è soddisfatti di una stima coerente ma parziale (ovvero il limite all'infinito è il valore previsto) :

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 

Questo è il caso della deviazione assoluta media. Normalmente viene utilizzato il matto (deviazione assoluta mediana), che è impossibile programmare in modo ricorsivo. ma la deviazione assoluta media è utile nella maggior parte dei casi. Quando parliamo di centinaia di valori da distribuzioni ravvicinate, entrambi i valori sono molto vicini.

Se si desidera solo la somma delle deviazioni assolute, la vita è ancora più semplice: basta restituire M2.

Essere consapevoli del fatto che ENTRAMBI l'algoritmo che hai dato e l'adeguamento banale per la deviazione assoluta sono leggermente di parte.

Una simulazione in R per dimostrare l'algoritmo funziona in questo modo:

La linea rossa è il vero valore, la linea nera è il valore progressivo seguente algoritmo descritto sopra.

Codice:

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