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)을 베이스로 파생된 계산 방식이에요.

출처: Markus P. Nemitz & Ryan J. Marcotte & Mohammed E. Sayed & Gonzalo Ferrer  2019 Multi-Functional Sensing for Swarm Robots Using Time Sequence Classification: HoverBot, an Example

위 이미지는 유클리디언(좌측)과 DTW(우측)의 거리 계산 방식의 차이를 보여주는 이미지입니다.

먼저 유클리디언을 보면, 두 데이터(빨강, 파랑)를 동일한 축으로 대응시키는 모습을 볼 수 있는데요. 이렇게 되면 거리는 두 데이터 포인트의 직선거리로 계산됩니다. 이러한 방식은 되게 간단하지만, 두 데이터의 패턴이 유사해도 시간 축이 조금만 어긋나면 거리를 크게 계산하는 한계가 있어요.

반면 DTW는 시간축의 왜곡을 허용하는 방식으로 이러한 한계를 보완해 주죠. 좀 더 자세히 알아볼게요.

출처: Markus P. Nemitz & Ryan J. Marcotte & Mohammed E. Sayed & Gonzalo Ferrer  2019 Multi-Functional Sensing for Swarm Robots Using Time Sequence Classification: HoverBot, an Example

이 다이어그램은 DTW 계산 과정을 보여주는 다이어그램입니다. 먼저 두 시계열 A, B가 있을 때, 이 두 시계열 데이터에 대한 거리행렬을 (A) 번 과정에서 구해줍니다. 이때 셀 값은 일반적으로 유클리디언 거리를 사용하고, 값이 클수록(거리가 멀수록) 붉은색으로 나타나요. 이 거리행렬을 바탕으로 (B) 번 과정에서 누적 거리 행렬을 구하게 돼요. 이때 각 셀 값은 아래의 수식으로 결정돼요.

여기서 좌측의 D가 누적 거리 행렬의 각 셀값이고, 이 값은 델타(이전 A번 과정에서 구한 유클리디언 거리) + 이전 경로 중 최솟값의 누적 거리로 구할 수 있어요. 이렇게 구해진 누적 거리 행렬에서 파란 선이 바로 두 데이터 간 최적 매핑 경로가 되고, (C) 번 과정은 이를 시각화한 모습이에요. 

 

다음으로 Barycenter Averaging 과정을 살펴볼게요.

출처: Markus P. Nemitz & Ryan J. Marcotte & Mohammed E. Sayed & Gonzalo Ferrer  2019 Multi-Functional Sensing for Swarm Robots Using Time Sequence Classification: HoverBot, an Example

여기서 (A) 번 과정은 아까와 동일한 과정이고, (B) 번 과정은 각 시점 k에 대해 매핑된 데이터 포인트의 합을 계산해 주는 과정이에요. 그 이유는 매핑된 데이터 포인트를 평균화해주어야 하기 때문이죠. 평균화 방법은 간단합니다. 각 데이터 포인트의 합을 개수만큼 나눠주면 되는데요. 이렇게 평균화를 거치면 아래에 (C) 번에서 볼 수 있듯이 새 centroid가 구해집니다.

이 과정을 이제 centroid가 클러스터 중심에 수렴할 때까지 반복해 주면 됩니다. 

 

3. 결론

지금까지 DBA K-Means에 대해 알아보았는데요.

아래 표로 간단하게 일반적인 K-Means와의 차이를 알아볼까요?

구분	DBA K-Means	K-Means
거리 계산 방식	DTW	유클리디안
장점	시계열 특성 반영 가능	구현이 간단하고, 대규모 데이터에서도 사용
단점	알고리즘 계산 비용이 높음	시계열 특성 반영 X

---

발표회까지 하고 나니 방학이 사라져 버렸지만... 그래도 남은 기간 동안 또 열심히 포스팅하겠습니다!!

다음 포스트에서 봬요~