개념
"비슷한 것들끼리 묶기"의 기본 알고리즘. 1957년 벨 연구소에서 시작된 단순한 아이디어가 모든 데이터 과학의 첫 도구가 되었다.
한 호흡으로 이해하기
"비슷한 데이터를 같은 그룹으로 묶기"의 가장 단순한 방법. k개 중심을 임의로 놓고 → 가장 가까운 중심에 데이터 할당 → 중심 재계산 → 반복. 고객 세그먼트 분석, 이미지 색 압축, 유전자 발현 분류, 추천 시스템의 첫 도구.
한눈에 보기
반복 | 단계 | 결과 |
|---|---|---|
초기화 | k개의 중심을 무작위 선택 | 예: μ₁=(2,3), μ₂=(8,7) |
1 | 각 점을 가장 가까운 중심에 할당 | 점 (3,3) → 군집 1 |
1 | 중심을 재계산 (군집 평균) | 새 μ₁, μ₂ |
2 | 재할당 → 재계산 | 점 몇 개가 군집을 바꿈 |
… | 변화 없을 때까지 반복 | 수렴 (지역 최솟값) |
수렴 | 최종 군집 분할 | 응용: 고객 세그먼트, 이미지 색 압축, 유전자 군집 |
K-means는 지역 최솟값에 빠질 수 있어, 보통 여러 번 다른 초기화로 돌려 가장 좋은 결과를 고른다.
핵심 식
각 군집 내 분산의 합 최소화
핵심 순간
AD 1957
로이드 — 벨 연구소 내부 보고서
스튜어트 로이드가 펄스 코드 변조 양자화를 위해 알고리즘 발명. 25년간 발표되지 않음.
AD 1967
맥퀸 — K-means라는 이름
제임스 맥퀸이 알고리즘을 일반화하고 k-means라는 이름 부여.
AD 2007
K-means++ — 더 나은 초기화
아서·바실비츠키가 초기 중심점을 똑똑하게 선택하는 K-means++ 발표. 사실상의 표준이 됨.
오늘날의 응용
고객 세그멘테이션, 이미지 압축, 유전체 분석, 추천 시스템, 이상 탐지, AI 학습 데이터 준비.
MathVoyage 너머로
불러오는 중…