Abstract

• Dynamic time warping은 시계열의 유사성을 측정하는 효율적인 방법이다. 그러나 노이즈와 이상치로 인해 Singularity 문제와 편향의 위험에 노출될 수 있다. DTW의 시간 복잡도는 시계열 길이에 비해 2차적이기 때문에 실시간 Application에 적용할 수 없다. 이에 따라 Noise와 이상치의 영향을 줄이기 위한 RobustDTW라는 새로운 유사성 측정 방법을 제안한다. RobustDTW는 Temporal graph trend filtering을 활용하여 trend를 추정하고 시간 왜곡을 최적화한다. 효율성을 향상시키기 위해 저해상도에서 Trend와 warp function을 추정한 다음 고해상도에서 반복적으로 refine하는 다단계로 이루어진 Framework를 제안한다.

Introduction

• Dynamic time warping은 시계열의 유사도를 측정하는 방법으로 다양항 Task에 사용되지만 한계가 존재한다. 첫째, 실제 시계열 데이터는 종종 Noise와 이상치에 의해 오염된다. DTW는 시간 축을 따라 늘어나거나 줄어드는 것만 고려하고 Noise와 Outlier을 처리하는 것은 무시한다. 이는 시계열 간 거리를 편향시킬 수 있으며 Time-series의 단일 지점이 다른 Time-seriesdml 큰 하위 섹션에 mapping되는 Singularity 문제로 이어질 수 있다. 둘째, DTW의 Time & Space complexity는 Time-series의 길이에 비해 2차적이기 때문에 긴 시퀀스 분석에 적용하기가 어렵다. 따라서 본 논문에서는 RobustDTW라는 이름의 새로운 방법론을 제안한다.

Methodology

• RobustDTW는 Noise와 Outlier를 필터링하기 위해 Robust trend를 사용한다. 구체적으로 말하자면 교대로 Time warp function과 Detrend Time-series를 추정할 것을 제안하며 아래 2개의 작업을 반복적으로 수행한다.

1. Time warp funciton을 고정한다음 Detrended Time-series를 추정한다.
2. 추정된 Detrended Time-series를 고정하고, 이를 기준으로 Time warp function을 추정한다.

Step 1: Robust Self-Detrending

• 대략적으로 Noise와 Outlier의 효과를 제거하기 위해 각각의 시계열에 Robust trend filtering을 사용한다.

• Filtering을 통해 위 수식과 같이 시계열이 분해가 된다. 본 논문에서는 Robust trend filtering을 사용하였기 때문에 이상치에 강하며 느리고 갑작스러운 Trend 변화를 모두 포착할 수 있다.

Step 2: Multi-Level Representation

• Multi-level representation은 Downsampling을 여러번 반복하여 얻어지는데, 해당 Downsampling은 level t representation을 얻을 때까지 진행하며 high-level representation은 lower resolution을 가진 Time-series에 해당한다고 말할 수 있다.

Step 3: Projection and Upsampling

• level t Time-series에 FastDTW를 적용하여 Warping index alignment를 얻고, 해당 시점의 Representation을 기준 Trend 추정치로 사용한다. 이후 이 작업을 반복하는 과정에서 이전 level의 warping path를 Upsampling하고 반지름 r에 의해 정의된 Extra searching width를 사용하여 제약 조건을 생성한다.

Step 4: Time Warping Alignment

• Step 3를 통해 얻은 Warping constrain으로 DTW를 실행하여 Warping path를 세분화한다.

Step 5: Temporal Graph Detrending

• 이 단계에서는 해당 시점의 이웃뿐만 아니라 유사한 peer Time-series를 고려하여 더욱 정확한 Detrended Time-series의 u와 v를 추정한다.

Step 6. Iterative Processing

• 더 나은 성능을 달성하기 위해 Step 3부터 5까지 반복하여 수렴할 때까지 Time warp function과 Trend estimates를 업데이트 한다. 또한, Higher resolution에서 Time warp funciton을 계산할 때 이전 단계에서 계산된 Time-warp function을 초기값으로 사용하여 계산 복잡성을 크게 줄인다.

Experiments

• RobustDTW의 성능을 검증하기 위해 Outlier detection과 Periodicity detection Task를 수행하여 기존 DTW-based 방법론들과의 성능 비교를 실시하였다.
• 위 두개의 Table에서 볼 수 있듯이 RobustDTW가 두가지 Task 모두에서 기존의 DTW-based 방법론들의 성능을 능가하는 것을 볼 수 있다.

Conclusion

• 본 논문에서는 새로운 DTW-based 방법론인 RobustDTW를 제안한다. 해당 방법론은 Alternating approach로 Time warp function과 Trend를 동시에 추정하고 Multi-level framework로 이를 가속화한다. 기존의 DTW와 그 변형된 방법론들과 비교했을 때 빠르며 Noise와 Outlier에 Robust하다.