Nearest Neighbor Classification

 

 분류 (classification) 하고자 하는 클래스의 종류에 대해서는 알고 있지만 샘플들 각각에 대한 확률밀도함수 (probability density function) 을 알지 못하는 상태에서 사용한다. 

 굳이 각 샘플에 대한 확률 인수 (parameter) 들을 구하지 않고  샘플의 값을 그대로 좌표에 표시하여 참조집합 (reference set) 에서 가장 유사 (similar) 하거나 거리 상으로 가까운 (nearest) class 에 속하는 것으로 분류하는 방법이다.

 nearest 의 의미는 무엇인가? 그것은 smallest Euclidean distance, absolute difference, maximum distance, Minkowski distance 등을 계산하여 그 거리가 가장 가까운 것을 의미한다. 다음 그림은 클래스 A 에 3 개, 클래스 B 에 2 개의 샘플을 가지는 경우의 feature space 이다. 어떤 클래스에 속하는지 알려지지 않은 샘플이 좌표 (1,1) 에 있을 경우 Euclidean distance 를 계산하여 가장 가까이 있는 클래스는 좌표 (1,3) 에 위치한 클래스 A 이다. 따라서 클래스 A 에 속하는 것으로 한다 .

 Nearest neighbor 방법중에서 일반적으로 사용되는 것은 단하나의 가장 가까이 있는 이웃 만으로 구하는 것이 아니라  개의 가까운 이웃중에서 "선출하여 (votes)" 미지의 샘플들을 분류하는 것이다. 이러한 k-nearest neighbor 분류과정은 흔히 이라고 표현된다. 만일 각 클래스에 대해 에러비용 (costs of error) 이 같다면 한다면, 미지의 샘플이 속하는 것으로 추정되는 클래스는  개의 가장가까운 이웃 집단중에서 가장 흔하게 표현되는 (most commonly represented) 클래스를 선택하는 것이다. 예를들면 위의 그림에서 미지의 샘플 (1, 1) 주변에 가장 가까이에 3 개의 이웃이 있다면, 미지의 샘플 (1, 1) 은 B 클래스에 속하는 것으로 분류된다. 왜냐하면 3 개의 가장가까운 이웃중에서 클래스 A 에는 하나 (1, 3), 클래스 B 는 두개의 샘플로 구성되기 때문이다. 

term :

패턴인식 (Pattern Recognition)   K-최근린 분류 (K-Nearest Neighbor Classification)   인공지능 (Artificial Intelligence)   불확실성 (Uncertainty)   기계학습 (Machine Learning)   통계 (Statistics)   Support Vector Machine

paper :

Nearest Neighbor Classification Techniques   The k-nearest Neighbor Technique : Earl Gose 외

Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques, Belur Dasarathy, editor, 1991

한국어 정보처리 : 휴리스틱을 이용한 kNN 의 효율성 개선 (Korean Information Processing : An Improvement Of Efficiency For kNN By Using A Heuristic) : 이재문, 한국정보처리학회, 2003

Nearest Pattern Classification : Thomas M. Cover and Peter E. Hart,  IEEE Trans. on Information Theory, Vol. IT-13, No. 1, pp 21-27 (January 1967)

Integrating Background Knowledge into Nearest-Neighbor Text Classification : Haym Hirsh, Proceedings of the 6th European Conference on Case Based Reasoning. Springer Verlag. 2002

site :

The Nearest Neighbor Rule : A Short Tutorial : Nearest Neighbor Applet

Wikipedia : Nearest neighbor (pattern recognition)