dreapta|miniatura|320x320px| Exemplu de mediană geometrică (în galben) a unei colecții de puncte. În albastru, centrul de masă. În geometrie, mediana geometrică a unei mulțimi finite de puncte într-un spațiu euclidian este punctul care minimizează suma distanțelor până la punctele eșantionului. Aceasta generalizează mediana, care are proprietatea de a minimiza suma distanțelor pentru datele unidimensionale. Este, de asemenea, cunoscut sub numele de mediană spațială, punct minisum euclidian, punct Torricelli, sau 1-mediană. Oferă o măsură a tendinței centrale în spații multidimensionale și este o problemă standard în localizarea facilității optimale, adică localizarea unei locații pentru a minimiza costurile de transport.

Mediana geometrică este un estimator important al locației în statistică, deoarece minimizează suma distanțelor L2 ale eșantionului. Este de comparat cu media, care minimizează suma pătratelor L2 distanțelor, dar și cu mediana coordonatelor care minimizează suma distanțelor L1. Problema <i id="mwPQ">k</i>-medianelor este o generalizare care cere locația a k centre minimizând suma distanțelor L2 de la fiecare punct din eșantion la cel mai apropiat centru al său.

Cazul special al problemei pentru trei puncte din plan (adică = 3 și = 2 în definiția de mai jos) este uneori cunoscut și ca problema lui Fermat; apare în construcția arborilor Steiner minimali și a fost formulată inițial de Pierre de Fermat și rezolvată de Evangelista Torricelli. Soluția sa este acum cunoscută ca punctul Fermat al triunghiului format din cele trei puncte. Mediana geometrică poate fi, la rândul său, generalizată la problema minimizării sumei distanțelor ponderate, cunoscută sub numele de problema Weber după discuția lui Alfred Weber despre această problemă în cartea sa din 1909 despre locația facilităților. Unele surse numesc problema lui Weber problema Fermat–Weber, dar altele folosesc acest nume pentru problema mediană geometrică neponderată.

Wesolowsky (1993) oferă o analiză a problemei medianei geometrice. Vezi Fekete, Mitchell & Beurer (2005) pentru generalizarea problemei pentru o mulțime de puncte nediscretă.

Definiție Formal, pentru o mulțime dată de m puncte cu fiecare , mediana geometrică este definită ca suma minimizatorului de distanțe L2:

Aici, arg min înseamnă valoarea argumentului care minimizează suma. În acest caz, este punctul din spațiul euclidian n-dimensional de unde suma tuturor distanțelor euclidiene la este minimă.

Proprietăți

Pentru cazul unidimensional, mediana geometrică coincide cu mediana. Acest lucru se datorează faptului că mediana univariată minimizează și suma distanțelor de la puncte. (Mai precis, dacă punctele sunt p1, ..., pn, în această ordine, mediana geometrică este punctul de mijloc dacă n este impar, dar nu este determinat în mod unic dacă n este par, când poate fi orice punct din intervalul dintre cele două puncte medii și .) Mediana geometrică este unică ori de câte ori punctele nu sunt coliniare. Mediana geometrică este echivariantă pentru transformările de asemănare euclidiană, inclusiv translația și rotația. Aceasta înseamnă că s-ar obține același rezultat fie transformând mediana geometrică, fie aplicând aceeași transformare datelor eșantionului și găsirea medianei geometrice a datelor transformate. Această proprietate rezultă din faptul că mediana geometrică este definită numai din distanțele perechilor și nu depinde de sistemul de coordonate carteziene ortogonale prin care sunt reprezentate datele eșantionului. În schimb, mediana componentelor pentru o mulțime de date multivariate nu este invariantă, în general, la rotații și nici nu este independentă de alegerea coordonatelor. Mediana geometrică are un prag de compromitere (în engleză, breakdown point) de 0,5. Adică, până la jumătate din datele eșantionului pot fi corupte în mod arbitrar, iar mediana eșantioanelor va oferi în continuare un estimator robust pentru locația datelor necorupte.

Cazuri speciale

Pentru 3 puncte (necoliniare), dacă orice unghi al triunghiului format de acele puncte este de 120° sau mai mult, atunci mediana geometrică este vârful acelui unghi. Dacă toate unghiurile sunt mai mici de 120°, mediana geometrică este punctul din interiorul triunghiului care subtinde un unghi de 120° la fiecare trei perechi de vârfuri de triunghi. Acesta este cunoscut și sub numele de punctul Fermat al triunghiului format din cele trei vârfuri. (Dacă cele trei puncte sunt coliniare, atunci mediana geometrică este punctul dintre celelalte două puncte, așa cum este cazul unei mediane unidimensionale.) Pentru 4 puncte coplanare, dacă unul dintre cele patru puncte se află în interiorul triunghiului format de celelalte trei puncte, atunci mediana geometrică este acel punct. În caz contrar, cele patru puncte formează un patrulater convex, iar mediana geometrică este punctul de trecere al diagonalelor patrulaterului. Mediana geometrică a patru puncte coplanare este aceeași cu unicul punct Radon al celor patru puncte.

Calcul În ciuda faptului că mediana geometrică este un concept ușor de înțeles, calcularea acesteia reprezintă o provocare. Centroidul sau centrul de masă, definit în mod similar cu mediana geometrică ca minimizarea sumei pătratelor distanțelor până la fiecare punct, poate fi găsit printr-o formulă simplă: coordonatele sale sunt mediile coordonatelor punctelor. Pe de altă parte, s-a demonstrat că nu poate exista nicio formulă explicită, nici un algoritm exact care implică doar operații aritmetice și radicali pentru medii geometrice generale. Prin urmare, numai aproximările numerice sau simbolice ale soluției acestei probleme sunt posibile sub acest model de calcul.

Cu toate acestea, este simplu să se calculeze o aproximare a medianei geometrice folosind o procedură iterativă în care fiecare pas produce o aproximare mai precisă. Procedurile de acest tip pot fi derivate din faptul că suma distanțelor până la punctele eșantionului este o funcție convexă, deoarece distanța până la fiecare punct eșantion este convexă, iar o sumă de funcții convexe rămâne convexă. Prin urmare, procedurile care reduc suma distanțelor la fiecare pas nu se operesc într-un optim local care nu este global.

O abordare uzuală de acest tip, numită algoritmul lui Weiszfeld, numit după Endre Weiszfeld, este o formă a metodei celor mai mici pătrate iterativ reponderate. Acest algoritm definește o mulțime de ponderi care sunt invers proporționale cu distanțele de la estimarea curentă la punctele eșantionului și creează o nouă estimare care este media ponderată a eșantionului în funcție de aceste ponderi. Mai precis,

Această metodă converge pentru aproape toate pozițiile inițiale, dar poate eșua să convergă atunci când una dintre estimările sale coincide cu unul dintre punctele date. Algoritmul poate fi modificat pentru a gestiona aceste cazuri, astfel încât să convergă pentru toate punctele inițiale.

Bose, Maheshwari & Morin (2003) descriu proceduri de optimizare geometrică mai sofisticate pentru a găsi soluții aproximativ optime la această problemă. Cohen et al. (2016) arată cum să calculezi mediana geometrică cu o precizie arbitrară în timp aproape liniar. Rețineți, de asemenea, că problema poate fi formulată ca program conic de ordinul al doilea

care poate fi rezolvată în timp polinomial utilizând metode uzuale de optimizare.

Caracterizarea medianei geometrice Dacă y este distinct de toate punctele date, xi, atunci y este mediana geometrică dacă și numai dacă satisface:

Această relație este echivalentă cu:

care este strâns legat de algoritmul lui Weiszfeld.

În general, y este mediana geometrică dacă și numai dacă există vectori ui astfel încât:

unde pentru x i ≠ y,

iar pentru x i = y,

O formulare echivalentă a acestei condiții este

Poate fi văzută ca o generalizare a proprietății mediane, în sensul că orice partiție a punctelor, în special cea indusă de orice hiperplan prin y, suma direcțiilor pozitive din y pe ambele părții e aceeași. În cazul unidimensional, hiperplanul este punctul y însuși, iar suma direcțiilor se simplifică la măsura de numărare (direcționată).

Generalizări Mediana 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 o varietate riemanniană. Fie o varietate Riemanniană cu funcția de distanță corespunzătoare , fie ponderi cu suma 1 și fie puncte de pe . Apoi putem defini mediana geometrică ponderată (sau mediana Fréchet ponderată) a punctelor de date ca

.

Dacă toate ponderile sunt egale, spunem pur și simplu că este mediana geometrică.

Note

Categorie:Algoritmi de geometrie Categorie:Optimizare Categorie:Medii Categorie:Articole cu surse în limba franceză (fr) Categorie:Articole cu surse în limba germană (de) Categorie:Pagini cu traduceri nerevizuite