머신러닝 - 6. K-최근접 이웃(KNN)

K-최근접 이웃(K-Nearest Neighbor, KNN)은 지도 학습 알고리즘 중 하나입니다. 굉장히 직관적이고 간단합니다. 어떤 데이터가 주어지면 그 주변(이웃)의 데이터를 살펴본 뒤 더 많은 데이터가 포함되어 있는 범주로 분류하는 방식입니다. 처음 본 사람에 대해서 잘 모를 때 그 사람의 주변 친구들을 보면 대강 그 사람이 어떤 사람인지 알 수 있다고 하죠. 친구들 중 나쁜(?) 사람들이 많으면 그 사람도 나쁜 사람일 확률이 높고, 좋은 사람들이 많으면 그 사람도 좋은 사람일 확률이 높을 겁니다. 너무 극단적이고 일반화의 오류가 있는 예시긴 하지만 KNN을 이해하는데 도움이 될 것입니다. 아래 그림을 보겠습니다.

출처: towardsdatascience

새로운 데이터가 주어졌을 때 (빨간 점) 이를 Class A로 분류할지, Class B로 분류할지 판단하는 문제입니다. k=3일 때, 즉 안 쪽 원을 먼저 살펴보겠습니다. k가 3이라는 것은 가장 가까운 주변의 3개 데이터를 본 뒤, 3개의 주변 데이터가 더 많이 포함되어 있는 범주로 분류하겠다는 것입니다. 빨간 점 주변에 노란색 점(Class A) 1개와 보라색 점(Class B) 2개가 있습니다. 따라서 k=3 일 때는 해당 데이터가 Class B (보라색 점)으로 분류됩니다. k=6일 때를 보겠습니다. 원이 더 커졌습니다. 이제 원 안에 노란색 점 4개와 보라색 점 2개가 있습니다. 따라서 k=6일 때는 노란색 점으로 분류합니다. KNN은 K를 어떻게 정하냐에 따라 결과 값이 바뀔 수 있습니다. K가 너무 작아서도 안 되고, 너무 커서도 안 됩니다. K의 default 값은 5입니다. 가장 가까운 주변 5개 데이터를 기반으로 분류한다는 것입니다. 일반적으로 K는 홀수를 사용합니다. 짝수일 경우 동점이 되어 하나의 결과를 도출할 수 없기 때문입니다.

Lazy Model

KNN의 특징은 훈련이 따로 필요 없다는 것입니다. 다른 모델들은 clf.fit(x_train, y_train)의 코드를 통해 훈련시킵니다. 즉 훈련데이터를 기반으로 모델을 만들고 테스트 데이터로 테스트를 하는 방식입니다. 하지만 KNN은 훈련이 따로 필요 없습니다. 그냥 훈련 데이터를 저장하는 게 훈련의 전부입니다. SVM을 예로 들면, 훈련 데이터를 기반으로 Decision Boundary를 만들고, 그렇게 만든 Decision Boundary를 통해 테스트 데이터를 분류합니다. KNN은 위 그림에서 보는 것과 같이 새로운 데이터가 주어지면 그제야 주변의 k개 데이터를 보고 새로운 데이터를 분류해주지요. 따라서 사전 모델링이 필요 없는 것입니다. real-time 예측이 이루어집니다. 모델을 별도로 구축하지 않는다는 뜻으로 게으른 모델 (Lazy model)이라고 부릅니다. 그렇기 때문에 SVM이나 선형 회귀보다 빠릅니다.

거리 계산

KNN에서는 데이터와 데이터 사이의 거리를 구해야 합니다. 거리를 구하는 방식은 두 가지가 있습니다.

1. 유클리드 거리 (Euclidean Distance)

일반적으로 점과 점 사이의 거리를 구하는 방법입니다. 

출처: Wikipedia

3차원에서 유클리드 거리 구하는 예시입니다.

출처: ratsgo's blog

2. 맨해튼 거리 (Manhattan Distance)

점과 점사이의 직선거리가 아니라 X축, Y축을 따라 간 거리를 의미합니다. 군대에서 했던 직각 보행을 생각하시면 이해하기 쉽습니다. 아래 예시를 보면 Route 1, Route 2, Route 3은 서로 다른 길로 갔지만 X축으로 간 거리, Y축으로 간 거리가 똑같아 맨해튼 거리로는 똑같습니다. 맨해튼 시내에 빌딩이 많아 어디에서 어디로 가기 위해서는 격자 모양의 길을 따라가야 한다고 해서 생겨난 말입니다.

출처: friend.tistory.com

실습

유명한 iris 데이터를 활용해서 KNN 분류 실습을 해보겠습니다.

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

url = "https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data"

# Assign colum names to the dataset
names = ['sepal-length', 'sepal-width', 'petal-length', 'petal-width', 'Class']

# Read dataset to pandas dataframe
dataset = pd.read_csv(url, names=names)

dataset.head()

X에 sepal-length 부터 petal-width까지의 feature 데이터만 담고, y에 Class만 담습니다. 그리고 Feature Scaling을 해줍니다. Feature Scaling이란 정규화(Normalization)의 개념으로 보시면 됩니다. 데이터의 크기 분포가 너무 들쑥날쑥할 때 Scale을 상대적으로 잡아주는 것입니다. Feature Scaling에 대한 자세한 사항은 다음에 다루겠습니다. 우선은 정규화한다 정도로만 알고 계시면 되겠습니다. 

# Preprocessing
X = dataset.iloc[:, :-1].values
y = dataset.iloc[:, 4].values

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.20)

#Feature Scaling
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
scaler.fit(X_train)

X_train = scaler.transform(X_train)
X_test = scaler.transform(X_test)

# Training and Predictions
from sklearn.neighbors import KNeighborsClassifier
classifier = KNeighborsClassifier(n_neighbors=5)
classifier.fit(X_train, y_train)

y_pred = classifier.predict(X_test)

# Evaluating the Algorithm
from sklearn.metrics import classification_report, confusion_matrix
print(confusion_matrix(y_test, y_pred))
print(classification_report(y_test, y_pred))

정확도가 100%입니다. 물론 본 데이터에서만 이렇게 나오는 거고 다른 데이터에서는 100%까지 안 나올 수 있습니다.

References

Reference1: Stack Abuse (K-Nearest Neighbors Algorithm in Python and Scikit-Learn)

Reference2: ratsgo's blog (K-Nearest Neighbor Algorithm)

Reference3: sklearn.neighbors.KNeighborsClassifier

Refernece4: WikiPedia (Euclidean distance)