« Médiane géométrique » : différence entre les versions

Un article de Wikipédia, l'encyclopédie libre.
Contenu supprimé Contenu ajouté
Ligne 92 : Ligne 92 :


== Références ==
== Références ==
 {{refbegin|30em}}
 
*{{cite journal
| last = Bajaj | first = Chanderjit | author-link = Chandrajit Bajaj
| title = Proving geometric algorithms nonsolvability: An application of factoring polynomials
| journal = [[Journal of Symbolic Computation]]
| year = 1986
| volume = 2
| pages = 99–102
| doi = 10.1016/S0747-7171(86)80015-3
| doi-access = free
}}
*{{cite journal
| last = Bajaj | first = Chanderjit | author-link = Chandrajit Bajaj
| title = The algebraic degree of geometric optimization problems
| journal = [[Discrete & Computational Geometry]]
| year = 1988
| volume = 3
| issue = 2 | pages = 177–191
| doi = 10.1007/BF02187906
| url = http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1415&context=cstech| doi-access = free
}}
*{{cite journal
| title = Fast approximations for sums of distances, clustering and the Fermat–Weber problem
| last1 = Bose | first1= Prosenjit | author1-link = Jit Bose | last2 = Maheshwari | first2 = Anil | last3 = Morin | first3 = Pat | author3-link = Pat Morin
| journal = [[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]
| volume = 24
| issue = 3
| pages = 135–146
| year = 2003
| doi = 10.1016/S0925-7721(02)00102-5
| url = http://www.scs.carleton.ca/~jit/publications/papers/bmm01.ps
| doi-access = free
}}
*{{cite journal
| last = Brimberg | first = J.
| doi = 10.1007/BF01592245
| issue = 1, Ser. A
| journal = [[Mathematical Programming]]
| mr = 1362958
| pages = 71–76
| title = The Fermat–Weber location problem revisited
| volume = 71
| year = 1995
| s2cid = 206800756
}}
*{{cite journal
| last1 = Chandrasekaran | first1 = R. | last2 = Tamir | first2 = A.
| title = Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem
| journal = [[Mathematical Programming]] | series = Series A
| volume = 44
| year = 1989
| issue = 1–3 | pages = 293–295
| doi = 10.1007/BF01587094
| s2cid = 43224801 }}
*{{cite book|title=Shortest Connectivity: An Introduction with Applications in Phylogeny|volume=17|series=Combinatorial Optimization|first=Dietmar|last=Cieslik|publisher=Springer|year=2006|isbn=9780387235394|page=3|url=https://books.google.com/books?id=4E0r3oWkn6AC&pg=PA3}}
*{{cite journal
| doi = 10.2307/2688541
| last1 = Cockayne | first1 = E. J. | last2 = Melzak | first2 = Z. A.
| title = Euclidean constructability in graph minimization problems
| jstor = 2688541
| journal = [[Mathematics Magazine]]
| volume = 42
| issue = 4
| pages = 206–208
| year = 1969
}}
*{{cite conference|contribution=Geometric median in nearly linear time|last1=Cohen|first1=Michael|last2=Lee|first2=Yin Tat|last3=Miller|first3=Gary|author3-link=Gary Miller (computer scientist)|last4=Pachocki|first4=Jakub|last5=Sidford|first5=Aaron|publisher=[[Association for Computing Machinery]]|title=Proc. 48th Symposium on Theory of Computing (STOC 2016)|title-link=Symposium on Theory of Computing|year=2016|contribution-url=http://www.cs.cmu.edu/~./glmiller/Publications/Papers/CLMPS16.pdf|arxiv=1606.05225|doi=10.1145/2897518.2897647}}
*{{cite journal
| last1 = Dodge | first1 = Yadolah
| last2 = Rousson | first2 = Valentin
| date = September 1999
| doi = 10.1007/s001840050029
| issue = 2
| journal = Metrika
| page = 127–134
| title = Multivariate {{math|''L''<sub>1</sub>}} mean
| volume = 49}}
*{{cite conference
| last1 = Drezner | first1 = Zvi
| last2 = Klamroth | first2 = Kathrin | author2-link = Kathrin Klamroth
| last3 = Schöbel | first3 = Anita | author3-link = Anita Schöbel
| last4 = Wesolowsky | first4 = George O.
| title = The Weber problem
| mr = 1933966
| pages = 1–36
| publisher = Springer, Berlin
| book-title = Facility Location: Applications and Theory
| url = https://books.google.com/books?id=sxpcsGN7K1YC&pg=PA1
| year = 2002
| isbn = 9783540213451
}}
*{{cite book|title=Foundations of Location Analysis|volume=155|series=International Series in Operations Research & Management Science|first1=H. A.|last1=Eiselt|first2=Vladimir|last2=Marianov|publisher=Springer|year=2011|isbn=9781441975720|page=6|url=https://books.google.com/books?id=6bQ8JJ_Rx6sC&pg=PA6}}
*{{cite journal
| last1 = Fekete | first1 = Sándor P.
| last2 = Mitchell | first2 = Joseph S. B. | author2-link = Joseph S. B. Mitchell
| last3 = Beurer | first3 = Karin
| title = On the continuous Fermat-Weber problem
| journal = [[Operations Research (journal)|Operations Research]]
| volume = 53 | issue = 1
| pages = 61–76
| year = 2005
| arxiv = cs.CG/0310027
| doi = 10.1287/opre.1040.0137| s2cid = 1121
}}
*{{cite journal
| first1 = P. Thomas | last1 = Fletcher | first2 = Suresh | last2 = Venkatasubramanian | first3 = Sarang | last3 = Joshi
| title = The geometric median on Riemannian manifolds with application to robust atlas estimation
| journal = NeuroImage
| volume = 45
| year = 2009
| pages = s143–s152
| doi = 10.1016/j.neuroimage.2008.10.052
| pmid = 19056498
| issue = 1 Suppl
| pmc = 2735114
}}
*{{cite journal|first=J. B. S.|last=Haldane|author-link=J. B. S. Haldane|title=Note on the median of a multivariate distribution|journal=Biometrika|year=1948|volume=35|issue=3–4|pages=414–417|doi=10.1093/biomet/35.3-4.414}}
*{{cite journal
| last1 = Krarup | first1 = Jakob
| last2 = Vajda | first2 = Steven
| doi = 10.1093/imaman/8.3.215
| issue = 3
| journal = IMA Journal of Mathematics Applied in Business and Industry
| mr = 1473041
| pages = 215–224
| title = On Torricelli's geometrical solution to a problem of Fermat
| volume = 8
| year = 1997
}}
*{{cite journal
| last = Kuhn | first = Harold W. | author-link = Harold W. Kuhn
| title = A note on Fermat's problem
| journal = [[Mathematical Programming]]
| year = 1973
| volume = 4
| issue = 1
| pages = 98–107
| doi = 10.1007/BF01584648
| s2cid = 22534094 }}
*{{cite conference|title=Some problems of estimation and testing in multivariate statistical process control|first1=Martin|last1=Lawera|first2=James R.|last2=Thompson|author2-link=James R. Thompson (statistician)|year=1993|pages=99–126|url=https://apps.dtic.mil/sti/pdfs/ADA390709.pdf|archive-url=https://web.archive.org/web/20140517155908/http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA390709|url-status=live|archive-date=May 17, 2014|book-title=Proceedings of the 38th Conference on the Design of Experiments|series=U.S. Army Research Office Report|volume=93-2}}
*{{cite journal
| last1 = Lopuhaä | first1 = Hendrick P.
| last2 = Rousseeuw | first2 = Peter J. | author2-link = Peter Rousseeuw
| title = Breakdown points of affine equivariant estimators of multivariate location and covariance matrices
| year = 1991
| journal = [[Annals of Statistics]]
| volume = 19
| pages = 229–248
| issue = 1
| doi = 10.1214/aos/1176347978
| jstor=2241852| url = https://repository.tudelft.nl/islandora/object/uuid%3A8e67fb99-7cb7-4b11-8e6a-02039c7ed1bb/datastream/OBJ/download
| doi-access = free
}}
*{{Cite book
| first1 = Jiawang | last1 = Nie | first2 = Pablo A. |last2 = Parrilo | first3 = Bernd | last3 = Sturmfels | author3-link = Bernd Sturmfels
| contribution = Semidefinite representation of the {{mvar|k}}-ellipse
| series = IMA Volumes in Mathematics and its Applications
| volume = 146
| editor1-first = A. | editor1-last = Dickenstein
| editor2-first = F.-O. | editor2-last = Schreyer
| editor3-first = A.J. | editor3-last = Sommese
| publisher = Springer-Verlag | pages = 117–132 | year = 2008 | arxiv = math/0702005
| title = Algorithms in Algebraic Geometry
| doi = 10.1007/978-0-387-75155-9_7 | bibcode = 2007math......2005N| s2cid = 16558095 }}
*{{cite journal
| last = Ostresh | first = L.
| title = Convergence of a class of iterative methods for solving Weber location problem
| year = 1978
| journal = [[Operations Research (journal)|Operations Research]]
| volume = 26
| pages = 597–609
| doi = 10.1287/opre.26.4.597
| issue = 4}}
*{{cite journal|title=Four-point Fermat location problems revisited. New proofs and extensions of old results|first=Frank|last=Plastria|author-link=Frank Plastria|year=2006|doi=10.1093/imaman/dpl007|journal=IMA Journal of Management Mathematics|url=http://mosi.vub.ac.be/papers/Plastria2005_Fegnano.pdf|zbl=1126.90046|volume=17|issue=4|pages=387–396}}.
*{{cite journal
| last = Spain | first = P. G.
| issue = 2
| journal = Mathematics Magazine
| jstor = 2690672?origin=pubexport
| mr = 1573157
| pages = 131–133
| title = The Fermat point of a triangle
| volume = 69
| year = 1996
| doi = 10.1080/0025570X.1996.11996409
}}
*{{cite journal
| last1 = Vardi | first1 = Yehuda
| last2 = Zhang | first2 = Cun-Hui
| doi = 10.1073/pnas.97.4.1423
| issue = 4
| journal = Proceedings of the National Academy of Sciences of the United States of America
| mr = 1740461
| pages = 1423–1426 (electronic)
| title = The multivariate {{math|''L''<sub>1</sub>}}-median and associated data depth
| volume = 97
| year = 2000
| pmc = 26449
| bibcode = 2000PNAS...97.1423V
| pmid=10677477
| doi-access = free
}}
*{{cite book
| last = Weber | first = Alfred | author-link = Alfred Weber
| title = Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes
| language = de
| location = Tübingen
| publisher = Mohr
| year = 1909
}}
*{{cite journal
| last = Wesolowsky | first = G.
| title = The Weber problem: History and perspective
| journal = Location Science
| volume = 1
| pages = 5–23
| year = 1993
}}
*{{cite journal
| last = Weiszfeld | first = E. | author-link = Andrew Vázsonyi
| title = Sur le point pour lequel la somme des distances de {{mvar|n}} points donnes est minimum
| journal = [[Tohoku Mathematical Journal]]
| language = fr
| url = https://www.jstage.jst.go.jp/article/tmj1911/43/0/43_0_355/_article/-char/en
| volume = 43
| year = 1937
| pages = 355–386
}} Translated into English as {{cite journal
| last1 = Weiszfeld | first1 = E.
| last2 = Plastria | first2 = Frank | author2-link = Frank Plastria
| date = April 2008
| doi = 10.1007/s10479-008-0352-z
| issue = 1
| journal = [[Annals of Operations Research]]
| pages = 7–41
| title = On the point for which the sum of the distances to {{mvar|n}} given points is minimum
| volume = 167| s2cid = 21000317
}}
{{refend}}

{{Portail|Probabilités et statistiques}}

[[Catégorie:Statistique descriptive]]
[[Catégorie:Statistique descriptive]]
[[Catégorie:Géométrie algorithmique]]
[[Catégorie:Géométrie algorithmique]]

Version du 9 janvier 2024 à 12:28

Exemple de médiane géométrique (en jaune) d'une série de points. En bleu le centre de gravité .

En géométrie, la médiane géométrique d'un ensemble discret de points d'un échantillon dans un espace euclidien est le point minimisant la somme des distances aux points de l'échantillon. Cela généralise la médiane, qui a la propriété de minimiser la somme des distances pour les données unidimensionnelles, et fournit un indicateur de tendance centrale dans les dimensions supérieures. Il est également connu sous le nom de 1-médiane, médiane spatiale, [1] point de somme euclidienne minimum, ou point de Torricelli . [2]

La médiane géométrique est un estimateur de localisation important en statistique [3] où elle est également connue sous le nom d'estimateur L1 (car elle minimise la norme L1 du vecteur des distances). [4] C'est également un problème standard d'emplacement des installations, où il modélise le problème de la localisation d'une installation afin de minimiser le coût du transport. [5] Le problème k -médiane plus général demande l'emplacement des k centres de cluster en minimisant la somme des distances entre chaque point d'échantillon et son centre le plus proche. Si le point est généralisé en une ligne ou une courbe, la solution la mieux adaptée est trouvée via les moindres déviations absolues .

Le cas particulier du problème des trois points du plan (c'est-à-dire m = 3 et n = 2 dans la définition ci-dessous) est parfois également connu sous le nom de problème de Fermat ; il apparaît dans la construction des arbres de Steiner minimaux et a été initialement posé comme problème par Pierre de Fermat et résolu par Evangelista Torricelli . [6] Sa solution est maintenant connue sous le nom de point de Fermat du triangle formé par les trois points de l'échantillon. [7] La médiane géométrique peut à son tour être généralisée au problème de la minimisation de la somme des distances pondérées, connu sous le nom de problème de Weber d'après la discussion du problème par Alfred Weber dans son livre de 1909 sur l'emplacement des installations. Certaines sources appellent plutôt le problème de Weber le problème de Fermat-Weber [8], mais d'autres utilisent ce nom pour le problème de la médiane géométrique non pondérée. [9]

Wesolowsky (1993) fournit une étude du problème de la médiane géométrique. Fekete, Mitchell & Beurer (2005) se sont posés la question du problème pour des points non discrets.

Définition

Formellement, pour un ensemble donné de m points avec chaque , la médiane géométrique est définie comme

Ici, arg min signifie la valeur de l'argument ce qui minimise la somme. Dans ce cas, c'est le point dans un espace euclidien à n dimensions d'où la somme de toutes les distances euclidiennes jusqu'au est minimale.

Propriétés

  • Pour le cas unidimensionnel, la médiane géométrique coïncide avec la médiane . En effet, la médiane univariée minimise également la somme des distances aux points. (Plus précisément, si les points sont p 1, …, p n, dans cet ordre, la médiane géométrique est le point médian si n est impair, mais n'est pas déterminé de manière unique si n est pair, auquel cas il peut s'agir de n'importe quel point du segment de droite entre les deux points intermédiaires et .) [10] [11]
  • La médiane géométrique est unique lorsque les points ne sont pas colinéaires .
  • La médiane géométrique est équivariante par similitude euclidienne, y compris la translation et la rotation . [12] Cela signifie que l'on obtiendrait le même résultat soit en transformant la médiane géométrique, soit en appliquant la même transformation aux données de l'échantillon et en trouvant la médiane géométrique des données transformées. Cette propriété découle du fait que la médiane géométrique est définie uniquement à partir des distances par paires et ne dépend pas du système de coordonnées cartésiennes orthogonales par lequel les données de l'échantillon sont représentées. En revanche, la médiane par composante d’un ensemble de données multivariées n’est généralement pas invariante par rotation, ni indépendante du choix des coordonnées. [12]
  • La médiane géométrique a un point de rupture de 0,5. Autrement dit, jusqu'à la moitié des données de l'échantillon peuvent être arbitrairement corrompues, et la médiane des échantillons fournira toujours un estimateur robuste pour l'emplacement des données non corrompues.

Cas spéciaux

  • Pour 3 points (non colinéaires), si un angle du triangle formé par ces points est de 120° ou plus, alors la médiane géométrique est le point au sommet de cet angle. Si tous les angles sont inférieurs à 120°, la médiane géométrique est le point à l'intérieur du triangle qui sous-tend un angle de 120° à chacune des trois paires de sommets du triangle. Ceci est également connu sous le nom de point de Fermat du triangle formé par les trois sommets. (Si les trois points sont colinéaires alors la médiane géométrique est le point entre les deux autres points, comme c'est le cas avec une médiane unidimensionnelle.)
  • Pour 4 points coplanaires , si l'un des quatre points est à l'intérieur du triangle formé par les trois autres points, alors la médiane géométrique est ce point. Sinon, les quatre points forment un quadrilatère convexe et la médiane géométrique est le point de croisement des diagonales du quadrilatère. La médiane géométrique de quatre points coplanaires est la même que le point de Radon unique des quatre points.

Calcul

Bien que la médiane géométrique soit un concept facile à comprendre, son calcul constitue un défi. Le centroïde ou centre de masse, défini de la même manière que la médiane géométrique comme minimisant la somme des carrés des distances à chaque point, peut être trouvé par une formule simple — ses coordonnées sont les moyennes des coordonnées des points — mais il a été démontré qu'aucune formule explicite, ni algorithme exact impliquant uniquement des opérations arithmétiques et des racines k ièmes , ne peuvent exister en général pour la médiane géométrique. Par conséquent, seules des approximations numériques ou symboliques de la solution de ce problème sont possibles dans ce modèle de calcul .

Cependant, il est simple de calculer une approximation de la médiane géométrique en utilisant un algorithme itératif dans lequel chaque étape produit une approximation plus précise. Des procédés de ce type peuvent être dérivés du fait que la somme des distances aux points d'échantillonnage est une fonction convexe, puisque la distance à chaque point d'échantillonnage est convexe et que la somme des fonctions convexes reste convexe. Par conséquent, les algorithmes qui diminuent la somme des distances à chaque étape ne peuvent pas rester piégées dans un optimal local .

Une approche courante de ce type, appelée algorithme de Weiszfeld d'après les travaux d' Endre Weiszfeld, est une forme de moindres carrés itérativement repondérés . Cet algorithme définit un ensemble de poids inversement proportionnels aux distances entre l'estimation actuelle et les points d'échantillonnage, et crée une nouvelle estimation qui est la moyenne pondérée de l'échantillon en fonction de ces poids. C'est,

Cette méthode converge pour presque toutes les positions initiales, mais peut échouer lorsqu'une de ses estimations tombe sur l'un des points donnés. Il peut être modifié pour gérer ces cas afin qu'il converge pour tous les points initiaux.

Bose, Maheshwari & Morin (2003) ont décrit des algorithmes d'optimisation géométrique plus sophistiqués pour trouver des solutions approximativement optimales à ce problème. Cohen et al. (2016) ont montré comment calculer la médiane géométrique avec une précision arbitraire en un temps quasi linéaire. On peut remarquer que ce problème peut être reformulé comme un programme du cône de second ordre

qui peut être résolu en temps polynomial à l'aide de solveurs d'optimisation courants .

Caractérisation de la médiane géométrique

Si y est distinct de tous les points donnés x i, alors y est la médiane géométrique si et seulement si elle satisfait :

Cela équivaut à :

qui est étroitement lié à l'algorithme de Weiszfeld.

En général, y est la médiane géométrique si et seulement s'il existe des vecteurs u i tels que :

où pour x iy ,

et pour x i = y ,

Une formulation équivalente de cette condition est

Cela peut être vu comme une généralisation de la propriété de la médiane, dans le sens où toute partition des points, en particulier induite par tout hyperplan passant par y, a la même somme opposée de directions positives de y de chaque côté. Dans le cas unidimensionnel, l'hyperplan est le point y lui-même, et la somme des directions se simplifie en mesure de comptage (dirigée).

Généralisations

La médiane géométrique peut être généralisée des espaces euclidiens aux variétés riemanniennes générales (et même aux espaces métriques ) en utilisant la même idée qui est utilisée pour définir la moyenne de Fréchet sur une variété riemannienne. [13] [14] Soit une variété riemannienne avec une fonction de distance correspondante , soient poids dont la somme vaut 1, et soient observations de . Ensuite, on définit la médiane géométrique pondérée (ou médiane de Fréchet pondérée) des données comme

.

Si tous les poids sont égaux, on dit simplement que est la médiane géométrique.

Voir également

  • Médoïde
  • Écart absolu médian géométrique

Références

  1. Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées dksw
  2. Cieslik (2006).
  3. Lawera et Thompson (1993).
  4. Dodge et Rousson (1999).
  5. Eiselt et Marianov (2011).
  6. Krarup et Vajda (1997).
  7. Spain (1996).
  8. Brimberg (1995).
  9. Bose, Maheshwari et Morin (2003).
  10. Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées haldane
  11. Claim 18.10, Geometric Methods and Optimization Problems, V. Boltyanski, H. Martini, V. Soltan, Springer, 1999.
  12. a et b Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées lr
  13. P. Thomas Fletcher et Suresh Venkatasubramanian « Robust statistics on Riemannian manifolds via the geometric median » () (lire en ligne)
    IEEE Conference on Computer Vision and Pattern Recognition
    « (ibid.) », dans 2008 IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, AK, USA, IEEE
  14. Fletcher, Venkatasubramanian et Joshi (2009).

Références