스탠퍼드 CS229 Lecture 9: K-평균과 가우시안 혼합 모델 (Spring 2026)

TL;DR

이 강의에서는 K‑means를 하드 할당 클러스터링 알고리즘으로, 가우시안 혼합 모델(GMM)을 소프트 할당 확률적 대응물로 제시하며, 두 알고리즘이 기대‑최대화(EM) 루프를 통해 어떻게 해결되는지, 초기화가 왜 중요한지, 그리고 젠센 부등식이 EM에 대한 계산 가능한 하한을 어떻게 제공하는지를 보여줍니다.

K‑means 알고리즘 직관

K‑means는 각 점을 가장 가까운 클러스터 중심에 반복적으로 할당하고, 그 중심을 해당 점들의 평균으로 재계산함으로써 데이터를 K개의 클러스터로 분할하려고 합니다.

알고리즘은 무작위 초기 중심 μ₁ … μ_K로 시작하여, 각 점을 유클리드 거리를 사용해 가장 가까운 중심이 있는 클러스터에 할당하고, 각 중심을 해당 점들의 산술 평균으로 업데이트한 후, 할당이 더 이상 변하지 않을 때까지 반복합니다.

클러스터 레이블은 임의적이므로 모든 μ를 교환해도 동일한 해가 나오며, 중요한 것은 중심이 올바른 위치에 수렴하는지 여부입니다.

종료, 최적성, 및 초기화

K‑means는 항상 종료되는데, 이는 클러스터 내 제곱 거리 합(L₂ 목적 함수)이 단조 감소하고 하한이 존재하기 때문이며, 따라서 알고리즘은 할당이 더 이상 변하지 않는 고정점에 도달합니다.

이 목적 함수의 전역 최솟값을 찾는 것은 NP‑어려우므로, K‑means는 초기 중심에 의존하는 최적이 아닌 해로 수렴할 수 있습니다.

여러 지역 최소가 존재하며, 서로 다른 랜덤 초기화는 서로 다른 최종 클러스터링을 초래할 수 있는데, 따라서 초기화 단계가 매우 중요합니다.

초기화를 개선하기 위해 K‑means++ 절차는 좋은 근사 비율을 보장하는 방식으로 초기 중심을 선택하며, 이 변형은 scikit‑learn과 같은 일반적인 라이브러리의 기본값입니다.

클러스터 수 K 선택

K를 선택하는 것은 모델링 가정이며, 분석가는 데이터에 몇 개의 서로 다른 그룹이 존재하는지에 대한 사전 믿음을 표현해야 합니다.

K를 늘리면 더 세밀한 분할이 나오지만, 비용이 낮다고 해서 자동으로 더 나은 모델을 의미하는 것은 아니며, 더 큰 K가 실제로 유익한지 평가하려면 외부 지식이나 검증 기준이 필요합니다.

따라서 K를 선택하는 것은 순전히 알고리즘적 기준이 아니라 문제 영역에 의해 guida되는 정성적 결정으로 남아 있습니다.

하드에서 소프트 할당으로: 가우시안 혼합 모델

GMM은 K‑means의 하드 클러스터 멤버십을 확률적 할당으로 대체합니다: 각 점은 알려지지 않은 평균, 공분산, 혼합 가중치를 가진 K개의 가우시안 소스 중 하나에서 생성됩니다.

순방향 모델은 점 X_i의 출처를 나타내는 잠재 변수 Z_i를 가정하며, Z_i는 K개의 소스에 대한 다항 분포에서 추출되고, X_i는 이에 해당하는 가우시안에서 샘플링됩니다.

관측된 점들만을 바탕으로, 데이터를 가장 잘 설명하는 가우시안 매개변수와 혼합 가중치를 추론하는 것이 목표입니다.

가우시안 혼합 모델에 대한 기대‑최대화

EM은 두 단계 사이를 반복합니다:

• E‑step: 현재 매개변수 추정치에 베이즈 규칙을 적용하여 점 i가 소스 j에서 유래한 사후 확률 w_{ij}를 계산합니다.
• M‑step: 각 가우시안의 평균, 공분산, 혼합 가중치를 점들의 가중 평균으로 업데이트하며, 이때 가중치는 사후 확률 w_{ij}입니다.

사후 확률이 0 또는 1일 때, M‑step은 정확히 K‑means 업데이트로 축소되며, 그렇지 않은 경우 EM은 동일한 계산의 소프트, 가중 버전을 수행합니다.

알고리즘은 매개변수 추정치가 수렴할 때까지 반복됩니다.

젠센 부등식과 EM 하한

EM은 데이터 로그 우도의 하한을 최대화하는 것으로 볼 수 있습니다.

젠센 부등식은 볼록 함수 φ에 대해 𝔼[φ(X)] ≥ φ(𝔼[X])가 성립하며, 오목 함수에서는 부등호가 반전됩니다.

E‑step에서 EM은 현재 매개변수에서 tight하고 최적화하기 쉬운 surrogate 함수를 구성하며, 로그 우도에 젠센 부등식을 적용하면 이 surrogate를 얻어져 각 M‑step이 실제 우도를 증가시키거나 변하지 않게 보장합니다.

따라서 EM은 우도의 정지점에 수렴함을 보장하지만, 반드시 전역 최대점은 아닙니다.

실제적인 교훈

• K‑means는 간단하고 해석 가능하지만 초기화에 민감하며 열악한 지역 최점에 빠질 수 있습니다.
• K‑means++은 강력한 이론적 보장을 제공하는 중심 초기화의 원칙적인 방법을 제공합니다.
• GMM은 클러스터 멤버십의 불확실성을 모델링하고 공분산을 통해 타원형 클러스터 형태를 포착함으로써 K‑means를 확장합니다.
• EM은 잠재 변수 모델에 대한 일반적인 프레임워크를 제공하며, 그 수렴은 타이트한 하한을 구성하기 위해 젠센 부등식에 의존합니다.
• 두 알고리즘 모두 분석가가 클러스터 수 K를 지정하도록 요구하며, 이 모델링 결정은 도메인 지식을 바탕으로 해야 합니다.

이 개념들은 많은 현대 비지도 학습 기술의 기초를 형성하며, 알고리즘의 단순성, 계산적 난이도, 그리고 신중한 초기화와 모델 선택의 필요성 사이의 trade‑off를 보여줍니다.