Como calcular a média móvel sem manter a contagem e o total de dados?

118

Estou tentando encontrar uma maneira de calcular uma média cumulativa móvel sem armazenar a contagem e o total de dados recebidos até agora.

Eu vim com dois algoritmos, mas ambos precisam armazenar a contagem:

  • nova média = ((contagem antiga * dados antigos) + próximos dados) / próxima contagem
  • nova média = média antiga + (próximos dados - média antiga) / próxima contagem

O problema com esses métodos é que a contagem fica cada vez maior, resultando na perda de precisão na média resultante.

O primeiro método usa a contagem antiga e a próxima, que são obviamente 1 de diferença. Isso me fez pensar que talvez haja uma maneira de remover a contagem, mas infelizmente ainda não a encontrei. Isso me levou um pouco mais longe, resultando no segundo método, mas ainda assim a contagem está presente.

É possível ou estou apenas procurando o impossível?

user1705674
fonte
1
NB que numericamente, armazenar o total atual e a contagem atual é a maneira mais estável. Caso contrário, para contagens mais altas, próximo / (próxima contagem) começará a diminuir. Portanto, se você está realmente preocupado em perder precisão, mantenha os totais!
AlexR
1
Veja Wikipedia en.wikipedia.org/wiki/Moving_average
xmedeko

Respostas:

91

Você pode simplesmente fazer:

double approxRollingAverage (double avg, double new_sample) {

    avg -= avg / N;
    avg += new_sample / N;

    return avg;
}

Onde Nestá o número de amostras das quais você deseja calcular a média. Observe que esta aproximação é equivalente a uma média móvel exponencial. Veja: Calcular a média móvel / móvel em C ++

Muis
fonte
3
Você não tem que adicionar 1 a N antes desta linha? média + = nova_amostra / N;
Damian
20
Isso não é inteiramente correto. O que @Muis descreve é ​​uma média móvel exponencialmente ponderada, que às vezes é apropriada, mas não é precisamente o que o OP solicitou. Como exemplo, considere o comportamento que você espera quando a maioria dos pontos está na faixa de 2 a 4, mas um valor está acima de um milhão. Um EWMA (aqui) manterá os vestígios desse milhão por algum tempo. Uma convolução finita, como indicado por OP, iria perdê-lo imediatamente após N passos. Ele tem a vantagem de armazenamento constante.
jma
9
Isso não é uma média móvel. O que você descreve é ​​um filtro de um pólo que cria respostas exponenciais a saltos no sinal. Uma média móvel cria uma resposta linear com comprimento N.
ruhig brauner
3
Esteja ciente de que isso está muito longe da definição comum de média. Se você definir N = 5 e inserir 5 5amostras, a média será 0,67.
Dan Dascalescu
2
@DanDascalescu Embora você esteja certo de que não é realmente uma média móvel, seu valor declarado está errado em uma ordem de magnitude. Com avginicializado em 0, você acaba com 3.36após 5 5s e 4.46após 10: cpp.sh/2ryql Para médias longas, esta é certamente uma aproximação útil.
cincodenada de
80
New average = old average * (n-1)/n + new value /n

Isso pressupõe que a contagem mudou apenas em um valor. Caso seja alterado por valores M, então:

new average = old average * (n-len(M))/n + (sum of values in M)/n).

Esta é a fórmula matemática (acredito que seja a mais eficiente), acredite que você pode fazer mais códigos por conta própria

Abdullah Al-Ageel
fonte
Qual é a soma do novo valor? isso é de alguma forma diferente do "novo valor" em sua fórmula original?
Mikhail
@Mikhail no segundo exemplo, há mnovos valores sendo fatorados na nova média. Eu acredito que sum of new valueaqui se destina a ser a soma dos mnovos valores usados ​​para calcular a nova média.
Patrick Goley
9
Um pouco mais eficiente para o primeiro: new_average = (old_average * (n-1) + new_value) / n- Remove uma das divisões.
Pixelstix
Que tal correr em média de 3 elementos com 6,0,0,9?
Roshan Mehta
1
Quando implemento esta equação, o valor ou a média contínua sempre aumenta lentamente. Nunca desce - apenas sobe.
anon58192932
30

De um blog sobre a execução de cálculos de variação de amostra, onde a média também é calculada usando o método de Welford :

insira a descrição da imagem aqui

Pena que não podemos fazer upload de imagens SVG.

Giro
fonte
3
Isso é semelhante ao que Muis implementou, exceto que a divisão é usada como um fator comum. Portanto, apenas uma divisão.
Flip
Na verdade, está mais próximo de @ Abdullah-Al-Ageel (matemática essencialmente comutativa) no sentido de que Muis não leva em consideração o incremento de N; referência da fórmula copiar e colar: [Média em n] = [Média em n-1] + (x - [Média em n-1]) / n
drzaus
2
@Flip & drwaus: As soluções de Muis e Abdullah Al-Ageel não são exatamente as mesmas? É o mesmo cálculo, apenas escrito de forma diferente. Para mim, essas 3 respostas são idênticas, sendo esta mais visual (uma pena que não podemos usar MathJax no SO).
user276648
21

Aqui está outra resposta que oferece comentários sobre como a resposta de Muis , Abdullah Al-Ageel e Flip são matematicamente a mesma coisa exceto que escritas de forma diferente.

Claro, temos José Manuel Ramos a análise de explicando como os erros de arredondamento afetam cada um de maneira ligeiramente diferente, mas isso depende da implementação e mudaria com base em como cada resposta foi aplicada ao código.

No entanto, há uma grande diferença

Está no Muis 's N, Flip 's ke Abdullah Al-Ageel 's n. Abdullah Al-Ageel não chega a explicar o que ndeveria ser, mas Ne kdiferem em que Né " o número de amostras em que deseja média ao longo ", enquanto ké a contagem de valores amostrados. (Embora eu tenha dúvidas se ligar para N o número de amostras é preciso.)

E aqui chegamos à resposta abaixo. É essencialmente a mesma velha média móvel exponencial ponderada dos outros, então, se você estiver procurando por uma alternativa, pare aqui.

Média móvel exponencial ponderada

Inicialmente:

average = 0
counter = 0

Para cada valor:

counter += 1
average = average + (value - average) / min(counter, FACTOR)

A diferença é a min(counter, FACTOR)parte. Isso é o mesmo que dizer min(Flip's k, Muis's N).

FACTORé uma constante que afeta a rapidez com que a média "alcança" a tendência mais recente. Quanto menor o número, mais rápido. (Em 1não é mais uma média e apenas se torna o valor mais recente).

Esta resposta requer o contador em execução counter. Se for problemático, o min(counter, FACTOR)pode ser substituído por just FACTOR, transformando-o na resposta de Muis . O problema em fazer isso é que a média móvel é afetada por tudo o que averageé inicializado. Se foi inicializado para0 , esse zero pode levar muito tempo para sair da média.

Como fica parecendo

Média móvel exponencial

Antak
fonte
3
Bem explicado. Só perdi uma média simples em seu gráfico, porque foi isso que OP pediu.
xmedeko
Talvez eu esteja faltando alguma coisa, mas você, por acaso, quis dizer max(counter, FACTOR). min(counter, FACTOR)sempre retornará FACTOR, certo?
WebWanderer
1
Acho que o objetivo do min(counter, FACTOR)é dar conta do período de aquecimento. Sem ele, se seu FACTOR (ou N, ou contagem de amostra desejada) for 1000, você precisará de pelo menos 1000 amostras antes de obter um resultado preciso, já que todas as atualizações anteriores assumirão que você tem 1000 amostras, quando você pode apenas tem 20.
rharter
Seria bom parar de contar depois de chegar ao fator, provavelmente seria mais rápido assim.
inf3rno
8

A resposta de Flip é computacionalmente mais consistente do que a de Muis.

Usando o formato de número duplo, você pode ver o problema de arredondamento na abordagem de Muis:

A abordagem Muis

Quando você divide e subtrai, um arredondamento aparece no valor armazenado anterior, alterando-o.

No entanto, a abordagem Flip preserva o valor armazenado e reduz o número de divisões, portanto, reduzindo o arredondamento e minimizando o erro propagado para o valor armazenado. Adicionar apenas trará arredondamentos se houver algo a adicionar (quando N é grande, não há nada a adicionar)

A abordagem Flip

Essas mudanças são notáveis ​​quando você faz com que uma média de valores grandes tenda a sua média para zero.

Eu mostro os resultados usando um programa de planilha:

Em primeiro lugar, os resultados obtidos: Resultados

As colunas A e B são os valores n e X_n, respectivamente.

A coluna C é a abordagem Flip, e a coluna D é a abordagem Muis, o resultado armazenado na média. A coluna E corresponde ao valor médio usado no cálculo.

Um gráfico que mostra a média dos valores pares é o próximo:

Gráfico

Como você pode ver, há grandes diferenças entre as duas abordagens.

José Manuel Ramos
fonte
2
Não é realmente uma resposta, mas uma informação útil. Seria ainda melhor se você adicionasse a 3ª linha ao seu gráfico, para a média real sobre n valores anteriores, para que pudéssemos ver qual das duas abordagens chega mais perto.
jpaugh
2
@jpaugh: A coluna B está alternando entre -1,00E + 15 e 1,00E + 15, então quando N é par, a média real deve ser 0. O título do gráfico é "Médias parciais pares". Isso significa que a terceira linha sobre a qual você pergunta é simplesmente f (x) = 0. O gráfico mostra que ambas as abordagens apresentam erros que continuam aumentando.
desowin
Isso mesmo, o gráfico mostra exatamente o erro propagado usando grandes números envolvidos nos cálculos usando ambas as abordagens.
José Manuel Ramos
A legenda do seu gráfico tem cores erradas: a de Muis é laranja, a de Flip é azul.
xmedeko
6

Um exemplo usando javascript, para comparação:

https://jsfiddle.net/drzaus/Lxsa4rpz/

function calcNormalAvg(list) {
    // sum(list) / len(list)
    return list.reduce(function(a, b) { return a + b; }) / list.length;
}
function calcRunningAvg(previousAverage, currentNumber, index) {
    // [ avg' * (n-1) + x ] / n
    return ( previousAverage * (index - 1) + currentNumber ) / index;
}

drzaus
fonte
1

Em Java8:

LongSummaryStatistics movingAverage = new LongSummaryStatistics();
movingAverage.accept(new data);
...
average = movingAverage.getAverage();

você também tem IntSummaryStatistics, DoubleSummaryStatistics...

jmhostalet
fonte
2
OP está pedindo um algoritmo, não um ponteiro para calcular isso em Java.
olq_plo
0

Uma solução Python bacana com base nas respostas acima:

class RunningAverage():
    def __init__(self):
        self.average = 0
        self.n = 0
        
    def __call__(self, new_value):
        self.n += 1
        self.average = (self.average * (self.n-1) + new_value) / self.n 
        
    def __float__(self):
        return self.average
    
    def __repr__(self):
        return "average: " + str(self.average)

uso:

x = RunningAverage()
x(0)
x(2)
x(4)
print(x)
Dima Lituiev
fonte