시계열 데이터에서 변화점 찾기(change point detection)

시계열 데이터에서 change point는 시계열 데이터의 추세나 분포가 변화하는 지점을 뜻합니다. 따라서 변화점을 감지한다는 것은 어느 특정 지점에서 시계열 데이터의 평균이나 분포가 변화하였는지를 감지하는 것입니다.

이러한 시계열 데이터의 변화점을 감지하는 대표적인 알고리즘과 쉽게 적용할 수 있는 Python 라이브러리를 정리해보겠습니다.

[CUSUM (cumulative sum) 방법]

해당 방법론은 change point 전,후로 평균이 변화한다고 가정하고 그 변화가 일어난 지점을 찾는 방법입니다. 이번 포스팅에서는 Facebook에서 제공한 시계열 분석 패키지 Kats 패키지를 활용하고자 하며, 해당 패키지에서 변화점을 감지하는 순서는 다음과 같습니다. 

1) 초기 initial change point를 설정합니다.

2) change point 전후의 분포를 추정합니다.(가우시간 분포 가정(평균, 분포 활용))

3) change point 전후의 분포를 활용하여 누적 우도비(likelihood ration)를 측정합니다.
- 여기서 대문자 S가 누적 우도비이고 소문자 s가 각 지점에서 우도비입니다.

 4) 누적 우도비는 changepoint 전에 감소하는 추세, changepoint가 지난후 증가하는 추세를 보입니다.  따라서 누적우도비가 최소화되는 지점을 지난 후 누적우도비가 일정 threshhlod를 넘으면 changepoint로 결정합니다.
- 소문자 s로 된 우도비 공식을 보게 되면, change point가 k지점이라고 가정했을 때 k-1 지점에서는 아직 평균이 바뀌기기 전이기 때문에 분모가 더 큰 값을 가질 것입니다. 그렇기 때문에 로그 우도비는 음수가 될 것입니다. 따라서 k지점이 오기전까지는 누적우도비는 계속 음수로 누적되어 감소하는 추세를 나타낼 것입니다.
- 만약 k+1 지점이라면 평균이 바뀐후이고 분자가 커지기 때문에 로그 우도비가 양수가 될 것입니다. 따라서 k+1 지점이 지나면 누적우도비는 다시 커질 것입니다.

https://www.fs.isy.liu.se/Edu/Courses/TSFS06/PDFs/Basseville.pdf

5) 이때 threshhold는 임의로 설정 할 수 있고 kats library에서는 우도비검정시 활용하는 chi-squared분포 기반의 p-value를 threshhold로 사용합니다. 최종적으로 특정 누적우도비의 pattern과 우도검정비를 함께 활용하여 changepoint를 감지합니다.

해당 방법론은 분포를 어떻게 가정하는지 등에서도 다양한 변주가 가능한 알고리즘입니다. 따라서 조금씩 다른 방법으로 적용되고 있는 모습을 확인할 수 있으나 Concept자체는 유사한것으로 보입니다.

Cusum 방법론을 실현하기 위한 코드는 상당히 간단하나, 패키지 설치가 조금 복잡할 수 있습니다. 저는 아래와 같은 순서로 설치했습니다.

    conda install -c conda-forge fbprophet
    pip install kats
    
    [참고] https://github.com/facebookresearch/Kats/issues/308

 

import pandas as pd
import yfinance as yf
import matplotlib.pyplot as plt
from kats.detectors.cusum_detection import CUSUMDetector
from kats.consts import TimeSeriesDatadf = yf.download("AAPL",start="2020-01-01",end="2020-12-31",progress =False)

df = df[["Adj Close"]].reset_index(drop=False)
df.columns = ["time", "price"]
tsd = TimeSeriesData(df)

cusum_detector = CUSUMDetector(tsd)
change_points = cusum_detector.detector(change_directions=["increase"])
cusum_detector.plot(change_points)

change_points
"""
[CUSUMChangePoint(start_time: 2020-07-30 00:00:00, end_time: 2020-07-30 00:00:00, confidence: 1.0, direction: increase, index: 145, delta: 39.61389248745175, regression_detected: True, stable_changepoint: True, mu0: 76.46574550785431, mu1: 116.07963799530606, llr: 451.89567622024873, llr_int: inf, p_value: 0.0, p_value_int: nan)]
"""

[Robust stat detection 방법]

해당 방법론도 Kats 패키지에서 제공하는 방법론이며, 간단하게 알고리즘을 정리해보면 아래와 같습니다.

1) 시계열 데이터를 moving average를 이용하여 smoothing을 수행합니다.

2) smoothing한 시계열 데이터를 특정 window size 만큼 차분합니다.
- window size가 2라면 $T_t - $T_{t-2}를 해줍니다.

3) 차분한 시계열 데이터에 대해서 한 point, point별로 zscore를 계산하고 각 포인트별로 생존함수(1-CDF)를 측정합니다.

4) 해당 생존함수를 활용하여 change point인지 아닌지를 식별합니다.

결국 정리하면 시계열 데이터를 smoothing 하고, 특정 지점들끼리 비교하여 smoothing을 했음에도 불구하고 변화가 큰 지점을 식별하는 방법입니다.

주요 Cusum 방법론과 차이점은 Robust stat detection에서는 한번에 많은 change point를 식별할 수 있다는 것입니다.

코드는 상당히 간단하나, import시 오류가 발생하여, 해당 방법론이 있는 패키지 코드를 제 working folder로 복사하여 module을 import 해주었습니다.

from robust_stat_detection import RobustStatDetector

robust_detector = RobustStatDetector(tsd)
change_points = robust_detector.detector()
robust_detector.plot(change_points)

[참고]

Cusum 방법론

https://www.fs.isy.liu.se/Edu/Courses/TSFS06/PDFs/Basseville.pdf
https://zephyrus1111.tistory.com/400

https://facebookresearch.github.io/Kats/api/kats.detectors.cusum_detection.html
https://github.com/facebookresearch/Kats/blob/main/kats/detectors/cusum_detection.py

Robust stat detection 방법

https://github.com/facebookresearch/Kats/blob/main/tutorials/kats_202_detection.ipynb