ज्यामितीय माध्यिका: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(15 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Point minimizing sum of distances to given points}}[[File:Geometric median example.svg|thumb|right|320px|अंकों की एक श्रृंखला के ज्यामितीय माध्यिका (पीले रंग में) का उदाहरण। द्रव्यमान का केंद्र नीले रंग में।]][[ज्यामिति]] में, [[यूक्लिडियन अंतरिक्ष|यूक्लिडियन]] में प्रतिरूप बिंदुओं के असतत सेट का '''ज्यामितीय माध्यिका''' वह बिंदु है जो प्रतिरूप बिंदुओं की दूरी को कम करता है। यह माध्यिका का सामान्यीकरण करता है, जिसमें एक-आयामी डेटा के लिए दूरियों के योग को कम करने का गुण होता है, और उच्च आयामों में एक [[केंद्रीय प्रवृत्ति]] प्रदान करता है। इसे 1-माध्यिका,<ref>The more general [[k-median problem|''k''-median problem]] asks for the location of ''k'' cluster centers minimizing the sum of distances from each sample point to its nearest center.</ref> स्थानिक माध्यिका,<ref name="dksw">{{harvtxt|Drezner|Klamroth|Schöbel|Wesolowsky|2002}}</ref> यूक्लिडियन मिनिसम बिंदु,<ref name="dksw" /> या टोरिकेली बिंदु{{sfnp|Cieslik|2006}} के रूप में भी जाना जाता है।
{{Short description|Point minimizing sum of distances to given points}}[[File:Geometric median example.svg|thumb|right|320px|अंकों की एक श्रृंखला के ज्यामितीय माध्यिका (पीले रंग में) का उदाहरण। द्रव्यमान का केंद्र नीले रंग में।]][[ज्यामिति]] में, [[यूक्लिडियन अंतरिक्ष|यूक्लिडियन स्पेस]] में प्रतिदर्शबिंदु के असतत सेट का '''ज्यामितीय माध्यिका''' वह बिंदु है जो प्रतिदर्शबिंदु की दूरी को कम करता है। यह माध्यिका का सामान्यीकरण करता है, जिसमें एक-आयामी डेटा के लिए दूरियों के योग को कम करने का गुण होता है, और उच्च आयामों में एक [[केंद्रीय प्रवृत्ति]] प्रदान करता है। इसे 1-माध्यिका,<ref>The more general [[k-median problem|''k''-median problem]] asks for the location of ''k'' cluster centers minimizing the sum of distances from each sample point to its nearest center.</ref> स्थानिक माध्यिका,<ref name="dksw">{{harvtxt|Drezner|Klamroth|Schöbel|Wesolowsky|2002}}</ref> यूक्लिडियन मिनिसम बिंदु,<ref name="dksw" /> या टोरिकेली बिंदु{{sfnp|Cieslik|2006}} के रूप में भी जाना जाता है।


ज्यामितीय माध्यिका [[स्थान पैरामीटर]] का एक महत्वपूर्ण अनुमानक होता है,{{sfnp|Lawera|Thompson|1993}} जहां इसे L<sub>1</sub> अनुमानक के रूप में भी जाना जाता है।<ref name="lr"/> यह स्थान में एक मानक समस्या भी है, जहाँ यह परिवहन की लागत को कम करने के लिए पता लगाने की समस्या का मॉडल बनाती है।{{sfnp|Eiselt|Marianov|2011}}
ज्यामितीय माध्यिका आंकड़ों में स्थान का एक महत्वपूर्ण अनुमानक है ,{{sfnp|Lawera|Thompson|1993}} जहां इसे L<sub>1</sub> अनुमानक के रूप में भी जाना जाता है।<ref name="lr"/> यह एक मानक समस्या भी है, जहाँ यह अभिगमन की लागत को कम करने के लिए पता लगाने के लिए मॉडल बनाती है।{{sfnp|Eiselt|Marianov|2011}}


समतल में तीन बिंदुओं के लिए समस्या की विशेष स्थिति (अर्थात्, नीचे दी गई परिभाषा में {{mvar|m}} = 3 और {{mvar|n}} = 2) को कभी-कभी फ़र्मेट की समस्या के रूप में भी जाना जाता है, मूल रूप से [[पियरे डी फर्मेट]] द्वारा एक समस्या के रूप में प्रस्तुत किया गया था और [[इवेंजलिस्ता टोरिकेली]] द्वारा हल किया गया था।{{sfnp|Krarup|Vajda|1997}} इसके समाधान को अब तीन प्रतिरूप बिंदुओं द्वारा गठित त्रिभुज के [[फर्मेट बिंदु]] के रूप में जाना जाता है।{{sfnp|Spain|1996}} बदले में ज्यामितीय माध्यिका को दूरियों के योग को कम करने की समस्या के लिए सामान्यीकृत किया जा सकता है, जिसे [[अल्फ्रेड वेबर]] की 1909 की स्थान पर पुस्तक में समस्या की चर्चा के बाद [[वेबर समस्या]] के रूप में जाना जाता है।<ref name="dksw"/> इसके अतिरिक्त कुछ स्रोत वेबर की समस्या को फ़र्मेट-वेबर समस्या कहते है,{{sfnp|Brimberg|1995}} लेकिन इस नाम का उपयोग ज्यामितीय माध्यिका समस्या के लिए करते है।{{sfnp|Bose|Maheshwari|Morin|2003}}
समतल में तीन बिंदुओं के लिए समस्या की विशेष स्थिति (अर्थात्, नीचे दी गई परिभाषा में {{mvar|m}} = 3 और {{mvar|n}} = 2) को कभी-कभी फ़र्मेट की समस्या के रूप में भी जाना जाता है; यह न्यूनतम स्टाइनर ट्री के निर्माण में उत्पन्न होता है, और मूल रूप से '''पियरे डी''' फर्मेट द्वारा एक समस्या के रूप में प्रस्तुत किया गया और इसे [[इवेंजलिस्ता टोरिकेली]] द्वारा हल किया गया था।{{sfnp|Krarup|Vajda|1997}} इसके विधि को अब तीन प्रतिदर्शबिंदु द्वारा गठित त्रिभुज के फर्मेट बिंदु के रूप में जाना जाता है। {{sfnp|Spain|1996}} बदले में ज्यामितीय माध्यिका को भारित दूरियों के योग को कम करने की समस्या के लिए सामान्यीकृत किया जा सकता है, जिसे [[अल्फ्रेड वेबर]] की 1909 की सुविधा स्थान पुस्तक में समस्या की चर्चा के बाद [[वेबर समस्या]] के रूप में जाना जाता है।<ref name="dksw"/> इसके अतिरिक्त कुछ स्रोत वेबर की समस्या को फ़र्मेट-वेबर समस्या कहते हैं,{{sfnp|Brimberg|1995}} लेकिन अन्य इस नाम का उपयोग भारित ज्यामितीय माध्यिका समस्या के लिए करते हैं।{{sfnp|Bose|Maheshwari|Morin|2003}}


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


== परिभाषा ==
== परिभाषा ==
Line 17: Line 17:
* 1-आयामी स्थिति के लिए, ज्यामितीय माध्य माध्यिका के साथ मेल खाता है। ऐसा इसलिए है क्योंकि अविभाजित माध्यिका भी बिंदुओं से दूरियों के योग को कम करती है। (अधिक त्रुटिहीन रूप से, यदि अंक पी<sub>1</sub> है, …, पी<sub>n</sub> है, उस क्रम में, ज्यामितीय माध्यिका मध्य बिंदु है <math>p_{(n+1)/2}</math> यदि n विषम है, लेकिन विशिष्ट रूप से निर्धारित नहीं है यदि n जोड़ है, जब यह दो मध्य बिंदुओं के बीच रेखा खंड में कोई बिंदु होती है <math>p_{n/2}</math> और <math>p_{(n/2)+1}</math>.) <ref name="haldane"/><ref>Claim 18.10, ''Geometric Methods and Optimization Problems'', V. Boltyanski, H. Martini, V. Soltan, Springer, 1999.</ref>
* 1-आयामी स्थिति के लिए, ज्यामितीय माध्य माध्यिका के साथ मेल खाता है। ऐसा इसलिए है क्योंकि अविभाजित माध्यिका भी बिंदुओं से दूरियों के योग को कम करती है। (अधिक त्रुटिहीन रूप से, यदि अंक पी<sub>1</sub> है, …, पी<sub>n</sub> है, उस क्रम में, ज्यामितीय माध्यिका मध्य बिंदु है <math>p_{(n+1)/2}</math> यदि n विषम है, लेकिन विशिष्ट रूप से निर्धारित नहीं है यदि n जोड़ है, जब यह दो मध्य बिंदुओं के बीच रेखा खंड में कोई बिंदु होती है <math>p_{n/2}</math> और <math>p_{(n/2)+1}</math>.) <ref name="haldane"/><ref>Claim 18.10, ''Geometric Methods and Optimization Problems'', V. Boltyanski, H. Martini, V. Soltan, Springer, 1999.</ref>
*ज्यामितीय माध्य अद्वितीय होता है जब भी बिंदु संरेख नहीं होती है<ref name="vz">{{harvtxt|Vardi|Zhang|2000}}</ref>
*ज्यामितीय माध्य अद्वितीय होता है जब भी बिंदु संरेख नहीं होती है<ref name="vz">{{harvtxt|Vardi|Zhang|2000}}</ref>
* ज्यामितीय मध्य यूक्लिडियन [[समानता (ज्यामिति)]] के लिए [[समतुल्य]] होता है, जिसमें [[अनुवाद (ज्यामिति)]] और [[रोटेशन (गणित)]] सम्मलित होता है।<ref name="lr"/><ref name="haldane">{{harvtxt|Haldane|1948}}</ref> इसका मतलब यह है कि एक ही परिणाम या तो ज्यामितीय माध्यिका को बदलकर, या समान परिवर्तन को प्रतिरूप डेटा में लागू करके और रूपांतरित डेटा के ज्यामितीय माध्य को खोजने से प्राप्त होता है। यह इस तथ्य से अनुसरण करता है कि ज्यामितीय मध्यिका केवल जोड़ीदार दूरी से परिभाषित होता है, और यह ऑर्थोगोनल कार्टेशियन निर्देशांक की प्रणाली पर निर्भर नहीं करता है जिसके द्वारा प्रतिरूप डेटा का प्रतिनिधित्व किया जाता है। इसके विपरीत, एक बहुभिन्नरूपी डेटा सेट के लिए घटक-वार माध्य सामान्य रोटेशन अपरिवर्तनीय नहीं होता है, न ही यह निर्देशांक  स्वतंत्र होता है<ref name="lr"/>
* ज्यामितीय मध्य यूक्लिडियन [[समानता (ज्यामिति)]] के लिए [[समतुल्य]] होता है, जिसमें [[अनुवाद (ज्यामिति)]] और [[रोटेशन (गणित)|रोटेशन]] सम्मलित होता है।<ref name="lr"/><ref name="haldane">{{harvtxt|Haldane|1948}}</ref> इसका मतलब यह है कि एक ही परिणाम या तो ज्यामितीय माध्यिका को बदलकर, या समान परिवर्तन को प्रतिरूप डेटा में लागू करके और रूपांतरित डेटा के ज्यामितीय माध्य को खोजने से प्राप्त होता है। यह इस तथ्य से अनुसरण करता है कि ज्यामितीय मध्यिका केवल जोड़ीदार दूरी से परिभाषित होता है, और यह ऑर्थोगोनल कार्टेशियन निर्देशांक की प्रणाली पर निर्भर नहीं करता है जिसके द्वारा प्रतिरूप डेटा का प्रतिनिधित्व किया जाता है। इसके विपरीत, एक बहुभिन्नरूपी डेटा सेट के लिए घटक-वार माध्य सामान्य रोटेशन अपरिवर्तनीय नहीं होता है, न ही यह निर्देशांक  स्वतंत्र होता है<ref name="lr"/>
*ज्यामितीय माध्यिका का विश्लेषण बिंदु 0.5 है।<ref name="lr">{{harvtxt|Lopuhaä|Rousseeuw|1991}}</ref> अर्थात्, प्रतिरूप डेटा का आधा हिस्सा मनमाने ढंग से दूषित होता है, और नमूनों का माध्य अभी भी अदूषित डेटा के स्थान के लिए एक [[मजबूत अनुमानक]] प्रदान करता है
*ज्यामितीय माध्यिका का विश्लेषण बिंदु 0.5 है।<ref name="lr">{{harvtxt|Lopuhaä|Rousseeuw|1991}}</ref> अर्थात्, प्रतिरूप डेटा का आधा हिस्सा मनमाने ढंग से दूषित होता है, और नमूनों का माध्य अभी भी अदूषित डेटा के स्थान के लिए एक [[मजबूत अनुमानक]] प्रदान करता है


Line 24: Line 24:
*4 [[समतलीय]] बिंदुओं के लिए, यदि चार बिंदुओं में से एक बिंदु अन्य तीन बिंदुओं से बने त्रिभुज के अंदर है, तो ज्यामितीय माध्यिका वह बिंदु होती है। अन्यथा, चार बिंदु उत्तल चतुर्भुज बनाते है और ज्यामितीय माध्य चतुर्भुज के विकर्णों का क्रॉसिंग बिंदु होता है। चार समतलीय बिंदुओं का ज्यामितीय माध्य चार बिंदुओं के अद्वितीय [[रेडॉन बिंदु|बिंदु]] के समान होता है<ref>{{harvtxt|Cieslik|2006}}, p.&nbsp;6; {{harvtxt|Plastria|2006}}. The convex case was originally proven by [[Giovanni Fagnano]].</ref>
*4 [[समतलीय]] बिंदुओं के लिए, यदि चार बिंदुओं में से एक बिंदु अन्य तीन बिंदुओं से बने त्रिभुज के अंदर है, तो ज्यामितीय माध्यिका वह बिंदु होती है। अन्यथा, चार बिंदु उत्तल चतुर्भुज बनाते है और ज्यामितीय माध्य चतुर्भुज के विकर्णों का क्रॉसिंग बिंदु होता है। चार समतलीय बिंदुओं का ज्यामितीय माध्य चार बिंदुओं के अद्वितीय [[रेडॉन बिंदु|बिंदु]] के समान होता है<ref>{{harvtxt|Cieslik|2006}}, p.&nbsp;6; {{harvtxt|Plastria|2006}}. The convex case was originally proven by [[Giovanni Fagnano]].</ref>
== गणना ==
== गणना ==
ज्यामितीय माध्यिका की आसानी से समझ में आने वाली अवधारणा होने के अतिरिक्त, इसकी गणना करना एक चुनौती होती है। केंद्रक या द्रव्यमान का केंद्र, जिसे ज्यामितीय माध्यिका के समान परिभाषित किया गया है, प्रत्येक बिंदु के लिए दूरी के वर्गों के योग को कम करने के रूप में, एक सरल सूत्र द्वारा पाया जा सकता है - इसके निर्देशांक बिंदुओं के निर्देशांक के औसत होते है - लेकिन इसमें दिखाया गया है कि कोई स्पष्ट सूत्र, न ही एक त्रुटिहीन एल्गोरिदम जिसमें केवल अंकगणितीय संचालन और kth मूल सम्मलित है, सामान्य रूप से ज्यामितीय माध्यिका के लिए उपस्तिथ हो सकते है। इसलिए, गणना के इस मॉडल के अनुसार इस समस्या के समाधान के लिए केवल संख्यात्मक या प्रतीकात्मक सन्निकटन संभव होता है।<ref>{{harvtxt|Bajaj|1986}}; {{harvtxt|Bajaj|1988}}. Earlier, {{harvtxt|Cockayne|Melzak|1969}} proved that the Steiner point for 5 points in the plane cannot be constructed with [[ruler and compass]]</ref>
ज्यामितीय माध्यिका की आसानी से समझ में आने वाली अवधारणा होने के बावजूद, इसकी गणना करना एक चुनौती है। केंद्रक या द्रव्यमान का केंद्र, जिसे ज्यामितीय माध्यिका के समान परिभाषित किया गया है, प्रत्येक बिंदु के लिए दूरी के वर्गों के योग को कम करने के रूप में, एक सरल सूत्र द्वारा पाया जा सकता है - इसके निर्देशांक बिंदुओं के निर्देशांक के औसत होते है - लेकिन इसमें दिखाया गया है कि कोई स्पष्ट सूत्र, न ही एक त्रुटिहीन एल्गोरिदम जिसमें केवल अंकगणितीय संचालन और kth मूल सम्मलित है, सामान्य रूप से ज्यामितीय माध्यिका के लिए उपस्तिथ हो सकते है। इसलिए, गणना के इस मॉडल के अनुसार इस समस्या के समाधान के लिए केवल संख्यात्मक या प्रतीकात्मक सन्निकटन संभव होता है।<ref>{{harvtxt|Bajaj|1986}}; {{harvtxt|Bajaj|1988}}. Earlier, {{harvtxt|Cockayne|Melzak|1969}} proved that the Steiner point for 5 points in the plane cannot be constructed with [[ruler and compass]]</ref>


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


== ज्यामितीय माध्यिका की विशेषता ==
== ज्यामितीय माध्यिका की विशेषता ==
यदि y दिए गए सभी बिंदुओं से भिन्न है, तो x<sub>''i''</sub>, तब y ज्यामितीय माध्यिका है और केवल यदि यह संतुष्ट करती है:
यदि y दिए गए सभी बिंदुओं, xi से भिन्न है, तो y ज्यामितीय माध्यिका है यदि और केवल यदि यह संतुष्ट करती है:
:<math>0 = \sum_{i=1}^m \frac {x_i - y} {\left \| x_i - y \right \|}.</math>
:<math>0 = \sum_{i=1}^m \frac {x_i - y} {\left \| x_i - y \right \|}.</math>
यह इसके बराबर है:
यह इसके बराबर है:
Line 43: Line 43:
जो वीज़फेल्ड के एल्गोरिथम से निकटता से संबंधित है।
जो वीज़फेल्ड के एल्गोरिथम से निकटता से संबंधित है।


सामान्यतः, y ज्यामितीय माध्यिका है और केवल यदि सदिश u है<sub>''i''</sub> चूंकि:
सामान्यतः, y ज्यामितीय माध्यिका है यदि और केवल यदि सदिश ui हैं जैसे कि:
:<math>0 =  \sum_{i=1}^m u_i </math>
:<math>0 =  \sum_{i=1}^m u_i </math>
जहां x<sub>''i''</sub> ≠ y है और,
जहां x<sub>''i''</sub> ≠ y है और,
Line 49: Line 49:
और x<sub>''i''</sub> = y है और,
और x<sub>''i''</sub> = y है और,
:<math>\| u_i \| \leq 1 .</math>
:<math>\| u_i \| \leq 1 .</math>
इस स्थिति का एक समकक्ष सूत्रीकरण है
इस स्थिति का एक समकक्ष सूत्रीकरण होता है
:<math>\sum _{1\le i\le m, x_i\ne y}
:<math>\sum _{1\le i\le m, x_i\ne y}
\frac {x_i - y} {\left \| x_i - y \right \|} \le \left|\{
\frac {x_i - y} {\left \| x_i - y \right \|} \le \left|\{
\,i\mid 1\le i\le m, x_i= y\,\}\right|.</math>
\,i\mid 1\le i\le m, x_i= y\,\}\right|.</math>
इसे मध्य संपत्ति के सामान्यीकरण के रूप में देखा जा सकता है, इस अर्थ में कि बिंदुओं के किसी भी विभाजन, विशेष रूप से y के माध्यम से किसी के रूप में, प्रत्येक तरफ y से सकारात्मक दिशाओं का समान और विपरीत योग होता है। एक आयामी स्थिति में, बिंदु y होती है, और दिशाओं का योग (निर्देशित) गिनती माप को सरल करता है।
इसे माध्यिका संपत्ति के सामान्यीकरण के रूप में देखा जा सकता है, इस अर्थ में कि बिंदुओं के किसी भी विभाजन, विशेष रूप से ''y'' के माध्यम से किसी भी हाइपरप्लेन द्वारा प्रेरित के रूप में, प्रत्येक तरफ ''y'' से सकारात्मक दिशाओं का समान और विपरीत योग होता है। आयामी स्थितियों में, हाइपरप्लेन बिंदु ''y'' ही है, और दिशाओं का योग (निर्देशित) गिनती माप को सरल करता है।


== सामान्यीकरण ==
== सामान्यीकरण ==
ज्यामितीय माध्यिका को यूक्लिडियन स्थान से सामान्य [[रीमैनियन कई गुना]] तक उसी विचार का उपयोग करके सामान्यीकृत किया जा सकता है जिसका उपयोग रीमैनियन मैनिफोल्ड माध्य को परिभाषित करने के लिए किया जाता है।<ref>{{cite conference |url=https://ieeexplore.ieee.org/document/4587747 |title=ज्यामितीय माध्यिका के माध्यम से रीमैनियन मैनिफोल्ड्स पर मजबूत आंकड़े|last1=Fletcher |first1=P. Thomas |last2=Venkatasubramanian |first2=Suresh |last3=Joshi |first3=Sarang |date=23 June 2008 |publisher=IEEE |book-title=2008 IEEE Conference on Computer Vision and Pattern Recognition |location=Anchorage, AK, USA |conference=IEEE Conference on Computer Vision and Pattern Recognition}}</ref>{{sfnp|Fletcher|Venkatasubramanian|Joshi|2009}} <math>M</math> संबंधित दूरी के साथ एक रिमेंनियन मैनिफोल्ड है <math>d(\cdot, \cdot)</math>, <math>w_1, \ldots, w_n</math> है <math>n</math> वज़न का योग 1 है, और <math>x_1, \ldots, x_n</math> है <math>n</math> से अवलोकन <math>M</math>. फिर हम ज्यामितीय माध्यिका को परिभाषित करते है <math>m</math> डेटा बिंदुओं के रूप में
ज्यामितीय माध्यिका को यूक्लिडियन स्थान से सामान्य [[रीमैनियन कई गुना|रीमैनियन मैनिफोल्ड]] (और यहां तक ​​कि मीट्रिक रिक्त स्थान) तक उसी विचार का उपयोग करके सामान्यीकृत किया जा सकता है जिसका उपयोग रीमैनियन मैनिफोल्ड पर फ्रेचेट माध्य को परिभाषित करने के लिए किया जाता है।<ref>{{cite conference |url=https://ieeexplore.ieee.org/document/4587747 |title=ज्यामितीय माध्यिका के माध्यम से रीमैनियन मैनिफोल्ड्स पर मजबूत आंकड़े|last1=Fletcher |first1=P. Thomas |last2=Venkatasubramanian |first2=Suresh |last3=Joshi |first3=Sarang |date=23 June 2008 |publisher=IEEE |book-title=2008 IEEE Conference on Computer Vision and Pattern Recognition |location=Anchorage, AK, USA |conference=IEEE Conference on Computer Vision and Pattern Recognition}}</ref>{{sfnp|Fletcher|Venkatasubramanian|Joshi|2009}} <math>M</math> संबंधित दूरी के साथ एक रिमेंनियन मैनिफोल्ड है <math>d(\cdot, \cdot)</math>, <math>w_1, \ldots, w_n</math> है <math>n</math> वज़न का योग 1 है, और मान लीजिए <math>x_1, \ldots, x_n</math> है <math>n</math> टिप्पणियों से <math>M</math>.फिर हम भारित ज्यामितीय माध्यिका को परिभाषित करते हैं <math>m</math> (या भारित फ़्रेचेट माध्यिका) डेटा बिंदुओं के रूप में
: <math> m = \underset{x \in M}{\operatorname{arg\,min}} \sum_{i=1}^n w_i d(x,x_i) </math>.
: <math> m = \underset{x \in M}{\operatorname{arg\,min}} \sum_{i=1}^n w_i d(x,x_i) </math>
यदि सभी बराबर है, तो हम बस यही कहते है <math>m</math> ज्यामितीय माध्यिका है।ka
यदि सभी भार बराबर है, तो <math>m</math> ज्यामितीय माध्यिका है।


== यह भी देखें ==
== यह भी देखें ==
* [[मेडॉयड]]
* [[मेडॉयड]]
* मध्य_पूर्ण_विचलन#ज्यामितीय_मध्य_पूर्ण_विचलन
* मध्य_पूर्ण_विचलन ज्यामितीय_मध्य_पूर्ण_विचलन


== टिप्पणियाँ ==
== टिप्पणियाँ ==
Line 298: Line 298:
  }}
  }}
{{refend}}
{{refend}}
[[Category: साधन]] [[Category: बहुभिन्नरूपी आँकड़े]] [[Category: गैर पैरामीट्रिक आँकड़े]] [[Category: गणितीय अनुकूलन]] [[Category: ज्यामितीय एल्गोरिदम]] [[Category: वर्णनात्मक आँकड़े]]


 
[[Category:CS1 Deutsch-language sources (de)]]
 
[[Category:CS1 errors]]
[[Category: Machine Translated Page]]
[[Category:CS1 français-language sources (fr)]]
[[Category:Created On 20/03/2023]]
[[Category:Created On 20/03/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:गणितीय अनुकूलन]]
[[Category:गैर पैरामीट्रिक आँकड़े]]
[[Category:ज्यामितीय एल्गोरिदम]]
[[Category:बहुभिन्नरूपी आँकड़े]]
[[Category:वर्णनात्मक आँकड़े]]
[[Category:साधन]]

Latest revision as of 18:02, 15 April 2023

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

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

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

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

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

परिभाषा

औपचारिक रूप से, m बिंदुओं के दिए गए सेट के लिए प्रत्येक के साथ , ज्यामितीय माध्यिका के रूप में परिभाषित किया गया है

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

गुण

  • 1-आयामी स्थिति के लिए, ज्यामितीय माध्य माध्यिका के साथ मेल खाता है। ऐसा इसलिए है क्योंकि अविभाजित माध्यिका भी बिंदुओं से दूरियों के योग को कम करती है। (अधिक त्रुटिहीन रूप से, यदि अंक पी1 है, …, पीn है, उस क्रम में, ज्यामितीय माध्यिका मध्य बिंदु है यदि n विषम है, लेकिन विशिष्ट रूप से निर्धारित नहीं है यदि n जोड़ है, जब यह दो मध्य बिंदुओं के बीच रेखा खंड में कोई बिंदु होती है और .) [11][12]
  • ज्यामितीय माध्य अद्वितीय होता है जब भी बिंदु संरेख नहीं होती है[13]
  • ज्यामितीय मध्य यूक्लिडियन समानता (ज्यामिति) के लिए समतुल्य होता है, जिसमें अनुवाद (ज्यामिति) और रोटेशन सम्मलित होता है।[5][11] इसका मतलब यह है कि एक ही परिणाम या तो ज्यामितीय माध्यिका को बदलकर, या समान परिवर्तन को प्रतिरूप डेटा में लागू करके और रूपांतरित डेटा के ज्यामितीय माध्य को खोजने से प्राप्त होता है। यह इस तथ्य से अनुसरण करता है कि ज्यामितीय मध्यिका केवल जोड़ीदार दूरी से परिभाषित होता है, और यह ऑर्थोगोनल कार्टेशियन निर्देशांक की प्रणाली पर निर्भर नहीं करता है जिसके द्वारा प्रतिरूप डेटा का प्रतिनिधित्व किया जाता है। इसके विपरीत, एक बहुभिन्नरूपी डेटा सेट के लिए घटक-वार माध्य सामान्य रोटेशन अपरिवर्तनीय नहीं होता है, न ही यह निर्देशांक स्वतंत्र होता है[5]
  • ज्यामितीय माध्यिका का विश्लेषण बिंदु 0.5 है।[5] अर्थात्, प्रतिरूप डेटा का आधा हिस्सा मनमाने ढंग से दूषित होता है, और नमूनों का माध्य अभी भी अदूषित डेटा के स्थान के लिए एक मजबूत अनुमानक प्रदान करता है

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

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

गणना

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

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

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

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

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

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

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

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

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

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

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

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

और xi = y है और,

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

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

सामान्यीकरण

ज्यामितीय माध्यिका को यूक्लिडियन स्थान से सामान्य रीमैनियन मैनिफोल्ड (और यहां तक ​​कि मीट्रिक रिक्त स्थान) तक उसी विचार का उपयोग करके सामान्यीकृत किया जा सकता है जिसका उपयोग रीमैनियन मैनिफोल्ड पर फ्रेचेट माध्य को परिभाषित करने के लिए किया जाता है।[17][18] संबंधित दूरी के साथ एक रिमेंनियन मैनिफोल्ड है , है वज़न का योग 1 है, और मान लीजिए है टिप्पणियों से .फिर हम भारित ज्यामितीय माध्यिका को परिभाषित करते हैं (या भारित फ़्रेचेट माध्यिका) डेटा बिंदुओं के रूप में

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

यह भी देखें

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

टिप्पणियाँ

  1. The more general k-median problem asks for the location of k cluster centers minimizing the sum of distances from each sample point to its nearest center.
  2. 2.0 2.1 2.2 Drezner et al. (2002)
  3. Cieslik (2006).
  4. Lawera & Thompson (1993).
  5. 5.0 5.1 5.2 5.3 Lopuhaä & Rousseeuw (1991)
  6. Eiselt & Marianov (2011).
  7. Krarup & Vajda (1997).
  8. Spain (1996).
  9. Brimberg (1995).
  10. Bose, Maheshwari & Morin (2003).
  11. 11.0 11.1 11.2 Haldane (1948)
  12. Claim 18.10, Geometric Methods and Optimization Problems, V. Boltyanski, H. Martini, V. Soltan, Springer, 1999.
  13. 13.0 13.1 Vardi & Zhang (2000)
  14. Cieslik (2006), p. 6; Plastria (2006). The convex case was originally proven by Giovanni Fagnano.
  15. Bajaj (1986); Bajaj (1988). Earlier, Cockayne & Melzak (1969) proved that the Steiner point for 5 points in the plane cannot be constructed with ruler and compass
  16. Weiszfeld (1937); Kuhn (1973); Chandrasekaran & Tamir (1989).
  17. Fletcher, P. Thomas; Venkatasubramanian, Suresh; Joshi, Sarang (23 June 2008). "ज्यामितीय माध्यिका के माध्यम से रीमैनियन मैनिफोल्ड्स पर मजबूत आंकड़े". 2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE Conference on Computer Vision and Pattern Recognition. Anchorage, AK, USA: IEEE.
  18. Fletcher, Venkatasubramanian & Joshi (2009).


संदर्भ