K-Nearest Neighbor (KNN)

# 개요

k개의 가장 가까운 이웃을 보고 분류/예측하는 방법이다. 

 

아래와 같이 k개 만큼의 가장 가까운 이웃을 찾고 majority voting를 통해 최종 분류를 한다. 

Instance-based Learning의 한 종류로 별도의 모델을 생성하지 않고 각각의 관측치 (instance) 만으로 예측을 진행한다. 

 

# 분류 알고리즘

1. 분류할 관측치 x를 선택

2. x로부터 인접한 k개의 학습 데이터를 탐색

3. 탐색된 k개 학습 데이터의 majority class c를 정의

4. c를 x의 분류결과로 반환

 

# 예측 알고리즘

관측치 y가 있을 경우는 k개 이웃의 평균을 구한다. 

중위값을 쓰면 안되나 생각할 수 있는데 여러 연구 결과 평균이 가장 정확하다고 한다. 

 

1. 예측할 관측치 x를 선택

2. x로부터 인접한 k개의 학습 데이터를 탐색

3. 탐색된 k개 학습 데이터의 평균을 x의 예측 값으로 반환

 

# 하이퍼파라미터

1. k - 인접한 학습 데이터를 몇 개까지 탐색할 것인가?

2. Distance Measures - 데이터 간 거리는 어떻게 측정할 것인가?

 

# k에 따른 결과

k가 매우 작을 경우 : 데이터의 지역적 특성을 지나치게 반영 (overfitting)

k가 매우 클 경우 : 다른 범주의 개체를 너무 많이 포함하여 오분류 위험 (underfitting)

 

# k 선택 방법

일정 범위 내로 k를 조정하면서 가장 좋은 결과를 보이는 k를 설정 (trial and error)

 

분류냐 예측이냐에 따라 다르다. 

 

분류 모델

Indicator Function은 거짓이면 0 참이면 1을 반환하는 함수를 뜻한다. 

예측 모델

 

아래와 같이 k가 줄어들수록 overfitting으로 test, train의 차이가 벌어진다. 

 

train, test error가 모두 최소가 되는 지점을 찾아야 한다. 

아래에서는 k=5가 최적의 지점이다. 

 

# 장점과 한계점

장점

- 노이즈 영향을 크게 받지 않는다. 

- 특히 Mahalanobis distance와 같이 분산을 고려하면 강건하다. 

- 학습 데이터의 수가 많을 수록 효과적이다. 

 

한계점

- 파라미터 k의 값을 설정해야 한다. 

- 어떤 거리 척도가 해당 데이터에 적합한 지 불분명하다. (임의로 설정해봐야됨)

- 새로운 관측치가 들어오면 전체 거리를 다 계산해봐야하므로 오래 걸린다. 

 

# Weighted KNN

k개의 이웃을 볼 때 가까운 이웃에 더 가중치를 준다. 

 

예측 모델의 경우 거리에 반비례하는 가중치를 y에 곱해준다. 

분류 모델의 경우도 컨셉은 동일한데 거리를 구할 때 가중치를 곱해준다. 

 

# 정리

KNN은 매우 단순하면서 새로운 관측치를 분류나 예측하는데 좋은 알고리즘이다. 

 

선형모델처럼 모델을 만드는 방식이 아니라 관측치를 토대로 새로운 데이터를 예측한다. 

 

일부 유사한 관측치의 반응변수를 조합해서 예상되는 값을 구하는 방식이다. (average, majority, voting)

 

Weighted KNN으로 가중치를 고려할 수도 있고 기타 다른 모델도 많이 나와있다. 

 

 

참고 : 김성범 교수님 유튜브