K-Nearest Neighbors (k-NN) एक गैर-पैरामीट्रिक पर्यवेक्षित शिक्षण एल्गोरिथ्म है जिसका उपयोग वर्गीकरण और प्रतिगमन दोनों के लिए किया जाता है। वर्गीकरण में, एक नए डेटा बिंदु को उसके k निकटतम पड़ोसियों के बीच सबसे सामान्य वर्ग सौंपा जाता है, जो दूरी मीट्रिक द्वारा निर्धारित होता है। प्रतिगमन में, आउटपुट उन पड़ोसियों के मानों का औसत (या भारित औसत) होता है। यह एल्गोरिथ्म उदाहरण-आधारित है, जिसका अर्थ है कि यह पूरे प्रशिक्षण डेटासेट को संग्रहीत करता है और केवल तभी गणना करता है जब भविष्यवाणी की आवश्यकता होती है, सभी सामान्यीकरण को क्वेरी समय तक स्थगित कर देता है।
यह विधि पहली बार 1951 में एवलिन फिक्स और जोसेफ हॉजेस द्वारा विकसित की गई थी और बाद में थॉमस कवर द्वारा विस्तारित की गई। यह सबसे सरल मशीन लर्निंग एल्गोरिदम में से एक है, फिर भी यह कई डोमेन में प्रतिस्पर्धात्मक सटीकता प्राप्त कर सकता है, विशेष रूप से जब निर्णय सीमा अनियमित होती है। इसका प्रदर्शन k की पसंद, दूरी मीट्रिक और फीचर स्केलिंग पर काफी हद तक निर्भर करता है।
ऐतिहासिक विकास
k-NN की उत्पत्ति 1951 में हुई जब एवलिन फिक्स और जोसेफ हॉजेस, जो यूएस एयर फोर्स स्कूल ऑफ एविएशन मेडिसिन में काम कर रहे थे, ने निकटतम पड़ोसियों पर आधारित एक गैर-पैरामीट्रिक वर्गीकरण विधि पेश की। उनका काम विशिष्ट सांख्यिकीय वितरण ग्रहण किए बिना अवलोकनों को वर्गीकृत करने की आवश्यकता से प्रेरित था। 1967 में, थॉमस कवर और पीटर हार्ट ने एक महत्वपूर्ण पेपर प्रकाशित किया जिसने एल्गोरिथ्म के गुणों को औपचारिक रूप दिया, जिसमें बेयस इष्टतम क्लासिफायर के सापेक्ष इसकी त्रुटि दर पर सीमाएं शामिल थीं। इसने k-NN को पैटर्न पहचान में सैद्धांतिक रूप से आधारित दृष्टिकोण के रूप में स्थापित किया। 1960 और 1970 के दशक में कंप्यूटिंग के उदय के साथ एल्गोरिथ्म ने लोकप्रियता हासिल की, क्योंकि इसमें न्यूनतम प्रशिक्षण समय लेकिन पर्याप्त भंडारण की आवश्यकता थी। बाद के विकास, जैसे भारित मतदान और दूरी मीट्रिक सीखने की शुरुआत, ने इसकी कुछ सीमाओं को संबोधित किया।
एल्गोरिथ्म अवलोकन
k-NN वर्गीकरण में, इनपुट में लेबल किए गए उदाहरणों का एक प्रशिक्षण सेट होता है, जिनमें से प्रत्येक को एक बहुआयामी स्थान में एक फीचर वेक्टर के रूप में दर्शाया जाता है। एल्गोरिथ्म इन वैक्टरों और उनके लेबल को संग्रहीत करता है। जब एक क्वेरी बिंदु प्रस्तुत किया जाता है, तो यह क्वेरी से सभी प्रशिक्षण बिंदुओं तक की दूरी की गणना करता है, k निकटतम बिंदुओं का चयन करता है, और उनमें से सबसे अधिक बार दिखाई देने वाला वर्ग निर्दिष्ट करता है। k=1 के लिए, क्वेरी को केवल उसके निकटतम पड़ोसी के वर्ग को सौंपा जाता है। k का चुनाव महत्वपूर्ण है: एक छोटा k उच्च भिन्नता और शोर के प्रति संवेदनशीलता पैदा कर सकता है, जबकि एक बड़ा k निर्णय सीमा को अधिक स्मूथ कर सकता है और अन्य वर्गों के बिंदुओं को शामिल कर सकता है।
प्रतिगमन के लिए, आउटपुट k निकटतम पड़ोसियों के लक्ष्य मानों का औसत है। इसे निकटतम पड़ोसी स्मूथिंग के रूप में जाना जाता है। यदि k=1 है, तो यह निकटतम पड़ोसी इंटरपोलेशन बन जाता है, जहां भविष्यवाणी किया गया मान बिल्कुल निकटतम प्रशिक्षण बिंदु के मान के बराबर होता है। भारित वेरिएंट निकट पड़ोसियों को अधिक प्रभाव देते हैं, अक्सर दूरी के व्युत्क्रम (1/d) के अनुपात में भार का उपयोग करते हैं।
दूरी मीट्रिक और फीचर स्केलिंग
दूरी मीट्रिक का चुनाव महत्वपूर्ण है। निरंतर फीचर्स के लिए, यूक्लिडियन दूरी सबसे आम है। असतत फीचर्स के लिए, जैसे पाठ वर्गीकरण में, हैमिंग दूरी या ओवरलैप मीट्रिक का उपयोग किया जाता है। विशेष डोमेन जैसे जीन अभिव्यक्ति विश्लेषण में, सहसंबंध गुणांक (पियर्सन, स्पीयरमैन) का उपयोग किया गया है। दूरी पर एल्गोरिथ्म की निर्भरता का मतलब है कि विभिन्न इकाइयों या स्केल वाले फीचर्स गणना पर हावी हो सकते हैं। इसलिए, प्रत्येक फीचर को एक सामान्य स्केल (जैसे, z-स्कोर या मिन-मैक्स स्केलिंग) में सामान्य करना आवश्यक है ताकि समान योगदान सुनिश्चित हो सके। यह प्रीप्रोसेसिंग चरण सटीकता में काफी सुधार कर सकता है।
सांख्यिकीय गुण
सांख्यिकीय दृष्टिकोण से, k-NN एक गैर-पैरामीट्रिक विधि है क्योंकि यह अंतर्निहित डेटा वितरण के लिए एक कार्यात्मक रूप नहीं मानता है। प्रशिक्षण डेटा को जोड़े (X_i, Y_i) माना जाता है जहां X_i एक फीचर वेक्टर है और Y_i वर्ग लेबल है। दिए गए क्वेरी बिंदु x के लिए, प्रशिक्षण बिंदुओं को x से उनकी दूरी के आधार पर पुनर्व्यवस्थित किया जाता है। एल्गोरिथ्म की त्रुटि दर नमूना आकार बढ़ने पर बेयस त्रुटि दर में परिवर्तित हो जाती है, बशर्ते k उचित रूप से n के साथ बढ़े और k/n शून्य की ओर बढ़े। यह संपत्ति, जो कवर और हार्ट द्वारा स्थापित की गई थी, k-NN को अनंत रूप से इष्टतम बनाती है। हालांकि, सीमित नमूनों में, एल्गोरिथ्म आयामीता के अभिशाप से ग्रस्त है: जैसे-जैसे फीचर्स की संख्या बढ़ती है, स्थान की मात्रा तेजी से बढ़ती है, और बिंदु विरल हो जाते हैं, जिससे दूरी माप कम सार्थक हो जाती है।
लाभ और हानि
k-NN का एक प्रमुख लाभ इसकी सरलता और प्रशिक्षण चरण की अनुपस्थिति है। नए डेटा बिंदुओं को जोड़कर इसे आसानी से अपडेट किया जा सकता है। यह बहु-वर्ग समस्याओं के लिए भी प्रभावी है और जटिल निर्णय सीमाओं को पकड़ सकता है। हालांकि, इसकी उल्लेखनीय हानियां हैं। भविष्यवाणी का समय धीमा है क्योंकि सभी प्रशिक्षण बिंदुओं तक दूरी की गणना करने की आवश्यकता होती है, जो बड़े डेटासेट के लिए अनुकूलन (जैसे, केडी-ट्री या बॉल ट्री का उपयोग) के बिना अव्यावहारिक बनाता है। यह अप्रासंगिक फीचर्स और शोर वाले डेटा के प्रति संवेदनशील है। एल्गोरिथ्म डेटा की स्थानीय संरचना के प्रति भी संवेदनशील है, जिसका अर्थ है कि आउटलायर या असंतुलित वर्ग वितरण परिणामों को तिरछा कर सकते हैं। तिरछे वितरण में, बहुसंख्यक वर्ग हावी होते हैं क्योंकि वे k पड़ोसियों के बीच दिखाई देने की अधिक संभावना रखते हैं। व्युत्क्रम दूरी द्वारा भारित करना या अमूर्त तकनीकों का उपयोग इसे कम कर सकता है।
वेरिएंट और विस्तार
कई वेरिएंट k-NN की सीमाओं को संबोधित करते हैं। भारित k-NN दूरी के आधार पर पड़ोसियों को भार निर्दिष्ट करता है, ताकि निकट बिंदुओं का अधिक प्रभाव हो। दूरी मीट्रिक सीखने की विधियां, जैसे लार्ज मार्जिन निकटतम पड़ोसी और पड़ोस घटक विश्लेषण, सटीकता में सुधार के लिए एक कस्टम दूरी मीट्रिक सीखती हैं। एडिटेड k-NN सामान्यीकरण में सुधार के लिए शोर या गलत वर्गीकृत प्रशिक्षण बिंदुओं को हटाता है। संघनित k-NN प्रशिक्षण सेट आकार को केवल उन बिंदुओं को रखकर कम करता है जो वर्गीकरण के लिए आवश्यक हैं। स्थानीय रूप से अनुकूली k-NN क्वेरी बिंदु के आसपास के क्षेत्र के घनत्व के आधार पर k को समायोजित करता है। इन वेरिएंट को प्रदर्शन में सुधार के लिए Machine learning और Artificial intelligence जैसे क्षेत्रों में लागू किया गया है।
अनुप्रयोग
k-NN एल्गोरिथ्म विभिन्न डोमेन में उपयोग किया जाता है। पैटर्न पहचान में, इसे छवि वर्गीकरण और हस्तलेखन पहचान पर लागू किया जाता है। चिकित्सा में, इसका उपयोग रोगी सुविधाओं के आधार पर निदान के लिए किया जाता है। वित्त में, यह क्रेडिट स्कोरिंग और धोखाधड़ी का पता लगाने में मदद करता है। अनुशंसा प्रणालियों में, यह समान उपयोगकर्ताओं या आइटमों को ढूंढता है। बायोइन्फॉरमैटिक्स में, यह जीन अभिव्यक्ति डेटा को वर्गीकृत करता है। इसकी सरलता इसे Neural network और Deep learning जैसे अधिक जटिल मॉडलों की तुलना के लिए एक सामान्य आधार रेखा बनाती है।
अन्य विधियों से संबंध
k-NN उदाहरण-आधारित शिक्षण का एक रूप है, जो Neural network या Support Vector Machine जैसे मॉडल-आधारित दृष्टिकोणों से अलग है जो प्रशिक्षण के दौरान एक स्पष्ट मॉडल बनाते हैं। यह गैर-पैरामीट्रिक घनत्व अनुमान से भी संबंधित है। Machine learning के व्यापक संदर्भ में, k-NN अक्सर एक बेंचमार्क के रूप में उपयोग किया जाता है। इसने स्थानीयता-संवेदनशील हैशिंग और अनुमानित निकटतम पड़ोसी खोज के विकास को प्रभावित किया है, जो बड़े पैमाने पर प्रणालियों में उपयोग की जाती हैं। जबकि Deep learning जैसी आधुनिक विधियों ने कई कार्यों में k-NN को पीछे छोड़ दिया है, k-NN छोटे डेटासेट और व्याख्यात्मक भविष्यवाणियों के लिए मूल्यवान बना हुआ है।
व्यावहारिक विचार
k-NN लागू करते समय, कई व्यावहारिक मुद्दे उत्पन्न होते हैं। k का मान आमतौर पर क्रॉस-वैलिडेशन के माध्यम से चुना जाता है। द्विआधारी वर्गीकरण में टाई से बचने के लिए k के विषम मान अक्सर उपयोग किए जाते हैं। फीचर स्केलिंग आवश्यक है। केडी-ट्री जैसी कुशल डेटा संरचनाएं निकटतम पड़ोसी खोज को तेज कर सकती हैं, लेकिन उच्च आयामों में वे घट जाती हैं। बहुत बड़े डेटासेट के लिए, अनुमानित विधियां आवश्यक हैं। एल्गोरिथ्म की मेमोरी उपयोग प्रशिक्षण सेट आकार के अनुपात में है, जो एक सीमा हो सकती है। आधुनिक अनुप्रयोगों में, k-NN को कभी-कभी अन्य एल्गोरिदम के साथ जोड़ा जाता है, जैसे कि Neural network से सीखे गए एम्बेडिंग के शीर्ष पर अंतिम क्लासिफायर के रूप में उपयोग करना।
यह भी देखें
- Machine learning
- Artificial intelligence
- Neural network
- Deep learning
- Stanford AI Lab
- MIT CSAIL
- Carnegie Mellon University
- BAIR (Berkeley AI Research)
- Xerox PARC
- Thomas G. Dietterich
- Michael I. Jordan
- Daphne Koller
- Anima Anandkumar
- Samy Bengio
- Joshua Tenenbaum
- Brendan Lake
- Melanie Mitchell
- Aaron Courville
- Alexei Efros
- Ali Rahimi