3.7 k-최근접 이웃: 게으른 학습 알고리즘
이 장에서 언급할 마지막 지도 학습 알고리즘은 k-최근접 이웃(K-Nearest Neighbor, KNN)입니다. 이 알고리즘은 지금까지 설명했던 학습 알고리즘과는 근본적으로 다릅니다. KNN은 전형적인 게으른 학습기(lazy learner)입니다. 단순하기에 게으르다고 말하는 것이 아니라 알고리즘은 훈련 데이터에서 판별 함수(discriminative function)를 학습하는 대신 훈련 데이터셋을 메모리에 저장하기 때문입니다.
Note ≡ 모수 모델 vs 비모수 모델
머신 러닝 알고리즘은 모수 모델(parametric model)과 비모수 모델(nonparametric model)로 묶을 수 있습니다. 모수 모델은 새로운 데이터 포인트를 분류할 수 있는 함수를 학습하기 위해 훈련 데이터셋에서 모델 파라미터를 추정합니다.32 훈련이 끝나면 원본 훈련 데이터셋이 더 이상 필요하지 않습니다. 전형적인 모수 모델은 퍼셉트론, 로지스틱 회귀, 선형 SVM입니다. 반대로 비모수 모델은 고정된 개수의 파라미터로 설명될 수 없습니다. 훈련 데이터가 늘어남에 따라 파라미터 개수도 늘어납니다. 지금까지 본 모델 중 비모수 모델 두 개는 결정 트리/랜덤 포레스트와 커널 SVM입니다.33
KNN은 비모수 모델에 속하며 인스턴스 기반 모델이라고 합니다. 인스턴스 기반 모델은 훈련 데이터셋을 메모리에 저장하는 것이 특징입니다. 게으른 학습은 인스턴스 기반 학습의 특별한 경우이며 학습 과정에 비용이 전혀 들지 않습니다.
KNN 알고리즘은 매우 간단해서 다음 단계로 요약할 수 있습니다.
1. 숫자 k와 거리 측정 기준을 선택합니다.
2. 분류하려는 샘플에서 k개의 최근접 이웃을 찾습니다.
3. 다수결 투표를 통해 클래스 레이블을 할당합니다.
그림 3-26은 새로운 데이터 포인트(물음표로 표시된 포인트)가 어떻게 이웃 다섯 개의 다수결 투표를 기반으로 삼각형 클래스 레이블에 할당되는지 보여 줍니다.
▲ 그림 3-26 k-최근접 이웃의 다수결 투표
선택한 거리 측정 기준에 따라서 KNN 알고리즘이 훈련 데이터셋에서 분류하려는 포인트와 가장 가까운 (가장 비슷한) 샘플 k개를 찾습니다. 새로운 데이터 포인트의 클래스 레이블은 이 k개의 최근접 이웃에서 다수결 투표를 하여 결정됩니다.
이런 메모리 기반 방식의 분류기는 수집된 새로운 훈련 데이터에 즉시 적응할 수 있는 것이 주요 장점입니다. 새로운 샘플을 분류하는 계산 복잡도는 단점입니다. 데이터셋의 차원(특성)이 적고 알고리즘이 k- d 트리 같은 효율적인 데이터 구조로 구현되어 있지 않다면 최악의 경우 훈련 데이터셋의 샘플 개수에 선형적으로 증가합니다.34, 35 또 훈련 단계가 없기 때문에 훈련 샘플을 버릴 수 없습니다. 대규모 데이터셋에서 작업한다면 저장 공간에 문제가 생깁니다.
다음 코드를 실행하면 유클리디안(euclidean) 거리 측정 방식을 사용한 사이킷런의 KNN 모델을 만듭니다.
>>> from sklearn.neighbors import KNeighborsClassifier
>>> knn = KNeighborsClassifier(n_neighbors=5, p=2,
... metric='minkowski')
>>> knn.fit(X_train_std, y_train)
>>> plot_decision_regions(X_combined_std, y_combined,
... classifier=knn, test_idx=range(105, 150))
>>> plt.xlabel('petal length [standardized]')
>>> plt.ylabel('petal width [standardized]')
>>> plt.legend(loc='upper left')
>>> plt.tight_layout()
>>> plt.show()
KNN 모델에 다섯 개의 이웃을 지정했으므로 이 데이터셋에서 그림 3-27과 같이 비교적 부드러운 결정 경계를 얻었습니다.
▲ 그림 3-27 k-최근접 이웃 모델이 학습한 붓꽃 데이터셋의 결정 경계
Note ≡ 동점 처리
다수결 투표가 동일할 경우 사이킷런의 KNN 구현은 분류하려는 데이터 포인트에 더 가까운 이웃을 예측으로 선택합니다. 이웃들의 거리가 같다면 훈련 데이터셋에서 먼저 나타난 샘플의 클래스 레이블을 선택합니다.
적절한 k를 선택하는 것은 과대적합과 과소적합 사이에서 올바른 균형을 잡기 위해 중요합니다. 데이터셋의 특성에 알맞은 거리 측정 지표를 선택해야 합니다. 붓꽃 데이터셋의 센티미터 단위를 가진 특성처럼 실수 값을 가진 특성에는 보통 간단한 유클리디안 거리를 사용합니다. 유클리디안 거리를 사용하려면 각 특성이 동일하게 취급되도록 표준화를 하는 것이 중요합니다. 앞 코드에서 사용한 minkowski 거리는 유클리디안 거리와 맨해튼(Manhattan) 거리를 일반화한 것으로 다음과 같이 쓸 수 있습니다.
매개변수 p=2로 지정하면 유클리디안 거리가 되고 p=1로 지정하면 맨해튼 거리가 됩니다.36 사이킷런에는 다른 거리 측정 기준이 많으며 metric 매개변수로 지정할 수 있습니다. 다음 주소를 참고하세요.
https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.DistanceMetric.html
Note ≡ 차원의 저주
KNN은 차원의 저주 때문에 과대적합되기 쉽다는 것이 중요합니다. 차원의 저주(curse of dimensionality)는 고정된 크기의 훈련 데이터셋이 차원이 늘어남에 따라 특성 공간이 점점 희소해지는 현상입니다.37 고차원 공간에서는 가장 가까운 이웃이라도 좋은 추정 값을 만들기에는 너무 멀리 떨어져 있다는 뜻입니다.
로지스틱 회귀에 관한 절에서 과대적합을 피하기 위한 방법으로 규제 개념을 설명했습니다. 결정 트리나 KNN처럼 규제를 적용할 수 없는 모델38에서는 특성 선택과 차원 축소 기법을 사용하면 차원의 저주를 피하는 데 도움이 됩니다. 이는 다음 장에서 자세히 설명하겠습니다.