K-평균 군집화 — 알고리즘과 작동 원리

K-평균 군집화는 수치형 데이터를 $k$개의 군집으로 묶는 방법입니다. $k$를 정하고 표준 유클리드 버전을 사용하면, 알고리즘은 하나의 반복 과정을 계속 수행합니다. 각 점을 가장 가까운 중심에 할당한 뒤, 각 중심을 그 군집에 속한 점들의 평균으로 옮깁니다.

쉽게 말해, 같은 그룹 안의 점들은 서로 가깝게 보이도록 하고 다른 그룹의 점들은 더 멀어지도록 하려는 방법입니다. 빠르고 유용하지만, 이런 "그룹"이 어느 정도 조밀하고 거리라는 개념이 의미 있을 때 잘 작동합니다.

K-평균 군집화가 최적화하는 것

표준 유클리드 형태에서 K-평균은 각 군집 안의 점들이 그 군집의 중심점에 최대한 가깝도록 하려고 합니다. 자주 쓰이는 목적함수는 다음과 같습니다.

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

여기서 $C_j$는 $j$번째 군집이고, $\mu_j$는 그 군집의 중심점입니다.

이 값은 군집 내 제곱합(within-cluster sum of squares)입니다. 값이 작을수록 할당된 점들이 자신의 중심점 주변에 더 촘촘하게 모여 있다는 뜻입니다.

이 목적함수는 알고리즘의 두 부분을 설명해 줍니다.

• 중심점이 고정되어 있으면, 각 점을 가장 가까운 중심점에 할당하는 것이 최선입니다.
• 할당이 고정되어 있으면, 가장 좋은 중심점은 할당된 점들의 평균입니다.

그래서 업데이트 규칙은 임의로 정한 것이 아닙니다. K-평균의 "평균"은 말 그대로 산술평균입니다.

K-평균 알고리즘은 어떻게 작동하나

일반적인 반복 과정은 짧습니다.

1. 초기 중심점 $k$개를 고릅니다.
2. 각 점을 가장 가까운 중심점에 할당합니다.
3. 각 중심점을 그 군집에 할당된 점들의 평균으로 다시 계산합니다.
4. 할당이 더 이상 바뀌지 않거나 개선이 매우 작아질 때까지 반복합니다.

이 과정은 보통 빠르게 수렴하지만, 항상 가능한 최적의 군집화에 도달하는 것은 아닙니다. 시작 중심점이 다르면 최종 결과도 달라질 수 있으므로 초기화가 중요합니다.

K-평균 군집화 예시를 단계별로 보기

다음과 같은 1차원 데이터 점들을 생각해 봅시다.

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

이제 $k = 2$개의 군집을 원하고, 초기 중심점을 $1$과 $10$으로 둔다고 합시다. 이 예시는 첫 번째 업데이트 뒤에 중심점이 실제로 이동하기 때문에 좋은 예시입니다.

1단계: 가장 가까운 중심점에 점 할당하기

점 $1, 2, 3$은 $1$에 더 가깝습니다.

점 $10, 11, 12$는 $10$에 더 가깝습니다.

따라서 군집은 다음과 같습니다.

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

2단계: 중심점 업데이트하기

첫 번째 군집의 새로운 중심점은 다음과 같습니다.

$$\mu_1 = \frac{1+2+3}{3} = 2$$

두 번째 군집의 새로운 중심점은 다음과 같습니다.

$$\mu_2 = \frac{10+11+12}{3} = 11$$

두 중심점 모두 이동했습니다. 각각 $1$에서 $2$로, $10$에서 $11$로 바뀌었습니다.

3단계: 다시 할당하기

이제 $2$와 $11$을 사용해 다시 가장 가까운 중심점을 확인합니다.

점 $1, 2, 3$은 여전히 첫 번째 군집에 속하고, 점 $10, 11, 12$는 여전히 두 번째 군집에 속합니다. 할당이 더 이상 바뀌지 않으므로 알고리즘은 수렴한 것입니다.

이 예시는 데이터가 자연스럽게 두 개의 조밀한 그룹으로 나뉘기 때문에 깔끔합니다. 실제 데이터셋은 더 복잡하며, 바로 그런 지점에서 K-평균이 오해를 불러올 수 있습니다.

K-평균이 잘 작동하는 경우

다음 조건이 대체로 맞을 때 K-평균은 가장 잘 작동합니다.

• 특성이 수치형이다.
• 유클리드 거리가 유사성을 재는 합리적인 방법이다.
• 군집이 길거나 휘어 있지 않고 비교적 조밀하다.
• 한 변수가 나머지를 압도하지 않도록 특성 스케일링이 되어 있다.

이 조건이 맞지 않으면, 결과가 겉보기에는 깔끔해 보여도 데이터의 실제 구조를 놓칠 수 있습니다.

K-평균에서 흔히 하는 실수

K-평균을 만능 군집화 방법으로 보는 것

K-평균은 군집이 어느 정도 조밀하고 평균이 적절한 요약값일 때 가장 잘 작동합니다. 모든 데이터셋에 대한 좋은 기본 선택은 아닙니다.

특성 스케일링을 무시하는 것

어떤 특성이 다른 특성보다 훨씬 큰 스케일로 측정되면, 그 특성이 거리 계산을 지배할 수 있습니다. K-평균을 실행하기 전에 표준화나 정규화가 중요한 경우가 많습니다.

답이 유일하다고 가정하는 것

K-평균은 시작점에 따라 서로 다른 국소 최소값으로 수렴할 수 있습니다. 그래서 여러 번 실행하거나 k-means++ 같은 초기화 방법을 자주 사용합니다.

수치형이 아니거나 부적절하게 인코딩된 특성을 사용하는 것

중심점은 평균이므로, 표준 K-평균은 수치형 변수에 맞춰져 있습니다. 특성이 범주형이라면 산술평균을 구하는 것이 의미 없을 수 있습니다.

강하게 비구형인 군집에 사용하는 것

실제 그룹이 길거나 휘어 있거나 밀도가 매우 불균등하면, K-평균은 하나의 자연스러운 그룹을 쪼개거나 서로 다른 두 그룹을 합쳐 버릴 수 있습니다. 이 방법은 조밀하고 중심점 기반인 군집을 선호합니다.

이상치가 중심점을 끌어당긴다는 점을 잊는 것

중심점은 평균이기 때문에 극단값이 있으면 중심점이 눈에 띄게 이동할 수 있습니다. 데이터에서 이상치가 중요하다면 결과를 믿기 전에 이 점을 확인해야 합니다.

K-평균 군집화는 어디에 쓰이나

K-평균은 탐색적 그룹화, 고객 또는 행동 세분화, 이미지 색상 양자화, 그리고 비지도학습에서 빠른 기준선 모델로 자주 사용됩니다.

수치형 특성이 있고, 빠르고 단순한 모델을 원하며, 유클리드 공간에서 군집이 대체로 조밀할 것이라고 예상할 때 특히 유용합니다.

간단한 머릿속 그림

산점도 위에 움직일 수 있는 핀 $k$개를 꽂는다고 상상해 보세요. 모든 점은 가장 가까운 핀에 붙습니다. 그런 다음 각 핀은 자신에게 붙은 점들의 평균 위치로 미끄러져 이동합니다. 핀이 거의 더 이상 움직이지 않을 때까지 이를 반복합니다.

이 그림은 단순한 직관에 그치지 않습니다. 사실상 알고리즘의 거의 전부를 담고 있습니다.

비슷한 군집화 문제를 직접 해보기

직선 위의 작은 점 집합을 하나 정하고, $k = 2$를 선택한 뒤, 손으로 한 번 전체 할당-업데이트 과정을 해 보세요. 그런 다음 시작 중심점을 바꾸거나 이상치 하나를 추가해서 결과가 어떻게 달라지는지 확인해 보세요. 한 걸음 더 나아가고 싶다면, 작은 데이터셋으로 직접 해 보고 특성 스케일링 전후에 무엇이 달라지는지도 비교해 보세요.