K-Nearest Neighbor Algorithm (KNN 알고리즘)

K-Nearest Neighbor 

 

K-NN 알고리즘은 데이터를 가장 가까운 속성에 따라 분류하는 알고리즘으로,  K개의 가까운 이웃의 속성에 따라 분류합니다. K-NN 알고리즘의 경우 모델을 만들지 않고 새로운 데이터가 주어지면 기존의 학습 데이터를 기반으로 클래스를 예측하는 방식입니다.

 

 

Basic Approach

 

 

K-NN 알고리즘의 경우 d차원 공간에서 (x, y)를 한 점으로 간주합니다. 이때 x는 d개의 데이터셋이며, y는 각 데이터들의 클래스 레이블을 의미합니다. 만약 새로운 x'가 주어지게 되면 각각의 (x, y)와 거리를 계산하고, x'와 비슷한 k개의 거리를 찾습니다. k개의 거리 중 다수의 이웃이 있는 클래스에 따라 새로운 데이터 x'의 클래스를 예측할 수 있습니다. 

 

 

 

만약 k를 너무 작게 설정하면, 클래스가 주변의 1~2개의 데이터에 영향을 받아 달라질 수 있으므로 overfitting(과적합)에 취약합니다. 즉 데이터 전체를 보지 않고 국소적인 부분만 보기 때문이라고 할 수 있습니다. 반면 k를 너무 크게 설정하면 클래스를 구분하기 위하여 이웃과 멀리 떨어진 데이터들도 고려하기 때문에 잘못 판단할 가능성이 높아집니다.

위의 사진을 보면 k를 2로 설정하면 unknown class의 주변에는 class B의 개수가 더 많기 때문에 class B로 할당하게 되지만  k를 7로 설정하면 주변의 클래스뿐 아니라 여러 개의 클래스도 고려하게 되므로 결국 class B가 아닌 A로 잘못 판단하게 됩니다.

 

 

Voting

 

K-NN의 경우 새로운 데이터인 x'가 주어졌을 때  x'의 클래스를 결정하기 위해 여러가지 방법을 사용하는데, 그중 Majority voting 방식과 Distance-weighted voting 방식을 사용합니다.

 

Majority voting 방식은 모든 이웃에게 동일한 가중치를 부여하기 때문에, k를 몇 개로 설정할 것인지가 중요해지는 반면, Distance-weighted voting 방식은 각각의 (x, y)에 대하여 1 / (x, y)^2의 가중치를 부여하여 x'와 멀리 떨어져 있을수록 가중치가 작아지므로 k의 개수는 크게 중요하지 않게 됩니다.

 

 

Characterisitics 

 

1) instance-based model

 

K-NN의 경우 전체 데이터셋에 잘 맞는 전체적인 하나의 모델을 만들지 않고, 데이터만 이용하여 클래스를 예측하므로 모델 생성에 있어 자유롭습니다. 하지만 모델을 만들지 않기 때문에 모델을 만드는 시간은 소요하지 않지만, 새로운 관측치와 각각의 학습 데이터 사이의 거리를 전부 측정해야 하므로 계산 시간이 오래 걸려 실시간 처리에 적합하지 않다는 특징을 가집니다. 

 

 

2) local & arbitrary

 

 

K-NN은 앞서 살펴봤다시피 주변의 k개의 local한 이웃 정보에 기반하기 때문에 노이즈에 취약하다는 단점을 가집니다. 또한, K-NN은 k를 증가시킬 수록 전체적인 데이터셋을 보기 때문에 선이 좀 더 완만하게 되는 것을 볼 수 있으며, 임의적인 모양도 잘 분류할 수 있습니다. 

 

 

3) missing & irrelevant value

 

K-NN은 새로운 데이터가 주어지면 모든 데이터들 간의 거리를 측정하여 클래스를 예측하는 방식이고, 이때 거리측정은 모든 attribute가 존재해야 하기 때문에 K-NN은 missing value에 취약합니다. 또한 유사성을 '거리'로 측정하기 때문에 관련성이 없는 attribute가 포함되어 있더라도 관련성이 없는 attribute가 많은 상황에서는 이를 잘 판단할 수 없습니다.

 

 

4) importance of proximity measure

 

K-NN은 K의 값과 거리 측정 방식에 따라서 그 성능이 달라집니다. 예를 들어, 사람을 키와 몸무게를 기반하여 분류한다고 가정해보겠습니다. 예를들어 키는 1.5~1.85m라는 값을 가질 수 있고, 몸무게는 40kg ~ 120 kg 사이의 값을 가질 수 있게 됩니다. 하지만 이때 정규화를 하지 않으면 몸무게로 인해 값이 지배되기 때문에 적절한 예측을 할 수 없게 됩니다. 이때 모든 특성들을 모두 고르게 반영하기 위해 정규화를 해야하는데, 그 방법에는 2가지가 널리 쓰입니다.

 

 

① 최소-최대 정규화

 

Z=(X−min(X))/(max(X)−min(X))

 

최소값을 0, 최대값을 1로 고정한 뒤 모든 값들을 0과 1사이 값으로 변환하는 방법

 

 

② z-점수 표준화

 

Z=(X−평균)/표준편차

 

평균과 표준편차를 활용해서 평균으로부터 얼마나 떨어져 있는지 z-점수로 변환하는 방법