K 최근접 이웃 알고리즘이란?

본 블로그 작성 글들은, 강의를 목표로 하고 제작되었습니다. 또한 작성된 글의 정보도 틀렸을 수 있으니, 주의해주세요.

K-Nearest Neighbors, 줄여서 KNN은 새로운 데이터와 가장 가까운 K개의 데이터를 찾아 결과를 정하는 알고리즘이다. 한국어로는 K 최근접 이웃 알고리즘이라고 부른다.

주변의 다수를 따라간다

사과와 오렌지의 무게, 색상 데이터를 이미 가지고 있다고 해보자. 새 과일이 들어오면 기존 데이터 중 가장 가까운 과일들을 찾는다.

새 과일 주변 5개
사과 4개
오렌지 1개

예측 결과: 사과

여기서 K가 5라면 가까운 데이터 5개를 확인한다. 분류 문제에서는 가장 많은 클래스를 선택하고, 회귀 문제에서는 가까운 값들의 평균을 사용할 수 있다.

학습보다 검색에 가깝다

KNN은 복잡한 모델을 미리 만드는 과정이 거의 없다. 학습 데이터를 그대로 보관해두고 예측할 때마다 새로운 데이터와의 거리를 계산한다.

학습 단계: 데이터를 저장한다.
예측 단계: 모든 데이터와 거리를 계산한다.

그래서 구현은 단순하지만 데이터가 많아질수록 예측이 느려진다. 데이터가 N개이고 특징이 D개라면 단순 구현은 한 번 예측할 때 대략 N개의 거리를 계산해야 한다.

K 값은 결과를 바꾼다

K가 1이면 가장 가까운 데이터 하나만 믿는다. 작은 노이즈에도 결과가 쉽게 바뀔 수 있다.

K가 너무 크면 멀리 있는 데이터까지 포함해서 지역적인 특징을 잃는다. 두 클래스가 비슷한 수로 존재한다면 동률을 줄이기 위해 홀수를 선택하기도 하지만, 항상 홀수가 정답인 것은 아니다.

KNN의 핵심은 가까운 데이터는 비슷한 성질을 가진다는 가정이다. 따라서 거리의 의미가 분명하고 데이터의 크기가 지나치게 크지 않은 문제에서 먼저 시험해보기 좋은 알고리즘이다.