K-최근접 이웃 알고리즘, KNN(k-Nearest Neighbors)

 

이 알고리즘은 학습한 후, 저장된 데이터 세트와 하나의 데이터 요소를 근접성을 이용해 비교하고 예측을 수행하는 머신러닝 알고리즘이다. 서로 유사한 요소가 가까이에 위치한다는 가정을 기반으로 한다.

 

즉, “끼리끼리 모인다”라는 속담과 같다.

 

분류 또는 회귀 문제를 처리할 수 있다.

• 분류 알고리즘: 이웃한 데이터 중 다수 세트에 새로운 데이터 요소를 할당
• 회귀 알고리즘: 쿼리(새로운 데이터 포인트) 지점에 가장 가까운 값의 평균을 기반으로 예측을 수행

 

knn은 지도 학습 알고리즘으로, 여기서 ‘k’는 분류 또는 회귀 문제에서 고려되는 최근접 이웃의 수를 나타내고, ‘nn’은 k로 선택된 수에 대한 최근접 이웃을 나타낸다.

 

🏛️ [알쓸코잡] KNN 알고리즘의 역사

미군을 위해 수행된 연구 중 1951년 Evelyn Fix와 Joseph Hodges가 처음 개발하였다.
그들은 *비모수적 분류 방법인 판별 분석을 설명하는 논문을 발표하였다.
1967년에 Thomas Cover와 Peter Hart는 비모수적 분류 방법을 확장하여 Nearest Neighbor Pattern Classification” 논문을 발표하였다.
거의 20년이 지난 후, James Keller는 더 낮은 오류율을 생성하는 “*퍼지 KNN”을 개발하여 이 알고리즘을 개선하였다.
오늘날 KNN 알고리즘은 유전학부터 금융, 고객 서비스에 이르기까지 대부분의 분야에 적용할 수 있어 가장 널리 사용되는 알고리즘이다.

*비모수적 분류 방법: 데이터의 분포나 특정한 가정을 두지 않고 패턴을 학습하여 분류를 수행하는 방법
*Fuzzy knn: 기존에는 한 데이터 포인트를 하나의 클래스로 강제 배정하는 반면, 퍼지 knn은 각 클래스에 속할 확률을 부여하는 방식

 

그래서 KNN이 데이터를 이해하는 방식은 ?

: 다양한 레이블의 데이터 중에서, 자신과 가까운 데이터를 찾아 자신의 레이블을 결정하는 방식

 

knn은 지도 학습 알고리즘으로서 작동한다. 즉, 기억하는 훈련 데이터 세트를 제공받는다. 레이블이 지정되지 않은 새로운 데이터가 주어졌을 때, 적절한 출력을 생성하는 함수를 학습하기 위해 레이블이 지정된 해당 입력 데이터에 의존한다.

 

 

2차원이라고 가정하고, 위의 그림은 레이블이 2개인 경우이다. 세모, 네모 데이터가 이미 존재하는 상태에서 동그라미라는 데이터가 들어왔을때, 이 데이터는 둘 중 어디에 가까운지를 판단한다. 그림 속에서 동그라미와 가까운 데이터는 세모가 2개, 네모가 1개이므로, 동그라미는 세모라고 판단할 수 있다.

 

• 분류 문제의 경우 knn 알고리즘은 다수를 기반으로 클래스 레이블을 할당한다. 분류 문제의 출력은 최근접 이웃들의 최빈값이다. 즉, 주어진 데이터 요소 주변에 가장 자주 나타나는 레이블을 사용한다.
• 회귀 문제는 가장 가까운 이웃들의 평균을 사용하여 분류를 예측한다. 새로운 데이터 포인트의 값을 예측할 때, 가장 가까운 k개의 이웃을 찾아 평균(또는 가중 평균)을 계산하여 값을 추정하는 방법이다. 회귀 문제는 쿼리 출력으로 실수를 생성한다.

 

이를 통해 분류 또는 회귀 문제를 해결할 수 있다. knn의 계산은 훈련 단계가 아닌 쿼리 중에 발생하지만, 중요한 데이터 저장 요구 사항이 있으므로 메모리에 크게 의존한다.

 

KNN 거리 측정 방식 (Distance Metric)

knn 알고리즘의 핵심은 쿼리 지점과 다른 데이터 지점 사이의 거리를 결정하는 것이다. 다시 말해, 데이터 간의 유사도를 측정하는 것이다. 거리 메트릭을 결정하면 결정 경계가 가능해진다. 이러한 경계는 다양한 데이터 지점 영역을 만든다. 거리를 계산하는 데 사용되는 방법은 다양하다.

 

• 유클리드 거리 (Euclidean Distance)
  : 가장 일반적인 거리 측정법으로, 쿼리 지점과 다른 측정 대상 지점 사이의 직선 거리를 측정한다.

 

• 맨해튼 거리 (Manhattan Distance)
  : 널리 사용되는 측정법으로, 두 지점 사이의 절대값을 측정한다. 그리드상에 표시되며 흔히 택시 기하학이라고도 하는데, A 지점(쿼리 지점)에서 B 지점(측정 대상 지점)까지 어떻게 이동하는지를 의미한다.

사진 속 초록색이 유클리드. 나머지(빨, 파, 노)는 맨해튼 거리. : 회색을 도로, 흰색을 건물이라고 하면, 유클리드처럼 뚫고 지나갈 수 없으니, 맨해튼 거리로 측정.

 

• 민코프스키 거리 (Minkowski Distance)
  : 유클리드(L2) 거리와 맨해튼(L1) 거리 메트릭을 일반화한 것으로, 다른 거리 메트릭을 생성할 수 있게 해준다. 이는 정규화된 벡터 공간에서 계산된다. 민코프스키 거리에서 p는 계산에 사용되는 거리 유형을 정의하는 매개변수이다. p=1이면 맨해튼 거리가 사용된다. p=2이면 유클리드 거리가 사용된다.

❓ [알쓸코잡] 그럼 p=1, p=2만 쓰면 되는데, 왜 민코프스키 거리를 써?

p를 1과 2 사이(예: 1.5)로 설정할 수 있음

p=1 (맨해튼 거리) → 직각 방향(격자형) 이동
p=2 (유클리드 거리) → 대각선 이동 가능
p=1.5 → 맨해튼과 유클리드 거리 중간 형태

⇒ 이렇게 p 값을 조정하면서 최적의 거리 측정 방식을 찾을 수 있다.

 

• 해밍 거리 (Hamming Distance)
  : 중첩 메트릭이라고도 하며, 부울 또는 스트링 벡터에서 벡터가 일치하지 않는 위치를 식별하기 위해 사용되는 기술이다. 즉, 길이가 같은 두 스트링 사이의 거리를 측정한다. 특히 오류 탐지 및 오류 수정 코드에 유용하다.

⇒ x_i와 y_i가 다르면 1, 같으면 0

 

최적의 k 값을 선택하는 방법

최적의 k 값(고려된 최근접 이웃의 수)을 선택하려면 몇 가지 값을 실험하여 가장 적은 수의 오류로 가장 정확한 예측을 생성하는 k 값을 찾아야 한다. 최적의 값을 결정하는 것은 균형을 맞추는 작업이다.

 

• k 값이 낮으면 예측이 불안정해진다.
• k 값이 높으면 잡음이 끼게 된다.

 

이상적으로는 높은 분산과 높은 편향 사이의 균형을 이루는 k 값을 찾아야 한다. 또한, 분류 분석에서 동점을 피하기 위해 k 값을 홀수로 선택하는 것이 좋다. (짝수로 했을 경우 분류가 동점이 될 수 있기 때문에)

높은 편향(Bias)

모델이 데이터의 패턴을 충분히 학습하지 못한 상태
과소적합(Underfitting)의 원인
ex. 직선 하나로 모든 데이터를 설명하려고 하는 경우

높은 분산(Variance)

모델이 데이터의 작은 변동(노이즈)까지 지나치게 학습한 상태
과적합(Overfitting)의 원인
ex. 데이터마다 일일이 다른 곡선을 그려서 예측하는 경우

 

적합한 k 값은 데이터 세트와도 관련이 있다. 해당 값을 선택하려면 N의 제곱근(일반적인 경험칙)을 찾아야 한다. 여기서 N은 훈련 데이터 세트의 데이터 요소 수이다. 교차 검증 전략도 데이터 세트에 가장 적합한 k 값을 선택하는데 도움이 될 수 있다.

 

KNN 알고리즘의 장점

“가장 간단한” 지도 학습 알고리즘으로 설명된다.

 

• 간단하다
  단순하고 정확하기 때문에 구현이 용이하다. 따라서 데이터 과학자가 배우는 첫 번째 분류기 중 하나로 종종 사용된다.
• 적응력
  새로운 훈련 샘플이 데이터 세트에 추가되면 knn 알고리즘은 그 새로운 훈련 데이터를 포함하도록 예측을 즉시 조정한다.
• 쉽게 프로그래밍 가능
  knn에는 k 값과 거리 메트릭 등 몇 가지 하이퍼파라미터만 필요하다. 이는 알고리즘을 상당히 단순하게 만든다.

 

KNN의 한계

단순성으로 인한 몇 가지 과제와 한계를 가지고 있다.

• 확장하기 어렵다
  많은 메모리와 데이터 저장 공간을 차지하므로 저장과 관련된 비용이 증가한다. 메모리에 대한 이러한 의존성도 알고리즘이 계산 집약적이며, 결과적으로 리소스 소모가 크다는 것을 의미한다.
• 차원의 저주
  이는 컴퓨터 과학에서 일어나는 현상을 가리키는 말로, 차원 수가 늘어나고 이러한 차원에 특징 값이 본질적으로 증가함에 따라 고정된 훈련 예제 세트가 어려움을 겪는 것을 말한다. 다시 말해, 모델의 훈련 데이터는 진화하는 초공간의 차원을 따라잡을 수 없다. 즉, 쿼리 지점과 유사한 지점 사이의 거리가 다른 차원에서 더 멀어지기 때문에 예측의 정확도가 떨어진다.
• 과적합
  k 값이 너무 낮으면 데이터를 과적합시킬 수 있는 반면, k 값이 높을수록 알고리즘은 더 넓은 영역에 대해 값의 평균을 계산하므로 예측 값이 ‘평활’해진다.

 

Reference

k-최근접 이웃(kNN)이란 무엇인가? | k-최근접 이웃 종합 안내서

KNN 알고리즘 [ Python 데이터 분석과 이미지 처리 ] (KNN Algorithm)

[머신러닝] kNN(k-Nearest Neighbors) 최근접 이웃 알고리즘

k-최근접 이웃 알고리즘

맨해튼 거리

Minkowski, Manhatten, Euclidean, Chebyshev Distance, Lasso, Ridge 를 알아보자