दूरी मैट्रिक्स से अंक के निर्देशांक ढूँढना

मेरे पास अंक का एक सेट है (अज्ञात निर्देशांक के साथ) और दूरी मैट्रिक्स। मुझे इन बिंदुओं के समन्वय को खोजने और उन्हें अपने एल्गोरिदम के समाधान दिखाने के लिए खोजने की आवश्यकता है।दूरी मैट्रिक्स से अंक के निर्देशांक ढूँढना

मैं समन्वय (0,0) में इन बिंदुओं में से एक को सिंपाने और दूसरों को ढूंढने के लिए सेट कर सकता हूं। क्या कोई मुझे बता सकता है कि अन्य बिंदुओं के निर्देशांक ढूंढना संभव है, और यदि हां, तो कैसे?

अग्रिम धन्यवाद!

संपादित कहना है कि मैं एक्स-y पर निर्देशांक की जरूरत है केवल

स्रोत

2012-06-09 Trino00

यह है ... बहुत सारे ब्रूट-फोर्सिंग की आवश्यकता होगी ... –

तीन बिंदुओं (एक त्रिकोण) पर विचार करें। दो उन्मुखताएं हैं, और घूर्णन की अनंत संख्या जो समान दूरी मैट्रिक्स प्रदान करती हैं। –

एक कदम आगे, क्या हम एक-आयामी अंतरिक्ष, या दो, या तीन, या चार बात कर रहे हैं .... प्रत्येक मामले में जवाब बदल जाएगा। (0,0) तक, क्या हमें इसके द्वि-आयामी को स्वीकार करना चाहिए? – Rasman

चरण 1, मनमाने ढंग से के रूप में (0,0) एक बिंदु पी 1 आवंटित भूल।

चरण 2, मनमाने ढंग से सकारात्मक एक्स अक्ष के साथ एक बिंदु पी 2 असाइन करें। (0, Dp1p2)

चरण 3, ऐसी है कि

Dp1p2 ~= Dp1p3+Dp2p3 
Dp1p3 ~= Dp1p2+Dp2p3 
Dp2p3 ~= Dp1p3+Dp1p2

एक बिंदु पी 3 खोजने के लिए और "सकारात्मक" y डोमेन कि बिंदु निर्धारित (अगर यह इन मानदंडों में से किसी को पूरा करती है, बिंदु रखा जाना चाहिए पी 1 पी 2 धुरी पर)।
दूरी का निर्धारण करने के कोज्या कानून का उपयोग करें:

cos (A) = (Dp1p2^2 + Dp1p3^2 - Dp2p3^2)/(2*Dp1p2* Dp1p3) 
P3 = (Dp1p3 * cos (A), Dp1p3 * sin(A))

अब आप सफलतापूर्वक एक orthonormal अंतरिक्ष बनाया गया है और है कि अंतरिक्ष में तीन अंक दिए हैं।

चरण 4: सभी अन्य बिंदुओं को निर्धारित करने के लिए, चरण 3 को दोहराएं, आपको एक टेंटेटिव वाई समन्वय देने के लिए। (एक्सएन, वाईएन)।
अपने मैट्रिक्स में दूरी {(एक्सएन, वाईएन), (एक्स 3, वाई 3)} को एमपी 3 में तुलना करें। यदि यह समान है, तो आपने बिंदु एन के समन्वय को सफलतापूर्वक पहचाना है। अन्यथा, बिंदु एन पर है (एक्सएन, -Yn)।

नोट चरण 4 के लिए एक विकल्प नहीं है, लेकिन यह अपने मैट्रिक्स में एक शनिवार की दोपहर

स्रोत

2012-06-09 18:11:02 Rasman

@ ब्रूनोब्रुक कोसाइन कानून पी 1 पी 2 और पी 1 पी 3 के बीच कोण (पहला समीकरण) देता है। अगला भाग पी 3 पी 2 अक्ष पर पी 3 के प्रक्षेपण को प्राप्त करना है। दूरी P1P3 को जानना, और इसे त्रिकोण के hypotenuse के रूप में सेट करना, एक्स और वाई मान क्रमशः hypotenuse, cos और साइन समय हैं। – Rasman

आपने पी 2 के साथ क्या किया है ठीक है, लेकिन पी 3 के मामले में मैं अपने सेट का एक बिंदु नहीं चुन सकता, जो पी 1 और पी 2 की एक ही पंक्ति में नहीं है, और यह सुनिश्चित करने के लिए कहें कि यह वाई-अक्ष पर है। – Trino00

ठीक है, मुझे लगता है कि मुझे यह मिला। सबसे पहले हम दिखाते हैं कि पी 3 सही त्रिभुज प्राप्त करने के लिए वाई-अक्ष में है, और ऐसे मामले में हम निर्देशांक के लिए समीकरण बना सकते हैं। लेकिन हम पी 3 और पी 2 के बीच वास्तविक दूरी को जानते हैं, इसलिए हम पी 1 पी 2 और पी 1 पी 3 के बीच वास्तविक कोण प्राप्त करने में सक्षम हैं, और समन्वय के लिए समीकरणों में इसका उपयोग करके हम Xp3 और Yp3 के लिए वास्तविक मूल्य प्राप्त कर सकते हैं। क्या मैं सही समझ गया? – Trino00

तो अंक के लिए p, q के लिए बहुत ज्यादा गणित है, और r आप pq है, qr, और आरपी, आपके पास एक त्रिभुज।

जहां भी आपके मैट्रिक्स में त्रिकोण है, आप उस त्रिभुज के लिए दो समाधानों में से एक की गणना कर सकते हैं (विमान पर त्रिकोण के यूक्लिडियन परिवर्तन से स्वतंत्र)। यही है, प्रत्येक त्रिकोण के लिए आप गणना करते हैं, यह दर्पण छवि भी एक त्रिकोण है जो पी, क्यू, और आर पर दूरी की बाधाओं को पूरा करती है। तथ्य यह है कि त्रिभुज के लिए भी दो समाधान हैं chirality समस्या की ओर जाता है: आपको प्रत्येक त्रिभुज की chirality (अभिविन्यास) चुनना है, और सभी विकल्पों को समस्या का एक व्यवहार्य समाधान नहीं हो सकता है।

फिर भी, मेरे पास कुछ सुझाव हैं। यदि संख्या प्रविष्टियां छोटी हैं, तो simulated annealing का उपयोग करने पर विचार करें। आप एनीलिंग चरण में chirality शामिल कर सकते हैं। यह बड़ी प्रणालियों के लिए धीमा हो जाएगा, और यह एक सही समाधान के लिए अभिसरण नहीं हो सकता है, लेकिन कुछ समस्याओं के लिए यह सबसे अच्छा है और आप करते हैं।

दूसरा सुझाव आपको एक सही समाधान नहीं देगा, लेकिन यह त्रुटि वितरित करेगा: method of least squares। आपके मामले में उद्देश्य कार्य आपके मैट्रिक्स में दूरी और आपके बिंदुओं के बीच वास्तविक दूरी के बीच त्रुटि होगी।

स्रोत

2012-06-09 18:20:02

उत्तर के लिए धन्यवाद। मुझे नहीं पता कि यह सबसे अच्छा तरीका है क्योंकि कुछ सीनेरियो में मेरे पास बहुत अधिक अंक हैं और एक मेटाएरिस्टिक हमेशा इष्टतम समाधान नहीं देता है, या इस मामले में, एक व्यवहार्य समाधान। तो मैं इसके साथ बहुत समय बिता सकता हूं और अभी भी एक व्यवहार्य उत्तर नहीं मिलता है। – Trino00

@DeepYellow: मुझे आपका जवाब कुछ हद तक पसंद है क्योंकि यह कल एक अलग उपयोगकर्ता द्वारा पोस्ट किए गए एक अलग, कठिन प्रश्न का उत्तर देने में मदद कर सकता है। मैंने उस दूसरे प्रश्न का उत्तर देने की कोशिश की और असफल रहा। यदि चुनौती आपको रूचि देती है, तो यहां यूआरएल है: http://stackoverflow.com/questions/10957359/minimal-rectangle-containing-all-intersections-of-lines – thb

@thb: उस प्रश्न को इंगित करने के लिए धन्यवाद। मैंने पोस्ट किया जो मुझे लगता है कि एक सही समाधान है, मुझे बताएं कि आप क्या सोचते हैं। –

कोणों पर आधारित उत्तरों को लागू करने के लिए बोझिल हैं और उच्च आयामों में डेटा को आसानी से सामान्यीकृत नहीं किया जा सकता है।एक बेहतर दृष्टिकोण है कि मेरे और WimC के जवाब here में उल्लेख किया है:, दूरी मैट्रिक्स D(i, j) दिया परिभाषित

M(i, j) = 0.5*(D(1, j)^2 + D(i, 1)^2 - D(i, j)^2)

जो रैंक के साथ एक सकारात्मक अर्द्ध निश्चित मैट्रिक्स न्यूनतम इयूक्लिडियन आयाम k बराबर होना चाहिए जो अंक कर सकते हैं एम्बेडेड हो। एक n x k मैट्रिक्स X में स्तंभों के रूप में जगह वैक्टर sqrt(q(i))*v(i);: अंक के निर्देशांक तो k eigenvectors M की v(i) गैर शून्य eigenvalues q(i) करने के लिए इसी से प्राप्त किया जा सकता तो X की प्रत्येक पंक्ति एक बिंदु है। दूसरे शब्दों में, sqrt(q(i))*v(i) सभी बिंदुओं के i वें घटक देता है।

eigenvalues और एक मैट्रिक्स के eigenvectors (आदि जैसे, सी/C++ GSL का उपयोग कर, मैटलैब में निर्मित समारोह eig का उपयोग कर, पायथन में Numpy का उपयोग कर,) सबसे प्रोग्रामिंग भाषाओं में आसानी से प्राप्त किया जा सकता है

ध्यान दें कि यह विशेष विधि हमेशा उत्पत्ति पर पहला बिंदु रखती है, लेकिन अंक के किसी भी घूर्णन, प्रतिबिंब, या अनुवाद मूल दूरी मैट्रिक्स को भी संतुष्ट करेगा।

स्रोत

2013-06-18 20:01:41 Legendre17

यह जवाब होना चाहिए। हालांकि इसे स्वयं कोड करने की कोई आवश्यकता नहीं है, मल्टी-डायमेंशनल स्केलिंग फ़ंक्शन पाइथन या आर में पाए जा सकते हैं। –

यह एक गणित समस्या है। समन्वय मैट्रिक्स एक्स प्राप्त करने के लिए केवल इसकी दूरी मैट्रिक्स द्वारा दिया गया है।

हालांकि इसके लिए एक कुशल समाधान है - बहुआयामी स्केलिंग, जो कुछ रैखिक बीजगणित करता है। सीधे शब्दों में कहें, इसके लिए एक युग्मित यूक्लिडियन दूरी मैट्रिक्स डी की आवश्यकता है, और आउटपुट अनुमानित समन्वय वाई (शायद घुमाया गया) है, जो एक्स के निकट है। प्रोग्रामिंग कारण के लिए, केवल Python में SciKit.manifold.MDS का उपयोग करें।

स्रोत

2015-09-15 23:02:39 Hualin

दूरी मैट्रिक्स से अंक के निर्देशांक ढूँढना

उत्तर

संबंधित मुद्दे