DBA K-Means Clustering이란?
안녕하세요. 오랜만에 포스팅하는 것 같네요!
제가 연구실에 들어와서 바로 논문 발표 준비를 하느라 여유가 없었습니다...
이번 글은 제가 썼던 논문에서 사용한 알고리즘에 대해 소개해보려고 해요!!
DBA K-Means Clustering
1. K-Means Clustering 이란?
아마 데이터 분석을 접해보셨더라면, K-Means 자체는 몇 번 들어보셨을 거라 생각해요. K-Means 알고리즘은 주어진 데이터를 K개의 클러스터로 나누는 비지도 학습 기법 중 하나입니다. 여기서 비지도 학습이란, 정답이 주어지지 않은 데이터에서 유의미한 패턴이나 구조를 학습하는 걸 의미해요. 이러한 비지도 학습을 수행하는 K-Means의 특징은 다음과 같아요.
1.1. initial centroid 설정
- 먼저 군집 수 K를 정합니다. 이때 최적의 K값을 구하기 위해 보통 elbow나 실루엣 기법을 사용해요.
- K개의 centroid를 초기값으로 지정합니다. 이때 initial centroid 설정의 파라미터로 k-means++를 설정해 주면, 기존의 무작위 방식이 아니라 데이터 분포를 바탕으로 초기값을 설정하기 때문에, 좀 더 정밀한 값으로 세팅됩니다.
1.2. 할당
- 각 데이터 포인트를 현재 centroid과의 거리(유클리디안 거리, DTW거리 등)를 기준으로 가장 가까운 centroid에 할당합니다.
- 이렇게 할당된 결과로 K개의 클러스터가 형성됩니다.
1.3. 재계산
- 새롭게 형성된 각 클러스터 내 데이터 포인트들의 평균 위치를 구해, 그 클러스터의 새로운 centroid로 설정합니다.
1.4. 반복
- 모든 데이터 포인트에 대해 새로운 centroid와의 거리를 다시 계산하여 클러스터에 재할당합니다.
- 그 후 다시 centroid를 계산합니다.
- centroid가 수렴할 때 알고리즘을 중단합니다.
2. DBA K-Means Clustering 이란?
그럼 DBA K-Means는 기존의 K-Means와 뭐가 다를까요?
간단히 말해서 DBA K-Means는 데이터의 시계열 특성을 반영한다는 점에서 큰 차이가 있어요. 그렇다면 그 원리가 어떻게 되는 걸까요?
먼저 DBA는 Dynamic time warping Barycenter Averaging의 약자입니다. 여기서 먼저 Dynamic time warping인 DTW에 대해서 알아볼게요. DTW는 기존의 거리 계산 방식인 유클리디언(Euclidean)을 베이스로 파생된 계산 방식이에요.
위 이미지는 유클리디언(좌측)과 DTW(우측)의 거리 계산 방식의 차이를 보여주는 이미지입니다.
먼저 유클리디언을 보면, 두 데이터(빨강, 파랑)를 동일한 축으로 대응시키는 모습을 볼 수 있는데요. 이렇게 되면 거리는 두 데이터 포인트의 직선거리로 계산됩니다. 이러한 방식은 되게 간단하지만, 두 데이터의 패턴이 유사해도 시간 축이 조금만 어긋나면 거리를 크게 계산하는 한계가 있어요.
반면 DTW는 시간축의 왜곡을 허용하는 방식으로 이러한 한계를 보완해 주죠. 좀 더 자세히 알아볼게요.
이 다이어그램은 DTW 계산 과정을 보여주는 다이어그램입니다. 먼저 두 시계열 A, B가 있을 때, 이 두 시계열 데이터에 대한 거리행렬을 (A) 번 과정에서 구해줍니다. 이때 셀 값은 일반적으로 유클리디언 거리를 사용하고, 값이 클수록(거리가 멀수록) 붉은색으로 나타나요. 이 거리행렬을 바탕으로 (B) 번 과정에서 누적 거리 행렬을 구하게 돼요. 이때 각 셀 값은 아래의 수식으로 결정돼요.
여기서 좌측의 D가 누적 거리 행렬의 각 셀값이고, 이 값은 델타(이전 A번 과정에서 구한 유클리디언 거리) + 이전 경로 중 최솟값의 누적 거리로 구할 수 있어요. 이렇게 구해진 누적 거리 행렬에서 파란 선이 바로 두 데이터 간 최적 매핑 경로가 되고, (C) 번 과정은 이를 시각화한 모습이에요.
다음으로 Barycenter Averaging 과정을 살펴볼게요.
여기서 (A) 번 과정은 아까와 동일한 과정이고, (B) 번 과정은 각 시점 k에 대해 매핑된 데이터 포인트의 합을 계산해 주는 과정이에요. 그 이유는 매핑된 데이터 포인트를 평균화해주어야 하기 때문이죠. 평균화 방법은 간단합니다. 각 데이터 포인트의 합을 개수만큼 나눠주면 되는데요. 이렇게 평균화를 거치면 아래에 (C) 번에서 볼 수 있듯이 새 centroid가 구해집니다.
이 과정을 이제 centroid가 클러스터 중심에 수렴할 때까지 반복해 주면 됩니다.
3. 결론
지금까지 DBA K-Means에 대해 알아보았는데요.
아래 표로 간단하게 일반적인 K-Means와의 차이를 알아볼까요?
| 구분 | DBA K-Means | K-Means |
| 거리 계산 방식 | DTW | 유클리디안 |
| 장점 | 시계열 특성 반영 가능 | 구현이 간단하고, 대규모 데이터에서도 사용 |
| 단점 | 알고리즘 계산 비용이 높음 | 시계열 특성 반영 X |