KNN (K-Nearest Neighbor)

Sunday. June 25, 2017

preface 이번 포스트에서는 분류classification 방법론 가운데 하나인 KNN (K-Nearest Neighbor) 에 대하여 설명합니다. 분류classification란 A 그룹과 B 그룹으로 분류된 데이터가 있을 때, 새로 관측된 데이터가 어느 그룹에 속할지 추정하는 것을 말합니다.

알고리즘

다음 자료를 참고하였습니다:

James, et. al. “An Introduction to Statistical Learning with Application in R” (이하 ISLR)

KNN 방법론은 사실 매우 간단한 분류 방법론입니다.

먼저 적절한 K 와 거리측정방법(Distance Metric)을 결정합니다.
새로운 데이터와 기존 데이터 간의 거리를 측정합니다.
가장 가까운 K 개의 샘플(K-Nearest Neighbor)을 뽑습니다. (Outlier 는 제외합니다.)
K 개 샘플 가운데 더 많이 관찰된 그룹으로 새로운 데이터를 분류합니다.
예를 들어 K = 5 이고 가장 가까운 5개 관측치 가운데 A 그룹이 3개, B 그룹이 2개 있다면 A그룹일 확률이 60% 가 됩니다. 확률이 가장 높은 그룹으로 분류합니다.

위 알고리즘을 수식으로 표현하면 아래와 같습니다.

(ISLR eq 2.12):

$\Pr \left( Y = j | X = x_0 \right) = \frac{1}{K} \Sigma_{i \in N_o} I \left( y_i = j \right)$

$N_0$: $K$ points in the training data that are closest to $x_0$

몇 가지 논의가 남아있습니다.

통계적 방법론 가운데 K 가 앞에 나오는 것들은(K-means, K-익명성 등) 대부분 사전에 정의된 K (pre-defined K) 를 씁니다. KNN 역시 이 방법론 만으로는 가장 적절한 K를 찾을 수 없습니다.

두 관측치 사이의 거리를 구하는 방법(Distance Metric)은 여러가지가 있습니다.

Euclidean Distance
가장 기본적인 거리 계산법입니다.

Manhattn Distance
빌딩 사이를 피해간다고 생각하고 모든 x들 사이의 차이와 모든 y들 사이의 차이를 더하는 방법입니다.

KNN은 training data로부터 식별 함수를 학습하는 대신 데이터를 기억하는 방식을 사용합니다. 따라서 학습 과정동안 비용이 들지 않는 lazy learning 이라고 합니다.

KNN in Python

KNN in Python by using user-defined function

먼저 샘플 데이터를 불러와서 training set 과 test set 으로 나눕니다. 데이터는 iris dataset 을 사용하였습니다.

import pandas as pd
import numpy as np
from sklearn.model_selection import train_test_split

names = ['sepal_length', 'sepal_width', 'petal_length', 'petal_width', 'class']
df = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data', header=None, names=names)

# X = np.array(df.ix[:, 0:4])
X = np.array(df.iloc[:, 0:4])
y = np.array(df['class'])

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33, random_state=42)

다음은 KNN 알고리즘을 표현한 사용자 정의 함수입니다.

def knn(k, data, dataClass, inputs):
    nInputs = np.shape(inputs)[0]
    closet = np.zeros(nInputs)

    for n in range(nInputs):
        distances = np.sum((data-inputs[n,:])**2, axis=1)
        indices = np.argsort(distances, axis=0)
        classes = np.unique(dataClass[indices[:k]])

        if len(classes)==1:
            closet[n] = np.unique(classes)
        else:
            counts = np.zeros(max(classes)+1)
            for i in range(k):
                counts[dataClass[indices[i]]] += 1
            closet[n] = np.max(counts)

    return closet

사용자 정의 함수를 이용하여 KNN 방법을 이용하여 분류합니다.

from sklearn.preprocessing import LabelEncoder

le = LabelEncoder()

k = 3
data = X_train[1:,]
dataClass = le.fit_transform(y_train[1:,])

predict = knn(3, data, dataClass, X_test)
predict = le.inverse_transform(predict.astype(int))

다음을 실행하면 예측의 정확도가 계산됩니다.

from sklearn import metrics
metrics.accuracy_score(y_test, predict)

0.9599 가 출력됩니다.

KNN in Python by using scikit-learn

scikit-learn 패키지에서 제공하는 KNeighborsClassifier 함수를 사용하여 분류할 수도 있습니다.

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train, y_train)
pred = knn.predict(X_test)

print(metrics.accuracy_score(y_test, pred))

0.98 이 출력됩니다.

Cross validation

다음 코드를 실행하면 K 값의 변화에 따라 에러가 어떻게 변화하는지 그래프를 통해 알 수 있습니다.

from sklearn.model_selection import cross_val_score
import matplotlib.pyplot as plt

neighbors = list(range(1,10))
cv_scores = []

# perform 10-fold cross validation
for k in neighbors:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X_train, y_train, cv=10, scoring='accuracy')
    cv_scores.append(scores.mean())

MSE = [1 - x for x in cv_scores]

# determining best k
optimal_k = neighbors[MSE.index(min(MSE))]
print("The optimal number of neighbors is %d" % optimal_k)

# plot misclassification error vs k
plt.plot(neighbors, MSE)
plt.xlabel('Number of Neighbors K')
plt.ylabel('Misclassification Error')

Hyeongjun Kim

Financial Economist, Data Scientist, and Hearthstone Player