K-means clustering, K-NN

 

K-means Clustering vs K-NN: 이름은 비슷하지만 모든 것이 다르다

머신러닝을 처음 배울 때 많은 학생들이 K-means와 K-NN(K-최근접 이웃)을 혼동합니다. 이름에 똑같이 'K'가 들어가고 '가까운' 데이터 포인트를 다루는 것처럼 보이기 때문입니다. 하지만 두 알고리즘은 목표, 학습 방식, 사용 사례가 완전히 다른, 근본적으로 다른 도구입니다.
이 글에서는 먼저 K-means 클러스터링을 깊이 있게 파헤쳐 본 후, K-NN의 목적 함수를 상세히 분석하여 두 알고리즘을 다시는 헷갈리지 않도록 명확하게 정리하겠습니다.

• K-means 클러스터링: "이 데이터는 어떻게 그룹지을 수 있을까?" (비지도 학습, 그룹 찾기)
• K-NN: "이 새로운 데이터는 어떤 분류에 속할까?" (지도 학습, 예측하기)

---

1. K-means 클러스터링: 데이터에 숨겨진 구조 찾기 (비지도 학습)

1-1. 목표: 군집 내 응집도 최대화

K-means의 목표는 주어진 데이터들을 K개의 군집(cluster)으로 묶는 것입니다. 좋은 군집이란 어떤 상태일까요? 바로 "같은 군집 내의 데이터들은 서로 최대한 가깝게 모여있고, 다른 군집의 데이터들과는 최대한 멀리 떨어져 있는 상태"입니다.
K-means는 이 중 전자인 "군집 내 응집도"를 수학적으로 정의하고 이를 최적화합니다. 각 군집의 '중심(centroid)'을 $\mu_k$라고 할 때, 모든 데이터 포인트 $x_i$로부터 자신이 속한 군집의 중심 $\mu_{z_i}$까지의 거리 제곱의 합을 최소화하는 것을 목표로 삼습니다. 이를 군집 내 제곱합(WCSS: Within-Cluster Sum of Squares)이라고 부릅니다.

1-2. 목적 함수 (WCSS)

K-means가 최소화하려는 목적 함수 $J$는 다음과 같습니다.
$$ J = \sum_{i=1}^{n} \|x_i - \mu_{z_i}\|^2 = \sum_{k=1}^{K} \sum_{i \text{ in cluster } k} \|x_i - \mu_k\|^2 $$

• $x_i$: $i$번째 데이터 포인트 ($d$차원 벡터).
• $\mu_k$: $k$번째 군집의 중심 벡터.
• $z_i$: $i$번째 데이터가 속한 군집의 번호.
• $\| \cdot \|^2$: 유클리드 거리의 제곱.

이 식을 최소화하는 최적의 군집 중심 $\{\mu_k\}$와 각 데이터의 소속 $\{z_i\}$를 동시에 찾는 것은 매우 어려운 문제입니다 (NP-hard). 그래서 K-means는 두 변수를 번갈아가며 최적화하는 효율적인 휴리스틱 알고리즘을 사용합니다.

1-3. Lloyd 알고리즘: 두 단계의 춤

K-means는 좌표 강하법(Coordinate Descent)의 일종으로, 두 단계를 반복하여 목적 함수 $J$를 점진적으로 줄여나갑니다.

1. (A-Step) 할당 (Assignment)$$ z_i \leftarrow \arg\min_{k \in \{1, \dots, K\}} \|x_i - \mu_k\|^2 $$직관: 학생들이 여러 교실 중 가장 가까운 교실로 들어가는 과정입니다.
2. 먼저, 각 군집의 중심 $\mu_k$들이 고정되어 있다고 가정합니다. 이때 각 데이터 포인트 $x_i$는 어떤 군집에 속해야 WCSS가 최소화될까요? 당연히 자신과 가장 가까운 중심을 가진 군집에 속해야 합니다.
3. (U-Step) 업데이트 (Update)$$ \mu_k \leftarrow \frac{1}{|C_k|} \sum_{i \in C_k} x_i $$(여기서 $C_k$는 $k$번째 군집에 속한 데이터들의 집합, $|C_k|$는 그 개수입니다.)
4. 직관: 각 교실의 선생님이 자기 반 학생들의 평균 위치로 자리를 옮기는 과정입니다.
5. 이제 각 데이터의 소속 $z_i$가 고정되었다고 가정합니다. $k$번째 군집에 속한 데이터들이 정해졌을 때, 이 군집의 중심 $\mu_k$는 어디에 위치해야 이 데이터들과의 거리 제곱합이 최소가 될까요? 그 답은 바로 해당 군집에 속한 데이터들의 산술 평균입니다.

이 두 단계를 반복하면 목적 함수 $J$는 절대 증가하지 않음이 보장되며, 더 이상 군집의 변화가 없을 때(지역 최적해) 수렴하게 됩니다. 초기 중심 위치에 따라 결과가 달라지므로, 여러 번 실행하거나 k-means++와 같은 똑똑한 초기화 기법을 사용하는 것이 일반적입니다.

---

2. K-최근접 이웃 (K-NN): 이웃을 보고 예측하기 (지도 학습)

이제 완전히 다른 세상인 K-NN으로 넘어가 보겠습니다. K-NN은 지도 학습(Supervised Learning) 알고리즘으로, 분류(Classification)나 회귀(Regression) 문제에 사용됩니다. 즉, K-NN은 이미 정답(label)이 있는 데이터 $(x_i, y_i)$를 가지고 학습합니다.
K-NN의 핵심 아이디어는 "끼리끼리 모인다(Birds of a feather flock together)"는 속담과 같습니다. 새로운 데이터 포인트가 주어지면, 기존 데이터 중에서 가장 가까운 K개의 이웃을 찾고, 그 이웃들의 정보를 바탕으로 새로운 데이터의 값을 예측합니다.

2-1. K-NN의 목적: 예측을 위한 지역적 최적화

K-means와 달리 K-NN은 전체 데이터에 대한 하나의 전역 목적 함수를 최적화하지 않습니다. 대신, 새로운 쿼리 데이터 $x$가 들어올 때마다 그 주변의 지역적인(local) 문제를 풉니다.
이러한 접근법을 경험적 위험 최소화(Empirical Risk Minimization, ERM) 관점에서 설명할 수 있습니다. ERM은 주어진 데이터에서 손실(loss)의 평균을 최소화하는 모델을 찾는 원리입니다. K-NN은 이 원리를 전체 데이터가 아닌, K개의 최근접 이웃이라는 작은 부분집합에 대해서만 적용합니다.

2-2. K-NN의 목적 함수 (쿼리별 지역 ERM)

새로운 쿼리 $x$에 대한 예측값 $\hat{y}$을 찾기 위해, K-NN은 다음 목적 함수를 풉니다.

(A) 분류 (Classification)

분류 문제에서 손실은 보통 '틀리면 1, 맞으면 0'인 0-1 손실을 사용합니다. K-NN은 K개의 이웃 내에서 이 0-1 손실을 최소화하는 클래스 $y$를 찾습니다.
$$ \hat{y}(x) = \arg\min_{y \in \mathcal{Y}} \sum_{i \in \mathcal{N}_K(x)} \mathbf{1}\{y_i \neq y\} $$

• $\mathcal{N}_K(x)$: $x$의 K-최근접 이웃 데이터들의 인덱스 집합.
• $\mathcal{Y}$: 가능한 모든 클래스(레이블)의 집합.
• $\mathbf{1}\{\cdot\}$: 지시 함수 (indicator function). 조건이 참이면 1, 거짓이면 0.

위 식은 "이웃들의 레이블과 다른 예측 $y$의 개수를 최소화하라"는 의미이며, 이는 결국 "이웃들 사이에서 가장 많은 표를 얻는 클래스를 선택하라"는 다수결(majority vote)과 정확히 동일한 문제입니다.
$$ \hat{y}(x) = \arg\max_{y \in \mathcal{Y}} \sum_{i \in \mathcal{N}_K(x)} \mathbf{1}\{y_i = y\} $$

(B) 회귀 (Regression)

회귀 문제에서는 보통 제곱 오차 손실(squared error loss)을 사용합니다. K-NN은 K개의 이웃 내에서 이 제곱 오차를 최소화하는 값 $c$를 찾습니다.
$$ \hat{f}(x) = \arg\min_{c \in \mathbb{R}} \sum_{i \in \mathcal{N}_K(x)} (y_i - c)^2 $$
이 식을 $c$에 대해 미분하여 0으로 두면, 그 해는 놀랍게도 이웃들의 $y_i$ 값들의 산술 평균이 됩니다.
$$ \hat{f}(x) = \frac{1}{K} \sum_{i \in \mathcal{N}_K(x)} y_i $$

---

3. 최종 비교: K-means vs. K-NN, 절대 헷갈리지 말자!

구분	K-means (클러스터링)	K-NN (분류/회귀)
학습 유형	비지도 학습 (정답 레이블 없음)	지도 학습 (정답 레이블 필요)
"K"의 의미	찾고자 하는 군집의 개수	참조할 이웃의 개수
목표	데이터의 숨겨진 구조(군집)를 발견	새로운 데이터의 값을 예측
목적 함수	전역적(Global) WCSS 최소화	지역적(Local) 경험적 위험 최소화
알고리즘 출력물	각 데이터의 군집 번호, 군집의 중심	새로운 데이터에 대한 예측값(레이블)
학습 과정	중심을 반복적으로 업데이트하는 '학습' 과정이 있음	단순히 데이터를 저장. '게으른 학습자(Lazy Learner)'