[머신러닝] K-최근접 이웃(K-NN) 알고리즘 및 실습

 

[목차]

1. K-NN 알고리즘이란?

2. K-NN 알고리즘 실습

3. K-NN 알고리즘 실습 (훈련 셋과 데이터 셋 분리)

4. K-NN 알고리즘의 주의점

 

 

  1. K-NN 알고리즘이란?

 

K-최근접 이웃(K-NN, K-Nearest Neighbor) 알고리즘은 가장 간단한 머신러닝 알고리즘으로, 분류(Classification) 알고리즘이다. 비슷한 특성을 가진 데이터는 비슷한 범주에 속하는 경향이 있다는 가정하에 사용한다.

예를 들어 위와 같이 데이터가 주어져 있을 때, 빨간색인 세모 모양의 데이터는 초록색 그룹과 노란색 그룹 중 어디에 속한다고 말할 수 있을까?
주변에 가까운 데이터들이 모두 노란색이기 때문에 '노란색 그룹에 속할 것이다'라고 추측할 수 있다.
이처럼, 주변의 가장 가까운 K개의 데이터를 보고 데이터가 속할 그룹을 판단하는 알고리즘이 K-NN 알고리즘이다.

K-NN 알고리즘은, 단순히 훈련 데이터셋을 그냥 저장하는 것이 모델을 만드는 과정의 전부이다. 그리고 거리를 측정할 땐 유클리드 거리(Euclidean distance)를 사용한다.
K-NN 알고리즘의 특징 중 하나는 K의 값에 따라 분류가 달라질 수 있다는 점이다.
예를 들어 아래와 같은 상황을 보면 K = 1인 경우에는 초록색 그룹이라고 판단하고, K = 3인 경우에는 노란색 그룹이라고 판단할 것이다.

그리고, 항상 분류가 가능하도록 K는 홀수로 설정하는 것이 좋으며, 최선의 K를 선택하는 것은 데이터마다 다르게 접근해야 하는데, 일반적으로는 총 데이터 수의 제곱근 값을 사용한다.

K-NN 알고리즘은 너무나 간단한 알고리즘이지만, 실제로 이미지 처리, 글자/얼굴 인식, 추천 알고리즘, 의료 분야 등에서 많이 사용된다. 그렇다면 장단점은 뭘까?

우선 장점으로는 단순하기 때문에 다른 알고리즘에 비해 구현하기가 쉽다. 또 훈련 데이터를 그대로 가지고 있어 특별한 훈련을 하지 않기 때문에 훈련 단계가 매우 빠르게 수행된다.

다만, 단점으로는 모델을 생성하지 않기 때문에 특징과 클래스 간 관계를 이해하는데 제한적이다. 모델의 결과를 가지고 해석하는 것이 아니라, 미리 변수와 클래스 간의 관계를 파악하여 이를 알고리즘에 적용해야 원하는 결과를 얻을 수 있기 때문이다.
또, 적절한 K의 선택이 필요하고, 훈련 단계가 빠른 대신 데이터가 많아지면 분류 단계가 느리다.

 

  2. K-NN 알고리즘 실습

 

K-NN 알고리즘을 사용하여 2개의 종류를 분류하는 머신러닝 모델을 직접 훈련해보자.
실습 내용은 '혼자 공부하는 머신러닝+딥러닝' 책을 이용하였다.

(데이터셋 출처 : https://www.kaggle.com/aungpyaeap/fish-market)

생선을 분류하기 위해 생선의 길이와 무게를 사용한다. 먼저, 35마리의 도미를 준비하여 도미의 길이(cm)와 무게(g)를 파이썬 리스트로 만들어둔다.

bream_length = [25.4, 26.3, 26.5, 29.0, 29.0, 29.7, 29.7, 30.0, 30.0, 30.7, 31.0, 31.0, 31.5, 32.0, 32.0, 32.0, 33.0, 33.0, 33.5, 33.5, 34.0, 34.0, 34.5, 35.0, 35.0, 35.0, 35.0, 36.0, 36.0, 37.0, 38.5, 38.5, 39.5, 41.0, 41.0] 
bream_weight = [242.0, 290.0, 340.0, 363.0, 430.0, 450.0, 500.0, 390.0, 450.0, 500.0, 475.0, 500.0, 500.0, 340.0, 600.0, 600.0, 700.0, 700.0, 610.0, 650.0, 575.0, 685.0, 620.0, 680.0, 700.0, 725.0, 720.0, 714.0, 850.0, 1000.0, 920.0, 955.0, 925.0, 975.0, 950.0]

이 데이터를 그래프에 점으로 한번 표시해보자. 편의상 앞으로 사용될 모든 데이터는 K_NN_data 모듈에 작성하였다.

from K_NN_data import * 
import matplotlib.pyplot as plt 

plt.scatter(bream_length, bream_weight) 
plt.xlabel('length') 
plt.ylabel('weight') 
plt.show()

matplotlib 패키지는 파이썬에서 과학계산용 그래프를 그리는 대표적인 패키지이다.
scatter 함수는 산점도를 그리는 함수로, 처음 두 매개변수로 x축 값과 y축 값을 전달한다. 이 값은 파이썬 리스트 혹은 넘파이 배열이다. 그래프의 색도 지정할 수 있다.

생선의 길이가 길수록 무게가 많이 나갈 확률이 높기 때문에 위와 같이 그래프가 일직선에 가까운 형태로 나타난다. 이를 선형적이라고 한다.

그리고 분류 작업을 위해, 빙어 14마리의 데이터도 추가하자.

smelt_length = [9.8, 10.5, 10.6, 11.0, 11.2, 11.3, 11.8, 11.8, 12.0, 12.2, 12.4, 13.0, 14.3, 15.0] 
smelt_weight = [6.7, 7.5, 7.0, 9.7, 9.8, 8.7, 10.0, 9.9, 9.8, 12.2, 13.4, 12.2, 19.7, 19.9]

from K_NN_data import * 
import matplotlib.pyplot as plt 

plt.scatter(bream_length, bream_weight) 
plt.scatter(smelt_length, smelt_weight) 
plt.xlabel('length') 
plt.ylabel('weight') 
plt.show()

이제, K-NN 알고리즘을 이용하여 도미와 빙어 데이터를 구분해보자.
우선, 준비한 도미 데이터와 빙어 데이터를 하나의 데이터로 합쳐준다.

length = bream_length + smelt_length 
weight = bream_weight + smelt_weight

앞으로 사용할 머신러닝 패키지는 사이킷런(Scikit-learn)이다. 사이킷런은 파이썬 머신러닝 라이브러리 중 가장 많이 사용되는 라이브러리이다. 이 패키지를 사용하려면 다음처럼 각 특성의 리스트를 세로 방향으로 늘어뜨린 2차원 리스트를 만들어야 한다.

fish_data = [[l, w] for l, w in zip(length, weight)]

zip 함수는 나열된 리스트 각각에서 원소를 하나씩 꺼내 반환한다. 이 함수와 리스트 내포 구문을 이용하면 2차원 리스트를 만들 수 있다.

이제 49마리의 생선 데이터를 준비했으니, 각 생선마다 도미인지 빙어인지를 알려주는 정답 데이터가 필요하다.
임의의 생선이 주어질 때 해당 생선이 도미인지 빙어인지 구분하기 위해선 적어도 기존의 생선들이 도미인지 빙어인지를 알려주어야 하기 때문이다. 따라서 도미를 1로, 빙어를 0으로 나타낸다.

fish_target = [1] * 35 + [0] * 14

그다음엔 사이킷런 패키지에서 이미 구현되어 있는 K-NN 알고리즘 클래스인 KNeighborsClassifier를 import 한다.
그리고 해당 클래스의 객체를 만들어준다.

from sklearn.neighbors import KNeighborsClassifier 
kn = KNeighborsClassifier()

이 객체에 fish_data와 fish_target을 전달해서 도미를 찾기 위한 기준을 학습시킨다. 사이킷런에서 fit() 메서드가 이를 수행하며 이 과정을 훈련이라고 한다.
훈련이 잘 되었는지 평가하기 위해서는 score() 메서드를 사용한다. 0에서 1 사이의 값을 반환하고, 1은 모든 데이터를 정확히 맞혔다는 의미이고, 0.5는 절반의 데이터를 맞혔다는 의미이다.

kn.fit(fish_data, fish_target) 
print(kn.score(fish_data, fish_target)) # 1.0

score 메서드를 수행하면 결과로 1.0이 나오게 된다. 즉, 올바르게 결괏값이 나왔기 때문에 도미와 빙어를 잘 분류했다고 볼 수 있다.

기본적으로 KNeighborsClassifier 클래스는 K의 기본값이 5로 설정되어있다. 이 기준은 n_neighbors 매개 변수로 변경할 수 있다. 만약 총 생선의 수인 49로 바꾸면 어떻게 될까?

kn = KNeighborsClassifier(n_neighbors=49) 
kn.fit(fish_data, fish_target) 
print(kn.score(fish_data, fish_target)) # 0.7142857142857143

K = 49인 경우 어떤 데이터를 넣어도 항상 도미로 예측하기 때문에 정확도를 계산하면 35/49 = 0.7142... 의 결과가 나오는 것을 볼 수 있다. 그러므로 적절한 K를 설정해주는 것이 중요하다.

 

  3. K-NN 알고리즘 실습 (훈련 셋과 데이터 셋 분리)

 

위의 과정을 잘 살펴보면 훈련시킬 때 사용한 데이터를 그대로 테스트하는 것을 알 수 있다. 이미 답을 알고 있는 데이터로 테스트해서 올바른 결과가 도출되는 것을 통해 알고리즘의 성능을 제대로 평가할 수 있을까? 그렇지 않다.
따라서, 알고리즘의 성능을 제대로 평가하기 위해서는 훈련 데이터(Train set)와 평가에 사용될 데이터(Test set)가 달라야 한다.
당연히 각 데이터 셋은 샘플이 골고루 섞여 있어야 한다. 만약 샘플링이 한쪽으로 치우쳐있는 경우를 샘플링 편향(Sampling bias)이라고 부른다.

이제, 데이터를 섞거나 혹은 골고루 샘플을 뽑아서 훈련 셋과 테스트 셋을 만들기 위해서 '넘파이(numpy)'라는 파이썬 라이브러리를 사용해보자. 넘파이는 파이썬의 대표적인 배열(array) 라이브러리이다.

import numpy as np 

input_arr = np.array(fish_data) 
target_arr = np.array(fish_target)

파이썬 리스트를 넘파이 배열로 바꾸는 과정이다. 넘파이 배열을 출력해보면 행과 열이 가지런히 출력된다.

이제 이 데이터에서 무작위로 샘플을 선택해야 한다. (섞은 후 앞의 n개 데이터를 뽑아내도 된다)
이때, input_arr와 target_arr에서 동일한 인덱스에 대응되는 원소는 같이 선택되어야 한다.
따라서 0 ~ 48의 인덱스 중 임의로 35개의 인덱스를 선택한 다음, 해당 인덱스에 해당하는 원소를 뽑아내는 방식으로 훈련 셋을 만들자.

np.random.seed(42) 
index = np.arange(49) # [0, 1, 2, ... , 48] 
np.random.shuffle(index) 

train_input = input_arr[index[:35]] 
train_target = target_arr[index[:35]]

넘파이에서 무작위 결과를 만드는 함수들은 실행할 때마다 다른 결과를 만든다. 일정한 결과를 얻기 위해서는 위처럼 랜덤 시드(Random seed)를 설정해주면 된다.

넘파이는 배열 인덱싱(Array Indexing)이란 기능을 제공한다. 배열 인덱싱은 1개의 인덱스가 아닌 여러 개의 인덱스로 한 번에 여러 원소를 선택할 수 있다. 예를 들어 arr[1], arr[3]이 아니라 arr[[1, 3]]처럼 한 번에 선택할 수 있다.
따라서 위의 코드에서 input_arr[index[:35]]는 index[0] ~ index[34]의 값이 인덱스가 되어 선택된 원소들을 배열로 반환한다.

이제, 나머지 데이터들로 테스트 셋을 만들고 산점도로 그려보면 아래와 같이 잘 섞여있는 것을 볼 수 있다.

만든 훈련 셋과 테스트 셋으로 K-NN 모델을 훈련시켜보자.

kn.fit(train_input, train_target) 
print(kn.score(test_input, test_target)) # 1.0 

print(kn.predict(test_input)) # [0 0 1 0 1 1 1 0 1 1 0 1 1 0] 
print(test_target) # [0 0 1 0 1 1 1 0 1 1 0 1 1 0]

predict 메서드는 새로운 데이터의 정답을 예측한다. 리스트의 리스트를 인자로 넘겨줘야 한다.
출력한 결과 테스트 셋의 예측 결과와 실제 타깃이 일치하는 것을 볼 수 있다.
위 코드의 주석에서 볼 수 있듯이 사이킷런 모델의 입력과 출력은 모두 넘파이 배열인 점을 참고하자.

 

  4. K-NN 알고리즘의 주의점

 

이전의 실습에서 훈련된 모델에 길이가 25cm이고, 무게가 150g인 생선을 테스트해보자.

print(kn.predict([[25.0, 150.0]])) # [0]

분명, 훈련 셋을 참고하면 도미라고 판단해야 할 텐데 빙어라고 예측한다.

위의 산점도를 봐도 도미라고 판단해야 할 것이다. 왜 이런 문제점이 발생할까?

K-NN 알고리즘은 가장 가까운 주변의 K개의 샘플 중 다수인 그룹을 예측으로 사용하므로 주변의 K개의 샘플을 알아보자.

 

kneighbors() 메서드를 사용하면 주어진 샘플에서 가장 가까운 이웃을 찾아준다. 이웃까지의 거리와 이웃 샘플의 인덱스를 반환하고, KNeighborsClassifier 클래스의 n_neighbors의 기본값이 5이므로 5개의 이웃이 반환된다. 

distances, indexes = kn.kneighbors([[25, 150]])

plt.scatter(train_input[:,0], train_input[:,1])
plt.scatter(25, 150, marker='^')
plt.scatter(train_input[indexes, 0], train_input[indexes, 1], marker='D')
plt.xlabel('length')
plt.ylabel('weight')
plt.show()

 

산점도를 그려보면 그림상으론 빙어들의 거리가 굉장히 멀리 있지만, 도미는 1개만 포함되고 나머지 4개의 샘플은 모두 빙어임을 알 수 있다. 실제로 이웃까지의 거리를 출력해보자. 

print(distances) # [[ 92.00086956 130.73859415 137.17988191 138.32150953 138.39320793]]

데이터를 확인해보면, 빨간선으로 나타난 거리가 대략 130이고, 파란선으로 나타난 거리가 약 92로 나타난다. 딱 봐도 거리가 이상하게 나오는 것을 알 수 있다. 

그 이유는, x축은 범위가 좁고 y축은 범위가 넓기 때문이다. 따라서 y축으로 조금만 멀어져도 실제 거리는 아주 크게 증가하게 되므로 도미 샘플들이 이웃에 속하지 못하게 된 것이다. 

 

x축 범위를 y축과 동일하게 표현해보자. x축의 범위 또는 y축의 범위를 조절하려면 xlim, ylim 함수를 사용하면 된다. 

plt.scatter(train_input[:,0], train_input[:,1])
plt.scatter(25, 150, marker='^')
plt.scatter(train_input[indexes, 0], train_input[indexes, 1], marker='D')
plt.xlim((0, 1000))
plt.xlabel('length')
plt.ylabel('weight')
plt.show()

실제로 x는 거리에 영향을 거의 미치지 않는 것을 볼 수 있다. 

이처럼 두 특성의 값의 범위가 매우 다른 경우를 두 특성의 스케일(scale)이 다르다고 말한다.

 

K-NN과 같이 거리 기반 알고리즘을 사용할 땐 데이터를 표현하는 기준이 다르면 알고리즘이 올바르게 예측할 수 없다. 따라서 일정한 기준으로 맞춰주어야 하는데, 이런 작업을 데이터 전처리(Data preprocessing)라고 한다. 

흔히 사용하는 방식으로 최소-최대 정규화(min-max normalization), z-점수 표준화(z-score standardization)가 있다. 

 

최소-최대 정규화는 변수 X의 범위를 0%에서 100%까지로 나타내는 방식이다. 

$X_{new} = \frac{X - min(X)}{max(X) - min(X)}$

 

z-점수 표준화는 변수 X의 범위를 평균으로부터 몇 표준편차만큼 떨어져 있는지를 관점으로 변수를 확대/축소시키는 방식이다. 데이터에서 평균을 뺀 값을 모두 제곱한 다음 평균을 낸 것이 분산이고, 표준편차는 분산의 제곱근이다. 

$X_{new} = \frac{X - mean(X)}{StdDev(X)}$

 

두 방식 중에서는 주로 z-점수 표준화를 많이 사용한다. 최소-최대 정규화는 테스트 셋의 최소/최대가 범위를 벗어나는 경우가 생길 수 있기 때문이다. 본 글에서도 z-점수 표준화를 이용해서 실습을 할 것이다. 

 

넘파이는 편리하게 평균과 표준편차를 계산해주는 함수를 모두 제공한다. 

mean = np.mean(train_input, axis=0)
std = np.std(train_input, axis=0)
print(mean, std) # [ 28.29428571 483.35714286] [  9.54606704 323.47456715]

train_scaled = (train_input - mean) / std

 

axis = 0은 행을 따라 각 열의 통계 값을, axis = 1은 열을 따라 각 행의 통계 값을 계산한다. 

그리고 넘파이는 train_input의 모든 행에서 mean에 있는 두 평균값을 빼주고, std에 있는 두 표준편차를 나누어준다. 이러한 넘파이 기능을 브로드캐스팅(Broadcasting)이라고 한다. 

 

new = ([25, 150] - mean) / std

plt.scatter(train_scaled[:, 0], train_scaled[:, 1])
plt.scatter(new[0], new[1], marker='^')
plt.xlabel('length')
plt.ylabel('weight')
plt.show()

이제 x축과 y축의 범위가 모두 동일하게 바뀐 것을 볼 수 있다. 이 데이터셋을 이용하여 다시 훈련을 해보자. 

kn.fit(train_scaled, train_target)
test_scaled = (test_input - mean) / std

kn.score(test_scaled, test_target) # 1.0
print(kn.predict([new])) # [1]

 

테스트 셋도 동일하게 표준화를 시켜줘야 함을 주의하자. 

새로 훈련시킨 모델에 [25, 150] 데이터를 테스트한 결과 올바르게 도미로 분류한 것을 볼 수 있다. 그러면 5개의 가장 가까운 이웃은 어떻게 바뀌었을까?

 

예상한 결과대로 5개의 가장 가까운 이웃이 모두 도미로 나오게 되었다. 

 

 

 

참고)
- 혼자 공부하는 머신러닝+딥러닝(박해선, 한빛미디어)
- https://m.blog.naver.com/bestinall/221760380344

 

PC로 보시는 것을 권장합니다.
피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^