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

Not to be confused with माध्यिका (ज्यामिति) or ज्यामितीय माध्य.

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

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

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

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

बोस, माहेश्वरी & मोरिन (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 दिए गए सभी बिंदुओं से भिन्न है, तो x_i, तब 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 ज्यामितीय माध्यिका है यदि और केवल यदि सदिश u हैं_i चूंकि:

$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.