K-최근접 이웃

k-최근접 이웃(KNN) 알고리즘은 머신러닝에서 분류 및 회귀 작업에 사용되는 비모수적 지도 학습 알고리즘입니다. 이 알고리즘은 근접성의 개념에 기반하여, 유사한 데이터 포인트가 서로 가까이 위치한다는 가정을 합니다. KNN은 게으른 학습(lazy learning) 알고리즘으로, 별도의 학습 단계가 필요 없으며 전체 학습 데이터를 저장한 뒤, 새로운 데이터 포인트의 클래스나 값을 결정할 때 이를 활용하여 예측을 수행합니다. 알고리즘은 테스트 데이터 포인트에 대해 가장 가까운 ‘k’개의 학습 데이터 포인트를 찾아, 이 이웃들을 기반으로 결과를 추론합니다. 이 방식은 새로운 데이터를 기존의 예시와 비교해 인식하는 인간의 인지 전략과 유사하여 직관적입니다.

KNN의 작동 원리

KNN은 쿼리 포인트와 가장 가까운 ‘k’개의 데이터 포인트를 식별하고, 이 이웃들을 활용해 예측을 수행합니다.

• 분류 작업에서는, 알고리즘이 쿼리 포인트를 ‘k’개의 최근접 이웃 중 가장 많이 속하는 클래스(다수결)에 할당합니다. 다수결은 여러 클래스가 있을 때 “최다 득표(plurality voting)”로 이해할 수 있으며, 절대 다수가 아니더라도 가장 많은 이웃의 클래스로 할당됩니다.
• 회귀 작업에서는, ‘k’개의 최근접 이웃의 값을 평균 내어 예측값으로 사용합니다.

근접성과 유사성의 원리는 인간의 인지에도 핵심적인데, KNN 역시 특성 공간 상에서 가까운 데이터가 더 유사하다고 가정하여 동작합니다.

거리 측정 방법

가장 가까운 이웃을 결정하기 위해 KNN은 여러 거리 측정 방법을 사용하며, 이는 알고리즘 성능에 매우 중요합니다.

• 유클리드 거리: 다차원 공간에서 두 점 사이의 직선 거리를 의미하며, 연속형 변수에 흔히 사용됩니다. KNN에서 가장 널리 쓰이는 거리로, 데이터가 조밀하고 연속적일 때 특히 유용합니다.
• 맨해튼 거리: 택시 거리라고도 불리며, 두 점의 각 좌표 간 절대값 차이의 합으로 계산합니다. 격자형 경로 등 이동이 수직·수평으로 제한되는 경우에 유용합니다.
• 민코프스키 거리: 유클리드 및 맨해튼 거리의 일반화 형태로, 파라미터 ‘p’에 따라 달라집니다. p=1이면 맨해튼, p=2이면 유클리드 거리가 되어, 데이터 특성에 맞게 유연하게 적용할 수 있습니다.
• 해밍 거리: 범주형 데이터에 주로 사용되며, 두 이진 벡터 간 상이한 비트의 개수를 셉니다. 속성이 이진값일 때 특히 유용한 거리 측정법입니다.

적절한 ‘k’ 값 선택하기

KNN에서 ‘k’는 고려할 이웃의 수를 나타냅니다. 올바른 ‘k’ 선택은 매우 중요합니다.

• 작은 ‘k’는 모델이 학습 데이터의 잡음에 민감해져 과적합이 발생할 수 있습니다.
• 큰 ‘k’는 모델이 너무 일반화되어 중요한 패턴을 놓쳐 과소적합이 발생할 수 있습니다.
• 일반적으로 ‘k’는 교차 검증을 통해 경험적으로 결정하며, 분류의 경우 동점을 피하기 위해 홀수로 설정하는 것이 좋습니다. ‘k’ 값의 선택은 모델의 정확도에 큰 영향을 미치므로 신중히 결정해야 합니다.

장점과 단점

장점

• 단순하고 직관적임: 이해 및 구현이 쉬워 초보자에게 적합합니다. 테스트 인스턴스를 저장된 예시와 비교하는 간단한 접근 방식이 KNN의 가장 큰 강점입니다.
• 학습 단계 불필요: 별도의 학습 과정 없이 데이터셋을 저장하여 바로 예측에 활용할 수 있습니다. 데이터셋에 새로운 데이터 추가만으로 즉시 모델을 업데이트할 수 있습니다.
• 다양한 적용 가능성: 분류와 회귀 모두에 사용할 수 있으며, 다양한 분야에서 폭넓게 활용됩니다. 다중 레이블 분류 등에도 유용합니다.

단점

• 계산 비용이 큼: 새로운 데이터 포인트와 전체 데이터셋을 비교해야 하므로, 특히 대용량 데이터에서는 느리고 자원 소모가 큽니다. KNN의 시간 복잡도는 O(n)으로, n은 학습 샘플의 수를 의미합니다.
• 이상치에 민감함: 이상치 데이터가 예측에 큰 영향을 줄 수 있으며, 특히 ‘k’가 작을 때 결과가 왜곡될 수 있습니다.
• 차원의 저주: 고차원 공간에서는 데이터 포인트 간 거리가 덜 의미 있어져 알고리즘의 성능이 저하됩니다. 차원이 증가할수록 데이터가 희소해져, KNN이 이웃을 효과적으로 찾기 어려워집니다.

활용 사례

KNN은 단순성과 효과성 덕분에 다양한 분야에 활용됩니다.

• 추천 시스템: 유사한 사용자의 선호도를 기반으로 상품이나 콘텐츠를 추천하는 데 사용됩니다. 특징의 유사성을 평가해 비슷한 사용자나 아이템을 식별할 수 있습니다.
• 패턴 인식: 필기체 인식 등 이미지의 픽셀 값 유사성에 따라 분류를 수행하는 패턴 인식 작업에 사용됩니다.
• 데이터 결측값 보정: 유사한 데이터 포인트를 기반으로 결측값을 추정해 데이터셋의 완전성을 유지할 수 있습니다.
• 금융 및 헬스케어: 과거 데이터의 유사성을 분석하여 주식 시장 예측, 위험 평가, 의료 진단 등에 활용됩니다. 예를 들어, 환자 증상을 기존 사례와 비교해 진단을 예측할 수 있습니다.

파이썬에서의 구현

KNN은 파이썬의 scikit-learn 등 라이브러리를 통해 쉽게 구현할 수 있습니다. 아래는 분류 작업에서 KNN을 사용하는 기본 예시입니다.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score

# 데이터셋 불러오기
iris = load_iris()
X, y = iris.data, iris.target

# 학습/테스트 데이터 분할
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# k=3으로 KNN 분류기 초기화
knn = KNeighborsClassifier(n_neighbors=3)

# 모델 학습
knn.fit(X_train, y_train)

# 예측 수행
y_pred = knn.predict(X_test)

# 정확도 평가
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

과학 연구에서의 K-최근접 이웃(KNN)

K-최근접 이웃(KNN)은 멀티미디어 정보 검색, 데이터 마이닝, 머신러닝 등 다양한 분야에서, 특히 대용량 데이터셋을 다루는 맥락에서 널리 사용되는 기본 알고리즘입니다.

주요 연구 논문

• “Approximate k-NN Graph Construction: a Generic Online Approach” (Wan-Lei Zhao 외):
  근사 k-최근접 이웃 검색과 그래프 구축을 위한 효과적인 방법을 제시합니다. 이 논문은 다양한 데이터 규모와 차원에서 동적으로 적용 가능한 현실적 솔루션을 보여주며, 기존 방법에서는 불가능했던 온라인 업데이트를 지원합니다. 더 읽기.

• “Parallel Nearest Neighbors in Low Dimensions with Batch Updates” (Magdalen Dobson, Guy Blelloch):
  kd-트리와 모턴 순서를 결합한 zd-트리 구조 기반의 병렬 알고리즘을 제안하며, 저차원 데이터에 최적화되어 있습니다. 저자는 병렬 처리를 통해 기존 알고리즘 대비 상당한 속도 향상을 증명했으며, zd-트리는 k-최근접 이웃 데이터 구조 중 최초로 병렬 배치-동적 업데이트를 지원합니다. 더 읽기.

• “Twin Neural Network Improved k-Nearest Neighbor Regression” (Sebastian J. Wetzel):
  쌍둥이 신경망(twin neural networks)을 활용한 새로운 k-최근접 이웃 회귀 방법을 제시합니다. 이 방식은 회귀 타깃 간의 차이에 대한 예측에 초점을 맞추어, 소형 및 중형 데이터셋에서 기존 신경망 및 k-최근접 이웃 회귀보다 뛰어난 성능을 보였습니다. 더 읽기.