# K-means clustering (K-평균 클러스터링) K-means clustering은 비지도 학습에서 널리 사용되는 군집화 알고리즘 중 하나로, 데이터 포인트를 K개의 군집으로 분할하는 것을 목표로 한다. 각 군집은 그 군집에 속한 데이터의 산술적 중심인 중심점(centroid)에 가장 가까운 포인트들로 구성된다. 이 알고리즘은 간단한 아이디어와 계산 효율성으로 인해 이미지 압축, 색상 양자화, 문서 클러스터링, 고객 세분화 등 다양한 응용 분야에서 활용된다. 개요 - 목표: 데이터 포인트를 K개의 군집으로 나누고, 각 포인트를 가장 가까운 군집의 중심점으로 할당한다. - 핵심 아이디어: 각 포인트의 제곱거리 합(SSE, sum of squared errors)을 최소화하는 방식으로 군집 중심점을 반복해서 갱신한다. - 특징: 수렴성 보장(반복적 업데이트 후 SSE가 더 이상 감소하지 않으면 종료), 구현이 비교적 간단하다. - 한계: 군집의 모양이 구형에 가깝다고 가정하며, 초기화와 K의 선택에 민감하고 이상치에 취약할 수 있다. 수학적 배경 - 데이터: n개의 샘플 x_i ∈ R^d - 군집 수: K (1 ≤ K ≤ n) - 군집 할당: c(i) ∈ {1, ..., K} - 군집 중심점: μ_j ∈ R^d (j = 1,...,K) - 목표 함수(합 제곱 오차, SSE): J = sum_{i=1}^n ||x_i - μ_{c(i)}||^2 - 최적화 문제: c(i)와 μ_j를 번갈아가며 최적화해 J를 최소화한다. - 할당 단계: 각 포인트 x_i에 대해 가장 가까운 군집 중심 μ_j를 선택한다. - 업데이트 단계: 각 군집 j에 속한 모든 포인트의 평균을 새로운 중심점 μ_j로 설정한다. - 관찰: 최적의 μ_j는 해당 군집에 속한 포인트들의 산술 평균이다. 알고리즘 - 초기화: K개의 중심점 μ_1^0, μ_2^0, ..., μ_K^0를 초기화한다. (랜덤 초기화 또는 K-means++를 이용) - 반복: 1) 할당 단계: 각 데이터 포인트 x_i에 대해 c(i) = argmin_j ||x_i - μ_j||^2 로 가장 가까운 중심점에 할당한다. 2) 업데이트 단계: 각 군집 j에 대해 μ_j = (1 / n_j) sum_{i: c(i)=j} x_i 를 계산하여 새로운 중심점으로 설정한다. 여기서 n_j은 군집 j에 속한 포인트의 수이다. 3) 수렴 여부 점검: 할당 또는 중심점이 더 이상 변화하지 않으면 종료. 또는 SSE의 변화가 작은 임계값 이하가 될 때까지 반복한다. - 복수 반복 수행 시: 수렴 경향은 로컬 최적해에 의존하므로, 여러 번 다른 초기화를 시도하여 나은 해를 찾는 것이 일반적이다. 초기화 방법 - 랜덤 초기화(Random initialization): 데이터 중 K개 포인트를 무작위로 선택하여 중심점으로 삼는다. - K-means++: 가장 널리 추천되는 방법으로, 초기 중심점을 데이터 분포를 고려해 점진적으로 선택한다. 처음 하나를 임의로 선택하고, 그다음 중심점을 선택할 때 현재 중심점들과의 거리에 비례하는 확률로 선택하여 SSE를 줄이는 경향을 만든다. - 기타 방법: 선형 변환 후 K-means 수행, 성능 향상을 위한 샘플링 기반 초기화 등. 거리 측정 - 주로 Euclidean distance(유클리드 거리)를 사용한다. - 데이터의 특성에 따라 다른 거리 측정 방법이 유용할 수 있다. - 코사인 거리: 방향성에 민감한 벡터 데이터에서 각도 기반 거리로 활용하는 변형(예: 스페어링 데이터의 코사인 유사도 기반 K-means). - Manhattan 거리, M-estimator 거리 등: 이상치에 대한 견고성을 높이기 위한 변형. - 거리 측정 선택은 데이터의 스케일링 및 특성에 큰 영향을 준다. 파라미터 - K: 군집의 수. 데이터의 구조에 따라 적절한 K를 선택해야 한다. - 선택 방법: 엘보 방법(Elbow method), 실루엣 점수(Silhouette score), Gap statistic 등. - 거리 함수: 주로 Euclidean 거리이나 데이터 특성에 따라 변경 가능. - 초기화 방식: 위의 초기화 방법 참고. - 수렴 임계값과 최대 반복 수: SSE의 변화가 임계값 이하가 되거나 최대 반복 횟수에 도달하면 종료. - 정규화/표준화 여부: 각 특성의 스케일 차이가 크면 표준화가 필요하다. 변형 및 확장 - Mini-batch K-means: 대용량 데이터에서 배치 단위로 업데이트하여 계산 비용을 줄이는 버전. 근사적으로 빠르게 수렴하며 메모리 사용을 줄인다. - K-medians, K-medoids: 이상치에 덜 민감한 로버스트 버전으로, 중심점 대신 중앙값(median)이나 중심점 대신 중심 데이터 포인트(medoid)를 사용한다. - Soft K-means / Fuzzy C-means: 각 포인트가 각 군집에 대해 소속도(확률적 가중치)를 갖는 소프트 클러스터링 방식. 완전히 경계가 선명한 하드 클러스터링과 다르다. - Kernel K-means: 커널 트릭을 사용해 비선형적으로 분리 가능한 데이터를 저차원의 공간에서 선형적으로 분리 가능하도록 확장한다. - Spectral K-means: 스펙트럴 클러스터링과 결합하여 복잡한 구조의 데이터에 적용하는 변형. - Sphere K-means: 데이터가 이미 방향성 중심으로 정규화되어 있을 때 코사인 거리 기반으로 사용하는 변형. - 온라인/스트리밍 K-means: 데이터가 연속 도착하는 환경에서 점진적으로 업데이트하는 버전. 데이터 전처리 - 표준화(Standardization) 또는 정규화(Normalization): 각 특성의 스케일 차이가 클 경우 SSE를 왜곡하므로 전처리가 필수인 경우가 많다. - 차원 축소: PCA 등으로 차원을 축소해 연산 비용과 노이즈를 줄이고, 때로는 성능을 개선하기도 한다. - 이상치 처리: 이상치가 군집 중심과 배치를 왜곡시키므로 사전에 탐지 및 처리하는 것이 좋다. - 범주형 데이터 처리: 원-핫 인코딩 등으로 수치화한 후 K-means를 적용하거나, 특성에 맞는 거리 척도/변형을 적용한다. 모델 평가 - 내재적 평가(Intrinsic): SSE(또는 inertia)로 군집 내 분산의 합을 측정한다. - 실루엣 점수(Silhouette score): 각 포인트에 대해 두 가지 거리의 조화로 전체 클러스터링 품질을 평가한다. - Davies-Bouldin index: 군집 간의 평균 유사도 지표의 평균을 낮을수록 좋다. - 외재적 평가(External): 라벨이 주어진 경우 Adjusted Rand Index(ARI), NMI 등으로 평가 가능하나 비지도 학습의 기본 목표는 데이터 자체의 구조를 발견하는 것이다. - 시각화: 2차원 또는 3차원으로 축소한 후 클러스터 구분을 시각적으로 확인한다. 시간 복잡도 및 성능 고려 - 일반적인 구현에서의 시간 복잡도: O(n k d t) (n: 데이터 포인트 수, k: 군집 수, d: 차원 수, t: 반복 횟수) - 공간 복잡도: O(n d) 저장 공간과 O(k d) 중심점 저장 공간 - 대용량 데이터: Mini-batch K-means나 스트리밍 버전이 실용적이다. 한계점 - 초기화 의존성: 잘못된 초기화는 로컬 최적해에 수렴할 수 있다. - 군집 모양 제약: 구형(球状) 군집에 대해 잘 작동하지만 비구형 군집에는 잘 맞지 않는 경우가 많다. - 스케일링/이상치 민감: 데이터 스케일과 이상치가 성능에 큰 영향을 준다. - K의 선택 문제: 적절한 K를 미리 알기 어렵고, K에 따라 결과가 크게 달라질 수 있다. 적용 분야 - 색상 양자화 및 이미지 압축: 이미지의 색상 공간을 K개의 대표 색상으로 양자화. - 고객 세그먼테이션: 마케팅 데이터에서 유사한 특성을 가진 고객 군집화. - 문서 클러스터링: 텍스트 데이터의 코사인 유사도 기반 전처리 후 클러스터링. - 데이터 압축 및 패턴 발견: 대규모 데이터의 구조를 작은 그룹으로 축약. 구현 팁 - 데이터 전처리와 스케일링에 주의하라. - 초기화를 여러 차례 시도해 로컬 최적해의 영향을 줄이자. - 대용량 데이터는 Mini-batch K-means를 고려하라. - 이상치와 잡음에 대비해 로버스트 버전(K-medians, K-medoids)도 검토하라. - 차원 축소와의 조합으로 속도와 해석성을 개선하자. 사례 연구(요약) - 색상 양자화: 이미지의 대표 색상 16~256색으로 축소하면서도 시각적 품질을 유지한다. - 고객 세분화: 구매 패턴과 특성에 따라 서로 다른 마케팅 전략을 설계하기 위한 그룹을 도출한다. - 문서 군집화: 대규모 코퍼스에서 토픽 간의 군집 구조를 파악하고, 후속 토픽 모델링의 전처리로 활용한다. --- 관련 문서: [[K-means++ 알고리즘]], [[클러스터링 평가 방법]]