KNN 거리 측도와 차원 저주를 다루는 방법

예측 시점에 비용이 발생하는 KNN

KNN(k-Nearest Neighbors)은 학습 단계에서 파라미터를 추정하는 대신 데이터를 저장해 두었다가, 예측 요청이 들어오면 쿼리 샘플과 학습 샘플 사이의 거리를 계산한다. 가장 가까운 k개 이웃의 레이블을 집계해 분류 결과를 만들고, 회귀에서는 값의 평균 또는 가중평균을 산출한다.

비모수적·지연 학습(Lazy learning) 모델이므로 새 데이터를 추가했을 때 즉시 적응할 수 있다. 반면 쿼리마다 탐색 비용이 발생한다. 학습 복잡도는 O(N) 저장이고, 브루트포스 예측 복잡도는 O(Nd)다. 메모리 역시 O(Nd)가 필요하다.

d가 낮으면 KD-Tree나 Ball-Tree로 평균 O(log N) 탐색을 기대할 수 있지만, 차원이 커질수록 트리의 이점은 약해진다. KNN을 운영할 때 전처리, 차원 축소, 인덱싱 전략이 함께 필요한 이유다.

거리와 이웃 집계가 결과를 바꾼다

유클리드 거리(L2)는 연속형 변수와 등방성 공간에서 대각선 방향의 차이를 반영하는 데 적합하다. 다만 피처 스케일에 민감하므로 표준화나 정규화가 필요하다.

맨해튼 거리(L1)는 절대 차이의 합으로 계산한다. 경로 비용처럼 해석하기 쉽고, 이상치에 상대적으로 강건하다. 희소 벡터나 카운트 기반 피처처럼 격자형 특성을 가진 데이터에도 적합하다.

범주형 변수가 섞여 있다면 원-핫 인코딩 뒤 L1/L2 거리를 적용하거나 Gower 거리 같은 대안을 검토할 수 있다. 이질적인 스케일이 공존하면 피처 스케일링과 가중 거리(metric learning)를 함께 고려한다.

k가 작으면 분산이 커져 과적합 위험이 높아지고, k가 커지면 편향이 커지면서 경계가 부드러워진다. 이진 분류에서는 동수를 피하기 위해 홀수 k를 권장하며, 최종 k는 교차검증으로 탐색한다. 이웃은 균등 가중(uniform)으로 집계하거나 거리 가중(distance)을 줄 수 있다. 노이즈에 민감한 경우와 경계 근처에서는 거리 가중이 유리할 수 있다. 동률이 생길 때는 가중합 비교, 사전 확률, 소수 클래스 우대 같은 규칙을 미리 정해야 한다.

유클리드와 맨해튼 거리의 선택 기준

관점	Euclidean(L2)	Manhattan(L1)
성능	연속형·등방성 데이터에서 높은 정확도 경향	희소·격자형·이상치 포함 데이터에서 안정적 성능
확장성	KD-Tree에 우호적(저차원)	트리 이점 제한적이나 L1 거리 계산 비용 단순
일관성	스케일·상관관계에 민감, 표준화 필요성 큼	이상치 영향 상대적 완화, 절대차 기반 일관성
안정성	노이즈에 취약, 거리 집중 심화 가능	경계 완만, 로버스트 회귀·분류 경향
운영 편의	광범위 도구 지원, 직관적 해석 용이	대안적 선택지로 튜닝 폭 확대, 혼합형 변수와 결합 용이

고차원에서는 탐색 방식부터 다시 본다

저차원에서는 KD-Tree가 효과적일 수 있다. 대략 d ≤ 20에서는 KD-Tree나 Ball-Tree를 고려할 수 있으며, Ball-Tree는 비등방 또는 비균질 데이터에서 유리한 경우가 있다. d가 커지면 브루트포스 탐색이 오히려 일관된 성능을 제공할 수 있다.

고차원에서는 최근접 샘플과 원격 샘플의 거리 차이가 줄어드는 거리 집중 현상이 나타난다. 이 차원 저주는 트리 인덱스 효율도 떨어뜨린다. 피처 선택(L1 규제, mRMR), 차원 축소(PCA), 메트릭 러닝(LMNN, NCA)이 대응 수단이 된다. 문서나 이미지를 임베딩 벡터로 전환할 때도 임베딩 차원 최적화와 정규화가 필요하다.

대규모 또는 고차원 탐색에는 HNSW, FAISS, Annoy 같은 근사 최근접 탐색(ANN)을 사용할 수 있다. 이 방식은 지연을 낮추는 대신 재현율과 지연 사이의 교환관계를 가진다. 오프라인 인덱스 빌드와 주기적 리빌드 전략도 운영 범위에 포함된다.

입력부터 검증까지의 처리 흐름

입력에는 원시 데이터, 스키마와 형 변환 규칙, 성능 요구사항(QPS/지연), k와 metric 후보가 포함된다. 결측 보간, 스케일링·정규화, 이상치 완화를 거친 뒤 PCA 또는 규제 기반 선택으로 차원을 다룬다. 인덱스는 d ≤ 20이면 KD/Ball-Tree를, d > 20이면 브루트포스 또는 ANN을 고려한다.

탐색 결과는 거리 계산, k 이웃 선택, 필요 시 거리 가중 집계로 이어진다. 검증 단계에서는 교차검증으로 k, metric, 가중 방식, 인덱스 파라미터를 조정한다. 출력은 예측 결과뿐 아니라 근거 이웃 목록, 거리 분포, 정확도·MAE·지연·메모리 같은 성능 지표까지 포함할 수 있다. 동률은 사전 규칙으로 처리하고, 결측 입력은 사전 보간 또는 거부하며, 시간 초과 시 ANN으로 폴백한다.

⤢✕

근접 탐색이 쓰이는 장면

임베딩 공간의 문서·이미지·상품 검색에서는 최근접 이웃을 이용해 유사 항목을 찾고, ANN 인덱스와 결합해 실시간 추천을 구현할 수 있다.

이상치 탐지에서는 k-거리 기반 임계치로 외란을 식별하고, 제조 또는 거래 로그에서 국소 밀도가 낮은 지점을 판별한다. 신규 고객을 최근 이웃 그룹의 행동 패턴에 매핑해 콜드스타트를 완화하는 방식도 가능하다. 센서 피처의 근접 유사도는 결함 판정과 잔여수명 추정에도 활용된다.

실행 가능한 파이프라인 예제

사전 조건: Python 3.10+, scikit-learn 1.4+, numpy 1.26+

# pip install scikit-learn==1.4.2 numpy==1.26.4
from sklearn.datasets import make_classification
from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, classification_report
import numpy as np

# 1) 데이터 생성
X, y = make_classification(n_samples=5000, n_features=50, n_informative=10,
                           n_redundant=10, n_classes=3, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42, stratify=y)

# 2) 파이프라인: 스케일링 → (옵션) PCA → KNN
pipe = Pipeline(steps=[
    ("scaler", StandardScaler()),
    ("pca", PCA(n_components=0.95, svd_solver="full")),  # 분산 95% 유지
    ("knn", KNeighborsClassifier(algorithm="auto"))
])

# 3) 하이퍼파라미터 그리드
param_grid = {
    "pca__n_components": [0.90, 0.95, 0.99],
    "knn__n_neighbors": [3, 5, 9, 15],
    "knn__metric": ["euclidean", "manhattan"],
    "knn__weights": ["uniform", "distance"]
}

cv = GridSearchCV(pipe, param_grid, cv=3, n_jobs=-1, scoring="accuracy", verbose=0)
cv.fit(X_train, y_train)

print("Best params:", cv.best_params_)
y_pred = cv.predict(X_test)
print("Accuracy:", accuracy_score(y_test, y_pred))
print(classification_report(y_test, y_pred))

이진 분류는 홀수 k를 우선 검토한다. 클래스 불균형이 있으면 weights="distance"+class_weight 보완과 전처리 단계의 샘플 가중 적용을 고려할 수 있다. 대규모 검색은 HNSW/FAISS로 임베딩 인덱스를 운영하고, 재순위화 단계에서 정확 KNN을 다시 계산하는 구성이 가능하다.

모델 단순성과 탐색 비용의 균형

브루트포스 예측은 O(Nd)이며, KD/Ball-Tree는 저차원에서 평균적으로 O(log N) 탐색을 기대할 수 있다. ANN은 서브선형 탐색과 지연 감소를 목표로 하지만 재현율과 지연의 교환관계를 가진다. 메모리는 O(Nd)가 필요하고, 차원 축소로 선형 비율로 절감할 수 있다.

KNN은 근거 이웃을 함께 제시해 국소적인 설명을 제공한다. 별도의 파라미터 학습 없이 데이터를 교체해 빠르게 업데이트할 수 있으며, 거리·k·전처리 조합을 통해 다양한 데이터 분포에 대응할 수 있다. 소규모~중간 규모 데이터, 임베딩 기반 유사도 검색, 국소적 설명이 필요한 과제에서 우선 검토할 만하다. 고차원·대규모 실시간 요구에서는 차원 축소와 ANN을 결합해 운영한다.