ज्यामितीय माध्यिका

अंकों की एक श्रृंखला के ज्यामितीय माध्यिका (पीले रंग में) का उदाहरण। द्रव्यमान का केंद्र नीले रंग में।

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

ज्यामितीय माध्यिका आंकड़ों में स्थान का एक महत्वपूर्ण अनुमानक है , जहां इसे L₁ अनुमानक के रूप में भी जाना जाता है। यह एक मानक समस्या भी है, जहाँ यह अभिगमन की लागत को कम करने के लिए पता लगाने के लिए मॉडल बनाती है।

समतल में तीन बिंदुओं के लिए समस्या की विशेष स्थिति (अर्थात्, नीचे दी गई परिभाषा में m = 3 और n = 2) को कभी-कभी फ़र्मेट की समस्या के रूप में भी जाना जाता है; यह न्यूनतम स्टाइनर ट्री के निर्माण में उत्पन्न होता है, और मूल रूप से पियरे डी फर्मेट द्वारा एक समस्या के रूप में प्रस्तुत किया गया और इसे इवेंजलिस्ता टोरिकेली द्वारा हल किया गया था। इसके विधि को अब तीन प्रतिदर्शबिंदु द्वारा गठित त्रिभुज के फर्मेट बिंदु के रूप में जाना जाता है। बदले में ज्यामितीय माध्यिका को भारित दूरियों के योग को कम करने की समस्या के लिए सामान्यीकृत किया जा सकता है, जिसे अल्फ्रेड वेबर की 1909 की सुविधा स्थान पुस्तक में समस्या की चर्चा के बाद वेबर समस्या के रूप में जाना जाता है। इसके अतिरिक्त कुछ स्रोत वेबर की समस्या को फ़र्मेट-वेबर समस्या कहते हैं, लेकिन अन्य इस नाम का उपयोग भारित ज्यामितीय माध्यिका समस्या के लिए करते हैं।

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

परिभाषा

औपचारिक रूप से, m बिंदुओं के दिए गए सेट के लिए $x_{1},x_{2},\dots ,x_{m}\,$ प्रत्येक के साथ $x_{i}\in \mathbb {R} ^{n}$, ज्यामितीय माध्यिका के रूप में परिभाषित किया गया है

${\underset {y\in \mathbb {R} ^{n}}{\operatorname {arg\,min} }}\sum _{i=1}^{m}\left\|x_{i}-y\right\|_{2}$

यहाँ, arg min का अर्थ है तर्क का मान $y$ जो योग को कम करता है। इस स्थिति में, यह बात है $y$ जहाँ से सभी यूक्लिडियन दूरियों का योग $x_{i}$न्यूनतम है।

गुण

• 1-आयामी स्थिति के लिए, ज्यामितीय माध्य माध्यिका के साथ मेल खाता है। ऐसा इसलिए है क्योंकि अविभाजित माध्यिका भी बिंदुओं से दूरियों के योग को कम करती है। (अधिक त्रुटिहीन रूप से, यदि अंक पी₁ है, …, पी_n है, उस क्रम में, ज्यामितीय माध्यिका मध्य बिंदु है $p_{(n+1)/2}$ यदि n विषम है, लेकिन विशिष्ट रूप से निर्धारित नहीं है यदि n जोड़ है, जब यह दो मध्य बिंदुओं के बीच रेखा खंड में कोई बिंदु होती है $p_{n/2}$ और $p_{(n/2)+1}$.)
• ज्यामितीय माध्य अद्वितीय होता है जब भी बिंदु संरेख नहीं होती है
• ज्यामितीय मध्य यूक्लिडियन समानता (ज्यामिति) के लिए समतुल्य होता है, जिसमें अनुवाद (ज्यामिति) और रोटेशन सम्मलित होता है। इसका मतलब यह है कि एक ही परिणाम या तो ज्यामितीय माध्यिका को बदलकर, या समान परिवर्तन को प्रतिरूप डेटा में लागू करके और रूपांतरित डेटा के ज्यामितीय माध्य को खोजने से प्राप्त होता है। यह इस तथ्य से अनुसरण करता है कि ज्यामितीय मध्यिका केवल जोड़ीदार दूरी से परिभाषित होता है, और यह ऑर्थोगोनल कार्टेशियन निर्देशांक की प्रणाली पर निर्भर नहीं करता है जिसके द्वारा प्रतिरूप डेटा का प्रतिनिधित्व किया जाता है। इसके विपरीत, एक बहुभिन्नरूपी डेटा सेट के लिए घटक-वार माध्य सामान्य रोटेशन अपरिवर्तनीय नहीं होता है, न ही यह निर्देशांक स्वतंत्र होता है
• ज्यामितीय माध्यिका का विश्लेषण बिंदु 0.5 है। अर्थात्, प्रतिरूप डेटा का आधा हिस्सा मनमाने ढंग से दूषित होता है, और नमूनों का माध्य अभी भी अदूषित डेटा के स्थान के लिए एक मजबूत अनुमानक प्रदान करता है

विशेष स्थितियां

• 3 (गैर संरेख) बिंदुओं के लिए, यदि उन बिंदुओं से बने त्रिभुज का कोई कोण 120° या अधिक होता है, तो ज्यामितीय माध्यिका उस कोण के शीर्ष पर स्थित बिंदु होता है। यदि सभी कोण 120° से कम होता है, तो ज्यामितीय माध्य त्रिभुज के भीतर का वह बिंदु है जो त्रिभुज के शीर्षों के प्रत्येक तीन युग्मों में 120° का कोण अंतरित करता है। इसे तीन शीर्षों से बने त्रिभुज के फर्मेट बिंदु के रूप में भी जाना जाता है। (यदि तीन बिंदु संरेख है तो ज्यामितीय माध्य दो अन्य बिंदुओं के बीच का बिंदु है, जैसा कि एक आयामी माध्यिका के स्थितियों में होता है)
• 4 समतलीय बिंदुओं के लिए, यदि चार बिंदुओं में से एक बिंदु अन्य तीन बिंदुओं से बने त्रिभुज के अंदर है, तो ज्यामितीय माध्यिका वह बिंदु होती है। अन्यथा, चार बिंदु उत्तल चतुर्भुज बनाते है और ज्यामितीय माध्य चतुर्भुज के विकर्णों का क्रॉसिंग बिंदु होता है। चार समतलीय बिंदुओं का ज्यामितीय माध्य चार बिंदुओं के अद्वितीय बिंदु के समान होता है

गणना

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

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

इस प्रकार का एक सामान्य दृष्टिकोण, एंड्रे वीज़फेल्ड के काम के बाद वीज़फेल्ड का एल्गोरिथ्म कहलाता है, पुनरावृत्ति पुन: कम से कम वर्गों का एक रूप होता है। यह एल्गोरिथ्म एक सेट को परिभाषित करता है जो वर्तमान अनुमान से प्रतिरूप बिंदुओं तक की दूरी के व्युत्क्रमानुपाती होता है, और एक नया अनुमान बनाता है जो इनके अनुसार प्रतिरूप का औसत होता है। वह है,

$\left.y_{k+1}=\left(\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y_{k}\|}}\right)\right/\left(\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y_{k}\|}}\right).$

यह विधि लगभग सभी प्रारंभिक स्थितियों के लिए अभिसरण करती है, लेकिन जब इसका कोई अनुमान दिए गए बिंदुओं में से किसी एक पर पड़ता है तो यह अभिसरण करने में विफल हो सकता है। इन स्थितियों को संभालने के लिए इसे संशोधित किया जा सकता है जिससे कि यह सभी प्रारंभिक बिंदुओं के लिए अभिसरण कर सकता है।

बोस, माहेश्वरी & मोरिन (2003) इस समस्या का लगभग सर्वोत्तम समाधान खोजने के लिए अधिक ज्यामितीय अनुकूलन प्रक्रियाओं का वर्णन करते है। कोहेन et al. (2016) दिखाते है कि ज्यामितीय माध्यिका की गणना लगभग रैखिक समय में मनमाने ढंग से कैसे की जाती है। यह भी ध्यान दें कि समस्या को दूसरे क्रम के शंकु के रूप में तैयार किया जा सकता है

${\underset {y\in \mathbb {R} ^{n},\ s\in \mathbb {R} ^{m}}{\min }}\ \sum _{i=1}^{m}s_{i}{\text{ subject to }}s_{i}\geq \left\|x_{i}-y\right\|_{2}{\text{ for }}i=1,\ldots ,m,$

जिसे सामान्य अनुकूलन सॉल्वरों का उपयोग करके बहुपद समय में हल किया जा सकता है।

ज्यामितीय माध्यिका की विशेषता

यदि y दिए गए सभी बिंदुओं, xi से भिन्न है, तो y ज्यामितीय माध्यिका है यदि और केवल यदि यह संतुष्ट करती है:

$0=\sum _{i=1}^{m}{\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}.$

यह इसके बराबर है:

$\left.y=\left(\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y\|}}\right)\right/\left(\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y\|}}\right),$

जो वीज़फेल्ड के एल्गोरिथम से निकटता से संबंधित है।

सामान्यतः, y ज्यामितीय माध्यिका है यदि और केवल यदि सदिश ui हैं जैसे कि:

$0=\sum _{i=1}^{m}u_{i}$

जहां x_i ≠ y है और,

$u_{i}={\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}$

और x_i = y है और,

$\|u_{i}\|\leq 1.$

इस स्थिति का एक समकक्ष सूत्रीकरण होता है

$\sum _{1\leq i\leq m,x_{i}\neq y}{\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}\leq \left|\{\,i\mid 1\leq i\leq m,x_{i}=y\,\}\right|.$

इसे माध्यिका संपत्ति के सामान्यीकरण के रूप में देखा जा सकता है, इस अर्थ में कि बिंदुओं के किसी भी विभाजन, विशेष रूप से y के माध्यम से किसी भी हाइपरप्लेन द्वारा प्रेरित के रूप में, प्रत्येक तरफ y से सकारात्मक दिशाओं का समान और विपरीत योग होता है। आयामी स्थितियों में, हाइपरप्लेन बिंदु y ही है, और दिशाओं का योग (निर्देशित) गिनती माप को सरल करता है।

सामान्यीकरण

ज्यामितीय माध्यिका को यूक्लिडियन स्थान से सामान्य रीमैनियन मैनिफोल्ड (और यहां तक ​​कि मीट्रिक रिक्त स्थान) तक उसी विचार का उपयोग करके सामान्यीकृत किया जा सकता है जिसका उपयोग रीमैनियन मैनिफोल्ड पर फ्रेचेट माध्य को परिभाषित करने के लिए किया जाता है। $M$ संबंधित दूरी के साथ एक रिमेंनियन मैनिफोल्ड है $d(\cdot ,\cdot )$, $w_{1},\ldots ,w_{n}$ है $n$ वज़न का योग 1 है, और मान लीजिए $x_{1},\ldots ,x_{n}$ है $n$ टिप्पणियों से $M$.फिर हम भारित ज्यामितीय माध्यिका को परिभाषित करते हैं $m$ (या भारित फ़्रेचेट माध्यिका) डेटा बिंदुओं के रूप में

$m={\underset {x\in M}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}d(x,x_{i})$

यदि सभी भार बराबर है, तो $m$ ज्यामितीय माध्यिका है।

यह भी देखें

• मेडॉयड
• मध्य_पूर्ण_विचलन ज्यामितीय_मध्य_पूर्ण_विचलन

संदर्भ

• Bajaj, C. (1986). "Proving geometric algorithms nonsolvability: An application of factoring polynomials". Journal of Symbolic Computation. 2: 99–102. doi:10.1016/S0747-7171(86)80015-3.
• Bajaj, C. (1988). "The algebraic degree of geometric optimization problems". Discrete and Computational Geometry. 3 (2): 177–191. doi:10.1007/BF02187906.
• Bose, Prosenjit; Maheshwari, Anil; Morin, Pat (2003). "Fast approximations for sums of distances, clustering and the Fermat–Weber problem". Computational Geometry: Theory and Applications. 24 (3): 135–146. doi:10.1016/S0925-7721(02)00102-5.
• Brimberg, J. (1995). "The Fermat–Weber location problem revisited". Mathematical Programming. 71 (1, Ser. A): 71–76. doi:10.1007/BF01592245. MR 1362958. S2CID 206800756.
• Chandrasekaran, R.; Tamir, A. (1989). "Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem". Mathematical Programming. Series A. 44 (1–3): 293–295. doi:10.1007/BF01587094. S2CID 43224801.
• Cieslik, Dietmar (2006). Shortest Connectivity: An Introduction with Applications in Phylogeny. Combinatorial Optimization. Vol. 17. Springer. p. 3. ISBN 9780387235394.
• Cockayne, E. J.; Melzak, Z. A. (1969). "Euclidean constructability in graph minimization problems". Mathematics Magazine. 42 (4): 206–208. doi:10.2307/2688541. JSTOR 2688541.
• Cohen, Michael; Lee, Yin Tat; Miller, Gary; Pachocki, Jakub; Sidford, Aaron (2016). "Geometric median in nearly linear time" (PDF). Proc. 48th Symposium on Theory of Computing (STOC 2016). Association for Computing Machinery. arXiv:1606.05225. doi:10.1145/2897518.2897647.
• Drezner, Zvi; Klamroth, Kathrin; Schöbel, Anita; Wesolowsky, George O. (2002). "The Weber problem". Facility Location: Applications and Theory. Springer, Berlin. pp. 1–36. ISBN 9783540213451. MR 1933966.
• Eiselt, H. A.; Marianov, Vladimir (2011). Foundations of Location Analysis. International Series in Operations Research & Management Science. Vol. 155. Springer. p. 6. ISBN 9781441975720.
• Fekete, Sándor P.; Mitchell, Joseph S. B.; Beurer, Karin (2005). "On the continuous Fermat-Weber problem". Operations Research. 53 (1): 61–76. arXiv:cs.CG/0310027. doi:10.1287/opre.1040.0137. S2CID 1121.
• Fletcher, P. Thomas; Venkatasubramanian, Suresh; Joshi, Sarang (2009). "The geometric median on Riemannian manifolds with application to robust atlas estimation". NeuroImage. 45 (1 Suppl): s143–s152. doi:10.1016/j.neuroimage.2008.10.052. PMC 2735114. PMID 19056498.
• Haldane, J. B. S. (1948). "Note on the median of a multivariate distribution". Biometrika. 35 (3–4): 414–417. doi:10.1093/biomet/35.3-4.414.
• Krarup, Jakob; Vajda, Steven (1997). "On Torricelli's geometrical solution to a problem of Fermat". IMA Journal of Mathematics Applied in Business and Industry. 8 (3): 215–224. doi:10.1093/imaman/8.3.215. MR 1473041.
• Kuhn, Harold W. (1973). "A note on Fermat's problem". Mathematical Programming. 4 (1): 98–107. doi:10.1007/BF01584648. S2CID 22534094.
• Lawera, Martin; Thompson, James R. (1993). "Some problems of estimation and testing in multivariate statistical process control" (PDF). Proceedings of the 38th Conference on the Design of Experiments. U.S. Army Research Office Report. Vol. 93–2. pp. 99–126. Archived from the original on May 17, 2014.
• Lopuhaä, Hendrick P.; Rousseeuw, Peter J. (1991). "Breakdown points of affine equivariant estimators of multivariate location and covariance matrices". Annals of Statistics. 19 (1): 229–248. doi:10.1214/aos/1176347978. JSTOR 2241852.
• Nie, Jiawang; Parrilo, Pablo A.; Sturmfels, Bernd (2008). "Semidefinite representation of the k-ellipse". In Dickenstein, A.; Schreyer, F.-O.; Sommese, A.J. (eds.). Algorithms in Algebraic Geometry. IMA Volumes in Mathematics and its Applications. Vol. 146. Springer-Verlag. pp. 117–132. arXiv:math/0702005. Bibcode:2007math......2005N. doi:10.1007/978-0-387-75155-9_7. S2CID 16558095.
• Ostresh, L. (1978). "Convergence of a class of iterative methods for solving Weber location problem". Operations Research. 26 (4): 597–609. doi:10.1287/opre.26.4.597.
• Plastria, Frank (2006). "Four-point Fermat location problems revisited. New proofs and extensions of old results" (PDF). IMA Journal of Management Mathematics. 17 (4): 387–396. doi:10.1093/imaman/dpl007. Zbl 1126.90046..
• Spain, P. G. (1996). "The Fermat point of a triangle". Mathematics Magazine. 69 (2): 131–133. doi:10.1080/0025570X.1996.11996409. JSTOR 2690672?origin=pubexport. MR 1573157.
• Vardi, Yehuda; Zhang, Cun-Hui (2000). "The multivariate L₁[[Category: Templates Vigyan Ready]]-median and associated data depth". Proceedings of the National Academy of Sciences of the United States of America. 97 (4): 1423–1426 (electronic). Bibcode:2000PNAS...97.1423V. doi:10.1073/pnas.97.4.1423. MR 1740461. PMC 26449. PMID 10677477. {{cite journal}}: URL–wikilink conflict (help)
• Weber, Alfred (1909). Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes (in Deutsch). Tübingen: Mohr.
• Wesolowsky, G. (1993). "The Weber problem: History and perspective". Location Science. 1: 5–23.
• Weiszfeld, E. (1937). "Sur le point pour lequel la somme des distances de n[[Category: Templates Vigyan Ready]] points donnes est minimum". Tohoku Mathematical Journal (in français). 43: 355–386. {{cite journal}}: URL–wikilink conflict (help) Translated into English as Weiszfeld, E.; Plastria, Frank (April 2008). "On the point for which the sum of the distances to n given points is minimum". Annals of Operations Research. 167 (1): 7–41. doi:10.1007/s10479-008-0352-z. S2CID 21000317.