k-Nearest Neighbors
'k-최근접 이웃' 혹은 'kNN'으로 불리는 알고리즘입니다.
선형모델이 아니기 때문에 독립변수와 종속변수간의 선형성에 영향을 받지 않고 간결함 때문에 classification 베이스라인 모델로 자주 사용됩니다.
knn은 사전 훈련을 필요로 하지 않기 때문에 instance-based learning이라 할 수 있습니다.
아래에서 다시 설명하겠습니다.
- 분류 : Supervised learning
- 형태 : Distance-based model
- 용도 : Classification or Regression
- 장점 : 간결함(베이스라인), 사전 트레이닝 필요 없음
- 단점
- 느린 속도 (예측 시마다 모든 계산)
- 비효율적인 메모리 사용 (모델이 없기때문에 예측 시마다 모든 데이터셋 필요)
- 거리 기반으로 피처 스케일링 필수
- 차원의 저주(Curse of Dimensionality)에 취약
- 아웃라이어(outlier)에 취약
1. Model
모델의 원리는 매우 간단합니다.
새로운 observation 에 대한 예측을 위해서는 전체 데이터셋에서 가장 거리가 가까운 k개의 데이터를 선택해서 다수결의 원리로 가장 많이 분류된 값을 따라가는 형태입니다.
Regression 이라면 가장 가까운 k의개의 데이터 중 평균치로 할당됩니다. 이렇게 간단할수가요..
여기서 벡터 공간 내 데이터들간 거리를 표현하는 방법은 여러가지가 있습니다.
대표적으로 유클리디안 거리와 코사인 유사도가 있습니다.
1.1. Euclidean Distance
1.2. Cosine Similarity
수식이 필요하지 않을 정도로 이해하기 쉬운 간단한 모델입니다만, 실제로 kNN모델은 non-parametic 알고리즘이기 때문에 모델을 하나의 수식으로 표현할 수 없습니다.
수식으로 표현할 수 없다는 말은 다시말해 매번 prediction을 수행할때마다 모든 데이터셋을 가지고 다시 처음부터 모델을 학습한다는 의미입니다.
이렇게 매번 prediction 시마다 모델의 훈련을 시작하는 알고리즘을 instance-based learning algorithm이라고 합니다. 데이터셋이 커질수록 예측속도가 매우 느려지는 특징이 있습니다.
반대로 한번 훈련한 이후로는 해당 모델을 재사용할 수 있는 형태를 model-based algorithm이라고 합니다.
Reference
[1] Wikipedia, https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
