KNN (K-Nearest Neighbor)

머신러닝 지도학습에서 사용되는 가장 간단하고 직관적인 분류 및 회귀 방법 중 하나인 KNN 방법에 대한 정리

KNN (K-Nearest Neighbors) 개요

• K-최근접 이웃(KNN, K-Nearest Neighbors)은 지도학습(Supervised Learning)에서 자주 사용되는 간단하지만 강력한 분류(Classification) 및 회귀(Regression) 알고리즘으로, 학습 과정이 거의 없고, 예측 시점에 계산이 이루어지는 Lazy Learning 방식의 대표적인 예이다.
• 아이디어: 새로운 데이터 포인트가 주어졌을 때, 학습 데이터 중 가장 가까운 K개의 이웃을 찾고, 이웃들의 레이블을 바탕으로 예측을 수행한다.
• 용도: 분류(Classification), 회귀(Regression), 이상치 탐지 등

---

KNN 방법

1. 거리 측정

• 데이터 간 거리(유사성)를 계산하기 위해 다양한 거리 함수가 사용되며, 대표적으로 유클리드 거리(Euclidean Distance) 가 있다.

$$\text{두 벡터}\mathbf{x}=(x_1,x_2,\dots ,x_n),\mathbf{y}=(y_1,y_2,\dots ,y_n)\text{간의 거리}:$$ $$\begin{array}{rl}& \\ & \text{Euclidean distance: }\\ & d(\mathbf{x},\mathbf{y})=\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2}\\ & \\ & \\ & \text{Manhattan distance: }\\ & d(\mathbf{x},\mathbf{y})=\sum _{i=1}^n|x_i-y_i|\\ & \\ & \\ & \text{Monkowski distance: }\\ & d(\mathbf{x},\mathbf{y})={\left(\sum _{i=1}^n|x_i-y_i{|}^p\right)}^{1/p}\\ & \end{array}$$

2. 분류(Classification)에서의 KNN

• 분류 문제에서 KNN 알고리즘은 새로운 샘플 $\mathbf{x}$ 에 대해 다음과 같이 동작한다:
  1. 모든 학습 샘플 ${\mathbf{x}}^{(i)}$와의 거리를 계산한다.
  2. 가장 가까운 $K$ 개의 샘플을 선택한다.
  3. 클래스 레이블을 확인하여 다수결(Voting) 로 최종 클래스를 결정한다.

3. 회귀(Regression)에서의 KNN

• 회귀 문제에서 KNN 알고리즘은 $K$ 개의 이웃 샘플의 타겟 값 평균으로 예측 값을 계산한다.

$$\hat{y}=\frac{1}{K}\sum _{i\in {\mathcal{N}}_K(\mathbf{x})}{y}^{(i)}$$

4. KNN 하이퍼파라미터

• K (이웃 수): 작을수록 민감, 클수록 부드러운 결정 경계
• 거리 척도: 유클리드, 맨해튼 등
• 가중치(필요시):
  • 균등 가중치: 모든 이웃이 동일한 영향
  • 거리 가중치: 가까운 이웃에 더 큰 가중치를 부여

---

KNN 장단점

장점	단점
- 구현이 간단함 - 비선형 데이터에도 잘 작동 - 학습 과정이 필요 없음	- 예측 시 계산량이 큼 (메모리 요구량 큼) - 고차원 데이터에서 성능 저하 (차원의 저주) - 이상치에 민감하고 적절한 $K$ 선택 필요

---

KNN 사용 시 고려해야할 점

• 데이터 정규화: 서로 다른 범위의 데이터가 공존할 경우 거리 측정이 의미를 가지지 못하므로, 공평한 거리 측정을 위해 모든 데이터를 특정 범위내로 정규화가 필요함.
• 홀수 K: 분류 문제에서 $K$ 개 샘플을 이용해 다수결로 레이블 선택 시, 짝수개의 경우 동점 상황이 발생함. 이를 방지하고자 $K$는 홀수로 지정하는 것을 추천함.

---

Python 예시 코드

• Scikit-learn 을 이용한 KNN 실습 코드

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
 
# 데이터셋 불러오기
X, y = load_iris(return_X_y=True)
 
# 학습/테스트 분할
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
 
# KNN 모델 학습
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train, y_train) 
# 실제로 학습하는 것이 아닌, 입력으로 주어진 X_train(특징벡터)와 Y_train(정답레이블)을
# 내부에 저장함. 이후 예측 단계에서 저장된 데이터를 이용함.
 
# 예측 및 정확도 평가
y_pred = knn.predict(X_test)
print("Accuracy:", accuracy_score(y_test, y_pred))

---

참고

• k-nearest neighbors algorithm - Wikipedia
• [머신러닝] K-최근접 이웃(K-NN) 알고리즘 및 실습