K-Nearest Neighbors (KNN)

K-최근접 이웃(KNN)은 새 사례에서 가장 가까운 k개의 레이블 지정 사례를 바탕으로 레이블을 예측하는 지도 학습 알고리즘입니다. 분류에서는 이웃들의 다수결을 사용하고, 회귀에서는 이웃 값의 평균을 사용합니다. KNN은 비모수적이고 "게으른" 알고리즘입니다. 가중치를 학습하지 않고 학습 데이터를 저장하기만 하며, 예측을 요청받을 때 모든 작업을 수행합니다. Evelyn Fix와 Joseph Hodges가 1951년에 이 방법을 소개했고, 1967년 Thomas Cover와 Peter Hart는 데이터가 무한히 주어질 때 최근접 이웃 규칙의 오차율이 최적 분류기의 오차율의 두 배를 넘지 않는다는 것을 증명했습니다. 동일한 최근접 이웃 검색은 이제 벡터 데이터베이스와 신경망의 임베딩을 비교하는 이미지 검색 시스템에서 대규모로 실행됩니다.

KNN의 예측 방식#

KNN은 각 쿼리 포인트마다 세 단계를 수행합니다.

1. 거리 측정: 쿼리와 저장된 모든 사례 간의 거리를 계산합니다. 기본값은 유클리드 거리이며, 맨해튼 거리와 민코프스키 거리가 일반적인 대안입니다. 벡터의 방향에 의미가 담긴 임베딩에는 코사인 유사도가 표준적으로 사용됩니다.
2. 이웃 선택: 거리가 가장 작은 k개의 사례를 선택합니다.
3. 레이블 결합: 분류에서는 이웃 중 가장 많이 나타나는 클래스를 선택하고, 회귀에서는 이웃 값의 평균을 사용합니다. 거리 가중치(scikit-learn의 weights="distance")를 적용하면 가까운 이웃에 더 큰 비중을 둡니다.

모든 특성이 거리에 영향을 미치므로 규모가 큰 특성이 지배적입니다. 예를 들어 달러 단위 소득은 연 단위 나이를 압도할 수 있습니다. 따라서 KNN 파이프라인은 먼저 특성을 표준화하거나 특성 추출 모델의 임베딩을 비교하여 각 차원이 비슷한 규모로 기여하도록 합니다.

k 선택#

k 값은 과적합과 과소적합 사이의 균형을 결정합니다. k = 1이면 노이즈가 있거나 레이블이 잘못된 포인트를 포함해 모든 학습 포인트가 자체 영역을 차지하여 결정 경계가 들쭉날쭉해집니다. k가 매우 크면 각 투표가 쿼리에서 멀리 떨어진 곳까지 영향을 미쳐 실제 클래스 경계가 흐려집니다. 클래스가 두 개일 때는 홀수 k를 사용하면 동률 투표를 피할 수 있으며, k를 선택하는 표준적인 방법은 교차 검증입니다. scikit-learn의 노이즈가 있는 two-moons 데이터셋에서는 다음 세 값으로 이러한 절충 관계를 확인할 수 있습니다.

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

k = 1이면 분류기가 학습 포인트를 그대로 기억하여 해당 포인트에서는 1.00, 홀드아웃 포인트에서는 0.83의 점수를 얻습니다. k = 15일 때는 각각 0.90과 0.89로, 세 경우 중 테스트 결과가 가장 좋습니다. 학습 포인트 700개 중 거의 절반에 해당하는 k = 300을 사용하면 경계가 지나치게 평활화되어 두 점수가 모두 0.84와 0.81로 떨어집니다.

이웃 검색 속도 향상#

브루트포스 검색은 d차원에 저장된 n개의 모든 포인트와 쿼리를 비교하므로 예측마다 드는 비용은 대략 n × d 연산에 비례하고, 데이터셋이 커질수록 메모리 사용량도 증가합니다. k-d 트리와 볼 트리 같은 공간 분할 구조는 저차원에서 대부분의 비교를 건너뛰며, scikit-learn의 algorithm="auto"는 브루트포스, k-d 트리, 볼 트리 중 하나를 선택합니다. 고차원에서는 차원의 저주로 인해 포인트 간 거리가 거의 같아지고 트리 가지치기의 이점이 사라집니다. 이에 따라 대규모 시스템은 HNSW 그래프와 곱 양자화를 적용한 역파일(IVF) 인덱스 같은 근사 최근접 이웃(ANN) 인덱스로 전환하며, 이러한 인덱스는 FAISS 같은 라이브러리에서 구현됩니다. 이러한 인덱스는 쿼리와 저장된 벡터 중 일부만 비교하면서 실제 최근접 이웃 대부분을 반환합니다.

KNN과 관련 방법 비교#

• K-means 클러스터링: 레이블이 없는 포인트를 학습된 중심점 주변의 k개 클러스터로 그룹화하는 비지도 학습 알고리즘입니다. 이름에 같은 문자가 들어가는 것은 우연입니다. k-means에서 k는 클러스터 수를 나타냅니다.
• 벡터 검색: 동일한 연산을 검색에 적용한 형태입니다. 일반적으로 근사 인덱스를 사용해 쿼리 임베딩과 가장 가까운 저장 항목을 반환하며, 애플리케이션은 해당 항목을 직접 사용합니다.
• 서포트 벡터 머신과 로지스틱 회귀: 학습 중 결정 경계를 학습하는 파라미터 기반 모델이므로, 학습 세트가 커져도 예측 비용은 일정하게 유지됩니다.

실제 적용 사례#

• 추천 시스템: 항목 기반 협업 필터링은 사용자가 이미 선호한 항목과 평점 벡터 또는 구매 벡터가 가장 가까운 제품을 추천합니다.
• 이상 탐지: 포인트와 k번째 최근접 이웃 간의 거리를 이상 점수로 사용하므로, 정상 사례와 거리가 먼 거래나 센서 측정값을 식별할 수 있습니다.
• 결측값 대치: scikit-learn의 KNNImputer은 가장 유사한 k개 행에서 해당 특성의 평균을 구해 각 결측값을 채웁니다.
• 이미지 검색 및 재식별: 시스템은 이미지의 임베딩을 갤러리와 비교하여 다른 카메라에 포착된 동일한 제품, 얼굴 또는 사람을 찾습니다. Ultralytics의 유사도 검색 솔루션은 OpenAI의 CLIP을 사용해 이미지 폴더를 임베딩하고, "red car"와 같은 텍스트 쿼리를 모든 인덱스 이미지와 정확한 브루트포스 검색 방식의 코사인 유사도로 비교한 뒤 기본적으로 최대 30개의 최근접 이미지를 반환합니다.