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)