आइसोमैप: Difference between revisions
No edit summary |
(→परिचय) |
||
| Line 2: | Line 2: | ||
== परिचय == | == परिचय == | ||
आइसोमैप सममितीय मानचित्रण विधियों का एक प्रतिनिधि है, और एक भारित आलेख़ द्वारा लगाई गई जियोडेसिक दूरी को सम्मलित करके मीट्रिक [[बहुआयामी स्केलिंग]] (एमडीएस) का विस्तार करता है। विस्तार से, मीट्रिक एमडीएस का विशिष्ट स्केलिंग डेटा बिंदुओं के बीच युग्मानूसार दूरी के आधार पर निम्न-आयामी एम्बेडिंग करता है, जिसे सामान्यतः सीधी रेखा [[यूक्लिडियन दूरी]] का उपयोग करके मापा जा सकता है। आइसोमैप विशिष्ट स्केलिंग में एम्बेडिंग एक निकट आलेख द्वारा प्रेरित [[जियोडेसिक दूरी]] के उपयोग से अलग है। परिणामी एम्बेडिंग में मैनिफोल्ड संरचना को सम्मलित करने के लिए ऐसा किया जाता है। आइसोमैप जियोडेसिक दूरी को दो नोड्स के बीच सबसे छोटे पथ के किनारे के वजन (किनारे की "लागत") के योग के रूप में परिभाषित करता है (उदाहरण के लिए दिज्क्स्ट्रा के एल्गोरिथ्म का उपयोग करके गणना की गई)। जियोडेसिक [[ दूरी मैट्रिक्स |दूरी मैट्रिक्स]] के शीर्ष ''n'' [[आइजन्वेक्टर]], नए | आइसोमैप सममितीय मानचित्रण विधियों का एक प्रतिनिधि है, और एक भारित आलेख़ द्वारा लगाई गई जियोडेसिक दूरी को सम्मलित करके मीट्रिक [[बहुआयामी स्केलिंग]] (एमडीएस) का विस्तार करता है। विस्तार से, मीट्रिक एमडीएस का विशिष्ट स्केलिंग डेटा बिंदुओं के बीच युग्मानूसार दूरी के आधार पर निम्न-आयामी एम्बेडिंग करता है, जिसे सामान्यतः सीधी रेखा [[यूक्लिडियन दूरी]] का उपयोग करके मापा जा सकता है। आइसोमैप विशिष्ट स्केलिंग में एम्बेडिंग एक निकट आलेख द्वारा प्रेरित [[जियोडेसिक दूरी]] के उपयोग से अलग है। परिणामी एम्बेडिंग में मैनिफोल्ड संरचना को सम्मलित करने के लिए ऐसा किया जाता है। आइसोमैप जियोडेसिक दूरी को दो नोड्स के बीच सबसे छोटे पथ के किनारे के वजन (किनारे की "लागत") के योग के रूप में परिभाषित करता है (उदाहरण के लिए दिज्क्स्ट्रा के एल्गोरिथ्म का उपयोग करके गणना की गई)। जियोडेसिक [[ दूरी मैट्रिक्स |दूरी मैट्रिक्स]] के शीर्ष ''n'' [[आइजन्वेक्टर]], नए ''n''-आयामी यूक्लिडियन स्थान में निर्देशांक का प्रतिनिधित्व करते हैं। | ||
== एल्गोरिथम == | == एल्गोरिथम == | ||
| Line 29: | Line 29: | ||
: <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> | ||
Revision as of 17:18, 30 May 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
