K-평균 군집화: 데이터를 K개 그룹으로 나누는 법

지난 글에서 그래디언트 부스팅이 잔차를 순차적으로 교정해 강력한 예측기를 만드는 원리를 봤다. 지금까지 다룬 알고리즘은 전부 지도 학습이었다 — 훈련 데이터에 정답 레이블이 붙어 있었고 모델은 그 레이블을 맞히도록 최적화됐다. 이번에는 정답이 없는 자리로 간다. 레이블 없이 데이터 스스로의 생김새만 보고 무리를 지어 내는 비지도 학습의 대표 알고리즘, K-평균 군집화다. 단순해서 널리 쓰이지만 단순한 만큼 세우는 가정도 뚜렷하고, 그 가정을 벗어난 데이터에서는 조용히 엉뚱한 답을 낸다. 이 글은 알고리즘이 무엇을 최소화하는지, 초기값이 왜 결과를 가르는지, K를 어떤 근거로 정하는지를 숫자로 따라간다.

군집화의 갈래

정답 없는 학습

지도 학습에서는 무엇이 잘한 것인지가 데이터에 적혀 있다. 정답이 y이고 예측이 ŷ이면 둘의 차이가 곧 성적표다. 군집화에는 그런 줄이 없다. 그래서 "잘했다"의 정의를 알고리즘이 스스로 세워야 하고, K-평균이 세우는 정의는 같은 무리에 든 점들이 그 무리의 평균에 가깝다는 것이다. 이 문장이 목적 함수가 되고 알고리즘 전체가 여기서 나온다.

정의가 알고리즘 안에 있다는 것은 평가도 그렇다는 뜻이다. 분류 모델의 정확도처럼 바깥에서 가져올 기준이 없으므로, 군집화 결과가 좋은지는 같은 목적 함수를 다시 재거나(관성) 다른 기준을 새로 들이거나(실루엣) 사람이 열어 보는 수밖에 없다. 이 사실은 뒤의 「K 고르기」에서 곧바로 문제가 된다.

여기서 낱말 넷의 관계를 정리해 두자. 데이터의 한 줄이 점이고, 점들을 묶은 덩어리가 군집이고, 군집 하나를 대표하는 좌표가 중심점이고, 점이 어느 군집에 속하는지를 적은 것이 할당이다. K-평균이 되풀이하는 일은 할당을 고쳐 중심점을 옮기고, 옮긴 중심점으로 할당을 다시 고치는 것 둘뿐이다. 아래 모든 이야기가 이 둘 위에 선다.

분할 · 계층 · 밀도

군집화 알고리즘은 무리를 만드는 방식으로 세 갈래다. 분할은 데이터를 미리 정한 개수의 조각으로 한 번에 나눈다. K-평균이 여기 속한다. 계층은 가장 가까운 둘을 묶는 일을 되풀이해 나무 모양의 구조를 만들고, 나무를 어느 높이에서 자르느냐로 군집 수가 정해진다. 밀도는 점이 빽빽한 구역을 군집으로 보고 성긴 자리를 경계로 삼는다. DBSCAN이 대표다.

셋의 차이는 취향이 아니라 군집이 무엇이냐에 대한 답의 차이다. 분할은 "중심에 가까운 것들", 계층은 "서로 가까운 것들", 밀도는 "붙어 있는 것들"을 한 무리로 본다. 초승달 두 개가 맞물린 데이터에서 K-평균이 실패하고 DBSCAN이 성공하는 것은 성능 차이가 아니라 정의 차이다.

K-평균의 가정 셋

K-평균을 쓰기 전에 확인할 가정이 셋이다. 첫째, 군집의 모양이 대체로 구형이다 — 중심에서 모든 방향으로 비슷하게 퍼져 있다고 본다. 둘째, 군집의 크기가 크게 다르지 않다 — 거리만 보고 나누므로 큰 군집이 작은 군집을 삼키기 쉽다. 셋째, 군집 수 K를 사람이 미리 안다.

셋 다 데이터가 아니라 알고리즘 쪽의 사정이고, 어기면 결과가 틀렸다는 신호 없이 그냥 나온다. K-평균은 어떤 데이터를 넣어도 언제나 K개의 무리를 돌려준다 — 무리가 실제로 K개 있든 없든 그렇다.

완전히 균일한 난수 점 천 개를 넣어도 K-평균은 K개의 예쁜 조각을 내놓는다. 구조가 없다는 답을 낼 길이 알고리즘 안에 없기 때문이다. 그래서 군집화 결과를 받았을 때 첫 질문은 "무리가 어떻게 생겼나"가 아니라 "이 데이터에 무리가 있기는 한가"여야 한다. 실루엣이 0 근처에 눌러앉아 있으면 대개 후자의 답이 아니오다.

알고리즘 네 걸음

할당과 갱신

절차는 네 줄이다. 중심점 K개를 잡고, 각 점을 가장 가까운 중심에 할당하고, 각 무리의 평균으로 중심을 다시 계산하고, 할당이 더 안 바뀔 때까지 둘째와 셋째를 반복한다.

1차원 다섯 점 [1, 2, 8, 9, 20]을 K=2로 나눠 보자. 중심을 1과 2로 잡고 시작한다. 첫 할당에서 1만 첫 중심에 가고 나머지 넷이 둘째 중심으로 간다. 평균을 다시 내면 중심이 1과 9.75가 된다. 둘째 할당에서는 2가 넘어와 {1, 2}와 {8, 9, 20}으로 갈리고, 중심이 1.5와 12.33이 된다. 셋째 할당에서 소속이 그대로라 여기서 멈춘다.

이 세 걸음에서 눈여겨볼 것은 멈추는 조건이 중심의 이동량이 아니라 할당의 변화라는 점이다. 할당이 그대로면 평균도 그대로이고 그다음 할당도 그대로라, 더 돌려 봐야 같은 자리에 머문다. max_iter는 그 전에 손을 떼기 위한 안전장치이지 보통 쓰이는 종료 조건이 아니다.

한 번 반복의 비용도 여기서 읽힌다. 할당은 점 n개마다 중심 K개와의 거리를 재므로 n · K · d에 비례하고, 갱신은 점을 한 번 훑으므로 n · d다. 반복 횟수를 t라 하면 전체가 t · n · K · d다 — 네 값 모두에 선형이라 K-평균이 수십만 건에서도 버티는 이유가 이 식에 들어 있다.

kmeans = KMeans(
    n_clusters=4,
    init='k-means++',   # 초기화 전략
    n_init=10,          # 다른 초기값으로 10회 실행 후 최선 선택
    max_iter=300,
    random_state=42
)
kmeans.fit(X)
print("WCSS (관성):", kmeans.inertia_)

목적 함수의 단조 감소

알고리즘이 줄이는 수는 WCSS, 곧 각 점과 자기 중심 사이 거리의 제곱을 전부 더한 값이다. sklearn에서는 inertia_로 읽는다.

$$\mathrm{WCSS} = \sum_{i=1}^{K} \sum_{x \in C_i} \lVert x - \mu_i \rVert^2$$

두 걸음이 각각 이 값을 줄인다는 것이 수렴의 근거다. 할당 단계에서는 각 점이 더 가까운 중심으로 옮겨 가니 그 점의 기여가 줄거나 같다. 갱신 단계에서는 평균이 제곱 거리 합을 최소로 만드는 점이라는 성질 때문에 역시 줄거나 같다. 값이 단조 감소하고 아래로 유계이며 가능한 할당의 경우의 수가 유한하므로, 알고리즘은 반드시 유한 번에 멈춘다.

지역 최솟값

멈춘다는 것과 최선에서 멈춘다는 것은 다르다. 같은 다섯 점을 중심 1과 20으로 시작해 보자. 첫 할당에서 {1, 2, 8, 9}와 {20}으로 갈리고 중심이 5와 20이 된다. 다음 할당에서 소속이 안 바뀌어 바로 멈춘다. 이때 WCSS는 50이다.

앞의 실행은 89.17이었다. 같은 데이터, 같은 알고리즘인데 시작점만 달라 값이 78% 차이 난다. K-평균이 찾는 것은 전역 최적이 아니라 시작점에서 굴러 내려간 지역 최솟값이다. 그래서 초기화가 성능 튜닝이 아니라 정확도 문제가 된다.

K-means++ 초기화

무작위 초기화의 실패

기본형 K-평균은 중심 K개를 데이터에서 무작위로 고른다. 위의 두 실행이 보여 준 대로, 운이 나쁘면 가까이 붙은 점 둘이 중심으로 뽑혀 실제로는 하나인 무리를 둘로 쪼개고 멀리 있는 무리를 통째로 놓친다. 무리가 많아질수록 확률이 나빠진다. 크기가 같은 무리가 K개 있을 때 K개 중심이 서로 다른 무리에서 하나씩 뽑힐 확률은 K! / K^K다. K가 4면 9.4%이고 10이면 0.036%다. 무리 열 개짜리 데이터에서 무작위 초기화가 제대로 된 시작점을 잡을 확률이 삼천 번에 한 번이라는 뜻이다.

그리고 나쁜 시작점은 나쁜 결과로 조용히 끝난다. 한 무리가 둘로 쪼개지고 다른 둘이 하나로 합쳐져도 WCSS는 그럴듯한 값을 내고 경고도 없다. 결과를 열어 보기 전에는 실패했다는 사실조차 모른다.

D² 표집

K-means++ 초기화는 중심을 무작위가 아니라 멀리 있는 쪽에 유리하게 뽑는다. 첫 중심 하나만 무작위로 고르고, 그다음부터는 이미 고른 중심들과의 최단 거리를 제곱한 값에 비례하는 확률로 다음 중심을 뽑는다.

같은 다섯 점에서 첫 중심이 2로 뽑혔다고 하자. 나머지 점의 최단 거리 제곱은 1은 1, 8은 36, 9는 49, 20은 324다. 합이 410이므로 20이 뽑힐 확률은 79%, 9는 12%, 8은 8.8%, 1은 0.24%다. 앞에서 좋은 답(WCSS 50)을 낸 그 초기화가 79%의 확률로 뽑힌다. 무작위였다면 25%다.

제곱을 쓰는 것이 핵심이다. 거리에 그냥 비례하게 뽑으면 20의 확률이 58%로 내려간다. 제곱이 먼 점을 더 세게 밀어 주고, 동시에 확률이 0이 아니라 이상치 하나가 항상 중심이 되는 일도 막는다.

n_init

sklearn의 기본값은 init='k-means++'이고 여기에 n_init이 하나 더 붙는다. 서로 다른 초기값으로 전체 절차를 n_init번 돌린 뒤 WCSS가 가장 작은 결과만 남기는 장치다. 초기화를 잘하는 것과 여러 번 해 보는 것은 다른 대책이고 둘은 함께 쓰인다.

비용은 그대로 n_init배다. 다만 K-means++가 좋은 자리에서 시작하므로 반복 횟수 자체가 줄어, 실측하면 무작위 초기화보다 n_init이 같아도 오히려 빠른 경우가 많다.

K 고르기

엘보우의 한계

K를 모를 때 가장 먼저 시도하는 것이 엘보우 법이다. K를 1부터 늘려 가며 WCSS를 재고, 감소폭이 확 꺾이는 지점을 고른다.

문제는 WCSS가 K에 대해 항상 줄어든다는 데 있다. 점이 n개일 때 K=n이면 모든 점이 자기 중심이 되어 WCSS는 0이다. 그래서 "값이 작은 K를 고른다"는 기준이 성립하지 않고, 꺾이는 자리를 눈으로 찾아야 한다. 무리가 또렷한 데이터에서는 꺾임이 분명하지만 밀도가 완만하게 변하는 실제 데이터에서는 곡선이 매끄러워 팔꿈치가 안 보인다. 엘보우는 답을 주는 방법이 아니라 후보를 좁히는 방법으로 쓰는 것이 맞다.

눈에 의존하지 않으려는 시도도 있다. 감소율을 직접 표로 찍어 큰 폭에서 작은 폭으로 떨어지는 자리를 보거나, K와 WCSS 곡선의 두 끝을 이은 직선에서 가장 멀리 떨어진 점을 고르는 방식이 흔하다. 후자는 사람이 「팔꿈치」라고 부르는 자리를 기하로 옮긴 것이라 재현은 되지만, 곡선이 완만하면 그 최대 거리도 애매해진다는 본래의 한계까지 옮겨 온다.

실루엣 계수

실루엣 계수는 다른 것을 잰다. 점 하나에 대해 같은 무리 안 점들과의 평균 거리를 a, 가장 가까운 다른 무리 점들과의 평균 거리를 b라 할 때 (b - a) / max(a, b)가 그 점의 실루엣이고, 전체 평균이 그 군집화의 점수다.

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

값은 -1에서 1 사이다. 1에 가까우면 자기 무리에 잘 묻혀 있고, 0 근처면 두 무리의 경계에 걸쳐 있고, 음수면 다른 무리에 더 가깝다 — 잘못 배정됐다는 뜻이다. 엘보우와 달리 K가 커진다고 단조로 오르지 않으므로 최댓값을 주는 K를 그냥 고를 수 있다. 계산 비용은 모든 점 쌍의 거리를 재야 해 데이터가 커지면 부담스럽고, 그럴 때는 표본을 뽑아 재는 방식을 쓴다.

평균값 하나만 보지 말고 점마다의 실루엣을 분포로 펼쳐 보면 더 많은 것이 보인다. 전체 평균이 0.55로 같아도, 모든 점이 0.5~0.6에 몰려 있는 군집화와 절반이 0.8이고 절반이 0.3인 군집화는 전혀 다른 상태다. 후자라면 잘 뭉친 무리와 억지로 만든 무리가 섞여 있다는 뜻이고, K를 하나 줄여 보라는 신호다.

for k in range(2, 11):
    labels = KMeans(n_clusters=k, n_init=10, random_state=42).fit_predict(X)
    print(f"K={k}: 실루엣={silhouette_score(X, labels):.4f}")

도메인이 정하는 K

지표 둘이 서로 다른 K를 가리키는 일이 흔하고, 그때 답을 내는 것은 대개 지표가 아니라 그 데이터를 쓰는 쪽의 사정이다. 고객을 나눈 뒤 무리마다 다른 메시지를 보낼 계획인데 마케팅 팀이 운영할 수 있는 메시지가 셋이면 K는 3이다. 실루엣이 K=7을 가리켜도 쓸 수 없는 답이면 좋은 답이 아니다.

거꾸로 지표가 고른 K를 열어 보는 일도 필요하다. 무리마다 평균 특성을 찍어 보고 사람 말로 이름이 붙는지 확인한다 — 「자주 오고 많이 쓰는」·「한 번 오고 안 오는」처럼 이름이 붙으면 쓸 수 있는 분할이고, 붙지 않으면 숫자만 맞은 분할이다.

전처리와 스케일

스케일링

K-평균은 거리만 보므로 단위가 큰 특성 하나가 거리를 독점한다. 나이와 연봉으로 고객을 나눈다고 하자. 25살에 연봉 5,000만 원인 사람과 55살에 5,100만 원인 사람의 거리 제곱은 나이 쪽이 900, 연봉 쪽이 1조다. 나이의 기여는 10억분의 1이고, 사실상 연봉만으로 나눈 것과 같다.

표준화를 거치면 두 특성이 모두 평균 0, 표준편차 1의 척도로 옮겨져 같은 무게로 거리에 들어간다. K-평균에 StandardScaler가 거의 항상 붙어 다니는 이유다. 스케일링은 군집화가 끝난 뒤에도 한 번 더 문제가 된다 — 무리의 특성을 사람이 읽으려면 중심점을 원래 단위로 되돌려야 하므로, 변환기를 버리지 말고 들고 있어야 한다. 다만 표준화가 중립인 것도 아니다 — 모든 특성을 동등하게 보겠다는 선택이고, 특정 특성이 더 중요하다면 그쪽에 가중치를 주는 편이 맞다.

범주형과 혼합형

범주형 특성에는 평균이 없다. 「서울, 부산, 대구」의 평균은 정의되지 않으므로 갱신 단계가 성립하지 않는다. 원-핫 인코딩으로 숫자를 만들어 밀어 넣을 수는 있지만, 그러면 범주가 많은 특성 하나가 차원을 수십 개 차지해 거리를 다시 독점한다.

범주형만 있으면 평균 대신 최빈값을 쓰는 K-modes를, 수치형과 범주형이 섞여 있으면 둘을 각각 다루고 가중치로 합치는 K-prototypes를 쓴다. 이 갈림길을 모르고 원-핫으로 밀어붙인 결과가 "군집이 이상하게 나온다"의 흔한 원인이다.

고차원에서의 거리

특성이 많아지면 거리 자체가 변별력을 잃는다. 차원이 올라갈수록 임의의 두 점 사이 거리가 서로 비슷해져 가장 가까운 점과 가장 먼 점의 비가 1로 수렴한다. 모든 점이 고르게 멀어지면 "가장 가까운 중심"이라는 말이 뜻을 잃고, 할당 단계가 사실상 무작위가 된다.

차원이 몇부터 위험한지는 데이터가 정한다. 특성이 스무 개라도 그중 셋만 실제로 변하고 나머지가 거의 상수면 유효 차원은 셋이다. 반대로 원-핫으로 부풀린 수백 차원은 대부분이 0이라 거리가 「겹치는 범주가 몇 개인가」로 퇴화한다. 차원 수를 세기 전에 특성마다 분산과 상관을 먼저 보는 것이 순서다.

실무의 순서는 차원을 먼저 줄이고 군집화를 하는 것이다. PCA로 주요 성분 몇 개만 남기거나 도메인 지식으로 특성을 추려 낸 뒤 K-평균을 돌린다. 이때 PCA가 몇 차원을 남길지는 설명 분산 비율로 정하고, 줄인 공간에서 실루엣을 다시 재어 줄이기 전보다 나아졌는지 확인한다.

한계와 대안

구형 가정 · 이상치 · K 지정

K-평균의 실패는 세 모양으로 나타난다. 초승달이나 고리처럼 구형이 아닌 무리는 중심에서의 거리로 나눌 수 없어 통째로 잘못 갈린다. 이상치는 평균을 끌어당기므로 멀리 떨어진 점 하나가 중심을 옮겨 무리 전체의 소속을 바꾼다. 그리고 K를 미리 정해야 하는 제약은 데이터를 보기 전에 답의 일부를 정해 두는 셈이다.

이상치는 전처리에서 걷어 내거나, 평균 대신 실제 데이터 점을 중심으로 쓰는 K-Medoids로 완화한다. 평균은 극단값에 끌리지만 중앙에 있는 실제 점은 덜 끌린다. 대신 중심 후보가 데이터 점으로 제한되어 계산량이 크게 는다 — 점 n개짜리 무리에서 최적의 대표 점을 찾으려면 점 쌍의 거리를 다 재야 한다.

K를 미리 정해야 하는 제약은 대안이 두 갈래다. K를 안 받는 알고리즘으로 갈아타거나, K를 바꿔 가며 돌려 보고 지표로 고르거나다. 앞 절의 엘보우와 실루엣이 후자의 도구이고, 다음 절의 둘이 전자에 해당한다.

DBSCAN과 GMM

비구형이면 DBSCAN이다. 밀도로 무리를 정의하므로 모양에 제약이 없고 K를 안 받으며 어디에도 속하지 않는 점을 잡음으로 따로 빼 준다. 대신 밀도 기준 두 개(반경과 최소 점 수)를 정해야 하고, 무리마다 밀도가 크게 다르면 한 벌의 기준으로는 안 잡힌다.

무리가 구형이긴 한데 길쭉하거나 서로 겹치면 GMM이 낫다. 각 무리를 정규분포로 보고 점마다 각 무리에 속할 확률을 주므로, 경계에 걸친 점을 하나로 못 박지 않는다. K-평균은 GMM에서 모든 분포가 같은 구형이고 소속이 0 아니면 1인 특수한 경우에 해당한다.

Mini-Batch K-Means

데이터가 수십만 건을 넘으면 매 반복마다 전체 점을 훑는 비용이 문제가 된다. Mini-Batch K-Means는 반복마다 무작위 표본 하나를 뽑아 그 표본으로만 중심을 조금씩 옮긴다. 100만 건에서 수 분 걸리던 것이 수 초로 줄고, WCSS는 표준 K-평균보다 조금 높게 나온다.

표본이 작을수록 빠르고 부정확하다는 관계가 그대로 성립하므로 batch_size가 정확도 손잡이 역할을 한다. 무리 하나가 표본에 거의 안 잡힐 만큼 작으면 그 무리의 중심이 갱신되지 않아 통째로 사라지기도 한다 — 불균형이 심한 데이터에서 Mini-Batch를 쓸 때 먼저 확인할 자리다.

바꿔치기가 아니라 거래다. 탐색 단계에서 K 후보를 빠르게 훑을 때는 Mini-Batch로 돌리고, K를 정한 뒤 최종 결과만 표준 K-평균으로 한 번 더 내는 방식이 흔하다. K-평균이 지금도 군집화의 기본 도구로 남아 있는 이유는 정확해서가 아니라 이렇게 규모와 정확도를 조절할 수 있을 만큼 단순해서다.

---

읽어주셔서 감사합니다. 😊