k-평균 군집화

통계 수치해석 소프트웨어 마지막 수정: 2026-07-30 04:23:51

1. 개요[편집]

k-평균 군집화(k-means clustering)는 $n$ 개의 점을 미리 정한 $k$ 개의 군집으로 나누되, 각 점과 자기 군집 중심 사이의 제곱거리 합을 최소화하는 분할을 찾는 문제이자 그 문제를 푸는 표준 휴리스틱이다. 목적함수는 군집내 제곱합(WCSS), 흔히 관성(inertia)이라 부르는 값이다.

J(\mathcal{S}) = \sum_{i=1}^{k} \sum_{\mathbf{x} \in S_i} \lVert \mathbf{x} - \boldsymbol\mu_i \rVert^2, \qquad \boldsymbol\mu_i = \frac{1}{|S_i|}\sum_{\mathbf{x}\in S_i}\mathbf{x}

비지도 학습 강의 첫 주에 나오고, 구현이 열 줄이면 되고, 웬만한 데이터에 일단 던지면 뭔가 나온다. 그래서 세상에서 가장 많이 오용되는 알고리즘 중 하나이기도 하다. 아래에서 볼 가정들을 확인하지 않고 결과 그림에 색만 칠해 보고하면, 실제로는 존재하지 않는 군집을 발견했다고 주장하게 된다.

2. 로이드 알고리즘[편집]

$J$ 를 최소화하는 분할을 정확히 찾는 문제는 NP-난해다. 일반 차원에서 $k=2$ 만 되어도 그렇고, 평면( $d=2$ )에서 $k$ 가 일반이어도 그렇다.¹ 가능한 분할 수가 $k^n$ 근처라 전수 탐색은 애초에 논외. 그래서 실제로 돌리는 건 로이드 알고리즘(Lloyd’s algorithm)이라는 교대 최소화다.

배정 단계 — 각 점을 가장 가까운 중심에 배정한다. 중심을 고정한 채 $J$ 를 최소화하는 최적 배정이다.
갱신 단계 — 각 군집의 중심을 배정된 점들의 산술평균으로 옮긴다. 배정을 고정한 채 $J$ 를 최소화하는 최적 중심이다(제곱오차의 최소점이 평균이라는 사실 그대로).²
배정이 변하지 않을 때까지 반복.

두 단계 모두 $J$ 를 증가시키지 않고, 가능한 분할은 유한하므로 유한 스텝에 반드시 멈춘다. 다만 멈추는 곳은 지역 최소점이며, 최악의 경우 반복 횟수가 초다항적으로 늘어나는 입력이 구성 가능하다. 현실 데이터에서는 대개 수십 번 안에 끝나는데, 이건 이론이 아니라 경험칙에 가깝다.³ 한 반복의 비용은 소박하게 짜면 $O(nkd)$ .

3. 보로노이 분할과의 관계[편집]

배정 단계는 기하학적으로 정확히 중심들이 만드는 보로노이 다이어그램으로 공간을 자르는 것이다. 따라서 k-평균의 군집 경계는 언제나 초평면 조각으로 이루어진 볼록 다면체다. 곡선 경계는 원리적으로 나올 수 없다.

수렴한 해는 각 보로노이 셀의 생성점이 그 셀의 무게중심과 일치하는 상태, 즉 중심 보로노이 테셀레이션(CVT)이다. 이 관점 덕분에 k-평균은 통계 바깥에서도 계속 튀어나온다 — CVT 기반 메시 생성에서 격자점을 고르게 퍼뜨리는 로이드 완화(Lloyd relaxation)가 바로 같은 반복이고, 들로네 삼각분할과의 쌍대성도 그대로 따라온다.

4. 초기화 — k-means++[편집]

로이드 알고리즘의 결과는 초기 중심에 심하게 좌우된다. 무작위로 $k$ 개 점을 골라 시작하면 두 중심이 같은 덩어리에 빠지고 다른 덩어리는 통째로 하나로 뭉개지는 사고가 흔하다.

k-means++(Arthur & Vassilvitskii, 2007)는 이걸 확률적 거리 비례 표본추출로 고친다. 첫 중심은 균등하게 하나 뽑고, 이후 각 중심은 이미 뽑힌 중심들까지의 최단거리 $D(\mathbf{x})$ 에 대해

\Pr[\mathbf{x} \text{ 선택}] = \frac{D(\mathbf{x})^2}{\sum_{\mathbf{x}'} D(\mathbf{x}')^2}

의 확률로 뽑는다. 멀리 떨어진 점이 뽑힐 확률이 높지만 확정은 아니라서, 이상점 하나에 중심을 낭비하는 최악의 경우를 피한다. 이 초기화만으로도 기댓값 기준 $O(\log k)$ 근사 보장이 붙는다.

\mathbb{E}[J] \le 8(\ln k + 2)\, J_{\mathrm{OPT}}

로이드 반복을 한 번도 안 돌린 시점에서 이미 그렇다는 것이 요점이다. 오늘날 대부분의 라이브러리 기본값이며, 그래도 서로 다른 시드로 여러 번 돌려 $J$ 가 가장 작은 해를 채택하는 다중 시작은 여전히 권장된다.

5. k를 어떻게 고를까[편집]

가장 성가신 부분. $J$ 는 $k$ 에 대해 단조 감소하므로( $k=n$ 이면 0) 관성만 보고 $k$ 를 고를 수는 없다.

엘보 방법 — $J(k)$ 곡선이 꺾이는 지점을 눈으로 찾는다. 원리적 기준이 없고, 실전 데이터에서는 팔꿈치가 아예 안 보이는 경우가 태반이다.
실루엣 계수 — 점 $i$ 에 대해 자기 군집 내 평균거리 $a_i$ , 가장 가까운 다른 군집까지의 평균거리 $b_i$ 를 놓고 $s_i = (b_i - a_i)/\max(a_i,b_i) \in [-1,1]$ . 전체 평균이 큰 $k$ 를 고른다. 계산이 $O(n^2)$ 이라 큰 데이터에선 표본추출이 필요하다.
갭 통계 — 관측 데이터의 $\ln W_k$ 를, 군집 구조가 없는 균등 참조분포에서 같은 절차로 얻은 기댓값과 비교해 격차가 최대인 $k$ 를 고른다(Tibshirani 등, 2001). 유일하게 “군집이 하나뿐”이라는 답도 낼 수 있는 축에 든다.
정보기준 — 모형 기반으로 옮겨 가서 BIC로 고르는 X-means 계열. 사실상 가우시안 혼합 모형 쪽 문법이다.

셋 이상을 돌려서 서로 다른 답이 나오면, 그건 도구 문제가 아니라 데이터에 뚜렷한 군집 구조가 없다는 신호일 확률이 높다.

6. 가정과 한계[편집]

k-평균이 암묵적으로 요구하는 것들이다. 하나라도 깨지면 결과는 조용히 틀린다.

등방·구형 군집. 목적함수가 유클리드 제곱거리라 길쭉하거나 기울어진 군집을 잘라 버린다.
비슷한 크기(분산과 개수). 큰 군집이 작은 군집의 점을 빼앗아 가는 편향이 있다. 밀도가 크게 다른 덩어리들이 섞여 있으면 경계가 엉뚱한 곳에 선다.
스케일 민감. 단위가 다른 축을 그냥 넣으면 값이 큰 축이 거리를 독점한다. 표준화는 선택이 아니라 전처리 필수 단계다. 차원이 높으면 주성분 분석으로 먼저 줄이는 것이 관례인데, 실제로 PCA 부분공간이 k-평균 목적함수의 연속 완화해와 관련된다는 결과도 있다.
이상점에 취약. 중심이 평균이라 극단값 하나가 중심을 끌고 간다. 중앙값을 쓰는 k-medoids/PAM이 대안.
볼록 아닌 군집은 불가능. 동심원 두 개는 절대 못 나눈다. 이건 튜닝으로 해결되지 않으며 스펙트럴 군집화나 밀도 기반 방법으로 갈아타야 한다.
$k$ 를 사람이 준다. 그리고 어떤 $k$ 를 주든 알고리즘은 성실하게 그 개수만큼 군집을 만들어 낸다. 군집이 없는 데이터에도.⁴

대용량 처리는 미니배치 k-평균(Sculley, 2010)이 맡는다. 매 반복 크기 $b$ 의 미니배치만 배정하고, 각 중심을 그 중심이 받은 누적 표본 수를 학습률로 삼아 조금씩 옮긴다. 품질을 조금 내주는 대신 속도가 자릿수로 빨라져서, 웹 스케일 데이터에서 사실상 표준.

7. GMM의 하드 배정 극한[편집]

k-평균은 가우시안 혼합 모형에 EM을 돌리는 것의 극한으로 정확히 유도된다. 모든 성분에 $\boldsymbol\Sigma_i = \sigma^2 \mathbf{I}$ (등방·동일)와 균등 혼합계수를 강제하고 $\sigma \to 0$ 을 보내면, E-단계의 책임도

\gamma_{ji} = \frac{\exp\!\big(-\lVert \mathbf{x}_j - \boldsymbol\mu_i\rVert^2 / 2\sigma^2\big)}{\sum_{l}\exp\!\big(-\lVert \mathbf{x}_j - \boldsymbol\mu_l\rVert^2/2\sigma^2\big)}

에서 지수의 스케일이 무한대로 커져 가장 가까운 중심 하나만 1, 나머지는 0인 지시함수로 붕괴한다. 그러면 E-단계는 “가장 가까운 중심에 배정”, M-단계는 “배정된 점의 평균으로 이동”이 되어 정확히 로이드 알고리즘이다. 즉 k-평균 = 소프트 배정을 하드 배정으로 굳힌 EM. 기댓값 최대화 알고리즘의 단조성 논증이 그대로 넘어와 $J$ 의 단조 감소를 설명해 준다.

실무 순서도 여기서 나온다 — k-평균++로 시작해 로이드 몇 번 돌린 결과를 GMM의 초기 중심으로 넘기는 것이 사실상 표준 파이프라인이다.

8. 시뮬레이션 바닥에서의 쓰임[편집]

벡터 양자화 — 신호처리에서 코드북을 설계하는 LBG 알고리즘이 본질적으로 k-평균이다. 색 양자화(24비트 이미지를 256색 팔레트로)도 RGB 공간의 k-평균이고, 오래된 GIF 인코더가 하던 일이 이것.
스냅숏 군집화 기반 ROM — 축소차수모델에서 전 구간에 POD 기저 하나를 쓰면 대류 지배 문제에서 기저 개수가 폭발한다. 스냅숏을 군집으로 나눠 군집마다 국소 기저를 두고 상태에 따라 갈아 끼우는 접근이 있으며, 난류 데이터에 이걸 적용한 군집 기반 ROM 계열이 대표적이다.
영역 분할 — 병렬 컴퓨팅에서 격자를 프로세스에 나눠 줄 때 셀 중심 좌표에 k-평균을 돌리면 기하학적으로 뭉친 균형 잡힌 조각이 나온다. 다만 실무 표준은 여전히 통신량(절단 간선)을 직접 최소화하는 그래프 분할 쪽이다 — k-평균은 부하 균형을 보장하지 않기 때문.
입자·군중 처리 — 파티클 그룹핑, 광원 클러스터링(타일드 라이팅), 군중 시뮬레이션의 그룹 단위 경로 계획 등에서 값싼 공간 분할로 쓰인다.

9. 관련 문서[편집]

Aloise 등(2009)이 일반 차원 $k=2$ 의 NP-난해성을, Mahajan 등이 평면에서 일반 $k$ 의 NP-난해성을 보였다. “학부 실습으로 나오는 알고리즘이 푸는 문제가 NP-난해”라는 조합은 생각보다 흔하다. 알고리즘이 정답을 보장하지 않을 뿐이니까. ↩
이름에 “평균”이 들어가는 이유가 갱신 단계 그 자체다. 거리를 제곱이 아닌 다른 것으로 바꾸면 중심 갱신식도 바뀌어서, $L^1$ 이면 중앙값(k-medians)이 되고 코사인 거리면 정규화된 평균(구면 k-평균)이 된다. 목적함수가 갱신식을 결정한다는 교과서적 예시. ↩
Arthur & Vassilvitskii가 반복 횟수를 초다항으로 밀어올리는 입력을 구성했고, 이후 평활화 해석(smoothed analysis)으로 “입력에 아주 작은 잡음만 있어도 기대 반복 횟수가 다항”임이 보여졌다. 현실 데이터가 최악의 경우를 만들 만큼 정교하게 사악하지 않다는 것이 요지. ↩
균등분포에서 뽑은 완전한 난수 점군에 k-평균을 돌려 보면 아주 예쁜 벌집 모양 군집이 나온다. 보로노이 분할이 원래 그렇게 생겼기 때문이다. 발표 자료에 그 그림만 띄우면 아무도 의심하지 않는다는 게 무섭다. ↩