[Time Series] Change point Detection

Change Point Detection(CPD)은 시계열 데이터에서 데이터의 특성이 급격하게 변화하는 지점을 찾아내는 기법으로, 이는 데이터의 평균, 분산, 분포 등의 통계적 특성이 변화하는 시점을 탐지하는 것을 목표로 한다(분류를 위한 label이 주어지는 경우도 있음)

후행연구로 시계열의 의미론적 분석, Event 탐지, 이상치 탐지로 이어질 수 있다. 

 

Change Point Detection 

Change Point는 데이터를 표현하는 모델의 매개변수가 갑자기 변하는 지점을 의미하며 CPD는 크게 두 가지 방식으로 나눌 수 있다. 
온라인 방식: 실시간으로 들어오는 데이터 스트림에서 변화를 감지(or  예측), Anomaly or Event Detection이라고도 불림
오프라인 방식: 과거의 전체 데이터(혹은 batch)를 분석하여 CP를 찾아냄, Signal Segmentation 이라고도 불림

 

 

대표적 방법론

1. CUSUM (Cumulative Sum) 알고리즘

CUSUM은 편차(deviation, 관측값에서 평균 또는 중앙값을 뺀 값)의 누적합을 사용해 변화점을 탐지하는 기법이다. 
평균의 변화를 빠르게 탐지할 수 있고, 점진적인 변화나 특정 값 이상의 변화가 발생할 때 유용하기에  산업 분야에서 공정 제어나 품질 관리에 많이 사용된다. 

출처: https://nado-coding.tistory.com/13

 

자세한 내용은 다른 포스트를 참고.

 

2. Bayesian Online Change Point Detection (BOCPD)

https://arxiv.org/pdf/0710.3742

베이지안 확률 모델을 사용해 변화점의 발생 가능성을 실시간으로 계산하는 방법이다. Run renth라는 개념을 사용하며
과거와 현재 데이터 간 사후 확률을 비교하여 변화 발생 가능성을 평가하며, 계산 복잡도가 높지만 불확실성이 높은 상황에서 유용하다. 

보다 자세한 내용은 차후 작성할 기회가 된다면 작성해볼 예정. 

3. PELT (Pruned Exact Linear Time)
PELT는 여러 개의 변화점을 찾는 알고리즘으로 가지치기를 통해 변화점을 찾는 최적화 기반의 알고리즘이다. 

보자 자세한 내용은 차후 작성할 예정. 

4. Binary Segmentation
신호를 반복적으로 두 부분으로 분할하여 재귀적으로 변화점을 탐지하는 방법으로 빠르게 변화점을 찾을 수 있지만 과탐지의 위험이 있기에 단순한 데이터에 사용하는 것이 좋다고 한다. 

 

5. Bottom-up

Binary segmentation과는 반대로 모든 구간을 작은 단위로 나눈 후, 서로 비슷한 구간들을 합쳐 나가는 방법. 최종적으로 변화점이 있는 구간만을 남기는 방법이다. 

6. Gaussian Process-based 방법
가우시안 프로세스와 통계적 가설 검정을 결합한 방법이다. Temporal process의  평균과 공분산 구조가 함께 변화(즉 평균과 공분산 구조가 상수여야한다는 가정이 없음)

아래 논문을 읽어보면서 관련 내용을 정리해볼 예정
https://proceedings.mlr.press/v162/caldarelli22a.html

Adaptive Gaussian Process Change Point Detection

 

7. Kernel based method

SVM이나 기타 ML에서 다루엇듯이, Kernel을 이용하여 고차원에서 최적점을 찾는 방법론. 매핑된 신호의 평균 변화로 변화를 탐지하며 비선형 패턴도 감지할 수 있다. 

관련 내용은 차후에 다룰 예정. 

https://arxiv.org/pdf/2206.01853

 

 

결론은 많은 방법론들이 있고 대부분 확률 베이스 + 시계열 관련 기초적인 개념들은 알고 있는게 편할듯해서 예전 전공수업 자료들을 뒤적뒤적해봐야할 것 같다..! 

 

우선 CUSUM부터 내용정리하면서 논문들마다 주요하게 다루는 방법론들 위주로 개념과 내용을 정리해볼 예정이다. 

 

추가 참고자료

https://www.youtube.com/watch?v=l6GprjLizHo&t=2s

 

- 영상 중반부~후반부에 언근한 논문 

https://arxiv.org/abs/2011.14097

Time Series Change Point Detection with Self-Supervised Contrastive Predictive Coding

-추가 자료: 기업에서 적용한 사례(https://labs.brandi.co.kr/2022/11/30/choiyj5.html)

https://dl.acm.org/doi/abs/10.1145/775047.775148

A unifying framework for detecting outliers and change points from non-stationary time series data | Proceedings of the eighth A