[ML] K-means clustering

1. K-means clustering?

• 데이터를 $K$개의 그룹(군집)으로 자동으로 나눠주는 비지도학습 알고리즘
• 각 군집을 대표하는 중심점(centroid)을 그 군집에 속한 데이터들의 평균(mean) 위치로 잡아가면서 군집을 갱신해 나가기 때문에 "K-평균(K-means)"라고 함.
• 정답 라벨 없이, 데이터들끼리 얼마나 가까운지만 보고 그룹을 찾아냄.

2. 문제 상황

수만 개의 데이터(예: 고객 문의 티켓)가 있는데, 사람이 일일이 보지 않고도 "비슷한 것들끼리 자동으로 묶고 싶다."
라벨(정답)은 없다.

그냥 데이터의 분포만 보고 그룹을 찾아내는 것, -> 비지도학습(unsupervised learning).

K-Means는 그중 가장 단순하고 널리 쓰이는 알고리즘이다.

3. 알고리즘

$K$개의 그룹으로 나눈다고 하자.

1. 초기화: $K$개의 중심점(centroid)을 무작위로(혹은 똑똑하게) 배치
2. 할당(assign): 모든 데이터를 가장 가까운 중심점에 배정
3. 갱신(update): 각 중심점을 자기에게 배정된 데이터들의 평균 위치로 이동
4. 2~3을 반복하다가 더 이상 바뀌지 않으면(수렴) 종료

초기 중심점 무작위 배치
   ↓
[반복] 모든 점 → 가장 가까운 중심점에 배정
   ↓
[반복] 중심점 → 자기 그룹의 평균으로 이동
   ↓
변화 없음? → 종료 / 있음? → 반복으로

핵심 - 중심점은 서로 독립적이다.

• KMeans의 가장 중요한 특징.
• $K$개의 중심점은 서로 아무 관계가 없다.
  e.g.) 중심점 5번이 중심점 50번 바로 근처로 이동해도, 50번에게 아무 영향이 없다.
• 각 중심점은 오직 "자기에게 배정된 데이터의 평균"만 보고 독립적으로 움직인다.

이 특징이 나중에 SOM과 비교할 때 핵심 차이점이 되는데,
SOM은 중심점(노드)들이 격자 위에서 서로 연동되어 움직인다는 점이 다르다.

4. k-means++: 초기화를 똑똑하게

위 1단계("무작위로")를 그대로 쓰면 운이 나쁠 때 문제가 생긴다.
두 중심점이 우연히 같은 군집 근처에 가깝게 찍히면, 알고리즘이 그 근처에서만 수렴해버려서 다른 진짜 군집을 놓치는 지역 최적해(local optimum)에 빠지기 쉽다.

• k-means++는 이 문제를 줄이기 위한 초기화 방법이다.
• 아이디어: "이미 찍은 중심점들로부터 먼 데이터일수록 다음 중심점으로 뽑힐 확률을 높이자."

1. 첫 번째 중심점은 데이터 중에서 무작위로 하나 뽑는다
2. 그다음 중심점은, 각 데이터 $x$에 대해 "이미 뽑힌 중심점들 중 가장 가까운 것까지의 거리" $D(x)$를 구하고, 다음 확률로 하나를 뽑는다:

$$
P(x) = \frac{D(x)^2}{\sum_{x' \in X} D(x')^2}
$$

거리가 먼 데이터일수록(=기존 중심점들과 안 겹치는 영역일수록) 뽑힐 확률이 커진다.
이렇게 $K$개를 다 뽑은 뒤, 일반 KMeans(할당→갱신 반복)를 시작한다.

scikit-learn의 KMeans는 기본값이 init='k-means++'라서, 따로 설정 안 해도 이미 이 방식을 쓰고 있다.

5. 목적함수

KMeans가 최소화하려는 값은 "군집 내 분산의 합"(Within-Cluster Sum of Squares, WCSS):

$$
J = \sum_{k=1}^{K} \sum_{x \in C_k} |x - \mu_k|^2
$$

$C_k$는 $k$번째 군집, $\mu_k$는 그 군집의 중심점.
각 데이터가 자기 군집의 중심점으로부터 얼마나 떨어져 있는지(거리의 제곱)를 전부 더한 값.
이게 작을수록 "군집이 빽빽하게 잘 모여있다"는 뜻.

왜 갱신 단계에서 하필 "평균"으로 이동하는가?

직관이 아니라 수학적으로 정해진다. 군집 $C_k$의 데이터들이 고정돼 있다고 하고,
$\mu_k$에 대해 $J$를 최소화하는 지점을 찾아보자.

$J$를 $\mu_k$로 미분해서 0이 되는 지점을 구하면:

$$
\frac{\partial J}{\partial \mu_k} = \sum_{x \in C_k} -2(x - \mu_k) = 0
$$

$$
\Rightarrow \mu_k = \frac{1}{|C_k|}\sum_{x \in C_k} x
$$

즉 "그 군집에 속한 데이터들의 평균"이 WCSS를 최소화하는 유일한 지점이다.
갱신 단계가 평균으로 이동하는 건 임의의 선택이 아니라, 그 시점에서 $J$를 가장 작게 만드는 수학적으로 최적인 위치로 움직이는 것이다.

매 반복마다 이 $J$ 값이 줄어들거나 그대로 유지된다(절대 늘지 않음).

-> 할당 단계는 각 점을 더 가까운 중심점으로 옮겨서 $J$를 줄이고, 갱신 단계는 방금 증명한 대로 $\mu_k$를 최적 위치로 옮겨서 또 줄인다.
두 단계 모두 $J$를 늘리는 방향으로는 절대 움직이지 않으니 알고리즘이 결국 멈춘다(수렴이 보장됨).

다만 전역 최적해(global optimum)가 보장되는 건 아니다.

-> 초기 중심점 위치에 따라 다른 (지역적으로 최적인) 결과가 나올 수 있다. 그래서 보통 여러 번 다른 초기값으로 시도해서(n_init) 가장 좋은 결과를 채택한다.

6. 계산 복잡도: 데이터가 많아도 감당 가능한 이유

한 번의 반복(할당+갱신)에 드는 연산량을 따져보자.

할당 단계에서 $n$개의 데이터 각각에 대해 $K$개의 중심점까지 거리를 계산($d$차원 벡터 간 거리 계산은 $O(d)$)하므로 $O(nKd)$.
갱신 단계는 각 데이터를 자기 군집의 합산에 한 번씩만 더하면 되므로 $O(nd)$로 할당 단계보다 가볍다.

전체 반복 횟수를 $i$라 하면:

$$
O(nKdi)
$$

핵심은 데이터 개수 $n$에 대해 **선형(linear)**이라는 점이다.

데이터가 10배 늘어나면 연산량도 대략 10배만 늘어난다(제곱이나 그 이상으로 폭증하지 않는다)

-> 수만~수백만 건 규모에서도 KMeans가 비교적 감당 가능한 속도로 동작한다.

7. 할당 경계의 모양: 보로노이 다이어그램

중심점들이 고정된 상태에서 "이 점은 어느 중심점에 배정되는가"를 평면 전체에 대해 그려보면, 
중심점 사이의 경계선은 항상 두 중심점을 잇는 선분의 수직이등분선이 된다. (두 중심점으로부터 거리가 같은 점들의 집합이니까)

보로노이 다이어그램

이 경계선들이 만들어내는, 즉 평면을 다각형 영역으로 나누는 패턴을 보로노이 다이어그램(Voronoi diagram)이라고 부른다.

KMeans의 "할당" 단계는 본질적으로 각 점이 어느 보로노이 셀(cell)에 속하는지를 찾는 것과 같다.

8. $K$는 어떻게 정하는가: Elbow Method

KMeans를 쓰려면 군집 개수 $K$를 미리 정해줘야 한다.

그런데 "몇 개로 나눠야 적절한지"는 데이터만 보고는 바로 알기 어렵다.

이 때, 가장 단순하고 널리 쓰이는 방법이 elbow method(팔꿈치 방법)다.

절차

1. $K$를 1, 2, 3, ...으로 늘려가며 매번 KMeans를 돌린다.
2. 그때마다 목적함수 $J$(WCSS)를 기록한다.
3. $K$(x축) vs $J$(y축) 그래프를 그린다.

왜 팔꿈치 모양?

• $K$가 작을 때: 군집을 하나 늘릴 때마다 $J$가 크게 줄어든다
• 어느 지점을 넘어서면: 군집을 더 늘려도 $J$가 거의 안 줄어든다.
  이미 자연스러운 그룹들을 다 찾았기 때문에, 그 이상 쪼개는 건 억지로 나누는 것에 가깝다
• 이 "기울기가 급격히 완만해지는 지점"이 팔꿈치처럼 꺾여 보여서 elbow라고 부르고, 그 지점의 $K$를 적절한 군집 수로 채택한다

한계

실제 데이터에서는 팔꿈치가 이렇게 선명하게 안 꺾이고 완만하게 이어지는 경우가 많음.
-> 어디가 "꺾이는 지점"인지 보는 사람마다 다르게 판단할 수 있음.

그래서 실전에서는 elbow method 하나만 보지 않고,
실루엣스코어를 같이 계산해서 더 객관적인 근거로 $K$를 정하는 경우가 많다.

또한 실루엣스코어는 군집화 후에 "군집 분리가 잘 됐는지"의 평가 지표로도 쓰인다.

9. 정리

• KMeans = 중심점 $K$개를 할당↔갱신 반복해서 WCSS를 최소화하는 비지도 클러스터링
• 갱신 단계가 "평균"으로 이동하는 건 임의가 아니라 WCSS를 최소화하는 수학적 최적해(미분=0 지점)
• k-means++로 초기화하면 지역 최적해에 빠질 위험을 줄일 수 있음
• 계산량이 데이터 수에 선형($O(nKdi)$)이라 대용량에도 비교적 잘 버팀
• $K$는 elbow method나 Silhouette Score로 정함