[ML 머신러닝] K-NN(K-Nearest Neighbor) 알고리즘 개념 및 코드

K-NN 알고리즘이란?

유유상종이라는 속담은 K-NN 알고리즘을 설명하기 좋은 표현이다. K-NN 알고리즘은 머신러닝에서 데이터를 가장 가까운 유사 속성에 따라 분류하여 레이블링하는 알고리즘이다.

유유상종 : 같은 날개를 가진 새들끼리 함께 모인다

즉, 비슷한 속성이나 특성을 가진 것들끼리 가깝게 모여있다는 개념을 기반으로 한다. K-NN 알고리즘은 데이터 포인트를 주변의 'k'개의 다른 데이터의 레이블을 참조하여 분류하는 알고리즘이다.  

 

예를 들어, A라는 사람이 '영웅'이라는 특성을 가진 사람들과 가장 유사하다면, K-NN 알고리즘은 A를 '영웅'으로 분류할 것이다. 반대로 B라는 사람이 '빌런'과 유사한 속성을 가지고 있다면, B를 '빌런'으로 추정할 수 있다.

 

K-NN은 간단한 알고리즘이지만 이미지 처리, 글자 및 얼굴 인식, 영화나 음악 추천, 의료 및 유전자 데이터의 패턴 인식 등 다양한 분야에서 응용됩니다.

 

---

지도학습에 속하는 K-NN 알고리즘

 

K-nn은 지도학습에 한 종류이며, 거리기반 분류 분석 모델이라고 할 수 있다. 지도학습은 데이터의 정답(레이블)을 주고 학습을 시키는 방법이다. 지도학습은 크게 회귀(regression)과 분류(classification)로 나뉘는데, K-NN 알고리즘은 지도학습 중에도 분류에 속한다. 이는 거리기반으로 분류를 수행하기 때문에 비지도학습에 속하는 클러스터링과 유사한 개념이지만, 클러스터링과 달리 기존 데이터의 Y값(레이블)이 존재한다는 점에서 차이가 있다.

 

출처 : https://opentutorials.org/course/4548/28942

---

거리기반 분류 분석 모델 'K-NN'

 

K-NN 알고리즘은 판별하고 싶은 데이터와 가까운 K개의 데이터를 찾아, 해당 데이터의 라벨이 다수인 범주로 분류하는 방식이다. 여기서, '가깝다'는 기준에 대한 설정이 필요하다. K-NN 알고리즘은 거리기반 분류분석 모델로, 거리를 기반으로 분류하는 알고리즘이다. 즉, 데이터 포인트 간의 거리로 정의되며, 거리가 짧을수록 더 가까운 이웃으로 취급된다. 

 

거리 측정 방법

K-NN 알고리즘에서 일반적으로 사용되는 두 가지 거리 측정 방식은 유클리드 거리(Euclidean Distance)와 맨해튼 거리(Manhattan Distance)이다. 물론, 이들 외에도 해밍 거리(Hamming distance) 등등 자주 사용하지는 않는 여러 거리 측정 방식이 있다.

 

1. 유클리드 거리 (Euclidean Distance)

유클리드 거리는 가장 일반적인 거리 측정 방법 중 하나로, 두 점 사이의 직선 거리를 계산한다. 2차원 평면에 서로 다른 두 점 A(x₁, y₁)와 B(x₂, y₂)가 있을 때, 이 둘의 거리 d는 유클리드 거리 계산법에 의해 다음과 같이 나온다. 

​

출처 : https://needjarvis.tistory.com/454

 

유클리드 거리는 직선 거리를 측정하므로, 가장 빠른 경로를 찾을 때 유용하다. 다른 말로, 유클리드 거리는 L2 Distance라고도 불다.

 

2. 맨해튼 거리(Manhattan Distance)

맨해튼 거리는 두 점 사이의 축을 따라 이동하는 거리를 계산한다. 이는 뉴욕시 맨해튼의 격자형 거리 구조에서 유래된 이름이다. 2차원 평면에 서로 다른 두 점 A(x₁, y₁)와 B(x₂, y₂)가 있을 때, 이 둘의 거리는 다음과 같이 계산된다.

 

 

맨해튼 거리는 직선으로 이동할 수 없는 경우, 즉 축을 따라 이동해야 하는 경우에 유용하다. 이 거리는 L1 Distance라고도 불린다.

 

아래의 그림은 맨해튼 거리를 설명하기에 매우 유용한 그림이다. 검은색 두 점의 거리를 측정하려 한다. 

초록색 직선이 바로 위에서 말한 유클리드 거리이다. 바로 검은색 두 점 사이의 최단거리이다.

그리고 나머지 빨간색, 파란색, 노란색 선이 맨해튼 거리를 의미한다. 이 세 선이 모두 맨해튼 거리라는 것은 모두 총 거리가 동일하다는 것이며 이는 실제로 자명한 사실이다.

 

출처 : https://ko.wikipedia.org/wiki/%EB%A7%A8%ED%95%B4%ED%8A%BC_%EA%B1%B0%EB%A6%AC

---

K-NN 알고리즘의 원리

K-NN 알고리즘의 원리를 제대로 이해하기 위한 예시이다.

데이터는 총 6개가 있고 변수에 x와 y가 있다. 그리고 각각의 데이터에는 레이블 값이 있다.(K-NN 알고리즘은 앞서 말했듯이 지도학습이기 때문이다.) 

 

위의 데이터를 그래프를 그려보면 다음과 같다.

 

 

여기서 새로운 데이터 (4, 4)가 추가되어, 레이블 0(보라색)과 1(노란색) 중 하나로 분류해야 한다. 앞서 살펴본 K-NN 알고리즘의 정의에 따라 거리를 기반으로 가장 가까운 K개의 이웃의 값을 참고해서 분류해야한다. 그러기 위해 먼저 K의 값을 지정해야한다.

 

 

k=1, 레이블 0(보라색)으로 분류

k=2, 동률로 분류할 수 없는 상황이다. 즉, 보편적으로 k의 값을 정할 때 동률이 나오지 않도록 홀수로 지정한다

k=3, 레이블 1(노란색)로 분류

k=5, 레이블 2(보라색)으로 분류

 

결과적으로, K의 값에 따라 참고하는 데이터의 개수가 달라지고, 그에 따라 분류되는 레이블이 달라질 수 있다. 따라서, K의 값 선택이 매우 중요하다. (보통 k는 홀수로 선택한다)  K를 잘못 지정하면 예측 결과가 부정확해질 수 있다. 하지만, 데이터의 개수가 많아지면 K의 값에 따른 레이블 변화가 상대적으로 안정되기 때문에, 레이블이 변덕스럽게 바뀌는 현상은 줄어들게 된다. K 값을 최적화하기 위해 교차 검증 등의 방법을 사용하는 것이 좋다.

---

K-NN 알고리즘의 장/단점

K-NN 알고리즘의 장점은 알고리즘이 간단하여 구현하기가 쉽다는 장점이 있다. 그러나, 다른 머신러닝 알고리즘과 달리 모델을 생성하지 않아, 특징과 클래스 간 관계를 이해하는 데 제한적이며, 데이터가 많아질수록 분류 속도가 느려지고 계산량이 많아진다는 단점이 존재한다.

 

* 더미 코딩(Dummy coding) : 명목 특징을 수치 형식으로 변환

명목 데이터에 정의되지 않으므로, 수치 형식으로 변환할 필요가 있는데 이를 위한 방법으로 더미 코딩을 활용할 수 있다.

예를 들어, 남성과 여성 등의 성별 범주 변수를 사용하기 위해 수치 형식(0 or 1)으로 변환하는 작업을 해야한다.

---

K-NN 알고리즘의 구현 시 주의점

K-NN 알고리즘과 같이 거리기반 모델에서는 표준화가 필수적이다. 이는 변수 값의 범위를 조정하여, 각 변수의 중요도를 고르게 해석할 수 있게 하기 위함이다. 만약 변수를 표준화하지 않으면, 값의 범위가 큰 변수가 거리 계산에 더 큰 영향을 미치게 되어 모델의 성능이 저하될 수 있다. 참고로 K-means 알고리즘도 비지도학습에 포함되는 거리기반 분류 알고리즘이라서 마찬가지로 변수 값 범위 재조정이 필요하다. 

 

왜 표준화가 필요한가?

거리 기반 모델에서 거리는 각 변수의 차이에 따라 계산된다. 예를 들어, 아래와 같이  A변수는 1에서 1000 사이의 값을 가지는 반면, B변수는 0에서 1 사이의 값을 가진다면, 첫 번째 변수가 거리 계산에 더 큰 영향을 미치게 된다. 이렇게 되면, 두 변수의 중요도가 왜곡되어 모델의 정확도가 떨어질 수 있다.

 

 

표준화 방법

K-NN 알고리즘을 위해 각 변수들의 범위를 재조정하는 방법으로, 최소-최대 정규화(min-max normalization)와 z-점수 표준화(z-score standardization) 가 있다. 데이터의 특성에 따라 적절히 선택하여 사용해야 한다.

 

 

'최소-최대 정규화'는 변수 X의 값을 0과 1 사이의 범위로 변환하는 방법이다. 이를 통해 모든 변수는 0에서 1 사이의 범위 안에 들어오게 된다.

 

'z-점수 표준화'는 변수 X의 값을 평균으로부터의 표준 편차 단위로 변환하는 방법이다. 평균의 위 또는 아래로 몇 표준 편차만큼 떨어져 있는지 관점으로 변수를 확대/축소하는 방식이다. z-점수는 정규화 값과 달리 미리 정의된 최소값과 최대값이 없다.

---

K-NN 알고리즘의 코드

< 일반 데이터>

 

0. 데이터 셋

# [x, y, type]
dataset = [[2.7810836,2.550537003,0],
   [1.465489372,2.362125076,0],
   [3.396561688,4.400293529,0],
   [1.38807019,1.850220317,0],
   [3.06407232,3.005305973,0],
   [7.627531214,2.759262235,1],
   [5.332441248,2.088626775,1],
   [6.922596716,1.77106367,1],
   [8.675418651,-0.242068655,1],
   [7.673756466,3.508563011,1]]

 

1. 거리 계산하기

# 거리 계산하기 - 유클리드 거리 공식 사용
from math import sqrt
# row = [x,y,type]
def euclidean_distance(row1, row2):
   distance = 0.0
   for i in range(len(row1)-1):
      distance += (row1[i]-row2[i])**2
   return sqrt(distance)

test = [3,3]
for row in dataset:
   distance = euclidean_distance(test, row)
   print(distance)
#아래와 같이 거리 차이 값 출력
# 0.2189163999999999
# 1.534510628
# 0.3965616879999998
# 1.61192981
# 0.06407232000000018
# 4.627531214
# 2.3324412480000003
# 3.922596716
# 5.675418650999999
# 4.673756466

 

2. 가장 근처에 있는 요소 뽑기 (K기준)

#가장 근처에 있는 요소 뽑기 (k기준)
def get_neighbors(train,test_row,num_neighbors):
   distances = list()
   for train_row in train:
      dist = euclidean_distance(train_row,test_row)
      distances.append((train_row,dist))

   distances.sort(key=lambda x:x[1])
   neighbors = list()
   for i in range(num_neighbors):
      neighbors.append(distances[i][0])

   return neighbors

 

좌표 (3,3)이고, K=3으로 설정해서 test 해보면,

neighbors = get_neighbors(dataset, test, 3) # k=3
print(*neighbors)
#아래와 같이 거리 차이 값 출력
#[3.06407232, 3.005305973, 0] [2.7810836, 2.550537003, 0] [3.396561688, 4.400293529, 0]

 

3. 예측하기 - (1) 예측 함수 생성

#예측하기
def predict_classification(train,test_row,num_neighbors):
   neighbors = get_neighbors(train,test_row,num_neighbors)

   output_values = [row[-1] for row in neighbors]
   prediction = max(set(output_values), key=output_values.count)
   return prediction

 

(2) 테스트 데이터 입려하여 예측 값 확인하기

row0 = [3,3,0]

prediction = predict_classification(dataset, row0, 3)
print('Expected %d, Got %d.' % (row0[-1], prediction))
# Expected 0, Got 0.

 

 

< iris 데이터>

0. 데이터 셋

import numpy as np
from sklearn.datasets import load_iris
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split

iris = load_iris()
knn = KNeighborsClassifier(n_neighbors = 3)
X_train, X_test, Y_train, Y_test = train_test_split(iris['data'], iris['target'], test_size=0.25, stratify = iris['target'])

knn.fit(X_train, Y_train)

y_pred = knn.predict(X_test)

print("prediction accuracy: {:.2f}".format(np.mean(y_pred == Y_test)))

# 결과: prediction accuracy: 1.00

 

 

 

 

References

  [1] https://velog.io/@jhlee508/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-KNNK-Nearest-Neighbor-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

  [2] https://m.blog.naver.com/bestinall/221760380344