आइसोमैप: Difference between revisions
| Line 26: | Line 26: | ||
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> | 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> भूगर्भीय दूरी मैट्रिक्स डी = [डीजे<sub>''ij''</sub>], का तत्ववार वर्ग है, एच केंद्रित मैट्रिक्स है, द्वारा दिया गया | |||
: <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 को एक स्थिर-शिफ्टिंग विधि का उपयोग करके एक मर्सर कर्नेल मैट्रिक्स (जो कि सकारात्मक अर्ध-निश्चित है) के रूप में बनाया जाए, ताकि इसे कर्नेल पीसीए से संबंधित किया जा सके, ताकि सामान्यीकरण गुण स्वाभाविक रूप से उभर आए।<ref>H. Choi, S. Choi, Robust Kernel Isomap, Pattern Recognition, Vol. 40, No. 3, pp. 853-862, 2007</ref> | ||
== यह भी देखें == | == यह भी देखें == | ||
* कर्नेल पीसीए | * कर्नेल पीसीए | ||
* [[स्पेक्ट्रल क्लस्टरिंग]] | * [[स्पेक्ट्रल क्लस्टरिंग]] | ||
* नॉनलाइनियर | * नॉनलाइनियर डायमेंशनलिटी रिडक्शन | ||
== संदर्भ == | == संदर्भ == | ||
{{reflist}} | {{reflist}} | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
* [https://web.archive.org/web/20040411051530/http://isomap.stanford.edu/ | * [https://web.archive.org/web/20040411051530/http://isomap.stanford.edu/ स्टैनफोर्ड विश्वविद्यालय में आइसोमैप वेबपेज] | ||
* [http://www-clmc.usc.edu/publications/T/tenenbaum-Science2000.pdf | * [http://www-clmc.usc.edu/publications/T/tenenbaum-Science2000.pdf टेनेनबाम एट अल द्वारा प्रारंभिक लेख] | ||
* [http://web.mit.edu/cocosci/Papers/nips02-localglobal-in-press.pdf | * [http://web.mit.edu/cocosci/Papers/nips02-localglobal-in-press.pdf टेनेनबाम एट अल द्वारा एमआईटी में गैर-रैखिक आयामी कमी में वैश्विक बनाम स्थानीय तरीके। वेबैक मशीन पर 2020-09-23 को संग्रहित किया गया] {{Webarchive|url=https://web.archive.org/web/20200923104510/http://web.mit.edu/cocosci/Papers/nips02-localglobal-in-press.pdf |date=2020-09-23 }} | ||
[[Category: कम्प्यूटेशनल आँकड़े]] | [[Category: कम्प्यूटेशनल आँकड़े]] | ||
Revision as of 19:05, 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
