Joonas' Note

Joonas' Note

실시간 평균 (Moving Average; 이동 평균) 본문

알고리즘

실시간 평균 (Moving Average; 이동 평균)

2020. 1. 13. 23:08 joonas

    성능 테스트 코드를 작성하다가, 평균을 실시간으로 구하는 방법을 글로 정리해볼까 한다.

    (직관으로) 어렸을 적에 이게 당연한 줄 알았다. 근데 몇개의 반례를 찾고는 틀렸다고 생각했다. 그런데 학부 시절에 교수님께서 '그런 것이 있다'고 말씀해주셨다.

    이름은 Moving average이고, 한국어로는 모르겠다. 나는 데이터 범위에 따라 점진적으로 평균을 구해간다는 느낌으로 점진적 평균 또는 실시간 평균으로 부르고 싶지만, 통계쪽에서 "이동 평균"으로 부르는 모양이다.


    아무튼, 본디 평균을 구하는 식은 전체 합 \(S_n\)에서 데이터의 개수 \(n\)만큼 나눈 \(S_{n} / n\) 이다.

    그럼 이것이 뭐가 문제인가?

    \(n\)개를 전부 더하거나 카운팅 하지 않으면 평균을 구할 수 없다. 어떤 실험 \(X_i\) 하나가 끝나는 데 1분씩 걸리고 실험 100개의 평균을 내고 싶다면 100분을 기다려야 알 수 있다 (!)

    누적합으로도 가능하지만, 누적합의 범위가 담을 수 없을 만큼 너무 큰 경우에 유용하다.

    나는 정확히 이런 상황에 놓인 적이 있었고, 이 Moving average로 해결하였다.


    우선, 그림으로 보는 것이 빠르다.

    점선은 전체 데이터의 평균값이고, 빨간선은 이동평균값이다.

    느낌은 딥러닝에서의 경사하강법(gradient descent)과 비슷하다고 생각한다. 어떤 정답(평균)이 있고, 부분적으로 살펴가며 그것을 조금씩 찾아가는 것이다. (경사하강법도 재밌으니 궁금하면 찾아보자.)

    그림을 보면 알겠지만, 횟수가 많아야 진짜 평균값과 비슷해지고, 데이터 값의 범위가 너무 작으면 오차가 크게 벌어지기도 한다. (즉, 정확도가 떨어지기도 한다.)

    아래는 횟수가 1000회일때, 평균을 찾아가는 모습

    어떻게?

    이전에 구한 평균값을 그대로 사용할 수 있다.

    이전에 구했던 평균값은, 새로운 데이터 1개가 추가되었을 때 (n-1) : 1 의 비율만큼만 평균에 반영될 것이다.

    위 그림처럼 비율을 맞춰서 새로운 평균값을 조정해주면, 전체 식은 \((a_1 + \dots + a_n)~/~n\)으로 유지되는 것을 볼 수 있다.

    이것 역시, 라빈 카프의 해싱(또는 그것의 fingerprint)과 비슷한 점이 재밌다.


    결론

    수열 \(a\)의 \(n\)번째까지의 이동 평균 \(Avg_n\)은 \(Avg_n = ((n-1)Avg_{n-1}+a_n)~/~n\) 이다.


    코드 역시 간단하다.

    다만, 실수 오차가 있음에 주의해야 한다.

    Comments