2-3-8. k-근접이웃 알고리즘

-대부분의 기계학습 방법은 학습 데이터로부터 주어진 문제를 해결하기 위한 모델을 먼저 학습한 다음, 이를 이용하여 질의(또는 입력)에 대한 답을 찾는데 미리 학습을 하지 않은 채 있다가, 질의 입력이 들어올 때야 학습데이터를 사용하여 출력(대답)을 결정하는 방법도 있음.

-k-nearest neighbor algorithm:KNN algorithm) 은 분류가 되어 있지 않은 데이터(Test data)들을 분류된 데이터(training data)들 중 가장 비슷한 속성을 가진 그룹으로 분류해주는 방식으로서 그룹의 항목들이 동질적인 경향을 보일 때 적합하지만 그룹 간 명확한 차이가 없으면 효과적이지 못함

-즉, 입력과 결과로 구성된 학습데이터들이 주어진 상황에서 새로운 입력이 들어오면, 입력에 가장 근접한 k개의 학습데이터를 찾고 이들 데이터의 결과 정보를 이용하여 결과를 추정함

 

토마토는 위 그림에서 어느 그룹에 속할것인가?

이런 질문에 속할 때, 어디에 더 가깝나에 따라서 어느 기준을 정해서 분류를 한다. 방법에는 여러가지가 있는데, 흔히 유클리드안 방법을 사용함.

 

-KNN을 사용하기 위해서는 질의와 학습 데이터간의 거리를 계산하는 방법이 있어야 함. 데이터의 속성이 모두 수치값인 경우에는, 데이터를 유클리드 공간(거리가 정의될 수 있는 공간으로 사람이 사는 3차원 공간이 대표적)상의 점으로 나타낼 수 있음. 질의와 학습 데이터의 입력이 모두 유클리드 공간상의 점으로 간주될 수 있으므로 유클리드 거리를 측정하는데 사용할수 있음. N차원 공간의 두 점 와

이 주어질때, 두 점 사이의 유클리드 거리 d(X, Y) 는 다음과 같이 정의 됨

 

-데이터가 범주형 속성을 갖는 경우 타당한 거리를 정의하는 것이 어려운 경우도 있음. 데이터 간의 타당한 거리를 정의할 수 없다면 KNN 적용

-주요 특징

   ＊Lazy Learning <- No abstraction, No generalization
   ＊Instead of instance-based Learning
   ＊Non-parametric Learning
   ＊너무 작은 k : Overfitting 우려
   ＊너무 큰 k : 데이터 구조 파악의 어려움

□