KNN(K-Nearest Neighbors)
- 별도의 모델 생성 없이 인접 데이터를 분류/예측에 사용하는 기법, 새로운 데이터가 들어왔을때 해당 데이터에 근접 한 K개의 데이터를 통해 예측한다.
- Instance-based Learning: 각각의 관측치(instance)만을 이용하여 새로운 데이터에 대한 예측을 진행
- Memory-based Learning: 모든 학습 데이터를 메모리에 저장한 후, 이를 바탕으로 예측 시도
- Lazy Learning: 모델을 별도로 학습하지 않고 테스트 데이터가 들어와야 비로소 작동하는 게으른(Lazy) 알고리즘
- classification일 경우 k개의 이웃중에 가장 많이 나타나는 범주로 해당 class를 추정한다. tie문제를 막기 위해 K는 홀수로 정하는것이 좋다.
- regression일 경우 k개의 이웃들의 대표값(평균)으로 추정한다.
K를 정하는 방법
- k는 1부터 전체 데이터의 개수만큼 가능하다.
- 너무큰 k는 underfitting
- 너무작은 k는 overfitting
- 적당한 k를 구하는 방법: cross validation을 통하여 error가 제일 작은 최적의 k를 구하면된다.
- KNN의 error function
여러가지 거리의 측정 방법
- 거리를 계산하기전의 데이터 내 변수들이 각기 다른 데이터 범위, 분산등을 가질 수 있으므로, 데이터 정규화를 통해 이를 맞추는것이 중요하다.
- Euclidean Distance:
- 가장 흔히 사용되는 거리측도
- 두 관측치 사이의 직선 거리
- Manhattan Distance:
- x 에서 y로 이동 시 각 좌표축 방향으로만 이동할 경우에 계산 되는 거리
- Mahalanobis Distance:
- 변수 내 분산, 변수 간 공분산을 모두 반영하여 x,y간 거리를 계산하는 방식
- 데이터의 covarinace matrix가 identity matrix인 경우는 Euclidean Distance와 동일하다.
KNN의 학습
KNN은 모델을 생성하는 것이 아니여서 최적의 k 와 distance 측정 방법을 알아내는것이 KNN을 학습하는 과정이다.
Weighted KNN
- 일반적인 KNN과는 달리 새 데이터와 기존 학습 관측치 간의 거리를 가중치로 하여 예측결과를 도출한다.
KNN의 장점
- 데이터 내 노이즈에 영향을 크게 받지 않으며, 특히 Mahalanobis distance와 같이 데이터의 분산을 고려할 경우 강건하다.
- 학습 데이터의 수가 많을 수록 효과적이다.
KNN의 단점
- 파라미터 K의 값을 설정해야한다.
- 어떤 거리 척도가 분석에 적합한 지 불분명하며, 따라서 데이터의 튿성에 맞는 거이측도를 임의로 선정해야한다.
- 새로운 관측치와 가각의 학습 데이터 간 거리를 전부 측정해야 하므로, 계산시간이 오래 걸리는 단점이 있다.
- 고차원의 데이터에는 KNN이 잘 작동하지 않는다.
study blog