Geometrinen keskusta

Diskreetin pistejoukon geometrinen keskipiste euklidisessa avaruudessa (tilastollisesti - näytteet) on piste, jossa etäisyyksien summa joukon pisteisiin minimoidaan. Geometrinen keskus yleistää mediaanin matemaattiseksi tilastoksi, joka minimoi etäisyydet yksiulotteisessa tietonäytteessä. Siten geometrinen keskipiste heijastaa keskeistä suuntausta suuriulotteisissa tiloissa. Käsite tunnetaan myös nimillä 1-mediaani [1] , spatiaalinen mediaani [2] tai Torricelli-piste [3] .

Geometrinen keskipiste on tärkeä siirtymäestimaattori tilastoissa [4] , jossa tämä käsite tunnetaan nimellä L 1 -pistemäärä [5] . Geometrisen keskipisteen löytäminen on myös vakiotehtävä esineitä sijoitettaessa, jolloin objektien sijainti (tuotanto tai kulutus) mallinnetaan kuljetuskustannusten minimoimiseksi [6]

Kolmen tason pisteen ongelman erikoistapaus (eli m =3 ja n =2 alla kuvatuilla termeillä) kuvataan joskus Fermatin ongelmaksi. Se syntyy minimaalisten Steiner-puiden rakentamisessa, ja Pierre de Fermat esitti sen ongelmaksi ja sen ratkaisi Evangelista Torricelli [7] . Tämän ongelman ratkaisu tunnetaan nyt kolmion Fermat-pisteenä [8] . Geometrisen keskipisteen etsiminen puolestaan voidaan yleistää painotettujen etäisyyksien summan minimoimisen ongelmaksi . Tämä ongelma tunnetaan Weber-ongelmana , koska Alfred Weber käsitteli tätä ongelmaa vuoden 1909 kirjassa objektien sijoittamisesta [2] . Jotkut lähteet käyttävät sen sijaan nimeä Fermat–Weber-ongelma [9] , mutta jotkut lähteet käyttävät samaa nimeä painottamattomalle ongelmalle [10]

Vesolovski [11] teki katsauksen geometrisen keskustan ongelmasta. Katso Feketen, Michelin ja Boyerin artikkeli [12] , jossa käsitellään ongelman yleistämistä ei-diskreettien joukkojen tapaukseen.

Määritelmä

Muodollisesti annettuna joukko, joka sisältää m pistettä , jossa kaikki , geometrinen keskusta määritellään seuraavasti $x_{1},x_{2},\dots ,x_{m}\,$ $x_{i}\in \mathbb {R} ^{n}$

geometrinen keskusta

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

Huomaa, että tässä arg min tarkoittaa argumentin arvoa, jolla minimisumma saavutetaan. Tämä on piste , jolle kaikkien euklidisten etäisyyksien summa on minimaalinen. $y$ $y$ $x_{i}$

Ominaisuudet

Yksiulotteisen avaruuden tapauksessa mediaani on geometrinen keskipiste (jos pisteitä on parillinen määrä, geometrinen keskipiste ei välttämättä ole ainutlaatuinen). Tämä johtuu siitä, että yksiulotteinen mediaani minimoi pisteiden etäisyyksien summan [13] .
Geometrinen keskipiste on ainoa kaikissa tapauksissa, joissa pisteet eivät ole kollineaarisia [14] .
Geometrinen keskipiste on ekvivariantti euklidiselle samanlaiselle , translaatiolle ja rotaatiolle [5] [13] . Tämä tarkoittaa, että saat saman tuloksen, jos löydät kuvan keskipisteestä muunnoksen aikana tai käyttämällä samaa muunnosa kaikkiin näytepisteisiin ja etsimällä sitten geometrisen keskipisteen. Tämä ominaisuus johtuu siitä, että geometrinen keskipiste määritetään vain parittaisten etäisyyksien perusteella, eikä se riipu suorakulmaisten ortogonaalisten koordinaattien järjestelmästä . Sitä vastoin monimuuttujatietojen komponenttikohtainen mediaani kierron aikana ei yleensä ole invariantti ja riippuu koordinaattien valinnasta [5] .
Geometrisellä keskipisteellä on murtumispiste 0,5 [5] . Toisin sanoen jopa puolet näytetiedoista voi olla epäluotettavia, mutta näytteen geometrinen keskipiste pysyy vakaana arviona vahingoittumattoman datan sijainnista.

Erikoistilaisuudet

Jos 3 ( ei-kollineaarista ) pistettä varten jokin kolmion kulmista, jonka kärjet ovat näissä pisteissä, on 120° tai suurempi, geometrinen keskipiste on kulman kärki. Jos kaikki kulmat ovat alle 120°, geometrinen keskipiste on kolmion sisällä oleva piste, joka muodostaa 120° kulman minkä tahansa kolmion kärkiparin kanssa [13] . Tämä piste tunnetaan kolmion Fermat-pisteenä (jos kolme pistettä ovat kollineaarisia, niin geometrinen keskipiste osuu yhteen kahden muun välissä olevan pisteen kanssa).
Jos yksi neljästä pisteestä on neljän samantasoisen pisteen kohdalla, on kolmen muun pisteen muodostaman kolmion sisällä, locus on tuo sisäpiste. Muuten neljä pistettä muodostavat kuperan nelikulmion ja nelikulmion lävistäjien leikkauspiste toimii geometrisena keskipisteenä. Neljän samantasoisen pisteen geometrinen keskipiste on sama kuin neljän pisteen ainoa radonpiste [15] .

Laskenta

Vaikka geometrisen keskuksen käsite on helppo ymmärtää, sen laskeminen on vaikeaa. Kolmion painopiste (eli sen massakeskipiste ), joka määritellään samalla tavalla kuin geometrinen keskipiste minimoimaan kunkin pisteen neliöetäisyyksien summa , voidaan saada yksinkertaisilla kaavoilla - sen koordinaatit ovat kolmion koordinaattien aritmeettinen keskiarvo. pisteitä. Tällaista yksinkertaista geometrisen keskuksen kaavaa ei kuitenkaan tunneta. On jopa osoitettu, että ei ole olemassa eksplisiittistä kaavaa eikä tarkkaa algoritmia, joka käyttää vain aritmeettisia ja kantalukuoperaatioita. Tämän ongelman ratkaisemiseksi on siis vain likiarvoja [16] .

On kuitenkin mahdollista laskea approksimaatio geometriseen keskipisteeseen käyttämällä iteratiivista menettelyä, jossa jokainen vaihe antaa tarkemman approksimation. Tämän tyyppiset proseduurit voidaan johtaa siitä, että näytepisteiden etäisyyksien summa on konveksi funktio , koska etäisyys kuhunkin näytepisteeseen on konveksi funktio ja konveksien funktioiden summa on myös konveksi funktio. Näin ollen menettely etäisyyksien summan pienentämiseksi ei voi pudota paikalliseen optimiin .

Yksi tällainen lähestymistapa on Weisfeld-algoritmi ( André Weisfeld ) [17] [18] [19] , joka on iteratiivisen painotetun pienimmän neliösumman menetelmä , jonka painot vaihtelevat. Tämä algoritmi asettaa joukon painoja, jotka ovat kääntäen verrannollisia etäisyyksiin nykyiseen approksimaatioon, ja laskee uuden likiarvon, joka on näiden painojen mukaan näytepisteiden painotettu keskiarvo. Tuo on

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

Menetelmä konvergoi lähes kaikista lähtökohdista, mutta voi epäonnistua, jos approksimaatio päätyy johonkin näytepisteeseen. Algoritmia voidaan muokata siten, että se konvergoi kaikissa lähtöpisteissä [14] .

Bose, Mageshwari ja Morin [10] kuvasivat kehittyneemmän optimointimenettelyn likimääräisen optimaalisen ratkaisun löytämiseksi tiettyyn ongelmaan. Kuten Ne, Parrilo ja Starmfils [20] ovat osoittaneet , ongelmaa voidaan pitää puolimääräisenä ohjelmointiongelmana .

Cohen, Lee, Miller ja Pachoki [21] osoittivat kuinka geometrinen keskipiste lasketaan mielivaltaiseen tarkkuuteen lähes lineaarisessa ajassa.

Geometrisen keskuksen kuvaus

Jos piste y on eri kuin kaikista annetuista näytepisteistä x j , niin y on geometrinen keskipiste jos ja vain jos

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

Tämä vastaa

\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),

joka liittyy läheisesti Weisfeld-algoritmiin.

Yleisesti ottaen y on geometrinen keskus, jos ja vain jos on vektoreita u j , jotka ovat sellaisia

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

missä x j ≠ y ,

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

ja x j = y ,

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

Tämän ehdon vastaava muotoilu

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

Yleistykset

Geometrinen keskus voidaan yleistää euklidisista avaruksista yleisiin Riemannin monisteisiin (ja jopa metrisiin avaruuksiin ) käyttämällä samaa ideaa, jota käytetään Fréchet'n keskiarvon määrittämiseen Riemannin monistoon [22] . Antaa olla Riemannin monimuotoinen etäisyysfunktio , Antaa olla painoja, joiden summa on 1, ja antaa olla havaintoja . Sitten määritetään datapisteiden painotettu geometrinen keskipiste (tai painotettu Fréchet-keskiarvo). $M$ $d(\cdot ,\cdot )$ $w_{1},\ldots ,w_{n}$ $n$ $x_{1},\ldots,x_{n}$ $n$ $M$ $m$

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

Jos kaikki painot ovat yhtä suuret, sanotaan mikä on geometrinen keskipiste. $m$

Muistiinpanot

↑ Yleisempi k -mediaaniongelma kysyy k keskipisteen paikkaa minimoiden etäisyyksien summan joukon jokaisesta pisteestä lähimpään keskustaan.
↑ 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 .
↑ Espanja, 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 . Kupera tapaus todisti ensimmäisenä Giovanni Fagnano .
↑ Bajaj, 1986 ; Bajaj, 1988 . Aikaisemmin Cockayne ja Melzak Cockayne, Melzak, 1969 osoittivat, että Steiner-pistettä 5 tason pisteelle ei voida rakentaa kompassin ja suoraviivan avulla.
↑ Weiszfeld, 1937 .
↑ Kuhn, 1973 .
↑ Chandrasekaran, Tamir, 1989 .
↑ Nie, Parrilo, Sturmfels, 2008 .
↑ Cohen, Lee, Miller, Pachocki, Sidford, 2016 .
↑ Fletcher, Venkatasubramanian, Joshi, 2009 .

Kirjallisuus

Chandrajit Bajaj. Geometristen algoritmien ratkaisemattomuuden todistaminen: tekijäpolynomien sovellus // Journal of Symbolic Computation . - 1986. - T. 2 . — S. 99–102 . - doi : 10.1016/S0747-7171(86)80015-3 .
Geometristen optimointiongelmien algebrallinen aste // Diskreetti ja laskennallinen geometria . - 1988. - T. 3 . — S. 177–191 . - doi : 10.1007/BF02187906 .
Nopeat approksimaatiot etäisyyksien, klusteroinnin ja Fermat-Weber-ongelman summille // Computational Geometry: Theory and Applications . - 2003. - T. 24 , no. 3 . — S. 135–146 . - doi : 10.1016/S0925-7721(02)00102-5 .
J. Brimberg. Fermat-Weberin sijaintiongelma uudelleen // Matemaattinen ohjelmointi . - 1995. - T. 71 , no. 1 Ser. A. _ - S. 71-76 . - doi : 10.1007/BF01592245 .
R. Chandrasekaran, A. Tamir. Avoimet kysymykset Weiszfeldin algoritmista Fermat-Weber-paikannusongelmaan // Matemaattinen ohjelmointi . - 1989. - T. 44 . — S. 293–295 . - doi : 10.1007/BF01587094 .
Dietmar Cieslik. Lyhyin liitettävyys: Johdatus filogenian sovelluksiin . - Springer, 2006. - Vol. 17. - ISBN 9780387235394 .
EJ Cockayne, ZA Melzak. Euklidinen rakennettavuus graafin minimointiongelmissa // 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. Geometrinen mediaani lähes lineaarisessa ajassa // Proc. 48th Symposium on Theory of Computing (STOC 2016). - Computing Machinery Association , 2016.
Zvi Drezner, Kathrin Klamroth, Anita Schöbel, George O. Wesolowsky. Weber-ongelma // Laitoksen sijainti: Sovellukset ja teoria . - Springer, Berliini, 2002. - S. 1-36.
HA Eiselt, Vladimir Marianov. Sijaintianalyysin perusteet . - Springer, 2011. - T. 155. - P. 6. - (International Series in Operations Research & Management Science). — ISBN 9781441975720 .
Sandor P. Fekete, Joseph SB Mitchell, Karin Beurer. Jatkuvasta Fermat-Weber-ongelmasta // 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. Geometrinen mediaani Riemannin monistimessa sovelluksella vankalle atlasestimaatiolle // NeuroImage. - 2009. - T. 45 , no. 1 Suppl . — S. s143–s152 . - doi : 10.1016/j.neuroimage.2008.10.052 . — PMID 19056498 .
JBS Haldane. Huomautus monimuuttujajakauman mediaanista // Biometrika. - 1948. - T. 35 , no. 3-4 . — S. 414–417 . - doi : 10.1093/biomet/35.3-4.414 .
Jakob Krarup, Steven Vajda. Torricellin geometrisestä ratkaisusta Fermatin ongelmaan // 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. Huomautus Fermatin ongelmasta // Matemaattinen ohjelmointi . - 1973. - T. 4 , no. 1 . — S. 98–107 . - doi : 10.1007/BF01584648 .
Martin Lawera, James R. Thompson. Eräitä estimointi- ja testausongelmia monimuuttujatilastollisen prosessin ohjauksessa // Proceedings of the 38th Conference on the Design of Experiments . - 1993. - T. 93-2. — s. 99–126.
Hendrick P. Lopuhaä, Peter J. Rousseeuw. Monimuuttujien sijainti- ja kovarianssimatriisien affiinisten ekvivalenttiestimaattien jaottelupisteet // Annals of Statistics . - 1991. - T. 19 , no. 1 . — S. 229–248 . - doi : 10.1214/aos/1176347978 . — .
Jiawang Nie, Pablo A. Parrilo, Bernd Sturmfels. Algoritmit algebrallisessa geometriassa / A. Dickenstein, F.-O. Schreyer, AJ Sommese. - Springer-Verlag, 2008. - T. 146. - S. 117-132. - (IMA-määrät matematiikassa ja sen sovelluksissa).
L. Ostresh. Weber-paikannusongelman ratkaisemiseen tarkoitettujen iteratiivisten menetelmien luokan konvergenssi // Operaatiotutkimus . - 1978. - T. 26 , no. 4 . — S. 597–609 . doi : 10.1287 / opre.26.4.597 .
Frank Plastry. Neljän pisteen Fermat-paikannusongelmat käsiteltiin uudelleen. Uusia todisteita ja vanhojen tulosten laajennuksia // IMA Journal of Management Mathematics. - 2006. - T. 17 , no. 4 . — S. 387–396 . - doi : 10.1093/imaman/dpl007 .
PG Espanja. Kolmion Fermat-piste // Mathematics Magazine. - 1996. - T. 69 , no. 2 . — S. 131–133 . — .
Yehuda Vardi, Cun-Hui Zhang. Monimuuttuja L 1 -mediaani ja siihen liittyvä datasyvyys // Proceedings of the National Academy of Sciences of the United States of America. - 2000. - T. 97 , no. 4 . — S. 1423–1426 (sähköinen) . - doi : 10.1073/pnas.97.4.1423 .
Alfred Weber. Yber den Standort der Industrien, Erster Teil: Reine Theorie des Standortes. - Tübingen: Mohr, 1909.
G. Wesolowsky. Weber-ongelma: historia ja näkökulma // 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 .

Tarkoittaa
Matematiikka	Tehon keskiarvo ( painotettu ) harmoninen keskiarvo painotettu geometrinen keskiarvo painotettu Keskiverto painotettu juuri tarkoittaa neliötä Keskimääräinen kuutio liukuva keskiarvo Aritmeettis-geometrinen keskiarvo Toiminto Keskiarvo Kolmogorov tarkoittaa
Geometria	geometrinen keskusta Barycenter
Todennäköisyysteoria ja matemaattinen tilasto	Winsorized keskiarvo näytteen keskiarvo Odotettu arvo Mediaani Muoti keskihajonta Katkaistu keskiarvo Ehdollinen odotus
Tietotekniikka	Medoid k-mediaani menetelmä
Lauseet	Ensimmäinen keskiarvolause Toinen keskiarvolause Aritmeettisen, geometrisen ja harmonisen keskiarvon epäyhtälö
Muut	Jakelukeskuksen mittarit