आइसोमैप: Difference between revisions
From Vigyanwiki
(→परिचय) |
No edit summary |
||
| Line 1: | Line 1: | ||
आइसोमैप एक अरैखिक आयामीता में कमी विधि है। यह कई व्यापक रूप से उपयोग किए जाने वाली निम्न-आयामी अंत:स्थापन विधियों में से एक है। <ref>{{cite journal |last1=Tenenbaum |first1=Joshua B. |last2=Silva |first2=Vin de |last3=Langford |first3=John C. |title=नॉनलाइनियर डायमेंशनलिटी रिडक्शन के लिए एक ग्लोबल जियोमेट्रिक फ्रेमवर्क|journal=Science |date=22 December 2000 |volume=290 |issue=5500 |pages=2319–2323 |doi=10.1126/science.290.5500.2319}}</ref> आइसोमैप का उपयोग उच्च-आयामी डेटा बिंदुओं के एक सेट के अर्ध-सममितीय, निम्न-आयामी अंत:स्थापन की गणना के लिए किया जाता है। एल्गोरिथ्म [[कई गुना]] पर प्रत्येक डेटा बिंदु के पड़ोसियों के मोटे अनुमान के आधार पर डेटा मैनिफोल्ड की आंतरिक ज्यामिति का अनुमान लगाने के लिए एक सरल विधि प्रदान करता है। आइसोमैप अत्यधिक कुशल है और | आइसोमैप एक अरैखिक आयामीता में कमी विधि है। यह कई व्यापक रूप से उपयोग किए जाने वाली निम्न-आयामी अंत:स्थापन विधियों में से एक है। <ref>{{cite journal |last1=Tenenbaum |first1=Joshua B. |last2=Silva |first2=Vin de |last3=Langford |first3=John C. |title=नॉनलाइनियर डायमेंशनलिटी रिडक्शन के लिए एक ग्लोबल जियोमेट्रिक फ्रेमवर्क|journal=Science |date=22 December 2000 |volume=290 |issue=5500 |pages=2319–2323 |doi=10.1126/science.290.5500.2319}}</ref> आइसोमैप का उपयोग उच्च-आयामी डेटा बिंदुओं के एक सेट के अर्ध-सममितीय, निम्न-आयामी अंत:स्थापन की गणना के लिए किया जाता है। एल्गोरिथ्म [[कई गुना]] पर प्रत्येक डेटा बिंदु के पड़ोसियों के मोटे अनुमान के आधार पर डेटा मैनिफोल्ड की आंतरिक ज्यामिति का अनुमान लगाने के लिए एक सरल विधि प्रदान करता है। आइसोमैप अत्यधिक कुशल है और सामान्यतः डेटा स्रोतों और आयामों की एक विस्तृत श्रृंखला के लिए लागू होता है। | ||
== परिचय == | == परिचय == | ||
आइसोमैप सममितीय मैपिंग विधियों का एक प्रतिनिधि है, और एक भारित ग्राफ़ द्वारा लगाई गई भूगर्भीय दूरियों को | आइसोमैप सममितीय मैपिंग विधियों का एक प्रतिनिधि है, और एक भारित ग्राफ़ द्वारा लगाई गई भूगर्भीय दूरियों को सम्मलित करके मीट्रिक [[बहुआयामी स्केलिंग]] (एमडीएस) का विस्तार करता है। विशिष्ट होने के लिए, मीट्रिक एमडीएस का प्रतिष्ठित स्केलिंग डेटा बिंदुओं के बीच जोड़ीदार दूरी के आधार पर निम्न-आयामी एम्बेडिंग करता है, जिसे सामान्यतः सीधी रेखा [[यूक्लिडियन दूरी]] का उपयोग करके मापा जाता है। आइसोमैप प्रतिष्ठित स्केलिंग में अंत:स्थापन एक पड़ोस ग्राफ द्वारा प्रेरित [[जियोडेसिक दूरी]] के उपयोग से अलग है। परिणामी अंत:स्थापन में कई गुना संरचना को सम्मलित करने के लिए ऐसा किया जाता है। आइसोमैप जियोडेसिक दूरी को दो नोड्स के बीच सबसे छोटे पथ के किनारे के वजन (किनारे की "लागत") के योग के रूप में परिभाषित करता है (उदाहरण के लिए दिज्क्स्ट्रा के एल्गोरिथ्म का उपयोग करके गणना की गई)। जियोडेसिक [[ दूरी मैट्रिक्स |दूरी मैट्रिक्स]] के शीर्ष एन [[आइजन्वेक्टर]], नए एन-आयामी यूक्लिडियन स्थान में निर्देशांक का प्रतिनिधित्व करते हैं। | ||
== एल्गोरिथम == | == एल्गोरिथम == | ||
| Line 8: | Line 8: | ||
* प्रत्येक बिंदु के पड़ोसियों का निर्धारण करें। | * प्रत्येक बिंदु के पड़ोसियों का निर्धारण करें। | ||
** सभी बिंदु एक निश्चित त्रिज्या में। | ** सभी बिंदु एक निश्चित त्रिज्या में। | ||
** ''K'' निकटतम | ** ''K'' निकटतम निकटतम। | ||
* आस-पड़ोस का ग्राफ बनाएँ। | * आस-पड़ोस का ग्राफ बनाएँ। | ||
** यदि यह K निकटतम | ** यदि यह K निकटतम निकटतम है तो प्रत्येक बिंदु दूसरे से जुड़ा हुआ है। | ||
** किनारे की लंबाई यूक्लिडियन दूरी के बराबर है। | ** किनारे की लंबाई यूक्लिडियन दूरी के बराबर है। | ||
* दो नोड्स के बीच सबसे छोटे पथ की गणना करें। | * दो नोड्स के बीच सबसे छोटे पथ की गणना करें। | ||
| Line 19: | Line 19: | ||
== आइसोमैप के एक्सटेंशन == | == आइसोमैप के एक्सटेंशन == | ||
* लैंडमार्क आइसोमैप (एल-आईएसओएमएपी): लैंडमार्क-आइसोमैप इसोमैप का एक रूप है जो इसोमैप से तेज है। | * लैंडमार्क आइसोमैप (एल-आईएसओएमएपी): लैंडमार्क-आइसोमैप इसोमैप का एक रूप है जो इसोमैप से तेज है। चूंकि, कई गुना की परिशुद्धता सीमांत कारक से समझौता की जाती है। इस एल्गोरिथम में, कुल N डेटा बिंदुओं में से n << N लैंडमार्क बिंदुओं का उपयोग किया जाता है और लैंडमार्क बिंदुओं के लिए प्रत्येक डेटा बिंदु के बीच जियोडेसिक दूरी के एनएक्सएन मैट्रिक्स की गणना की जाती है। लैंडमार्क-एमडीएस (एलएमडीएस) तब सभी डेटा बिंदुओं के यूक्लिडियन एम्बेडिंग को जाँच के लिए मैट्रिक्स पर लागू किया जाता है।<ref name="mit">{{cite web |title=गैर-रैखिक आयामी कमी में वैश्विक बनाम स्थानीय तरीके|url=http://web.mit.edu/cocosci/Papers/nips02-localglobal-in-press.pdf |url-status=dead |archive-url=http://web.mit.edu/cocosci/archive/Papers/nips02-localglobal-in-press.pdf |archive-date=2023-03-30 |access-date=2014-09-09}}</ref> | ||
* सी आइसोमैप: सी-आइसोमैप में उच्च घनत्व वाले क्षेत्रों को आवर्धित करना और कई गुना डेटा बिंदुओं के कम घनत्व वाले क्षेत्रों को सिकोड़ना | * सी आइसोमैप: सी-आइसोमैप में उच्च घनत्व वाले क्षेत्रों को आवर्धित करना और कई गुना डेटा बिंदुओं के कम घनत्व वाले क्षेत्रों को सिकोड़ना सम्मलित है। बहु आयामी स्केलिंग (एमडीएस) में अधिकतम किनारे को संशोधित किया जाता है, बाकी सब कुछ अप्रभावित रहता है।<ref name="mit" /> | ||
*समानांतर ट्रांसपोर्ट अनफोल्डिंग: इसके | *समानांतर ट्रांसपोर्ट अनफोल्डिंग: इसके अतिरिक्त [[समानांतर परिवहन]] आधारित सन्निकटन के साथ दिज्क्स्ट्रा पथ-आधारित जियोडेसिक दूरी अनुमानों को प्रतिस्थापित करता है, जिससे नमूनाकरण में अनियमितता और शून्यता की मजबूती में सुधार होता है।<ref>{{Cite journal|last=Budninskiy|first=Max|last2=Yin|first2=Gloria|last3=Feng|first3=Leman|last4=Tong|first4=Yiying|last5=Desbrun|first5=Mathieu|date=2019|title=Parallel Transport Unfolding: A Connection-Based Manifold Learning Approach|url=https://epubs.siam.org/doi/10.1137/18M1196133|journal=SIAM Journal on Applied Algebra and Geometry|language=en|volume=3|issue=2|pages=266–291|doi=10.1137/18M1196133|issn=2470-6566|arxiv=1806.09039}}</ref> | ||
== संभावित मुद्दे == | == संभावित मुद्दे == | ||
अड़ोस-पड़ोस के ग्राफ में प्रत्येक डेटा बिंदु के संपर्क को उच्च-आयामी स्थान में उसके निकटतम k यूक्लिडियन पड़ोसियों के रूप में परिभाषित किया गया है। यह कदम "शॉर्ट-सर्किट त्रुटियों" के लिए असुरक्षित है यदि k कई गुना संरचना के संबंध में बहुत बड़ा है या यदि डेटा में रव ( अथवा नॉयज) कई गुना से बिंदुओं को थोड़ा दूर ले जाता है।<ref>M. Balasubramanian, E. L. Schwartz, The Isomap Algorithm and Topological Stability. Science 4 January 2002: | अड़ोस-पड़ोस के ग्राफ में प्रत्येक डेटा बिंदु के संपर्क को उच्च-आयामी स्थान में उसके निकटतम k यूक्लिडियन पड़ोसियों के रूप में परिभाषित किया गया है। यह कदम "शॉर्ट-सर्किट त्रुटियों" के लिए असुरक्षित है यदि k कई गुना संरचना के संबंध में बहुत बड़ा है या यदि डेटा में रव ( अथवा नॉयज) कई गुना से बिंदुओं को थोड़ा दूर ले जाता है।<ref>M. Balasubramanian, E. L. Schwartz, The Isomap Algorithm and Topological Stability. Science 4 January 2002: | ||
Vol. 295 no. 5552 p. 7</ref> यहां तक कि एक शॉर्ट-सर्किट त्रुटि भी जियोडेसिक दूरी मैट्रिक्स में कई प्रविष्टियों को बदल सकती है, जो बदले में एक बहुत भिन्न (और गलत) निम्न-आयामी एम्बेडिंग का कारण बन सकती है। इसके विपरीत, यदि k बहुत छोटा है, तो आस-पड़ोस का ग्राफ सटीक रूप से जियोडेसिक पथों का अनुमान लगाने के लिए बहुत विरल हो सकता है। लेकिन इस एल्गोरिद्म में सुधार किए गए हैं | Vol. 295 no. 5552 p. 7</ref> यहां तक कि एक शॉर्ट-सर्किट त्रुटि भी जियोडेसिक दूरी मैट्रिक्स में कई प्रविष्टियों को बदल सकती है, जो बदले में एक बहुत भिन्न (और गलत) निम्न-आयामी एम्बेडिंग का कारण बन सकती है। इसके विपरीत, यदि k बहुत छोटा है, तो आस-पड़ोस का ग्राफ सटीक रूप से जियोडेसिक पथों का अनुमान लगाने के लिए बहुत विरल हो सकता है। लेकिन इस एल्गोरिद्म में सुधार किए गए हैं जिससे कि यह विरल और रव (अथवा नॉयज) वाले डेटा सेट के लिए श्रेष्ठ काम कर सके।<ref>''A. Saxena'', ''A. Gupta'' and ''A. Mukerjee''. Non-linear dimensionality reduction by locally linear Isomaps, ''. Lecture Notes in Computer Science'', 3316:1038–1043, 2004.</ref> | ||
== अन्य विधियों के साथ संबंध == | == अन्य विधियों के साथ संबंध == | ||
शास्त्रीय स्केलिंग और प्रमुख घटक विश्लेषण के बीच संबंध के | शास्त्रीय स्केलिंग और प्रमुख घटक विश्लेषण के बीच संबंध के पश्चात, मीट्रिक बहुआयामी स्केलिंग की [[कर्नेल पीसीए]] के रूप में व्याख्या कि जा सकती है। इसी तरह, आइसोमैप में जियोडेसिक दूरी मैट्रिक्स को [[कर्नेल विधि|कर्नेल मैट्रिक्स]] के रूप में देखा जा सकता है। आइसोमैप में दोगुना केंद्रित जियोडेसिक दूरी मैट्रिक्स K रूप का है | ||
: <math> K = -\frac{1}{2} HD^2 H\, </math> | : <math> K = -\frac{1}{2} HD^2 H\, </math> | ||
| Line 32: | Line 32: | ||
: <math> H = I_n-\frac{1}{N} e_N e^T_N, \quad\text{where }e_N= [1\ \dots\ 1]^T \in \mathbb{R}^N. </math> | : <math> H = I_n-\frac{1}{N} e_N e^T_N, \quad\text{where }e_N= [1\ \dots\ 1]^T \in \mathbb{R}^N. </math> | ||
हालाँकि, कर्नेल मैट्रिक्स K हमेशा सकारात्मक अर्ध-निश्चित नहीं होता है। कर्नेल आइसोमैप के लिए मुख्य विचार यह है कि इस K को एक स्थिर-शिफ्टिंग विधि का उपयोग करके एक मर्सर कर्नेल मैट्रिक्स (जो कि सकारात्मक अर्ध-निश्चित है) के रूप में बनाया जाए, | हालाँकि, कर्नेल मैट्रिक्स K हमेशा सकारात्मक अर्ध-निश्चित नहीं होता है। कर्नेल आइसोमैप के लिए मुख्य विचार यह है कि इस K को एक स्थिर-शिफ्टिंग विधि का उपयोग करके एक मर्सर कर्नेल मैट्रिक्स (जो कि सकारात्मक अर्ध-निश्चित है) के रूप में बनाया जाए, जिससे कि इसे कर्नेल पीसीए से संबंधित किया जा सके, जिससे कि सामान्यीकरण गुण स्वाभाविक रूप से उभर आए।<ref>H. Choi, S. Choi, Robust Kernel Isomap, Pattern Recognition, Vol. 40, No. 3, pp. 853-862, 2007</ref> | ||
== यह भी देखें == | == यह भी देखें == | ||
* कर्नेल पीसीए | * कर्नेल पीसीए | ||
Revision as of 20:42, 26 May 2023
आइसोमैप एक अरैखिक आयामीता में कमी विधि है। यह कई व्यापक रूप से उपयोग किए जाने वाली निम्न-आयामी अंत:स्थापन विधियों में से एक है। [1] आइसोमैप का उपयोग उच्च-आयामी डेटा बिंदुओं के एक सेट के अर्ध-सममितीय, निम्न-आयामी अंत:स्थापन की गणना के लिए किया जाता है। एल्गोरिथ्म कई गुना पर प्रत्येक डेटा बिंदु के पड़ोसियों के मोटे अनुमान के आधार पर डेटा मैनिफोल्ड की आंतरिक ज्यामिति का अनुमान लगाने के लिए एक सरल विधि प्रदान करता है। आइसोमैप अत्यधिक कुशल है और सामान्यतः डेटा स्रोतों और आयामों की एक विस्तृत श्रृंखला के लिए लागू होता है।
परिचय
आइसोमैप सममितीय मैपिंग विधियों का एक प्रतिनिधि है, और एक भारित ग्राफ़ द्वारा लगाई गई भूगर्भीय दूरियों को सम्मलित करके मीट्रिक बहुआयामी स्केलिंग (एमडीएस) का विस्तार करता है। विशिष्ट होने के लिए, मीट्रिक एमडीएस का प्रतिष्ठित स्केलिंग डेटा बिंदुओं के बीच जोड़ीदार दूरी के आधार पर निम्न-आयामी एम्बेडिंग करता है, जिसे सामान्यतः सीधी रेखा यूक्लिडियन दूरी का उपयोग करके मापा जाता है। आइसोमैप प्रतिष्ठित स्केलिंग में अंत:स्थापन एक पड़ोस ग्राफ द्वारा प्रेरित जियोडेसिक दूरी के उपयोग से अलग है। परिणामी अंत:स्थापन में कई गुना संरचना को सम्मलित करने के लिए ऐसा किया जाता है। आइसोमैप जियोडेसिक दूरी को दो नोड्स के बीच सबसे छोटे पथ के किनारे के वजन (किनारे की "लागत") के योग के रूप में परिभाषित करता है (उदाहरण के लिए दिज्क्स्ट्रा के एल्गोरिथ्म का उपयोग करके गणना की गई)। जियोडेसिक दूरी मैट्रिक्स के शीर्ष एन आइजन्वेक्टर, नए एन-आयामी यूक्लिडियन स्थान में निर्देशांक का प्रतिनिधित्व करते हैं।
एल्गोरिथम
आइसोमैप एल्गोरिथम का एक बहुत ही उच्च स्तरीय विवरण नीचे दिया गया है।
- प्रत्येक बिंदु के पड़ोसियों का निर्धारण करें।
- सभी बिंदु एक निश्चित त्रिज्या में।
- K निकटतम निकटतम।
- आस-पड़ोस का ग्राफ बनाएँ।
- यदि यह K निकटतम निकटतम है तो प्रत्येक बिंदु दूसरे से जुड़ा हुआ है।
- किनारे की लंबाई यूक्लिडियन दूरी के बराबर है।
- दो नोड्स के बीच सबसे छोटे पथ की गणना करें।
- दिज्क्स्ट्रा का एल्गोरिथ्म
- फ्लोयड-वॉर्शल एल्गोरिथम
- निम्न-आयामी एम्बेडिंग की गणना करें।
- बहुआयामी स्केलिंग
आइसोमैप के एक्सटेंशन
- लैंडमार्क आइसोमैप (एल-आईएसओएमएपी): लैंडमार्क-आइसोमैप इसोमैप का एक रूप है जो इसोमैप से तेज है। चूंकि, कई गुना की परिशुद्धता सीमांत कारक से समझौता की जाती है। इस एल्गोरिथम में, कुल N डेटा बिंदुओं में से n << N लैंडमार्क बिंदुओं का उपयोग किया जाता है और लैंडमार्क बिंदुओं के लिए प्रत्येक डेटा बिंदु के बीच जियोडेसिक दूरी के एनएक्सएन मैट्रिक्स की गणना की जाती है। लैंडमार्क-एमडीएस (एलएमडीएस) तब सभी डेटा बिंदुओं के यूक्लिडियन एम्बेडिंग को जाँच के लिए मैट्रिक्स पर लागू किया जाता है।[2]
- सी आइसोमैप: सी-आइसोमैप में उच्च घनत्व वाले क्षेत्रों को आवर्धित करना और कई गुना डेटा बिंदुओं के कम घनत्व वाले क्षेत्रों को सिकोड़ना सम्मलित है। बहु आयामी स्केलिंग (एमडीएस) में अधिकतम किनारे को संशोधित किया जाता है, बाकी सब कुछ अप्रभावित रहता है।[2]
- समानांतर ट्रांसपोर्ट अनफोल्डिंग: इसके अतिरिक्त समानांतर परिवहन आधारित सन्निकटन के साथ दिज्क्स्ट्रा पथ-आधारित जियोडेसिक दूरी अनुमानों को प्रतिस्थापित करता है, जिससे नमूनाकरण में अनियमितता और शून्यता की मजबूती में सुधार होता है।[3]
संभावित मुद्दे
अड़ोस-पड़ोस के ग्राफ में प्रत्येक डेटा बिंदु के संपर्क को उच्च-आयामी स्थान में उसके निकटतम k यूक्लिडियन पड़ोसियों के रूप में परिभाषित किया गया है। यह कदम "शॉर्ट-सर्किट त्रुटियों" के लिए असुरक्षित है यदि k कई गुना संरचना के संबंध में बहुत बड़ा है या यदि डेटा में रव ( अथवा नॉयज) कई गुना से बिंदुओं को थोड़ा दूर ले जाता है।[4] यहां तक कि एक शॉर्ट-सर्किट त्रुटि भी जियोडेसिक दूरी मैट्रिक्स में कई प्रविष्टियों को बदल सकती है, जो बदले में एक बहुत भिन्न (और गलत) निम्न-आयामी एम्बेडिंग का कारण बन सकती है। इसके विपरीत, यदि k बहुत छोटा है, तो आस-पड़ोस का ग्राफ सटीक रूप से जियोडेसिक पथों का अनुमान लगाने के लिए बहुत विरल हो सकता है। लेकिन इस एल्गोरिद्म में सुधार किए गए हैं जिससे कि यह विरल और रव (अथवा नॉयज) वाले डेटा सेट के लिए श्रेष्ठ काम कर सके।[5]
अन्य विधियों के साथ संबंध
शास्त्रीय स्केलिंग और प्रमुख घटक विश्लेषण के बीच संबंध के पश्चात, मीट्रिक बहुआयामी स्केलिंग की कर्नेल पीसीए के रूप में व्याख्या कि जा सकती है। इसी तरह, आइसोमैप में जियोडेसिक दूरी मैट्रिक्स को कर्नेल मैट्रिक्स के रूप में देखा जा सकता है। आइसोमैप में दोगुना केंद्रित जियोडेसिक दूरी मैट्रिक्स K रूप का है
जहां भूगर्भीय दूरी मैट्रिक्स डी = [डीजेij], का तत्ववार वर्ग है, एच केंद्रित मैट्रिक्स है, द्वारा दिया गया
हालाँकि, कर्नेल मैट्रिक्स K हमेशा सकारात्मक अर्ध-निश्चित नहीं होता है। कर्नेल आइसोमैप के लिए मुख्य विचार यह है कि इस K को एक स्थिर-शिफ्टिंग विधि का उपयोग करके एक मर्सर कर्नेल मैट्रिक्स (जो कि सकारात्मक अर्ध-निश्चित है) के रूप में बनाया जाए, जिससे कि इसे कर्नेल पीसीए से संबंधित किया जा सके, जिससे कि सामान्यीकरण गुण स्वाभाविक रूप से उभर आए।[6]
यह भी देखें
- कर्नेल पीसीए
- स्पेक्ट्रल क्लस्टरिंग
- नॉनलाइनियर डायमेंशनलिटी रिडक्शन
संदर्भ
- ↑ Tenenbaum, Joshua B.; Silva, Vin de; Langford, John C. (22 December 2000). "नॉनलाइनियर डायमेंशनलिटी रिडक्शन के लिए एक ग्लोबल जियोमेट्रिक फ्रेमवर्क". Science. 290 (5500): 2319–2323. doi:10.1126/science.290.5500.2319.
- ↑ 2.0 2.1 "गैर-रैखिक आयामी कमी में वैश्विक बनाम स्थानीय तरीके" (PDF). Archived from the original (PDF) on 2023-03-30. Retrieved 2014-09-09.
- ↑ Budninskiy, Max; Yin, Gloria; Feng, Leman; Tong, Yiying; Desbrun, Mathieu (2019). "Parallel Transport Unfolding: A Connection-Based Manifold Learning Approach". SIAM Journal on Applied Algebra and Geometry (in English). 3 (2): 266–291. arXiv:1806.09039. doi:10.1137/18M1196133. ISSN 2470-6566.
- ↑ M. Balasubramanian, E. L. Schwartz, The Isomap Algorithm and Topological Stability. Science 4 January 2002: Vol. 295 no. 5552 p. 7
- ↑ A. Saxena, A. Gupta and A. Mukerjee. Non-linear dimensionality reduction by locally linear Isomaps, . Lecture Notes in Computer Science, 3316:1038–1043, 2004.
- ↑ H. Choi, S. Choi, Robust Kernel Isomap, Pattern Recognition, Vol. 40, No. 3, pp. 853-862, 2007
