Time series clustering에 대한 내용으로 세미나를 진행하였다. 시계열 데이터 분석의 필요성은 점차 늘고 있다. 시계열 데이터는 기존의 다변량 데이터와 달리 시간 개념이 포함된다. 따라서 분석을 함에 있어 시계열적인 특성 (scale- translate-, shift invariance 등)을 고려해야한다. 만약 시계열 데이터 분석을 수행해본다고 가정해보자. 위의 시계열 데이터의 특징을 반영하여 분석할 수 있는 방법은 1) 딥러닝을 활용하는 방법 / 2) DTW를 필두로한 유사도 기반의 알고리즘을 사용하는 방법과 같이 크게 2가지로 나눌수가 있다. 특히 유사도 기반한 방법은 대표적으로 k-means / knn(1nn)이 있다. 즉, 우리가 유사도 기반으로 시계열 데이터를 분석한다고 할때 사용할 수 있는 방법이 극히 제한적이라는 것이다. 특히 clustering은 더욱 그러하다. 따라서 이번 세미나에서는 아래의 내용을 다뤘다.

1) DTW 및 DTW 확장 방법

DTW를 사용하여 시계열 데이터간의 유사도를 산출하는 것은 매우 유용하게 사용된다. 그러나 DTW는 그 자체의 연산량이 상당하기 때문에 computational cost가 매우 높다. 따라서 DTW를 다시 한번 리뷰하고 연산량을 개선하기 위한 cDTW 및 LB_Koegh과 같은 방법에 대해 다뤘다.

2) TADPole algorithm

이와 같은 선상으로 DTW를 사용하여 군집화를 수행할때, 좀더 효율적으로 계산을 하기 위한 군집화 기법에 대해 다뤘다. DTW 유사도를 산출하는데 있어 상한과 하한을 정의하여 모든 관측치 간의 유사도를 계산하는것이 아니라 필요한 계산만을 수행하여 계산량을 효과적으로 줄임과 동시에 군집화 시간을 효율적으로 단축시킬수 있는 방법론에 대해 다뤘다.

3) K-shape clustering algorithm

일반적으로 유사도를 정의함에 있어 DTW가 아닌 cross-correlation을 통해 유사도를 정의하였다. 두 개의 시계열을 시간축을 기준으로 움직이면서 둘 간의 내적이 최대가 되는 값을 두 관측치의 유사도라 정의하고 이를 shape based distane (SBD)라고 정의하였다. 일반적인 과정은 k-means와 유사하지만 거리를 정의함에 있어 두 관측치간의 cross-correlation을 통해 정의하였다는 점이 상당히 인상깊은 부분이라 할 수 있겠다.

​

​오늘 세미나 주제는 time series clustering algorithms였다. clustering을 위해 기본적으로 필요한 것이 관측치간의 유사도이다. 따라서 time series 데이터에서 유사도(거리)를 구하는 DTW, DTW의 변형들에 대한 기본설명과 Density Peak이라는 Science지에 게재되었던 clustering 알고리즘에 대해 기초 설명이 있었다. 그 이후 어떻게 Density Peak을 time series데이터에 적용하였는지, DTW연산을 빠르게 하기위해 사용한 방법이 무엇인지 초점이 맞춰져서 Tadpole clustering 설명이 이루어졌다. 또한 K-means방법이 time series 데이터에 적합하게 변경된 K-shape clustering도 다루어졌다. 굉장히 방대하고 어려운 알고리즘인대도 불구하고 발표가 핵심을 쉽게 전달되어 배우는 것이 많았던 세미나였다. 오늘 세미나는 univariate time series 데이터에 대한 알고리즘이라고 이해되었다. multivariate time series에 해당 알고리즘들이 사용가능한지 이를 효율적으로 처리하기위해 어떤 연구가 있었는지 살펴보고 싶어졌다. 또한 따로 time series의 유사도를 구하는 DTW 이외의 많은 방법을 한번 정리해 볼 필요가 있다고 생각되었다. 많은 아이디어와 인사이트를 준 오늘 세미나 발표를 준비한 한규오빠에게 노고에 감사를 표하면서 세미나 후기를 마무리하겠다.

이번주는 강남 토즈에서 세미나가 열렸다. 한규 형이 “Time Series Clustering” 이라는 주제로 발표하였다. 시계열 데이터 분석에서는 크게 2가지로 나눌 수 있다. Deep learning 기반 접근법과 Similarity (Distance) 기반 접근법이다. Deep Learning의 경우 Classification 문제는 많이 다루고 있지만 Clustering 문제는 많이 다루지 못한다. 따라서, 이번 세미나에서는 Similarity 기반 Clustering 접근법에 대해 발표를 들을 수 있었다. 시계열 분석에서 가장 문제가 되는 것이 Time Shift 되어 있는 것이다. 이것을 해결하기 위해 Dynamic Time Warping 기법을 활용한다. 하지만, 이 기법은 시간이 굉장히 많이 걸린다. 이러한 Time Complexity를 해결하기 위해 많은 기법들이 소개되었다. 그 중 가장 흥미로웠던 것은 Density Peak이다. Density Peak의 경우 Local density와 Minimum Distance from Points of Higher Density를 계산한다. 이 두 가지 지표를 활용하여 Cluster를 이루는데, 굉장히 간단하면서도 파워풀한 알고리즘이였다. 하지만, Density Peak에서도 많은 하이퍼파라미터가 존재하기 때문에 완벽한 알고리즘이라고 판단하기 어려웠다. Density Peak의 개념을 확장하여 TADPole리하는 Clustering 알고리즘을 설명하였다. TADPole은 기존 Distance 기반 Clustering 기법보다 훨씬 더 빠른 결과를 가지고 왔다. Density Peak에서 Local density를 계산할 때 사용하는 기법을 활용하여 계산량을 확실하게 줄이는 것을 확인할 수 있었다. 그 다음으로 소개해준 알고리즘은 K-shape Clustering이다. 이 기법은 Cross-Correlation을 계산하여, 유사도를 측정하는 것이다. 이 기법 또한 신선하였다. 굉장히 많고 어려운 것을 차근차근 준비해준 한규형에게 감사하다는 말을 전하고 싶다.

이번 세미나의 주제는 Time series clustering algorithms이었다. 시계열 데이터가 지니는 기본적인 특성에 대한 설명으로 세미나는 시작 되었다. 다음으로 Time series clustering algorithms의 이해를 돕기 위한 배경 지식으로 DTW, variance of DTW, Density Peak에 대한 설명이 이어졌다. 배경 지식에 대한 설명 이후 잠시 휴식 시간을 가진 뒤, Time series algorithms 중 Tadpole algorithms과 k-shape algorithms에 대한 내용을 들을 수 있었다. Time series 데이터를 분석하기 위해서는 sequence 자체가 가지고 있는 패턴을 고려하면서 동시에 시간 축에 따른 misalignment 등을 고려해야 한다. 배경 지식으로 처음 설명을 들었던 DTW 방법론은 이 두가지를 고려해서 제안된 것이다. DTW란 축이 다른 두개의 시계열 데이터의 시간 축을 어느정도 유사하게 만드는 방법론 중 하나이다. 이를 위해서 두개의 시계열 데이터의 유사도를 토대로 Distance matrix를 만든 이후 유사도의 총합이 최소가 되는 길을 찾는 것이 DTW 방법론의 핵심이다. 하지만 이 방법론의 문제점은 관측치의 증가에 따라 계산 시간이 지수승으로 매우 크게 증가한다는 것이었고, 이를 해결하기 위해 cDTW, Lower bound(of keogh) 등이 제안되었다. Clustering 기법으로는 Density Peak에 대한 설명이 뒤를 이었다. Density Peak은 Local Density(

오늘 세미나 주제는 Time Series Clustering 에 대한 내용이었다. 시계열 데이터에 대한 일반적인 분석방법으로는 딥러닝 기반과 유사도 기반으로 크게 나뉜다. Clustering 최근 연구에서는 유사도 기반의 접근법을 주로 사용하여 유사도 기반의 접근법에 대해 집중적으로 설명하였다. 시계열 데이터 간의 유사도를 측정하는데는 DTW(Dynami time warping)와 Euclidean distance를 사용한다. DTW는 misalignment와 time series length를 고려하여 유사도를 구할 수 있고, cost matrix에서 합의 최소가 되는 path를 구하여 유사도를 측정한다. 하지만 계산량이 많아져 효율적인 계산을 위해 다양한 방법들이(cDTW, lower bound ..) 제시되었다. Density peak 은 밀도 기반의 군집화 방법으로 Lcoal density 와 Minimum distance from points of Higher Density 요약 값을 추출하여 두개의 요약 값을 곱한다. 곱한 값에 대해 상위 K개를 군집의 중심으로 선택을 하게 된다. Tadpole clustering 은 시계열 데이터의 적용가능한 Density peak 알고리즘으로 input으로는 DTW를 사용한 matrix을 사용한다. 여기서 DTW를 효율적으로 계산하기 위해 Lower bound의 방법이 사용된다. Lower bound는 Euclidean distance로 계산하고 Upper bound는 DTW distance로 계산한다. 군집 중심에서의 LB 와 UB를 기준으로 수치가 낮은 최소 거리를 구하여 계산량을 크게 줄이면서 군집화를 하게 된다. K-shape clustering은 Shape-based distance(SBD)를 구하여 유사도를 산출한다. 유사도는 SBD 값이 0에 가까울수록 두 시계열 데이터가 유사하다고 할 수 있다. Shape extraction은 SBD를 통해 유사도를 산출하고 군집 내에서 Sum of squared correlation을 최대화 하도록 군집의 중심을 최적화 식을 통해 산출하여 효율적인 군집화를 한다. 전반적으로 시계열 데이터의 유사도 산출을 어떻게 효율적으로 계산할 것인가에 대한 방법들을 배우게 되었고 이와 관련한 clustering 들을 접해 볼 수 있었다. 많은 것을 배울 수 있었고, machine learning에 대한 깊이 있는 공부 및 연구를 생각해볼 수 있는 좋은 시간이었다. 발표를 해준 한규형에게 고마움을 전한다.

Time series clustering은 다양한 분야에서 요구되나, time series 또는 sequence data가 가지고 있는 특성 때문에 다변량 데이터를 분석하기 위한 일반적인 알고리즘을 그대로 적용하기 어렵다. Time series clustering을 위해서는 time series 간 유사도를 잘 정의해야 하는데, time series에는 misalignment, 시간에 따른 패턴 등 다변량 데이터에서는 나타나지 않는 특성들이 있기 때문에 유사도를 잘 정의하는 것이 쉽지 않다. 이러한 문제는 전통적으로 dynamic time warping (DTW)를 통해 해결해왔다. 하지만 dynamic time warping(DTW)은 게산복잡도가 상당히 높기 때문에, 다수의 time series를 clustering하는 상황에는 적합하지 않다. DTW를 보다 효율적으로 계산하고, time series 간 유사도를 잘 정의하여 clustering을 수행하고자 하는 다양한 연구들이 제안되었고, 그 중 일부가 이번 세미나에서 리뷰되었다. 주제는 time series clustering이었지만, TADpole 알고리즘을 소개하기에 앞서 설명된 density peak이라는 clustering algorithm이 더 흥미로웠다. 최근 neural network 기반의 time series 데이터 분석이 주로 이루어지고 있는데, neural network가 아닌 알고리즘을 통해 time series 데이터를 분석하는 방법론을 접하게 되어 의미있었다.

최근 센서 기술 발전으로 다양한 분야에서 많은 종류의 데이터 수집이 가능하게 되면서 시계열 데이터 분석에 대한 관심이 증가하고있다. 금일 세미나는 이러한 시계열 데이터를 효과적으로 분석하는 방법론에 대하여 진행 되었다. 특히 시계열 데이터를 효과적으로 클러스터링하는 방법에 대하여 진행 되었다. 시계열 데이터가 가지는 scale 이나 shift invariance로 인하여 두 시계열 관측치 간의 유사도 측정방법으로는 해석에 한계가 있다. 시계열 유사도 분석에 주로 사용되는 방법은 DTW 가 있으며, 이는 minalignment 와 time series length 를 고려하여 유사도 산출이 가능하다. 이 과정에서 cost matrix 를 계산하여야 하는데 계산 복잡도가 커 시간이 많이 걸리는 단점이 있다. 연산을 효율적으로 하기 위하여 band를 주거나 lower bound 개념을 도입하여 계산량을 줄이는 방법론들이 있었다. 최근 TADPole 이라는 방법론이 제안되었는데 density peak 의 개념과 유사한 방법론이다. Lower bound 값을 이용하여 특정 criteria 에 있는 데이터로만 계산을 하기떄문에 계산량을 상당히 줄일 수 있다. 또 다른 방법으로 k-shape clustering을 소개하였는데 이는 k-means 와 상당히 유사하다. 여기에서는 시계열 데이터간의 거리를 측정하기 위해서 cross-correlation 을 이용하여 수행되었다. 이러한 방법론은 기존의 알고리즘에 대비하여 계산시간을 획기적으로 줄이고 있기 때문에 실제 환경에서 많이 사용될 수 있을 것 같다. 오늘 세미나를 통하여 알고리즘의 수행 시간에 대해서는 큰 의미를 두지 않고 있었는데 알고리즘의 효율성도 상당히 중요한 부분이라는 것을 이해하였으며, 실제 환경에 적용할 때 어떻게 하면 더 효율적으로 계산할 수 있을지에 대해서도 많은 고민이 필요하다는 것을 느꼈다. 시계열 데이터에 대한 전반적인 이해를 할 수 있었던 좋은 세미나 였다.​

금일 세미나에서는 한규형이 시계열 데이터를 활용한 클러스터링 기법에대해 설명을 해줬다. 기본적으로 시계열 데이터가 갖는 중요한 속정 중 alignment 가 맞지 않는 특성 때문에 시계열 데이터간 거리를 계산하기 어렵다. 때문에 오늘 소개한 여러 시계열 데이터 군집화 알고리즘은 dynamic time wrapping (DTW)를 사용하여 거리를 계산한다. 그런데 DTW는 computation cost가 높기 때문에 샘플 수 가 많은 실제 데이터에는 적용하기 어렵다. 이러한 한계를 극복하기 위해 TADPole은 DTW 계산을 최소화 하여 효율성을 향상 시켰다. 샘플간 거리 계산을 마친 후에는 밀도기반 클러스터링 알고리즘인 density peak이 적용되었다. 오늘 소개한 또 다른 알고리즘으로는 k-shape 알고리즘이 있다. k-shape 알고리즘은 시계열 데이터에 적용할 수 있도록 k-means clustering을 확장한 기법이다. 우선 유사한 시계열 샘플을 찾기 위해 k-shape 알고리즘에서는 cross-correlation을 이용한다. 군집의 중심은 앞서 군한 correlation을 최대화 할 수 있는 샘플을 최적화 문제로 정의하고 푼다. 오늘 세미나에서는 시계열 데이터를 군집화 할 수 있는 방법론을 접하기 흔치 않은 상황에서 유익한 알고리즘을 배울 수 있는 기회였다.

오늘 세미나는 시계열 데이터 군집화 기법을 주제로 진행되었다. 군집화에서는 관측치 간 거리(혹은 유사도)를 계산하는 것이 기본인데, 시계열 데이터에서는 misalignment 문제 때문에 관측치 간 거리를 정의, 나아가 그 거리를 계산하는 것조차 쉽지 않다. 가장 널리 쓰이는 Dynamic Time Warping(DTW)의 경우 관측치의 수가 많아짐에 따라 기하급수적으로 그 연산량이 증가한다. 따라서 DTW의 계산을 효율적으로 개선하고자 하는 많은 연구들이 진행된 바 있다. 오늘 소개된 TADPole에서는 density peak 알고리즘을 시계열 데이터에 활용하면서 DTW의 계산을 최소화할 수 있는 방법을 제안하고 있다. K-shape 알고리즘의 경우에는 cross-correlation을 활용한다. 평소 공부해보지 않았던 주제들이라 전부 이해하지는 못했지만, 청취자들을 배려한 발표자의 슬라이드 덕분에 어렵지 않게 입문할 수 있던 것 같다. DTW의 계산을 개선할 수 있는 방식으로 관측치 간 거리를 학습할 수 있는 모델을 만들면 어떨까 싶다. 실제 거리와 유사한 approximation 값만 빠르게 만들 수 있어도 계산 효율성이 많이 좋아질 것 같다는 생각이 든다.

금일 진행한 세미나에서 한규오빠가 'Time series clustering algorithm'이라는 주제로 time series데이터에서의 전통적인 misalignment 보정방법인 DTW(Dynamic Time Warping)의 계산 복잡도 문제를 해결하며, 더불어 군집화에 적용하는 k-shape clustering algorithms과 tadpole algorithm에 대해 소개해주셨다. 최근 학회에서 time series데이터에서 DTW를 기반으로 전처리한 방법론에 대해 접하며, 어떤 과정에 의해 보정이 되는지 의문이 있었는데 세미나에서 간략하게 DTW의 연산 과정에 대해 알 수 있었다. 먼저 시계열데이터에서도 여느 데이터와 같이 군집 및 분류 문제의 성능을 위해서 각 데이터간의 유사도를 잘 정의하는 것이 중요하다. 이 때 DTW는 시계열간 유사도를 측정하는 방법이며, 시계열 데이터가 갖는 특징 (1)misalignment (2)time series length 를 고려한다는 점에서 유용하게 사용되고있다. Cost matrix는 일종의 유사도 행렬이라 할 수 있었는데, 해당 행렬을 산출하고 총 누계가 최소가 되는 path를 탐색하므로써 두 시계열 데이터의 misalignment를 해결할 수 있다. 하지만 time step과 관측치의 개수를 고려해야한다는 점에서 계산과정이 복잡하다는 한계가 있으며, 이를 해결하기 위한 다양한 후속연구가 있다. 최cDTW, Lower bound 등이 있었다. 이는 간략히 누계가 최소가 되는 path위주로만 탐색하거나, DTW를 계산하지 않고, lower/upper bound를 넘어가는 부분에 대해서만 유클리디언 거리로 계산하여 비슷한 효과를 내는 방법이다. 이런 방법론을 통해 시계열 데이터에서의 유사도를 잘 정의한다면 이를 다양한 알고리즘에 활용할 수 있다. 이 때 보다 time series 특성을 잘 반영한다고 알려진 Density peak과 Tadpole clustering에 적용할 수 있다. 특히 Tadpole clustering방법에서는 DTW를 입력값으로 갖는데, 이때 앞서 설명한 계산효율성을 개선한 유사도 정의 방법론을 사용할 수 있다. 이번 학기 예측모델 수업을 통해 다양한 time series방법론에 대해 접하며, 고려해야할 특이점들이 흥미롭다고 생각했다. 이들을 고려한 다양한 방법론에 대해 단계적으로 설명해주신 한규오빠께 감사하며, 오늘 소개해준 다양한 방법론들을 시간을 두고 나도 제대로 공부해봐야겠다는 생각을 할 수 있었다.

이번 세미나는 Time series clustering 기법에 대해 다루었다. Tadpole 알고리즘과 k-shape 알고리즘을 소개하기에 앞서, Time series 데이터는 어떤 특성을 가지고 있는지 먼저 설명하고 해당 알고리즘을 이해하기 위해 먼저 알아야 하는 다른 개념에 대해 설명하였다. Time series 데이터는 시간적 순서를 가지므로 scaling이나 shifting 측면에서 독특한 특성을 가지고 있다. 이와 같은 특성 때문에 Dynamic Time Wrapping(DTW)나 Fourier Transform(FT)와 같이 Time series 데이터를 처리하기 위한 방법론들이 나타나게 되었다. Time series 데이터를 clustering하는 연구들에는 주로 시퀀스간 유사도를 측정하기 위해 DTW를 사용하고 있다. DTW는 misalignment와 시퀀스의 길이를 고려하여 유사도를 측정할 수 있다는 점에서 의의가 있다. 그러나 계산량이 많아 시간이 오래 걸리므로 이를 극복하기 위한 다양한 변형 방법론이 제안되었다. 발표자는 이에 대해 예시를 들어 상세하게 설명하여 청취자들의 이해를 도왔다. Density peak은 local density를 고려하는 밀도 기반 클러스터 할당 방법론으로, Tadpole 알고리즘에 사용되었다. Tadpole 알고리즘에서 사용된 거리는 DTW로 계산되기 때문에 계산량을 줄이기 위하여 DTW의 변형 방법론 중 하나인 Keogh를 채택하였다. 이 때문에 DTW 거리를 사용함에도 불구하고 빠르게 수렴하고 전통적인 clustering 기법들과 비교하였을 때 실험적으로 더 나은 결과를 보였다. 다음으로 k-shape 알고리즘은 우리가 아는 k-means 방법론에서 Time series 데이터를 처리할 수 있도록 변형한 방법론이다. 거리로는 cross correlation을 쓰고 이를 기반으로 중심점 계산을 하게 된다. 두 시퀀스간 cross correlation을 계산하여 shape-based distance를 계산하고 이를 통해 클러스터를 할당하는데 그 프로세스는 k-means clustering과 같다. 이번 세미나에서는 Time series 데이터를 clustering하는 방법론 두 가지에 대해서 다루었는데, 새로운 방법론을 소개하기 위해서 그 두 방법론에서 사용된 여러가지 기본적인 개념들을 먼저 상세하게 소개해준 것이 인상 깊었다. 아무 배경지식이 없는 상태에서 Tadpole 알고리즘과 k-shape 알고리즘에 대해 들었다면 이해하기가 힘들었을 것이다. 청취자들의 이해를 돕기 위하여 기본 개념부터 상세하게 설명하고 준비해준 발표자에게 감사 인사를 전하고 싶다.

신논현 토즈에서 진행된 이번 세미나의 주제는 Time Series Clustering이였다. 보통 시계열 데이터 분석법이라고 하면 보통 ARIMA, 전이함수 등의 Regression 등을 떠올리거나, Deep Learning 기반의 Classification을 떠올리는데 Clustering을 활용한 분석 이론을 소개해주셔서 흥미로웠다. 본격적인 이론 설명에 앞서 알고리즘의 베이스가 되는 DTW, Variance of DTW, Density Peak 등의 개념에 대하여 설명해주셨다. DTW는 Distance를 계산하여 Cost Matrix를 구하고, 임의의 window 내에서 거리의 합이 최소화되도록 Path를 설정하는 방식으로 계산된다. 이 계산법을 통해 데이터 간의 misalignment problem을 해결할 수 있는데, 이 계산법은 n의 수가 충분하지 않거나 계절성이 중요한 의미를 갖는 데이터에 대해서는 잘못된 결과나 해석을 이끌수도 있겠다는 생각이 들었다. 그러나 빅데이터 분석에서는 (계산량이 많지만)의미가 있는 유사도 계산법이라는 생각이 들었다. Variance of DTW는 boundary 개념을 도입하여 DTW의 계산량을 줄일 수 있는 방법이였다. Density Peak은 군집의 중점이 되는 포인트를 Local Density와 Minimum Distance from Points of Higher Density의 곱으로 계산하여 찾는 방법이였다.

위 3가지 개념을 기반으로 하여 Tadpole과 K-shape clustering algorithm에 대한 설명이 이어졌다. Tadpole의 경우 DTW 계산을 통해 구한 Distance matrix를 input으로 하는데, DTW를 계산하기 위해서 진행되는 과도한 연산을 피하기 위해 계산이 필요하지 않은 데이터를 filtering하여 계산을 최소화 하였다. 알고리즘의 효율성 측면에서 계산량과 속도의 중요성에 대하여 다시 한번 생각해볼 수 있었다. K-shape에서는 Distance matrix로 Shape-based distance를 사용하는데, 이를 계산하는데 있어 Cross-Correlation값을 활용하였다. Cross-Correlation은 두 시계열의 Time lag에 따른 내적값을 통해 계산하는데, Shape Extraction을 통해 시점을 일치시키고 Sequence가 얼마나 유사한지를 보는 유사도 계산법이였다.

전체적인 소감으로는 먼저 의료 데이터, 웹로그 데이터 등의 Time Series data를 좋은 성능을 가진 알고리즘으로 군집화 할 수 있다면 의미있는 연구나 프로젝트를 할 수 있을 것이라는 생각이 들었다. Multivariate data를 활용하여 먼저 데이터셋을 categorize하고 집단간의 특성을 보는 것이 아니라 이미 주어진 데이터를 clustering을 활용하여 트랜드나 패턴을 찾아낼 수 있다면 재밌을 것 같다. 다음으로는 다양한 형태의 데이터를 적절하게 처리하는 연구가 다양하게 진행되고 있다는 것을 알 수 있었다. 기존 이론을 변형/활용하여 다른 영역에 적용해보는 것도 새로운 연구 방법론을 개발하는 것만큼 의미가 있다는 것을 느꼈다. 연구Time Series data로 clustering을 한다는 접근법 자체가 나에게는 생소한 주제였는데, 논문 2개를 용어부터 이론까지 하나하나 자세하게 설명해주신 발표자 한규형에게 감사했다.​

본 세미나에서는 시계열 군집화를 다루었다. 다양한 군집화 방법 중 유사도 기반의 군집화 연구들을 소개하였고, 특히, 시계열 간의 유사도를 측정하는 방법들에 대해 소개하였다. 대표적인 시계열 유사도 측정 방법 중 하나인 Dynamic time warping (DTW) 방법은 시계열 간의 어긋남과 시계열 간의 길이가 다른 이슈를 해결 할 수 있다. 하지만 계산복잡도가 매우 높기 때문에 빅데이터에 활용하는데 현실적인 어려움이 있다. DTW의 계산복잡도를 줄이기 위해 다양한 변종 방법이 소개되었고, 본 세미나에서 소개한 연구는 변종 DTW 방법을 Clustering 방법에 임베딩 시킨 방법들에 대해 소개하였다. 최근 많은 연구들이 샘플간의 시간 독립성 가정을 깨고 좀 더 현실적인 문제를 푸는데 집중하고 있다. 특히 최근 관심 갖고 있는 바이오 및 의료 데이터에서는 이러한 시간 의존성 현상이 많이 나타난다. 본 세미나를 토대로 유사도 기반 접근법과 모델 기반 접근법의 차이 및 공통성을 좀 더 파악하고 관련 기술들의 트렌드를 좀 더 파악해 볼 필요가 있을 것 같다.

오늘은 시계열 군집화 방법론들에 대한 설명을 들을 수 있었다. 시계열 군집화는 다양한 시그널이 생성되고 있는 최근에 해당 현상을 이해하기 위해 많은 분야에서 활발히 적용되고 있다. 시계열 군집화를 할 때는 기존에 우리가 했던 방식과는 조금 다른 접근법이 요구된다. 그 이유는 시계열 관측치의 경우 측정 시간이 조금 달라질 수도 있고, 패턴이 유사하지만 시간의 렉이 발생할 수도 있는 문제가 생긴다. 그래서 이러한 문제를 해결하기 위해서 일반적으로 DTW 라고 하는 거리 측정 방법이 사용된다. 이 방법은 시계열의 얼라인을 조정하면서 전체적인 패턴의 유사성을 측정하는 방법이다. 굉장히 다양한 분야에서 사용되는 유명한 방법이지만 시계열 길이의 제곱에 비례하는 계산 복잡도 때문에 빅데이터를 분석할 때는 많은 시간의 제약이 따른다. 그래서 이러한 문제를 해결하기 위해 최근에는 모든 관측치를 계산하는 것이 아닌 꼭 필요한 관측치들에 대해서만 DTW를 계산하는 방식이 널리 사용되고 있다. 일종의 필터링을 하는 개념인데 꼭 계산이 되야하는 관측치들을 시계열 데이터의 상한과 하한을 이용해서 추려내고 이것들에 대해서는 DTW를 계산하는 것이다. 이렇게 하게 되면 DTW를 많은 데이터에 적용하지 않아도 되서 계산 효율성이 크게 증가하게 된다. 개인적으로도 시계열 군집화에 관심을 가지고 있어서 흥미롭게 들을 수 있었고, DTW 관련해서 좀 더 공부를 해보고 싶어졌다.

오늘 전체세미나는 'Time Series Clustering'이라는 주제로 한규형이 진행하였다. 첫 번째로 기본적인 시퀀스 유사도 추출 기법인 DTW(dynamic time wrapping)를 시작으로 시간비용적으로 DTW의 단점을 효율적으로 극복한 알고리즘을 소개해주었다. 최근 수면 시퀀스데이터를 분석하며 DTW 기법 등을 접할 기회가 많았는데 정확히 이해할 수 있는 시간이었다.​ 두 번째로 k-shape 군집 알고리즘이 인상적이었다. 거리를 기반으로 군집화하는 점은 k-means와 같고, 그 거리로 cross-correlation을 적용한다. cross-correlation​은 두 시계열 데이터 유사도를 측정하는 방법이다. 두 시계열 데이터가 있다면 하나의 시계열 데이터에 또 다른 시계열 데이터를 순차적으로 흘려 겹치는 크기의 면적을 유사도로 보는 것이다. 이를 sliding dot product라고도 말하며 시계열 데이터를 반대로 적용하는 것을 우리가 자주 접하는 합성곱(convolution)이라고 한다. 또한, 같은 방법으로 각 시계열 데이터가 자기 자신의 시계열 데이터를 적용하여 유사도를 산출하는 것이 Autocorrelation이다. 이처럼 오늘 세미나는 ​시계열 데이터 군집기법 k-shape을 ​새로 접할 수 있는 기회가 되었을 뿐만 아니라 전반적으로 시계열 데이터 분석에 기본이 되는 개념들을 정확히 짚을 수 있었다. ​요즘 연구하고 있는 수면 상태 시퀀스에도 적용해 볼 계획이다. ​그리고 오늘 소개해준 시계열 데이터는 연속형으로 이산형 시계열 데이터는 어떤식으로 적용하는 것이 효과적일지 궁금하다. 순서형(ordinal) 이산형이라면 큰 문제 없지만 범주형 이산형 시계열에는 적용하기 어렵다. ​그에 적합한 알고리즘은 없을지 ​알아보아야겠다. ​ ​끝으로 ​​오늘 세미나는 알아들을 수 있고, 지루하지 않았다. ​이러한 강의는 매우 오랜만인 것 같다.​ 또 역시 오랜만에 외부에서 진행된 전체세미나를 알차고 재밌게 진행해준 한규형에게 감사드린다.

금일 세미나에서는 시계열 데이터를 군집화하는 알고리즘을 주제로 진행되었다. 최근 연구실에서도 많이 진행이 되고 있고, 개인 연구 토픽 중에 하나인 센서 데이터의 분석 또한 근본적으로는 시간 개념이 포함되어 있는 다변량 데이터이다. 따라서, 데이터 분석에 있어 시간속성을 반영해야 하고 이는 해결하기 어려운 문제로 알려져 있다. 이번 세미나에서는 시간 속성을 반영한 유사도 산출 알고리즘과 군집화 알고리즘을 소개하였다. 유사도 산출 알고리즘은 DTW와 DTW의 변형 알고리즘를 소개하였고, DTW 관련 알고리즘을 활용한 군집화 방법론인 TADpole algorithm, k-shape algorithm에 대한 내용을 핵심 위주로 정리하는 시간을 가졌다. DTW는 잘 알려진 시계열 데이터의 유사도 산출방법으로, path 기반 알고리즘을 사용하여 두 데이터 사이의 aligment를 조정하여 '어그러진' 시계열 축을 맞춰준다. 하지만 이는 시간이 매우 오래 걸리고 computational cost가 높기 때문에 (필요한 연산 테이블의 크기만 mxn) cDTW나 LB Koegh와 같은 변형 알고리즘들이 주로 사용된다고 한다. TADpole은 DTW에 필요한 데이터를 정량적으로 필터링하여 계산량을 대폭 단축시킨 후 군집화를 진행하는 방식이며, k-shape algorithm은 두 시계열 데이터 모양 (shape) 유사도를 추출하여 사용한다. 모양 유사도를 계산하기 위해서는 cross-correlation을 사용하게 되는데, 이는 time lag를 주어서 두 시계열 데이터의 pearson correlation을 계산하는 방법이다. Time lag를 주다보면 실제로는 상관관계가 크지 않지만 '우연의 일치'로 cross-correlation이 높아지는 경우가 생기는데 이러한 계산을 막기위해서 false discovery rate와 같은 방법론을 사용하여 보정을 한다고 알고 있다. 세미나를 준비하는데 있어서, 아직까지 연구실 세미나에서 소개되지 않은 분야에 대한 주제를 선택했을 때가 가장 어렵다고 느껴진다. 오늘 세미나 시간에는 시계열 군집화를 이해하는데 있어서 가장 기본적인 DTW부터 다양한 알고리즘들이 소개되었는데, 방대한 내용을 정리하여 설명해준 한규형에게 감사하다.

금일 세미나는 Time series clustering algorithm이라는 주제로 진행되었다. 시계열 clustering 방법론에는 DTW, variance of DTW, Density peak 등이 있는데 오늘 세미나에서는 이에 덧붙여서 Tadpole algorithm과 k-shape algorithm에 대한 설명이 있었다. Tadpole algorithm은 특정한 dc를 기준으로 lower bound, upper bound, dtw distance를 고려하여 필요한 data에 대해서만 연산이 진행되므로, 기존의 clustering algorithm과는 정확도와 속도에서 차별점을 보인다는 데에 의의가 있다. K-shape 알고리즘은 cross-correlation을 활용하여 distance를 구하고 shape extraction을 통해 군집의 center을 구하는 방법론이다. 이는 time series 데이터를 분석 할 때 sequence 데이터의 패턴의 misalignment를 고려하는 기본 아이디어를 반영한 듯 보인다. 기존 방법론에서 데이터의 misalignment 대신 cross correlation을 활용하여 두 시점을 일치시켜 이 합이 최대가 되도록 하는 것이 핵심이다. 세미나를 들으며 궁금했던 점은 단순히 데이터 간의 sequence pattern 시점을 embedding 시키는 것에서 나아가 clustering의 군집화 특성을 더욱 잘 파악할 수 있는 연산방법이 유사도 외에 무엇이 있을까였다. 관련 알고리즘에 대해 관심 있게 공부해야 할 필요성이 있을 것 같다.​