Step Data Clustering via Thick Pen Transformation

Abstract

This thesis studies clustering time-series data by suggesting a new similarity measure and an optimization algorithm. To illustrate, we propose a new time-series clustering method based on the Thick Pen Transformation (TPT) of Fryzlewicz and Oh (2011), whose basic idea is to draw along the data with a pen of given thicknesses. The main contribution of this research is that we suggest a new similarity measure for time-series data based on the overlap or gap between the two thick lines after transformation and smoothing. This method of applying TPT to measure the association exploits the strengths of the transformation; it is a multi-scale visualization technique that can be defined to provide some information on neighborhood values temporal trends. Moreover, we further suggest an efficient iterative clustering optimization algorithm appropriate for the proposed measure. Our main motivation is to cluster a large number of physical step count data obtained from a wearable device. Moreover, a numerical simulation is performed to compare our method to some existing methods, suggesting that the proposed scheme can be adapted to more general cases.

본 학위 논문에서는 시계열 자료의 군집화 방법을 탐색하며 새로운 유사도 척도와 최적화 알고리즘을 제시한다. 보다 구체적으로 Fryzlewicz and Oh 가 2011년 제시한 굵은 펜 변환법에 기반하여 새로운 시계열 자료 군집화 방식을 제안한다. 이 변환법의 기본 발상은 두께가 있는 굵은 펜을 이용하여 자료를 따라 그리는 것이다. 우리 연구의 주된 기여는 변환과 평활화 작업을 진행한 후 얻어지는 두꺼운 선들 끼리의 겹침 혹은 격차를 기반으로 두 시계열 자료의 유사성을 정의하는 것에 있다. 굵은 펜 변환의 강점은 이것이 다중 척도의 성질을 띄는 시각화 기법이고, 인접한 값들의 추세를 반영하여 변환이 정의될 수 있다는 것에 있다. 따라서 해당 변환을 이용해 연관성을 측정하는 우리의 방식은 앞서 언급한 강점들을 적극 활용하게 된다. 나아가 우리는 제안한 유사도 척도를 이용하여 군집화를 최적화 문제로 정의하고, 이를 해결하는 효율적인 반복 알고리즘을 제시한다. 본 연구는 기기를 통해 측정된 대용량의 걸음 수 자료를 군집화하여 비슷한 걸음 양상끼리 분류하는 것을 목표로 시작되었다. 나아가 합성 자료에 대해 군집화를 진행하며 기존의 다른 방법들과 성능을 비교하고, 우리의 방법이 다른 자료에도 일반적으로 적용 가능하다는 것을 확인한다.