[머신러닝] tslearn TimeSeriesKmeans : 시계열 데이터에 K-Means 클러스터링 적용
1. 목적(사용 이유)
시계열 데이터를 클러스터링 하는데, 일반적인 방법은 시계열 데이터를 인덱스로 평면한 다음 K-means 같은 클러스터링 알고리즘을 적용 하는 것 이다.
클러스터링 알고리즘은 '레이블' 없이 유사한 데이터 포인트를 군집화하는 비지도 학습 방법(Unsupervised Learning) 이다. 클러스터링 알고리즘은 유사한 데이터 포인트를 그룹화 하기 때문에, 데이터 포인트 간의 유사성을 찾는데 초점을 맞춘다.
서로 다른 시계열(ex: 카카오와 엔비디아의 주가 등) 을 유사한 그룹으로 클러스터링 하는 것은 각 시계열이 가진 시간차원을 무시한다는 점이다.
문제가 생기게 되는 점은 유클리디안 방법과 같은 일반적인 클러스터링 기법을 사용시, 시계열로 되어 있는 데이터를 클러스터링 하며 '시간에 따른 고유한 정보를 보존하지 못한다.' 점이다.
timeseriesKmeans 는 시간에 따른 군집화가 가능하기 때문에, 위의 문제를 해결할 수 있다는 장점을 갖고 있다.
2. 방법
DTW(동적 시간 왜곡) 을 활용한 K-Means 클러스터링
클러스터링 알고리즘은 레이블 없이, 유사한 데이터 포인트를 그룹화 시키는 비지도 학습 방법이다. 일반적으로, 데이터 포인트간의 유사성은 유클리디안 거리 측정법으로 측정한다.
대표적인 알고리즘이 K-Means(샘플을 K 개의 그룹으로 분할하고, 각 클러스터의 제곱합을 최소화하여 데이털르 클러스터로 구성하는 방법)
그러나, K-Means 는 위에서 언급 했듯, 시계열에 적합하지 않는 경우가 많다. 때문에, 동적 시간 왜곡 같은 시계열 비교를 위한 메트릭으로 변경하여 문제를 해결하려 한다.
그렇다면, 왜? 유클리드디안 거리 측정법이 시계열에 적합하지 않을까? 를 파악해야 한다. 요약하자면, 유클리디안 거리는 데이터의 시간 차원을 무시하고 시간 이동에 불변한다. 두 시계열이 높은 상관관계가 있지만, 하나가 한 시간 단계만큼 이동하는 경우 유클리드 거리는 더 멀리 떨어져 있다고 잘못 측정한다. (자세한 설명)
* DTW(Dynamic Time Warping Matching) : 동적 시간 왜곡은 두 개의 시계열 데이터간의 유사성을 비교하거나, 패턴을 찾는데 유용한 알고리즘이다.
DTW는 시간에 따라 데이터가 서로 다른 속도로 변화할 수 있는 경우에도 적용할 수 있다. DTW 알고리즘의 주요 아이디어는 두 시계열 데이터 간의 최적의 정렬을 찾는 것.
이를 위해 다이내믹 프로그래밍 기법을 사용하여 두 시계열 데이터의 각 포인트 간의 거리를 계산하고, 최적의 경로를 찾아 정렬하는 기법이다.
- 거리 행렬 계산: 각 시계열 데이터 간의 거리를 계산하여 거리 행렬을 생성한다. 주로 유클리드 거리 또는 맨하탄 거리를 사용함.
- 적합한 경로 찾기: 거리 행렬을 기반으로 최적의 경로를 찾는다. 이 경로는 시간에 따라 데이터가 정렬되는 방식을 나타낸다.
- 정렬된 데이터의 거리 계산: 찾아진 최적 경로를 기반으로 정렬된 데이터 간의 거리를 계산한다. 이 거리가 시계열 데이터 간의 유사성을 나타내는 척도가 된다.
- 유사성 측정: 계산된 거리를 기반으로 두 시계열 데이터의 유사성을 측정한다. 보통 이 거리가 작을수록 두 데이터가 유사하다고 간주한다. 이는 K-means 에도 적용되는 기법이다.
- 장점 : DTW는 시계열 데이터 간의 시간적 변동이나 속도 차이를 고려할 때 유용합하다. 음성 인식, 자연어 처리, 운동 동작 분류 등 다양한 분야에서 적용되며, 유사성 비교나 패턴 인식에 효과적으로 사용되는 기법이다.
- DTW 방정식은 X 의 각 요소와 Y 의 가장 가까운 점 사이의 거리 제곱합의 제곱근으로 계산 된다.
1. DTW 클러스터링(첫번째 그림) : 유클리디안 거리의 직선으로 가까운 지점을 찾는 것과 다르게, 파란색 계열의 각 지점을 빨간색 계열의 가장 가까운 점을 입체적으로 가로질러 찾는다. X 와 Y에 입력된 인덱스 값들을 1:1로 비교하는 것이 아닌 X 와 Y의 가장 가까운 점 사이를 찾고 있다. 위와 같이 학습시, X와 Y의 뒤틀린 경로가 생성된다. 경로는 정렬 된 계열간의 유클리디안 거리를 최소화하는 시계열의 시간적 정렬을 보여주고 있다.
해당 알고리즘은 동적 프로그래밍(dynamic programming = DP) 을 활용한다. 최적화의 알고리즘의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.
K-Means 클러스터링 알고리즘에서, 다음과 파라미터를 조정하면 DTW(동적 시간 왜곡) 이 있는 시계열을 클러스터링 할 수 있다.
* DTW 는 유사한 모양의 시계열을 군집화하는데 사용된다.
* 유클리디안, DBA, Soft-DTW 별로 K-Means 를 적용하여 클러스터를 적용한 결과.
* soft-DTW 는 미분할 수 없는 연산을 대체하는 DTW의 미분 가능한 변형이다.
* 각 열은 서로 다른 클러스터와 해당 중심의 계열을 빨간색으로 표시한 것
3. 코드 및 적용
from tslearn.clustering import TimeSeriesKMeans
model = TimeSeriesKMeans(n_clusters=3, metric="dtw",
max_iter=10, random_state=seed)
model.fit(X_train)
# where X_train is the considered unlabelled dataset of time series. The metric parameter can also be set
# to "softdtw" as an alternative time series metric (cf. our User Guide section on soft-DTW).
위의 코드로 시계열 데이터를 DTW 방식을 활용하여 군집화 할 수 있습니다.
from tslearn.metrics import dtw
dtw_score = dtw(x, y)
# Or, if the path is also an important information:
optimal_path, dtw_score = dtw_path(x, y)
두 시계열(파란색) 사이의 DTW 경로를 하얀색으로 표시한 것 입니다. 히트맵은 두 시계열 간의 거리를 색으로 강조한 것 입니다.
해당 코드는 참고 링크에서 확인할 수 있습니다.
4. 결론
시계열 데이터를 분석할 때, 클러스터링을 하고 싶다면 tslearn 을 활용하여 클러스터링을 적용해야 한다. 시계열 데이터를 비지도 학습으로 클러스터링 할 경우, 시계열 데이터가 가지고 있는 시간에 따른 고유 정보를 무시하기 때문이다. 이를 해결하고자 DTW 방법을 활용하여 K-means 알고리즘을 적용한다면, 시계열 데이터가 가진 시간에 대한 고유성을 보존하면서 군집화 할 수 있다.
* 참고 1 : mauricio montilla - Clustering Sales Record with K-Means and DTW (링크)
* 참고 2: tslearn 공식 문서 (링크)
* 참고 3 : 공식 코드(링크)
* 참고 4 : 블로그 Data-Science Magazine(링크)