개념
훈련 데이터를 저장해두고 새로운 데이터가 들어왔을 때 가장 가까운 k개의 이웃을 참조하여 분류 또는 예측하는 알고리즘이다.
새로운 데이터에 대한 예측은 다수결(classification) 혹은 평균(regression)으로 결정된다.
과정
k-NN은 학습 과정이 따로 없이 예측 시점에 계산을 수행한다.
예측 과정
- 새로운 샘플에 대해 모든 학습 데이터와의 거리 계산
- 가장 가까운 K개 이웃 선택
- 분류 문제인 경우:
- K개의 클래스 중에서 다수결로 클래스 결정
- 회귀 문제인 경우:
- K개의 타깃 값의 평균/중앙값으로 예측
하이퍼파라미터(K)의 선택 방법
k=1 이면 노이즈에 취약하다. k가 증가할수록 부드러워지지만, 너무 크면 과소적합이 발생한다. 보통 동점 방지를 위해 (3,5,7)등 홀수를 사용하며 교차 검증으로 k를 선택한다.
거리 측정 방법
1. Euclidean Distance (유클리드 거리)
가장 일반적으로 사용되는 거리 척도이다. 두 점 간의 직선 거리를 계산한다.
2. Manhattan Distance (맨하탄 거리)
각 차원별 거리의 절댓값 합을 계산한다.
3. Minkowski Distance (민코프스키 거리)
유클리드 거리와 맨하탄 거리의 일반화된 형태이다. p값에 따라 거리 방식이 달라진다.
4. Cosine Similarity (코사인 유사도)
두 벡터 간 방향을 기준으로 유사도를 측정한다.
장단점 및 성능향상 기법
k-NN은 이해 및 구현이 쉽고 분류,회귀 모두 사용이 가능하다. 대신 모든 점과 거리를 계산하기 때문에 계산량이 크고 outlier의 영향을 받으며 고차원에서 성능이 떨어진다.
성능 향상을 위한 기법으로 자주 쓰이는 몇 가지를 알아보자
| 표준화 / 정규화 | 각 피처의 스케일을 맞춰야 거리 계산이 왜곡되지 않음 |
| 가중치 부여 (가까운 이웃에) | 가까운 이웃에 더 높은 영향력 부여 |
| KD-Tree, Ball-Tree | 거리 계산 최적화를 위한 데이터 구조 (고속 검색용) |
| 차원 축소 (PCA) | 고차원 → 저차원 투영하여 성능 향상 |
KNN 구현
height=161cm이고 weight=61kg인 사람의 T-shirt size 예측해보기
import pandas as pd
import numpy as np
# T-shirt dataset
data = {
"Height": [158, 158, 158, 160, 160, 163, 163, 160, 163, 165, 165, 165, 168, 168, 168, 170, 170],
"Weight": [58, 59, 63, 59, 60, 60, 61, 64, 64, 61, 62, 65, 62, 63, 66, 63, 64],
"T-Shirt Size": ["M", "M", "M", "M", "M", "M", "M", "L", "L", "L", "L", "L", "L", "L", "L", "L", "L"]
}
df = pd.DataFrame(data)
# New customer's height and weight
new_customer = np.array([161, 61])
# Compute Euclidean distance between new_customer and each row in df
df["Distance"] = np.sqrt((df["Height"] - new_customer[0])**2 + (df["Weight"] - new_customer[1])**2)
# Find 3 nearest neighbors
neighbors_k3 = df.nsmallest(3, "Distance")[["Height", "Weight", "T-Shirt Size", "Distance"]]
prediction_k3 = neighbors_k3["T-Shirt Size"].mode()[0]
# Find 5 nearest neighbors
neighbors_k5 = df.nsmallest(5, "Distance")[["Height", "Weight", "T-Shirt Size", "Distance"]]
prediction_k5 = neighbors_k5["T-Shirt Size"].mode()[0]
# Print results
print("K = 3 Nearest Neighbors:")
print(neighbors_k3)
print("\n K = 5 Nearest Neighbors:")
print(neighbors_k5)
print("\n Prediction for new customer (height=161, weight=61):")
print(" k = 3:", prediction_k3)
print(" k = 5:", prediction_k5)
