K-최근접 이웃(K-Nearest Neighbors, K-NN)

K-최근접 이웃

K-최근접 이웃(K-NN)은 '유유상종'이라는 사자성어에 맞는 머신 러닝이다.

K-NN 알고리즘은 지도 학습의 한 종류로 데이터를 가장 가까운 유사 속성에 따라 분류하는 거리기반 분류 분석 모델이다.

거리 기반으로 분류하는 클러스터링과 유사한 개념이긴하나, 기존 관측치의 Y값(Class)이 존재한다는 점에서 비지도학습에 해당하는 클러스터링과 차이가 있다.    

 

K-NN 알고리즘은 거리를 측정할 때 유클리디안 거리 계산법을 사용한다. 

유클리디안 거리 계산법은 N차원의 공간에서 두 점간의 거리를 알아내는 공식으로 'L2 Distance'라고도 한다.  

 

 

K-NN 장단점

장점

• 단순하고 효율적이다. 
• 기저 데이터 분포에 대한 가정을 하지 않는다
• 훈련 단계가 빠르다
• 수치 기반 데이터 분류 작업에서 성능이 우수하다. 

단점

• 모델을 생성하지 않아 특징과 클래스간의 관계를 이해하는데 제한적이다.
• 적절한 K의 선택이 필요하다.
• 데이터가 많아지면 분류 단계가 느리다.
• 명목 특징 및 누락 데이터를 위한 추가 처리가 필요하다. 
  • 명목 특징을 수치 형식으로 변환하는 것을 '더미 코딩'이라고 한다. 
    유클리드 거리 계산법은 명목 데이터에 정의되지 않아 수치 형식으로 변환할 필요가 있는데 이를 위한 방법으로 '더미 코딩'을 활용한다 . 
    
    '더미 코딩' 예시
    남성과 여성이 있는 성별 범주 변수를 사용할 때 수치형으로 변환하는 작업

 

 

K-NN에서 K값 정하는 법

K값은 분류하는 데이터 포인트와 가장 가까운 K개의 이웃 데이터 포인트를 선택하는 데 사용된다. 

K값을 선택하는 것은 알고리즘이 어떻게 작동할지에 영향을 미치기 때문에 중요한데, 이런 K값을 정하기 위해서 신경을 써야하는 부분은 정규화와 K 개수 선택 두 가지가 있다. 

 

정규화

예를 들어 성인 남녀의 연봉과 시력을 특정으로 생각했을 때 연봉 단위가 원이면 편차가 천만 단위를 넘어갈 것이고 시력은 소숫점까지 따져가며 최대값과 최소값의 편차가 10 미만일 것이다. 이 두 기준을 똑같이 고려해서 반영하면 연봉이 압도적으로 반영되기 때문에 터무니없는 결론이 나올 것이다. 

그래서 모든 특성을 고르게 반영하기 위해 정규화(Normalization)을 해야 한다. 

 

정규화를 하는 방법에는 여러가지가 있지만 가장 널리 사용되는 방법은 두 가지다. 

1. 최소값을 0, 최대값을 1로 고정한 뒤 모든 값을 0과 1 사이 값으로 변환하는 방법
2. 평균과 표준편차를 활용해서 평균으로부터 얼마나 떨어져있는지 z-점수로 변환하는 방법 

물론 정규화가 언제나 능사는 아닐 것이지만 정규화를 하면 어느정도는 해결이 된다.  

 

 

K 개수 선택

K 개수를 선택하는 것은 모든 값을 실제로 테스트하면서 분류 정확도(Accuracy)를 계산하는과정에서 단서를 찾을 수 있다. 

• K가 너무 작을 때 : Overfitting
  K가 너무 작으면 분류 정확도가 상당히 낮아진다. 시야가 좁아지고 근처에 있는 아주 작은 점 하나에 민감하게 영향을 받기 때문이다. 이를 과적합(overfitting)이라고 한다. 
  K-NN 알고리즘에서는 주변 다른 이웃들까지 충분히 고려하지 않았을 때 overfitting이 발생하고, 하나의 이상치(outlier)가 있을 경우 근처에 있는 점의 레이블이 그 이상치에 의해 결정될 수 있다. 
  또한, K값이 작으면 잡음과 이상치 등의 노이즈를 포함하기가 쉽다. 
  
  위 그림을 이용해 좀 더 쉽게 설명하자면, 그림 왼쪽 상단의 검은색 공은 이상치인 것으로 보이지만 K = 1인 경우 그 근처에 데이터가 위치하면 초록색으로 분류되는 것이 아니라 이상치를 따라 검은색으로 분류된다.  
  
  
•  K가 너무 클 때 : Underfitting
  K가 너무 크면 과소적합(underfitting)이 발생한다. 
  과소적합은 분류기가 학습 세트의 세세한 부분에 충분히 주의를 기울이지 않았기 때문에 나타난다. 
  K값이 크면 많은 이웃을 포함하기 때문에 잡음과 이상치 등 노이즈의 영향은 줄지만 데이터 포인트 주변의 세부적인 특성을 파악하기는 어렵다.  

K값이 작아도, 많아도 정확도가 떨어지기 때문에 정확도를 확인하며 적절한 K값을 정하는 것이 좋다. 

 

 

K-NN 정확도

그리드 서치 교차검증(GridsearchCV)을 통해 성능이 높은 파라미터 K값을 찾을 수 있다.  

위 그래프를 설명하면 아래와 같다.

• k가 1~10 정도 일때는 Underfitting으로 정확도가 65% 정도로 낮을 것을 볼 수 있다.
• K가 100을 넘어가면 Overfitting되어 정확도가 70% 정도로 떨어진다.
• k가 75정도일 때, ACC가 73% 정도로 가장 높으니 적절한 k값이라고 볼 수 있다.

 

 

K-NN 코드공부

https://github.com/DIB-PP/Machine-Learning

GitHub - DIB-PP/Machine-Learning

 

 

 

 

 

 

 

 

 

 

참고 사이트 

• https://m.blog.naver.com/bestinall/221760380344
• https://blog.naver.com/bsw2428/221388885007
• https://d-craftshop.tistory.com/8
• https://velog.io/@hyesoup/KNN-K-Nearest-Neighbor-%EA%B0%9C%EB%85%90
• https://blog.naver.com/bsw2428/221388885007
• https://velog.io/@deep-of-machine/ML-K-Nearest-Neighbor-KNN-K-%EC%B5%9C%EA%B7%BC%EC%A0%91-%EC%9D%B4%EC%9B%83