최근접 분류기

최근접 분류기(Nearest Neighbor Classifier)

---

최근접 분류기는 테스트 데이터가 주어지면, 테스트 데이터들과 상대적으로 유사한 훈련 데이터들을 찾는다.

그림 1

그림 1의 2차원의 예시를 보자. 테스트 데이터 z를 2차원 공간에 찍으면 그림 1.(a)의 x처럼 찍을 수 있다. 그리고 테스트 데이터 객체는 인접한 클래스 레이블을 기반으로 분류된다. 이웃에 하나 이상의 레이블이 있으면, 테스트 데이터는 가장 근접한 이웃들이 갖는 클래스들 중 가장 많은 클래스에 지정된다. 보통 K Nearest Neighbor 라고 불리는데, K는 주변의 데이터를 몇개를 볼 것인가 이다. 그림 1에 예제가 나와있다.

클래스들 사이에 같은 개수가 있을 경우, 임의로 하나를 선택한다.

수학 식으로는 다음과 같이 표현된다.

\[\text{Majority Voting}\;:\;y'= \text{arg}\max_v \sum_{(x_i,y_i)\in D_z} I(v=y_i)\]

※ v는 클래스 레이블, $y_i$는 가장 가까운 이웃 중 하나에 대한 클래스 레이블, $I(\cdot)$은 true면 1, 아니면 0을 출력하는 함수다.

그러나 사실 클래스 레이블들이 거리에 상관 없이 원안에 들어오기만 한다면 모두 분류에 영향을 미친다. 따라서 K에 따라 분류가 확확 바뀔 수가 있다. 문제 해결을 위해, 각각의 trainig 객체들에 대해 거리에 대한 weight를 줌으로써 K의 영향을 줄일 수 있다.

\[\text{Majority Voting}\;:\;y'= \text{arg}\max_v \sum_{(x_i,y_i)\in D_z} w_i \times I(v=y_i)\] \[w_i = \frac{1}{x',x_i}\]

※ $x’$은 테스트 데이터의 feature vector를, $x_i$는 i번째 nearest neighbor를 나타낸다.

특징 정리

• 최근접 분류기는 학습을 하지 않기 때문에 모델이 없다.
• 테스트 데이터와 개별 훈련 데이터들 간의 근접성을 모두 측정해야하기 때문에, 계산량이 많다.
• noise에 매우 취약하다.
• 근처의 데이터들과의 근접도를 계산하려면 모든 feature들이 존재해야하므로, 결측 값을 처리하는데 어려움이 있다.
• 클래스를 구분 짓는 것에 관련이 없는 feature들이 사용되면 성능이 떨어진다.
• feature들의 scale에 굉장히 민감하다. 예를 들면, 체중(40kg~150kg)과 키(1.5M~1.8M)를 정규화하지 않고 사람을 분류한다면? 체중에 의해 분류될 확률이 높다. 왜냐하면 K-NN은 원으로 의사결정 경계를 넓혀가는데, 상대적으로 좁은 범위에 포진된 키는 원이 조금만 커져도 범위 내에 다 들어오기 때문이다.