8. K-Nearest Neighbors

what?

• 새로운 데이터가 주어졌을 때 기존 데이터 가운데 가장 가까운 k개의 이웃의 정보로 새로운 데이터를 분류하는 방법
• 분류와 회귀 모두 가능하다.
• model을 별도로 구축하지 않는 instance-based learning
• hyperparameter로 범주의 개수인 k개, 거리 측정 방법인 distance를 가진다.
• k는 일반적으로 홀수를 사용한다. 짝수의 경우 범주를 결정하지 못하는 문제가 발생할 수 있다.
• 거리를 측정하는 방법에는 Euclidean distance, Manhattan distance, Mahalanobis ditance, Correlation distance가 있다.

why?

• 직관적이고 실행하기 쉽고 다중 분류에서도 좋은 성능을 보임
• 비모수 알고리즘이기 때문에 학습 과정을 필요로 하지 않는다.
• 새로운 데이터를 수집하는 동시에 새로운 정보를 반영한다.

why not?

• 데이터의 수가 많아지면 연산량이 늘어나 느려진다.
• 이상치에 민감함
• imbalance 데이터를 잘못 분류할 가능성이 높음

how?

Input

1)Data{(\(x_i, y_i\))}, M rows(data) and N columns(feature)
2) parameter k
3) 거리 측정 방법
4) 새로운 데이터 \(x_n\)

Step 1 distance 내에 있는 데이터 샘플 수집

Step 2 문제에 따른 새로운 데이터에 대한 정보 할당

1) classification

• distance 내에 있는 데이터 샘플의 수를 범주별로 측정하여 가장 많은 데이터를 가지고 있는 범주를 새로운 데이터에 할당한다.

2) regression

• distance 내에 있는 데이터 샘플의 값의 평균을 계산하여 새로운 데이터에 할당한다.

Step 3 새로운 데이터에 대한 정보 할당

Code usage

import numpy as np
from sklearn import neighbors, datasets
from sklearn.neighbors import KNeighborsClassifier

n_neighbors = 15

iris = datasets.load_iris()
X = iris.data[:, :2]
y = iris.target

knn = KNeighborsClassifier(n_neighbors)
knn.fit(X, y)

Reference

K-Nearest Neighbors 설명
K-Nearest Neighbors 장단점