Centru geometric

Centrul geometric al unei mulțimi discrete de puncte din spațiul euclidian (în termeni statistici - eșantioane) este punctul în care suma distanțelor până la punctele mulțimii este minimizată. Centrul geometric generalizează mediana la o statistică matematică care minimizează distanțele într-un eșantion de date unidimensionale. Astfel, centrul geometric reflectă tendința centrală în spațiile cu dimensiuni mari. Conceptul este cunoscut și sub numele de 1-mediană [1] , mediană spațială [2] , sau punct Torricelli [3] .

Centrul geometric este un estimator de deplasare important în statistică [4] , în care acest concept este cunoscut sub numele de scor L 1 [5] . Găsirea centrului geometric este, de asemenea, o sarcină standard la plasarea obiectelor , unde locația obiectelor (producție sau consum) este modelată pentru a minimiza costurile de transport [6]

Un caz special al problemei pentru trei puncte din plan (adică m =3 și n =2 în termenii descriși mai jos) este uneori descris ca problema lui Fermat. Ea apare în construcția arborilor Steiner minimali și a fost mai întâi pusă ca o problemă de Pierre de Fermat și rezolvată de Evangelista Torricelli [7] . Soluția la această problemă este acum cunoscută ca punctul Fermat al triunghiului [8] . La rândul său, căutarea centrului geometric poate fi generalizată la problema minimizării sumei distanțelor ponderate . Această problemă este cunoscută ca problema Weber deoarece Alfred Weber a discutat această problemă într-o carte din 1909 despre plasarea obiectelor [2] . Unele surse folosesc în schimb denumirea de problemă Fermat–Weber [9] , dar unele surse folosesc același nume pentru problema neponderată [10]

Vesolovsky [11] a dat un studiu al problemei centrului geometric. Vezi articolul lui Fekete, Michel și Boyer [12] pentru o discuție despre generalizarea problemei în cazul mulțimilor nediscrete.

Definiție

Formal, având în vedere o mulțime care conține m puncte , unde toate , centrul geometric este definit ca

Rețineți că aici arg min înseamnă valoarea argumentului la care este atinsă suma minimă. Acesta este punctul pentru care suma tuturor distanțelor euclidiene la , este minimă.

Proprietăți

• În cazul unui spațiu unidimensional, mediana este centrul geometric (dacă există un număr par de puncte, centrul geometric poate să nu fie unic). Acest lucru se datorează faptului că mediana unidimensională minimizează suma distanțelor până la puncte [13] .
• Centrul geometric este singurul pentru toate cazurile în care punctele nu sunt coliniare [14] .
• Centrul geometric este echivariant pentru similitudine euclidiană , translație și rotație [5] [13] . Aceasta înseamnă că veți obține același rezultat dacă găsiți imaginea centrului în timpul transformării sau aplicând aceeași transformare tuturor punctelor de probă și apoi găsiți centrul geometric. Această proprietate rezultă din faptul că centrul geometric este determinat numai pe baza distanțelor pe perechi și nu depinde de sistemul de coordonate carteziene ortogonale . În schimb, mediana componentelor pentru datele multivariate în timpul rotației nu este, în general, un invariant și depinde de alegerea coordonatelor [5] .
• Centrul geometric are un punct de defalcare 0,5 [5] . Adică, până la jumătate din datele eșantionului pot fi nesigure, dar centrul geometric al eșantionului rămâne o estimare stabilă a poziției datelor necorupte.

Ocazii speciale

• Pentru 3 puncte ( necoliniare ) , dacă oricare dintre colțurile unui triunghi cu vârfuri în acele puncte este de 120° sau mai mare, atunci centrul geometric este vârful acelui colț. Dacă toate unghiurile sunt mai mici de 120°, centrul geometric este punctul din interiorul triunghiului care formează un unghi de 120° cu orice pereche de vârfuri triunghiulare [13] . Acest punct este cunoscut sub numele de punctul Fermat al triunghiului (dacă trei puncte sunt coliniare, atunci centrul geometric coincide cu punctul care se află între celelalte două).
• Pentru 4 puncte coplanare , dacă unul dintre cele patru puncte se află în interiorul triunghiului format de celelalte trei puncte, locul va fi acel punct interior. În caz contrar, patru puncte formează un patrulater convex , iar punctul de intersecție al diagonalelor patrulaterului servește ca centru geometric. Centrul geometric al patru puncte coplanare este același cu singurul punct Radon pentru patru puncte [15] .

Calcul

Deși conceptul de centru geometric este ușor de înțeles, calculul său este dificil. Centroidul unui triunghi (adică centrul său de masă ), definit în mod similar cu centrul geometric ca minimizând suma distanțelor pătrate până la fiecare punct, poate fi obținut folosind formule simple - coordonatele sale sunt media aritmetică a coordonatelor lui punctele. Cu toate acestea, nu se cunoaște o astfel de formulă simplă pentru centrul geometric. S-a demonstrat chiar că nu există nici o formulă explicită , nici un algoritm exact care să utilizeze doar operații aritmetice și radix. Astfel, există doar aproximări pentru rezolvarea acestei probleme [16] .

Cu toate acestea, este posibil să se calculeze o aproximare a centrului geometric folosind o procedură iterativă în care fiecare pas oferă o aproximare mai precisă. Procedurile de acest tip pot fi derivate din faptul că suma distanțelor până la punctele de eșantion este o funcție convexă , deoarece distanța până la fiecare punct de eșantion este o funcție convexă, iar suma funcțiilor convexe este, de asemenea, o funcție convexă. Astfel, procedura de reducere a sumei distanțelor nu se poate încadra în optimul local .

O astfel de abordare este algoritmul Weisfeld ( André Weisfeld ) [17] [18] [19] care este un tip de metodă iterativă a celor mai mici pătrate ponderate cu ponderi diferite. Acest algoritm stabilește un set de greutăți care sunt invers proporționale cu distanțele față de aproximarea curentă și calculează o nouă aproximare care este media ponderată a punctelor eșantionului în funcție de aceste greutăți. Acesta este

Metoda converge din aproape toate pozițiile inițiale, dar poate eșua dacă aproximarea ajunge la unul dintre punctele eșantionului. Algoritmul poate fi modificat în așa fel încât să convergă pentru toate punctele de plecare [14] .

Bose, Mageshwari și Morin [10] au descris o procedură de optimizare mai sofisticată pentru găsirea unei soluții optime aproximative pentru o problemă dată. După cum au arătat Ne, Parrilo și Starmfils [20] , problema poate fi gândită ca o problemă de programare semidefinită .

Cohen, Lee, Miller și Pachoki [21] au arătat cum se calculează centrul geometric la o precizie arbitrară în timp aproape liniar.

Descrierea centrului geometric

Dacă punctul y este diferit de toate punctele eșantion date x j , atunci y este centrul geometric dacă și numai dacă

Aceasta este echivalentă cu

care este strâns legat de algoritmul Weisfeld.

În general, y este un centru geometric dacă și numai dacă există vectori u j astfel încât

unde pentru x j ≠ y ,

iar pentru x j = y ,

O formulare echivalentă a acestei afecțiuni

Generalizări

Centrul geometric poate fi generalizat de la spații euclidiene la varietăți riemanniene generale (și chiar spații metrice ) folosind aceeași idee care este folosită pentru a defini media Fréchet pe varietățile riemanniene [22] . Fie o varietate Riemanniană cu o funcție de distanță , fie ponderi care însumează 1 și fie observații din . Apoi definim centrul geometric ponderat (sau media ponderată Fréchet) al punctelor de date

Dacă toate greutățile sunt egale, spunem care este centrul geometric.

Note

1. ↑ Problema k -mediană mai generală se întreabă despre poziția k centrelor minimizând suma distanțelor de la fiecare punct al mulțimii la cel mai apropiat centru.
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. ↑ Spania, 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 ; Plasterie, 2006 . Cazul convex a fost dovedit pentru prima dată de Giovanni Fagnano .
16. ↑ Bajaj, 1986 ; Bajaj, 1988 . Anterior Cockayne și Melzak Cockayne, Melzak, 1969 au demonstrat că punctul Steiner pentru 5 puncte din plan nu poate fi construit folosind o busolă și o linie dreaptă.
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 .

Literatură

• Chandrajit Bajaj. Demonstrarea nesolubilității algoritmilor geometrici: O aplicație a polinoamelor factoring // Journal of Symbolic Computation . - 1986. - T. 2 . — S. 99–102 . - doi : 10.1016/S0747-7171(86)80015-3 .
• Gradul algebric al problemelor de optimizare geometrică  // Geometrie discretă și computațională . - 1988. - T. 3 . — S. 177–191 . - doi : 10.1007/BF02187906 .
• Aproximații rapide pentru sumele distanțelor, clustering și problema Fermat–Weber  // Computational Geometry: Theory and Applications . - 2003. - T. 24 , nr. 3 . — S. 135–146 . - doi : 10.1016/S0925-7721(02)00102-5 .
• J. Brimberg. Problema locației Fermat–Weber revizuită // Programare matematică . - 1995. - T. 71 , nr. 1 Ser. A. _ — S. 71–76 . - doi : 10.1007/BF01592245 .
• R. Chandrasekaran, A. Tamir. Întrebări deschise referitoare la algoritmul lui Weiszfeld pentru problema locației Fermat-Weber  // Programare matematică . - 1989. - T. 44 . — S. 293–295 . - doi : 10.1007/BF01587094 .
• Dietmar Cieslik. Cea mai scurtă conectivitate: o introducere în aplicațiile în filogenie . - Springer, 2006. - Vol. 17. - ISBN 9780387235394 .
• EJ Cockayne, ZA Melzak. Construcbilitatea euclidiană în probleme de minimizare a graficelor  // Revista de matematică . - 1969. - T. 42 , nr. 4 . — S. 206–208 . - doi : 10.2307/2688541 . — .
• Michael Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, Aaron Sidford. Mediană geometrică în timp aproape liniar // Proc. Cel de -al 48-lea Simpozion de Teoria Calculului (STOC 2016). - Asociația pentru Mașini de Calcul , 2016.
• Zvi Drezner, Kathrin Klamroth, Anita Schöbel, George O. Wesolowsky. Problema Weber // Locația instalației: aplicații și teorie . - Springer, Berlin, 2002. - S. 1-36.
• HA Eiselt, Vladimir Marianov. Bazele analizei locației . - Springer, 2011. - T. 155. - P. 6. - (International Series in Operations Research & Management Science). — ISBN 9781441975720 .
• Sandor P. Fekete, Joseph SB Mitchell, Karin Beurer. Despre problema continuă Fermat-Weber // Cercetare operațională . - 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. Mediana geometrică pe varietățile Riemanniene cu aplicare la estimarea robustă a atlasului // NeuroImage. - 2009. - T. 45 , nr. 1 Supl . — S. s143–s152 . - doi : 10.1016/j.neuroimage.2008.10.052 . — PMID 19056498 .
• JBS Haldane. Notă despre mediana unei distribuții multivariate // Biometrika. - 1948. - T. 35 , nr. 3–4 . — S. 414–417 . - doi : 10.1093/biomet/35.3-4.414 .
• Jakob Krarup, Steven Vajda. Despre soluția geometrică a lui Torricelli la o problemă a lui 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. O notă despre problema lui Fermat // Programare matematică . - 1973. - T. 4 , nr. 1 . — S. 98–107 . - doi : 10.1007/BF01584648 .
• Martin Lawera, James R. Thompson. Câteva probleme de estimare și testare în controlul proceselor statistice multivariate // Proceedings of the 38th Conference on the Design of Experiments . - 1993. - T. 93-2. — P. 99–126.
• Hendrick P. Lopuhaä, Peter J. Rousseeuw. Puncte de defalcare ale estimatorilor echivarianți afine de locație multivariată și matrice de covarianță  // Annals of Statistics . - 1991. - T. 19 , nr. 1 . — S. 229–248 . - doi : 10.1214/aos/1176347978 . — .
• Jiawang Nie, Pablo A. Parrilo, Bernd Sturmfels. Algoritmi în geometrie algebrică / A. Dickenstein, F.-O. Schreyer, AJ Sommese. - Springer-Verlag, 2008. - T. 146. - S. 117-132. - (Volume IMA în matematică și aplicațiile sale).
• L. Ostresh. Convergența unei clase de metode iterative pentru rezolvarea problemei de locație Weber // Cercetare operațională . - 1978. - T. 26 , nr. 4 . — S. 597–609 . doi : 10.1287 / opre.26.4.597 .
• Frank Plastry. Probleme de locație Fermat în patru puncte revizuite. Noi dovezi și extensii ale rezultatelor vechi  // IMA Journal of Management Mathematics. - 2006. - T. 17 , nr. 4 . — S. 387–396 . - doi : 10.1093/imaman/dpl007 .
• PG Spania. Punctul Fermat al unui triunghi  // Revista de matematică. - 1996. - T. 69 , nr. 2 . — S. 131–133 . — .
• Yehuda Vardi, Cun-Hui Zhang. The multivariate L 1 -median and associated data depth // Proceedings of the National Academy of Sciences of the United States of America. - 2000. - T. 97 , nr. 4 . — S. 1423–1426 (electronic) . - 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. Problema Weber: istorie și perspectivă  // ​​Știința locației. - 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 .