K-최근접 이웃 - AI Wiki

K-최근접 이웃(k-NN)은 분류 및 회귀에 사용되는 비모수적 지도 학습 방법으로, k개의 가장 가까운 훈련 예제에 가중치를 부여하여 결정을 내립니다. 모든 훈련 데이터를 저장하고 거리 메트릭을 기반으로 결정을 내리며, 명시적인 훈련 단계가 없습니다.

K-최근접 이웃(K-Nearest Neighbors, k-NN)은 분류와 회귀 모두에 사용되는 비모수적 지도 학습 알고리즘이다. 분류에서는 새 데이터 포인트가 특성 공간에서 거리 메트릭으로 결정된 k개의 최근접 이웃 중 가장 흔한 클래스로 할당된다. 회귀에서는 출력이 해당 이웃들의 값의 평균(또는 가중 평균)이다. 이 알고리즘은 인스턴스 기반으로, 전체 훈련 데이터셋을 저장하고 예측이 필요할 때만 계산을 수행하며, 모든 일반화는 쿼리 시점에 지연된다.

이 방법은 1951년 Joseph Fix와 Evelyn Hodges에 의해 처음 개발되었고, 이후 Thomas Cover에 의해 확장되었다. 가장 단순한 머신러닝 알고리즘 중 하나이지만, 특히 결정 경계가 불규칙한 경우 많은 영역에서 경쟁력 있는 정확도를 달성할 수 있다. 성능은 k의 선택, 거리 메트릭, 특성 스케일링에 크게 의존한다.

역사적 발전

k-NN의 기원은 1951년 미국 공군 항공의학학교(US Air Force School of Aviation Medicine)에서 근무하던 Evelyn Fix와 Joseph Hodges가 최근접 이웃 기반의 비모수적 분류 방법을 도입하면서 시작되었다. 그들의 연구는 특정 통계적 분포를 가정하지 않고 관측값을 분류해야 할 필요성에서 동기가 부여되었다. 1967년 Thomas Cover와 Peter Hart는 이 알고리즘의 속성을 공식화하는 중요한 논문을 발표했으며, 여기에는 베이즈 최적 분류기 대비 오류율의 한계가 포함되었다. 이를 통해 k-NN은 패턴 인식에서 이론적으로 근거가 있는 접근법으로 자리잡았다. 이 알고리즘은 1960년대와 1970년대 컴퓨팅의 발전과 함께 인기를 얻었는데, 훈련 시간이 거의 필요하지 않았지만 저장 공간을 많이 요구했다. 이후 가중 투표와 거리 메트릭 학습의 도입과 같은 발전이 이러한 한계를 해결했다.

알고리즘 개요

k-NN 분류에서 입력은 레이블이 지정된 훈련 샘플의 집합으로 구성되며, 각 샘플은 다차원 공간의 특성 벡터로 표현된다. 알고리즘은 이러한 벡터와 해당 레이블을 저장한다. 쿼리 포인트가 주어지면 쿼리에서 모든 훈련 포인트까지의 거리를 계산하고, 가장 가까운 k개를 선택한 후 그중 가장 빈번한 클래스를 할당한다. k=1인 경우 쿼리는 단순히 가장 가까운 이웃의 클래스로 할당된다. k의 선택은 중요하다. k가 작으면 분산이 커지고 노이즈에 민감해질 수 있으며, k가 크면 결정 경계가 지나치게 평활화되어 다른 클래스의 포인트가 포함될 수 있다.

회귀의 경우 출력은 k개의 최근접 이웃의 타깃 값의 평균이다. 이를 최근접 이웃 평활화(nearest neighbor smoothing)라고 한다. k=1이면 최근접 이웃 보간(nearest neighbor interpolation)이 되어 예측값이 가장 가까운 훈련 포인트의 값과 정확히 일치한다. 가중 변형은 더 가까운 이웃에 더 높은 가중치를 부여하며, 종종 거리의 역수(1/d)에 비례하는 가중치를 사용한다.

거리 메트릭과 특성 스케일링

거리 메트릭의 선택은 중요하다. 연속 특성의 경우 유클리드 거리가 가장 일반적이다. 이산 특성의 경우, 예를 들어 텍스트 분류에서는 해밍 거리나 일치도 메트릭이 사용된다. 유전자 발현 분석과 같은 전문 분야에서는 Pearson 또는 Spearman 상관 계수가 사용되기도 한다. 알고리즘이 거리에 의존하므로, 단위나 스케일이 다른 특성은 거리 계산을 지배할 수 있다. 따라서 각 특성을 공통 스케일(예: z-점수 또는 min-max 스케일링)로 정규화하는 것이 모든 특성이 동등하게 기여하도록 하는 데 필수적이다. 이러한 전처리 단계는 정확도를 크게 향상시킬 수 있다.

통계적 속성

통계적 관점에서 k-NN은 비모수적 방법으로, 기본 데이터 분포의 함수적 형태를 가정하지 않는다. 훈련 데이터는 (X_i, Y_i) 쌍으로 가정되며, 여기서 X_i는 특성 벡터이고 Y_i는 클래스 레이블이다. 주어진 쿼리 포인트 x에 대해 훈련 포인트는 x까지의 거리로 재정렬된다. 표본 크기 n이 증가하고 k가 n에 따라 적절히 증가하며 k/n이 0에 접근하면, 알고리즘의 오류율은 베이즈 오류율로 수렴한다. Cover와 Hart가 확립한 이 속성은 k-NN이 점근적으로 최적임을 보여준다. 그러나 유한한 표본에서는 차원의 저주(curse of dimensionality)가 발생한다. 특성의 수가 증가하면 공간의 부피가 기하급수적으로 커지고 포인트가 희박해져 거리 측정의 의미가 약해진다.

장점과 단점

k-NN의 주요 장점은 단순성과 훈련 단계가 없다는 점이다. 새 데이터를 추가하기만 하면 쉽게 업데이트할 수 있다. 다중 클래스 문제에도 효과적이며 복잡한 결정 경계를 포착할 수 있다. 그러나 명백한 단점도 있다. 예측 시 모든 훈련 포인트와의 거리를 계산해야 하므로 예측 시간이 느리며, 최적화(예: KD-트리 또는 볼 트리) 없이는 대규모 데이터셋에 비실용적이다. 또한 관련 없는 특성과 노이즈 데이터에 민감하다. 알고리즘은 데이터의 국소 구조에 민감하므로, 이상치나 불균형한 클래스 분포는 결과를 왜곡할 수 있다. 클래스가 불균형하면 다수 클래스가 k개의 이웃에 더 자주 나타나 소수 클래스의 포인트가 잘못 분류될 수 있다. 거리의 역수에 따른 가중치 부여나 특성 선택과 같은 기법이 이러한 문제를 완화할 수 있다.

변형과 확장

k-NN의 한계를 해결하기 위해 여러 변형이 개발되었다. 가중 k-NN은 거리에 따라 이웃에 가중치를 부여하여 더 가까운 포인트가 더 큰 영향을 미치게 한다. 거리 메트릭 학습 방법(예: large margin nearest neighbor, neighborhood components analysis)은 데이터에 맞게 거리 메트릭을 학습하여 성능을 향상시킨다. Edited k-NN은 노이즈가 있거나 잘못 분류된 훈련 포인트를 제거하여 일반화를 개선한다. Condensed k-NN은 분류에 필수적인 포인트만 남겨 훈련 세트를 줄인다. Locally adaptive k-NN은 쿼리 포인트 주변의 밀도에 따라 k를 조정한다. 이러한 변형들은 Machine learning 및 Artificial intelligence 분야에서 널리 응용된다.

응용 분야

k-NN은 다양한 영역에서 사용된다. 패턴 인식에서는 이미지 분류와 손글씨 인식에 적용된다. 의학에서는 환자 특성 기반 진단에 사용된다. 금융에서는 신용 평가와 사기 탐지에 활용된다. 추천 시스템에서는 유사한 사용자나 아이템을 찾는 데 사용된다. 생물정보학에서는 유전자 발현 데이터를 분류하는 데 쓰인다. 단순함 덕분에 Neural network이나 Deep learning과 같은 더 복잡한 모델을 비교하는 기준선(baseline)으로 자주 사용된다.

다른 방법과의 관계

k-NN은 인스턴스 기반 학습의 한 형태로, 훈련 중에 명시적 모델을 구축하는 Neural network이나 Support Vector Machine 같은 모델 기반 접근법과 구별된다. 또한 비모수적 밀도 추정과도 관련이 있다. Machine learning의 더 넓은 맥락에서 k-NN은 자주 기준선으로 사용된다. locality-sensitive hashing과 approximate nearest neighbor search의 발전에 영향을 주었으며, 이는 대규모 시스템에서 사용된다. 현대의 Deep learning 방법이 많은 작업에서 k-NN을 능가하지만, k-NN은 작은 데이터셋과 해석 가능한 예측이 필요한 경우 여전히 유용하다.

실용적 고려 사항

k-NN을 구현할 때 몇 가지 실용적인 문제가 발생한다. k의 값은 일반적으로 교차 검증을 통해 선택된다. 이진 분류에서는 동률을 피하기 위해 홀수 k가 자주 사용된다. 특성 스케일링은 필수적이다. KD-트리와 같은 효율적인 데이터 구조는 최근접 이웃 검색을 가속화할 수 있지만, 고차원에서는 성능이 저하된다. 매우 큰 데이터셋의 경우 근사 방법이 필요하다. 알고리즘의 메모리 사용량은 훈련 세트 크기에 비례하므로 제한이 될 수 있다. 현대 응용에서는 k-NN이 Neural network에서 학습된 임베딩 위에 최종 분류기로 결합되기도 한다.

같이 보기

Text is available under the Creative Commons Attribution-ShareAlike 4.0 license. Attribution: wikiprompt.org. Raw markdown (for humans and machines).

분류:machine-learning·classification·regression·non-parametric

이 문서는 다음 날짜에 마지막으로 편집되었습니다: 2026년 9월 7일 작성자 AI Wiki Bot · 역사