02 - 4. K-Nearest Neighbors

이론적으로는 모든 상황에서 Bayes Classifier를 사용하여 categorical response를 예측하는 것이 좋지만

실제 데이터에 대해서는 X가 특정 class에 속할 확률을 알지 못하기 때문에 적용할 수가 없습니다.

이러한 상황에서 사용할 수 있는 여러 방법 중 K-Nearest Neighbors(KNN)을 살펴보겠습니다.

KNN을 이용하기 위해서는 우선 레이블된 학습 데이터를 좌표 공간에 표현해야 합니다.

이후 어떤 class에 속하는 지를 알고자하는 데이터를 중심으로 가상의 원(단, 2차원일 경우)을

k개의 데이터가 발견될 때까지 확장시키며 그려나갑니다.

k개의 데이터가 발견되었을 때 그 중 가장 많은 데이터가 속하는 class를

새로운 데이터의 class로 결정합니다.

이를 수식을 통해 다시 정리해보도록 하겠습니다.

class를 알고자하는 observation을 ,

에 가장 가까이 있는 k(단, k는 양의 정수)개의 데이터를 라고 합시다.

이때 가 class 에 속할 확률을 다음과 같이 정의합니다.

수식을 통해 알 수 있는 것은 KNN이 Bayes rule을 적용했다는 것입니다.

k개의 데이터 중 가장 개수가 많은 데이터의 class로 지정한다는 것은

가장 확률이 높은 class로 지정해준다는 것이기 때문입니다.

이번에는 그림을 통해 KNN을 살펴보겠습니다.

왼쪽 그림은 K=3일 때 KNN을 적용한 것을 나타낸 것입니다.

Class는 2가지로 orange class와 blue class가 있으며

class를 알고자하는 데이터는 X로 표시되어 있습니다.

X를 중심으로 원을 그렸을 때 원 내부에 속하는 점이

3개가 되었을 때의 영역을 초록색 원으로 표현되어 있습니다.

이때 원 안에서 orange point가 1개 blue point가 2개 있으므로

X가 각각의 class에 속할 확률은 1/3, 2/3 입니다.

따라서 더 높은 확률을 가지는 blue class가 X의 class로 분류됩니다.

오른쪽 그림은 K=3일 때 좌표 상 모든 점을 KNN을 적용하여 알아낸

decision boundary를 나타낸 것입니다.

이렇게 KNN은 간단한 방법이지만 좋은 성능을 보여줍니다.

위의 그림은 KNN과 Bayes Classifier를 비교한 것입니다.

검은색 실선은 K=10일 때 KNN을 적용하였을 때의 decision boundary이고

보라색 점선은 Bayes Classifier를 적용하였을 때의 decision boundary입니다.

하지만 KNN도 피해갈 수 없는 문제점이 있습니다.

이는 전에 다루었던 Overfitting과 Underfitting 문제입니다.

그렇다면 KNN에서 fitting의 정도에 영향을 주는 요소는 무엇일까요?

바로 k를 무엇으로 지정하느냐에 달려있습니다.

위의 그림은 k의 값을 1과 100으로 지정했을 때 각각의 상황에서의 decision boundary를 표현한 것입니다.

그리고 마찬가지로 보라색 점선은 Bayes decision boundary입니다.

그림을 통해 k가 1일 때 flexibility가 높다는 것을 알 수 있습니다.

그리고 tradeoff을 통해 설명하자면 k가 1일 때 bias가 낮고 variance가 높습니다.

즉, Overfitting이 발생하였습니다.

이와 달리 k가 100일 때 flexibility가 낮으며 bias가 높고 variance가 낮습니다.

즉, Underfitting이 발생하였습니다.

아래 그림은 1/K 따른 Error Rate의 변화를 나타낸 그림입니다.

그래프를 통해 알 수 있듯이

K값이 작아질수록 (1/K값이 커질수록) Training Error는 감소하는 추세를 보임을 알 수 있습니다.

하지만 Test Error는 어느정도 감소하는 추세를 보이다가 1/K이 0.10인 지점 이후로 다시 증가하는 것을 확인할 수 있습니다.

즉, K값이 10을 넘어가자 Overfitting이 발생한 것입니다.

결론적으로 KNN 또한 k값 설정을 통해 bias-variance tradeoff를 고려하여 적절한 flexibility를 고르는 것이 중요한 문제입니다.

이와 관련하여 5장에서는 적절한 flexibility를 고르는 방법을 다룰 것입니다.

출처 : Gareth James -  'An Introduction to Statistical Learning'