Anomaly Detection in Time Series Data Based on Unthresholded Recurrence Plots (2018)

Anomaly Detection in Time Series Data Based on Unthresholded Recurrence Plots (2018)

Abstract 

- 시계열 데이터에서 이상치를 감지하는 것은 매우 큰 흥미를 끌고 있다. 비선형 방법 기반의 새로운 framework을 제안함

1. time-dependent한 URP(Unthresholded Recurrence Plots)를 사용

• 시계열 데이터를 나타내는 이미지 데이터  생성하고, 비선형적인 특징을 찾기 위함

2. ELM-AE (Extreme Learning Machine Auto-Encoder) 를 이용

• 주된 URP 데이터를 학습시킨 모델 생성

3. 잔차 계산 (residual error)

• 시계열 포인트에서 anomaly score로 잔차를 사용

- 해당 framework 은 unlabeled 된 dataset을 사용해서 비선형 문제에 잘 동작할 것으로 예상

>> 즉 실제 실험 결과는 없음...단순 제안하는 논문임

1. Introduction

- 이상탐지는 비정상적인 패턴(예상에서 벗어난)을 찾는 문제

- 이러한 이유로 기후변화, 센서, 헬스 모니터링 데이터에서 많이 활용되고 있음

- 다양한 이상탐지 방법들이 많이 제안되고 있고, 주로 분류, 최근접 이웃, 클러스터링, 통계적검증을 기반으로 한 방법들로 나눌수 있음

- 시계열 데이터에서 이상탐지 기법은 최초에 AR모델 (자기회귀)을 이용한 연속적인 sequential poin를 탐지하는 것 또는 면역시스템 기법으로 미리 정상데이터를 학습한 모델을 이용하는 방법임

- 그러나, 실제로 정상적 데이터나 label 이 있는 데이터를 모델학습에 사용할 수 없는 경우가 많음

- 그리고 또다른 중대한 것은 시계열 데이터를 대표할 수 있는 feature를 추출하는 것임

• Discrete Wavelet Transform (DWT) 

• Discrete Fourier Transform(DFT)

• Symbolic Aggregate Approximation (SAX)

• 위 세가지 모두 시계열 데이터에서 의미있는 Feature를 뽑는 일반적인 방법

- 위 방법 외 시계열 데이터를 표현하는 단순한 방법

• time-dependent recurrence quantification analysis (RQA)

• Recurrence Plots을 기반으로 생성

- this paper 에서는 Unthresholded RPs (URP)를 이용함 

• URP는 RP보다 더 많은 시계열 정보를 가지고 있고, 튜닝할 파라미터를 요구하지 않음

- 분석을 위해 사용하는 Model인 ELM-AE는 window-sliding RP를 기반으로 학습

 

2. Anomaly Detection Algorithm Based on URPs andELM-AE

- 전체적인 이상탐지 로직

• URPs : 시계열 데이터 이미지화 (Feature extraction)

• ELM-AE : AE의 Encoder & Decoder 비교를 통해 score 도출 → 이상탐지 

 

 

2.1 Recurrence Plots

- 시계열 데이터를 이미지화 시키는 방법으로 d-dimensional 한 space 위에 trajectory 데이터를 reconstruct 하는 방법

- 예를 들어, trajectory 데이터 X  = {x1, x2, …, xi, …, xn} 가 있을때,

   xi 에서 대표되는 데이터는

와 같다.

- 즉, m차원으로 x를 표현하면

array 가 나오게 됨

 

- 만들어진 array를 가지고, RP를 구성할 좌표를 만듦

 

- 식(2) 에서 e 엡실론은 매우 중요한 parameter로 그 값에 따라 RP를 보다 직관적인지, 추상적인지 표현할 수 있음

- 근데, 사실이 이 parameter를 정의하는 것은 매우 어려운 일이라, 이 논문에서는 threshold distance parameter를 제거하기 위해 pairwise distance를 이용하였음

- 식 (3)은 URPs 를 나타냄

2.2 Extreme Learning Machine

- Extreme Learning Machine은 single layer feed-forward NN (SLFN)을 기반으로 하고 있음

- Input data는 L dimensional한 ELM의 random feature space에 맵핑됨

- 익히 아는 dnn의 개념과 유사하지만 학습방식이 다름

- 일반적인 NN 학습방법 : Foward propagation → Back propagation을 반복하며 weight 를 학습

- ELM : back propagation을 쓰지 않고 Moore-Penrose generalized inverse matrix를 이용하여 weight 를 구함

 

[참고자료]

1. 일반적인 NN 나타내면 아래 그림과 같음

 

1. 위 그림을 토대로 H B T는 아래와 같은 수식으로 정의가능

1. 결국 Model은 아래 식과 같이 가중치와 B를 곱한 값과 실제값 T의 차이를 최소화하는 것을 의미

1. weight 매트릭스인 B는 Moore-Penrose 방식을 도입하여 수학적으로 추정할 수 있음

1. 결국 최종 추정된 B는 아래 식과 같이 계산 가능

 

• 즉, Back propagation없이 수학적 연산으로 빠르게 연산이 가능 (ELM의 장점)

2.3 Extreme Learning Machine Auto Encoder

- Extreme Learning Machine은 single layer feed-forward NN (SLFN)을 기반으로 하고 있음

- self supervised learning → input과 output 값이 같음

- 초기 hidden node의 weight와 bias는 직교행렬로 분배

- structure 구성은 아래 그림과 같이 compressed, equal, sparse로 나눌수 있음

- Johnson-Lindenstrauss Lemma 논문에서는 Structure를 동등한 dimension으로 구성함

• 계산하면 아래와 같은 식으로 weight 추정 가능

 

2.4 Proposed Algorithm for Anomaly Detection

- 제안하는 알고리즘은 URP와 ELM-AE의 강점을 조합한 알고리즘

- URP는 비선형적인 패턴을 가진 시계열 데이터를 나타낼 수 있고, ELM-AE는 URP를 이용하여 자동으로 학습하고, 이상치를 찾을 수 있음

- 알고리즘은 normalizing을 하여 input data에 넣음 (standardization)

- sliding하며 URP 데이터를 만들고, 이를 ELM-AE 학습 시킴

- 모델의 잔차 residual error score 산정으로 이상치 탐지

 

3.Conclusion

- 시계열 이상탐지 framework를 제안함

- RP의 한계들을 URP로 극복하면 된다고 제안

- 제안된 모델을 multivariate time series 데이터로 확장해서 적용할 것이라고 함

 

 

출처 : HU, Min, et al. Anomaly Detection in Time Series Data Based on Unthresholded Recurrence Plots. In: International Conference on Applications and Techniques in Cyber Security and Intelligence. Springer, Cham, 2018. p. 477-484.