Implementação De Média Móvel Ponderada

Estou tentando calcular a média móvel de um sinal. O valor do sinal (um duplo) é atualizado em tempos aleatórios. Eu estou procurando uma forma eficiente de calcular a sua média ponderada em tempo sobre uma janela de tempo, em tempo real. Eu poderia fazer isso sozinho, mas é mais desafiador do que eu pensava. A maioria dos recursos que eu encontrei na internet estão calculando a média móvel do sinal periódico, mas as atualizações de minas em tempo aleatório. Alguém sabe bons recursos para que o truque é o seguinte: Você recebe atualizações em tempos aleatórios por meio de atualização void (tempo int, valor float). No entanto, você também precisa acompanhar quando uma atualização cai fora da janela de tempo, então você definir um alarme que chamado no tempo N que remove a atualização anterior de ser sempre considerado novamente na computação. Se isso acontece em tempo real, você pode solicitar o sistema operacional para fazer uma chamada para um dropoffoldestupdate método void (int time) para ser chamado em tempo N Se esta é uma simulação, você não pode obter ajuda do sistema operacional e você precisa Faça-o manualmente. Em uma simulação você chamaria métodos com o tempo fornecido como um argumento (que não se correlaciona com o tempo real). No entanto, uma suposição razoável é que as chamadas são garantidas de tal forma que os argumentos de tempo estão aumentando. Neste caso, você precisa manter uma lista ordenada de valores de tempo de alarme e, para cada atualização e chamada de leitura, você verifica se o argumento de tempo é maior que o cabeçalho da lista de alarmes. Enquanto é maior você faz o processamento relacionado com o alarme (solte a atualização mais antiga), remova a cabeça e verifique novamente até que todos os alarmes antes do tempo determinado sejam processados. Em seguida, faça a chamada de atualização. Até agora tenho assumido que é óbvio o que você faria para a computação real, mas vou elaborar apenas no caso. Eu suponho que você tem um método float read (tempo int) que você usa para ler os valores. O objetivo é tornar essa chamada o mais eficiente possível. Portanto, você não calcula a média móvel sempre que o método de leitura é chamado. Em vez disso, você precompute o valor a partir da última atualização ou o último alarme e ajustar esse valor por um par de operações ponto flutuante para conta para a passagem do tempo desde a última atualização. (Isto é, um número constante de operações excepto para talvez processar uma lista de alarmes acumulados). Esperemos que isso seja claro - este deve ser um algoritmo bastante simples e bastante eficiente. Otimização adicional. Um dos problemas restantes é se um grande número de atualizações acontecer dentro da janela de tempo, então há um longo tempo para que não há nem lê nem atualizações e, em seguida, uma leitura ou atualização vem junto. Neste caso, o algoritmo acima será ineficiente na atualização incremental do valor para cada uma das atualizações que está caindo. Isso não é necessário porque só nos preocupamos com a última atualização além da janela de tempo, por isso, se houver uma maneira de descartar eficientemente todas as atualizações antigas, isso ajudaria. Para fazer isso, podemos modificar o algoritmo para fazer uma busca binária de atualizações para encontrar a atualização mais recente antes da janela de tempo. Se houver relativamente poucas atualizações que precisam ser descartadas, então um pode atualizar incrementalmente o valor para cada atualização descartada. Mas se houver muitas atualizações que precisam ser descartadas, então um pode recalcular o valor do zero após deixar as atualizações antigas. Apêndice na Incremental Computação: Eu deveria esclarecer o que quero dizer com computação incrementais acima na frase ajustar este valor por um par de operações de ponto flutuante para dar conta da passagem do tempo desde a última atualização. Cálculo inicial não incremental: então iterar sobre datas relevantes por ordem crescente de tempo: movendo-se (sum lastupdate timesincelastupdate) windowlength. Agora, se exatamente uma atualização cai da janela, mas nenhuma nova atualização chegar, ajuste a soma como: (note que é priorupdate que tem seu timestamp modificado para iniciar o último início da janela). E se exatamente uma atualização entra na janela, mas nenhuma nova atualização cair, ajustar soma como: Como deveria ser óbvio, este é um esboço, mas esperamos que ele mostra como você pode manter a média de tal forma que é O (1) operações por atualização Sobre uma base amortizada. Mas observe otimização adicional no parágrafo anterior. Observe também problemas de estabilidade a que alude uma resposta mais velho, o que significa que os erros de ponto flutuante pode acumular-se ao longo de um grande número de tais operações incrementais de tal forma que há uma divergência entre o resultado do cálculo integral que é significativo para a aplicação. Se uma aproximação é OK e há um tempo mínimo entre as amostras, você pode tentar super-amostragem. Tenha uma matriz que represente intervalos de tempo uniformemente espaçados que são menores do que o mínimo e, em cada período de tempo, armazene a amostra mais recente que foi recebida. Quanto mais curto o intervalo, mais próxima a média será do valor verdadeiro. O período não deve ser maior do que a metade do mínimo ou há uma chance de faltar uma amostra. Respondeu Dec 15 11 at 18:12 respondeu Dec 15 11 at 22:38 Obrigado pela resposta. Uma melhoria que seria necessário para realmente quotcachequot o valor da média total para que don39t loop o tempo todo. Além disso, pode ser um ponto menor, mas não seria mais eficiente usar um deque ou uma lista para armazenar o valor, uma vez que assumimos que a atualização virá na ordem correta. A inserção seria mais rápida do que no mapa. Ndash Arthur 16 dez às 8:55 Sim, você poderia armazenar em cache o valor de soma. Subtraia os valores das amostras que você apaga, adicione os valores das amostras inseridas. Além disso, sim, um dequeltpairltSample, Dategtgt pode ser mais eficiente. Eu escolhi o mapa para a legibilidade, ea facilidade de invocar map :: upperbound. Como sempre, escreva o código correto primeiro, depois perfil e mude as mudanças incrementais. Ndash Rob 16 de dezembro às 15:00 Nota: Aparentemente esta não é a maneira de abordar isso. Deixando aqui para referência sobre o que está errado com esta abordagem. Verifique os comentários. UPDATED - com base no comentário Olis. Não tenho certeza sobre a instabilidade de que ele está falando embora. Use um mapa ordenado de tempos de chegada contra valores. Após a chegada de um valor adicionar a hora de chegada para o mapa ordenado, juntamente com o seu valor e atualizar a média móvel. Aviso este é pseudo-código: Lá. Não totalmente desenvolvido, mas você começa a idéia. Coisas a observar. Como eu disse o acima é pseudo código. Você precisará escolher um mapa apropriado. Não remova os pares à medida que você iterar através como você irá invalidar o iterador e terá que começar novamente. Veja Olis comentário abaixo também. Este trabalho não funciona: ele não leva em conta que proporção do comprimento da janela de cada valor existe para. Além disso, essa abordagem de adição e subtração é apenas estável para tipos inteiros, e não para flutuadores. Ndash Oliver Charlesworth Dec 15 11 em 12:29 OliCharlesworth - desculpe eu perdi alguns pontos-chave na descrição (duplo e ponderada). Eu vou atualizar. Obrigado. Ndash Dennis Dec 15 11 at 12:33 A ponderação de tempo é ainda outro problema. Mas isso não é o que eu estou falando. Eu estava me referindo ao fato de que quando um novo valor entra pela primeira vez na janela de tempo, sua contribuição para a média é mínima. Sua contribuição continua a aumentar até que um novo valor entre. Eu tenho uma matriz de valores como este: A matriz acima é simplificada, estou coletando um valor por milissegundo no meu código real e eu preciso processar a saída em um algoritmo que eu escrevi para encontrar o Máximo antes de um ponto no tempo. Minha lógica falha porque no meu exemplo acima, 0.36 é o pico real, mas meu algoritmo olharia para trás e verá o último número 0.25 como o pico, pois há uma diminuição para 0.24 antes dele. O objetivo é tomar esses valores e aplicar um algoritmo para eles que irá suavizar-los um pouco para que eu tenha mais valores lineares. (Ou seja: Id como meus resultados para ser curvy, não jaggedy) Ive foi dito para aplicar um filtro exponencial de média móvel para os meus valores. Como posso fazer isso É muito difícil para mim ler equações matemáticas, eu lidar muito melhor com o código. Como processar valores em minha matriz, aplicando um cálculo exponencial de média móvel para igualá-los out perguntou Feb 8 12 at 20:27 Para calcular uma média móvel exponencial. Você precisa manter algum estado ao redor e você precisa de um parâmetro de ajuste. Isso requer uma pequena classe (supondo que você está usando o Java 5 ou posterior): Instantiate com o parâmetro de decadência desejado (pode ter ajuste deve estar entre 0 e 1) e use a média () para filtrar. Ao ler uma página sobre alguma recorrência matemática, tudo o que você realmente precisa saber ao transformá-lo em código é que os matemáticos gostam de escrever índices em matrizes e seqüências com subscritos. (Eles têm algumas outras notações também, o que não ajuda.) No entanto, o EMA é bastante simples, como você só precisa se lembrar de um antigo valor não arrays estado complicado necessário. Respondeu 8 fevereiro às 20:42 TKKocheran: Muito bonito. Não é bom quando as coisas podem ser simples (se começar com uma nova seqüência, obter um novo averager.) Observe que os primeiros termos na seqüência média saltarão um pouco devido a efeitos de limite, mas você obtém aqueles com outras médias móveis também. No entanto, uma boa vantagem é que você pode envolver a lógica de média móvel para o averager e experimentar sem perturbar o resto do seu programa demais. Ndash Donal Fellows Feb 9 12 em 0:06 Estou tendo dificuldade em compreender suas perguntas, mas vou tentar responder de qualquer maneira. 1) Se o seu algoritmo encontrado 0,25 em vez de 0,36, então ele está errado. É errado porque assume um aumento ou uma diminuição monotônica (que está sempre subindo ou sempre indo para baixo). A menos que você média TODOS os seus dados, seus pontos de dados --- como você apresentá-los --- são não-lineares. Se você realmente deseja encontrar o valor máximo entre dois pontos no tempo, corte sua matriz de tmin para tmax e localize o máximo desse subarray. 2) Agora, o conceito de médias móveis é muito simples: imagine que eu tenho a seguinte lista: 1.4, 1.5, 1.4, 1.5, 1.5. Eu posso suavizar isto tomando a média de dois números: 1.45, 1.45, 1.45, 1.5. Observe que o primeiro número é a média de 1,5 e 1,4 (segundo e primeiro números) a segunda (nova lista) é a média de 1,4 e 1,5 (terceira e segunda lista antiga) a terceira (nova lista) a média de 1,5 e 1,4 (Quarto e terceiro), e assim por diante. Eu poderia ter feito o período três ou quatro, ou n. Observe como os dados são muito mais suaves. Uma boa maneira de ver as médias móveis no trabalho é ir ao Google Finance, selecionar um estoque (tente Tesla Motors bastante volátil (TSLA)) e clique em technicals na parte inferior do gráfico. Selecione Média Móvel com um determinado período, e média móvel exponencial para comparar suas diferenças. A média móvel exponencial é apenas mais uma elaboração disto, mas pondera os dados mais antigos menos do que os novos dados, isto é uma forma de influenciar a suavização em direção às costas. Por favor, leia a entrada da Wikipedia. Então, isso é mais um comentário do que uma resposta, mas a pequena caixa de comentários era apenas pequena. Boa sorte. Se você está tendo problemas com a matemática, você poderia ir com uma média móvel simples, em vez de exponencial. Então a saída que você obtém seria o último x termos dividido por x. Pseudocódigo não testado: Note que você precisará manipular as partes inicial e final dos dados, uma vez que claramente você não consegue média dos últimos 5 termos quando você está no seu 2º ponto de dados. Além disso, há maneiras mais eficientes de calcular essa média móvel (soma sum - mais antigo mais recente), mas isso é para obter o conceito do que está acontecendo em toda. Respondeu 8 de fevereiro em 20:41 É possível implementar uma média móvel em C sem a necessidade de uma janela de amostras Ive descobri que eu posso otimizar um pouco, escolhendo um tamanho de janela thats um poder de dois para permitir bit-shifting Em vez de dividir, mas não precisava de um buffer seria bom. Existe uma maneira de expressar um novo resultado da média móvel apenas como uma função do antigo resultado e da nova amostra Definir um exemplo de média móvel, através de uma janela de 4 amostras para ser: Adicionar nova amostra e: Uma média móvel pode ser implementada recursivamente , Mas para um cálculo exato da média móvel você deve se lembrar da amostra de entrada mais antiga na soma (ou seja, o a no seu exemplo). Para um comprimento N média móvel você calcula: onde yn é o sinal de saída e xn é o sinal de entrada. Eq. (1) pode ser escrito recursivamente como Então você sempre precisa lembrar a amostra xn-N para calcular (2). Como indicado por Conrad Turner, você pode usar uma janela exponencial (infinitamente longa), que permite calcular a saída somente da saída anterior e da entrada atual: mas esta não é uma média móvel padrão (não ponderada), mas uma média exponencial Ponderada média móvel, onde as amostras mais no passado obter um menor peso, mas (pelo menos em teoria) você nunca se esqueça nada (os pesos apenas ficar menor e menor para amostras no passado). Eu implementei uma média móvel sem memória de item individual para um programa de rastreamento GPS que eu escrevi. Eu começo com 1 amostra e dividir por 1 para obter o avg atual. Eu adiciono então uma outra amostra e divido por 2 à corrente avg. Isso continua até que eu chegar ao comprimento da média. Cada vez depois, eu adiciono na nova amostra, obter a média e remover essa média do total. Eu não sou um matemático, mas isso parecia ser uma boa maneira de fazê-lo. Eu imaginei que iria transformar o estômago de um cara de matemática real, mas, verifica-se que é uma das formas aceitas de fazê-lo. E funciona bem. Basta lembrar que quanto maior o seu comprimento, mais lento é seguir o que você deseja seguir. Isso pode não importar a maior parte do tempo, mas quando os satélites seguintes, se você é lento, a trilha poderia estar longe da posição real e vai ficar mal. Você poderia ter uma lacuna entre o sat e os pontos de arrasto. Eu escolhi um comprimento de 15 atualizado 6 vezes por minuto para obter alisamento adequado e não ficar muito longe da posição real sentado com os pontos de trilha suavizada. Respondida Nov 16 16 at 23:03 initialize total 0, count0 (cada vez vendo um novo valor Então uma entrada (scanf), um add totalnewValue, um incremento (count), uma divide average (totalcount) Todas as entradas Para calcular a média apenas nas últimas 4 entradas, seria necessário 4 variáveis ​​de entrada, talvez copiando cada entrada para uma variável de entrada mais antiga, calculando a nova média móvel como a soma das 4 variáveis ​​de entrada, dividida por 4 Bom se todos os insumos foram positivos para fazer o cálculo médio respondido Feb 3 15 at 4:06 Isso vai realmente calcular a média total e não a média móvel. Como a contagem fica maior o impacto de qualquer nova amostra de entrada torna-se ndash nitidamente pequena Hilmar fevereiro 3 15 às 13:53 Sua resposta 2017 Stack Exchange, Inc