KNN (K-Nearest Neighbor)

머신러닝 지도학습에서 사용되는 가장 간단하고 직관적인 분류 및 회귀 방법 중 하나인 KNN 방법에 대한 정리

KNN (K-Nearest Neighbors)

• KNN (K-Nearest Neighbors)은 지도 학습 알고리즘의 하나로, 분류(Classification) 및 회귀(Regression) 문제에 모두 사용될 수 있다.
• KNN은 매우 직관적이고 이해하기 쉬운 알고리즘이며, 별도의 훈련 단계가 없다는 특징이 있다.

개요

• 정의: 새로운 데이터 포인트가 주어졌을 때, 기존 데이터 셋에서 가장 가까운 K개의 이웃을 찾아, 이들의 정보를 바탕으로 새로운 데이터 포인트를 예측한다.
• 분류 (Classification): K개의 이웃 중 가장 많은 클래스로 새로운 데이터 포인트를 분류한다.
• 회귀 (Regression): K개 이웃 값들의 평균 또는 가중 평균을 사용하여 새로운 데이터 포인트의 값을 예측한다.
• Lazy Learning: KNN은 훈련 데이터셋을 저장하는 것이 전부이며, 실제 예측 시점에 계산이 이루어지므로 “Lazy Learning”이라고도 불림.

KNN 알고리즘

1. 데이터 준비: 훈련 데이터셋과 테스트 데이터셋을 준비합니다. 훈련 데이터셋은 이미 클래스(분류) 또는 값(회귀)이 할당된 데이터 포인트들로 구성됩니다.

2. 거리 측정: 새로운 데이터 포인트(테스트 데이터)와 훈련 데이터셋의 모든 데이터 포인트 간의 거리를 계산합니다. 일반적으로 유클리드 거리(Euclidean Distance)가 많이 사용되지만, 필요에 따라 다른 거리 측정 방식(맨하탄 거리, 민코프스키 거리 등)을 사용할 수도 있습니다.

   • 유클리드 거리 (Euclidean Distance): 두 점 와  사이의 거리는 다음과 같이 계산됩니다.

   • 맨하탄 거리 (Manhattan Distance):

3. K개의 이웃 선택: 계산된 거리를 기준으로 가장 가까운 K개의 훈련 데이터 포인트를 선택합니다. K는 사용자가 지정하는 파라미터입니다.

4. 예측:

   • 분류 (Classification): 선택된 K개의 이웃 중 가장 많은 클래스를 새로운 데이터 포인트의 클래스로 예측합니다. (다수결 투표)
   • 회귀 (Regression): 선택된 K개 이웃들의 값의 평균을 계산하여 새로운 데이터 포인트의 값으로 예측합니다. 또는, 거리에 따른 가중 평균을 사용할 수도 있습니다. (가까운 이웃일수록 더 큰 가중치를 부여)

5. 결과: 예측된 클래스 또는 값을 반환합니다.

3. K 값 선택

• K 값은 KNN 알고리즘의 성능에 큰 영향을 미칩니다.
• 작은 K 값: 모델이 데이터의 지역적인 특징에 민감하게 반응하여 과적합(Overfitting)될 가능성이 있습니다.
• 큰 K 값: 모델이 데이터의 전체적인 특징을 반영하여 과소적합(Underfitting)될 가능성이 있습니다.
• 적절한 K 값 선택 방법:
  • 홀수 K 값: 분류 문제에서 K를 홀수로 설정하면 동점(tie)이 발생하는 것을 방지할 수 있습니다. (특히 이진 분류 문제)
  • 교차 검증 (Cross-Validation): 다양한 K 값에 대해 교차 검증을 수행하여 최적의 K 값을 찾습니다.
  • Elbow Method: K 값을 변화시키면서 모델의 성능을 평가하고, 성능 변화가 둔화되는 지점을 최적의 K 값으로 선택합니다.

4. 장단점

• 장점:
  • 구현이 간단하고 이해하기 쉽습니다.
  • 별도의 훈련 단계가 필요 없습니다.
  • 비선형 데이터에도 잘 작동합니다.
  • 새로운 데이터 추가에 유연하게 대처할 수 있습니다.
• 단점:
  • 데이터셋 크기가 클 경우 계산 비용이 많이 듭니다. (모든 데이터 포인트와의 거리를 계산해야 함)
  • 최적의 K 값을 선택하는 것이 중요합니다.
  • 특성(feature)의 스케일에 민감합니다. (거리 기반 알고리즘이므로, 특성 스케일링이 필요)
  • 차원의 저주(Curse of Dimensionality) 문제가 발생할 수 있습니다. (특성 수가 많아질수록 성능 저하)

5. 활용 분야

• 이미지 인식: 이미지 분류, 객체 인식
• 추천 시스템: 사용자-아이템 간 유사도 기반 추천
• 의료 진단: 환자 데이터 기반 질병 예측
• 신용 평가: 신용 점수 예측

6. 개선 방법

• 차원 축소 (Dimensionality Reduction): PCA(Principal Component Analysis) 등의 방법을 사용하여 특성 수를 줄여 계산 비용을 줄이고 성능을 향상시킬 수 있습니다.
• 특성 선택 (Feature Selection): 중요한 특성만 선택하여 모델의 성능을 향상시킬 수 있습니다.
• 거리 가중치 (Distance Weighting): 가까운 이웃에 더 큰 가중치를 부여하여 예측 정확도를 높일 수 있습니다.
• KD-Tree, Ball-Tree: 대규모 데이터셋에서 효율적인 이웃 검색을 위해 KD-Tree 또는 Ball-Tree와 같은 공간 분할 자료 구조를 사용할 수 있습니다.

KNN은 간단하면서도 강력한 알고리즘이지만, 데이터의 특성과 문제의 성격에 따라 적절한 K 값을 선택하고, 필요한 전처리 과정을 거치는 것이 중요합니다.