[데이터 분석] K-NN 알고리즘

KNN (K-Nearest Neighbors) 알고리즘 

참고글 : [R 분석] K-NN 알고리즘 적용 및 매개변수 튜닝

 KNN 알고리즘은 거리기반 분류분석 모델입니다.

'기존 데이터와 특성이 비슷하면 새로운 데이터도 저들과 비슷하지 않을까?' 라는 고안으로 나온 알고리즘이라고 합니다.

 예측을 하고자하는 새로운 관측치(데이터)와 이미 정답이 있는 기존 관측치(데이터) 사이의 거리를 계산하여,

가장 가까운 K개 관측치들의 Class(범주, 그룹)를 확인하여 예측하게 됩니다.

여기서 기존 관측치의 Y값(Class)이 존재한다면 KNN 알고리즘으로, 

          기존 관측치의 Y값(Class)이 존재하지 않는다면 군집분석 Clustering 알고리즘으로 구분됩니다.

위 그림을 예로 들면, 중앙에 새로 들어온 관측치(1번 관측치)는 기존 관측치들과의 거리를 계산하게 됩니다.

여기서 K의 값을 4로 설정했을 때, 4개의 가장 가까운 관측치들의 Class를 확인합니다.

가까운 거리의 K개 데이터에 빨간 원이 더 많이 포함되어있으므로 새로 들어온 관측치는 빨간 원이라는 그룹이라고 예측할 수 있습니다.

KNN 알고리즘의 특징

 1. 거리 계산

  - 관측치들끼리의 거리를 계산해서 데이터들을 분류 (가까운 관측치의 데이터와 같은 그룹을 가질 것 이라는 전재)

  - 관측치들의 거리 계산은 유클리드 거리 계산식을 이용

  - 모델에 새로운 데이터를 적용시키면, 기존 데이터들과의 모든 거리를 계산

  - 변수들의 중요도 중심이 아닌 단순한 관측치(데이터)간 거리를 통해 예측 -> 예측력이 떨어지는 단점

 2. K의 의미

 - K개의 가장 가까운 이웃의 Class를 확인 -> K개의 데이터 중 많은 Class가 확인된 그룹으로 최종 분류

 - K값이 커질수록 많은 관측치를 활용하므로 예측력이 증가 -> 하지만, 과대적합이 발생하여 일반화가 어려움

   과대적합 방지를 위해, 예측력을 향상시키면서 일반화시킬 수 있는 적절한 K 지점을 찾아야 함

 - 이중분류(ex. YES of NO)인 경우, K가 짝수이면 예측력이 떨어짐 (Class의 동률이 발생하면 판단 기준이 어려움)

    * 이중분류일 경우, K를 홀수개로 지정해야 함

 3. KNN 알고리즘의 사용 예

  - 실제로 추천, 인식 알고리즘에서 많이 사용되는 알고리즘

  - 이미지 인식은 새로운 이미지를 픽셀(pixel) 단위로 분할하고, 기존 이미지의 픽셀들과 거리를 계산하여 가까운 Class로 분류

  - 보통 KNN 알고리즘 단독으로 사용하지 않고, 설명 변수에 가중치가 부여되는 알고리즘과 함께 사용 

 4. 기타

  - 지도학습이지만, 이전 데이터가 누적되어 학습되지 않음 (게으른 학습)

  - 데이터 내에 결측치, 이상치가 있다면 적용 전 전처리 필요

  - 설명변수마다 범위가 다르므로, 표준화 필요

거리기반 모델의 특징 

 1. 표준화의 필요

  - 표준편차 : 분산에 루트(제곱근, √x)을 씌운 것으로, 분산이 작으면 밀집, 분산이 크면 흩어지는 현상을 보임. Class(그룹)에 따라 그 값의 범위가 각기 다름

      * 같은 범위상에 있더라도 분포에 따라 범위가 달라지므로, 크기의 의미가 달라질 수 있음(거리는 각 설명변수의 범위에 민감) -> 동일 범위더라도 표준화 작업이 필요

         ex) 변수 A의 점수 범위는 1~1000점, 변수 B의 점수 범위는 1~10점일 경우, 1점 차이의 크기가 변수마다 다름, 분포가 다르면 각 변수의 차이를 해석하기 어려움

  - 표준화(Standatd scale) 방법

      * X - Xbar / SE : X에서 평균을 뺀 후, 표준편차로 나누는 방법 (scale 함수 사용, 평균은 0 기준으로 -1 ~ +1 범위)

      ** min-max scale : 최대값은 1, 최소값은 0으로 

 2. 이상치(outlier)에 민감한 반응

  - 이상치(기존 범주에 벗어나 유독 값이 작거나 큰 데이터) 데이터의 제어가 필요

      * 제거 또는 수정(평균, 최소, 최대 값으로)

  - Tree 알고리즘 같은 경우는 설명변수의 중요도 기반으로 동작하기때문에 민감하지 않음

3. 설명변수 민감한 반응

  - 설명변수에 매우 민감 (모델 내 변수 선택 기준이 없기 때문)

  - Tree 알고리즘은 중요도 기반이므로 불필요한 설명변수를 모델에서 사용하지 않지만, KNN 알고리즘은 거리 기반이므로 모든 설명변수를 고려

      * 중요하지 않은 변수가 모델에 추가될 수록 정확도가 낮아짐

  - 중요도가 높은 의미있는 설명변수만 추출하여, 정확성을 높이는 과정이 필요