• 목록

[일시] 2023.07.26

[세미나 주제] How to classify Time-series using shapelets

[참고 논문]
1)Time Series Shapelets: A New Primitive for Data Mining
2)A Shapelet Transform for Time Series Classification


*[미흡했던 부분에 대하여 보충한 자료를 업로드 하였습니다. 그리고 녹화한 영상도 함께 첨부하였습니다.]

[요약]
 (1)번 논문이 집필 되었을 당시, Time-Series Classification에서 가장 널리 사용된 알고리즘은 Nearest Neighbor algorithm이다. 최근접 이웃 알고리즘은 구현의 간편함과, 분류의 정확도, 강건함을 기반으로 Time-Series classification task에서 많이 사용되었다. 그러나 분류를 위해 모든 data를 저장하고 searching 해야하기에 computation cost가 높았으며, object가 특정 class로 분류되는 이유를 명확히 interpret하지 못했다. 이에 (1)번 논문의 저자는 'Shapelet'이라는 concept을 제안한다.

 Shapelet이란 Time-Series 'T'의 local한 pattern을 가장 잘 represent한 subsequence를 의미하며, Shapelet은 보편적으로 다음과 같은 절차를 통해 산출된다.
<Finding Shapelets>
1.Generate Candidates : Time-Series T를 sliding-window함으로써 가능한 모든 subsequence를 구하고, 이를 shapelet candidate라고 한다.
2. Check Candidates : 모든 candidates에 대해서, 각각의 candidate를 기준으로 T를 분할하였을 때 기존의 T를 가장 잘 분할하는 subsequence이 해당 Time-Series T의 shapelet이다. (Information gain을 통해 분할 전후의 엔트로피 차이를 확인할 수 있음).
기존의 Shapelet-based algorithms의 분류는 다음과 같은 절차를 거친다.
1)Finding shapelets -> 2)Decision Tree construction -> 3)Classification using decision tree

 그런데 Shapelet을 finding하는 step과 classification의 step이 동일한 procedure에 속한 것을 알 수 있다. 이는 분류를 할 때마다 shapelet를 find해야하기에 train이 오래 걸리면서 computation cost가 높아진다는 단점이 있다. 또한 binary classification에 대한 decision tree을 분류기로 사용하였기에 다중 분류에 대한 상황에 취약했다. 이에 (2)번의 논문은 Shapelet Transform이라는 procedure를 제안한다. Shapelet Transform은 기존의 shapelet based algorithm과 유사하지만 약간의 차이점이 있다. shapelet transform은 caching algorithm을 통해 한 번의 pass로 shapelet을 추출할 수 있게 해준다. 그리고 추출된 shapelet과 각각의 시계열의 거리를 vector값으로서의 새로운 데이터 공간을 생성한다. vector값으로서의 새로운 데이터 공간에서는 decision tree 뿐만 아니라 다른 여러 알고리즘을 분류기로 사용할 수 있다. 이를 통해 기존의 shapelet-based algorithm의 여러 문제를 극복할 수 있다.

 그러나 (2)번 논문의 실험결과를 통해 기존의 shapelet-based algorithm과 shapelet transform을 활용한 classification의 정확도의 차이가 subtle하다는 것을 알 수 있다.
성능이 개선되었다고 볼 수는 없지만 기존의 단점을 극복하였고, shapelet을 find하는 과정과 분류의 과정을 disconnect함으로써 shapelet을 활용하여 시계열을 분류하는 task에서 더욱 다양한 approach를 고려할 수 있게 해주었다는 점에서 큰 의미가 있다고 생각한다.