GENDIS: GENetic DIscovery of Shapelets

시계열 분류 분야에서 형태선(shapelets)은 특정 클래스에 대해 구분 가능한 작은 시계열을 의미한다. 기존 연구에서, 입력 시계열과 다양한 구분형 형태선 사이의 거리를 입력으로 사용하는 분류기들이 다양한 데이터셋에서 최첨단 성능을 달성할 수 있음을 입증하였다. 또한 이러한 형태선은 쉽게 시각화할 수 있어 해석 가능성이 높은 특성을 지니고 있으며, 종종 장기적 데이터가 존재하는 의료 분야와 같은 중요한 분야에서 매우 매력적인 특성으로 평가받고 있다. 본 연구에서는 진화 계산(evolutionary computation)을 기반으로 한 새로운 형태선 탐색 패러다임을 제안한다. 제안된 방법의 장점은 다음과 같다. (i) 기울기 기반(gradient-free)이므로 국소 최적해에서 탈출하기 쉬우며, 적합한 후보를 더 쉽게 탐색할 수 있으며, 미분 불가능한 목적함수에도 적용 가능하다. (ii) 브루트포스 탐색(brute-force search)이 필요 없어 계산 복잡도가 수개 차수만큼 크게 감소한다. (iii) 형태선 자체과 함께 형태선의 총 개수 및 각 형태선의 길이도 함께 진화되므로, 미리 설정할 필요가 없어진다. (iv) 단일 형태선이 아닌 전체 형태선 집합을 동시에 평가함으로써, 최종적으로 더 작은 크기의 형태선 집합을 도출할 수 있으며, 유사한 형태선 간의 중복이 줄어들어 유사한 예측 성능을 유지할 수 있다. (v) 탐색된 형태선이 입력 시계열의 부분수열(subsequence)일 필요가 없다. 본 연구에서는 이러한 제안된 장점들을 실험을 통해 검증한 결과를 제시한다.