[논문 정리] k-Shape: Efficient and Accurate Clustering of Time Series

Time series clustering 분야 논문을 찾던 도중에, 어렵지만 (내겐) 인용도 많이 되고, 구현도 잘 되어 있는 논문이길래 읽어보았다. 또한 무엇보다 선행 연구 정리가 잘 되어 있다! 수학적으로는 모두 이해하지는 못했지만, 일단 어떻게든 읽었으니 기록해두겠다..

 

논문은 자신의 알고리즘을 이야기하기 전에, time-series clustering 을 위해 필요한 성분(?) 들을 하나씩 정리하는데 이것부터 이야기해보려 한다.

 

1. Time-series Invariances : 

시계열 데이터를 클러스터링하려면 이들 간의 distance 를 계산해야 하는데, 시계열 데이터는 어떤 이유로는 시퀀스에 왜곡이 생긴 경우가 존재한다. 이렇게 되면 유사도를 계산할 때, 적합한 결과값이 나오지 않을 수 있는데, 이와 같이, time series 에 대한 distance measure 를 구할 때 필요한 요구 조건에 대한 것이다.

 

- Scaling and translation invariances : 쉽게 말해, 둘 중 하나의 시퀀스에 transformation (ex. linear, aX+b) 을 가했을 때, distance measure 가 바뀌지 않는 성질을 의미한다.

- Shift invariance : 말 그대로 시점에 대한 왜곡에 따라 발생하는, miss-alingment 에 대해, 강건한 성질을 의미한다. 

- Uniform scaling invariance : 두 시퀀스의 length 가 다를 때에 관한 것이다.

- Occlusion invariance : 시퀀스의 일부인 sub-sequence 가 missing 되었을 때에 관한 것이다.

- Complexity invariance : 두 시퀀스의 복잡도가 다를 때에 관한 것으로, 예로 들어 노이즈의 정도가 다를 때에 요구되는 강건함을 의미한다.

 

1.1 Time-series Distance Measures: 

예시로 두 가지 distance measure 가 나오는데, 하나는 Euclidean distance(ED) 이고, 다른 하나는 ED 기반의 Dynamic Time Wraping(DTW) 이다. ED 의 경우, 다들 알고 있을 것 같은 거리 개념일 것이라고 생각이 들고, DTW 는 부끄럽지만, 처음 접하게 되었는데, 두 시퀀스의 길이가 다르거나, 시점이 달라서 발생하는 miss-alignment 의 경우에, iteration 을 돌면서, 시퀀스 벡터 V_1, V_2 에 대한 각각의 인덱스를 매핑해주는 알고리즘이다. 아래에 첨부한 이미지 중, DTW(2)의 우변에 가장 앞의 부분에 사용된 ED 는 원하는 distance measure 로 바꿔주면 된다.

 

Euclidean Distance

 

DTW(1)

DTW(2)

1.2 Time-Series Clustering Algorithms

가장 유명한 알고리즘으로는 agglomerative hierachical, spectral, partitional clustering 이 있다. 그 중 partitional clustering 에는 k-medoids와 k-means 가 있는데, k-medoids 알고리즘의 경우, dis-similar matrix 를 줄 수 있고 centroid 를 실제 input data 중에 선택하기 때문에, sequence 들의 shifting, translation, scale 을 고려할 수 있는 distance measure 를 고려할 수 있는 반면, k-means 는 알고리즘을 학습하며, averaging 을 통해 artificial sequence 를 만들기 때문에, 이론적으로 ED가 아닌 distance measure 를 사용하는 것이 어렵다고 한다. 이를 보안하기 위해, ED를 사용한 DTW를 사용한 k-means 연구가 있다고 한다.

 

1.3 Time-Series Averaging Techiniques

averaging sequence 는 clustering task 에서 centroid 에 관한 것인데, time-series 문제에서 sequence 를 다루는 테크닉이 다양해짐에 따라 (ex. DTW), 단순 arithmetric mean 이 아닌, 다양한 방법이 제시되고 있음을 이야기한다.

 

2. k-SHAPE Clustering Algorithm

해당 알고리즘에 대한 설명은 총 2 가지로 나뉘어질 수 있다.

1. distance measure -> normalized cross-correlation (NCC)

2. compute centroid of clusters -> time-series shape extraction

 

2.1 Distance measure

본 논문에서는 cross-correlation 이라는 distance measure를 사용한다. time lagged correlation 이라고 생각하면 쉽다.

아래 이미지 중 CC(1) 가 그 예시인데, sequence x 에 한 쪽의 방향에 s 길이 만큼의 padding 을 주면, s 만큼의 time lagging 또는 leading 이 발생하게 된다. 두 sequence 의 길이가 m 으로 같고, 발생 가능한 lagging의 최대 경우를 고려하면, sequence 의 길이는 2m-1 이 된다. (-1 이 붙은 이유는, 최소 하나의 element 는 겹쳐야 하기 때문이다.)

CC(1)

위와 같이 padding 을 주고, ED를 계산한다. cross-correlation 의 목적은 유사도가 최대가 되는, shifting point 를 찾는 것이다. 아래의 그림 CC(2) 에 따르면, w 가 된다.

CC(2)

CC(3)

저자가 최종적으로 사용하는 distnace measure 는 normalized cross-correlation 인데, 공식은 아래 이미지의 가장 아래 우변을 따른다. 시퀀스 데이터에도 z-normalization 을 거쳐서 scale을 맞춰주지만, distance measure 에도 normalization를 적용해주는 것이 distance measure에 높은 성능 향상을 보였다고 한다.

NCC

2.2 Shape-based distance

NNC 는 가까움의 정도를 의미하니, 먼 정도는 1-NNC 가 된다. max_w 는 cross-correlation 의 목적에 따른 것이다.

SBD

2.2 Efficient compuation of SBD

convolution theorem 에 따르면, cross-correlation 은 아래의 식으로 쓰일 수 있으며, 이는 기존 복잡도인 m^2 를 m*log(m) 으로 줄일 수 있다고 한다. (Fast Fourier Transform 을 사용할 경우)

DFT and IDFT used equation

2.3 Algorithm 1

여태까지 이야기한 것을 한데 모아서, 하나의 함수를 만들면 아래와 같이 되는데, 두 개의 z-normalized 시퀀스 x,y 넣어서, SBD 거리 값과 sequence x 와 align 된 y` 를 함수를 상상하면 된다. algorithm 1 은 거리 값과 sequence alignment 를 해주는 역할을 한다.

2.2 Time-series Shape Extraction

해당 섹션은 k-shape 알고리즘이 centroid sequence 를 어떻게 정의내리는지에 대한 것이다. 저자는 단순 averaging 보다, SE(1) 에 따른, centroid sequence vector 가 더 성능이 좋았다고 이야기하였으며, SE(1) 식은 k-means 에서 사용되는 minimize optization 문제를 (k-means 에서 사용되는 ED 는 distance이기 때문) 거꾸로 maxmization 으로 푼 것이다. (NCC는 similarity이기 때문) square 값을 쓴 이유는, 따로 명시되지는 않았지만, 무언가 convex optimization(?) 과 관련된 것이 아닐까 유추된다... 

 

SE(1)

2.3. Algorithm 2

 

아래의 함수는 주어진 X 에 따른 최적의 centroid 벡터를 반환한다. 아래의 algorithm 2 를 보면, random initialized 되어 있거나 이전의 함수의 결과값으로 초기화되어 있는 C 는 우리가 가지고 있는 sequence x 와 loop 을 돌면서 SBD 를 최소화하는 aligned sequence x` 를 반환하게 된다. 즉, C 와 x` 는 align되어 있다.

SE(2)

이에 따라, SE(2) 를 최대화 하는 것이, aligned sequence 두 개의 NCC 를 최대화하는 것과 같게 된다.

 

SE(3)

간단히 표현하기 위해 SE(3) 의 과정을 거치고,

SE(4)

I:identity matrix    O:one matrix

현재 centroid sequence vector 가 z-normalized 가 되어 있지 않기 때문에, Q vector 를 곱해줌으로써, demean 효과를 가져오고,  centroid vector 의 l2 norm 으로 나눠줌으로써, z-normalization 을 mu 에도 적용한다. SE(2) 부터 SE(4) 까지는 rayleign Quotient 라는 maximization 문제로 풀 수 있다고 하며, SE(4)의 M matrix 의 1st eigenvector 와 최적의 mu_k 가 일치한다고 한다. 그렇다고 한다...

3. Overall Algorithm

전체적인 알고리즘을 보며, reminding 을 해보자. 처음 refinement step (algorithm 2) 에서는 주어진 sequence 에 따라 centroid vector 를 정한다. k 개의 cluster 갯수로 정했다면, 이 refinement step 을 k 번 해준다. 그 후, 우리가 가지고 있는 데이터가 어떤 클러스터에 속하는 지를 SBD 를 기준으로 업데이트해준다.

 

정리해보니, 참 간단해보인다.

 

4. Conclusion

사실 딥러닝 기반의 time-series clustering 논문을 읽고 난 후에, 인용 논문을 보다가, 관심이 생겨 있게 되었는데, 역시 알고리즘은 비-딥러닝 논문이 확실히 복잡한 것 같다.. 그래도 결국 구현체 적용에 있어서는, 비-딥러닝이 효율적이고 즉각적이여서 자주 쓰는 편인데, 무엇이든 알고 써야 하니 읽기를 잘 한 것 같다