आइसोमैप: Difference between revisions
(→परिचय) |
|||
| Line 19: | Line 19: | ||
== आइसोमैप के एक्सटेंशन == | == आइसोमैप के एक्सटेंशन == | ||
* लैंडमार्क आइसोमैप (L-आईएसओएमएपी): लैंडमार्क-आइसोमैप इसोमैप का एक रूप है जो इसोमैप से तीव्र है। चूंकि, | * लैंडमार्क आइसोमैप (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-आइसोमैप में उच्च घनत्व वाले क्षेत्रों को आवर्धित करना और | * 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> | ||
== संभावित मुद्दे == | == संभावित मुद्दे == | ||
अगल-बगल के आलेख में प्रत्येक डेटा बिंदु के संपर्क को उच्च-आयामी स्थान में उसके निकटतम k यूक्लिडियन | अगल-बगल के आलेख में प्रत्येक डेटा बिंदु के संपर्क को उच्च-आयामी स्थान में उसके निकटतम 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> | चूंकि, कर्नेल मैट्रिक्स K सदैव सकारात्मक अर्ध-निश्चित नहीं होता है। कर्नेल आइसोमैप के लिए मुख्य विचार यह है कि इस K को एक निरंतर स्थानांतरण विधि का उपयोग करके एक मर्सर (की प्रमेय) कर्नेल मैट्रिक्स (जो कि सकारात्मक अर्ध-निश्चित है) के रूप में बनाया जाए, जिससे कि इसे कर्नेल पीसीए से संबंधित किया जा सके, जिससे कि इसके सामान्यीकरण गुण स्वाभाविक रूप से उभर आए।<ref>H. Choi, S. Choi, Robust Kernel Isomap, Pattern Recognition, Vol. 40, No. 3, pp. 853-862, 2007</ref> | ||
== यह भी देखें == | == यह भी देखें == | ||
* कर्नेल पीसीए | * कर्नेल पीसीए | ||
Revision as of 11:41, 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
