k-평균 군집: 가까운 것끼리 묶기

정답표 없이 점들을 클러스터(cluster) k 개로 나눕니다. 「가장 가까운 중심에 붙이기」와 「중심을 평균 자리로 옮기기」를 번갈아 하면 거리 제곱의 합이 걸음마다 줄어듭니다. 한 걸음씩 눌러 보며 왜 그런지 확인해 보세요.

한 줄 답. k-평균은 정답 없이 점들을 가까운 것끼리 k 개의 클러스터로 묶는 방법입니다. 중심 k 개를 놓고 ① 점마다 가장 가까운 중심의 클러스터에 넣고 ② 중심을 그 클러스터 점들의 평균 자리로 옮기기를, 더 바뀌지 않을 때까지 되풀이합니다. 이때 J = 점마다 자기 중심까지 거리의 제곱을 모두 더한 값 은 걸음마다 줄거나 그대로라서 반드시 멈춥니다. 다만 처음 자리에 따라 덜 좋은 답에서 멈출 수 있습니다.

J(거리 제곱의 합)

「한 걸음」을 누를 때마다 할당(assignment)과 중심 갱신(update)이 번갈아 일어납니다. 동그라미 안의 글자가 중심의 이름이고, 점은 자기가 든 클러스터의 글자로 그립니다. 옅은 선은 점에서 자기 중심까지의 거리이고, 점선 화살표는 방금 옮긴 중심의 길입니다. k 를 바꾸거나 「처음 자리 다시 뽑기」를 누르면 처음부터 다시 합니다. 점 30 개는 고정 시드(seed) 난수기로 지어낸 것(클러스터 셋, 10 개씩)이라 쪽을 열 때마다 같습니다. 「길쭉한 둘」「크기가 다른 둘」「초승달 둘」은 9절의 잘 안 되는 모양을 지어낸 자료이고(진짜 클러스터 둘, k = 2 로 시작), 점의 모양(동그라미 ●, 세모 ▲)이 진짜 클러스터, 색이 k-평균이 준 클러스터입니다.

해 볼 것. ① 처음(k = 3)에 「한 걸음」을 계속 누르면 J 가 282.1 → 109.1 → 50.45 → 32.28 로 줄고, 다섯 번째 걸음(할당)에서 클러스터를 바꾸는 점이 없어 멈춥니다. 클러스터마다 점이 10 개씩입니다. ② 「처음 자리 다시 뽑기」를 한 번 누르면 처음 중심 셋이 모두 아래 클러스터에 놓입니다. 끝까지 누르면 걸음 9 번 뒤 J = 173.34 에서 멈춥니다. 위의 두 클러스터가 한 클러스터(점 20 개)로 묶이고 아래 클러스터는 8 개와 2 개로 갈립니다. J 는 걸음마다 줄기만 했는데 답은 나쁩니다. 한 번 더 누르면 다시 32.28 에서 멈춥니다. ③ 쪽을 새로 열고 k 를 2, 3, 4, 5, 6 으로 바꿔 끝까지 누르면 마지막 J 는 177.66, 32.28, 26.8, 24.67, 21.97 입니다. 3 에서 크게 꺾이고 그 뒤로는 조금씩만 줄어듭니다.

1. k-평균이란: 정답 없이 묶기

스팸 메일 분류처럼 자료마다 정답(스팸인가 아닌가)이 붙어 있고 그 정답을 맞히게 배우는 것을 지도 학습이라고 합니다(로지스틱 회귀가 그 예). 정답 없이 자료만 보고 그 안의 모양을 찾는 것은 비지도 학습입니다. 가까운 것끼리 클러스터로 묶는 군집이 대표적입니다.

k-평균은 클러스터의 수 k 를 사람이 정하고, 클러스터마다 중심을 하나씩 둡니다. 점은 가장 가까운 중심의 클러스터에 듭니다. 「가깝다」는 보통 곧은 거리(유클리드 거리)로 잽니다. 차원이 몇 개든 같습니다. 2차원 점이든 수백 차원의 임베딩 벡터든 같은 식으로 묶습니다. 클러스터에 「봄 옷」 같은 이름을 붙이는 일은 사람이 합니다. k-평균은 묶기만 합니다.

2. 절차: 두 걸음의 되풀이

처음     점 k 개를 골라 중심 c₁, …, c_k 로 삼는다
되풀이   ① 할당:    점마다 가장 가까운 중심의 클러스터에 넣는다
         ② 갱신:    중심마다 자기 클러스터에 든 점들의 평균 자리로 옮긴다
멈춤     ① 에서 클러스터를 바꾼 점이 하나도 없으면 멈춘다

목적 함수  J = (점마다 자기 중심까지 거리)² 을 모두 더한 값

J 는 「클러스터가 얼마나 빽빽한가」를 잽니다. 점들이 자기 중심 가까이 모여 있을수록 작습니다. k-평균은 J 를 작게 만드는 나눔을 찾는 방법이고, 두 걸음은 각각 J 를 줄이는 방향으로만 움직입니다(4절). 이 되풀이를 로이드 알고리즘(Lloyd's algorithm)이라고도 부릅니다. 한 걸음의 계산은 점마다 중심 k 개까지의 거리를 재는 것이라, 점 수 × k × 차원 수에 비례합니다.

3. 식이 만들어지는 과정: 중심은 왜 평균인가

클러스터가 정해져 있을 때, J 를 가장 작게 하는 중심 자리는 어디일까요? 한 클러스터에 든 숫자 셋 2, 3, 7 로 봅니다. 후보 자리를 c 라고 하면 이 클러스터의 몫은 J(c) = (2 − c)² + (3 − c)² + (7 − c)² 입니다. 「다음」을 누르면 식이 한 조각씩 붙고(주황 바탕이 새로 붙은 조각), 그림과 설명이 바뀝니다.

  1. 숫자 셋과 후보 자리: J(c) = (2 − c)² + (3 − c)² + (7 − c)². c = 6 이면 16 + 9 + 1 = 26, c = 5 면 9 + 4 + 4 = 17, c = 4 면 4 + 1 + 9 = 14, c = 3 이면 1 + 0 + 16 = 17. 4 근처가 가장 작아 보입니다. 까닭: 중심을 옮기는 걸음은 이 합을 가장 작게 하는 자리를 찾는 일입니다.
  2. 괄호 풀기: J(c) = 3c² − 24c + 62. 숫자가 3 개라 c² 가 3 번, −2c × (2 + 3 + 7) = −24c, 2² + 3² + 7² = 62. 까닭: c² 앞의 수가 양수인 이차식이라 그래프는 U 자이고, 가장 낮은 곳이 꼭 하나 있습니다.
  3. 기울기: J′(c) = 6c − 24. 미분하면 기울기가 나옵니다. c = 2 에서 −12, c = 6 에서 12 입니다. 까닭: U 자의 바닥에서는 기울기가 0 입니다. 왼쪽은 내려가고(음수) 오른쪽은 올라갑니다(양수). 이것은 경사 하강법이 쓰는 기울기와 같은 것입니다.
  4. 완성: 6c − 24 = 0 → c = (2 + 3 + 7) ÷ 3 = 4. 바닥은 세 수의 평균입니다. 숫자가 n 개여도 J′(c) = 2n·c − 2(x₁ + … + xₙ) = 0 이라 c = (x₁ + … + xₙ) ÷ n, 곧 평균입니다. 점이 2차원이면 거리의 제곱이 (가로 차이)² + (세로 차이)² 라서 가로와 세로를 따로 풀고, 답은 가로 평균과 세로 평균입니다.

해 볼 것. ① 첫 단계에서 c 를 6, 5, 4, 3 으로 옮기면 J 가 26, 17, 14, 17 이고, 가 본 자리마다 그래프에 회색 점이 남습니다. ② 둘째 단계에서 U 자 곡선이 그 점들을 지나는 것을 보세요. ③ 셋째 단계에서 c 를 2 로 두면 기울기 −12, 4 로 두면 0 입니다. ④ 마지막 단계의 바닥 c = 4, J = 14 는 숫자 셋의 평균과 그때의 합입니다.

4. J 가 늘지 않는 까닭, 그래서 반드시 멈춘다

5. 손으로 풀어 보기: 숫자 다섯 개, k = 2

숫자 1, 2, 4, 8, 9 를 클러스터 둘로 묶습니다. 처음 중심은 숫자 1 과 4 를 골랐습니다(중심 A = 1, B = 4).

걸음클러스터 A클러스터 B중심 A, BJ
① 할당1, 24, 8, 91, 40 + 1 + 0 + 16 + 25 = 42
② 갱신1, 24, 8, 91.5, 70.25 + 0.25 + 9 + 1 + 4 = 14.5
③ 할당1, 2, 48, 91.5, 70.25 + 0.25 + 6.25 + 1 + 4 = 11.75
④ 갱신1, 2, 48, 92.33, 8.51.78 + 0.11 + 2.78 + 0.25 + 0.25 = 5.17
⑤ 할당1, 2, 48, 92.33, 8.55.17, 바뀐 점 없음: 멈춤
  1. ① 할당. 2 는 1 까지 1, 4 까지 2 라서 A. 8 과 9 는 4 가 더 가까워 B. J 는 점마다 자기 중심까지 거리의 제곱: 0² + 1² + 0² + 4² + 5² = 42.
  2. ② 갱신. A 는 (1 + 2) ÷ 2 = 1.5, B 는 (4 + 8 + 9) ÷ 3 = 7. J 가 14.5 로 줄었습니다.
  3. ③ 할당. 4 는 1.5 까지 2.5, 7 까지 3 이라 A 로 옮겨 갑니다. J = 11.75.
  4. ④ 갱신. A 는 (1 + 2 + 4) ÷ 3 = 7 ÷ 3 ≈ 2.33, B 는 (8 + 9) ÷ 2 = 8.5. J ≈ 5.17.
  5. ⑤ 할당. 4 는 2.33 까지 1.67, 8.5 까지 4.5 라 A 그대로. 바뀐 점이 없어 멈춥니다. J 는 42 → 14.5 → 11.75 → 5.17 로 한 번도 늘지 않았습니다.

6. 꼭 알아야 할 성질

성질쉬운 말실험에서
J 는 줄거나 그대로두 걸음 모두 J 를 늘리지 않는다. 그래서 반드시 멈춘다J 의 기록이 한 번도 늘지 않는다
처음 자리에 따라 답이 다르다멈춘 곳이 가장 좋은 답이라는 보장이 없다해 볼 것 ②: 173.34 와 32.28
중심은 클러스터의 평균클러스터가 정해지면 J 를 가장 작게 하는 자리가 평균이다3절의 c = 4
경계는 곧은 선이웃한 두 중심에서 거리가 같은 곳이 경계다. 그래서 둥글고 크기가 비슷한 클러스터에 맞는다9절
거리라서 눈금에 민감하다단위가 큰 축이 거리를 다 차지한다. 먼저 눈금을 맞춘다9절, 정규화

7. 초기화: 처음 자리와 k-means++

실험은 처음 중심을 점들 가운데서 아무렇게나 고릅니다. 그러면 해 볼 것 ② 처럼 중심 여럿이 한 클러스터에 몰려 나쁜 답에서 멈출 수 있습니다. 흔히 쓰는 대책은 둘입니다. 하나는 처음 자리를 여러 번 바꿔 돌리고 J 가 가장 작은 결과를 쓰는 것입니다. 다른 하나는 k-means++ 입니다. 첫 중심은 점 하나를 아무렇게나 고르고, 다음 중심부터는 「이미 고른 중심 가운데 가장 가까운 것까지 거리의 제곱」에 비례하는 확률로 점을 고릅니다. 먼 점이 뽑히기 쉬워 처음 중심들이 퍼집니다. scikit-learn 의 KMeans 는 k-means++ 를 기본으로 씁니다.

p(x) = D(x)² ÷ (D(x₁)² + D(x₂)² + … + D(xₙ)²)

「다음」을 누를 때마다 중심을 하나씩 고릅니다(k = 3). 점의 크기는 그 걸음에서 뽑힐 확률이고, 세 걸음 모두 같은 눈금으로 그립니다. 뽑기는 고정 시드 난수기라 쪽을 열 때마다 같습니다.

8. k 고르기: 엘보 방법과 실루엣

엘보 방법(elbow method). k 를 늘리며 가장 작은 J 를 그립니다. 클러스터가 많을수록 점이 중심에 가까워지니 J 는 줄기만 하고, k 가 점의 수와 같으면 0 입니다. 그래서 「J 가 가장 작은 k」가 아니라 줄어드는 폭이 갑자기 작아지는 곳(팔꿈치처럼 꺾이는 곳)을 고릅니다. 이 쪽의 점 30 개로 처음 자리를 20 가지씩 돌려 가장 작은 J 를 재면 k = 2, 3, 4, 5, 6 에서 149.14, 32.28, 25.66, 20.44, 16.75 입니다. 3 에서 꺾입니다.

050100150 23456클러스터 수 k 가장 작은 J 149.1432.2825.6620.4416.75 여기서 꺾임: k = 3
엘보 방법. 위 문단의 숫자 그대로입니다. k = 2 → 3 에서 J 가 116.86 줄고, 3 → 4 에서는 6.62 만 줍니다.

실루엣. 점마다 a = 자기 클러스터의 다른 점들까지 평균 거리, b = 가장 가까운 다른 클러스터의 점들까지 평균 거리를 재고 s = (b − a) ÷ (a 와 b 가운데 큰 것) 을 냅니다. −1 ~ 1 이고 1 에 가까울수록 제 클러스터에 잘 들어 있습니다. 모든 점의 평균이 가장 큰 k 를 고릅니다.

9. 잘 안 되는 모양

k-평균에서 두 클러스터의 경계는 두 중심에서 거리가 같은 곳, 곧 두 중심을 잇는 선분을 수직으로 가르는 곧은 선입니다. 그래서 클러스터가 둥글고 크기와 퍼짐이 비슷한 덩어리라고 가정하는 셈이고, 아래에서는 잘 맞지 않습니다.

10. 언제 무엇을 쓰나

선택지좋은 점나쁜 점쓰는 경우
k-평균단순하고 빠르다. 한 걸음이 점 수 × k × 차원 수라 큰 자료에도 쓴다k 를 정해야 한다. 둥글고 비슷한 크기의 클러스터를 가정한다. 처음 자리와 이상치에 흔들린다클러스터가 대체로 둥근 덩어리일 때. 많은 벡터를 대표 몇 개로 줄일 때(IVF, PQ)
계층 군집가까운 것부터 차례로 합쳐 묶이는 과정을 덴드로그램(트리 그림)으로 본다. k 는 나중에 트리를 자를 높이로 정한다모든 점 쌍의 거리를 다뤄 점이 많으면 느리고 메모리를 많이 쓴다. 한 번 합친 것은 되돌리지 않는다점이 많지 않고, 클러스터 안의 작은 클러스터(계층)까지 보고 싶을 때
DBSCANk 가 필요 없다. 빽빽한 곳을 따라 묶어 초승달·고리 같은 모양도 찾는다. 어디에도 안 드는 점은 노이즈(noise)로 따로 뺀다반지름과 최소 이웃 수를 정해야 한다. 클러스터마다 빽빽한 정도가 다르면 반지름 하나로 맞추기 어렵다모양이 제멋대로이고 노이즈 점이 섞인 자료
가우스 혼합클러스터마다 타원의 모양·기울기·크기를 따로 배운다. 점마다 「이 클러스터일 확률」을 준다k-평균보다 느리고 정할 숫자가 많다. k 를 정해야 하고 처음 자리에 흔들린다클러스터가 기울거나 길쭉한 타원이고 크기가 다를 때. 딱 잘라 나누지 않고 확률이 필요할 때

아래 실험은 9절의 「초승달 둘」(점 40 개)을 왼쪽은 k-평균(k = 2)으로, 오른쪽은 DBSCAN 으로 묶어 나란히 놓습니다. DBSCAN 의 규칙은 넷입니다.

핵심 점   반지름 ε 안에 점이 m 개 이상 있다(자기 포함)
경계 점   핵심 점은 아니지만, 어느 핵심 점의 반지름 ε 안에 있다
노이즈    어느 핵심 점의 반지름 ε 안에도 없다
클러스터  핵심 점의 반지름 ε 안에 있는 점은 그 핵심 점과 같은 클러스터. 그래서 이웃을 따라 번진다
최소 점 수 m = 4(고정)

왼쪽: 색이 k-평균의 클러스터, 점선이 곧은 경계. 오른쪽: ● 핵심 점, ○ 경계 점, × 노이즈. 회색은 아직 클러스터가 없는 점, 화살표는 이번 걸음에 클러스터가 번진 길입니다.

해 볼 것. ① ε = 0.8 에서 「다음」을 끝까지 누르면(물결 11 번) 클러스터 둘, 노이즈 2 개로 끝나고, 클러스터마다 한 초승달입니다. 왼쪽의 k-평균은 11 개를 잘못 묶었습니다. ② ε 를 1 로 올리면 두 초승달이 이어져 클러스터 하나가 됩니다. ③ ε 를 0.6 으로 내리면 클러스터 셋, 노이즈 23 개입니다.

어디에 쓰나

자주 묻는 것

k-평균과 k-최근접 이웃(kNN)은 같은 건가요?

아닙니다. 이름만 닮았습니다. k-최근접 이웃은 정답이 붙은 점들 가운데 새 점과 가장 가까운 k 개를 찾아, 그 점들의 정답으로 새 점의 답을 정합니다. k 는 이웃의 수입니다. k-평균은 정답 없이 점들을 클러스터 k 개로 묶고, k 는 클러스터의 수입니다.

돌릴 때마다 결과가 다른데 틀린 건가요?

틀린 것은 아닙니다. k-평균은 처음 자리에서 출발해 J 가 늘지 않는 쪽으로만 가다가 더 바뀌지 않으면 멈춥니다. 출발점이 다르면 다른 곳에서 멈출 수 있습니다. 처음 자리를 여러 번 바꿔 돌려 J 가 가장 작은 결과를 쓰고, 처음 자리를 k-means++ 로 고르면 덜 흔들립니다. 같은 결과를 다시 내려면 난수 시드를 고정합니다.

클러스터의 수 k 는 어떻게 정하나요?

정답은 없습니다. k 를 바꿔 가며 J 가 줄어드는 폭이 갑자기 작아지는 곳(엘보)이나 실루엣 점수가 가장 큰 곳을 봅니다. 쓰는 목적이 정하기도 합니다. 옷을 세 가지 크기로만 만든다면 k = 3 입니다.

낱말

여기서 쓴 말책에서 부르는 말
정답 없이 배우기 · 정답을 보고 배우기비지도 학습(unsupervised learning) · 지도 학습(supervised learning)
가까운 것끼리 묶기, 클러스터군집화(clustering), 군집·클러스터(cluster)
중심중심점, 센트로이드(centroid)
가까운 중심에 넣기 · 중심을 평균으로 옮기기할당 단계(assignment step) · 갱신 단계(update step)
두 걸음의 되풀이로이드 알고리즘(Lloyd's algorithm)
거리 제곱의 합 J목적 함수(objective), 군집 내 제곱합(within-cluster sum of squares), 관성(inertia, scikit-learn)
곧은 거리유클리드 거리(Euclidean distance)
더 바뀌지 않아 멈춤수렴(convergence)
그 근처에서만 가장 낮은 곳지역 최솟값(local minimum)
처음 자리를 퍼뜨려 고르기k-means++ 초기화(initialization)
팔꿈치 · 실루엣엘보 방법(elbow method) · 실루엣 계수(silhouette coefficient)
합쳐 가며 묶기, 트리 그림계층 군집(hierarchical clustering), 덴드로그램(dendrogram)
빽빽한 곳을 따라 묶기밀도 기반 군집, DBSCAN
클러스터마다 타원을 배우는 묶기가우스 혼합 모형(Gaussian mixture model, GMM)
칸으로 나눠 찾기역파일 색인(inverted file index, IVF)

출처

← k-최근접 이웃(kNN)서포트 벡터 머신(SVM) →