प्रसार मानचित्र

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

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

प्रसार मानचित्रों की परिभाषा

अगले और,प्रसार मानचित्रों को चार चरणों में परिभाषित किया जा सकता है।

कनेक्टिविटी

डिफ्यूजन मैप्स गर्मी प्रसार और यादृच्छिक चाल मार्कोव श्रृंखला के बीच संबंध का फायदा उठाते हैं। मूल अवलोकन यह है कि यदि हम डेटा पर यादृच्छिक रूप से चलते हैं, तो पास के डेटा-पॉइंट पर चलने की संभावना दूसरे डेटा-बिंदु पर चलने की तुलना में अधिक होती है। होने देना $(X,{\mathcal {A}},\mu )$ एक माप स्थान हो, जहाँ $X$ डेटा सेट है और $\mu$ बिंदुओं के वितरण का प्रतिनिधित्व करता है $X$.

इसके आधार पर कनेक्टिविटी $k$ दो डेटा बिंदुओं के बीच, $x$ और $y$, से चलने की संभावना के रूप में परिभाषित किया जा सकता है $x$ को $y$ रैंडम वॉक के एक चरण में। आम तौर पर, यह संभावना दो बिंदुओं के कर्नेल फ़ंक्शन के संदर्भ में निर्दिष्ट होती है: $k:X\times X\rightarrow \mathbb {R}$. उदाहरण के लिए, लोकप्रिय गॉसियन कर्नेल:

$k(x,y)=\exp \left(-{\frac {||x-y||^{2}}{\epsilon }}\right)$

अधिक सामान्यतः, इंटीग्रल कर्नेल फ़ंक्शन में निम्नलिखित गुण होते हैं

$k(x,y)=k(y,x)$ ($k$ सममित है)

$k(x,y)\geq 0\,\,\forall x,y$

($k$ सकारात्मकता संरक्षित है)।

कर्नेल डेटा-सेट की स्थानीय ज्यामिति की पूर्व परिभाषा का गठन करता है। चूंकि एक दिया गया कर्नेल डेटा सेट की एक विशिष्ट विशेषता को कैप्चर करेगा, इसकी पसंद को उस एप्लिकेशन द्वारा निर्देशित किया जाना चाहिए जो किसी के दिमाग में हो। प्रमुख घटक विश्लेषण जैसे तरीकों के साथ यह एक बड़ा अंतर है, जहां सभी डेटा बिंदुओं के बीच सहसंबंधों को एक ही बार में ध्यान में रखा जाता है।

दिया गया $(X,k)$, फिर हम एक प्रतिवर्ती असतत-समय मार्कोव श्रृंखला का निर्माण कर सकते हैं $X$ (एक प्रक्रिया जिसे सामान्यीकृत ग्राफ लाप्लासियन निर्माण के रूप में जाना जाता है):

$d(x)=\int _{X}k(x,y)d\mu (y)$

और परिभाषित करें:

$p(x,y)={\frac {k(x,y)}{d(x)}}$

यद्यपि नया सामान्यीकृत कर्नेल सममित संपत्ति का वारिस नहीं करता है, लेकिन यह सकारात्मकता-संरक्षण संपत्ति को प्राप्त करता है और एक संरक्षण संपत्ति प्राप्त करता है:

$\int _{X}p(x,y)d\mu (y)=1$

प्रसार प्रक्रिया

से $p(x,y)$ हम एक मार्कोव श्रृंखला के संक्रमण मैट्रिक्स का निर्माण कर सकते हैं ($M$) पर $X$. दूसरे शब्दों में, $p(x,y)$ से एक-चरण संक्रमण संभावना का प्रतिनिधित्व करता है $x$ को $y$, और $M^{t}$ टी-चरण संक्रमण मैट्रिक्स देता है।

हम प्रसार मैट्रिक्स को परिभाषित करते हैं $L$ (यह ग्राफ लाप्लासियन मैट्रिक्स का एक संस्करण भी है)

$L_{i,j}=k(x_{i},x_{j})\,$

फिर हम नए कर्नेल को परिभाषित करते हैं

$L_{i,j}^{(\alpha )}=k^{(\alpha )}(x_{i},x_{j})={\frac {L_{i,j}}{(d(x_{i})d(x_{j}))^{\alpha }}}\,$

या समकक्ष,

$L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }\,$

जहां डी एक विकर्ण मैट्रिक्स है और $D_{i,i}=\sum _{j}L_{i,j}.$ हम इस नए कर्नेल पर लाप्लासियन सामान्यीकरण ग्राफ लागू करते हैं:

$M=({D}^{(\alpha )})^{-1}L^{(\alpha )},\,$

कहाँ $D^{(\alpha )}$ एक विकर्ण मैट्रिक्स है और ${D}_{i,i}^{(\alpha )}=\sum _{j}L_{i,j}^{(\alpha )}.$

$p(x_{j},t|x_{i})=M_{i,j}^{t}\,$

प्रसार ढांचे के मुख्य विचारों में से एक यह है कि श्रृंखला को समय के साथ आगे बढ़ाना (बड़ी और बड़ी शक्तियों को लेना)। $M$) की ज्यामितीय संरचना को प्रकट करता है $X$ बड़े और बड़े पैमाने पर (प्रसार प्रक्रिया)। विशेष रूप से, डेटा सेट में एक क्लस्टर की धारणा को एक ऐसे क्षेत्र के रूप में निर्धारित किया जाता है जिसमें इस क्षेत्र से बचने की संभावना कम होती है (एक निश्चित समय टी के भीतर)। इसलिए, टी न केवल एक समय पैरामीटर के रूप में कार्य करता है, बल्कि इसमें स्केल पैरामीटर की दोहरी भूमिका भी होती है।

मैट्रिक्स का आइजेनडीकम्पोज़िशन $M^{t}$ पैदावार

$M_{i,j}^{t}=\sum _{l}\lambda _{l}^{t}\psi _{l}(x_{i})\phi _{l}(x_{j})\,$

कहाँ $\{\lambda _{l}\}$ के eigenvalues ​​​​का क्रम है $M$ और $\{\psi _{l}\}$ और $\{\phi _{l}\}$ बायोऑर्थोगोनल दाएं और बाएं ईजेनवेक्टर क्रमशः हैं। ईजेनवैल्यू के स्पेक्ट्रम क्षय के कारण, इस योग में दी गई सापेक्ष सटीकता प्राप्त करने के लिए केवल कुछ शर्तें आवश्यक हैं।

पैरामीटर α और प्रसार ऑपरेटर

शामिल सामान्यीकरण कदम पेश करने का कारण $\alpha$ प्रसार के अनंत संक्रमण पर डेटा बिंदु घनत्व के प्रभाव को ट्यून करना है। कुछ अनुप्रयोगों में, डेटा का नमूना आम तौर पर कई गुना की ज्यामिति से संबंधित नहीं होता है जिसे हम वर्णन करने में रुचि रखते हैं। इस मामले में, हम सेट कर सकते हैं $\alpha =1$ और प्रसार ऑपरेटर लाप्लास-बेल्ट्रामी ऑपरेटर का अनुमान लगाता है। इसके बाद हम अंकों के वितरण की परवाह किए बिना डेटा सेट की रीमैनियन ज्यामिति को पुनर्प्राप्त करते हैं। स्टोचैस्टिक अंतर समीकरणों की एक प्रणाली के बिंदु वितरण के दीर्घकालिक व्यवहार का वर्णन करने के लिए, हम इसका उपयोग कर सकते हैं $\alpha =0.5$ और परिणामी मार्कोव श्रृंखला फोकर-प्लैंक समीकरण | फोकर-प्लैंक प्रसार का अनुमान लगाती है। साथ $\alpha =0$, यह शास्त्रीय ग्राफ लाप्लासियन सामान्यीकरण को कम करता है।

प्रसार दूरी

समय पर प्रसार दूरी $t$ दो बिंदुओं के बीच अवलोकन स्थान में दो बिंदुओं की समानता के रूप में उनके बीच कनेक्टिविटी के रूप में मापा जा सकता है। द्वारा दिया गया है

$D_{t}(x_{i},x_{j})^{2}=\sum _{y}{\frac {(p(y,t|x_{i})-p(y,t|x_{j}))^{2}}{\phi _{0}(y)}}$

कहाँ $\phi _{0}(y)$ के पहले बाएँ eigenvector द्वारा दिया गया मार्कोव श्रृंखला का स्थिर वितरण है $M$. स्पष्ट रूप से:

$\phi _{0}(y)={\frac {d(y)}{\sum _{z\in X}d(z)}}$

सहज रूप से, $D_{t}(x_{i},x_{j})$ छोटा होता है यदि बड़ी संख्या में छोटे रास्ते जुड़ते हैं $x_{i}$ और $x_{j}$. हमारी पिछली चर्चा के आधार पर प्रसार दूरी से जुड़ी कई दिलचस्प विशेषताएं हैं $t$ स्केल पैरामीटर के रूप में भी कार्य करता है:

1. अंक दिए गए पैमाने पर करीब हैं (जैसा निर्दिष्ट किया गया है $D_{t}(x_{i},x_{j})$) यदि वे ग्राफ़ में अत्यधिक जुड़े हुए हैं, इसलिए क्लस्टर की अवधारणा पर बल देते हैं।
2. यह दूरी शोर के लिए मजबूत है, क्योंकि दो बिंदुओं के बीच की दूरी लंबाई के सभी संभावित रास्तों पर निर्भर करती है $t$ बिंदुओं के बीच।
3. मशीन सीखने के दृष्टिकोण से, दूरी लिंक करने के सभी साक्ष्यों को ध्यान में रखती है $x_{i}$ को $x_{j}$, हमें यह निष्कर्ष निकालने की अनुमति देता है कि यह दूरी बहुमत के आधार पर अनुमान एल्गोरिदम के डिजाइन के लिए उपयुक्त है।

प्रसार प्रक्रिया और निम्न-आयामी एम्बेडिंग

eigenvectors का उपयोग करके प्रसार दूरी की गणना की जा सकती है

$D_{t}(x_{i},x_{j})^{2}=\sum _{l}\lambda _{l}^{2t}(\psi _{l}(x_{i})-\psi _{l}(x_{j}))^{2}\,$

इसलिए eigenvectors को डेटा के लिए निर्देशांक के एक नए सेट के रूप में उपयोग किया जा सकता है। प्रसार मानचित्र को इस प्रकार परिभाषित किया गया है:

$\Psi _{t}(x)=(\lambda _{1}^{t}\psi _{1}(x),\lambda _{2}^{t}\psi _{2}(x),\ldots ,\lambda _{k}^{t}\psi _{k}(x))$

स्पेक्ट्रम क्षय के कारण, यह केवल पहले k ईजेनवेक्टर और आइगेनवैल्यू का उपयोग करने के लिए पर्याप्त है। इस प्रकार हम मूल डेटा से एक के-डायमेंशनल स्पेस में प्रसार मानचित्र प्राप्त करते हैं जो मूल स्थान में सन्निहित है।

में यह सिद्ध होता है

$D_{t}(x_{i},x_{j})^{2}=||\Psi _{t}(x_{i})-\Psi _{t}(x_{j})||^{2}\,$

इसलिए प्रसार निर्देशांक में यूक्लिडियन दूरी प्रसार दूरी का अनुमान लगाती है।

एल्गोरिथम

प्रसार मानचित्र का मूल एल्गोरिथम ढांचा इस प्रकार है:

चरण 1. समानता मैट्रिक्स एल को देखते हुए।

चरण 2. पैरामीटर के अनुसार मैट्रिक्स को सामान्य करें $\alpha$: $L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }$.

चरण 3. सामान्यीकृत मैट्रिक्स तैयार करें $M=({D}^{(\alpha )})^{-1}L^{(\alpha )}$.

चरण 4. के सबसे बड़े eigenvalues ​​​​की गणना करें $M^{t}$ और संबंधित eigenvectors।

चरण 5. एम्बेडिंग प्राप्त करने के लिए प्रसार मानचित्र का उपयोग करें $\Psi _{t}$.

आवेदन

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

इसके अलावा, प्रसार मानचित्र ढांचे को उत्पादक रूप से जटिल नेटवर्क तक बढ़ाया गया है, रेफरी>{{cite journal

 | last1 = De Domenico
 | first1 = Manlio
 | url = https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.118.168301
 | title = प्रसार ज्यामिति सामूहिक घटना में कार्यात्मक समूहों के उद्भव को उजागर करती है| journal = Physical Review Letters
 | volume = 118
 | issue = 16
 | pages  = 168301
 | year = 2017
 | doi = 10.1103/PhysRevLett.118.168301
| pmid = 28474920
| arxiv = 1704.07068
| bibcode = 2017PhRvL.118p8301D
| s2cid = 2638868
}</ref> नेटवर्क के एक कार्यात्मक संगठन का खुलासा करता है जो विशुद्ध रूप से सांस्थितिकीय या संरचनात्मक एक से भिन्न होता है।

यह भी देखें

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