k-평균 알고리즘(k-means algorithm)은 비지도 학습(unsupervised learning) 방법 중 하나인 군집 분석(cluster analysis) 알고리즘이다. 주어진 데이터를 k개의 군집(cluster)으로 묶는 것을 목표로 하며, 각 데이터 포인트가 가장 가까운 군집의 중심(centroid)에 할당되고, 각 군집의 중심은 해당 군집에 속한 모든 데이터 포인트의 평균으로 업데이트되는 과정을 반복하여 군집을 형성한다. 군집 내의 분산(variance)을 최소화하는 방식으로 동작한다.
세부 설명
k-평균 알고리즘은 일반적으로 다음과 같은 단계로 진행된다.
- 초기화: 데이터 포인트 중에서 무작위로 k개의 점을 선택하거나, 특정 휴리스틱 방법을 사용하여 초기 군집 중심(centroid)을 설정한다. (예: k-means++ 방법은 초기 중심점 선택을 개선하여 알고리즘의 안정성을 높인다.)
- 할당 단계 (Assignment Step): 각 데이터 포인트를 k개의 군집 중심 중 가장 가까운 군집 중심에 할당한다. 이때 유클리드 거리(Euclidean distance)와 같은 거리 측정 방식이 주로 사용된다. 수식적으로는 각 데이터 포인트 $x_i$에 대해 다음을 만족하는 군집 $S_j$에 할당한다. $S_j = {x_i : |x_i - \mu_j|^2 \le |x_i - \mu_l|^2 \quad \forall l=1,...,k}$ 여기서 $\mu_j$는 $j$번째 군집의 중심이다.
- 업데이트 단계 (Update Step): 각 군집에 할당된 모든 데이터 포인트들의 평균(mean)을 계산하여 새로운 군집 중심으로 업데이트한다. $\mu_j = \frac{1}{|S_j|} \sum_{x_i \in S_j} x_i$
- 반복 및 수렴: 할당 단계와 업데이트 단계를 군집 중심의 위치가 더 이상 변하지 않거나, 사전에 정의된 최대 반복 횟수에 도달할 때까지 반복한다.
이 알고리즘의 목표는 모든 군집 내의 제곱 오차 합(Sum of Squared Errors, SSE) 또는 군집 내 분산의 합을 최소화하는 것이다.
특징 및 장점
- 간단함: 알고리즘이 직관적이고 구현이 용이하다.
- 효율성: 대규모 데이터셋에서도 비교적 효율적으로 동작하며, 계산 복잡도가 낮은 편이다.
- 널리 사용: 다양한 분야에서 데이터 군집화의 표준적인 방법으로 널리 사용된다.
단점 및 한계
- k 값 사전 결정: 군집의 개수 k를 사용자가 사전에 결정해야 한다. 최적의 k 값을 찾는 것은 별도의 분석이 필요하다.
- 초기 중심점 의존성: 초기 군집 중심의 선택에 따라 결과가 크게 달라질 수 있으며, 지역 최적점(local optimum)에 수렴할 가능성이 있다. 이를 보완하기 위해 여러 번 알고리즘을 실행하거나 k-means++와 같은 개선된 초기화 방법을 사용하기도 한다.
- 군집 형태 제약: 구형(spherical)이고 크기가 비슷한 군집을 잘 찾아내지만, 복잡한 형태나 밀도가 다른 군집에는 적합하지 않을 수 있다.
- 이상치 민감성: 이상치(outlier)에 민감하게 반응하여 군집 중심의 위치를 왜곡할 수 있다.
응용 분야
k-평균 알고리즘은 다음과 같은 다양한 분야에서 활용된다.
- 이미지 처리: 이미지 분할(image segmentation) 및 압축
- 고객 세분화: 마케팅 전략 수립을 위한 고객 그룹 분류
- 문서 군집화: 문서들의 유사성을 기반으로 그룹화
- 추천 시스템: 사용자 그룹별 추천
- 이상 감지: 정상 범주를 벗어나는 데이터 탐지
변형 및 관련 알고리즘
- k-medoids: 군집 중심을 실제 데이터 포인트 중 하나로 선택하여 이상치에 덜 민감하다.
- k-means++: 초기 군집 중심을 보다 효과적으로 선택하여 지역 최적화 문제를 완화한다.
- MiniBatch K-means: 대규모 데이터셋에서 계산 효율성을 높이기 위해 데이터의 부분 집합(mini-batch)을 사용하여 군집 중심을 업데이트한다.
- 가우시안 혼합 모델 (Gaussian Mixture Models, GMM): 각 군집이 가우시안 분포를 따른다고 가정하며, 각 데이터 포인트가 여러 군집에 속할 확률을 고려한다 (소프트 군집).
- 계층적 군집 (Hierarchical Clustering): 군집들을 계층적인 트리 구조로 만들어 나가는 방식이다.
참고 항목
- 비지도 학습
- 군집 분석
- 기계 학습
- 데이터 마이닝
- 유클리드 거리