K-평균 군집(K-Means)K-Means Clustering
표본마다 가장 가까운 중심에 배정하는 일과 중심을 그 군집의 평균으로 옮기는 일을 번갈아 되풀이해, 군집 안 제곱 거리 합(SSE)을 줄이는 군집 알고리즘이다.
1요약
- K-평균 군집은 비지도 학습의 중심 기반 분할 방법으로, 배정 · 갱신을 번갈아 도는 Lloyd 반복과 k-평균++ 초기화가 표준 구현이며(Arthur 2007 2절), 그 위에서 고객 세분화 · 벡터 양자화 · 이미지 색 줄이기가 돈다.
- 레이블 없는 표본을 사람이 기준을 정해 손으로 나누면 기준이 사람마다 갈린다 — k-평균은 반복마다 거리 계산 n · k 번으로 묶음을 정하고, 사례의 간헐천 분출 272회는 3회 반복에 SSE 102.68 → 79.58 로 멈췄다.
- 「군집이 이상하다」는 세 갈래로 가른다 — 실행마다 결과가 바뀌면 초기화, k 를 바꿔도 SSE 꺾임 · Gap 최댓값이 없으면 k, 늘어나거나 크기가 다른 무리를 가로지르면 모양 가정이다(그림 6).
2등장 배경
연속 신호를 디지털로 바꿀 때는 값의 범위를 대표 값 몇 개로 나눠야 한다. 벨 연구소의 Lloyd 는 1957년 사내 메모에서 «구간마다 대표 값 = 그 구간 표본의 평균, 경계 = 대표 값 사이 가운데»를 번갈아 맞추는 양자화 반복을 냈고, 이 글은 1982년에야 학술지에 실렸다(Lloyd 1982). 1967년 MacQueen 이 같은 생각을 다변량 표본 분류에 쓰며 «k-means» 라는 이름을 붙였다(MacQueen 1967).
그 뒤 약점이 하나씩 다뤄졌다. 2001년 Gap 통계가 k 를 기준 분포와 비교해 고르는 규칙을 냈고(Tibshirani 2001), 2007년 k-평균++ 는 초기 중심을 거리 제곱에 비례해 뽑아 기대 SSE 를 최적의 O(log k) 배 안으로 묶었으며(Arthur 2007 3절), 2010년 미니배치 갱신이 웹 규모 데이터에서 계산을 줄였다(Sculley 2010). 2011년에는 평면에서도 반복 횟수가 최악 2^Ω(n) 이 될 수 있음이 증명됐다(Vattani 2011).
지금도 군집 분석의 첫 기준선이다 — scikit-learn KMeans 의 기본값은 init= · max_iter=300 · tol=1e-4 이다(scikit-learn KMeans 문서). IT 쪽에서는 데이터 마이닝의 군집 분석 기법으로 같은 알고리즘을 다룬다 — 그쪽은 KDD 절차 안의 자리와 연관 규칙 · 분류와의 구분을 맡고, K-평균 군집은 초기화 · 수렴 · k 선택 · 한계를 맡는다.
3쉽게 이해하기 — 택배 보관함 두 대를 놓는 관리소장 도윤
새 단지 관리소장 도윤은 택배 보관함 두 대를 어디 둘지 정해야 한다. 한 대는 아무 동 앞에 두고, 둘째 자리는 첫 보관함에서 멀리 떨어진 동일수록 잘 뽑히게 제비를 뽑는다. 동마다 더 가까운 보관함을 정해 주고, 보관함을 맡은 동들의 한가운데로 옮긴 뒤 다시 가까운 쪽을 정해 준다. 옮겨도 맡는 보관함이 바뀌는 동이 하나도 없으면 그 자리로 굳힌다.
그림 1 · 도윤은 첫 자리를 멀리 떨어지게 뽑고, 가까운 함 정하기와 한가운데로 옮기기를 바뀌는 동이 없을 때까지 되풀이한다.
그림 2 · 보관함을 맡은 집들의 평균 자리로 옮기면 걸음 제곱 합이 53 에서 26 으로 줄고, 실제 갱신 단계도 같은 이유로 사례 SSE 를 102.68 에서 80.42 로 줄인다.
| 비유 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 단지의 동 | 표본 x | 특징 d 개의 점 하나(사례 = 분출 1회 · 분출 시간 · 대기 시간) |
| 보관함 수 | k | 사람이 미리 정하는 군집 수 · Gap 통계 등으로 고름 |
| 첫 자리 · 둘째 제비 | k-평균++ 초기화 | 첫 중심은 무작위 · 다음 중심은 가장 가까운 중심까지 거리² 에 비례해 뽑음 |
| 보관함 자리 | 중심 μⱼ | 군집마다 대표 점 하나 · 군집 평균 |
| 가까운 함 정하기 | 배정 단계 | 표본마다 거리가 가장 짧은 중심의 번호를 붙임 |
| 한가운데로 옮기기 | 갱신 단계 | 중심을 그 군집 표본의 평균으로 바꿈 |
| 걸음² 의 합 | SSE(관성) | 표본과 자기 중심 사이 제곱 거리의 합 · 두 단계가 모두 줄이거나 그대로 둠 |
| 바뀐 동 없음 | 수렴 | 배정이 바뀐 표본 0 또는 중심 이동이 tol 미만이면 멈춤 |
⚠ 비유가 맞지 않는 곳: 걸음은 실제 거리지만 k-평균은 특징 공간의 유클리드 거리를 쓰므로 단위가 다른 열은 먼저 표준화해야 한다. 또 도윤이 찾은 자리는 «더 옮길 이유가 없는» 자리일 뿐 가장 좋은 자리라는 보장이 없다 — 첫 제비가 다르면 다른 자리에서 굳을 수 있다.
4구조 — 초기화 · 배정 · 갱신 · 수렴 판정
그림 3 · 사람이 정한 k 로 초기화한 뒤 배정 · 갱신을 바뀐 표본이 0 이 될 때까지 돌고, 이 전체를 n_init 번 되풀이해 SSE 가 가장 작은 실행을 남긴다.
| 요소 | 역할 | 값 · 근거 |
|---|---|---|
| k | 군집 수 · 사람이 정함 | Gap 통계 · SSE 꺾임으로 고름(Tibshirani 2001) |
| 초기화 | 반복의 출발점 · 결과를 바꿈 | k-평균++ = D² 가중 · 기대 SSE ≤ 8(ln k + 2) × 최적(Arthur 2007 정리 3.1) |
| 배정 단계 | 표본마다 가장 가까운 중심 번호 | 경계 = 두 중심의 수직 이등분선(보로노이 분할) |
| 갱신 단계 | 중심 = 군집 평균 | 평균이 제곱 거리 합 최소(Arthur 2007 2.1절) |
| 수렴 판정 | 멈출 때 | 바뀐 표본 0 · 이동 < tol(기본 1e-4) · max_ |
| SSE(관성) | 목적 함수 · 비교 기준 | Σ‖x − μ_c(x)‖² · inertia_ |
목적 함수는 SSE = Σ‖x − μ_c(x)‖² 하나다. 정확한 최솟값 찾기는 k = 2 에서도 NP-난해라(Arthur 2007 1절) Lloyd 반복은 국소 최솟값에서 멈추고, 그래서 초기화와 n_init 이 구조의 일부가 된다.
🔑 k-평균이 찾는 것은 «SSE 의 최솟값»이 아니라 «배정 · 갱신 어느 쪽으로도 더 줄지 않는 자리»다 — 그래서 같은 k 라도 출발점이 다르면 답이 다르다.
5동작 — 간헐천 분출 272회를 두 군집으로
직접 실행 사례다(NumPy 로 k-평균 · k-평균++ · Gap 통계를 구현 · default_rng(0) 하나).
- 미국 옐로스톤 국립공원 간헐천의 분출 272회 기록을 읽는다 — 분출 시간 1.6 ~ 5.1분 · 다음 분출까지 대기 43 ~ 96분 두 열이다(R faithful 문서).
- 대기 열의 분산이 분출 시간 열의 약 142배라 그대로 두면 거리를 대기 시간 혼자 정한다 — 열마다 평균(3.488분 · 70.90분) · 표준편차(1.139분 · 13.57분)로 표준화한다.
- k = 2 로 k-평균++ 초기화를 한다 — 첫 중심은 무작위로 뽑힌 분출(2.417분 · 54분), 둘째는 D² 비례 확률로 뽑힌 분출(4.567분 · 78분)이며 이 표본의 뽑힐 확률은 0.55% 로 균등(0.37%)의 1.5배였다(Arthur 2007 2.2절).
- 반복 1 — 배정 뒤 SSE 102.68, 갱신으로 두 중심이 군집 평균으로 옮겨 80.42 가 되고, 다음 배정에서 2개 표본이 군집을 바꾼다.
- 반복 2 · 3 — SSE 79.76 → 79.64(1개 바뀜), 79.61 → 79.58(0개)로 바뀐 표본이 0 이 되어 3회 만에 멈춘다.
- 결과 — 군집 A 98회는 분출 2.05분 · 대기 54.6분, 군집 B 174회는 4.30분 · 80.1분이다(원 단위로 되돌림).
- k = 1 ~ 8 마다 초기화 10회 중 SSE 최소를 남기면 544 → 79.6 → 56.3 → 43.9 로 k = 2 에서 85% 줄고 그다음은 29% 다. 균등 기준 분포 20벌로 Gap 을 재면 Gap(2) = 1.312 ≥ Gap(3) − s₃ = 1.269 − 0.040 이라 규칙대로 k = 2 를 고른다(Tibshirani 2001).
그림 4 · 두 중심은 k-평균++ 가 고른 분출 두 곳에서 출발해 반복 1 의 갱신에서 대부분 움직이고, 반복 3 에서 바뀐 표본이 0 이 되어 짧은 분출 · 긴 분출 두 무리에 멈춘다.
같은 데이터에서 시드 0 ~ 19 로 초기화를 한 번씩만 하면 무작위 초기화는 2 ~ 6회, k-평균++ 는 1 ~ 4회 반복에 멈추고 SSE 는 모두 79.58 로 같았다 — 두 무리가 뚜렷한 k = 2 에서는 초기화가 답이 아니라 반복 횟수만 바꾼다.
그림 5 · 배정과 갱신이 번갈아 SSE 를 줄이거나 그대로 두므로 같은 분할이 다시 나오지 않고, 분할의 수가 유한해 반복은 반드시 멈춘다.
🔑 수렴은 «좋은 답에 닿았다»가 아니라 «더 줄일 단계가 없다»는 뜻이다 — 사례처럼 3회에 멈춰도 그 자리가 국소 최솟값인지 전역 최솟값인지는 다른 출발점과 SSE 를 견줘 봐야 안다.
6비교 — k-평균 · 미니배치 · k-중앙자 · 가우스 혼합 · DBSCAN
| 기준 | k-평균(Lloyd) | 미니배치 k-평균 | k-중앙자(PAM) | 가우스 혼합(EM) | DBSCAN |
|---|---|---|---|---|---|
| 군집 대표 | 평균(실제 표본 아님) | 평균의 근사 | 실제 표본 하나 | 평균 · 공분산 · 비율 | 대표 없음 · 밀도 연결 |
| 가정하는 모양 | 둥글고 퍼짐이 비슷함 | k-평균과 같음 | 거리 기준 묶음 | 타원 · 크기 다름 허용 | 모양 제약 없음 |
| 반복 한 번 계산 | n × k | 배치 b × k | 표본 쌍 거리 | n × k × 공분산 | 이웃 검색 |
| 이상치 | 중심을 끌고 한 점 군집이 생김 | 같음 | 중앙자가 실제 표본이라 덜 끌림 | 분산이 큰 성분으로 흡수 | 잡음으로 따로 표시 |
| 정할 값 | k | k · 배치 크기 | k | k · 공분산 꼴 | Eps · MinPts |
| 근거 | Lloyd 1982 | Sculley 2010 | Kaufman 1990 2장 | Dempster 1977 | Ester 1996 |
그림 6 · k-평균은 둥글고 크기가 같은 무리는 그대로 찾지만, 한 방향으로 늘어난 무리와 크기 · 퍼짐이 다른 무리는 가로질러 자른다.
미니배치는 표본 1,024개씩 뽑아 중심을 조금씩 옮긴다(scikit-learn MiniBatchKMeans 문서 · batch_size=1024). 합성 데이터 10만 개 · k = 8 에서 같은 시작 중심으로 시드 0 은 전체 Lloyd 가 26회 반복에 거리 2,160만 번, 미니배치 100회가 81.9만 번(26배 적음)을 계산했고 SSE 는 0.57% 컸다. 시드 0 ~ 9 에서 이 차이는 0.09 ~ 20.1% 였고, 초기화를 한 번만 한 전체 Lloyd 끼리도 SSE 가 최대 1.61배 갈렸다.
분석무리가 둥글고 크기가 비슷하며 표본이 수십만 개 이하이면 k-평균에 n_init 을 여러 번 주고, 메모리에 다 올라가지 않으면 미니배치를, 늘어나거나 크기가 다른 무리면 가우스 혼합을, 잡음이 섞이고 모양이 제각각이면 DBSCAN 을 쓴다. 그림 6 에서 늘어난 무리 · 크기 차이 무리의 ARI(Hubert · Arabie 1985)가 k-평균 0.85 · 0.06 대 가우스 혼합 1.00 · 0.96 이고, 미니배치의 SSE 손실(0.09 ~ 20.1%)보다 초기화 차이(최대 1.61배)가 더 컸다.
7실무 진단 — 군집 결과 이상의 원인 가르기
분석표현(표준화) → 초기화 → k → 모양 가정 순으로 본다. 표현이 틀리면 뒤의 모든 판단이 그 거리 위의 판단이 되고(사례 2단계), 초기화가 흔들리면 같은 k 에서도 SSE 가 1.61배까지 갈린다(비교 절 미니배치 실험).
| # | 증상 | 의심 원인 | 단계 | 확인 자료 | 판정 기준 |
|---|---|---|---|---|---|
| 1 | 군집이 한 열의 값으로만 갈림 | 단위 · 분산 차이 | 표현 | 열별 분산 비 · 중심의 원 단위 값 | 분산 비가 수십 배 이상이면 표준화 |
| 2 | 실행마다 SSE · 구성이 바뀜 | 국소 최솟값 | 초기화 | n_inertia_ 범위 | 최솟값과 몇 % 차이인가 · n_ |
| 3 | 표본 1 ~ 2개짜리 군집이 생김 | 이상치 · k 과다 | k · 데이터 | 군집 크기 · 그 표본의 거리 | 가정 값 1점(4.0분 · 200분)을 넣은 사례는 k = 3 에서 혼자 군집 |
| 4 | k 를 바꿔도 SSE 꺾임이 없음 | 군집 구조가 약함 | k | SSE 곡선 · Gap(k) − s | Gap(k) ≥ Gap(k+1) − sₖ₊₁ 인 첫 k(Tibshirani 2001) |
| 5 | 무리 하나가 여러 조각으로 잘림 | 모양 · 크기 가정 위반 | 모델 | 군집별 공분산 · 크기 비 | 크기 · 퍼짐 차이가 크면 가우스 혼합 · DBSCAN 과 비교 |
이상치 줄의 사례 값은 설명용 가정 값이다. 같은 점을 넣고 k = 2 로 돌리면 B 중심의 대기 시간이 80.08 → 80.74분으로 끌려가고, k-중앙자는 실제 표본(2.0분 · 55분 · 4.35분 · 80분)을 대표로 남긴다.
8시험 대비
www.q-net.or.kr시험에서는 배정 · 갱신 반복과 목적 함수를 쓰는 정의 · 동작 절차형, 그리고 계층 군집 · DBSCAN · 가우스 혼합과의 차이를 묻는 비교형이 나올 수 있다. 「가까운 중심에 넣고 평균을 다시 구한다」에서 멈추지 말고 SSE 식 · 수렴 이유 · 초기화 · k 선택 · 한계까지 한 답안에 넣는다.
- 정의 · 목적 — 비지도 중심 기반 분할 · SSE = Σ‖x − μ‖² 최소화 · 활용(세분화 · 벡터 양자화)
- 구조 — 그림 3 초기화 → 배정 → 갱신 → 수렴 판정 · 바깥 반복 n_init
- 동작 사례 — 그림 4 272회 분출 · 3회 반복 · SSE 102.68 → 79.58
- 수렴 · 초기화 — 그림 5 두 단계 모두 SSE 감소 · 국소 최솟값 · k-평균++ D² 가중 O(log k)
- k 선택 · 한계 — 엘보 · Gap 통계 · 그림 6 늘어난 · 크기 다른 무리 · 이상치
- 비교 · 개선 — 비교표(미니배치 · k-중앙자 · 가우스 혼합 · DBSCAN) · 선택 기준
꼭 쓸 키워드
배정 단계갱신 단계SSE관성국소 최솟값k-평균++엘보Gap 통계미니배치k-중앙자보로노이 분할
다른 답안과 차이를 내는 한 가지는 그림 5 다 — 「반복하면 수렴한다」 한 줄 대신 두 단계가 각각 SSE 를 늘리지 않는다는 근거와 «유한 번에 멈추지만 최악은 지수 번»을 함께 쓴다.
9오해와 사실
- 오해k-평균이 수렴하면 SSE 가 가장 작은 군집을 찾은 것이다.사실수렴은 국소 최솟값이다 — 합성 데이터 10만 개 · k = 8 에서 초기화를 한 번만 한 실행끼리 SSE 가 최대 1.61배 갈렸다.
- 오해k 를 늘리면 기존 군집이 조금씩 더 잘게 나뉠 뿐이다.사실이상치가 있으면 새 중심이 그 한 점에 가서 크기 1 인 군집이 생긴다(진단 표 셋째 줄).
- 오해미니배치 k-평균은 품질을 크게 잃는다.사실사례의 시드 0 에서 계산을 26분의 1로 줄이고 SSE 는 0.57% 커졌다 — 시드에 따라 손실 폭(0.09 ~ 20.1%)이 갈리므로 같은 시작 중심의 전체 실행과 한 번 견줘 본다.
10핵심 정리
| 구분 | 맡는 일 | 식 · 값 | 사례 값 | scikit-learn | 흔한 실수 |
|---|---|---|---|---|---|
| 표준화 | 단위 영향 제거 | (x − 평균) ÷ 표준편차 | 대기 분산 = 분출의 약 142배 | StandardScaler | 원 단위로 바로 군집 |
| k-평균++ | 출발점 고르기 | D² 비례 확률 · O(log k) | 둘째 중심 확률 0.55% | init= | 초기화 1회로 끝냄 |
| 배정 · 갱신 | 반복 본체 | 가까운 중심 · 군집 평균 | 3회 · 바뀐 표본 2 → 1 → 0 | max_iter · tol | 수렴 = 최적으로 읽음 |
| SSE(관성) | 목적 · 비교 | Σ‖x − μ‖² | 102.68 → 79.58 | inertia_ | 다른 표현끼리 SSE 비교 |
| k 선택 | 군집 수 | Gap(k) ≥ Gap(k+1) − s | k = 2 · Gap 1.312 | (직접 계산) | SSE 만 보고 큰 k |
| 미니배치 | 큰 데이터 | 배치 b 로 중심 이동 | 계산 1/26 · SSE +0.57% | MiniBatchKMeans | 품질 확인 없이 대체 |
| 한계 | 모양 · 크기 · 이상치 | 둥근 같은 크기 가정 | ARI 0.85 · 0.06 | GaussianMixture 등 | 잘린 무리를 그대로 해석 |
11참고 문헌
- 먼저 볼 문헌
- ★ k-means++: The Advantages of Careful Seeding (Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms 1027-1035) — D² 가중 초기화 절차와 배정 · 갱신 두 단계가 SSE 를 늘리지 않는 이유를 볼 때
- ★ Estimating the Number of Clusters in a Data Set via the Gap Statistic (Journal of the Royal Statistical Society Series B 63(2) 411-423) — k 를 SSE 꺾임이 아니라 기준 분포와의 차로 고르는 규칙을 볼 때
- ★ Old Faithful Geyser Data (R datasets package 4.6.0 faithful) — 사례 데이터 272회 분출 · 두 변수의 단위와 출처를 확인할 때
- ★ scikit-learn 1.9.1 API sklearn.cluster.KMeans — init · n_init · max_iter · tol 기본값과 inertia_ 속성을 볼 때
- 본문 근거
- Web-Scale K-Means Clustering (Proceedings of the 19th International Conference on World Wide Web 1177-1178) — ACM · 2010-04 ·
doi.org/10.1145/1772690.1772862· 확인 2026-11-12 - Least Squares Quantization in PCM (IEEE Transactions on Information Theory 28(2) 129-137) — IEEE · 1982-03 ·
doi.org/10.1109/TIT.1982.1056489· 확인 2026-11-12 - Some Methods for Classification and Analysis of Multivariate Observations (Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability 1 281-297) — University of California Press · 1967 ·
projecteuclid.org/euclid.bsmsp/1200512992· 확인 2026-11-12 - k-means Requires Exponentially Many Iterations Even in the Plane (Discrete & Computational Geometry 45(4) 596-616) — Springer · 2011 ·
cseweb.ucsd.edu/~avattani/papers/kmeans.pdf· 확인 2026-11-12 - scikit-learn 1.9.1 API sklearn.cluster.MiniBatchKMeans — scikit-learn developers · 2026-11 ·
scikit-learn.org/stable/modules/generated/sklearn.cluster.MiniBatchKMeans.html· 확인 2026-11-12 - A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise (KDD-96 226-231) — AAAI · 1996-08 ·
cdn.aaai.org/KDD/1996/KDD96-037.pdf· 확인 2026-11-12 - Maximum Likelihood from Incomplete Data via the EM Algorithm (Journal of the Royal Statistical Society Series B 39(1) 1-38) — Wiley · 1977 ·
doi.org/10.1111/j.2517-6161.1977.tb01600.x· 확인 2026-11-12 - Finding Groups in Data: An Introduction to Cluster Analysis (Chapter 2 Partitioning Around Medoids) — Wiley · 1990-03 ·
doi.org/10.1002/9780470316801· 확인 2026-11-12 - A Look at Some Data on the Old Faithful Geyser (Applied Statistics 39(3) 357-365) — Royal Statistical Society · 1990 ·
doi.org/10.2307/2347385· 확인 2026-11-12 - Comparing Partitions (Journal of Classification 2 193-218) — Springer · 1985-12 ·
doi.org/10.1007/BF01908075· 확인 2026-11-12