[ML] KNN(k-Nearest Neighbor)

728x90

KNN 에 대해 알아보기 전에, 먼저 Lazy learning과 Eager learning 에 대해서 알아보자.

Lazy learning vs Eager learning

- Lazy learning : 그냥 training data를 저장하기만 한다(최소한의 processing을 하기도 함). 그리고 test tuple 이 주어질 때까지 기다린다. ( 모델 미리 만들어두지 않음)

- Eager learning : training set이 주어지면, new data(classify를 하려고 하는 data)가 들어오기 전에 미리 classification model을 만들어 둔다.

그렇다면, knn은 lazy learning 일까, eager learning 일까?

knn은 전형적인 lazy learning으로, 우리가 궁금해하는, 즉 어떤 class 인지 궁금한 data를 넣기 전에는 training data 들을 그저 저장만 하고 있으며, model을 미리 만들어두지 않는다.

과연 어떤 알고리즘을 이용하기에 미리 model을 만들어두지 않아도 되는 것인가?

만약 어떤 동물이 test record 로 들어왔다고 생각해보자.

이 동물을 과연 무엇으로 분류해야 할지가 주 관심사가 될 테고, 만약 이 동물이 duck 처럼 걷고, duck 처럼 꽥꽥거린다면 duck으로 분류할 것이다.

Nearest-Neighbor Classifiers

분류기를 위해서 우리가 필요한 것은 어떤 게 있을까.

- 먼저, record를 가지고 있어야 한다. 즉, training records 가 필요하다.

- 이름에서 알 수 있듯이 test record가 과연 가장 가까운 class가 무엇인지 판별하기 위한 distance metric이 필요하다.

Distance metric 이란 그 가까움의 정도를 어떻게 정의할 것인가? 라고 생각하면 된다.

- k 를 정하는 것 또한 중요하다.

위의 내용을 토대로 분류기가 어떤 역할을 하는지 생각해보자.

먼저, unknown record(test record)가 들어오면, 다른 training records 과의 Distance를 계산한다.

만약, k가 설정이 되어 있다면 그 k 의 값에 따라 가까운 k개의 training records 를 이용해 이 unknown record를 분류한다.(하지만, 단지 그 k개 중에서 다수인 class로 할 것인지, 아니면 가중치를 줄 것인지는 우리가 정의할 필요가 있다)

위의 예에서 만약 가중치가 아닌 그냥 majority의 class로 그 unknown record를 판별한다면,

(a) 는 -

(b) 는 알 수 없음(따라서 이 경우에는 다른 분류 기준이 필요, 가중치 등)

이렇게 말할 수 있다.

Voronoi Diagram

Voronoi Diagram은 1-nearest-neighbor 의 경우에 그릴 수 있는 특별한 형태의 diagram으로 training records 중에 과연 어떤 record에 더 가까운지를 결정하는 boundary를 그린 것이다.

Distance Metric

Distance metric 이란 그 가까움의 정도를 어떻게 정의할 것인가? 라고 했었다.

보통 그냥 Euclidean distance를 많이 사용한다.

이 distance 값을 이용해서 가중치를 주는 등의 여러 기법을 적용할 수도 있다.

다만, 이 euclidean distance와 같은 distance를 이용할 때 주의할 점이 있다.

예를 들어, 미국 돈 1$와 한국 돈 1200\ 을 생각해보자. 두 돈은 같은 가치를 가지지만, 수의 scale 차이는 1200배가 난다. 즉 수만 놓고 봤을 때는 한국돈의 1200이 더 클 수 있다.

따라서 이런 문제를 standardization 등의 방법으로 해결해야 한다.

Choosing the value of k

k 값을 어떻게 정할 것인가도 중요한 문제이다.

만약, k가 너무 작다면, noise에 너무 민감해지는 문제가 생길 수 있고, k가 너무 커지면 실제와는 다른 class를 포함하게 되어 정확도가 낮아질 수 있다. 따라서 이를 정하는 것은, 분석하는 자가 데이터의 양상을 잘 보고 알맞게 설정을 해주어야 한다.

Curse of dimensionality in KNN

낮은 차원(feature가 적은 경우)의 dataset에서는 꽤나 record들 사이에 거리가 작아 정확도가 높을 수 있으나,

높은 차원으로 갈 수록 feature의 개수가 많아지므로 distance 또한 수제곱의 값이 되므로 증가한다.

따라서 records 간의 평균적인 distance가 커지게 되고 이는 nearest neighbor 분류기의 성능을 매우 악화시킨다.

따라서 이를 curse of dimensionality 라고 부른다.

Code 실습

Bream(도미)와 Smelt(방어) 의 두 가지 class를 분류하는, 즉 binary classification을 하는 코드를 살펴보도록 하자.

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]

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]

먼저, bream과 smelt의 length와 weight를 위와 같이 임의로 설정해주었다.

bream은 35, smelt는 14개의 record가 주어졌다.

import matplotlib.pyplot as plt

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

산점도로 찍어보니 위와 같은 양상을 보인다.

bream이 smelth 보다 대체로 weight와 length에서 더 큰 것을 알 수 있다.

length = bream_length+smelt_length
weight = bream_weight+smelt_weight

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

bream과 smelt 두 records 를 합쳐주었다.

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

실제 해당 리스트에서 그 record가 bream 인지 smelt인지를 확인하기 위해서 bream을 1, smelt를 0으로 하여 데이터의 class를 기록해준다.

from sklearn.neighbors import KNeighborsClassifier

kn = KNeighborsClassifier(n_neighbors=3, metric='euclidean')
kn.fit(fish_data, fish_target)

사이킷런의 kn분류기를 사용한다.

k의 값은 3, distance metric은 유클리드 거리로 한다.

newFish = [25, 200]
kn.predict([newFish]) # array([1]) 출력

length가 25, weight가 200인 unknown record를 classify 해보니 1 즉 bream으로 분류했다.

과연 어떻게 bream으로 분류했는지 알아보자.

dist, idx = kn.kneighbors([newFish]) # returns a list of lists
nn_dist = dist[0]	# [[ 42.00190472  90.0093884  140.00803548]] 로 return 해주므로 필요
nn_idx = idx[0]
print(nn_dist)	# [ 42.00190472  90.0093884  140.00803548]
print(nn_idx)	# [0 1 2]

newFish를 분류할 때 가장 가까웠던 record 3개와의 거리와 인덱스를 알아보니

[ 42.00190472 90.0093884 140.00803548]
[0 1 2]

를 얻었다.

dist 는 거리니까 그렇다 치고 idx 로 0 1 2 를 얻었다는 말은 fish 데이터의 첫 3개의 데이터가 가장 가깝다는 뜻이 된다.

import numpy as np
labels = np.array(fish_target)
labels[nn_idx] # array([1, 1, 1])

fish 들의 label 값을 알아보니 0, 1, 2번째 fish는 bream인 것을 확인할 수 있다.

좀 더 시각적으로 확인해보자.

plt.scatter(np.array(fish_data)[nn_idx][:,0],np.array(fish_data)[nn_idx][:,1], 
            facecolors = 'none', c='r', s=80)
plt.scatter(bream_length, bream_weight)
plt.scatter(smelt_length, smelt_weight)
plt.scatter(newFish[0], newFish[1],marker='^', c='r')
plt.xlabel('length [cm]')
plt.ylabel('weight [g]')
plt.show()

코드로 확인하고 예상했던 대로, 우리가 bream 리스트를 만들 때 0, 1, 2 번째 에 있던 [[25.4, 242.0], [26.3, 290.0], [26.5, 340.0]] 의 세 개 데이터가 가장 가까운 record 이다.

fisharr = np.array(fish_data)
diff = fisharr - newFish
diffsq = diff * diff
dist = np.sqrt(np.sum(diffsq, axis=1))

위의 코드는 모든 fish 데이터와 newFish와의 거리를 계산한 코드다.

idx_dist = np.array(range(0,len(diff)))
data = np.vstack((idx_dist,dist)).T

위의 코드는 아래의 모양의 numpy array를 만드는 코드이다.

sorted = data[data[:,1].argsort()]
print(sorted[0:3,])

data 어레이의 1번째 feature의 크기를 기준으로 data를 sort한 결과를 sorted에 대입하니,

[[  0.          42.00190472]
[  1.          90.0093884 ]
[  2.         140.00803548]]

위에서 우리가 얻었던 3가지 record와 같은 distance 가 나온다.

이제, k의 값에 따른 정확도를 한번 알아보자.

kn = KNeighborsClassifier()
kn.fit(fish_data, fish_target)

score = []
for k in range(2,50):
  kn.n_neighbors = k
  score.append(kn.score(fish_data,fish_target))

plt.plot(range(2,50), score)
plt.show()

k가 29일 때 급격하게 정확도가 하락하는데,

smelt의 record의 개수가 14개였으므로 k가 29 이상이면 무조건 bream으로 분류를 해버리기 때문에 이런 결과가 나온다.

scale 의 차이에서 생기는 문제를 한번 알아보자.

from sklearn.model_selection import train_test_split

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

# train_input, test_input, train_target, test_target = train_test_split(
#     fish_data, fish_target, random_state = 42
# )
train_input, test_input, train_target, test_target = train_test_split(
    fish_data, fish_target, stratify=fish_target, random_state = 42)

위의 코드는 train record를 적절한 비율로 train, test 데이터로 나눠주는 것이다.

위의 경우는 train과 test의 데이터 비율이 36 : 13 으로 나누어졌다.

plt.scatter(test_input[:,0],test_input[:,1], 
            facecolors = 'none', c='r', s=80)
plt.scatter(fish_data[:,0],fish_data[:,1])
plt.xlabel('length [cm]')
plt.ylabel('weight [g]')
plt.show()

산점도 그래프로 확인해보니 test 데이터가 골고루 잘 분포하는 것을 확인할 수 있다.

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

100%의 확률로 분류기가 잘 분류하는 것을 확인할 수 있다.

newFish = [30, 150]
plt.scatter(fish_data[:,0],fish_data[:,1])
plt.scatter(newFish[0], newFish[1],marker='^', c='r')
plt.xlabel('length [cm]')
plt.ylabel('weight [g]')
plt.show()

(30, 150)의 새 데이터가 들어온 경우를 생각해보자.

dist, idx = kn.kneighbors([newFish])
plt.scatter(train_input[:,0],train_input[:,1])
plt.scatter(newFish[0], newFish[1],marker='^')
plt.scatter(train_input[idx,0], train_input[idx,1], marker = 'D')
plt.xlabel('length [cm]')
plt.ylabel('weight [g]')
plt.show()

newFish와 가장 가까운 5개의 데이터가 위와 같이 분포해있다.

좀 이상하다고 느껴진다.

육안으로는 분명히 좌측하단에 있는 smelt 데이터들보다 위의 bream 데이터들과 더 가까워보이는데 smelt 데이터들과 더 가깝다고 말한다.

위에서 설명했던 scale 차이에 의한 문제점이 여기서 나온다.

weight의 scale 이 훨씬 크기 때문에 length보다 weight의 차이에 훨씬 더 분류기가 민감하게 반응하는 것이다.

plt.scatter(train_input[:,0],train_input[:,1])
plt.scatter(newFish[0], newFish[1],marker='^')
plt.scatter(train_input[idx,0], train_input[idx,1], marker = 'D')
plt.xlim((0,400))
plt.ylim((0,400))
plt.xlabel('length [cm]')
plt.ylabel('weight [g]')
plt.show()

같은 단위를 그래프에 주고 보니 왜 분류기가 아래의 smelt를 더 가깝다고 판단했는지 이해가 된다.

이때는 weight와 length를 표준화해주면 된다.

mean = np.mean(train_input, axis=0)
std = np.std(train_input, axis=0)
print(mean,std)	# [ 27.29722222 454.09722222] [  9.98244253 323.29893931]

모든 feature들에 대해서 평균과 표준편차를 구해보니 위와 같다.

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

위의 코드에서 training record의 모든 feature에 대해서 표준화를 해주었다.

newFish_scaled = (newFish - mean) / std
print(kn.predict([newFish_scaled]))	# [1]

분명히 아까 smelt와 더 가깝다고(잘못 분류한 것이긴 하지만) 분류했었는데 이제는 bream이라고 classifier가 분류한 것을 알 수 있다.

dist, idx = kn.kneighbors([newFish_scaled])
plt.scatter(train_scaled[:,0],train_scaled[:,1])
plt.scatter(newFish_scaled[0], newFish_scaled[1], marker = '^')
plt.scatter(train_scaled[idx,0],train_scaled[idx,1], marker = 'D')
plt.xlabel('length [cm]')
plt.ylabel('weight [g]')
plt.show()

우리가 원하던대로 표준화가 이루어져서 분류가 되었다.

이렇게 knn의 정의와 아이디어, 알고리즘, 한계점, 마지막으로 문제점과 해결법을 알아보았다.

KNN은 꽤나 오래된 전통적인 ML 알고리즘이지만, 알아둘 필요가 있는 기본적인 알고리즘이다.

//문제제기 및 피드백 언제든지 감사히 받겠습니다.