Médiane géométrique

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 médiane spatiale, point de somme euclidienne minimum, point de Torricelli, ou 1-médiane.

La médiane géométrique est un estimateur de localisation important en statistique car elle minimise la somme des distances L₂ des échantillons. Elle se compare donc à la moyenne, qui minimise la somme du carré des distances L₂, et à la médiane par composante qui minimise la somme des distances L₁. 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. 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.

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. Sa solution est maintenant connue sous le nom de point de Fermat du triangle formé par les trois points de l'échantillon. 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, mais d'autres utilisent ce nom pour le problème de la médiane géométrique non pondérée.

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 $\mathbb {X} ^{m}=x_{1},x_{2},\dots ,x_{m}\,$ avec chaque $x_{i}\in \mathbb {R} ^{n}$, la médiane géométrique est définie comme le minimiseur de la somme des distances L₂

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

Ici, arg min signifie la valeur de l'argument $y$ ce qui minimise la somme. Dans ce cas, c'est le point $y$ dans un espace euclidien à n dimensions d'où la somme de toutes les distances euclidiennes jusqu'au $x_{i}$ 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 ₁, …, p _n, dans cet ordre, la médiane géométrique est le point médian $p_{(n+1)/2}$ 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 $p_{n/2}$ et $p_{(n/2)+1}$)
• 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 par translation et rotation. 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.
• 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,

$\left.y_{k+1}=\left(\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y_{k}\|}}\right)\right/\left(\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y_{k}\|}}\right).$

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

${\underset {y\in \mathbb {R} ^{n},\ s\in \mathbb {R} ^{m}}{\min }}\ \sum _{i=1}^{m}s_{i}{\text{ avec }}s_{i}\geq \left\|x_{i}-y\right\|_{2}{\text{ pour }}i=1,\ldots ,m,$

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 :

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

Cela équivaut à :

$\left.y=\left(\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y\|}}\right)\right/\left(\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y\|}}\right),$

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 :

$0=\sum _{i=1}^{m}u_{i}$

où pour x_i ≠ y ,

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

et pour x_i = y ,

$\|u_{i}\|\leq 1.$

Une formulation équivalente de cette condition est

$\sum _{1\leq i\leq m,x_{i}\neq y}{\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}\leq \left|\{\,i\mid 1\leq i\leq m,x_{i}=y\,\}\right|.$

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 . Soit $M$ une variété riemannienne avec une fonction de distance correspondante $d(\cdot ,\cdot )$, soient $w_{1},\ldots ,w_{n}$ $n$ poids dont la somme vaut 1, et soient $x_{1},\ldots ,x_{n}$ $n$ observations de $M$. Ensuite, on définit la médiane géométrique pondérée $m$ (ou médiane de Fréchet pondérée) des données comme

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

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

Voir également

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

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Geometric median » (voir la liste des auteurs).