Algoritmo per la covarianza online con finestra

Question

Algoritmo per la covarianza online con finestra

#1 da (2 voti)

2

Sto cercando di adattare un algoritmo per calcolare la covarianza in modo che funzioni su una finestra a rotazione sui dati. Wikipedia ha un algoritmo per la covarianza online :

def online_covariance(data1, data2):
    mean1 = mean2 = 0
    M12 = 0
    for x, y in zip(data1, data2):
        n += 1
        delta1 = (x - mean1) / n
        mean1 += delta1
        delta2 = (y - mean2) / n
        mean2 += delta2
        M12 += (n - 1) * delta1 * delta2 - M12 / n
    return n / (n - 1) * M12

Ma ho bisogno che funzioni su una finestra a rotazione di dimensioni arbitrarie. Ho già adattato un algoritmo diverso su quella pagina di Wikipedia affinché la varianza funzioni su una finestra a rotazione, ma mi sto bloccando a farlo per covarianza.

Lo pseudo-codice sottostante è quello che ho finora. Supponiamo che la funzione window restituisca un'enumerazione su una struttura che contiene gli elementi che entrano e escono dalla finestra ( Entered e Exited , rispettivamente).

def online_covariance(data1, data2, windowSize):
    mean1 = mean2 = 0
    M12 = 0
    i = 0
    covars = []
    for x, y in zip(window(data1, windowSize), window(data2, windowSize)):

        if(n < windowSize)
            n += 1
        delta1 = (i < windowSize ? x.Entered - mean1 : x.Entered - x.Exited) / n
        mean1 += delta1
        delta2 = (i < windowSize ? y.Entered - mean2 : y.Entered - y.Exited) / n
        mean2 += delta2

        // Up to this point I can verify the algorithm is correct- 
        // it keeps the correct means for each data set
        // This next line is where I'm stuck- 
        // it needs to be modified to remove the value that 
        // just left the window
        M12 += (n - 1) * delta1 * delta2 - M12 / n

        covars.Add(n / (n - 1) * M12)
        i++
    return covars

algorithms math

posta MgSam 06.12.2016 - 14:54

fonte

1 risposta

Leggi altre domande sui tag algorithms math

Come denominare i progetti di test Registrazione Registrazione in un progetto utilizzando una libreria di classi o un servizio Web

score 2 · Answer 1

Per iniziare con

Pensa a come calcoli Var (X) online (dove X è un flusso infinito di numeri).

Quello che faresti qui è tenere traccia di due quantità:

Somma di tutti i valori X (cioè somma (x1, x2, x3, ....))
Somma di tutti i valori X ^ 2 (cioè somma (x1 ^ 2, x2 ^ 2, x3 ^ 2, ...))

Quindi quando hai bisogno di calcolare la varianza dopo il 1000 ° valore x tutto ciò che fai è tornare

Var(X) = SumOfSquares/n - (Sum/n)^2

(questa formula è data perché Var (X) = E [X ^ 2] - E [X] ^ 2)

Per calcolare Cov online

Tieni traccia di queste quantità (come detto sopra significa sottrarre quantità che non sono più nella tua finestra)

Somma di tutti i valori X nella finestra (es. somma (x1, x2, x3, ....))
Somma di tutti i valori Y nella finestra (cioè somma (x1, x2, x3, ....))
Somma di tutti i valori X * Y nella tua finestra (i..e sum (x1 * y1, x2 * y2, x3 * y3))

Tutto quello che rimane è un po 'di algebra ... che ti lascio.

Dal punto di vista di un programmatore

Suggerisco di scrivere una funzione come questa:

double covar(cumulativeSumOfXs, cumulativeSumOfYs, cumulativeSumofXYs){
    //only simple algebra is necessary if these are your inputs
}