쉐이플릿 (Shapelet)이란?

본 포스팅에서는 시계열 분류에서 사용되는 개념인 쉐이플릿(Shapelet)에 대해 소개하고, 다음 포스팅에서는 쉐이플릿 탐색에 대해 다뤄보도록 한다. 쉐이플릿은 최근 많은 시계열 분석 과제에서 직관적이고 설명 가능하다는 특성덕분에 많은 주목을 받고 있다. 우리 회사에서도 관심을 가지고 있고, 나도 쉐이플릿과 관련된 논문을 준비중이다.

 

시계열 분류란?

쉐이플릿은 시계열 분류(time series classification)에 사용되는 특징이므로, 시계열 분류에 대해 먼저 소개한다. 시계열 분류는 말그대로 시계열을 분류하는 지도학습 과제로, 샘플이 시계열이라는 것을 빼면 일반적인 분류와 크게 다를 것은 없다. 그러니까 아래 그림에서 왼쪽에 있는 시계열 인스턴스가 입력되면, 이 인스턴스의 라벨이 A인지 B인지를 맞추는 지도학습 문제를 시계열 분류라고 할 수 있다. 

시계열 분류

시계열 분류가 일반적인 분류와 가장 차별화되는 점은 아마도 인스턴스 간 길이가 다르다는 것이다. 즉, 일반적인 분류에 사용하는 데이터 구조는 아래와 같다. 즉, 결측을 제외하면 특징 개수는 모든 인스턴스가 같게되어있다. 

일반적인 분류에 사용되는 데이터 구조

하지만 시계열은 인스턴스마다 길이가 다를 수도 있고, 또 각 시점에서 측정한 값 자체가 특징으로 사용하기에는 무리가 있기도 하다. 그래서 시계열에서 특징을 추출하는 작업이 필요한데, 보통 특징으로 많이 사용되는 것이 통계량이다. 예를 들어서, 시계열 인스턴스마다 평균, 표준편차, 왜도를 추출하면 "일반적인 분류에 사용되는 데이터 구조"에 제시한 테이블 형태의 데이터가 된다. 쉐이플릿도 이처럼 시계열 분류를 하는데 사용하는 특징이다. 

 

쉐이플릿이란?

쉐이플릿은 Ye and Keogh (2009)의 논문에서 처음 제안되었다. 

이 논문에서는 쉐이플릿을 한스텝 한스텝 설명해서, 앞 내용을 안 읽고 쉐이플릿의 정의만 보면 이게 뭔가 싶을 것이다. 그래서 나는 쉐이플릿을 먼저 이해할 수 있게 정의하고 시작하겠다. 쉐이플릿은 "각 클래스에 속한 샘플까지의 거리가 분류 성능 향상에 가장 크게 도움이 되는 부분 시계열"이라고 정의할 수 있겠다.  

자. 이게 무슨 이야기인지 하나하나 살펴보자. 먼저, 부분 시계열은 말 그대로 시계열에 포함되는 조그마한 시계열이다. 

예를 들어서, 아래 그림에서 파란색이 시계열이라 하면, 빨간색은 파란색 시계열에 포함된 부분 시계열이다. 여기서 짚고 넘어가야 하는 점은 한 시계열에서 나올 수 있는 부분 시계열의 개수는 매우 많다는 것이다. 구체적으로, 시계열의 길이가 n이라면 길이가 k (k=1, 2, ..., n)인 부분 시계열은 n-k개가 나올 수 있어, 한 시계열에서 나올 수 있는 모든 부분 시계열의 개수는 n*(n-1) / 2개이다. 

 

자. 그러면 "각 클래스에 속한 샘플까지의 거리가 분류 성능 향상에 도움이 된다"라는 것이 무엇인지 이해해보자.

아래 표와 같이 5개의 시계열 (3개는 클래스 A에 속하고, 2개는 클래스 B에 속함)이 있고, 2개의 부분 시계열이 있다고 하자. 각 셀에 있는 값은 시계열과 부분 시계열 간 거리이다.  

표에서 보면, 부분 시계열 1과 클래스 A에 속한 시계열까지 거리는 가깝고, 클래스 B에 속한 시계열까지 거리는 멀다. 따라서 부분 시계열 1까지 거리가 20 이하이면 클래스 A라고, 20 초과이면 클래스 B라고 판별하는데 도움이 된다. 반면에, 부분 시계열 2는 클래스 A까지 거리와 B까지 거리가 명확히 구분되지 않아, 그다지 도움이 되지 않는다. 만약 부분 시계열 1이 다른 모든 부분 시계열보다 분류에 도움이 된다면, 부분 시계열 1을 쉐이플릿이라 부른다.

그러면 시계열과 부분 시계열 간 거리는 어떻게 계산할까?

논문에서는 아래와 같이 정의하고 있다.

 

그림에서 파란색이 시계열이고 빨간색이 부분 시계열을 나타낸다. 먼저, 부분 시계열을 시계열 맨 앞에 맞춘 다음에 거리를 계산하고, 한 칸 옮겨서 거리를 계산하고, 두 칸 옮겨서 거리를 계산하는 과정을 거친다. 그 가운데 최소 거리를 시계열과 부분 시계열의 거리라고 하는 것이다. 어떤 시계열 [1,2,3,4,5]와 부분 시계열 [3,4] 간 거리를 구하는 예를 들어 설명하면 다음과 같다. 

그림에서 보듯이, [3,4]를 맨 앞쪽에 맞춰서 거리를 계산하고, 한 칸 움직여서 계산하는 과정을 반복하여 거리를 계산한다. 거기서 최소 거리는 0이므로 시계열과 부분 시계열 간 거리를 0이라 정의한다.