[알고리즘] K-nearest Neighbors Algorithm(K-NN): K-최근접 이웃 알고리즘

K-nearest Neighbors Algorithm(K-NN)

---

포스트 난이도: HOO_Middle

[Notice] 포스트 난이도에 대한 설명

---

 

# KNN Algorithm

K-NN 또는 KNN이라고 불리는 K-nearest neighbors algorithm은 Pattern 인식 알고리즘의 한 종류이다.

머신러닝(Machine learning)에서 사용되는 알고리즘이며, K-mean clustering algorithm처럼 데이터 집단을 분류하는 데 사용된다.

이 알고리즘을 KNN 또는 최근접 이웃 알고리즘이라고 부르는 이유는 가까운 데이터 또는 노드부터 확인해가며 분류 작업이 이루어지기 때문이다.

KNN 알고리즘을 이해할 때 유의할 점은 KNN 알고리즘과 비슷한 다른 알고리즘들을 헷갈리는 경우가 종종 있다.

패턴 인식, 분류 또는 회귀 부분에서 비슷해 보일 수는 있지만 각 알고리즘마다 특징을 잘 이해하고 파악하는 것이 중요하다.

예를 들어 K 평균 알고리즘과 관련성이 전혀 없고 다른 알고리즘에 해당하기 때문에 헷갈려서 오해하지 않도록 유의해야 한다.

---

# 인스턴스 기반 학습

KNN은 매우 간단한 ML 알고리즘에 해당한다.

왜냐하면 KNN은 인스턴스 기반 학습을 하기 때문이다.

인스턴스 기반 학습이란 모든 데이터 또는 노드가 계산이 이루어지고 분류되는 결과가 산출될 때까지 연기되는 방식을 의미한다.

따라서 이를 ML 중에서도 게으른 학습법이라고도 부른다.

인스턴스 기반 학습법은 사례 기반 학습법이라고도 부르는데, 데이터 또는 노드들을 기억하고 유사도를 기반으로 데이터를 분류하는 학습법을 의미한다.

 

---

# KNN 데이터 또는 노드별 거리 측정

KNN 알고리즘의 경우에도 데이터 또는 노드별 거리 측정이 필요하다.

이때 사용하는 대표적인 방식이 유클리드 거리 공식을 사용하면 된다.

KNN은 유클리드 거리 공식 외에도 해밍거리(Hamming distance)인 중첩 거리를 사용하기도 한다.

Hamming distance의 경우에는 평균, 최고, 최악의 Time complexity가 모두 O(n)에 해당한다.

---

# 다른 알고리즘을 같이 사용하여 응용

KNN 알고리즘은 기본적으로 효율성이 떨어지지만 간단한 기계 학습 알고리즘이다.

따라서 효율성만 높인다면 충분히 조건에 따라 활용도가 높아질 수 있다.

KNN 알고리즘은 다른 알고리즘과 같이 사용되거나 KNN을 기반으로 응용된 버전의 KNN 알고리즘을 사용할 수 있다.

예를 들어 KNN은 SOM과 같이 사용되기도 하며, 인공 신경망 방식과 결합되어 사용된다.

 

---