आइसोमैप

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

परिचय

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

एल्गोरिथम

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

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

आइसोमैप के एक्सटेंशन

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

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

अगल-बगल के ग्राफ में प्रत्येक डेटा बिंदु के संपर्क को उच्च-आयामी स्थान में उसके निकटतम 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 को एक स्थिर-शिफ्टिंग विधि का उपयोग करके एक मर्सर कर्नेल मैट्रिक्स (जो कि सकारात्मक अर्ध-निश्चित है) के रूप में बनाया जाए, जिससे कि इसे कर्नेल पीसीए से संबंधित किया जा सके, जिससे कि सामान्यीकरण गुण स्वाभाविक रूप से उभर आए।

यह भी देखें

• कर्नेल पीसीए
• स्पेक्ट्रल क्लस्टरिंग
• अरैखिक आयामीता में कमी

बाहरी संबंध

• स्टैनफोर्ड विश्वविद्यालय में आइसोमैप वेबपेज
• टेनेनबाम एट अल द्वारा प्रारंभिक लेख
• टेनेनबाम एट अल द्वारा एमआईटी में गैर-रैखिक आयामी कमी में वैश्विक बनाम स्थानीय तरीके। वेबैक मशीन पर 2020-09-23 को संग्रहित किया गया Archived 2020-09-23 at the Wayback Machine