K-means, GMM, EM: 클러스터링의 세 겹 러시안 인형

숨겨진 구조를 찾는 문제

이 세 가지의 관계는 알 것 같으면서도 자꾸 까먹는다. 다음에 또 헷갈릴 미래의 나를 위해 정리해둔다. (Claude의 도움을 받아 작성했다.)

데이터가 있다. 레이블은 없다. 하지만 눈으로 보면 뭔가 “덩어리"가 보인다.

이 덩어리를 자동으로 찾아내는 것이 클러스터링이다. 여기에는 근본적인 질문이 숨어 있다.

“각 데이터가 어떤 덩어리에 속하는지” — 이 숨겨진 정보를 어떻게 추정할 것인가?

이 질문에 답하는 세 가지 방법이 있다. K-means, GMM, EM 알고리즘. 놀랍게도 이 셋은 독립된 방법이 아니라, 러시안 인형처럼 서로 안에 들어있는 구조다.

graph LR
    subgraph EM["EM 알고리즘"]
        subgraph GMM["GMM"]
            K["K-means"]
        end
    end
    style EM stroke:#2196F3,stroke-width:2px
    style GMM stroke:#FF9800,stroke-width:2px
    style K stroke:#E91E63,stroke-width:2px

K-means: 가위로 자르기

K-means는 가장 직관적인 클러스터링이다. 알고리즘은 두 단계를 반복한다.

1. 각 데이터를 가장 가까운 중심에 배정한다 (Assign)
2. 각 그룹의 평균으로 중심을 옮긴다 (Update)

graph TD
    A["중심점 초기화"] --> B["각 데이터를
가장 가까운 중심에 배정"]
    B --> C["중심을 그룹 평균으로
이동"]
    C --> D{"변화 있음?"}
    D -->|"예"| B
    D -->|"아니오"| E["완료"]

핵심 특성은 hard assignment다. 각 데이터는 반드시 하나의 클러스터에만 속한다. “70%는 A, 30%는 B” 같은 것은 허용되지 않는다.

K-means가 최소화하는 것은 결국 이것이다:

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

각 데이터와 소속 클러스터 중심 사이 거리의 총합. 단순하고 빠르다. 하지만 가정이 강하다.

• 모든 클러스터가 구형(원형)이다
• 모든 클러스터의 크기가 비슷하다
• 경계가 칼로 자른 듯 명확하다

현실의 데이터는 보통 이렇게 깔끔하지 않다.

GMM: 구름으로 감싸기

Gaussian Mixture Model은 K-means의 가정을 풀어준다. 각 클러스터를 “점"이 아니라 “구름”(가우시안 분포)으로 모델링한다.

$$p(x) = \sum_{k=1}^{K} \pi_k \cdot \mathcal{N}(x | \mu_k, \Sigma_k)$$

• $\pi_k$: 클러스터 $k$의 비율 (혼합 가중치)
• $\mu_k$: 클러스터 $k$의 중심
• $\Sigma_k$: 클러스터 $k$의 모양과 크기 (공분산 행렬)

K-means와의 결정적 차이는 soft assignment다. 각 데이터에 대해 “이 데이터가 클러스터 $k$에서 나왔을 확률"을 계산한다.

$$r_{ik} = \frac{\pi_k \cdot \mathcal{N}(x_i | \mu_k, \Sigma_k)}{\sum_j \pi_j \cdot \mathcal{N}(x_i | \mu_j, \Sigma_j)}$$

이 $r_{ik}$를 responsibility(책임도)라 부른다. “클러스터 $k$가 데이터 $x_i$에 대해 얼마나 책임이 있는가"라는 의미다.

EM 알고리즘: 숨겨진 것을 찾는 일반 원리

GMM의 파라미터를 어떻게 학습할까? 데이터가 어느 클러스터에서 왔는지 알면 간단하다. 하지만 그것이 바로 우리가 알고 싶은 정보다. 닭이 먼저냐 달걀이 먼저냐의 상황이다.

클러스터 소속을 알면 파라미터를 구할 수 있고, 파라미터를 알면 소속을 구할 수 있다.

EM(Expectation-Maximization) 알고리즘은 이 교착 상태를 “번갈아 가며” 풀어낸다.

• E-step (Expectation): 현재 파라미터로 잠재변수의 기대값을 계산한다
• M-step (Maximization): 그 기대값을 이용해 파라미터를 업데이트한다

graph TD
    A["파라미터 초기화 θ⁰"] --> B["E-step
현재 θ로 잠재변수의
사후확률 계산"]
    B --> C["M-step
사후확률을 이용해
파라미터 업데이트"]
    C --> D{"수렴?"}
    D -->|"아니오"| B
    D -->|"예"| E["최종 파라미터 θ*"]

GMM에 적용하면:

• E-step: responsibility $r_{ik}$ 계산 (각 데이터가 각 클러스터에 속할 확률)
• M-step: $r_{ik}$를 가중치로 사용해서 $\mu_k$, $\Sigma_k$, $\pi_k$ 업데이트

EM은 GMM에만 쓰이는 것이 아니다. 잠재변수가 있는 모든 확률 모델에 적용 가능한 일반 프레임워크다. Hidden Markov Model, 토픽 모델 등에도 모두 EM을 쓴다.

핵심 통찰: K-means는 GMM의 극한이다

여기서 가장 흥미로운 연결이 드러난다. GMM에서 다음 조건을 걸면:

1. 모든 클러스터의 공분산을 $\sigma^2 I$로 고정 (구형, 동일 크기)
2. $\sigma \to 0$으로 보낸다

그러면 responsibility $r_{ik}$는 어떻게 될까?

$$\lim_{\sigma \to 0} r_{ik} = \begin{cases} 1 & \text{if } k = \arg\min_j |x_i - \mu_j|^2 \ 0 & \text{otherwise} \end{cases}$$

soft assignment가 hard assignment로 변한다. 가장 가까운 클러스터에 확률 1, 나머지에 확률 0. 이것이 K-means의 assign 단계와 정확히 같다.

직관적으로 이해하면: 분산 $\sigma^2$은 “클러스터 구름의 퍼진 정도"다. 구름이 극단적으로 날카로워지면(분산→0), 각 구름은 점이 되고, soft한 경계는 칼로 자른 듯한 경계가 된다.

graph LR
    A["GMM
σ² 크다
퍼진 구름"] --> B["GMM
σ² 작다
날카로운 구름"]
    B --> C["K-means
σ² → 0
점"]
    A -.- D["soft assignment
확률적 경계"]
    C -.- E["hard assignment
명확한 경계"]
    style A stroke:#2196F3,stroke-width:2px
    style B stroke:#FF9800,stroke-width:2px
    style C stroke:#E91E63,stroke-width:2px

EM의 보증: 매 반복마다 나아진다

EM 알고리즘이 작동하는 이유는 무엇일까? 핵심은 ELBO(Evidence Lower Bound)에 있다.

우리가 최대화하고 싶은 것은 log-likelihood $\log p(X|\theta)$다. 직접 최대화가 어려울 때, EM은 이것의 하한(lower bound)을 반복적으로 올린다.

$$\log p(X|\theta) \geq \underbrace{E_{q(Z)}[\log p(X,Z|\theta)] + H[q(Z)]}_{\text{ELBO}}$$

• E-step은 ELBO를 $\log p(X|\theta)$에 밀착시킨다 (하한을 최대한 끌어올림)
• M-step은 밀착된 ELBO를 더 올린다 (파라미터 개선)

이 과정에서 log-likelihood는 절대 감소하지 않는다. 매 반복마다 단조 증가가 보장된다. 다만 전역 최적(global optimum)에 도달한다는 보장은 없고, 지역 최적(local optimum)에 빠질 수 있다.

정보 기하학의 시선

여기서 한 걸음 더 들어가면, EM 알고리즘의 작동 원리가 정보 기하학의 언어로 깔끔하게 설명된다.

EM = KL Divergence를 반복적으로 줄이는 과정

E-step과 M-step은 각각 서로 다른 KL divergence를 최소화하는 과정으로 볼 수 있다.

• E-step: $q(Z)$와 $p(Z|X,\theta)$ 사이의 KL divergence를 0으로 만든다.

$$q^*(Z) = \arg\min_q D_{KL}(q(Z) | p(Z|X,\theta)) = p(Z|X,\theta)$$

• M-step: 모델 분포와 데이터 분포 사이의 KL divergence를 줄인다.

$$\theta^* = \arg\min_\theta D_{KL}(p_{\text{data}} | p_\theta)$$

즉 EM은 “두 종류의 거리를 번갈아 줄여나가는 과정"이다. 한 번은 잠재변수 공간에서, 한 번은 파라미터 공간에서.

graph TD
    A["현재 상태"] --> B["E-step
q(Z)와 p(Z|X,θ) 사이
KL divergence → 0"]
    B --> C["M-step
모델과 데이터 사이
KL divergence ↓"]
    C --> D["더 나은 상태"]
    D --> B
    style B stroke:#4CAF50,stroke-width:2px
    style C stroke:#FF9800,stroke-width:2px

파라미터 공간은 평평하지 않다

일반적인 gradient descent는 파라미터 공간을 유클리드 공간(평평한 공간)으로 취급한다. 하지만 확률 분포의 파라미터 공간은 굽어 있다.

예를 들어, 가우시안 분포의 평균을 $\mu=0$에서 $\mu=1$로 바꾸는 것과 $\mu=100$에서 $\mu=101$로 바꾸는 것은 “파라미터 숫자상” 같은 크기의 변화다. 하지만 분포 모양이 변하는 정도는 분산($\sigma^2$)에 따라 완전히 다르다. 분산이 작으면 분포가 크게 변하고, 분산이 크면 거의 안 변한다.

이 “실제로 분포가 얼마나 변하는가"를 측정하는 것이 Fisher information이다.

$$F_{ij}(\theta) = E_{p_\theta}\left[\frac{\partial \log p_\theta(x)}{\partial \theta_i} \cdot \frac{\partial \log p_\theta(x)}{\partial \theta_j}\right]$$

Fisher information은 파라미터 공간의 곡률을 알려주는 “계량 텐서(metric tensor)“다. 이것을 사용해서 gradient를 보정하면 natural gradient가 된다.

$$\Delta\theta = -F(\theta)^{-1} \nabla_\theta \ell(\theta)$$

EM ≈ Natural Gradient

Amari(1998)의 결과에 의하면, EM 알고리즘의 업데이트는 natural gradient descent와 동치라는 것이 알려져 있다. 즉 EM은 자동으로 파라미터 공간의 곡률을 고려해서, “정보적으로 가장 효율적인 방향"으로 파라미터를 업데이트한다.

이것이 EM이 단순한 gradient descent보다 수렴이 빠른 경우가 많은 이유다. 평평한 좌표계에서의 최단 경로가 아니라, 확률 분포 공간에서의 최단 경로를 따라 이동하기 때문이다.

K-means → GMM → EM의 정보 기하학적 위계

GMM에서의 Fisher Information과 “관성”

GMM 관점에서 Fisher information의 직관을 하나 더 붙이면:

• 어떤 클러스터의 responsibility가 높은 데이터가 많다 → 그 클러스터의 파라미터에 대한 Fisher information이 크다 → 파라미터가 쉽게 변하지 않는다 (“관성"이 크다)
• 반대로 responsibility가 애매한(여러 클러스터에 걸친) 데이터가 많은 영역에서는 Fisher information이 작다 → 파라미터가 쉽게 바뀐다 (“유연"하다)

확신 있는 배정일수록 안정적이고, 불확실한 영역일수록 더 민감하게 반응하는 것이다. 물리적 비유로 돌아가면, 질량이 큰 물체(확고한 클러스터)는 쉽게 밀려나지 않고, 질량이 작은 물체(불확실한 클러스터)는 조금의 힘에도 크게 움직인다.

정리: 하나의 뿌리에서 세 갈래로

graph TD
    EM["EM 알고리즘
잠재변수가 있는 모든 모델의
MLE를 위한 일반 프레임워크"]
    GMM["GMM
잠재변수 = 클러스터 소속
관측 모델 = 가우시안"]
    KM["K-means
GMM에서 σ→0
soft → hard assignment"]
    IG["정보 기하학적 해석
EM = natural gradient
파라미터 공간의 곡률을
자동으로 고려"]

    EM --> GMM
    GMM --> KM
    EM -.- IG

    style EM stroke:#2196F3,stroke-width:2px
    style GMM stroke:#FF9800,stroke-width:2px
    style KM stroke:#E91E63,stroke-width:2px
    style IG stroke:#9C27B0,stroke-width:2px

• K-means는 “가장 가까운 중심에 배정"이라는 직관적 방법이다
• GMM은 “확률적으로 배정"함으로써 유연성을 얻는다
• EM은 이런 “숨겨진 변수를 추정하는 문제” 일반을 풀기 위한 프레임워크다
• 정보 기하학은 EM이 왜 효율적인지, 세 방법의 관계가 왜 그렇게 되는지를 “확률 공간의 기하학"으로 설명한다

결국 이 세 방법은 같은 질문 — “보이지 않는 구조를 어떻게 찾을 것인가” — 에 대해 서로 다른 수준의 일반성으로 답하는 것이다.

참고 문헌

• Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. Chapter 9.
• Amari, S. (1998). Natural Gradient Works Efficiently in Learning. Neural Computation, 10(2), 251-276.
• Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum Likelihood from Incomplete Data via the EM Algorithm. JRSS-B, 39(1), 1-38.