k-निकटतम पड़ोसी एल्गोरिथ्म (k-NN) एक गैर-पैरामीट्रिक, उदाहरण-आधारित शिक्षण विधि है जिसका उपयोग वर्गीकरण और प्रतिगमन के लिए किया जाता है। दोनों मामलों में, इनपुट में एक फीचर स्पेस में k निकटतम प्रशिक्षण उदाहरण शामिल होते हैं। आउटपुट इस बात पर निर्भर करता है कि k-NN का उपयोग वर्गीकरण या प्रतिगमन के लिए किया जाता है या नहीं: वर्गीकरण में, आउटपुट एक वर्ग सदस्यता है, जो k निकटतम पड़ोसियों के बीच बहुमत वोट द्वारा निर्धारित होती है; प्रतिगमन में, आउटपुट k निकटतम पड़ोसियों के मानों का औसत (या भारित औसत) होता है। k-NN एक प्रकार की आलसी शिक्षण (lazy learning) है, जहां फ़ंक्शन का केवल स्थानीय रूप से अनुमान लगाया जाता है, और सभी गणना फ़ंक्शन मूल्यांकन तक स्थगित कर दी जाती है। दूरी गणनाओं पर निर्भर होने के कारण, एल्गोरिथ्म डेटा की स्थानीय संरचना और दूरी मीट्रिक की पसंद के प्रति संवेदनशील है।
एल्गोरिथ्म पहली बार 1951 में एवलिन फिक्स और जोसेफ हॉजेस द्वारा यूएस एयर फोर्स स्कूल ऑफ एविएशन मेडिसिन में विकसित किया गया था, मूल रूप से एक गैर-पैरामीट्रिक वर्गीकरण तकनीक के रूप में। इसे बाद में 1967 में थॉमस कवर और पीटर हार्ट द्वारा विस्तारित और औपचारिक रूप दिया गया, जिन्होंने इसकी स्पर्शोन्मुख त्रुटि सीमाएं स्थापित कीं। तब से, k-NN Machine learning, पैटर्न पहचान और डेटा माइनिंग में एक मौलिक उपकरण बन गया है, जिसे अक्सर अधिक जटिल मॉडलों के लिए आधार रेखा के रूप में उपयोग किया जाता है।
यह कैसे काम करता है
एक क्वेरी बिंदु दिए जाने पर, एल्गोरिथ्म प्रत्येक प्रशिक्षण उदाहरण की दूरी (आमतौर पर यूक्लिडियन, मैनहट्टन, या मिंकोव्स्की) की गणना करता है। फिर यह सबसे छोटी दूरी वाले k प्रशिक्षण उदाहरणों का चयन करता है। वर्गीकरण के लिए, अनुमानित लेबल वह है जो इन k पड़ोसियों के बीच सबसे अधिक बार आता है। प्रतिगमन के लिए, अनुमानित मान पड़ोसियों के लक्ष्य मानों का माध्य है। k का चुनाव महत्वपूर्ण है: एक छोटा k (जैसे, 1) उच्च विचरण और शोर के प्रति संवेदनशीलता की ओर ले जाता है, जबकि एक बड़ा k स्थानीय पैटर्न को सुचारू कर सकता है, पूर्वाग्रह बढ़ा सकता है। सामान्य प्रथा क्रॉस-वैलिडेशन के माध्यम से k का चयन करना है, अक्सर टाई से बचने के लिए द्विआधारी वर्गीकरण के लिए विषम मानों का उपयोग करना।
एल्गोरिथ्म को एक दूरी मीट्रिक की भी आवश्यकता होती है। यूक्लिडियन दूरी निरंतर सुविधाओं के लिए मानक है, लेकिन उच्च-आयामी या श्रेणीबद्ध डेटा के लिए, हैमिंग दूरी या कोसाइन समानता जैसे अन्य मीट्रिक का उपयोग किया जा सकता है। फीचर स्केलिंग (जैसे, सामान्यीकरण या मानकीकरण) आवश्यक है क्योंकि बड़ी श्रेणियों वाली सुविधाएं दूरी गणना पर हावी होती हैं।
गुण और प्रकार
k-NN गैर-पैरामीट्रिक है, जिसका अर्थ है कि यह अंतर्निहित डेटा वितरण के बारे में कोई मजबूत धारणा नहीं बनाता है। यह उदाहरण-आधारित भी है, जो पूरे प्रशिक्षण सेट को संग्रहीत करता है और भविष्यवाणी के समय सीधे इसका उपयोग करता है। यह प्रशिक्षण को तुच्छ बनाता है (अनिवार्य रूप से केवल डेटा संग्रहीत करना) लेकिन भविष्यवाणी को कम्प्यूटेशनल रूप से महंगा बनाता है, प्रति क्वेरी O(nd) की समय जटिलता के साथ, जहां n प्रशिक्षण नमूनों की संख्या है और d सुविधाओं की संख्या है।
कई प्रकार इन सीमाओं को संबोधित करते हैं। भारित k-NN निकटतम पड़ोसियों को अधिक प्रभाव प्रदान करता है, अक्सर व्युत्क्रम दूरी भार का उपयोग करता है। स्थानीय रूप से भारित प्रतिगमन पड़ोस के भीतर एक रैखिक मॉडल फिट करता है। बड़े डेटासेट के लिए, अनुमानित निकटतम पड़ोसी खोज तकनीकें, जैसे कि k-d पेड़, बॉल पेड़, या स्थानीयता-संवेदनशील हैशिंग, खोज लागत को कम करती हैं। उच्च आयामों में, आयामीता का अभिशाप प्रदर्शन को खराब कर देता है, क्योंकि दूरियां कम विभेदक हो जाती हैं; आयामीता में कमी या फीचर चयन अक्सर लागू किया जाता है।
अनुप्रयोग
एल्गोरिथ्म का व्यापक रूप से Computer vision में छवि वर्गीकरण के लिए, Natural language processing में पाठ वर्गीकरण के लिए, और बायोइन्फॉर्मेटिक्स में जीन अभिव्यक्ति विश्लेषण के लिए उपयोग किया जाता है। यह अनुशंसा प्रणालियों में दिखाई देता है, जहां यह समान प्राथमिकताओं वाले उपयोगकर्ताओं या आइटम ढूंढता है। वित्त में, इसका उपयोग क्रेडिट स्कोरिंग और धोखाधड़ी का पता लगाने के लिए किया जाता है। इसकी सरलता और व्याख्यात्मकता इसे खोजपूर्ण विश्लेषण के लिए एक सामान्य पहला विकल्प और Neural network जैसे अधिक जटिल मॉडलों के खिलाफ एक बेंचमार्क बनाती है।
ताकत और सीमाएं
k-NN की मुख्य ताकत इसकी सरलता, कार्यान्वयन में आसानी, और कम से मध्यम आयामीता वाले छोटे से मध्यम आकार के डेटासेट पर प्रभावशीलता है। इसे किसी प्रशिक्षण चरण की आवश्यकता नहीं होती है, जिससे यह वृद्धिशील शिक्षण के लिए उपयुक्त हो जाता है। हालांकि, इसकी सीमाओं में उच्च मेमोरी उपयोग (सभी प्रशिक्षण डेटा संग्रहीत करना), धीमी भविष्यवाणी समय, अप्रासंगिक सुविधाओं और शोर के प्रति संवेदनशीलता, और उच्च-आयामी स्थानों में खराब प्रदर्शन शामिल हैं। यह यह भी मानता है कि सभी सुविधाएं समान रूप से महत्वपूर्ण हैं, जो व्यवहार में शायद ही सच है।
अन्य विधियों से संबंध
k-NN की तुलना अक्सर निर्णय पेड़ और सपोर्ट वेक्टर मशीन जैसी अन्य गैर-पैरामीट्रिक विधियों से की जाती है। यह Machine learning में एक आधारभूत तकनीक है और इसे अक्सर Artificial intelligence पाठ्यक्रम के साथ पढ़ाया जाता है। इसके सिद्धांत सिंथेटिक पड़ोसी उत्पन्न करने वाली Data Augmentation तकनीकों जैसी अधिक उन्नत विधियों को रेखांकित करते हैं, और इसका उपयोग Curriculum Learning में प्रशिक्षण उदाहरणों को कठिनाई के अनुसार क्रमबद्ध करने के तरीके के रूप में किया जाता है। आधुनिक अभ्यास में, k-NN का उपयोग कभी-कभी मीट्रिक लर्निंग के लिए डीप लर्निंग मॉडल में अंतिम परत के रूप में किया जाता है, जहां सीखे गए एम्बेडिंग की तुलना निकटतम पड़ोसी खोज का उपयोग करके की जाती है।
यह भी देखें
संदर्भ
- Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory.
- Fix, E., & Hodges, J. L. (1951). Discriminatory analysis, nonparametric discrimination: consistency properties. USAF School of Aviation Medicine.
- Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician.