K-최근접 이웃(K-Nearest Neighbor)은 머신러닝에서 사용되는 분류(Classification) 알고리즘이다. 유사한 특성을 가진 데이터는 유사한 범주에 속하는 경향이 있다는 가정하에 사용한다.

K-최근접 이웃 알고리즘의 개념

원리를 쉽게 이해하기 위해 그림을 참고하겠다.

아래 그림을 보자. 모든 데이터(점)에는 각각 x값과 y값이 있다. 그리고 점의 색상으로 초록/빨강으로 표시하여 분류를 나타냈다. 그리고 하얀 점은 아직 분류가 안 된 새로운 데이터다. K-최근접 이웃 알고리즘의 목적은 이렇게 새로운 점이 등장했을 때 이걸 초록이나 빨강으로 분류하는 거다.

그런데 하얀 점 주위로 원을 그려놓았고, 이 원 안에는 1개의 이웃이 있다. 이렇게 원 안에 포함될 이웃의 개수를 k라고 생각하면 된다. 위 그림에서 k=1이고, 하얀 점은 초록으로 분류되는 거다.

자, 이제 원을 확장해보자. k를 2로 조정해서 가장 가까운 이웃의 수를 2개까지 늘려보자.

이웃 2개 모두 초록이다. 이번에도 하얀점은 초록으로 분류된다.

이번엔 가장 가까운 이웃의 숫자를 3으로 늘려보자.

초록 2개, 빨강 1개다. 여전히 초록이 많기 때문에 하얀 점은 초록으로 분류된다. 일종의 다수결이다.

가장 가까운 이웃의 숫자를 4로 늘려보자.

오.. 초록 2개, 빨강 2개. 동률이 나왔다.

이 때는 좀 곤란하다. 애초에 k를 홀수로 지정하면 이런 문제가 없는데 말이다.
물론 이렇게 동률(tie)이 나왔을 때 처리하는 몇가지 방법이 있긴 하다. 예를 들면 가장 가까운 이웃을 따른다든가, 아니면 랜덤으로 찍는다든가. 그러나 데이터가 충분하다면 어쨌든 이러나 저러나 결과는 비슷하게 나오니 너무 걱정 말자.

마지막으로 k를 5로 늘리면 원이 확장되면서 이웃 중 빨강이 3개, 초록이 2개니까 하얀 점이 비로소 빨강으로 분류가 된다.

이게 K-Nearest Neighbor 알고리즘의 핵심 개념이다. 이미 각 점들의 분류를 알고 있으면 새로운 점이 등장했을 때 그 녀석을 어디로 분류할지 정할 수 있는 거다.

그런데 이 알고리즘에는 몇가지 생각해볼 문제들이 있다.

1. 정규화(Normalization)

위 예제에서는 x와 y값이 적당히 잘 퍼져 있으니 문제가 안 드러나지만 실제 데이터는 그렇지 않다. 예를 들어 성인 남녀의 연봉과 시력을 특성(feature)으로 생각해보자. 연봉 단위가 원()이면 편차가 천만 단위를 넘어가겠지만, 시력은 소숫점까지 따져가며 최대값과 최소값의 편차가 10 미만일 거다. 그걸 똑같은 기준으로 고려해서 반영하면 연봉이 압도적으로 반영되기 때문에 터무니 없는 결론이 나올 수 있다.

그래서 K-Means Neighbor 알고리즘을 사용할 때는 모든 특성들을 고르게 반영하기 위해 정규화(Normalization)를 해주곤 한다. 정규화하는 방법에는 여러가지가 있는데, 가장 널리 사용되는 방법은 두 가지다.

• 최소값을 0, 최대값을 1로 고정한 뒤 모든 값들을 0과 1사이 값으로 변환하는 방법

• 평균과 표준편차를 활용해서 평균으로부터 얼마나 떨어져있는지 z-점수로 변환하는 방법

이 외에 다른 방법들도 있고, 각각의 장단점이 있지만 아무튼 보통 위 방법을 적절히 사용해서 특성들을 정규화 해주면 어느정도는 해결된다. 물론 정규화가 언제나 능사는 아닐 거다. 기회가 되면 다른 포스팅에서 더 자세히 다루겠다.

2. K 개수 선택

또 다시 고려할 중요한 문제는 'k를 몇으로 정할 것인가'이다. 이건 모든 값을 실제로 테스트하면서 분류 정확도(Accuracy)를 계산하는 과정에서 단서를 찾을 수 있다.

k가 너무 작을 때 : Overfitting

일단 k가 너무 작은 경우를 생각해보자. 극단적으로 k=1이라고 하자. 그러면 분류 정확도가 상당히 낮을 수 밖에 없다. 시야가 좁아지는 거고, 아주 근처에 있는 점 하나에 민감하게 영향을 받기 때문이다. 이를 overfitting(과적합)이라고 한다. (overfitting은 머신러닝 알고리즘에서 정말정말 중요한 개념이니 꼭 알고 넘어가야 한다. 이 글을 참고하자.) 아무튼, K-Nearest Neighbors 알고리즘에서는 주변 다른 이웃들까지 충분히 고려하지 않았을 때 오버피팅이 발생한다. 그래서 하나의 이상치(outlier)가 있을 경우 근처에 있는 점의 레이블이 그 이상치에 의해 결정될 수 있다.

아래 그림을 보자.

그림 왼쪽 상단의 검은색 점은 이상치인 것으로 보인다. 만약 k=1인 경우 그 근처에 데이터가 위치하면 녹색으로 분류되지 않고 이상치를 따라 진한 파란색으로 분류되어 버린다.

k가 너무 클 때 : Underfitting

반면에 k가 너무 큰 경우에는 underfitting(과소적합)이 발생한다. underfitting은 분류기가 학습 세트의 세세한 부분에 충분히 주의를 기울이지 않았기 때문에 나타난다. 예를 들어 학습 세트에 100개의 점이 있고 k=100으로 설정했다고 극단적으로 가정해보자. 그러면 모든 점이 결국 동일한 방식으로 분류될 거다. 점 사이의 거리는 의미가 없어진다. 물론 이건 극단적인 예이지만... 아무튼 k가 너무 크면 분류기가 학습 데이터를 충분히 세세하게 살펴보지 못한다는 뜻이다.

분류 모델을 생성할 때 일부 데이터는 검증에 활용되도록 떼어놓고 학습 데이터로만 모델을 생성해서 검증 데이터를 넣어 정확도(Accuracy)를 확인할 수 있는데, (참고 글) 아래 그래프는 한 분류 모델에서 k 값을 변화시키면서 분류 정확도를 확인한 예시다.

k가 너무 작으면 과적합이 발생하여 정확도가 상대적으로 낮다. 반면 k가 너무 커져도 언더 피팅이 발생해서 정확도가 떨어지기 시작하는 걸 알 수 있다. 결국 75 언저리에서 가장 높은 정확도를 보여준다

---

아무튼 이 정도까지 고려할 수 있다면 K-최근접 이웃 알고리즘을 개념적으로 이해했다고 볼 수 있다. 구체적으로 점 사이의 거리를 구하는 방법도 중요한데, 그건 이 포스팅을 참고하자.

핵심 요약

아무튼 K-최근접 이웃 알고리즘의 핵심 내용을 요약해보면 아래와 같이 정리할 수 있다.

• n개의 특성(feature)을 가진 데이터는 n차원의 공간에 점으로 개념화 할 수 있다.

• 유사한 특성을 가진 데이터들끼리는 거리가 가깝다. 그리고 거리 공식을 사용하여 데이터 사이의 거리를 구할 수 있다.

• 분류를 알 수 없는 데이터에 대해 가장 가까운 이웃 k개의 분류를 확인하여 다수결을 할 수 있다.

• 분류기의 효과를 높이기 위해 파라미터를 조정할 수 있다. (K-Nearest Neighbors의 경우 k값을 변경할 수 있다)

• 분류기가 부적절하게 학습되면 overfitting 또는 underfitting이 나타날 수 있다. (K-Nearest Neighbors의 경우 너무 작은 k는 overfitting, 너무 큰 k는 underfitting을 야기한다)

개념적으로 이해했다면 이제 파이썬을 통해 직접 분류 모델을 만들고 실험을 해보자.

---

출처
https://hleecaster.com/ml-knn-concept/