आइसोमैप: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
== परिचय == | == परिचय == | ||
आइसोमैप सममितीय मानचित्रण विधियों का एक प्रतिनिधि है, और एक भारित ग्राफ़़ द्वारा लगाई गई भूगर्भीय दूरियों को सम्मलित करके मीट्रिक [[बहुआयामी स्केलिंग]] (एमडीएस) का विस्तार करता है। विस्तार से, मीट्रिक एमडीएस का विशिष्ट स्केलिंग डेटा बिंदुओं के बीच युग्मानूसार दूरी के आधार पर निम्न-आयामी एम्बेडिंग करता है, जिसे सामान्यतः सीधी रेखा [[यूक्लिडियन दूरी]] का उपयोग करके मापा जा सकता है। आइसोमैप विशिष्ट स्केलिंग में एम्बेडिंग एक निकट ग्राफ़ द्वारा प्रेरित [[जियोडेसिक दूरी|भूगर्भीय दूरी]] के उपयोग से अलग है। परिणामी एम्बेडिंग में मैनिफोल्ड संरचना को सम्मलित करने के लिए ऐसा किया जाता है। आइसोमैप सबसे छोटी पथ दूरी को दो नोड्स के बीच सबसे छोटे पथ के किनारे के वजन (किनारे की "लागत") के योग के रूप में परिभाषित करता है (उदाहरण के लिए दिज्क्स्ट्रा के कलन विधि का उपयोग करके गणना की गई)। भूगर्भीय दूरी [[ दूरी मैट्रिक्स |वर्ग | आइसोमैप सममितीय मानचित्रण विधियों का एक प्रतिनिधि है, और एक भारित ग्राफ़़ द्वारा लगाई गई भूगर्भीय दूरियों को सम्मलित करके मीट्रिक [[बहुआयामी स्केलिंग]] (एमडीएस) का विस्तार करता है। विस्तार से, मीट्रिक एमडीएस का विशिष्ट स्केलिंग डेटा बिंदुओं के बीच युग्मानूसार दूरी के आधार पर निम्न-आयामी एम्बेडिंग करता है, जिसे सामान्यतः सीधी रेखा [[यूक्लिडियन दूरी]] का उपयोग करके मापा जा सकता है। आइसोमैप विशिष्ट स्केलिंग में एम्बेडिंग एक निकट ग्राफ़ द्वारा प्रेरित [[जियोडेसिक दूरी|भूगर्भीय दूरी]] के उपयोग से अलग है। परिणामी एम्बेडिंग में मैनिफोल्ड संरचना को सम्मलित करने के लिए ऐसा किया जाता है। आइसोमैप सबसे छोटी पथ दूरी को दो नोड्स के बीच सबसे छोटे पथ के किनारे के वजन (किनारे की "लागत") के योग के रूप में परिभाषित करता है (उदाहरण के लिए दिज्क्स्ट्रा के कलन विधि का उपयोग करके गणना की गई)। भूगर्भीय दूरी [[ दूरी मैट्रिक्स |वर्ग आव्यूह]] के शीर्ष ''n'' [[आइजन्वेक्टर|अभिलाक्षणिक सदिश]] ,नए ''n''-आयामी यूक्लिडियन स्थान में निर्देशांक का प्रतिनिधित्व करते हैं। | ||
== एल्गोरिथम == | == एल्गोरिथम == | ||
| Line 19: | Line 19: | ||
== आइसोमैप के एक्सटेंशन == | == आइसोमैप के एक्सटेंशन == | ||
* लैंडमार्क आइसोमैप (L-आईएसओएमएपी): लैंडमार्क-आइसोमैप इसोमैप का एक रूप है जो इसोमैप से तीव्र है। चूंकि, कई गुना की परिशुद्धता सीमांत कारक से समझौता की जाती है। इस कलन विधि में, कुल N डेटा बिंदुओं में से n << N लैंडमार्क बिंदुओं का उपयोग किया जाता है और लैंडमार्क बिंदुओं के लिए प्रत्येक डेटा बिंदु के बीच भूगर्भीय दूरियों के nxN | * लैंडमार्क आइसोमैप (L-आईएसओएमएपी): लैंडमार्क-आइसोमैप इसोमैप का एक रूप है जो इसोमैप से तीव्र है। चूंकि, कई गुना की परिशुद्धता सीमांत कारक से समझौता की जाती है। इस कलन विधि में, कुल N डेटा बिंदुओं में से n << N लैंडमार्क बिंदुओं का उपयोग किया जाता है और लैंडमार्क बिंदुओं के लिए प्रत्येक डेटा बिंदु के बीच भूगर्भीय दूरियों के nxN आव्यूह की गणना की जाती है। लैंडमार्क-एमडीएस (एलएमडीएस) तब सभी डेटा बिंदुओं के यूक्लिडियन एम्बेडिंग को जाँच के लिए आव्यूह पर लागू किया जाता है।<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> | ||
* Cआइसोमैप: C-आइसोमैप में उच्च घनत्व वाले क्षेत्रों को आवर्धित करना और कई गुना डेटा बिंदुओं के कम घनत्व वाले क्षेत्रों को सिकोड़ना सम्मलित है। बहु आयामी स्केलिंग (एमडीएस) में अधिकतम किनारे को संशोधित किया जाता है, बाकी सब कुछ अप्रभावित रहता है।<ref name="mit" /> | * Cआइसोमैप: C-आइसोमैप में उच्च घनत्व वाले क्षेत्रों को आवर्धित करना और कई गुना डेटा बिंदुओं के कम घनत्व वाले क्षेत्रों को सिकोड़ना सम्मलित है। बहु आयामी स्केलिंग (एमडीएस) में अधिकतम किनारे को संशोधित किया जाता है, बाकी सब कुछ अप्रभावित रहता है।<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> | *समानांतर परिवहन खुलासा: इसके अतिरिक्त [[समानांतर परिवहन]] आधारित कई गुना के साथ दिज्क्स्ट्रा पथ-आधारित भूगर्भीय दूरी अनुमानों को प्रतिस्थापित करती है, जिससे नमूनाकरण में अनियमितता और शून्यता की मजबूती में सुधार होता है।<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> यहां तक कि एक शॉर्ट-सर्किट त्रुटि भी भूगर्भीय दूरी | 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> | ||
जहां <math>D^2 = D^2_{ij}:=(D_{ij})^2</math> भूगर्भीय दूरी | जहां <math>D^2 = D^2_{ij}:=(D_{ij})^2</math> भूगर्भीय दूरी आव्यूह ''D'' = [''D<sub>ij</sub>''], का तत्ववार वर्ग है, ''H'' केंद्रित आव्यूह है, द्वारा दिया गया | ||
: <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 को एक निरंतर स्थानांतरण विधि का उपयोग करके एक मर्सर (की प्रमेय) कर्नेल आव्यूह (जो कि सकारात्मक अर्ध-निश्चित है) के रूप में बनाया जाए, जिससे कि इसे कर्नेल पीसीए से संबंधित किया जा सके, जिससे कि इसके सामान्यीकरण गुण स्वाभाविक रूप से उभर आए।<ref>H. Choi, S. Choi, Robust Kernel Isomap, Pattern Recognition, Vol. 40, No. 3, pp. 853-862, 2007</ref> | ||
== यह भी देखें == | == यह भी देखें == | ||
* कर्नेल पीसीए | * कर्नेल पीसीए | ||
Revision as of 21:27, 1 June 2023
आइसोमैप एक अरैखिक आयामी कमी विधि है। यह कई व्यापक रूप से उपयोग किए जाने वाली निम्न-आयामी एम्बेडिंग विधियों में से एक है। [1] आइसोमैप का उपयोग अर्ध-सममितीय, उच्च-आयामी डेटा बिंदुओं के एक समुच्चय के निम्न-आयामी एम्बेडिंग की गणना के लिए किया जाता है। कलन विधि कई गुना पर प्रत्येक डेटा बिंदु के निकतम बिंदुओ के लग-भग अनुमान के आधार पर डेटा कई गुना की आंतरिक ज्यामिति का आकलन लगाने के लिए एक सरल विधि प्रदान करता है। आइसोमैप अत्यधिक कार्य-कुशल है और सामान्यतः डेटा स्रोतों और आयामों की एक विस्तृत श्रृंखला के लिए प्रयुक्त होता है।
परिचय
आइसोमैप सममितीय मानचित्रण विधियों का एक प्रतिनिधि है, और एक भारित ग्राफ़़ द्वारा लगाई गई भूगर्भीय दूरियों को सम्मलित करके मीट्रिक बहुआयामी स्केलिंग (एमडीएस) का विस्तार करता है। विस्तार से, मीट्रिक एमडीएस का विशिष्ट स्केलिंग डेटा बिंदुओं के बीच युग्मानूसार दूरी के आधार पर निम्न-आयामी एम्बेडिंग करता है, जिसे सामान्यतः सीधी रेखा यूक्लिडियन दूरी का उपयोग करके मापा जा सकता है। आइसोमैप विशिष्ट स्केलिंग में एम्बेडिंग एक निकट ग्राफ़ द्वारा प्रेरित भूगर्भीय दूरी के उपयोग से अलग है। परिणामी एम्बेडिंग में मैनिफोल्ड संरचना को सम्मलित करने के लिए ऐसा किया जाता है। आइसोमैप सबसे छोटी पथ दूरी को दो नोड्स के बीच सबसे छोटे पथ के किनारे के वजन (किनारे की "लागत") के योग के रूप में परिभाषित करता है (उदाहरण के लिए दिज्क्स्ट्रा के कलन विधि का उपयोग करके गणना की गई)। भूगर्भीय दूरी वर्ग आव्यूह के शीर्ष n अभिलाक्षणिक सदिश ,नए n-आयामी यूक्लिडियन स्थान में निर्देशांक का प्रतिनिधित्व करते हैं।
एल्गोरिथम
आइसोमैप कलन विधि का एक बहुत ही उच्च स्तरीय विवरण नीचे दिया गया है।
- प्रत्येक बिंदु के निकटतम का निर्धारण करें।
- सभी बिंदु एक निश्चित त्रिज्या में।
- K निकटतम पड़ोसी।
- अगल-बगल का ग्राफ़ बनाएँ।
- यदि यह K निकटतम समीप है तो प्रत्येक बिंदु दूसरे से जुड़ा हुआ है
- किनारे की लंबाई यूक्लिडियन दूरी के बराबर है।
- दो नोड्स के बीच सबसे छोटे पथ की गणना करें।
- दिज्क्स्ट्रा की कलन विधि
- फ्लोयड-वॉर्शल कलन विधि
- निम्न-आयामी एम्बेडिंग की गणना करें।
- बहुआयामी स्केलिंग
आइसोमैप के एक्सटेंशन
- लैंडमार्क आइसोमैप (L-आईएसओएमएपी): लैंडमार्क-आइसोमैप इसोमैप का एक रूप है जो इसोमैप से तीव्र है। चूंकि, कई गुना की परिशुद्धता सीमांत कारक से समझौता की जाती है। इस कलन विधि में, कुल N डेटा बिंदुओं में से n << N लैंडमार्क बिंदुओं का उपयोग किया जाता है और लैंडमार्क बिंदुओं के लिए प्रत्येक डेटा बिंदु के बीच भूगर्भीय दूरियों के nxN आव्यूह की गणना की जाती है। लैंडमार्क-एमडीएस (एलएमडीएस) तब सभी डेटा बिंदुओं के यूक्लिडियन एम्बेडिंग को जाँच के लिए आव्यूह पर लागू किया जाता है।[2]
- Cआइसोमैप: C-आइसोमैप में उच्च घनत्व वाले क्षेत्रों को आवर्धित करना और कई गुना डेटा बिंदुओं के कम घनत्व वाले क्षेत्रों को सिकोड़ना सम्मलित है। बहु आयामी स्केलिंग (एमडीएस) में अधिकतम किनारे को संशोधित किया जाता है, बाकी सब कुछ अप्रभावित रहता है।[2]
- समानांतर परिवहन खुलासा: इसके अतिरिक्त समानांतर परिवहन आधारित कई गुना के साथ दिज्क्स्ट्रा पथ-आधारित भूगर्भीय दूरी अनुमानों को प्रतिस्थापित करती है, जिससे नमूनाकरण में अनियमितता और शून्यता की मजबूती में सुधार होता है।[3]
संभावित मुद्दे
अगल-बगल के ग्राफ़ में प्रत्येक डेटा बिंदु के संपर्क को उच्च-आयामी स्थान में उसके निकटतम k यूक्लिडियन समीप बिंदुओं के रूप में परिभाषित किया गया है। यह कदम "शॉर्ट-सर्किट त्रुटियों" के लिए असुरक्षित है यदि k कई गुना संरचना के संबंध में बहुत बड़ा है या यदि डेटा में रव (अथवा नॉयज) कई गुना से बिंदुओं को थोड़ा दूर ले जाता है।[4] यहां तक कि एक शॉर्ट-सर्किट त्रुटि भी भूगर्भीय दूरी आव्यूह में कई प्रविष्टियों को बदल सकती है, जो बदले में एक बहुत भिन्न (और गलत) निम्न-आयामी एम्बेडिंग का कारण बन सकती है। इसके विपरीत, यदि k बहुत छोटा है, तो अगल-बगल का ग्राफ़ सटीक रूप से भूगर्भीय पथों का अनुमान लगाने के लिए बहुत विरल हो सकता है। लेकिन इस कलन विधि में सुधार किए गए हैं जिससे कि यह विरल और रव (अथवा नॉयज) वाले डेटा समुच्चय के लिए श्रेष्ठ कार्य कर सके।[5]
अन्य विधियों के साथ संबंध
ग्राफ़ सिद्धांत स्केलिंग और प्रमुख घटक विश्लेषण के बीच संबंध के पश्चात, मीट्रिक बहुआयामी स्केलिंग की कर्नेल पीसीए के रूप में व्याख्या कि जा सकती है। इसी तरह, आइसोमैप में भूगर्भीय दूरी आव्यूह को कर्नेल आव्यूह के रूप में देखा जा सकता है। आइसोमैप में दोगुना केंद्रित भूगर्भीय दूरी आव्यूह K का रूप है
जहां भूगर्भीय दूरी आव्यूह D = [Dij], का तत्ववार वर्ग है, H केंद्रित आव्यूह है, द्वारा दिया गया
चूंकि, कर्नेल आव्यूह 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
