이름표 없이 묶다
중심이 스스로 걸어가는 알고리즘

지난 두 시간을 떠올려 봅시다. 8차시에서는 씨앗 55알의 길이와 무게를 재고 가까운 이웃에게 품종을 물었습니다. 9차시에서는 학생 24명의 공부 시간과 시험 점수로 직선 하나를 찾았습니다. 두 번 다 데이터에는 정답이 함께 적혀 있었습니다 — 이 씨앗은 A 품종, 저 학생은 78.6점.

기계는 그 정답을 보고 맞았는지 틀렸는지 알았습니다. 틀리면 고쳤고, 그 고침이 곧 학습이었습니다. 7차시의 말로 하면 지도학습입니다.

이제 오늘의 데이터를 봅시다. 한 반 학생 72명에게서 하루 공부 시간과 하루 스마트폰 사용 시간 두 가지만 걷었습니다. 앞 네 명은 이렇습니다.

오른쪽 끝 칸이 오늘의 전부입니다. 비어 있습니다. 누구도 이 학생들을 미리 분류해 두지 않았습니다. 8차시라면 여기서 막힙니다 — 이웃에게 물어봐야 이웃도 자기가 뭔지 모르니까요. 9차시도 막힙니다 — 맞힐 점수가 없으니 손실을 잴 수가 없습니다.

답으로 가기 전에, 여러분이 먼저 해 보세요. 아래 그림은 그 72명을 가로축 공부 시간, 세로축 스마트폰 시간으로 찍은 것입니다. 몇 덩어리로 보이나요? 손가락으로 동그라미를 쳐 보세요.

사람은 이 일을 0.5초 만에 합니다. 그런데 어떻게 했는지 설명해 보라고 하면 막힙니다. "가까운 것끼리요"라고 답하겠지요. 좋습니다 — 오늘 배울 알고리즘이 하는 말이 정확히 그것입니다. 다만 기계는 '가깝다'를 5차시에서 배운 거리로 재고, '끼리'를 두 줄짜리 규칙으로 씁니다.

7차시에서 학습의 갈래를 셋으로 나눴습니다. 정답을 주고 맞히게 하는 지도학습, 정답 없이 데이터의 짜임만 보게 하는 비지도학습, 해 보고 상을 받는 강화학습이었습니다. 오늘 다루는 군집화(clustering)는 비지도학습의 대표 선수입니다.

이름표가 없다는 것은 생각보다 큰 사건입니다. 세 가지가 한꺼번에 사라집니다.

그러면 무엇이 남을까요? 점들 사이의 거리가 남습니다. 5차시에서 만든 거리 함수를 떠올려 봅시다. 두 점의 좌표 차이를 제곱해서 더하고 뿌리를 씌우는 그 함수 말입니다.

거리만 있으면 이런 문장을 쓸 수 있습니다. "서로 가까운 점들은 한 무리다." 말은 되는데, 이대로는 프로그램이 될 수 없습니다. '가깝다'의 기준이 없고, 무리의 대표가 누구인지도 정해지지 않았기 때문입니다. 이 문장을 실행 가능한 규칙으로 바꾼 것이 오늘의 주인공입니다.

k-평균이 하는 일은 두 줄로 끝납니다. 정말 두 줄입니다.

이 둘을 번갈아 되풀이합니다. 배정 → 이동 → 배정 → 이동…. 중심이 옮겨 가면 가장 가까운 중심이 바뀌는 점이 생기고, 배정이 바뀌면 평균이 바뀌어 중심이 또 옮겨 갑니다. 이 되먹임이 어느 순간 멎습니다. 그때가 답입니다.

배정 한 걸음을 손으로 — 첫 학생 하나

말로만 보면 쉬운데, 한 번 손으로 해 봐야 붙습니다. 우리 데이터의 첫 학생 (2.79, 4.82)를 놓고, 중심 셋이 (0.79, 5.46) · (1.47, 5.32) · (1.03, 5.04)에 있다고 합시다. (이 셋은 잠시 뒤 프로그램이 실제로 고르게 되는 시작 중심입니다.)

여기서 눈여겨볼 것이 하나 있습니다. 거리의 제곱 칸과 실제 거리 칸의 순위가 같습니다. 4.4096 > 3.1460 > 1.9924 이고, 2.0999 > 1.7737 > 1.4115 입니다. 당연합니다 — 제곱근은 값이 커질수록 결과도 커지는 함수라 순서를 뒤집지 않기 때문입니다. 우리에게 필요한 것은 '누가 가장 가까운가' 하나뿐이니, 뿌리를 씌우는 계산을 회차마다 216번(72명 × 중심 3개) 아낄 수 있습니다. 오늘 코드가 dist 대신 dist2를 쓰는 까닭입니다.

이동 한 걸음을 손으로 — 6명의 평균

72명을 전부 배정하고 나면, 1번 중심에는 6명이 붙습니다. 이 여섯 명입니다.

같은 회차에서 3번 중심에는 3명만 붙어 (1.25, 5.12) (0.94, 5.05) (1.03, 5.04)의 평균인 (1.07, 5.07)로 조금 옮겨 가고, 2번 중심에는 나머지 63명이 몰려 (3.97, 3.84)로 훌쩍 걸어갑니다. 1회 만에 2번 중심이 2.909만큼 움직인 것입니다 — 데이터 폭이 6 남짓인 판에서 꽤 큰 걸음이지요.

왜 하필 평균일까요? 다른 자리를 골라도 될 것 같은데요. 이 물음의 답은 개념 3에서 나옵니다. 잠깐 기억해 두세요 — 무엇을 잘하려는지 정하고 나면, 중심을 어디로 옮길지도 따라서 정해집니다.

두 걸음을 되풀이한다고 했는데, 언제까지 되풀이할까요? 답은 놀랄 만큼 단순합니다. 중심이 한 발짝도 움직이지 않으면 끝입니다. 코드로는 한 줄이에요.

실제로 우리 데이터를 K = 3으로 돌리면 이렇게 걸어갑니다. 시작 중심은 학생 72명 중 16번 · 7번 · 28번을 골라 그 자리에 두었습니다. (컴퓨터는 첫 학생을 0번이라 부르므로, 16번은 앞에서 열일곱째 학생입니다. 어떻게 골랐는지는 개념 4에서 다룹니다.)

표에서 두 가지를 읽어 봅시다.

첫째, 걸음이 점점 짧아집니다. 2.909 → 1.112 → 1.874 → 0.668 → 0.301 → 0. 쭉 줄기만 하는 것은 아니고 3회에 잠깐 다시 커지지만, 큰 흐름은 줄어드는 쪽입니다. 중심이 제자리를 찾아갈수록 옮길 거리가 없어지는 것이지요.

둘째, 누가 어느 무리인지가 중심보다 먼저 굳습니다. 표의 '묶음 크기'는 그 회차의 ① 배정에서 나온 값입니다. 4회는 21 / 24 / 27이었다가 5회에 26 / 24 / 22가 되고 6회에도 그대로예요. 그런데 5회의 배정은 4회가 만들어 놓은 중심으로 나눈 것입니다. 즉 4회를 마친 순간 분할은 이미 정답이었습니다. 그때의 SSE는 27.98이고, 중심이 한 번 더 걸어간 5회에야 25.58이 됩니다 — 분할이 먼저 굳고, 중심의 좌표가 뒤늦게 자리를 잡습니다.

SSE — 잘 묶였는지 재는 자

표에 계속 나온 SSE가 무엇인지 이제 밝힙니다. 응집도(SSE, sum of squared errors)는 이렇게 잽니다.

이제 개념 2에서 미뤄 둔 물음에 답할 수 있습니다. 왜 하필 평균으로 옮기는가?

SSE는 '중심까지 거리의 제곱 합'입니다. 그런데 어떤 점들의 모임에서 거리 제곱 합을 가장 작게 만드는 자리가 바로 그 점들의 평균입니다. 중심을 미지수로 두고 제곱 합을 쓰면 아래로 볼록한 이차식이 되고, 그 최솟값이 평균에서 잡히기 때문이에요. 그러니 '이동' 단계에서 평균으로 옮기는 것은 취향이 아니라 SSE를 그 상황에서 가장 많이 깎는 유일한 선택입니다.

덧붙여, SSE는 회차마다 줄기만 하고 늘어나지 않습니다. 배정 단계는 각 점을 더 가까운 중심으로 옮기니 줄고, 이동 단계는 방금 본 이유로 줄기 때문입니다. 표에서 329.54 → 202.02 → 58.06 → 27.98 → 25.58로 한 번도 오르지 않은 것이 그 증거입니다. 점의 개수가 유한하니 나눌 수 있는 가짓수도 유한하고, 줄기만 하는 값이 유한한 후보 안에서 돌면 언젠가 반드시 멈춥니다. k-평균이 무한 루프에 빠지지 않는 까닭입니다.

개념 3에서 한 가지를 슬쩍 넘어갔습니다. 시작 중심을 어떻게 골랐는가?

답은 시시합니다. 학생 72명 중 K명을 무작위로 뽑아 그 자리에 두었습니다. 씨앗(seed) 4로 뽑으니 16번 · 7번 · 28번이 나왔습니다. 이런 방식은 대충 정한 것처럼 보이지만, 사실 널리 쓰이는 표준적인 출발입니다. 데이터가 있는 자리에 중심을 두어야 아무도 안 붙는 중심이 생길 확률이 낮아지거든요.

그런데 여기에 이 차시에서 가장 중요한 함정이 숨어 있습니다. 씨앗만 7로 바꿔 보겠습니다. 데이터도 그대로, 코드도 한 글자 안 고쳤습니다.

씨앗 7이 한 일을 그림으로 옮기면 이렇습니다. 오른쪽 아래에 있던 24명짜리 덩어리를 8명 + 16명으로 쪼개고, 왼쪽 위와 가운데 위에 있던 26명 + 22명을 48명 한 무리로 합쳐 버렸습니다. 우리는 이 데이터를 만든 사람이라 정답을 압니다. 견주어 보면 이렇습니다.

이 현상에는 이름이 있습니다. 지역 최적(local optimum)입니다. 골짜기 여러 개가 있는 산에서 한 골짜기 바닥에 앉아 있는 것과 같아요. 주변은 다 오르막이니 더 내려갈 곳이 없어 보이지만, 산 너머에 더 깊은 골짜기가 있습니다.

언제 실패하는가 — 씨앗 20개를 전부 돌려서

씨앗 7만 나쁜 것일까요, 아니면 흔한 일일까요? 세어 보면 됩니다. 씨앗 1부터 20까지 스무 번 돌린 결과입니다.

실패한 다섯(7 · 13 · 16 · 18 · 20)에 공통점이 있을까요? 처음 떠오르는 짐작은 "시작 중심 셋이 같은 덩어리에서 뽑혔을 때"입니다. 그럴듯하죠. 그런데 확인해 보면 틀립니다.

• '같은 덩어리에서 둘 이상 뽑힌' 씨앗은 13개다. 그런데 실패는 5개뿐이다. 겹쳤어도 여덟 번은 잘 나눴다.
• 씨앗 4를 보라. 셋이 전부 왼쪽 위 한 덩어리 안에서 뽑혔는데도 6회를 걸어 제대로 나눴다.
• 실패한 다섯은 '멀리 떨어진 오른쪽 아래 덩어리에서 둘 이상 뽑힌' 씨앗 목록과 정확히 일치한다. 프로그램이 두 목록을 직접 견주어 True를 찍는다.
• 거꾸로, 시작 중심 셋이 서로 다른 세 덩어리에서 나온 경우는 20번 중 7번인데, 그 7번은 모두 성공했다.

왜 그럴까요? 왼쪽 위 덩어리와 가운데 위 덩어리는 서로 가깝습니다. 거기서 중심 둘이 뽑혀도 두 중심이 서로를 밀어내며 갈라섭니다. 반면 오른쪽 아래 덩어리는 멀리 떨어져 있습니다. 거기에 중심 둘이 갇히면, 남은 중심 하나가 위쪽 48명을 통째로 떠맡아야 합니다. 그리고 위쪽 48명은 한 무리로 묶여도 그럭저럭 뭉쳐 보여서 갈라질 힘이 생기지 않습니다.

이 설명이 정말 맞는지, 씨앗에 기대지 말고 손으로 찍어서 확인해 보았습니다. 시작 중심 셋을 한 덩어리 안에 아무렇게나 던져 넣고 1,000번씩 돌린 결과입니다.

⚠️ 다만 "오른쪽 아래에 몰아 찍으면 반드시 진다"고 말하면 안 됩니다. 840번이 졌다는 것은 160번은 이겼다는 뜻이기도 합니다. 시작점이 답을 정하는 것이 아니라 흔드는 것입니다.

조용한 고장 하나 — 빈 무리

실패에는 한 가지 유형이 더 있습니다. 씨앗 274로 돌리면 묶음 크기가 48 / 24 / 0이 나옵니다. 중심 하나에 아무도 붙지 않은 것입니다. 시작 중심 셋을 거의 같은 자리에 몰아 두어도 같은 일이 생깁니다 — 직접 찍어 보면 2회 만에 멈추고 묶음이 0 / 24 / 48, SSE는 70.2012가 나옵니다.

이때 프로그램은 어떻게 될까요? 오류가 날까요? 무한 루프에 빠질까요? 둘 다 아닙니다. 깔끔히 '수렴'하고 답을 내놓습니다. 다만 K = 3이라고 써 놓고 실제로는 두 무리인 답입니다. 화면에는 아무 경고도 뜨지 않습니다. 결과 표의 0을 사람이 발견해야만 알 수 있어요.

지금까지 K = 3으로 놓고 이야기했습니다. 그런데 왜 3인가요? 사실은 그림을 보고 "세 덩어리네" 하고 사람이 정한 것입니다. 정직하게 말하면 k-평균은 무리의 개수를 스스로 찾지 못합니다. 그것이 이 알고리즘의 가장 큰 약점이에요.

그러면 SSE를 자로 쓰면 되지 않을까요? SSE가 가장 작아지는 K를 고르는 것이지요. 좋은 생각처럼 들립니다. K를 1부터 7까지 바꿔 가며 SSE를 재 봅시다. (K마다 씨앗 12개를 다 돌려 가장 좋은 값을 적었습니다. 개념 4에서 배운 대로요.)

여기서 멈추면 안 됩니다. K를 계속 키우면 어떻게 될까요? K = 72, 즉 학생 수와 같게 하면 중심을 모든 점 위에 하나씩 놓을 수 있습니다. 그러면 모든 점이 자기 중심 위에 정확히 얹히니 SSE = 0.0입니다.

그러면 K는 어떻게 정할까요? 표를 다시 보되 SSE 값이 아니라 줄어든 양을 보세요.

줄어든 양을 보면 이야기가 달라집니다. 482.14 → 44.62 → 5.78 → 3.76 → 3.18 → 2.48. K = 3에서 4로 갈 때의 감소(5.78)는 K = 2에서 3으로 갈 때의 감소(44.62)의 7.7분의 1입니다. 그리고 K = 4 이후로는 직전 SSE의 19~23%씩 거의 일정하게 줄어듭니다.

일정하게 줄어든다는 것은 새로 나눌 덩어리가 더는 없다는 뜻입니다. 멀쩡한 덩어리를 억지로 반으로 자르면 SSE는 얼마간 줄기 마련이거든요. 그러니 뚝 떨어지다가 평평해지기 시작하는 자리를 고르면 됩니다. 이것이 팔꿈치 방법(elbow method)입니다. 우리 데이터의 팔꿈치는 K = 3이고, 눈으로 센 덩어리 수와 같습니다.

K = 3으로 제대로 나눈 결과를 다시 봅시다. 최종 중심 셋과 인원은 이랬습니다.

이 셋에 이름을 붙여 보라고 하면 교실에서 여러 답이 나올 겁니다. '폰을 많이 쓰는 무리', '공부에 집중한 무리', '중간 무리'. 그런데 여기서 반드시 짚어야 할 것이 있습니다.

지도학습과 견주면 차이가 뚜렷합니다. 8차시에서 씨앗을 'A 품종'이라고 부를 수 있었던 것은 누군가 미리 그렇게 적어 두었기 때문입니다. 군집에는 그런 사람이 없습니다. 그래서 군집 결과에는 맞고 틀림이 없습니다. SSE로 '얼마나 뭉쳤는지'는 잴 수 있어도, '올바른 무리인지'는 잴 수 없습니다.

그래도 쓸모가 있다 — 세 가지 쓰임

이상 탐지는 우리 데이터로도 확인할 수 있습니다. 학생 한 명을 (12.0, 12.0)에 놓아 봅시다. 하루에 12시간 공부하고 12시간 폰을 쓴다는, 물리적으로 말이 안 되는 기록입니다. 돌려 보면 이렇게 됩니다.

여기서 두 가지를 동시에 배웁니다. 첫째, SSE가 갑자기 치솟으면 이상한 점이 섞였다는 신호일 수 있습니다 — 이것이 이상 탐지입니다. 둘째, k-평균은 이상치에 약합니다. 평균으로 옮기는 방식이라 멀리 있는 점 하나가 중심을 끌고 갑니다. 4차시에서 1750cm 학생 한 명이 평균 키를 166cm에서 198cm로 끌어올렸던 것과 같은 일입니다. 그때 배운 전처리를 안 하면 여기서 대가를 치릅니다.

아래 판에 학생 72명이 전부 찍혀 있습니다. 개념 3의 표에 나온 그 데이터입니다. 👣 한 걸음을 누르면 ① 배정과 ② 이동이 번갈아 한 단계씩 진행됩니다. 중심이 지나온 자리는 선으로 남습니다.

중요한 것은 시작 중심을 여러분이 정한다는 점입니다. 씨앗 번호로 뽑을 수도 있고, 판 위를 직접 눌러 원하는 자리에 놓을 수도 있습니다. 일부러 나쁜 자리에 찍어 보세요. 그것이 오늘 과제 중 하나입니다. 공책을 펴 두세요. 아래 세 과제의 답은 확인 문제에서 다시 묻습니다.

과제 ① 표를 채운다 — 씨앗만 바꿔 네 번

K를 3에 두고, 씨앗을 바꿔 가며 ▶ 끝까지를 네 번 누릅니다. 매번 씨앗을 바꾸면 자동으로 처음 상태로 돌아갑니다.

SSE 칸을 먼저 보세요. 네 줄이 전부 같습니까? 다르다면 그것이 오늘의 첫 결론입니다 — 같은 데이터에 같은 코드를 돌렸는데 답이 갈렸다. 그리고 넷 다 "멈췄다"고 보고했다는 것도 함께 적어 두세요.

과제 ② 반례를 만든다 — 내 손으로 지게 만들기

이제 시작 중심을 '내가 직접 찍기'로 바꿉니다. 판을 누르면 그 자리에 중심이 놓입니다. K개를 다 찍어야 걸음을 뗄 수 있어요.

• 일부러 지게 만들기. 중심 셋을 모두 오른쪽 아래 덩어리 안에 찍어 보세요. 개념 4의 표대로 열 번 중 여덟 번은 집니다 — 두세 번 안에 성공할 거예요. SSE가 64.4168 · 65.0160 · 68.2336 중 하나가 나오면 반례를 만든 것입니다. 그때 묶음 크기와 '제자리' 칸을 함께 적으세요. (제자리가 50 / 72면 22명이 남의 무리에 들어간 것입니다.)
• 거꾸로도 해 보기. 이번에는 중심 셋을 왼쪽 위 덩어리 안에만 몰아 찍습니다. 거의 언제나 SSE 25.5772가 나올 겁니다 — 1,000번을 던져 한 번도 안 졌던 그 자리입니다. 같은 '몰아 찍기'인데 왜 여기서는 안 질까요? 한 줄로 적어 보세요.
• 가장 빨리 끝내기. 이번에는 세 덩어리에 하나씩 찍습니다. 몇 회 만에 멈췄나요? 씨앗 4의 6회보다 적나요? (씨앗 2 · 5 · 9 · 10은 2회 만에 끝납니다. 여러분은 몇 회에 끝냈나요?)
• 빈 무리 만들기. 중심 셋을 거의 같은 자리에 겹쳐 찍어 보세요. 묶음 크기 셋 중에 0이 나오면 성공입니다. 이때 오류가 나던가요? 프로그램은 뭐라고 보고하던가요?
• 중심을 데이터 밖에 찍기. 점이 하나도 없는 오른쪽 위 빈 곳에 중심 하나를 찍어 보세요. 그 중심은 어디로 걸어가나요? 자취를 눈으로 따라가 보세요.

과제 ③ 팔꿈치를 내 손으로 찾는다

K 슬라이더를 1부터 7까지 옮기며 ▶ 끝까지를 돌립니다. K마다 씨앗을 서너 개 바꿔 가며 돌리고, 그중 가장 작은 SSE를 적으세요. 개념 4에서 배운 대로, 한 번만 돌린 값은 못 믿습니다.

아랫줄을 다 채운 뒤 어디에서 줄어드는 양이 갑자기 작아지는지 동그라미를 치세요. 거기가 팔꿈치입니다. 그리고 한 줄로 답해 보세요 — K를 계속 키우면 SSE는 어디까지 내려갈까?

시뮬레이터는 누군가 미리 만들어 둔 것입니다. 이제 코드로 갑니다. 아래 프로그램은 304줄이지만 겁먹을 것 없습니다. k-평균 알고리즘 자체는 [B] 구역의 87줄이고, 나머지는 데이터를 만들고 화면에 그리고 실험을 돌리는 부분이라 이미 다 채워져 있습니다. 여러분이 채울 자리는 다섯 곳(????? 여섯 칸)뿐입니다.

제대로 채웠다면 [C] 구역에 개념 3의 표와 똑같은 여섯 줄이 찍힙니다. 329.54 → 202.02 → 58.06 → 27.98 → 25.58 → 그리고 중심이 한 발짝도 움직이지 않았다. 6회에서 끝.

그다음이 진짜입니다. 프로그램은 이어서 이렇게 합니다.

• [D] 나뉜 결과를 글자 그림으로 그린다. A · B · C가 무리이고 *가 중심이다. 중심은 그 칸의 점 하나를 덮어쓰니 그림에서 점을 세면 72개가 안 됩니다.
• [E] 씨앗만 7로 바꿔 같은 일을 한다. 3회에 멈추고 SSE 68.2336이 나온다. 그림에서 한 덩어리가 통째로 한 글자가 된 것을 눈으로 확인하세요.
• [F] 씨앗 1~20을 전부 돌려 성공·실패를 센다. 그리고 실패의 규칙을 프로그램이 스스로 검사해 두 목록이 같은가? True를 찍는다.
• [G] K를 1~7로 바꿔 팔꿈치 표를 만든다. 과제 ③에서 손으로 채운 표와 견주세요.
• [H] K = 72이면 SSE가 얼마인지 직접 계산해 보여 준다.

8 · 9 · 10차시에 걸쳐 알고리즘 셋을 직접 짰습니다. 이제야 이 표가 읽힙니다. 셋을 나란히 놓아 보세요.

표에서 가장 눈에 띄는 줄은 '출발점을 바꾸면'입니다. 9차시의 손실 함수는 골짜기가 하나뿐인 그릇이라 어디서 출발해도 같은 바닥에 닿았습니다. k-평균은 골짜기가 여럿이라 출발점이 답을 바꿉니다. '조금씩 좋아지는 방향으로 간다'는 같은 생각인데, 지형이 다르면 결과가 다릅니다.

또 하나. '학습이 남기는 것' 줄을 보세요. k-NN은 아무것도 남기지 않고 데이터를 통째로 안고 있습니다. 경사하강은 숫자 둘로 줄였습니다. k-평균은 중심 K개로 줄였습니다. 학습이란 결국 '많은 데이터를 몇 개의 숫자로 줄이는 일'이라는 감각을, 13차시 퍼셉트론부터는 훨씬 큰 규모로 다시 만나게 됩니다.

✍️ 문제마다 답을 쓰고 제출하기를 누르세요. 제출하면 모범 답안이 열리고, 제출한 답은 선생님께 전달됩니다.