kNN model (k-Nearest neighbor model)

KNN

:비선형 기법. 지도학습기법. 

결정 분계선(Decision boundary)을 정의하기위해서, 이 결정분계선이 피쳐들의 선형결합이어야 한다는 가정을 필요로 하지 않는다.  또한, 인스턴스 기반 학습(instance-based learning, memory-based learning)이기 때문에, 모수가 없다(주석 참고). 그렇기 때문에, 이전에는 아무런 학습 작업이 없고, 모형에 대한 아무런 파라미터가 없어서 게으른 학습(Lazy learning)이라고도 불린다. 따로 모집단을 추론하지 않고, 필요도 없으니 비모수적(non-parameteric) 인 방법이며 분류와, 회귀(regression)을 위한 방법이다. 또한 레이블이 있는 상태에서 분류를 하기 때문에, 지도학습모델이다. 레이블이 있는 상태에서, 모델에대한 평가를 할 수 있다. 가령, 원래 클레스가 3개가 있다고 했을 때, 새로운 unseen data가 들어왔을 때, 이 새로운 데이터가 어느 그룹으로 결정될지 알 수 있기 때문에, 지도학습이다. 

어떤 도서에서는 기계학습의 정의는 '어떤 Task을 반복적으로 시행되었을 때, 퍼포먼스가 증가하는 학습 방식'이라고 정의해 놓는 책도있지만, KNN 은 이러한 점진적인 개선이 이루어지 않는 모델로 보인다. [알고리즘으로 배우는 인공지능, 머신러닝, 딥러닝 입문]

kNN은 새로운 데이터가 어느 그룹에 속하는지 분류하기 위해, 그 데이터에 가장 가까이에 있는 학습된 데이터가 속한 그룹을 알아보는 것이다. 즉, 거리계산을 통해서, 유사도를 평가해서 새로운 변수를 평가한다는 것이다. 즉, 변수가 유사한 것 끼리 묶는다는 것인데, 이 변수들을 Feature space라고 한다. K는  알고리즘이 얼마나 많은 이웃을 검사해야하는지를 정하는데, 만일 K가 7이었다면, 7개의 가까운 점을 검사하는 것이다. 또한 7개가 모두 똑같은 가중 값을 갖는다. 또한, k가 짝수이면 안된다. k가 짝수이면, 안되고 홀수여야한다. 짝수를 지양한다. 

Common Distance Metrics:

---

유클리드 거리(Euclidean distance): 연속형 분포일 때 사용. 

해밍 거리(Hamming distance): overlap metric. 겹치는 것들이 있는 변수들일 때 활용한다. 

e.g) SNS와 MMS는 거리가 2이며, Hole과 Hale은 거리가 1이다.

Discrete Metric (Boolean metric): X=Y이면, 거리가 0, 다르면 1 이런식이다.

 - kNN regression: 종속변수가 자료의 특성중에 하나 일 때, 종속변수는 k개의 근접한 이웃들의 값의 평균값

 - kNN classificaion: 종속변수(output)이 class일 경우에는 분류분석

(Source:http://2.bp.blogspot.com/-EK4tA2525EM/U-c6Q4jJuwI/AAAAAAAADjw/hdqRXuunpnQ/s1600/ knn.png)

kNN은 인스턴스 기반의 러닝 또는 메모리 기반 러닝이라고도 한다. 왜냐하면, 학습을 미리 하지 않고 미뤄두고 있다가 새로운 데이터의 테스크 요청이 오면 그때  분류를 시작하기 때문이다. 즉, 학습에 필요한 데이터를 메모리에 기억만 하고, 인스턴스가 발생할 때, 일반화하는 일을 시작한다. 이렇게 KNN 모델을 만드려면 3가지가 필요한데, 1) Feature space(training data), 2) Distance metrics, 3) Value of K이다. 이는 KNN모델을 만들 때, 파마리터가 되기도 할 것이다. Feature space는 변수들을 고정된 개수의 백더로 만드는 것이고, Distance metric은 거리를 측정하는 방식들을 의미하며, K는 몇개를 뽑을 것인지를 정해야한다는 것이다.

K에 따른 Bias, Variance

분류분석인 경우, K가 3이면 가장 가까운 3점을 한 원안에 담는다. 이 원안에 같은 클레스인것이 많은 클레스로 New instance(문제)를 분류한다. 그러므로, 모델에서 K를 어떤 수로 정하느냐가 모델의 퍼포먼스를 결정한다. K가 너무 작으면 bias가 작을 수 있지만, variance는 클 수 있다. 왜냐하면, k가 작다는 것은, 노이즈에 민감하단 얘기고, 그렇게되면 너무 민감하게 모델이 적용되서 오버피팅이 될 수 있다. 따라서, 모든 개별 개별 하나의 인스턴스를 고려하기떄문에 Bias는 작고 Variance는 크다. 반대로, K가 너무 크면, Bias는 클 수 있지만, Variance는 작을 수 있다. 인접주변의 인스턴스를 모두 포함하기 때문에, 다른 클레스도 다 같은 군으로 분류할 수 있다. 이는 Bias가 크고, Variancer가 작다.

Notes

정규화: 퓨쳐들의 사이에 계산을 해야할 떄, distance의 scale을 정규화하여 사용하여야 한다.(Normalization) 만약 키와 소득이 피쳐라면, 키는 빼봤자 숫자가 100이하로 차이나서 별로 차이가 안나겠지만, 소득은 100만 1000만단위이기 떄문에 차이가 많이난다. 

Charateristics

1. 비교적 적용이 간편한 편이지만, 모델을 계산하는게 리소스를 너무 많이 잡아 먹을 수 있다. 왜나하면, 군집할 떄 모든 거리를 측정해야하기 때문에 컴퓨팅 파워가 필요할 수 있다. 

2. 트레이닝을 포함하지 않아, 비교적 유연한 방식의 분류기법이다.

3. 노이즈에 의해서 정확도가 급격히 낮아질 수 있다.

4. 고차원의 데이터인 경우(=피쳐수가 많을 경우) 계산량이 많아지고, 거리를 측정하기가 어려워서 퍼포먼스가 점점 안좋아 질 수 있다.

5. 큰 데이터세트(인스턴스가 많은) 경우에 사용할 경우, 계산량 많이 발생할 수 있다. 많은 데이터포인트(인스턴스)와 계산해야되기 때문에... (1번이랑 유사)

6. 범주형 변수에서 잘 작동하지 않을 수 있다. 범주형 변수의 거리를 측정하는게 애매모호 하다

K-Means clustering vs K-NN 비교

K라는 값이 같이 들어가서, 머신러닝에서 주로 혼동되는 개념이다. 비교는 아래와 같다

K-means	KNN
비지도학습(Unsupervised learning)	지도학습(Supervised learning)
Clustering method	Classification, Regression
K: 원하는 클러스터링의 집합(군집 집합의 갯수)	K: 새롭게 문제가 주어졌을 때, 근접한 인스턴스들의 갯수 (이를 이용해서 분류, 예측문제를 해결한다)

Model evaluation metric

---

분류문제의 평가는 보통 Confusion matrix을 통한 계산값들을 평가한다

	True  positive	True Negative
Predictive Positive	TP	FP
Predictive Negative	FN	TN

*Instance based learning: 명시적으로 일반화 하는 알고리즘이 아니라, 새로운 문제(인스턴스)가 들어왔을 때까지 다른 인스턴스들을메모리에 저장해놓는다. 

** Bias: 머신러닝 모델이 모든정보를 고려하지 않아서, 잘못된 학습을 하는 것. Traing set을 맞추지 못하는 것을 바이어스라고 부른다. (High bias: 너무 모델이 심플 .underfitted to training set)

*** Variance: 머신러닝 모델이 Test set을 맞추지 못하는 것이 variance라고 부른다. (High variance: 너무 모델이 복잡. overfitted to training set )

Feature space: 실제 데이터를 vector형태로 같은 고정된 길이의 벡터로 변환하여 만든 데이터