Overview

KNN(K-Nearest Neightbor) 알고리즘은 범주를 모르는 어떠한 데이터에 대해 분류되어 있는 가장 유사한 예제의 범주로 지정해주는 알고리즘이다.

입력 데이터와 유사한 K개의 데이터를 구하고, 그 K개 데이터의 분류 중 가장 빈도가 높은 클래스를 입력 데이터의 분류로 결정하는 알고리즘이다.

사용 예시
개인별 추천 영화 예측
유전자 데이터의 패턴 식별
얼굴과 글자를 인식하는 컴퓨터 vision application

---

KNN(K-Nearest Neightbor)

다음 그림은 파란색은 파충류, 빨간색은 조류로 분류된 데이터이다.

녹색으로 되어 있는 새로운 데이터가 파충류인지 조류 인지 분류를 하고자 한다.

이를 분류할 수 있는 방법 중의 하나는 가장 가까이 있는 항목으로 분류하는 방법이다.

이러한 기법을 Nearest Neighbor이라고 한다.

예시에서는 빨간색이 가장 가까우므로 조류라고 볼 수 있다.

하지만, 실제 데이터 분포를 보면 파란색이 훨씬 더 많고 범위를 조금만 더 넓혀 보면 파란색이 더 많다.

녹색 원으로 되어 범위까지 확대해 보면 파란색과 빨간색의 개수가 동일하다.

좀 더 확장하여 갈색 원까지 범위를 넓혀 보면 파란색이 더 많다.

이와 같이 주어진 개수(K 개) 만큼 가까운 멤버들과 비교하여 판단하는 방법을 KNN(K-Nearest Neighbor) 알고리즘이라고 한다.

추가적으로 고려해야 할 사항으로 가까운 거리에 있는 항목은 가중치를 크게, 멀리 있는 항목은 가중치를 적게 적용하는 방식 도 있다.

이 방식은 수정된 KNN이라고 부른다.

K 값의 선택

실제로 K의 값은 학습해야 할 데이터의 개수에 달려 있다.

보통 3 ~ 10 사이에서 결정한다.

일반적인 방법으로 훈련 데이터 개수의 제곱근으로 설정하기도 한다.

이러한 방법이 항상 최적의 결과를 만들지 못할 수도 있다.

다양한 테스트 데이터 셋에 대하여 일부 K 값을 테스트하여 최적의 분류 성능을 내는 K 값을 선택하는 것이다.

KNN을 사용하기 위한 데이터 준비

사전에 고려해야 할 사항은 각 속성들의 값의 분포를 상대적으로 균등하게 하기 위하여 최대-최소 정규화(Min-Max Normalization) 또는 Z 점수 표준화(Z-Score Standardization)를 수행하는 것이 좋다.

---

knn() 함수

class 패키지에 들어 있는 knn() 함수는 데이터에 들어 있는 각 인스턴스에 대하여 유클리드 거리를 사용하여 k 근접 이웃을 찾는다.

k 개의 인스턴스에 다수결의 ‘투표’로 분류를 한다.

만약 동수 투표인 경우에는 임의로 선택을 하게 되는데, 일반적으로 홀수 정수 값을 사용하여 동수가 나오지 않도록 한다.

• 사용 형식
  • knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=21)
• train
  • 훈련용 데이터 프레임
• test
  • 테스트용 데이터 프레임
• cl
  • 훈련용 데이터의 각 행에 대한 정답(label)을 가지고 있는 벡터
  • 최근접 이웃의 수를 명시하는 정수 값
  • 일반적으로 권장하는 수는 training 데이터 셋에 루트를 씌운 값에 홀수의 정수 값 권장
• 사용 예시
  • k_size <- floor(sqrt(training_row))
  • k_size <- ifelse(k_size %% 2 == 0, k_size + 1, k_size)