K-근접이웃(KNN) — 이웃의 다수결로 분류하고 평균으로 예측하는 법

학습 단계에서 KNN은 아무 것도 계산하지 않는다. 훈련 데이터를 그대로 저장해뒀다가, 새 데이터가 들어오는 예측 시점에야 거리 계산을 시작한다. 이 '지연 학습(Lazy Learning)' 방식과, 데이터의 분포를 가정하지 않는 비모수적(Non-parametric) 성격이 KNN을 가장 단순하면서도 여전히 쓰이는 분류·회귀 기법으로 만든다.

가장 가까운 K개가 결정한다

핵심 아이디어는 새로운 데이터 포인트를 분류할 때, 가장 가까운 K개의 이웃들의 특성을 참고해 결정하는 것이다. 이웃 간 거리는 유클리드 거리, 맨하탄 거리, 민코프스키 거리 등으로 잰다.

⤢✕

분류 문제에서는 K개의 가장 가까운 이웃들 중 가장 많은 클래스로 새 데이터를 분류하는 다수결 원칙을 쓰며, 각 클래스의 비율을 확률로 해석할 수도 있고 거리에 따라 가중치를 부여해 가까운 이웃에 더 높은 영향력을 줄 수도 있다. 회귀 문제에서는 K개 이웃의 타겟값 평균으로 새 데이터의 값을 예측하며, 거리에 반비례하는 가중 평균을 적용하면 데이터의 지역적 특성을 반영한 예측이 가능하다.

K값이 성능을 가른다

K값은 KNN 성능에 직접적인 영향을 미치는 핵심 하이퍼파라미터다.

작은 K값은 국소적 패턴에 민감하고 노이즈에 취약해 과적합(Overfitting) 위험이 커지며 결정 경계가 복잡해진다. 큰 K값은 전역적 패턴을 반영해 노이즈에 강건하지만 과소적합(Underfitting) 가능성이 생기고 결정 경계가 단순해진다.

⤢✕

최적의 K값은 교차 검증(Cross-validation)으로 찾으며, 일반적으로 훈련 데이터 크기의 제곱근을 초기값으로 시도해볼 수 있다. 분류 문제에서는 동점을 막기 위해 홀수 K값을 쓴다.

거리를 재는 여러 방법

유클리드 거리(Euclidean Distance): 가장 일반적으로 쓰이며, 공식은 √Σ(xi - yi)²다. 연속형 데이터에 적합하다.
맨하탄 거리(Manhattan Distance): 격자형 공간에서 유용하며, 공식은 Σ|xi - yi|다. 특성 간 가중치 균등화에 효과적이다.
민코프스키 거리(Minkowski Distance): 유클리드와 맨하탄 거리를 일반화한 것으로, 공식은 (Σ|xi - yi|ᵖ)^(1/p)이며 p=1이면 맨하탄, p=2이면 유클리드 거리가 된다.
코사인 유사도(Cosine Similarity): 벡터 방향의 유사성을 측정하며, 크기보다 방향을 중시해 텍스트 분석 등에 유용하다.

스케일을 맞춰야 하는 이유

KNN은 거리 기반 알고리즘이라 특성들의 스케일에 매우 민감하다. 서로 다른 단위의 특성들이 균등한 영향력을 갖도록 조정하지 않으면, 큰 범위의 특성이 작은 범위의 특성을 압도해 알고리즘 성능과 해석 가능성이 떨어진다.

⤢✕

주요 스케일링 방법으로는 평균 0·표준편차 1로 변환하는 표준화(Standardization, Z-score 변환), 0~1 범위로 변환하는 정규화(Normalization, Min-Max 스케일링), 이상치에 덜 민감한 로버스트 스케일링이 있다.

학습 없이 얻는 단순함과 그 대가

구현이 간단하고 직관적으로 이해할 수 있으며, 데이터 분포에 대한 가정이 필요 없는 비모수적 특성을 갖는다. 여러 클래스 문제를 자연스럽게 처리할 수 있고, 단순하지만 강력한 이론적 기반을 갖췄으며, 새 데이터가 추가돼도 모델을 재학습할 필요가 없다.

반면 대규모 데이터셋에서는 예측 시간이 늘어나는 계산 복잡성 문제가 있고, 고차원 데이터에서는 성능이 떨어지는 차원의 저주를 겪는다. 전체 훈련 데이터를 저장해야 하는 메모리 요구사항이 있고, 모든 특성이 동일한 중요도를 갖는다고 가정하며, 적절한 K값을 선택하기 어렵다는 한계도 있다.

차원의 저주에 대응하기

고차원 데이터에서 KNN은 심각한 성능 저하를 겪는데, 이를 '차원의 저주'라 부른다. 차원이 증가할수록 데이터 포인트 간 거리가 비슷해져 의미 있는 '근접' 개념이 희석되고, 희소 데이터 문제와 계산 복잡성 급증이 뒤따른다.

대응 방안으로는 PCA·t-SNE 등을 활용한 차원 축소, 중요 특성만 선별하는 특성 선택, 여러 하위 공간에서 KNN 모델을 구축하는 앙상블 방법, 거리 관계를 보존하는 투영 방법을 쓰는 지역성 보존 투영이 있다.

구현과 속도 최적화

기본 구현인 브루트 포스 방식은 모든 훈련 데이터와의 거리를 계산하며 O(nd) 복잡도를 갖는다. 파이썬에서는 Scikit-learn의 KNeighborsClassifier, KNeighborsRegressor를 쓰고, 하이퍼파라미터 튜닝에는 GridSearchCV를 활용한다.

속도를 높이려면 계층적 데이터 구조로 효율적으로 검색하는 볼 트리(Ball Tree), 차원별 분할로 빠르게 검색하는 KD 트리(KD Tree), 정확도를 약간 희생하고 속도를 높이는 근사 근접 이웃, 다중 코어를 활용하는 병렬 처리를 쓸 수 있다.

⤢✕

다른 알고리즘과 비교하면

선형 회귀·분류는 전역적 패턴을 학습하며 계산이 효율적인 반면, KNN은 지역적 패턴을 포착해 비선형 관계 모델링에 유리하다. 결정 경계가 복잡하고 학습 데이터가 충분할 때는 KNN이 우수하다.

결정 트리는 특성 중요도를 파악할 수 있고 해석이 쉬운 반면, KNN은 거리 개념을 반영해 연속적 예측이 가능하다. 앙상블인 랜덤 포레스트는 특성 선택과 견고성에서 종종 KNN을 능가한다.

신경망은 대규모 데이터에서 표현 학습이 가능하지만 계산 비용이 높다. KNN은 단순하게 구현할 수 있고 적은 데이터에서도 작동하며 설명이 쉽다. 딥러닝으로 특성을 추출한 뒤 KNN을 적용하는 하이브리드 접근도 쓰인다.