kNN 알고리즘

kNN algorithm이란?

k-Nearest Neighbor, 즉 kNN 알고리즘은 데이터들을 분류하기 위한 알고리즘 중 하나로, 간단히 말해 근처에 있는 데이터들의 분류를 확인해 해당 데이터의 분류를 결정하는 방식이다.

Wikipedia

초록 원의 분류를 결정해 보자.

• k=1인 경우, 가장 가까운 1개의 데이터를 확인한다. 따라서 이 데이터는 빨간 삼각형 그룹에 속한다.
• k=3인 경우, 가장 가까운 3개의 데이터를 확인한다. 파란 사각형이 1개, 빨간 삼각형이 2개이므로 이 데이터는 빨간 삼각형 그룹에 속한다.
• k=5인 경우, 가장 가까운 5개의 데이터를 확인한다. 파란 사각형이 3개, 빨간 삼각형이 2개이므로 이 데이터는 파란 사각형 그룹에 속한다.

이런 식으로 분류할 데이터와 가장 가까운 k개의 데이터를 확인하여, 그 데이터 내에서 가장 많은 그룹을 따라가는 게 kNN 알고리즘이다.

Distance Metric

이 "가장 가까운"을 판단하기 위한 거리 함수에는 여러 가지가 있다. 우선은 크게 L1과 L2에 대해서만 알아본다.

L1 distance

Manhattan Distance라고도 불리며, 각 차원에 대해 거리를 각각 구하여 더한다. 즉 일직선으로 거리를 구하는 게 아니라, x좌표 차이 + y좌표 차이 + z좌표 차이 + ... 이런 식으로 따로 구해 더한 것이다.

L2 distance

Euclidean Distance라고도 불리며, 우리가 점과 점 사이의 거리라고 하면 보통 생각하는 그 직선거리 맞다. 각 차원별 차이값의 제곱을 모두 더해 제곱근하는 방식이다. 앞서 경사 하강법에 대해 살펴볼 때도 Loss function으로 이를 사용했는데, 마찬가지로 앞서 설명했듯 제곱근을 해 봤자 별로 달라지는 게 없어서 그냥 각 차원별 거리의 제곱의 합으로만 표현되기도 하는 듯 하다.

k의 결정

k=1이면 데이터의 모든 영역을 딱 떨어지게 그룹화할 수 있지만, 가끔 그룹에서 튀어나와 있는 "outlier"에 의해 그 경계선이 깔끔하지 못할 수 있다는 문제가 있다.

이런 식으로.

k 값을 늘리면 이러한 outlier의 영향을 덜 받으며, 경계선 또한 부드러워지지만 근처 그룹들과의 거리가 전부 똑같아서 그룹을 결정짓지 못는 회색지대가 생기는 문제가 있다.

k=3인 경우. 흰 부분이 회색지대다.

아래의 링크에서 kNN을 직접 테스트해 볼 수 있다. L1, L2 metric 또한 비교 가능하다.

http://vision.stanford.edu/teaching/cs231n-demos/knn/

 

kNN의 장단점

• 장점: 간단하다. 학습도 필요 없다(학습 시간 복잡도가 O(1)).
• 단점: 데이터가 중간에 추가되면 다시 처음부터 전부 kNN을 찾아야 하기 때문에 시작부터 모든 데이터 정보를 알고 있어야 하데며, 데이터와 클래스 수에 따른 메모리 용량과 컴퓨팅에 부하가 크다. 추론 시간 복잡도가 O(N)으로, 학습 시간은 느려도 되지만 동작은 빨라야 하는데 이건 별로 좋지 않다.

하이퍼파라미터

이렇게 learning rate, k, Distance Metric과 같이 기계학습 프로세스의 세부 사항을 지정하는 매개변수들을 하이퍼파라미터(Hyperparameter)라고 부른다. 이건 우리가 직접 지정해 줘야 하는 부분인데, 그렇다면 가장 알맞은 하이퍼파라미터는 어떻게 찾을까?

1. 내 학습 데이터셋에 가장 잘 맞는 하이퍼파라미터 선택

가장 좋지 못한 생각이다. 그냥 k=1로 해버리면 학습 데이터에 대해서는 항상 정확도 100%가 나오지 않겠는가? 우리는 학습시키지 않은 데이터에 대해서도 맞춰낼 수 있도록 하는 hyperparameter가 필요하다.

2. 데이터셋을 학습용과 테스트용으로 분리

dataset을 train과 test로 분리해, train 데이터로 학습하여 test 데이터에서 가장 잘 동작하는 하이퍼파라미터를 선택한다. 그나마 낫지만, 테스트 데이터에 대해서만 최적화해놨을 뿐이지 새로운 데이터에 대해 어떻게 동작할지를 모른다는 건 여전히 문제이다.

3. 데이터셋을 학습, 검증, 테스트용으로 분리

dataset을 train, validation, test로 분리한다. train 데이터로 학습한 내용을 validation 데이터로 검증하여, 가장 나은 hyperparameter를 고른다. 그리고 이걸로 테스트 데이터에서 최종 테스트하는 방법이다. 퍼포먼스 확인에 가장 바람직한 방법이다.

3-1. 교차검증

validation 데이터를 따로 빼 두지 않고, train 데이터를 몇 개의 "fold" 로 나눈다. 한 번은 1번 fold를 validation 데이터로 선택하고, 다음엔 2번, 다음엔 3번... 이런 식으로 각각을 검증 데이터로 선택해 학습시킨 뒤 결과들의 평균을 낸다.

데이터셋 규모가 작은 경우엔 유용하지만, 보통 딥러닝에서는 너무 번거로워서? 잘 사용되지 않는 방법이다.