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

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

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

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

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

अनुयोजकता

प्रसार मानचित्र ऊष्मा प्रसार और यादृच्छिक चाल मार्कोव श्रृंखला के बीच संबंध का लाभ उठाते हैं। मूल अवलोकन यह है कि यदि हम आंकड़ों पर यादृच्छिक रूप से चलते हैं, तो पास के आंकड़ों-पॉइंट पर चलने की संभावना दूसरे आंकड़ों-बिंदु पर चलने की तुलना में अधिक होती है। होने देना $(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> नेटवर्क के एक कार्यात्मक संगठन का खुलासा करता है जो विशुद्ध रूप से सांस्थितिकीय या संरचनात्मक एक से भिन्न होता है।

यह भी देखें

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