k-최근접 이웃(k-NN)
1. 소개
k-최근접 이웃(k-Nearest Neighbors, k-NN)은 머신러닝에서 가장 직관적이고 이해하기 쉬운 분류 및 회귀 알고리즘입니다. 새로운 데이터가 들어왔을 때, 그와 가장 가까운 k개의 기존 데이터를 찾아 다수결 또는 평균으로 결과를 예측하는 방식입니다.
PM 에게 k-NN에 대해 아는 것이 중요한 이유는 다음과 같습니다. 첫째, 알고리즘의 작동 원리가 명확해서 비즈니스 이해관계자에게 설명하기 쉽습니다. 둘째, 별도의 훈련 과정 없이 바로 사용할 수 있어 프로토타입 개발이나 PoC(Proof of Concept) 단계에서 빠르게 검증할 수 있습니다. 셋째, 추천 시스템, 이상 탐지, 이미지 인식 등 다양한 비즈니스 문제에 적용 가능합니다.
2. 핵심 개념
거리 기반 분류
k-NN의 가장 기본적인 원리는 '비슷한 것끼리 가깝다'는 가정입니다. 새로운 데이터 포인트를 분류할 때, 기존 데이터들과의 거리를 계산하여 가장 가까운 이웃들을 찾습니다. 일반적으로 유클리드 거리(직선거리)를 사용하지만, 맨해튼 거리나 코사인 유사도 등 다양한 거리 측정 방법을 선택할 수 있습니다.
k값의 중요성
k는 참고할 이웃의 개수를 의미합니다. k=1이면 가장 가까운 1개만 보고, k=5면 가장 가까운 5개를 봅니다. k값이 너무 작으면 노이즈에 민감해지고(과적합), 너무 크면 결정 경계가 지나치게 단순해집니다(과소적합). 최적의 k값은 교차 검증을 통해 찾아야 하며, 이는 프로젝트 초기 기술 검토 단계에서 반드시 고려해야 할 하이퍼파라미터입니다.
Lazy Learning
k-NN은 훈련 단계에서 모델을 생성하지 않고, 모든 훈련 데이터를 메모리에 저장만 합니다. 실제 예측이 필요한 순간에 계산을 수행하는 방식으로, 이를 게으른 학습(Lazy Learning) 또는 인스턴스 기반 학습이라고 합니다. 이는 초기 개발이 빠르다는 장점이 있지만, 예측 시 계산 비용이 높다는 단점이 있습니다.
특성 스케일링의 필수성
거리를 계산하기 때문에 각 특성(feature)의 스케일이 결과에 큰 영향을 미칩니다. 예를 들어 나이(0-100)와 연봉(2000만-2억)을 함께 사용하면, 연봉의 영향력이 압도적으로 커집니다. 따라서 정규화(Normalization) 또는 표준화(Standardization)가 필수이며, 이는 데이터 전처리 파이프라인에 반드시 포함되어야 합니다.
분류와 회귀 모두 가능
k-NN은 분류 문제에서는 k개 이웃의 다수결로, 회귀 문제에서는 k개 이웃의 평균값으로 예측합니다. 이러한 유연성 덕분에 하나의 알고리즘으로 다양한 비즈니스 문제를 해결할 수 있습니다.
3. 이미지
k-NN 알고리즘의 작동 방식을 시각적으로 이해하기 위한 참고 이미지:
Wikipedia - k-NN 분류 예시 이미지 보기이미지 설명: 테스트 샘플(녹색 원)을 분류할 때, k=3이면 빨간 삼각형 클래스로, k=5면 파란 사각형 클래스로 분류되는 것을 보여줍니다.
4. 비유
k-NN을 이해하는 가장 좋은 비유는 "새로운 동네로 이사 갔을 때 맛집 찾기"입니다.
당신이 처음 보는 동네에서 저녁을 먹으려고 합니다. 어떤 식당이 좋을지 모르는 상황에서, 당신은 '가까운' 5명의 사람들에게 물어봅니다(k=5). 3명이 A식당을 추천하고, 2명이 B식당을 추천한다면, 당신은 다수결에 따라 A식당을 선택할 것입니다.
여기서 중요한 포인트는 다음과 같습니다. 첫째, 물어보는 사람의 수(k값)가 중요합니다. 1명만 물어보면 그 사람의 개인 취향에 좌우되고, 너무 많이 물어보면 멀리 있는 사람들의 의견까지 포함되어 부정확해집니다. 둘째, '가까운 사람'의 의견이 더 중요합니다. 거리는 물리적 거리일 수도 있고, 나이, 취향, 직업 등의 유사성일 수도 있습니다. 셋째, 이미 축적된 데이터(동네 사람들의 경험)를 활용하여 새로운 결정을 내리는 것입니다.
5. 등장 배경
k-NN은 1951년 Evelyn Fix와 Joseph Hodges에 의해 처음 제안되었고, 1967년 Cover와 Hart가 이론적 기초를 확립했습니다. 당시 머신러닝 초창기에는 복잡한 수학적 모델을 구현할 컴퓨팅 자원이 부족했고, 데이터의 패턴을 어떻게 학습할지에 대한 명확한 방법론도 없었습니다.
k-NN은 이러한 한계를 극복하기 위해 등장했습니다. 복잡한 모델 학습 과정 없이, 단순히 거리를 측정하고 비교하는 것만으로도 효과적인 분류가 가능하다는 것을 보여주었습니다. 이는 "모델을 만들지 않고도 학습할 수 있다"는 비매개변수적(non-parametric) 접근법의 시작이었습니다.
현재 k-NN은 그 본래 목적을 완벽하게 달성했습니다. 간단하고 직관적이며, 특별한 가정 없이 다양한 문제에 적용 가능합니다. 다만 대용량 데이터와 실시간 처리가 필요한 현대 AI 환경에서는 속도 문제로 인해 주로 베이스라인 모델, 프로토타입, 또는 다른 알고리즘과의 앙상블 구성요소로 활용됩니다. 그럼에도 불구하고 추천 시스템의 협업 필터링, 이상 탐지 등 특정 도메인에서는 여전히 강력한 성능을 보여줍니다.
6. 활용 사례
추천 시스템
k-NN은 협업 필터링 기반 추천 시스템에서 핵심적으로 사용됩니다. 사용자 A와 유사한 취향을 가진 k명의 사용자를 찾아, 그들이 좋아한 상품을 A에게 추천하는 방식입니다. Netflix, Amazon, YouTube 등이 초기에 이 방식을 활용했으며, 현재도 딥러닝 기반 추천과 함께 하이브리드 형태로 많이 사용됩니다.
이상 탐지
금융 사기 탐지, 네트워크 침입 탐지, 제조업의 불량품 검출 등에 활용됩니다. 정상 데이터들은 서로 가까이 모여있고, 이상 데이터는 멀리 떨어져 있다는 특성을 이용합니다. 특정 거래가 가장 가까운 이웃들과 평균 이상으로 멀리 떨어져 있다면 이상 거래로 판단합니다. 신용카드 회사들이 이 방법으로 실시간 사기 거래를 탐지합니다.
의료 진단 보조 시스템
환자의 증상, 검사 수치 등을 바탕으로 유사한 과거 환자들의 진단 결과를 참고하여 질병을 예측합니다. 예를 들어 당뇨병 진단에서 혈당, 나이, BMI 등의 특성이 비슷한 과거 환자 k명을 찾아 그들의 진단 결과를 참고합니다. 해석 가능성이 높아 의료진에게 "왜 이런 진단을 내렸는지" 설명하기 쉽다는 장점이 있습니다.
7. Key Words
k (이웃의 수)
참고할 가장 가까운 데이터 포인트의 개수. 홀수로 설정하면 동점 상황을 피할 수 있습니다.
유클리드 거리 (Euclidean Distance)
두 점 사이의 직선거리. 가장 일반적으로 사용되는 거리 측정 방법입니다. 공식: √[(x₁-x₂)² + (y₁-y₂)²]
맨해튼 거리 (Manhattan Distance)
두 점 사이를 격자 형태로 이동할 때의 거리. 공식: |x₁-x₂| + |y₁-y₂|. 고차원 데이터에서 유용합니다.
정규화 (Normalization)
모든 특성 값을 0과 1 사이로 변환하는 과정. 공식: (x - min) / (max - min). 거리 계산에서 스케일 차이를 제거합니다.
과적합 (Overfitting)
모델이 훈련 데이터에만 지나치게 맞춰져 새로운 데이터에 대한 예측 성능이 떨어지는 현상. k값이 너무 작을 때 발생합니다.
교차 검증 (Cross Validation)
데이터를 여러 부분으로 나누어 모델의 성능을 평가하는 기법. 최적의 k값을 찾는 데 사용됩니다.
차원의 저주 (Curse of Dimensionality)
특성(차원)의 수가 증가하면서 데이터가 희소해지고, 거리 개념이 무의미해지는 현상. k-NN의 주요 한계입니다.
가중 투표 (Weighted Voting)
모든 이웃에게 동일한 투표권을 주는 대신, 거리가 가까운 이웃에게 더 높은 가중치를 부여하는 방식입니다.
KD-Tree
k차원 공간에서 효율적인 최근접 이웃 탐색을 위한 자료구조. 대용량 데이터에서 검색 속도를 개선합니다.
하이퍼파라미터 튜닝 (Hyperparameter Tuning)
모델의 학습 전에 설정하는 변수(k값, 거리 측정 방법 등)를 최적화하는 과정입니다.
8. 한계
계산 복잡도와 속도
k-NN의 가장 큰 한계는 예측 시 모든 훈련 데이터와의 거리를 계산해야 한다는 점입니다. 데이터가 백만 건이면 백만 번 계산해야 하므로, 실시간 서비스에서는 응답 속도가 느려질 수 있습니다. 이를 극복하기 위해 KD-Tree, Ball Tree, Locality-Sensitive Hashing(LSH) 등의 근사 최근접 이웃 탐색 알고리즘이 연구되고 있습니다. Annoy, FAISS 같은 라이브러리가 이를 구현하고 있습니다.
메모리 요구사항
모든 훈련 데이터를 메모리에 보관해야 하므로, 대용량 데이터셋에서는 메모리 부족 문제가 발생할 수 있습니다. 특히 이미지나 텍스트 같은 고차원 데이터에서는 더욱 심각합니다. 해결책으로 프로토타입 선택, 데이터 압축, 또는 다른 알고리즘과의 결합이 연구되고 있습니다.
차원의 저주
특성이 많아질수록 모든 데이터 포인트가 서로 비슷한 거리에 위치하게 되어 "가까운 이웃"이라는 개념 자체가 무의미해집니다. 이를 극복하기 위해 차원 축소(PCA, t-SNE) 기법을 먼저 적용하거나, 특성 선택을 통해 중요한 특성만 사용하는 방법이 있습니다.
불균형 데이터
특정 클래스의 데이터가 압도적으로 많으면, k개 이웃 중 대부분이 다수 클래스에 속하게 되어 소수 클래스를 제대로 예측하지 못합니다. 가중치 부여, 언더샘플링/오버샘플링, 또는 거리 기반 가중 투표 방식으로 개선할 수 있습니다.
다음 학습 자료 추천
k-NN을 이해했다면 다음 단계로 다음 알고리즘들을 학습하는 것을 추천합니다.
- Decision Tree: k-NN과 달리 명확한 규칙 기반 분류를 학습합니다.
- Naive Bayes: 확률 기반 접근으로 텍스트 분류에 강합니다.
- Support Vector Machine (SVM): 고차원 데이터에서 k-NN보다 효율적입니다.
- Random Forest: 앙상블 학습의 대표적 알고리즘으로 실무에서 널리 사용됩니다.
9. 퀴즈
질문 1: k-NN에서 k=1과 k=100 중 어느 것이 과적합 위험이 더 높을까요?
답변: k=1이 과적합 위험이 더 높습니다. k=1은 가장 가까운 단 하나의 이웃만 보기 때문에 노이즈나 이상치에 매우 민감합니다. 반면 k=100은 너무 많은 이웃을 참고하여 결정 경계가 지나치게 단순해지는 과소적합 문제가 발생할 수 있습니다. 최적의 k값은 데이터의 특성에 따라 다르며, 교차 검증을 통해 찾아야 합니다.
질문 2: 나이(0-100)와 연봉(2000만-2억원)을 특성으로 사용할 때 왜 정규화가 필요한가요?
답변: 정규화를 하지 않으면 연봉의 값이 나이보다 약 200만 배 이상 크기 때문에, 거리 계산 시 연봉의 영향력이 압도적으로 커집니다. 예를 들어 나이 차이 10살은 거리 계산에서 10의 영향을 주지만, 연봉 차이 1000만원은 10,000,000의 영향을 줍니다. 따라서 나이는 사실상 무시되고 연봉만으로 분류가 이루어집니다. 정규화를 통해 모든 특성을 0-1 범위로 맞추면 각 특성이 공평하게 거리 계산에 기여할 수 있습니다.
질문 3: PM으로서 k-NN 기반 추천 시스템을 검토할 때 가장 먼저 확인해야 할 기술적 리스크는 무엇인가요?
답변: 사용자 수와 상품 수가 증가했을 때의 응답 속도입니다. k-NN은 예측 시마다 전체 데이터와 거리를 계산해야 하므로, 사용자가 10만 명, 상품이 10만 개라면 최악의 경우 수십억 번의 계산이 필요합니다. 이는 서비스의 응답 시간을 크게 저하시킵니다. 따라서 PoC 단계에서부터 예상 데이터 규모에서의 응답 시간을 측정하고, 필요시 근사 최근접 이웃 탐색 알고리즘(FAISS, Annoy 등) 도입이나 배치 처리 방식으로의 전환을 계획해야 합니다. 또한 캐싱 전략도 함께 고려해야 합니다.