आइसोमैप

आइसोमैप एक अरैखिक आयामी कमी विधि है। यह कई व्यापक रूप से उपयोग किए जाने वाली निम्न-आयामी अंत:स्थापन विधियों में से एक है। आइसोमैप का उपयोग उच्च-आयामी डेटा बिंदुओं के एक सेट के अर्ध-सममितीय, निम्न-आयामी अंत:स्थापन की गणना के लिए किया जाता है। एल्गोरिथ्म कई गुना पर प्रत्येक डेटा बिंदु के पड़ोसियों के मोटे अनुमान के आधार पर डेटा मैनिफोल्ड की आंतरिक ज्यामिति का अनुमान लगाने के लिए एक सरल विधि प्रदान करता है। आइसोमैप अत्यधिक कुशल है और आम तौर पर डेटा स्रोतों और आयामों की एक विस्तृत श्रृंखला के लिए लागू होता है।

परिचय

आइसोमैप चित्रसम मानचित्रण विधियों का एक प्रतिनिधि है, और एक भारित ग्राफ़ द्वारा लगाई गई भूगर्भीय दूरियों को शामिल करके मीट्रिक बहुआयामी स्केलिंग (MDS) का विस्तार करता है। विशिष्ट होने के लिए, मीट्रिक एमडीएस का प्रतिष्ठित स्केलिंग डेटा बिंदुओं के बीच जोड़ीदार दूरी के आधार पर निम्न-आयामी एम्बेडिंग करता है, जिसे आम तौर पर सीधी रेखा यूक्लिडियन दूरी का उपयोग करके मापा जाता है। आइसोमैप प्रतिष्ठित स्केलिंग में अंत:स्थापन एक पड़ोस ग्राफ द्वारा प्रेरित जियोडेसिक दूरी के उपयोग से अलग है। परिणामी अंत:स्थापन में कई गुना संरचना को शामिल करने के लिए ऐसा किया जाता है। आइसोमैप जियोडेसिक दूरी को दो नोड्स के बीच सबसे छोटे पथ के किनारे के वजन के योग के रूप में परिभाषित करता है (उदाहरण के लिए दिज्क्स्ट्रा के एल्गोरिथ्म का उपयोग करके गणना की गई)। जियोडेसिक दूरी मैट्रिक्स के शीर्ष एन आइजन्वेक्टर, नए एन-आयामी यूक्लिडियन स्थान में निर्देशांक का प्रतिनिधित्व करते हैं।

एल्गोरिथम

Isomap एल्गोरिथम का एक बहुत ही उच्च स्तरीय विवरण नीचे दिया गया है।

• प्रत्येक बिंदु के पड़ोसियों का निर्धारण करें।
  • सभी बिंदु एक निश्चित दायरे में।
  • के निकटतम पड़ोसी।
• पड़ोस का ग्राफ बनाएं।
  • प्रत्येक बिंदु दूसरे से जुड़ा हुआ है यदि यह 'के' निकटतम पड़ोसी है।
  • किनारे की लंबाई यूक्लिडियन दूरी के बराबर।
• दो नोड्स के बीच सबसे छोटे पथ की गणना करें।
  • दिज्क्स्ट्रा का एल्गोरिथ्म
  • फ्लोयड-वॉर्शल एल्गोरिथम
• निम्न-आयामी एम्बेडिंग की गणना करें।
  • बहुआयामी स्केलिंग

ISOMAP के एक्सटेंशन

• लैंडमार्क आइसोमैप (एल-आईएसओएमएपी): लैंडमार्क-आइसोमैप इसोमैप का एक रूप है जो इसोमैप से तेज है। हालांकि, कई गुना की शुद्धता सीमांत कारक से समझौता की जाती है। इस एल्गोरिथम में, कुल N डेटा बिंदुओं में से n << N लैंडमार्क बिंदुओं का उपयोग किया जाता है और लैंडमार्क बिंदुओं के लिए प्रत्येक डेटा बिंदु के बीच जियोडेसिक दूरी के nxN मैट्रिक्स की गणना की जाती है। लैंडमार्क-एमडीएस (एलएमडीएस) तब सभी डेटा बिंदुओं के यूक्लिडियन एम्बेडिंग को खोजने के लिए मैट्रिक्स पर लागू होता है।
• सी आइसोमैप: सी-आइसोमैप में उच्च घनत्व वाले क्षेत्रों को आवर्धित करना और कई गुना डेटा बिंदुओं के कम घनत्व वाले क्षेत्रों को सिकोड़ना शामिल है। मल्टी-डाइमेंशनल स्केलिंग (एमडीएस) में अधिकतम एज वेट को संशोधित किया जाता है, बाकी सब कुछ अप्रभावित रहता है।*समानांतर ट्रांसपोर्ट अनफोल्डिंग: दिज्क्स्ट्रा पथ-आधारित जियोडेसिक दूरी अनुमानों को इसके बजाय समानांतर परिवहन आधारित सन्निकटनों से प्रतिस्थापित करता है, जिससे नमूनाकरण में अनियमितता और शून्यता की मजबूती में सुधार होता है।

संभावित मुद्दे

पड़ोस के ग्राफ में प्रत्येक डेटा बिंदु की कनेक्टिविटी को उच्च-आयामी अंतरिक्ष में उसके निकटतम k यूक्लिडियन पड़ोसियों के रूप में परिभाषित किया गया है। यह कदम शॉर्ट-सर्किट त्रुटियों के लिए कमजोर है यदि k कई गुना संरचना के संबंध में बहुत बड़ा है या यदि डेटा में शोर कई गुना से बिंदुओं को थोड़ा दूर ले जाता है। यहां तक ​​कि एक शॉर्ट-सर्किट त्रुटि भी जियोडेसिक दूरी मैट्रिक्स में कई प्रविष्टियों को बदल सकती है, जो बदले में एक बहुत भिन्न (और गलत) निम्न-आयामी एम्बेडिंग का कारण बन सकती है। इसके विपरीत, यदि k बहुत छोटा है, तो आस-पड़ोस का ग्राफ सटीक रूप से जियोडेसिक पथों का अनुमान लगाने के लिए बहुत विरल हो सकता है। लेकिन इस एल्गोरिद्म में सुधार किए गए हैं ताकि यह विरल और शोर वाले डेटा सेट के लिए बेहतर काम करे।

अन्य विधियों के साथ संबंध

शास्त्रीय स्केलिंग और प्रमुख घटक विश्लेषण के बीच संबंध के बाद, मीट्रिक बहुआयामी स्केलिंग को कर्नेल पीसीए के रूप में व्याख्या किया जा सकता है। इसी तरह, आइसोमैप में जियोडेसिक डिस्टेंस मैट्रिक्स को कर्नेल विधि मैट्रिक्स के रूप में देखा जा सकता है। आइसोमैप में दोगुना केंद्रित जियोडेसिक दूरी मैट्रिक्स K फॉर्म का है

$K=-{\frac {1}{2}}HD^{2}H\,$

कहाँ $D^{2}=D_{ij}^{2}:=(D_{ij})^{2}$ भूगर्भीय दूरी मैट्रिक्स डी = [डी का तत्ववार वर्ग है_ij], एच केंद्रित मैट्रिक्स है, द्वारा दिया गया

$H=I_{n}-{\frac {1}{N}}e_{N}e_{N}^{T},\quad {\text{where }}e_{N}=[1\ \dots \ 1]^{T}\in \mathbb {R} ^{N}.$

हालाँकि, कर्नेल मैट्रिक्स K हमेशा सकारात्मक अर्ध-निश्चित मैट्रिक्स नहीं होता है। कर्नेल आइसोमैप के लिए मुख्य विचार यह है कि इस K को मर्सर के प्रमेय कर्नेल मैट्रिक्स (जो कि सकारात्मक अर्ध निश्चित है) के रूप में एक स्थिर-शिफ्टिंग विधि का उपयोग करके इसे कर्नेल पीसीए से संबंधित करने के लिए बनाया जाता है ताकि सामान्यीकरण गुण स्वाभाविक रूप से उभर आए .

यह भी देखें

• कर्नेल पीसीए
• स्पेक्ट्रल क्लस्टरिंग
• नॉनलाइनियर डाइमेंशनलिटी रिडक्शन # आइसोमैप

बाहरी संबंध

• Isomap webpage at Stanford university
• Initial article by Tenenbaum et al.
• Global versus local methods in nonlinear dimensionality reduction at MIT by Tenenbaum et al. Archived 2020-09-23 at the Wayback Machine