Geometriai középpont

Az euklideszi térben lévő diszkrét ponthalmaz geometriai középpontja (statisztikai értelemben - minták) az a pont, ahol a halmaz pontjaitól való távolságok összege minimálisra csökken. A geometriai középpont általánosítja a mediánt olyan matematikai statisztikává, amely minimalizálja a távolságokat egy egydimenziós adatmintában. Így a geometriai középpont a nagy dimenziós terek központi trendjét tükrözi. A fogalom 1-medián [1] , térbeli medián [2] vagy Torricelli pont [3] elnevezésekkel is ismert .

A geometriai középpont fontos eltolódásbecslő a statisztikában [4] , amelyben ezt a fogalmat L 1 pontszámként [5] ismerik . A geometriai középpont megtalálása szintén szokásos feladat az objektumok elhelyezésénél , ahol a szállítási költségek minimalizálása érdekében modellezzük az objektumok elhelyezkedését (termelés vagy fogyasztás) [6]

A probléma egy speciális esetét a síkban három pontra (azaz m =3 és n =2 az alábbiakban leírtak szerint) néha Fermat-problémaként írják le. Minimális Steiner fák építésénél merül fel, és először Pierre de Fermat állította fel problémaként, és Evangelista Torricelli oldotta meg [7] . A probléma megoldását ma a háromszög Fermat-pontjaként ismerjük [8] . A geometriai középpont keresése viszont általánosítható a súlyozott távolságok összegének minimalizálásának problémájára . Ezt a problémát Weber-problémaként ismerik, mivel Alfred Weber egy 1909-es tárgyelhelyezési könyvben tárgyalta ezt a problémát [2] . Egyes források helyett a Fermat–Weber-probléma [9] elnevezést használják , de vannak olyan források, amelyek ugyanezt a nevet használják a súlyozatlan problémára [10].

Vesolovsky [11] áttekintést adott a geometriai középpont problémájáról. Lásd Fekete, Michel és Boyer [12] cikkét a probléma nem-diszkrét halmazok esetére való általánosításáról.

Definíció

Formálisan adott egy m pontot tartalmazó halmaz , ahol minden , a geometriai középpont a következőképpen van definiálva $x_{1},x_{2},\dots ,x_{m}\,$ $x_{i}\in \mathbb {R} ^{n}$

geometriai középpont

={\underset {y\in \mathbb {R} ^{n}}{\operátornév {arg\,min} }}\sum _{i=1}^{m}\left\|x_{ i}-y\right\|_{2}

Vegye figyelembe, hogy itt az arg min az argumentum azon értékét jelenti , amelynél a minimális összeget elérjük. Ez az a pont , amelyre az összes euklideszi távolság összege minimális. $y$ $y$ $x_{i}$

Tulajdonságok

Egydimenziós tér esetén a medián a geometriai középpont (ha páros számú pont van, a geometriai középpont nem feltétlenül egyedi). Ennek az az oka, hogy az egydimenziós medián minimalizálja a pontok távolságának összegét [13] .
A geometriai középpont az egyetlen minden olyan esetben, amikor a pontok nem kollineárisak [14] .
A geometriai középpont ekvivariáns az euklideszi hasonlóságra , transzlációra és elforgatásra [5] [13] . Ez azt jelenti, hogy ugyanazt az eredményt kapja, ha az átalakítás során megtalálja a középpont képét, vagy ha ugyanazt a transzformációt alkalmazza az összes mintapontra, majd megtalálja a geometriai középpontot. Ez a tulajdonság abból adódik, hogy a geometriai középpontot csak páronkénti távolságok alapján határozzuk meg, és nem függ a derékszögű derékszögű koordináták rendszerétől . Ezzel szemben a többváltozós adatok komponensenkénti mediánja a forgatás során általában nem invariáns, és a koordináták megválasztásától függ [5] .
A geometriai középpont töréspontja 0,5 [5] . Vagyis a mintaadatok akár fele is megbízhatatlan lehet, de a minta geometriai középpontja a sértetlen adatok helyzetének stabil becslése marad.

Különleges alkalmak

3 ( nem kollineáris ) pont esetén, ha egy olyan háromszög egyik sarka, amelynek csúcsai ezekben a pontokban 120°-os vagy nagyobbak, akkor a geometriai középpont az adott sarok csúcsa. Ha minden szög 120°-nál kisebb, akkor a geometriai középpont a háromszög belsejében lévő pont, amely 120°-os szöget zár be bármely háromszög-csúcspárral [13] . Ezt a pontot a háromszög Fermat -pontjaként ismerjük (ha három pont egy vonalban van, akkor a geometriai középpont egybeesik azzal a ponttal, amely a másik kettő között van).
4 egysíkú pont esetén, ha a négy pont egyike a másik három pont által alkotott háromszögön belül helyezkedik el, akkor a lokusz az a belső pont lesz. Ellenkező esetben négy pont egy konvex négyszöget alkot , és a négyszög átlóinak metszéspontja szolgál geometriai középpontként. Négy egysíkú pont geometriai középpontja megegyezik a négy pont egyetlen Radon -pontjával [15] .

Számítás

Bár a geometriai középpont fogalma könnyen érthető, kiszámítása nehézkes. A háromszög súlypontja (vagyis tömegközéppontja ), amelyet a geometriai középponthoz hasonlóan úgy határozunk meg, hogy minimalizálja az egyes pontok távolságának négyzetének összegét , egyszerű képletekkel megkapható - koordinátái a háromszög koordinátáinak számtani középértékei. a pontokat. A geometriai középpont ilyen egyszerű képlete azonban nem ismert. Még azt is kimutatták, hogy nincs sem explicit formula , sem egzakt algoritmus, amely csak aritmetikai és radix műveleteket használna. Így ennek a problémának a megoldására csak közelítések léteznek [16] .

Lehetőség van azonban a geometriai középpont közelítésének kiszámítására egy iteratív eljárással, amelyben minden lépés pontosabb közelítést ad. Az ilyen típusú eljárások abból a tényből származtathatók, hogy a mintapontok távolságának összege egy konvex függvény , mivel az egyes mintapontok távolsága konvex függvény, és a konvex függvények összege is konvex függvény. Így a távolságok összegének csökkentésére szolgáló eljárás nem eshet a lokális optimumba .

Az egyik ilyen megközelítés a Weisfeld-algoritmus ( André Weisfeld ) [17] [18] [19] , amely az iteratív súlyozott legkisebb négyzetek módszere változó súllyal. Ez az algoritmus beállít egy súlykészletet, amely fordítottan arányos az aktuális közelítés távolságaival, és kiszámít egy új közelítést, amely a mintapontok súlyozott átlaga ezeknek a súlyoknak megfelelően. Azaz

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

A módszer szinte minden kiindulási pozícióból konvergál, de meghiúsulhat, ha a közelítés az egyik mintapontnál végződik. Az algoritmus úgy módosítható, hogy minden kiindulási pontra konvergáljon [14] .

Bose, Mageshwari és Morin [10] egy kifinomultabb optimalizálási eljárást írt le egy adott probléma megközelítőleg optimális megoldásának megtalálására. Ahogy Ne, Parrilo és Starmfils [20] megmutatta , a probléma félig meghatározott programozási problémaként fogható fel .

Cohen, Lee, Miller és Pachoki [21] megmutatta, hogyan lehet kiszámítani a geometriai középpontot tetszőleges pontossággal szinte lineáris időben.

A geometriai középpont leírása

Ha az y pont különbözik az összes megadott x j mintaponttól , akkor y akkor és csak akkor a geometriai középpont, ha

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

Ez egyenértékű

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

amely szorosan összefügg a Weisfeld-algoritmussal.

Általában y akkor és csak akkor geometriai középpont, ha vannak olyan u j vektorok , amelyekre

{\displaystyle 0=\sum _{j=1}^{m}u_{j))

ahol x j ≠ y ,

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

és x j = y esetén

\|u_{j}\|\leq 1.

Ennek a feltételnek egyenértékű megfogalmazása

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

Általánosítások

A geometriai középpont általánosítható euklideszi terekről általános Riemann-sokaságokra (sőt metrikus terekre is ), ugyanazt az ötletet használva, mint a Fréchet-átlag meghatározásához Riemann-sokaságokon [22] . Legyen egy Riemann-sokaság távolságfüggvénnyel , legyenek súlyok, amelyek összege 1, és legyenek megfigyelések -ból . Ezután meghatározzuk az adatpontok súlyozott geometriai középpontját (vagy súlyozott Fréchet-átlagát). $M$ $d(\cdot ,\cdot )$ $w_{1},\ldots ,w_{n}$ $n$ $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})

Ha minden súly egyenlő, akkor megmondjuk, mi a geometriai középpont. $m$

Jegyzetek

↑ Az általánosabb k -medián probléma k középpont helyzetére kérdez rá, minimalizálva a halmaz minden pontjától a legközelebbi középpontig tartó távolságok összegét.
↑ 1 2 Drezner, Klamroth, Schöbel, Wesolowsky, 2002 .
↑ Cieslik, 2006 .
↑ Lawera, Thompson, 1993 .
↑ 1 2 3 4 Lopuhaä, Rousseeuw, 1991 .
↑ Eiselt, Marianov, 2011 .
↑ Krarup, Vajda, 1997 .
↑ Spanyolország, 1996 .
↑ Brimberg, 1995 .
↑ 1 2 Bose, Maheshwari, Morin, 2003 .
↑ Wesolowsky, 1993 .
↑ Fekete, Mitchell, Beurer, 2005 .
↑ 1 2 3 Haldane, 1948 .
↑ 12 Vardi, Zhang, 2000 .
↑ Cieslik, 2006 ; Plasztika, 2006 . A konvex esetet először Giovanni Fagnano bizonyította .
↑ Bajaj, 1986 ; Bajaj, 1988 . Korábban Cockayne és Melzak Cockayne, Melzak, 1969 bebizonyította, hogy a Steiner-pont a síkban lévő 5 pontra nem szerkeszthető meg iránytűvel és egyenes éllel.
↑ Weiszfeld, 1937 .
↑ Kuhn, 1973 .
↑ Chandrasekaran, Tamir, 1989 .
↑ Nie, Parrilo, Sturmfels, 2008 .
↑ Cohen, Lee, Miller, Pachocki, Sidford, 2016 .
↑ Fletcher, Venkatasubramanian, Joshi, 2009 .

Irodalom

Chandrajit Bajaj. Geometriai algoritmusok feloldhatatlanságának bizonyítása: A faktorálási polinomok alkalmazása // Journal of Symbolic Computation . - 1986. - T. 2 . — S. 99–102 . - doi : 10.1016/S0747-7171(86)80015-3 .
A geometriai optimalizálási problémák algebrai foka // Diszkrét és számítási geometria . - 1988. - T. 3 . – S. 177–191 . - doi : 10.1007/BF02187906 .
Gyors közelítések távolságok összegére, klaszterezésre és a Fermat–Weber problémára // Számítási geometria: elmélet és alkalmazások . - 2003. - T. 24 , sz. 3 . – S. 135–146 . - doi : 10.1016/S0925-7721(02)00102-5 .
J. Brimberg. A Fermat–Weber helymeghatározási probléma újra áttekintve // Matematikai programozás . - 1995. - T. 71 , sz. 1 Ser. A. _ – S. 71–76 . - doi : 10.1007/BF01592245 .
R. Chandrasekaran, A. Tamir. Nyitott kérdések a Weiszfeld-algoritmussal kapcsolatban a Fermat-Weber helyproblémára // Matematikai programozás . - 1989. - T. 44 . – S. 293–295 . - doi : 10.1007/BF01587094 .
Dietmar Cieslik. Legrövidebb kapcsolat: Bevezetés a filogenetikai alkalmazásokba . - Springer, 2006. - 17. évf. - ISBN 9780387235394 .
EJ Cockayne, ZA Melzak. Euklideszi konstruálhatóság gráfminimalizálási problémákban // Mathematics Magazine . - 1969. - T. 42 , sz. 4 . – S. 206–208 . - doi : 10.2307/2688541 . — .
Michael Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, Aaron Sidford. Geometriai medián közel lineáris időben // Proc. 48. Számítástechnikai Szimpózium (STOC 2016). - Számítógépek Szövetsége , 2016.
Zvi Drezner, Kathrin Klamroth, Anita Schöbel, George O. Wesolowsky. A Weber-probléma // Létesítmény helye: Alkalmazások és elmélet . - Springer, Berlin, 2002. - S. 1-36.
HA Eiselt, Vlagyimir Marianov. A helyelemzés alapjai . - Springer, 2011. - T. 155. - P. 6. - (International Series in Operations Research & Management Science). — ISBN 9781441975720 .
Sándor P. Fekete, Joseph SB Mitchell, Karin Beurer. A folyamatos Fermat-Weber problémáról // Operations Research . - 2005. - T. 53 , sz. 1 . – S. 61–76 . - doi : 10.1287/opre.1040.0137 . — arXiv : cs.CG/0310027 .
P. Thomas Fletcher, Suresh Venkatasubramanian, Sarang Joshi. A Riemann-féle sokaságok geometriai mediánja robusztus atlaszbecslés alkalmazásával // NeuroImage. - 2009. - T. 45 , sz. 1 Suppl . — S. s143–s152 . - doi : 10.1016/j.neuroimage.2008.10.052 . — PMID 19056498 .
JBS Haldane. Megjegyzés a többváltozós eloszlás mediánjához // Biometrika. - 1948. - T. 35 , sz. 3–4 . – S. 414–417 . - doi : 10.1093/biomet/35.3-4.414 .
Jakob Krarup, Steven Vajda. Torricelli geometriai megoldásáról Fermat problémájára // IMA Journal of Mathematics Applied in Business and Industry. - 1997. - T. 8 , sz. 3 . – S. 215–224 . - doi : 10.1093/imaman/8.3.215 .
Harold W Kuhn. Megjegyzés Fermat-problémához // Matematikai programozás . - 1973. - T. 4 , sz. 1 . – S. 98–107 . - doi : 10.1007/BF01584648 .
Martin Lawera, James R. Thompson. A becslés és tesztelés néhány problémája a többváltozós statisztikai folyamatirányításban // Proceedings of the 38th Conference on the Design of Experiments . - 1993. - T. 93-2. — P. 99–126.
Hendrick P. Lopuhaä, Peter J. Rousseeuw. Többváltozós hely- és kovarianciamátrixok affin ekvivariáns becsléseinek bontási pontjai // Annals of Statistics . - 1991. - T. 19 , sz. 1 . – S. 229–248 . - doi : 10.1214/aos/1176347978 . — .
Jiawang Nie, Pablo A. Parrilo, Bernd Sturmfels. Algoritmusok az algebrai geometriában / A. Dickenstein, F.-O. Schreyer, AJ Sommese. - Springer-Verlag, 2008. - T. 146. - S. 117-132. - (IMA kötetek a matematikából és alkalmazásaiból).
L. Ostresh. A Weber-helymeghatározási probléma megoldásának iteratív módszereinek osztályának konvergenciája // Operációkutatás . - 1978. - T. 26 , sz. 4 . – S. 597–609 . doi : 10.1287 / opre.26.4.597 .
Frank Plastry. A négypontos Fermat helymeghatározási problémákat újra megvizsgálták. A régi eredmények új bizonyításai és kiterjesztései // IMA Journal of Management Mathematics. - 2006. - T. 17 , sz. 4 . – S. 387–396 . - doi : 10.1093/imaman/dpl007 .
PG Spanyolország. A háromszög Fermat-pontja // Matematikai folyóirat. - 1996. - T. 69 , sz. 2 . – S. 131–133 . — .
Yehuda Vardi, Cun-Hui Zhang. A többváltozós L 1 -medián és a kapcsolódó adatmélység // Proceedings of the National Academy of Sciences of the United States of America. - 2000. - T. 97 , sz. 4 . — S. 1423–1426 (elektronikus) . - doi : 10.1073/pnas.97.4.1423 .
Alfréd Weber. Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes. — Tübingen: Mohr, 1909.
G. Wesolowsky. A Weber-probléma: történelem és perspektíva // Location Science. - 1993. - T. 1 . – S. 5–23 .
E. Weiszfeld. Sur le point pour lequel la somme des distances de n points donnes est minimum // Tohoku Mathematical Journal . - 1937. - T. 43 . – S. 355–386 .

Átlagos
Matematika	Teljesítmény átlag ( súlyozott ) harmonikus átlag súlyozott geometriai átlag súlyozott Átlagos súlyozott négyzetes közép Átlagos köbméter mozgóátlag Számtani-geometriai átlag Funkció Átlag Kolmogorov jelentése
Geometria	geometriai középpont Barycenter
Valószínűségszámítás és matematikai statisztika	Winsorizált átlag minta átlag Várható érték Középső Divat szórás Csonka átlag Feltételes elvárás
Információs technológia	Medoid k-medián módszer
Tételek	Első átlagtétel Második átlagtétel Egyenlőtlenség a számtani, geometriai és harmonikus átlagról
Egyéb	Elosztóközpont mérőszámai