14. Classification & Image Pattern Recognition 2

📌 KNN Classifier

• K-Nearest Neighbor 분류기는 input data가 주어졌을 때 input data와 가까운 K개의 데이터를 이용하여 클래스를 예측하는 모델이다
• K : 거리를 측정할 데이터의 개수
• 알고리즘
  1. input data $x$가 주어졌을 때 training set $[x_1, x_2, ..., x_N]$에 있는 모든 원소들과 거리를 계산한다
  2. K개의 sample들과 input data$x$ 사이의 거리를 계산하여 $N(x)=[x^1, x^2, ..., x^K]$를 만든다.
  3. $N(x)$에 들어있는 원소들의 label을 찾아 $y(x^1), y(x^2), ..., y(x^K)$를 만든다.
  4. 3에서 가장 빈도수가 많은 class(label)를 $x$의 class로 분류한다
• overfitting되어 있는 모델의 에러는 K-NN으로 해결가능하다
• minimum distance classifier에 비해 더 정확한 결정경계를 만들 수 있다
• K 값이 높을 수록, 결정경계가 완만히지고, 복잡도가 낮아진다 -> 이상치에 덜 민감하다
• K 값이 낮을 수록, 결정경계가 복잡해지고, 복잡도가 증가한다 -> 이상치에 민감하다 -> overfitting 가능성이 올라간다
• various distance measure
  • Euclidean (2nd Norm), 1st Norm, P-th Norm, Inner product, Cosine distance, Mahalanobis distance
   

 

 

📌 K-NN classifier vs bayes classifier

• Bayes Classifier
  • 가우시안 정규분포의 평균과 분산을 파라미터로 가지는 parametric approach 방법이다
  • 구체적인 데이터 분포를 가정한다
  • PDF(Probability Density Function)이 추정되면, data sample은 더 이상 필요없다
• K-NN Classifier
  • nonparametric approach 방법이다
  • 각각의 test input에 대하여 모든 sample training data set과의 거리를 구해야 한다
  • training sample은 보존되어야 한다