[시계열 데이터] 부분배열의 평균과 분산을 O(n)에 계산하기

문제

• 시계열 데이터에서 부분배열의 평균과 분산 구하기
  • window_size 길이의 부분배열에서 평균과 분산을 계산해야 함
  • 가령 아래 예시에서는
    • (3,4,5,1,2)의 평균과 분산
    • (4,5,1,2,6)의 평균과 분산
    • (5,1,2,6,2)의 평균과 분산

series = [3,4,5,1,2,6,2]
wsize = 5
expected_output = [(3.0, 2.0), (3.6, 3.44), (3.2, 3.76)]

기록 포인트

• 평균을 구할 때는 시간복잡도를 줄이기 위한 방법은 상대적으로 쉽게 접근 가능했음
  • 평균 계산 공식은 sum(arr) / len(arr)
  • 이 때 sum(arr)에서 배열의 양 끝을 제외한 나머지는 다음 회기의 계산에도 포함됨
    • 위 예시에서 회기 1에서 부분배열은 (3,4,5,1,2)이며
    • 회기 2에서 부분배열은 맨 앞 3을 빼고 맨 끝 6을 더한 (4,5,1,2,6)
  • 결과적으로 시계열 데이터에서 부분배열의 평균을 계산하는 로직은 O(n)에 가능
• 그런데 분산은?
  • 오차의 제곱의 평균을 구해야 하기에 어렵지 않을까 생각했음
  • 하지만 분산 계산 공식을 생각해보면 분산 또한 O(n)에 해결 가능!
    • 자세한 내용은 아래 접근 방식(풀이 코드) 참고
• 분산 계산 공식 복습

접근 방식

풀이 코드

def describe_series_data(series, wsize):
    # wsize 체크
    wsize = int(wsize)
    if wsize <= 0:
        raise ValueError("window size should be positive integer.")
    # series 길이 체크
    if len(series) < wsize:
        raise Exception("the length of series data is not long enough.")

    # 평균과 분산 계산용 lambda 함수
    mean = lambda tot, s: round(tot/s, 4)
    variance = lambda tot_sq, m, s: round(tot_sq / s - m*m, 4)

    # 초기 값 설정: output은 (평균, 분산)의 배열
    output = []
    tmp_sum = sum(series[:wsize])
    tmp_sum_sq = sum([v * v for v in series[:wsize]])
    m = mean(tmp_sum, wsize)
    va = variance(tmp_sum_sq, m, wsize)
    output.append((m, va))

    # 부분배열의 평균과 분산 계산
    for i in range(wsize, len(series)):
        head, tail = series[i-wsize], series[i]
        # tmp_sum 업데이트 
        tmp_sum = tmp_sum - head + tail
        # tmp_sum_sq 업데이트
        tmp_sum_sq = tmp_sum_sq - head * head + tail * tail
        # output에 추가
        m = mean(tmp_sum, wsize)
        va = variance(tmp_sum_sq, m, wsize)
        output.append((m, va))
    
    return output


def test(series, wsize):
    print(f"[TEST] starts with {series}, {wsize}")
    try:
        results = describe_series_data(series, wsize)
        print(f"  RESULT : {results}")
    except Exception as e:
        print(f"  ERROR  : {e}")
    print("")


if __name__ == "__main__":
    series = [3,4,5,1,2,6,2]
    wsize = 5  # window size

    test(series, -1)
    test(series, 100)
    test(series, wsize)

실행 결과

[TEST] starts with [3, 4, 5, 1, 2, 6, 2], -1
  ERROR  : window size should be positive integer.

[TEST] starts with [3, 4, 5, 1, 2, 6, 2], 100
  ERROR  : the length of series data is not long enough.

[TEST] starts with [3, 4, 5, 1, 2, 6, 2], 5
  RESULT : [(3.0, 2.0), (3.6, 3.44), (3.2, 3.76)]