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)