Geometriskt centrum

Det geometriska centrumet för en diskret uppsättning punkter i det euklidiska rummet (i statistiska termer - prov) är den punkt där summan av avstånden till uppsättningens punkter minimeras. Det geometriska centret generaliserar medianen till en matematisk statistik som minimerar avstånden i ett endimensionellt dataprov. Således speglar det geometriska centret den centrala trenden i högdimensionella utrymmen. Begreppet är också känt under namnen 1-median [1] , rumslig median [2] , eller Torricelli-punkt [3] .

Det geometriska centret är en viktig förskjutningsuppskattare i statistik [4] , där detta koncept är känt som L 1 -poängen [5] . Att hitta det geometriska centrumet är också en standarduppgift när man placerar föremål , där objektens placering (produktion eller konsumtion) modelleras för att minimera transportkostnaderna [6]

Ett specialfall av problemet för tre punkter i planet (det vill säga m =3 och n =2 i termerna som beskrivs nedan) beskrivs ibland som Fermats problem. Det uppstår i konstruktionen av minimala Steiner-träd och ställdes först som ett problem av Pierre de Fermat och löstes av Evangelista Torricelli [7] . Lösningen på detta problem är nu känd som Fermatpunkten i triangeln [8] . I sin tur kan sökningen efter det geometriska centret generaliseras till problemet med att minimera summan av viktade avstånd. Detta problem är känt som Weber-problemet eftersom Alfred Weber diskuterade detta problem i en bok från 1909 om objektplacering [2] . Vissa källor använder istället namnet Fermat–Weber problem [9] , men vissa källor använder samma namn för det oviktade problemet [10]

Vesolovsky [11] gav en översikt över problemet med geometriska centrum. Se artikeln av Fekete, Michel och Boyer [12] för en diskussion om generaliseringen av problemet till fallet med icke-diskreta mängder.

Definition

Formellt, givet en uppsättning som innehåller m punkter , där alla , definieras det geometriska centrumet som

Observera att här betyder arg min värdet på argumentet vid vilket minimisumman uppnås. Detta är den punkt för vilken summan av alla euklidiska avstånd till , är minimal.

Egenskaper

• För fallet med ett endimensionellt utrymme är medianen det geometriska centret (om det finns ett jämnt antal punkter kan det geometriska centret inte vara unikt). Detta beror på att den endimensionella medianen minimerar summan av avstånden till punkterna [13] .
• Det geometriska centrumet är det enda för alla fall där punkterna inte är kolinjära [14] .
• Det geometriska centret är ekvivariant för euklidisk likhet , translation och rotation [5] [13] . Det betyder att du får samma resultat om du hittar bilden av centrum under transformationen, eller genom att tillämpa samma transformation på alla provpunkter, och sedan hitta det geometriska centrumet. Denna egenskap följer av det faktum att det geometriska centrumet bestäms endast på basis av parvisa avstånd och inte beror på systemet med ortogonala kartesiska koordinater . Däremot är den komponentmässiga medianen för multivariat data under rotation i allmänhet inte en invariant och beror på valet av koordinater [5] .
• Det geometriska centrumet har en nedbrytningspunkt 0,5 [5] . Det vill säga, upp till hälften av provdata kan vara opålitliga, men provets geometriska centrum förblir en stabil uppskattning av positionen för den oförstörda datan.

Särskilda tillfällen

• För 3 ( icke-kollinjära ) punkter , om något av hörnen i en triangel med hörn i dessa punkter är 120° eller större, då är det geometriska centrumet hörnets hörn. Om alla vinklar är mindre än 120° är det geometriska mittpunkten punkten inuti triangeln som gör en vinkel på 120° med valfritt par av triangelhörn [13] . Denna punkt är känd som Fermat-punkten i triangeln (om tre punkter är kolinjära, så sammanfaller det geometriska centrumet med punkten som ligger mellan de andra två).
• För 4 coplanar punkter , om en av de fyra punkterna ligger inuti triangeln som bildas av de andra tre punkterna, kommer platsen att vara den inre punkten. Annars bildar fyra punkter en konvex fyrhörning , och skärningspunkten för fyrhörningens diagonaler fungerar som geometriskt centrum. Det geometriska mitten av fyra punkter i samma plan är detsamma som den enda radonpunkten för fyra punkter [15] .

Beräkning

Även om konceptet med det geometriska centret är lätt att förstå, är dess beräkning svår. Tyngdpunkten för en triangel (det vill säga dess massacentrum ), definierad på samma sätt som det geometriska centrumet som minimering av summan av kvadratavstånden till varje punkt, kan erhållas med enkla formler - dess koordinater är det aritmetiska medelvärdet av koordinaterna för punkterna. Emellertid är ingen sådan enkel formel för det geometriska centrumet känd. Det har till och med visat sig att det varken finns en explicit formel eller en exakt algoritm som endast använder aritmetiska och radixoperationer. Det finns alltså bara approximationer för att lösa detta problem [16] .

Det är dock möjligt att beräkna en approximation till det geometriska centret med hjälp av en iterativ procedur där varje steg ger en mer exakt approximation. Procedurer av denna typ kan härledas från det faktum att summan av avstånden till provpunkter är en konvex funktion , eftersom avståndet till varje provpunkt är en konvex funktion, och summan av konvexa funktioner är också en konvex funktion. Proceduren för att minska summan av avstånd kan således inte falla in i det lokala optimum .

Ett sådant tillvägagångssätt är Weisfeld-algoritmen ( André Weisfeld ) [17] [18] [19] som är en typ av iterativ vägd minsta kvadrat metod med varierande vikter. Denna algoritm ställer in en uppsättning vikter som är omvänt proportionella mot avstånden till den aktuella approximationen, och beräknar en ny approximation som är det viktade medelvärdet av provpunkterna enligt dessa vikter. Det är

Metoden konvergerar från nästan alla initiala positioner, men kan misslyckas om approximationen hamnar i någon av provpunkterna. Algoritmen kan modifieras på ett sådant sätt att den konvergerar för alla startpunkter [14] .

Bose, Mageshwari och Morin [10] beskrev ett mer sofistikerat optimeringsförfarande för att hitta en ungefärlig optimal lösning på ett givet problem. Som Ne, Parrilo och Starmfils [20] har visat kan problemet ses som ett semidefinitivt programmeringsproblem .

Cohen, Lee, Miller och Pachoki [21] visade hur man beräknar det geometriska centret till godtycklig precision i nästan linjär tid.

Beskrivning av det geometriska centret

Om punkt y skiljer sig från alla givna provpunkter x j , då är y det geometriska centrum om och endast om

Detta motsvarar

som är nära besläktad med Weisfeld-algoritmen.

I allmänhet är y ett geometriskt centrum om och endast om det finns vektorer u j sådana

där för x j ≠ y ,

och för x j = y ,

En likvärdig formulering av detta tillstånd

Generaliseringar

Det geometriska centret kan generaliseras från euklidiska utrymmen till allmänna riemannska grenrör (och även metriska utrymmen ) med samma idé som används för att definiera Fréchet-medelvärdet på riemannska grenrör [22] . Låta vara en Riemann grenrör med en avstånd funktion , Låt vara vikter som summan till 1, och låt vara observationer från . Sedan definierar vi det viktade geometriska centrumet (eller det viktade Fréchet-medelvärdet) för datapunkterna

Om alla vikter är lika, säger vi vad som är det geometriska centrumet.

Anteckningar

1. ↑ Det mer generella k -medianproblemet frågar om positionen för k -centra som minimerar summan av avstånden från varje punkt i mängden till närmaste centrum.
2. ↑ 1 2 Drezner, Klamroth, Schöbel, Wesolowsky, 2002 .
3. ↑ Cieslik, 2006 .
4. ↑ Lawera, Thompson, 1993 .
5. ↑ 1 2 3 4 Lopuhaä, Rousseeuw, 1991 .
6. ↑ Eiselt, Marianov, 2011 .
7. ↑ Krarup, Vajda, 1997 .
8. ↑ Spanien, 1996 .
9. ↑ Brimberg, 1995 .
10. ↑ 1 2 Bose, Maheshwari, Morin, 2003 .
11. ↑ Wesolowsky, 1993 .
12. ↑ Fekete, Mitchell, Beurer, 2005 .
13. ↑ 1 2 3 Haldane, 1948 .
14. ↑ 12 Vardi, Zhang, 2000 .
15. ↑ Cieslik, 2006 ; Plastry, 2006 . Det konvexa fallet bevisades först av Giovanni Fagnano .
16. ↑ Bajaj, 1986 ; Bajaj, 1988 . Tidigare Cockayne och Melzak Cockayne, Melzak, 1969 bevisade att Steiner-punkten för 5 punkter i planet inte kan konstrueras med en kompass och rätlina
17. ↑ Weiszfeld, 1937 .
18. ↑ Kuhn, 1973 .
19. ↑ Chandrasekaran, Tamir, 1989 .
20. ↑ Nie, Parrilo, Sturmfels, 2008 .
21. ↑ Cohen, Lee, Miller, Pachocki, Sidford, 2016 .
22. ↑ Fletcher, Venkatasubramanian, Joshi, 2009 .

Litteratur

• Chandrajit Bajaj. Bevisa geometriska algoritmers olöslighet: En tillämpning av faktoreringspolynom // Journal of Symbolic Computation . - 1986. - T. 2 . — S. 99–102 . - doi : 10.1016/S0747-7171(86)80015-3 .
• Den algebraiska graden av geometriska optimeringsproblem  // Diskret och beräkningsgeometri . - 1988. - T. 3 . — S. 177–191 . - doi : 10.1007/BF02187906 .
• Snabba approximationer för summor av avstånd, klustring och Fermat–Weber-problemet  // Computational Geometry: Theory and Applications . - 2003. - T. 24 , nr. 3 . — S. 135–146 . - doi : 10.1016/S0925-7721(02)00102-5 .
• J. Brimberg. Lokaliseringsproblemet från Fermat–Weber återbesökt // Matematisk programmering . - 1995. - T. 71 , nr. 1 Ser. A. _ — S. 71–76 . - doi : 10.1007/BF01592245 .
• R. Chandrasekaran, A. Tamir. Öppna frågor angående Weiszfelds algoritm för Fermat-Weber lokaliseringsproblem  // Mathematical Programmering . - 1989. - T. 44 . — S. 293–295 . - doi : 10.1007/BF01587094 .
• Dietmar Cieslik. Shortest Connectivity: An Introduction to Applications in Phylogeny . - Springer, 2006. - Vol. 17. - ISBN 9780387235394 .
• EJ Cockayne, ZA Melzak. Euklidisk konstruktionsbarhet i grafminimeringsproblem  // Mathematics Magazine . - 1969. - T. 42 , nr. 4 . — S. 206–208 . - doi : 10.2307/2688541 . — .
• Michael Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, Aaron Sidford. Geometrisk median i nästan linjär tid // Proc. 48:e symposiet om datorteori (STOC 2016). - Association for Computing Machinery , 2016.
• Zvi Drezner, Kathrin Klamroth, Anita Schöbel, George O. Wesolowsky. Weberproblemet // Anläggningens plats: Tillämpningar och teori . - Springer, Berlin, 2002. - S. 1-36.
• HA Eiselt, Vladimir Marianov. Grunderna för platsanalys . - Springer, 2011. - T. 155. - P. 6. - (International Series in Operations Research & Management Science). — ISBN 9781441975720 .
• Sandor P. Fekete, Joseph SB Mitchell, Karin Beurer. Om det kontinuerliga Fermat-Weber-problemet // Operations Research . - 2005. - T. 53 , nr. 1 . — S. 61–76 . - doi : 10.1287/opre.1040.0137 . — arXiv : cs.CG/0310027 .
• P. Thomas Fletcher, Suresh Venkatasubramanian, Sarang Joshi. Den geometriska medianen på Riemannska grenrör med tillämpning på robust atlasberäkning // NeuroImage. - 2009. - T. 45 , nr. 1 Suppl . — S. s143–s152 . - doi : 10.1016/j.neuroimage.2008.10.052 . — PMID 19056498 .
• JBS Haldane. Notering om medianen för en multivariat distribution // Biometrika. - 1948. - T. 35 , nr. 3–4 . — S. 414–417 . - doi : 10.1093/biomet/35.3-4.414 .
• Jakob Krarup, Steven Vajda. Om Torricellis geometriska lösning på ett problem med Fermat // IMA Journal of Mathematics Applied in Business and Industry. - 1997. - T. 8 , nr. 3 . — S. 215–224 . - doi : 10.1093/imaman/8.3.215 .
• Harold W Kuhn. En anteckning om Fermats problem // Matematisk programmering . - 1973. - T. 4 , nr. 1 . — S. 98–107 . - doi : 10.1007/BF01584648 .
• Martin Lawera, James R. Thompson. Vissa problem med uppskattning och testning i multivariat statistisk processkontroll // Proceedings of the 38th Conference on the Design of Experiment . - 1993. - T. 93-2. — S. 99–126.
• Hendrick P. Lopuhaä, Peter J. Rousseeuw. Nedbrytningspunkter för affina ekvivarianta estimatorer av multivariat läge och kovariansmatriser  // Annals of Statistics . - 1991. - T. 19 , nr. 1 . — S. 229–248 . - doi : 10.1214/aos/1176347978 . — .
• Jiawang Nie, Pablo A. Parrilo, Bernd Sturmfels. Algorithms in Algebraic Geometry / A. Dickenstein, F.-O. Schreyer, AJ Sommese. - Springer-Verlag, 2008. - T. 146. - S. 117-132. - (IMA volymer i matematik och dess tillämpningar).
• L. Ostresh. Konvergens av en klass av iterativa metoder för att lösa Webers lokaliseringsproblem // Operations Research . - 1978. - T. 26 , nr. 4 . — S. 597–609 . doi : 10.1287 / opre.26.4.597 .
• Frank Plastry. Fyrpunktsproblem med Fermats läge återupptogs. Nya bevis och tillägg av gamla resultat  // IMA Journal of Management Mathematics. - 2006. - T. 17 , nr. 4 . — S. 387–396 . - doi : 10.1093/imaman/dpl007 .
• PG Spanien. The Fermat Point of a Triangle  // Mathematics Magazine. - 1996. - T. 69 , nr. 2 . — S. 131–133 . — .
• Yehuda Vardi, Cun-Hui Zhang. Den multivariata L 1 -medianen och tillhörande datadjup // Proceedings of the National Academy of Sciences of the United States of America. - 2000. - T. 97 , nr. 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. Weberproblemet: Historia och perspektiv  // Platsvetenskap. - 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 .