K-평균 군집화 (K-Means Clustering)

#개념

K-평균 군집화(K-Means Clustering)는 레이블이 없는 데이터를 미리 정한 개수 $k$의 군집으로 분할하는 비지도 학습(Unsupervised Learning) 기반의 군집화(Clustering) 알고리즘이다. 각 군집은 소속 데이터의 평균 벡터인 중심(centroid)으로 대표되며, 모든 데이터는 자신과 가장 가까운 중심의 군집에 속한다. 알고리즘의 목표는 각 데이터 $x_i$와 소속 군집 $C_j$의 중심 $\mu_j$ 사이의 유클리드 거리 제곱을 모두 더한 군집 내 제곱합(Within-Cluster Sum of Squares, WCSS), 즉 $J = \sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$을 최소화하는 것으로, 이 값은 관성(inertia) 또는 왜곡(distortion)이라고도 부른다. 이 목적 함수를 전역적으로 최소화하는 문제는 NP-난해(NP-hard)이므로, 실제로는 1957년 Stuart Lloyd가 펄스 부호 변조(PCM)의 최적 양자화 문제로 고안하고 1982년에 공식 출판한 Lloyd 알고리즘으로 근사해를 구한다. Lloyd 알고리즘은 (1) $k$개의 초기 중심을 선택하고, (2) 각 데이터를 가장 가까운 중심에 할당하는 할당 단계와, (3) 각 군집에 속한 데이터의 평균으로 중심을 다시 계산하는 갱신 단계를 할당이 더 이상 바뀌지 않거나 중심의 이동량이 임계값 아래로 떨어질 때까지 반복한다. 할당 단계는 중심이 고정된 상태에서 $J$를 최소화하고, 갱신 단계는 할당이 고정된 상태에서 $J$를 최소화하므로 $J$는 반복마다 단조 감소하며 유한 번의 반복 안에 수렴하지만, 도달한 해는 초기 중심에 따라 달라지는 지역 최적해(local optimum)일 뿐 전역 최적해라는 보장은 없다. 한 번의 반복 비용은 데이터 수 $n$, 군집 수 $k$, 차원 $d$에 대해 $O(nkd)$로 데이터 수에 선형이므로 대규모 데이터에도 적용하기 쉽다.

초기 중심 선택은 결과의 품질을 크게 좌우한다. 데이터 중 $k$개를 무작위로 고르는 단순한 방법은 여러 중심이 한 군집 안에 몰리거나 이상치가 중심으로 뽑혀 나쁜 지역 최적해에 갇히기 쉽다. Arthur와 Vassilvitskii(2007)가 제안한 k-means++ 초기화는 첫 중심을 무작위로 고른 뒤, 이후의 중심은 이미 선택된 가장 가까운 중심까지의 거리 제곱 $D(x)^2$에 비례하는 확률로 뽑아 서로 멀리 떨어진 초기 중심을 얻는다. 이 방법은 기대값 기준으로 최적해의 $O(\log k)$배 이내의 목적 함수 값을 보장하며, 이후의 Lloyd 반복 횟수도 줄여 주기 때문에 scikit-learn을 비롯한 대부분의 구현에서 기본값으로 채택되었다. 이와 별개로 서로 다른 초기값으로 알고리즘을 여러 번 실행한 뒤 WCSS가 가장 작은 결과를 택하는 다중 초기화(scikit-learn의 n_init)도 널리 쓰인다. 군집 수 $k$는 알고리즘이 스스로 결정하지 못하는 하이퍼파라미터(Hyperparameter)이므로 별도의 선택 기준이 필요하다. 엘보 방법(elbow method)은 $k$를 늘려가며 WCSS를 그렸을 때 감소 폭이 급격히 완만해지는 지점을 선택하는 휴리스틱인데, WCSS는 $k$가 커질수록 항상 감소하므로 꺾이는 지점이 뚜렷하지 않은 경우가 많다. 실루엣 계수(silhouette coefficient)는 각 데이터에 대해 같은 군집 내 평균 거리 $a$와 가장 가까운 다른 군집까지의 평균 거리 $b$로 $s = \frac{b - a}{\max(a, b)}$를 계산하여 $-1$에서 $1$ 사이의 값으로 군집의 응집도와 분리도를 함께 평가하며, 평균 실루엣 계수가 가장 큰 $k$를 선택한다. 그 밖에 갭 통계량(gap statistic), Calinski-Harabasz 지수, Davies-Bouldin 지수 등이 활용되고, 최종적으로는 도메인 지식과 군집의 해석 가능성을 함께 고려해 결정하는 것이 일반적이다.

K-평균은 단순하고 빠르지만 명확한 가정과 한계를 가진다. 유클리드 거리와 평균을 사용하므로 각 군집이 비슷한 크기와 밀도를 가진 구형(spherical) 분포라고 암묵적으로 가정하며, 길쭉하거나 초승달 모양, 서로 다른 크기의 군집은 올바르게 분리하지 못한다. 이는 K-평균이 등방성 공분산을 가진 가우시안 혼합 모델의 하드 할당(hard assignment) 특수 사례라는 점에서 이해할 수 있다. 또한 평균은 극단값에 민감하므로 소수의 이상치(outlier)가 중심을 끌어당기거나 이상치만으로 이루어진 군집이 생길 수 있어, 사전에 이상치를 제거하거나 강건한 변형을 사용하는 것이 좋다. 거리 기반 알고리즘이므로 특징의 스케일링(feature scaling)도 필수적이다. 예를 들어 연 소득(수천만 원 단위)과 나이(수십 단위)를 그대로 사용하면 거리가 소득에 의해 지배되므로, 표준화(standardization)나 최소-최대 정규화를 먼저 적용해야 한다. 차원이 매우 높으면 거리의 변별력이 떨어지는 차원의 저주가 발생하므로 주성분 분석(Principal Component Analysis, PCA)과 같은 차원 축소(Dimensionality Reduction)를 선행하기도 한다. 범주형 변수에는 평균이 정의되지 않아 최빈값을 사용하는 K-modes나 혼합형 데이터를 위한 K-prototypes 같은 변형이 필요하다.

수백만 개 이상의 데이터에서는 매 반복마다 전체 데이터를 순회하는 비용이 부담이 되므로, Sculley(2010)가 제안한 미니배치 K-평균(Mini-Batch K-Means)이 사용된다. 이 방법은 매 반복마다 무작위로 추출한 소규모 미니배치만으로 데이터를 할당하고, 각 중심을 지금까지 그 중심에 할당된 데이터 수의 역수를 학습률로 하는 이동 평균 방식으로 점진적으로 갱신한다. 동일한 목적 함수를 최적화하면서 계산 시간을 크게 줄이며, 결과 품질은 일반적으로 표준 알고리즘보다 약간 낮은 수준에 그친다. 이러한 확장성 덕분에 K-평균은 다른 기법의 구성 요소로도 널리 쓰이는데, 벡터 검색 라이브러리 Faiss의 IVF 색인은 K-평균으로 벡터 공간을 분할하고, 곱 양자화(Product Quantization)의 코드북 학습이나 이미지의 색상 양자화, 시각 단어 사전(bag of visual words) 구축에도 K-평균이 활용된다.

K-평균은 다른 군집화 알고리즘과 비교하여 선택된다. K-medoids(PAM)는 군집의 대표를 평균이 아닌 실제 데이터 포인트(medoid)로 정하고 임의의 거리 척도를 사용할 수 있어 이상치에 더 강건하지만, 계산 비용이 $O(k(n-k)^2)$ 수준으로 훨씬 크다. 가우시안 혼합 모델(Gaussian Mixture Model, GMM)은 EM 알고리즘으로 각 군집의 평균과 공분산을 함께 추정하므로 타원형 군집을 표현할 수 있고, 각 데이터가 군집에 속할 확률을 제공하는 소프트 할당(soft assignment)이 가능하지만 추정할 매개변수가 많아 데이터가 적을 때 불안정하다. DBSCAN은 밀도가 높은 영역을 군집으로 정의하기 때문에 군집 수를 미리 지정할 필요가 없고 임의의 모양의 군집을 찾으며 저밀도 지점을 잡음으로 분류하지만, 밀도가 서로 다른 군집이 섞여 있으면 어려움을 겪고 반경과 최소 이웃 수라는 매개변수에 민감하다. 계층적 군집화는 덴드로그램으로 여러 수준의 군집 구조를 한 번에 보여 주지만 $O(n^2)$ 이상의 메모리와 시간이 필요하다. 결론적으로 K-평균은 군집이 대략 구형이고 크기가 비슷하며 데이터가 많을 때 가장 먼저 시도할 만한 기준선(baseline)이며, 가정이 맞지 않는 데이터에서는 GMM이나 DBSCAN 같은 대안을 고려해야 한다.

#관련 용어

군집화

레이블 없이 유사한 데이터끼리 그룹으로 묶는 비지도 학습 기법

중심

군집에 속한 데이터의 평균 벡터로 군집을 대표하는 점

군집 내 제곱합(WCSS)

각 데이터와 소속 군집 중심 사이의 거리 제곱을 모두 더한 K-평균의 목적 함수

k-means++

이미 선택된 중심에서 먼 데이터가 다음 중심으로 뽑힐 확률을 높이는 초기 중심 선택 방법

실루엣 계수

군집 내 응집도와 군집 간 분리도를 함께 반영하여 군집 품질을 $-1$에서 $1$ 사이로 평가하는 지표

하이퍼파라미터

군집 수 $k$처럼 학습 전에 사람이 지정해야 하는 설정값

#직무 연관도

Data Analyst높음

고객 세분화와 상품 그룹화 같은 실무 분석에서 가장 자주 사용되는 군집화 도구로 결과 해석 능력이 요구된다

Data Scientist높음

탐색적 분석, 특징 구성, 벡터 양자화와 대규모 데이터 전처리에 폭넓게 활용되는 기본 군집화 알고리즘

Data Engineer보통

벡터 검색 색인, 이미지 압축, 로그·트래픽 패턴 분류 등 시스템 구성 요소로 구현하고 확장성을 관리해야 한다

#사용 사례

전자상거래금융통신인터넷 서비스제조의료

개요

K-평균 군집화는 고객 세분화, 상품·문서 그룹화, 이미지 색상 양자화와 압축, 벡터 검색을 위한 공간 분할, 이상 거래나 장비 이상 탐지를 위한 정상 패턴 정의 등 레이블이 없는 데이터에서 구조를 발견하는 다양한 작업에 활용된다.

사례

전자상거래 기업이 고객의 최근 구매일, 구매 빈도, 구매 금액(RFM)을 표준화한 뒤 K-평균으로 군집화하면, 자주 구매하는 우량 고객, 최근 유입된 신규 고객, 이탈 위험이 있는 휴면 고객 같은 세그먼트를 얻어 세그먼트별로 다른 프로모션과 재구매 유도 메시지를 설계할 수 있다.