Geometrisk centrum

Det geometriske centrum af et diskret sæt punkter i det euklidiske rum (i statistiske termer - prøver) er det punkt, hvor summen af afstande til punkter i sættet er minimeret. Det geometriske center generaliserer medianen til en matematisk statistik, der minimerer afstande i en endimensionel dataprøve. Det geometriske centrum afspejler således den centrale tendens i højdimensionelle rum. Begrebet kendes også under navnene 1-median [1] , rumlig median [2] eller Torricelli-punkt [3] .

Det geometriske centrum er en vigtig skiftestimator i statistik [4] , hvor dette koncept er kendt som L 1 - score [5] . At finde det geometriske centrum er også en standardopgave ved placering af objekter , hvor objekternes placering (produktion eller forbrug) modelleres for at minimere transportomkostninger [6]

Et særligt tilfælde af problemet for tre punkter i planet (det vil sige m =3 og n =2 i termerne beskrevet nedenfor) beskrives nogle gange som Fermats problem. Det opstår i konstruktionen af minimale Steiner-træer og blev først stillet som et problem af Pierre de Fermat og løst af Evangelista Torricelli [7] . Løsningen på dette problem er nu kendt som Fermat-punktet i trekanten [8] . Til gengæld kan søgningen efter det geometriske centrum generaliseres til problemet med at minimere summen af vægtede afstande. Dette problem er kendt som Weber-problemet , fordi Alfred Weber diskuterede dette problem i en bog fra 1909 om objektplacering [2] . Nogle kilder bruger i stedet navnet Fermat–Weber problem [9] , men nogle kilder bruger det samme navn for det uvægtede problem [10]

Vesolovsky [11] gav en oversigt over det geometriske centerproblem. Se artiklen af Fekete, Michel og Boyer [12] for en diskussion af generaliseringen af problemet til tilfældet med ikke-diskrete mængder.

Definition

Formelt givet et sæt indeholdende m punkter , hvor alle , er det geometriske centrum defineret som $x_{1},x_{2},\dots ,x_{m}\,$ $x_{i}\in \mathbb {R} ^{n}$

geometrisk centrum

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

Bemærk, at arg min her betyder værdien af argumentet , ved hvilken minimumsummen er nået. Dette er det punkt , hvor summen af alle euklidiske afstande til , er minimal. $y$ $y$ $x_{i}$

Egenskaber

I tilfælde af et endimensionelt rum er medianen det geometriske centrum (hvis der er et lige antal punkter, er det geometriske centrum muligvis ikke unikt). Dette skyldes, at den endimensionelle median minimerer summen af afstandene til punkterne [13] .
Det geometriske centrum er det eneste i alle tilfælde, hvor punkterne ikke er kollineære [14] .
Det geometriske centrum er ækvivariant for euklidisk lighed , translation og rotation [5] [13] . Det betyder, at du får det samme resultat, hvis du finder billedet af centrum under transformationen, eller ved at anvende den samme transformation på alle prøvepunkter og derefter finde det geometriske centrum. Denne egenskab følger af det faktum, at det geometriske centrum kun bestemmes på grundlag af parvise afstande og ikke afhænger af systemet med ortogonale kartesiske koordinater . I modsætning hertil er den komponentvise median for multivariate data under rotation generelt ikke en invariant og afhænger af valget af koordinater [5] .
Det geometriske centrum har et nedbrydningspunkt 0,5 [5] . Det vil sige, at op til halvdelen af prøvedataene kan være upålidelige, men det geometriske centrum af prøven forbliver et stabilt estimat af positionen af de ukorrupte data.

Særlige lejligheder

For 3 ( ikke-kollineære ) punkter , hvis et af hjørnerne i en trekant med toppunkter i disse punkter er 120° eller større, så er det geometriske centrum hjørnets toppunkt. Hvis alle vinkler er mindre end 120°, er det geometriske centrum det punkt inde i trekanten, der danner en vinkel på 120° med ethvert par af trekanthjørner [13] . Dette punkt er kendt som Fermat-punktet i trekanten (hvis tre punkter er kollineære, så falder det geometriske centrum sammen med det punkt, der ligger mellem de to andre).
For 4 koplanære punkter , hvis et af de fire punkter ligger inde i trekanten dannet af de andre tre punkter, vil stedet være det indre punkt. Ellers danner fire punkter en konveks firkant , og skæringspunktet for firkantens diagonaler tjener som det geometriske centrum. Det geometriske centrum af fire koplanære punkter er det samme som det eneste radonpunkt for fire punkter [15] .

Beregning

Selvom konceptet om det geometriske centrum er let at forstå, er dets beregning vanskelig. Tyngdepunktet for en trekant (det vil sige dens massecentrum ), defineret på samme måde som det geometriske centrum som minimering af summen af kvadratiske afstande til hvert punkt, kan opnås ved hjælp af simple formler - dens koordinater er det aritmetiske middelværdi af koordinaterne punkterne. Imidlertid kendes ingen sådan simpel formel for det geometriske centrum. Det er endda blevet vist, at der hverken er en eksplicit formel eller en nøjagtig algoritme, der kun bruger aritmetiske og radix-operationer. Der er således kun tilnærmelser til at løse dette problem [16] .

Det er dog muligt at beregne en tilnærmelse til det geometriske centrum ved hjælp af en iterativ procedure, hvor hvert trin giver en mere nøjagtig tilnærmelse. Procedurer af denne type kan udledes af det faktum, at summen af afstande til prøvepunkter er en konveks funktion , da afstanden til hvert prøvepunkt er en konveks funktion, og summen af konvekse funktioner også er en konveks funktion. Proceduren for at reducere summen af afstande kan således ikke falde ind i det lokale optimum .

En sådan tilgang er Weisfeld-algoritmen ( André Weisfeld ) [17] [18] [19] som er en type iterativ vægtet mindste kvadraters metode med varierende vægte. Denne algoritme sætter et sæt vægte, der er omvendt proportionale med afstandene til den aktuelle tilnærmelse, og beregner en ny tilnærmelse, der er det vægtede gennemsnit af prøvepunkterne i henhold til disse vægte. Det er

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

Metoden konvergerer fra næsten alle startpositioner, men kan mislykkes, hvis tilnærmelsen ender ved et af prøvepunkterne. Algoritmen kan modificeres på en sådan måde, at den vil konvergere for alle udgangspunkter [14] .

Bose, Mageshwari og Morin [10] beskrev en mere sofistikeret optimeringsprocedure til at finde en omtrentlig optimal løsning på et givet problem. Som Ne, Parrilo og Starmfils [20] har vist , kan problemet opfattes som et semibestemt programmeringsproblem .

Cohen, Lee, Miller og Pachoki [21] viste, hvordan man beregner det geometriske centrum til vilkårlig præcision i næsten lineær tid.

Beskrivelse af det geometriske centrum

Hvis punkt y er forskelligt fra alle givne prøvepunkter x j , så er y det geometriske centrum, hvis og kun hvis

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

Dette svarer til

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

som er tæt knyttet til Weisfeld-algoritmen.

Generelt er y et geometrisk centrum, hvis og kun hvis der er vektorer u j sådan

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

hvor for x j ≠ y ,

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

og for x j = y ,

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

En tilsvarende formulering af denne tilstand

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

Generaliseringer

Det geometriske centrum kan generaliseres fra euklidiske rum til generelle Riemann-manifolds (og endda metriske rum ) ved at bruge den samme idé, som bruges til at definere Fréchet-middelværdien på Riemann-manifolds [22] . Lade være en Riemannmanifold med en afstand funktion , lad være vægte, der summer til 1, og lad være observationer fra . Derefter definerer vi det vægtede geometriske centrum (eller vægtede Fréchet-middelværdi) af datapunkterne $M$ $d(\cdot ,\cdot )$ $w_{1},\ldots ,w_{n}$ $n$ $x_{1},\ldots ,x_{n}$ $n$ $M$ $m$

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

Hvis alle vægte er ens, siger vi, hvad der er det geometriske centrum. $m$

Noter

↑ Det mere generelle k -medianproblem spørger om positionen af k - centre, der minimerer summen af afstande fra hvert punkt i sættet til det nærmeste centrum.
↑ 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 .
↑ Spanien, 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 ; Plastry, 2006 . Det konvekse tilfælde blev først bevist af Giovanni Fagnano .
↑ Bajaj, 1986 ; Bajaj, 1988 . Tidligere Cockayne og Melzak Cockayne, Melzak, 1969 beviste, at Steiner-punktet for 5 punkter i flyet ikke kan konstrueres ved hjælp af et kompas og en lige
↑ Weiszfeld, 1937 .
↑ Kuhn, 1973 .
↑ Chandrasekaran, Tamir, 1989 .
↑ Nie, Parrilo, Sturmfels, 2008 .
↑ Cohen, Lee, Miller, Pachocki, Sidford, 2016 .
↑ Fletcher, Venkatasubramanian, Joshi, 2009 .

Litteratur

Chandrajit Bajaj. Beviser geometriske algoritmers uopløselighed: En anvendelse af faktoreringspolynomier // Journal of Symbolic Computation . - 1986. - T. 2 . — S. 99–102 . - doi : 10.1016/S0747-7171(86)80015-3 .
Den algebraiske grad af geometriske optimeringsproblemer // Diskret og beregningsgeometri . - 1988. - T. 3 . — S. 177–191 . - doi : 10.1007/BF02187906 .
Hurtige tilnærmelser for summer af afstande, clustering og Fermat-Weber-problemet // Computational Geometry: Theory and Applications . - 2003. - T. 24 , no. 3 . — S. 135–146 . - doi : 10.1016/S0925-7721(02)00102-5 .
J. Brimberg. Fermat-Weber placeringsproblemet genbesøgt // Matematisk programmering . - 1995. - T. 71 , no. 1 Ser. A. _ — S. 71–76 . - doi : 10.1007/BF01592245 .
R. Chandrasekaran, A. Tamir. Åbne spørgsmål vedrørende Weiszfelds algoritme til Fermat-Weber lokaliseringsproblemet // Matematisk programmering . - 1989. - T. 44 . — S. 293–295 . - doi : 10.1007/BF01587094 .
Dietmar Cieslik. Shortest Connectivity: En introduktion til applikationer i fylogeni . - Springer, 2006. - Vol. 17. - ISBN 9780387235394 .
EJ Cockayne, ZA Melzak. Euklidisk konstruerbarhed i grafminimeringsproblemer // Mathematics Magazine . - 1969. - T. 42 , no. 4 . — S. 206–208 . - doi : 10.2307/2688541 . — .
Michael Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, Aaron Sidford. Geometrisk median i næsten lineær tid // Proc. 48. symposium om teori om computing (STOC 2016). - Association for Computing Machinery , 2016.
Zvi Drezner, Kathrin Klamroth, Anita Schöbel, George O. Wesolowsky. Weber-problemet // Facilitets placering: applikationer og teori . - Springer, Berlin, 2002. - S. 1-36.
HA Eiselt, Vladimir Marianov. Fundamenter for lokalitetsanalyse . - Springer, 2011. - T. 155. - S. 6. - (International Series in Operations Research & Management Science). — ISBN 9781441975720 .
Sandor P. Fekete, Joseph SB Mitchell, Karin Beurer. Om det kontinuerlige Fermat-Weber-problem // Operations Research . - 2005. - T. 53 , no. 1 . — S. 61–76 . - doi : 10.1287/opre.1040.0137 . — arXiv : cs.CG/0310027 .
P. Thomas Fletcher, Suresh Venkatasubramanian, Sarang Joshi. Den geometriske median på Riemann-manifolder med anvendelse på robust atlas-estimering // NeuroImage. - 2009. - T. 45 , no. 1 Suppl . — S. s143–s152 . - doi : 10.1016/j.neuroimage.2008.10.052 . — PMID 19056498 .
JBS Haldane. Bemærk om medianen af en multivariat fordeling // Biometrika. - 1948. - T. 35 , Nr. 3–4 . — S. 414–417 . - doi : 10.1093/biomet/35.3-4.414 .
Jakob Krarup, Steven Vajda. Om Torricellis geometriske løsning på et problem med Fermat // IMA Journal of Mathematics Applied in Business and Industry. - 1997. - T. 8 , no. 3 . — S. 215–224 . - doi : 10.1093/imaman/8.3.215 .
Harold W Kuhn. En note om Fermats problem // Matematisk programmering . - 1973. - T. 4 , no. 1 . — S. 98–107 . - doi : 10.1007/BF01584648 .
Martin Lawera, James R. Thompson. Nogle problemer med estimering og afprøvning i multivariat statistisk proceskontrol // Proceedings of the 38th Conference on the Design of Experiments . - 1993. - T. 93-2. — S. 99–126.
Hendrick P. Lopuhaä, Peter J. Rousseeuw. Nedbrydningspunkter for affine ækvivariante estimatorer af multivariate lokations- og kovariansmatricer // Annals of Statistics . - 1991. - T. 19 , no. 1 . — S. 229–248 . - doi : 10.1214/aos/1176347978 . — .
Jiawang Nie, Pablo A. Parrilo, Bernd Sturmfels. Algoritmer i algebraisk geometri / A. Dickenstein, F.-O. Schreyer, AJ Sommese. - Springer-Verlag, 2008. - T. 146. - S. 117-132. - (IMA Volumes in Mathematics and its Applications).
L. Ostresh. Konvergens af en klasse af iterative metoder til løsning af Weber-lokationsproblem // Operationsforskning . - 1978. - T. 26 , no. 4 . — S. 597–609 . doi : 10.1287 / opre.26.4.597 .
Frank Plastry. Fire-punkts Fermat-placeringsproblemer genbesøgt. Nye beviser og udvidelser af gamle resultater // IMA Journal of Management Mathematics. - 2006. - T. 17 , no. 4 . — S. 387–396 . - doi : 10.1093/imaman/dpl007 .
PG Spanien. The Fermat Point of a Triangle // Mathematics Magazine. - 1996. - T. 69 , no. 2 . — S. 131–133 . — .
Yehuda Vardi, Cun-Hui Zhang. Den multivariate L 1 -median og tilhørende datadybde // Proceedings of the National Academy of Sciences of the United States of America. - 2000. - T. 97 , no. 4 . — S. 1423–1426 (elektronisk) . - doi : 10.1073/pnas.97.4.1423 .
Alfred Weber. Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes. — Tübingen: Mohr, 1909.
G. Wesolowsky. Weber-problemet: Historie og perspektiv //Placeringsvidenskab. - 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 .

Betyde
Matematik	Effektmiddel ( vægtet ) harmonisk middel vægtet geometrisk middelværdi vægtet Gennemsnit vægtet geometriske middelværdi Gennemsnitlig kubik glidende gennemsnit Aritmetisk-geometrisk middelværdi Funktion Middel Kolmogorov mener
Geometri	geometrisk centrum Barycenter
Sandsynlighedsteori og matematisk statistik	Winsoriseret middelværdi prøvegennemsnit Forventet værdi Median Mode standardafvigelse Afkortet middelværdi Betinget forventning
Informationsteknologi	Medoid k-median metode
Sætninger	Første middelsætning Anden middelsætning Ulighed om det aritmetiske, geometriske og harmoniske middelværdi
Andet	Distributionscenter-metrics