K-means Clustering에서 centroid와 assignment 업데이트하는 것 중 뭐가 더 오래 걸릴까?

K-means has two steps: updating centroids given assignments, and updating assignments given centroids. We note that the latter is more expensive while the former is a simple averaging. Hence, we update the centroids after each iteration and update the assignments once every t iterations.


출처) Compact3D: Smaller and Faster Gaussian Splatting with Vector Quantization

 

논문을 읽다가 왜 그렇지? 이해가 잘 안되는 부분이 있어서 정리해보려고 한다.

K-means Clustering에서 centroid update와 assignment update가 무엇을 의미하는가?

 

일단 K-means Clustering에 대해서 정리해보자.

 

---

K-means Clustering

가장 간단하면서도 널리 사용되는 클러스터링 기법으로, 사용자가 지정해준 K개의 클러스터로 나누는 방법으로 동작한다.

1. K개의 클러스터 중심점(centroid)을 랜덤하게 선택
2. 각 데이터 포인트들을 가장 가까운 클러스터 중심점에 할당
3. 할당된 데이터 포인트들의 평균값을 계산하여 새로운 클러스터 중심점을 업데이트
4. 2-3단계를 반복. 클러스터 할당이 변하지 않거나, 미리 정한 반복 횟수에 도달하면 알고리즘이 종료

 

클러스터의 centroid를 update하는 과정과

할당된 해당 포인트들을 의미하는 assignment를 update하는 과정은 2-3단계를 반복하면서 진행된다.

 

각 단계에 대해 자세히 설명해보자.

 

 

---

Centroid Update

각 클러스터에 속한 데이터 포인트들의 평균을 계산하여 새로운 centroid를 찾는 과정

이 과정은 사실 클러스터에 속하는 데이터 포인트들의 좌표를 평균 내는 과정이기 때문에 비교적 간단하다.

 

데이터 포인트들의 개수를 $N$이라고 한다면, 시간 복잡도는 $O(N)$이기 때문이다.

 

Assignment Update

각 데이터 포인트들을 가장 가까운 centroid에 할당하는 과정

이는 모든 데이터 포인트들에 대해 모든 centroid까지의 거리를 계산하고,

가장 가까운 centroid를 찾는 과정을 포함하므로 계산 비용이 매우 높다.

 

데이터 포인트들의 개수를 $N$, centroid의 개수를 $K$라고 한다면

이때는 각 데이터 포인트들에 대해 K개의 중심점까지 거리를 계산해야 하므로 $O(N*K)$의 시간 복잡도를 가진다.

 

 

---

즉, 3DGS 모델은 가우시안의 개수인 $N$이 수백만개이기 때문에 Assignment Update가 오래 걸리는 것이다.

따라서 Centroid Update는 매 iter마다 하더라도, Assignment Update는 특정 iter만 수행하도록 설계하였다.

 

여기서 그런 의문을 가질 수 있다.

매 iteration마다 완벽히 K-means Clustering이 수행되는건 아닌 것 같네요? 정확하다!

Assignment Update를 수행하지 않고 Centroid Update만 수행하는 iteration에서는 최적화된 결과는 아닌 것이다.

이는 계산 비용을 줄이기 위한 타협점으로, Clutering 정확도와 계산 비용간의 균형을 맞추는데 중요한 역할을 한다.

 

 

 

 

---

참고블로그

https://gsbang.tistory.com/entry/%EA%B8%B0%EA%B3%84%ED%95%99%EC%8A%B5-k-means-%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0%EB%A7%81-%EC%B5%9C%EC%A0%81%EC%9D%98-k%EA%B0%92-%ED%83%90%EC%83%89#google_vignette

[기계학습] k-means 클러스터링 - 최적의 k값 탐색

 

https://yoonschallenge.tistory.com/559

모두를 위한 머신러닝 과제2 - k means 진행, 계산