K-NN 알고리즘

<기본 아이디어>
- 새로운 레코드를 '분류'하거나 '예측'할 때 사용
- 분류되어야 할 주어진 레코드에서 근접(유사) 레코드를 찾는다(k개를 선정)
- "근접(nearby)"은 비슷한 예측변수 값을 가진 레코드를 뜻한다
- 근접한 레코드들("neighbor")이 주로 속한 클래스(우세한 클래스)로 해당 레코드의 클래스를 결정한다
- 특징
  - 데이터에 근거한 추론
  - 데이터에 대한 어떠한 가정도 없다





<이웃 결정하기>
- 소속 클래스와 예측변수들간의 관계에 대한 가정이 없다(비모수적 : nonparametric)
- 레코드들간의 유사성은 예측변수들로부터 얻는다
- 가장 많이 쓰이는 근접 측정방법은 '유클리드 거리'이다
- 예측변수의 척도를 균등하게 하기 위해 '표준화'
- 새로운 레코드를 표준화 할 때는 '학습데이터의 평균과 표준편차'사용





<분류규칙>
- 분류기에서 k 선택
- k는 새로운 레코드를 분류하는데 사용되는 근접 이웃의 개수
  - k=1 : 하나의 가장 근접한 레코드를 사용
  - k=5 : 5개의 가장 근접한 레코드를 사용

- 전형적으로 k의 값은 '검증 데이터'에서 가장 낮은 오류율을 가진 것을 선택





<작은 k VS 큰 k>
- 작은 k값은 데이터의 지역적 구조(잡음을 포함하여)를 반영
- 큰 k값은 지역적 구조에 덜 민감하고 잡음의 영향을 덜 받지만 지역적 구조가 주는 정보를 놓칠 수 있다
- k는 보통 1~20의 범위 내에서 홀추
 *k=n의 극단적 경우(i.e, 전체 데이터 세트)는 "나이브 규칙"과 같다(주요 클래스에 따라 전체 레코드를 분류)





<k값 선택>
- k가 너무 작으면 데이터의 노이즈를 적합할 위험
- k가 너무 크면 이 알고리즘의 주된 장점 중 하나인 데이터의 지역적 구조를 파악할 수 있는 능력을 놓칠 수 있다
- 학습 데이터셋을 사용해 얻은 knn 분류모형에 검증 데이터셋의 레코드를 분류한 다음 다양한 값에 대해 오차율을 계산하여 선택 가장 분류 성능이 좋은 k 선택
- k가 선택되면 '새로운 레코드를 분륳기 위해 학습 데이터셋과 테스트 데이터셋을 합치고' 알고리즘 반복





<예측을 위해 K-NN 사용(수치형 목표변수)>
- 분류는 "다수결 투표"를 이용해서 클래스 결정
- 예측에서는 목표 변수의 값을 예측하는 것이므로 최근접 이웃을 구하여 이들의 '목표변수의 평균값' 사용
- k 결정 : 검증데이터에서 RMSE 사용
  - k-nearst neighbor를 이용한 예측값과 검증데이터의 실제값을 이용하여 구한다
- 목표변수의 평균값은 가중 평균값 사용
  - 예측이 요구되는 레코드로부터 거리가 멀 수록 가중치 감소





<장점>
- 간단
- 분포 가정이 필요하지 않다
- 충분한 학습 데이터가 있을 때 좋은 성능을 보인다
- 통계적 모델을 정의하지 않고 변수들 사이에서 복잡한 상호작용을 수집하는 데 효과적





<단점>
- 예측변수의 수 p가 증가함에 따라 학습 세트로 필요한 레코드의 수가 기하급수적으로 증가
  - p가 증가함에 따라 근접 이웃의 기대거리도 증가하기 때문이다(예측변수의 벡터가 증가함에 따라, 모든 레코드는 결국 서로에게서 '멀어진다')
- 대용량 학습세트에서, 모든 이웃까지의 거리를 찾는 데 시간이 오래 걸리고 따라서 가장 가까운 이웃을 찾는 데도 시간이 오래 걸린다
- 예측변수의 수가 많아지면 "차원의 저주"의 영향을 받는다





<단점 극복 방안>
- 예측변수의 차원 축수(e.g, 주성분 분석으로)
- 검색 Tree등을 사용하여 근접 이웃을 정확히 찾기 보다는 '거의 가장 근접한 이웃'을 찾는다
- 중복되었거나 거의 중복된 학습레코드를 제거





<요약>
- 분류되어야 할 레코드와 다른 모든 레코드 사이의 거리를 계산
- k-근접 이웃 레코드 선택
  - 근접 이웃의 다수결 투표에 따라 분류
  - 예측에서, 근접 이웃의 평균을 취한다
- "차원의 저주" : 예측변수의 수를 제한할 필요