K-NN(최근접이웃) 알고리즘

K-NN(최근접이웃) 알고리즘 Start

BioinformaticsAndMe

What is a K-NN Algorithm?

---

: K-NN(Nearest Neighbor)는 단순하지만 높은 정확성의 특징으로 널리 사용되는 분류 알고리즘

: K-NN은 사용할 수 있는 모든 경우를 저장하고 Distance measure 등의 유사성에 기반하여, 새로운 정보를 분류하는 단순한 알고리즘

: 객체는 K개의 최근접 이웃 사이에서 가장 공통적인 항목에 할당되는 객체로 과반수 투표에 의해 분류

*예제: 당신은 내가 다음 총선 때 여당과 야당 중 어느 쪽을 지지할지 예측할 수 있는가?

   당신이 나를 전혀 몰라도, 내 주변 이웃들이 지지하는 정당을 안다면, 어느 정도 내 선택을 예측할 수 있다.

How the K-NN algorithm works?

---

: K-NN에서 K는 가장 가까운 이웃의 수 (이웃의 수는 이 알고리즘의 핵심적인 결정 요인)

: 클래스가 두 개인 경우에서 K는 일반적으로 홀수 (K=1 인 경우의 알고리즘은 가장 가까운 인접 알고리즘이라 함)

: 아래 그림은 노랑색 물음표의 Label을 예측하는 상황에서, K=1인 경우, 물음표에 가장 가까운 이웃의 Label을 물음표에 할당

KNN 알고리즘 아래 3단계로 수행된다

1) 가장 가까운 이웃을 찾기 위해, Distance measure를 사용해 이웃 간의 거리를 계산

*Distance measure: Euclidean distance/Manhattan distance/Minkowski distance

2) 거리가 가까운 이웃들 K개 만큼 찾음

3) 찾아진 이웃들을 다수결 투표 원칙으로 기반하여, 신규 데이터 Label 예측 

#일반적으로 사용되는 Euclidean distance measure

How to choose the optimal value of K?

---

: 이웃수 K는 K-NN 모델링에서 입력해야 하는 Hyper-parameter

: 일반적으로 K 값이 커질수록 전체 노이즈가 줄어들면서, 모델의 정확도가 커짐 (항상 그런 것은 아님)

: 대부분의 데이터셋에서 K 값은 3~10 정도를 사용

*Cross-validation을 통해, 적합한 K 값을 찾기도 함

: 보통, 클래스 개수가 짝수인 경우에는 홀수 K 값을 선택함

#Reference

1) https://www.datacamp.com/community/tutorials/k-nearest-neighbor-classification-scikit-learn

2) https://www.kdnuggets.com/2019/07/classifying-heart-disease-using-k-nearest-neighbors.html

3) https://ko.wikipedia.org/wiki/K-%EC%B5%9C%EA%B7%BC%EC%A0%91_%EC%9D%B4%EC%9B%83_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

4) https://kkokkilkon.tistory.com/14

K-NN(최근접이웃) 알고리즘 End

BioinformaticsAndMe