중심점을 옮겨가며 군집을 찾는 K-Means 클러스터링

정답 레이블이 붙어 있지 않은 데이터에도 구조는 있다. 어떤 고객이 어떤 그룹인지 아무도 표시해 주지 않았지만, 구매 이력이 비슷한 사람끼리는 실제로 모여 있다. 이 모임을 레이블 없이 찾아내는 작업이 클러스터링이다.

“비슷하다”의 기준은 대개 거리다. 가까우면 같은 그룹, 멀면 다른 그룹. 이 기준을 가장 곧이곧대로 구현한 알고리즘이 K-Means다. 클러스터마다 대표점(중심점, centroid)을 하나씩 두고, 각 데이터를 가장 가까운 중심점에 붙인 뒤, 중심점을 자기 식구들의 평균 자리로 옮긴다. 이 두 동작을 번갈아 반복하는 것이 전부다.

무엇을 최소화하는가

K-Means가 줄이려는 값은 WCSS(Within-Cluster Sum of Squares)다. sklearn은 이 값을 inertia_ 속성으로 내놓는다.

$\text{WCSS} = \sum_{k=1}^{K} \sum_{x \in C_k} \lVert x - \mu_k \rVert^2$

$C_k$는 $k$번째 클러스터이고 $\mu_k$는 그 중심점이다. 각 점이 자기 중심점에서 얼마나 떨어져 있는지를 제곱해 모두 더한 값이니, 작을수록 클러스터 내부가 촘촘하다.

이 함수에는 미지수가 두 종류 들어 있다. 중심점의 위치와 각 점의 소속이다. 둘을 동시에 최적으로 푸는 문제는 NP-hard라서 정면으로 풀지 않는다. 대신 한쪽을 고정하면 나머지가 쉽게 풀린다는 성질을 쓴다. 소속을 고정하면 WCSS를 최소로 만드는 중심점은 그 클러스터의 평균이고,

$\mu_k = \frac{1}{|C_k|} \sum_{x \in C_k} x$

중심점을 고정하면 각 점의 최적 소속은 가장 가까운 중심점이다. 두 단계 어느 쪽도 WCSS를 늘리지 않으므로 번갈아 돌리면 값은 단조 감소하고, 가능한 소속 조합이 유한하니 언젠가 멈춘다.

멈춘 자리가 전역 최적이라는 보장은 없다. 초기 중심점을 어디에 두었느냐에 따라 서로 다른 지역 최적에 갇힌다. K-Means에서 초기화가 하이퍼파라미터 취급을 받는 이유가 여기에 있다.

할당과 이동을 번갈아 반복한다

첫 칸은 초기 중심점 세 개를 놓은 상태다. 데이터 점 중에서 K개를 그냥 뽑는 방식이라 오른쪽 두 개가 나란히 뽑혔다. 두 번째 칸에서 모든 점이 자기와 가장 가까운 중심점 쪽에 붙는다. 자기 중심점을 얻지 못한 가운데 무리는 통째로 주황색 중심점에 딸려 가고, 오른쪽 무리는 검은색을 받는다.

세 번째 칸에서 중심점이 소속 점들의 평균 자리로 옮겨간다. 주황색 중심점은 가운데 무리를 따라 왼쪽 위로 크게 이동한다. 중심점이 움직였으니 “가장 가까운 중심점”도 달라진다. 네 번째 칸에서 다시 할당하면 두 무리 사이에 걸쳐 있던 점 하나가 검은색으로 넘어간다. 한 번 더 돌려도 바뀌는 점이 없으면 수렴이다.

sklearn의 KMeans는 소속이 하나도 바뀌지 않으면 그 자리에서 멈추고, 그 전이라도 중심점 이동량의 제곱합이 tol 아래면 끊는다. tol=1e-4는 절대 거리가 아니라 피처 분산의 평균에 곱해지는 상대값이라, 데이터의 스케일이 달라져도 같은 기준이 유지된다. 둘 중 어느 쪽에도 걸리지 않으면 max_iter=300회가 상한이고, 실제로 몇 번 돌았는지는 n_iter_로 확인한다.

초기화가 결과를 가른다

랜덤 초기화의 위험은 위 그림 첫 칸에 이미 들어 있다. 오른쪽 두 중심점이 서로 붙어서 뽑히는 바람에 가운데 무리는 자기 중심점을 얻지 못했다. 이번에는 첫 이동에서 주황색 중심점이 가운데로 끌려오면서 회복했지만, 세 덩어리가 더 멀리 떨어져 있었다면 한 덩어리를 두 중심점이 나눠 갖고 다른 덩어리는 통째로 남의 클러스터에 묻힌 채로 굳는다. 그 자리에서 수렴해도 WCSS는 나쁜 값에 머문다.

K-Means++는 2007년 Arthur와 Vassilvitskii가 제안한 초기화로, 중심점끼리 서로 멀리 떨어지도록 유도한다. 첫 중심점만 랜덤으로 뽑고, 그다음부터는 이미 뽑힌 중심점까지의 최단 거리 $D(x)$의 제곱에 비례하는 확률로 뽑는다.

$P(x) = \frac{D(x)^2}{\sum_{x'} D(x')^2}$

기존 중심점에서 먼 점일수록 뽑힐 확률이 커지니, 아직 중심점을 못 얻은 덩어리에서 다음 중심점이 나올 가능성이 높아진다. 이 초기화만으로 기대 WCSS가 최적값의 $O(\log K)$ 배 안에 든다는 보장이 붙는다. 순수 랜덤 초기화에는 그런 보장이 없다.

그래도 한 번의 실행으로 지역 최적을 완전히 피하지는 못해서, 서로 다른 초기화로 여러 번 돌린 뒤 WCSS가 가장 낮은 결과를 고르는 방법을 함께 쓴다. n_init이 그 횟수다.

K를 몇 개로 둘 것인가

K-Means는 K를 입력으로 받는다. 덩어리가 몇 개인지 모르는 상태에서 그 숫자를 먼저 정해야 한다는 뜻이다. 흔히 쓰는 기준은 둘이다.

엘보우는 K를 늘리면 WCSS가 반드시 줄어든다는 성질에서 출발한다. K가 데이터 개수와 같아지면 WCSS는 0이다. 그러니 값 자체가 아니라 줄어드는 속도를 본다. 급하게 떨어지다 완만해지는 지점이 있으면 거기를 고른다.

문제는 그 지점이 보이지 않을 때가 많다는 것이다.

아래쪽 곡선은 K를 늘릴수록 WCSS가 고르게 줄어들 뿐이라 어디를 골라도 근거가 약하다. 클러스터끼리 겹쳐 있거나 밀도가 이어져 있으면 이런 모양이 나오고, 실제 데이터에서 오히려 이쪽이 더 흔하다. 엘보우 하나만 보고 K를 정하면 안 되는 이유다.

실루엣은 점 단위로 두 값을 잰다. $a(i)$는 같은 클러스터의 다른 점들과의 평균 거리(응집도), $b(i)$는 가장 가까운 다른 클러스터의 점들과의 평균 거리(분리도)다.

$s(i) = \frac{b(i) - a(i)}{\max\left(a(i),\, b(i)\right)}$

값은 $-1$부터 $1$까지다. 1에 가까우면 자기 클러스터에 잘 붙어 있고, 0 근처면 경계에 걸쳐 있으며, 음수면 다른 클러스터가 더 가깝다는 뜻이니 잘못 할당된 점이다. 전체 평균이 실루엣 점수이고, K를 바꿔가며 이 값이 가장 높은 K를 고른다.

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

for k in range(2, 11):
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    labels = km.fit_predict(X_scaled)
    print(k, round(km.inertia_, 1), round(silhouette_score(X_scaled, labels), 3))

평균값만 보면 놓치는 것이 있다. silhouette_samples로 점마다의 값을 꺼내 클러스터별로 나눠 보면, 평균은 높은데 특정 클러스터 하나만 값이 낮거나 음수 구간이 넓은 경우가 드러난다. 그 클러스터를 더 쪼개는 쪽이 나은 상황이다. 엘보우와 실루엣이 다른 K를 가리키는 일도 흔한데, 그럴 때는 두 K로 각각 돌려 보고 클러스터의 내용이 해석되는 쪽을 고르는 편이 낫다.

K-Means가 틀리는 자리

첫 줄이 나머지를 상당 부분 설명한다. K-Means가 그릴 수 있는 경계는 중심점 두 개를 잇는 선분의 수직이등분선뿐이다. 결과적으로 공간은 중심점들의 보로노이 다이어그램으로 쪼개지고, 각 조각은 직선으로 둘러싸인 볼록한 영역이 된다. 이 조각들로 표현할 수 없는 모양이면 K를 아무리 잘 골라도 답이 나오지 않는다.

마지막 줄은 선택이 아니라 필수다. 연 소득(수천만 단위)과 월 방문 횟수(한 자릿수)를 그대로 넣으면 거리는 소득 차이만 반영한다. StandardScaler를 앞에 붙이는 것이 기본이다.

데이터가 커지면

반복마다 모든 점과 모든 중심점의 거리를 재는 비용은 $O(NKd)$다. N이 수십만을 넘어가면 이 계산이 부담스러워진다. MiniBatchKMeans는 반복마다 전체가 아니라 무작위로 뽑은 배치 $b$개만 써서 중심점을 갱신하고, 반복당 비용을 $O(bKd)$로 낮춘다. WCSS는 조금 나빠지지만 속도 차이가 크다.

from sklearn.cluster import MiniBatchKMeans

mbkm = MiniBatchKMeans(n_clusters=5, batch_size=1024, n_init=3, random_state=42)
mbkm.fit(X_scaled)

MiniBatchKMeans의 n_init 기본값도 'auto'이고, k-means++ 초기화에서는 역시 1회다. 여기서는 3으로 올려 잡았다.

고객 세분화라는 대표 사례

K-Means가 실무에서 가장 자주 불려 나오는 자리는 고객 세분화다. 최근성(Recency), 빈도(Frequency), 금액(Monetary) 세 축으로 고객을 묶는 RFM 분석이 대표적이다.

import pandas as pd
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler

X_scaled = StandardScaler().fit_transform(df[['recency', 'frequency', 'monetary']])

km = KMeans(n_clusters=3, n_init=10, random_state=42)
df['cluster'] = km.fit_predict(X_scaled)

print(df.groupby('cluster')[['recency', 'frequency', 'monetary']].mean().round(1))

축별 평균이 예를 들어 이렇게 나왔다고 하자.

         recency  frequency  monetary
cluster
0           10.2       29.8     498.3
1           49.5       10.1     201.2
2          119.8        3.2      52.1

세 줄만 봐도 성격이 갈린다. 0번은 최근에 자주 많이 사는 무리, 2번은 오래전에 몇 번 사고 끊긴 무리다. 여기서 짚어둘 점은 클러스터에 붙는 이름을 K-Means가 지어주지 않는다는 것이다. 알고리즘은 번호만 돌려주고, 각 번호가 무슨 뜻인지는 이렇게 축별 평균을 뜯어본 뒤 사람이 붙인다.

마치며

K-Means의 두 단계는 따로 떼어 놓고 보면 당연한 계산이다. 소속이 정해지면 최선의 중심점은 평균이고, 중심점이 정해지면 최선의 소속은 최근접이다. 이 둘을 번갈아 돌리는 것만으로 WCSS가 계속 줄어든다는 점이 알고리즘의 전부이자, 지역 최적을 벗어나지 못하는 이유이기도 하다.

그래서 K-Means를 쓸 때 실제로 손이 가는 곳은 알고리즘 바깥이다. 스케일링을 했는지, 초기화를 몇 번 돌렸는지, K를 무슨 근거로 골랐는지가 결과를 좌우한다. 반대로 경계가 직선이라는 제약과 K를 미리 정해야 한다는 제약은 알고리즘의 정의에서 곧장 나오는 것이라 튜닝으로 풀리지 않는다.

다음 글에서는 같은 비지도 문제이지만 목표가 반대인 쪽, 나머지와 다른 점을 골라내는 이상 탐지를 다룬다.

함께 보면 좋은 글

• 피처 스케일링 : 거리 기반 알고리즘 앞에 스케일링이 반드시 와야 하는 이유
• DBSCAN과 GMM : 구형 가정과 K 사전 지정을 벗어나는 클러스터링
• KNN : 같은 거리 개념을 레이블이 있는 문제에 쓰는 경우
• 이상 탐지 : 어느 무리에도 맞지 않는 점을 찾아내는 문제

참고자료

• Arthur & Vassilvitskii, k-means++: The Advantages of Careful Seeding (SODA 2007)
• Rousseeuw, Silhouettes: a graphical aid to the interpretation and validation of cluster analysis (1987)
• scikit-learn, Clustering
• scikit-learn, KMeans
• scikit-learn, Selecting the number of clusters with silhouette analysis on KMeans clustering