K-Nearest Neighbors(KNN)

• k의 개수만큼 주변에 있는 sample들의 정보를 이용해서 새로운 관측치의 종속변수를 예측하는 방법이다. 아래 그림에서 기존의 파란색 네모와 빨간색 세모라는 2가지 클래스를 갖는 데이터 집합이 있다고 할 때, 여기서 새로운 관측치인 녹색에 대해 어떻게 예측할지를 생각해 보자.

  • k=3인 경우(실선): 빨간색 세모로 분류될 가능성이 높다.
  • k=5인 경우(점선): 파란색 네모로 분류될 가능성이 높다.
    • 허나, k=5인 경우 빨간색 세모와의 거리가 더 가깝기 때문에 그만큼의 weight를 주어서 갯수를 떠나서 빨간색으로 분류될 가능성도 알고리즘에 따라 존재한다.

K-Nearest neighborhood

• 그렇다면 voting 방식외에도 관측치들간의 distance에 따른 가중치를 주는데 여기서 거리를 구하는 방법은 아래 그림과 같은 방법들이 존재한다. 물론, 이 밖에도 데이터의 거리를 구하는 방법은 더 많이 존재한다. 대표적인 유클리디안 거리와 맨하탄 거리, 그리고 범주형 변수에 사용되는 Hamming distance를 간단히 보여 줄 것이다. 유클리디안 거리는 우리가 잘 알고있는 피타고라스 정리에 의해 두 지점 사이의 최단 거리를 구하는 공식으로 계산되며, 맨하탄 거리는 맨하탄 같이 블록별로 되어있는 곳에서의 거리를 계산할 경우 사용된다. 마지막으로 Hamming distance를 계산하는 방식은 Indicator함수안의 조건이 참인 경우만을 1로 값을 산출하여 합한 값이다. 즉, 쉽게 말하면 해당 이진값들의 자리에서 다른 곳이 존재하는 개수를 의미한다.

• 먼저 독립 변수와 새로이 예측하려는 관측값과의 거리를 따져 가장 가까운 데이터부터 순서대로 정렬해 놓는다. 통계적으로 순서 통계량이라고 할 수 있다. 그에 따른 순서로 독립변수와 종속 변수의 쌍으로 정렬한다. 여기서의 거리는 위에서 언급했던 방법들을 사용한다.

• 종속변수가 범주형이라면 아래와 같이 소프트 보팅방법으로 확률을 구해 확률값이 가장 큰 클래스를 예측값으로 채택한다. 물론, 범주형 변수도 연속형 변수처럼 거리에 의한 가중치를 사용할 수 있다.

• 종속변수가 연속형인 경우는 평균을 구하는데, 거리에 따른 가중치를 두어 가중평균을 구하는 것이 일반적이다. 가중치는 거리에 반비례하게 하여 거리가 짧을수록 큰 가중치를 갖게 한다.

Cross validation

• 교차검증(Cross validation)은 기본적으로 과적합에 대한 방지를 위해서 실행하며, 또 다른 이유로는 sample loss에 관한 측면이 존재한다.

• 과적합(Overfitting)문제는 Training set에만 최적화 되어있어 새로운 데이터가 들어왔을 때 기존의 Training set에 이질적으로 처리하기 때문이다. 이는 모델의 복잡도와도 밀접한 연관이 있다. 모델의 복잡도가 높을수록 Training set은 잘 맞추지만, Test set에 대한 성능은 낮을 가능성이 높다. 그렇다고 너무 간단하게 만들어버려도 Training set과 Test set 모두에 대해 대한 성능이 좋지 않을 것이다.

• Training error는 error를 과소추정하는 성향이 있다는 말은 아래 그래프를 살펴보면서 설명하겠다. KNN 모델의 경우 K가 작을수록 모델의 복잡도는 높을 것이다. 가장 복잡한 k=1인 경우 Training error는 거의 0에 수렴한다. 허나, Test error는 상당히 높다. 즉, 과적합이 발생되었다는 이야기이다. 여기서 알 수 있는 것은 Training error로 모델을 선택한다면 너무 복잡한 모델을 선택하여 과적합을 발생시켜 Test error가 커지게 될 시킬 수 있다는 점이다.

• 또한, Test error를 구하기 위해 처음에 Train set, Test set으로 나누어야 하기에 Test set으로 나눈만큼의 데이터 소실로 인해 Test error는 증가하게 된다. 이렇게 Error를 과소추정하지 않기 위해서는 교차검증을 해야 할 것이다.

• 이러한 과적합을 방지하고자 CV를 실행하는데 그 중 K-hold Cross validation은 다음과 같은 방법으로 진행한다.

• Loss function은 예로 들어놓은 것인데, 해당 문제의 성능지표를 의미한다.

KNN의 심화적 이해

• 데이터에 따라 적절한 K가 다른데 아래 그림에서와 같이 너무 K를 작게 설정하면, Train set은 굉장히 잘 설명하지만 Test set에 대해선 성능이 안좋게 되는 과적합이 발생될 수 있다. 그 다음으로는 K=1로 설정했을 경우 이상치와의 거리가 가장 가까운 데이터에 영향을 줄 것이다. 아래의 예시 그래프 처럼 영역이 불연속적이어서 영역을 나누는 의미가 없어 보이는 경우가 발생 될 수 있다. 반대로 K가 너무 크다면 미세한 경계에 분류가 아쉬울 것이다.

• 데이터에 따라 적절한 K가 다르므로 Test error를 작게하는 k를 선택해야 할 것이다. Cross-validation을 이용하여 보통 모형의 모수들을 조절하게 된다. 그 중 검증 데이터에 대한 성능이 좋은 모수를 채택하여 최종적으로 test 데이터를 예측하는 것이다.

• 지난 번에 언급했던 차원의 저주와 KNN 알고리즘도 밀접한 관련이 있다. 차원의 저주는 차원이 늘어남에 따라 우리가 설명하고 싶은 공간 대비 설명할 수 있는 공간이 줄어드는 문제인데, 아래 그림에서와 같이 가로축 변수만을 사용한다면 충분히 두 클래스를 나눌 수 있는 기준을 설정할 수 있지만, 오히려 세로축에 의해서는 클래스를 구분하는데 아무런 영향을 주지 않는데 세로축 변수도 고려하게 되면서 다른 예측을 하게 된다.

k-Nearest Neighborhood Algorithm 실습

1. 데이터, 모듈 불러오기 및 kNN 피팅 방법

import modin.pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn import neighbors, datasets
from sklearn.metrics import confusion_matrix

• iris 데이터를 사용할 것이다.

iris = datasets.load_iris()

X = iris.data[:, :2]
y = iris.target

• 모델 구축
  • neighbors를 5로 설정

clf = neighbors.KNeighborsClassifier(n_neighbors=5)
clf.fit(X,y)
y_pred=clf.predict(X)

confusion_matrix(y,y_pred)

결과

array([[49,  1,  0],
       [ 0, 38, 12],
       [ 0, 12, 38]])

2.Cross-validation을 활용한 최적의 k찾기

from sklearn.model_selection import cross_val_score

k_range = np.arange(1,100)
k_scores = []

for k in k_range:
    knn=neighbors.KNeighborsClassifier(k)
    scores= cross_val_score(knn, X, y, cv=10, scoring="accuracy")
    k_scores.append(scores.mean())

plt.plot(k_range, k_scores)
plt.xlabel('Value of K for KNN')
plt.ylabel('Cross-validated accuracy')
plt.show()

• 이렇게 적절한 모수를 찾는 방법은 위에서와 같이 직접 grid search를 하는 방법을 주로 사용한다.

2.Weight를 준 kNN

• 거리를 가중치로 사용한 경우가 좀 더 decision boundary가 매끄럽게 연결되어 있다. 좀 더 보편적인 모델인 것이다.

n_neighbors = 40

h = .02  # step size in the mesh

cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])

for weights in ['uniform', 'distance']:
    clf = neighbors.KNeighborsClassifier(n_neighbors, weights=weights)
    clf.fit(X, y)

    # Plot the decision boundary. For that, we will assign a color to each
    # point in the mesh [x_min, x_max]x[y_min, y_max].
    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])

    # Put the result into a color plot
    Z = Z.reshape(xx.shape)
    plt.figure()
    plt.pcolormesh(xx, yy, Z, cmap=cmap_light)

    # Plot also the training points
    plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold,
                edgecolor='k', s=20)
    plt.xlim(xx.min(), xx.max())
    plt.ylim(yy.min(), yy.max())
    plt.title("3-Class classification (k = %i, weights = '%s')"
              % (n_neighbors, weights))

plt.show()

np.random.seed(0)
X = np.sort(5 * np.random.rand(40, 1), axis=0)
T = np.linspace(0, 5, 500)[:, np.newaxis]
y = np.sin(X).ravel()
y[::5] += 1 * (0.5 - np.random.rand(8))

knn = neighbors.KNeighborsRegressor(n_neighbors)
y_ = knn.fit(X, y).predict(T)

• 이웃을 하나만 사용할 때는 훈련 세트의 각 데이터 포인트가 예측에 주는 영향이 커서 예측값이 훈련 데이터 포인트를 모두 지나간다. 이는 매우 불안정한 예측을 만들어 낸다. 이웃을 많이 사용하면 훈련 데이터에는 잘 안 맞을 수 있지만 더 안정된 예측을 얻게 된다. 또한 Uniform하게 모두 동일한 가중치를 사용해서 계산하는 것보다 때론 거리를 통해 가중치를 주는 편이 아래 그림에서와 같이 좀 더 예측하는 데 효과가 있을수도 있다.

n_neighbors = 5

for i, weights in enumerate(['uniform', 'distance']):
    knn = neighbors.KNeighborsRegressor(n_neighbors, weights=weights)
    y_ = knn.fit(X, y).predict(T)

    plt.subplot(2, 1, i + 1)
    plt.scatter(X, y, c='k', label='data')
    plt.plot(T, y_, c='g', label='prediction')
    plt.axis('tight')
    plt.legend()
    plt.title("KNeighborsRegressor (k = %i, weights = '%s')" % (n_neighbors,
                                                                weights))

plt.tight_layout()
plt.show()

장단점과 매개변수

• 일반적으로 KNeighbors 분류기에 중요한 매개변수는 두 가지이다. 데이터 포인트 사이의 거리를 재는 방법과 이웃의 수이다. 실제로 이웃의 수는 3개나 5개 정도로 적을 때 잘 작동하지만, 이 매개변수는 잘 조정해야 합니다.

• k-NN의 장점은 이해하기 매우 쉬운 모델이라는 점이다. 그리고 많이 조정하지 않아도 자주 좋은 성능을 발휘한다. 더 복잡한 알고리즘을 적용해보기 전에 시도해볼 수 있는 좋은 시작점이다. 보통 최근접 이웃 모델은 매우 빠르게 만들 수 있지만, 훈련 세트가 매우 크면 (특성의 수나 샘플의 수가 클 경우) 예측이 느려진다. k-NN 알고리즘을 사용할 땐 데이터를 전처리하는 과정이 중요하다. 그리고 (수백 개 이상의) 많은 특성을 가진 데이터셋에는 잘 동작하지 않으며, 특성 값 대부분이 0인 (즉 희소한) 데이터셋과는 특히 잘 작동하지 않는다.

• k-최근접 이웃 알고리즘이 이해하긴 쉽지만, 예측이 느리고 많은 특성을 처리하는 능력이 부족해 현업에서는 잘 쓰지 않는다.