Mediana geométrica

Supóngase que se quiere localizar una fábrica que trabaja con materiales procedentes de seis almacenes, minimizando la suma de las distancias de transporte resultantes. La ubicación que cumple este criterio es la mediana geométrica y con respecto a los seis almacenes x_i.

La mediana geométrica de un conjunto discreto de puntos de una muestra en un espacio euclídeo es el punto que minimiza la suma de las distancias a los puntos de la muestra. Esto generaliza el concepto de mediana estadística, que tiene la propiedad de minimizar la suma de distancias para datos unidimensionales, y proporciona una medida de tendencia central en dimensiones superiores. También se conoce como la 1-mediana,​ mediana espacial,​ punto minisum euclidiano,​ o punto de Torricelli.​

La mediana geométrica es un estimador importante de localización en estadística, ​ donde así mismo se la conoce como el estimador₁.​ También es un indicador estándar en la resolución del problema de localización de instalaciones, donde modela el problema de localizar una instalación para minimizar el costo del transporte. ​

El caso especial del problema para tres puntos en el plano (es decir, m = 3 y n = 2 en la definición que figura a continuación) también se conoce a veces como el problema de Fermat; surge en la construcción de árboles de Steiner mínimos, y se planteó originalmente como un problema por Pierre de Fermat, y fue resuelto por Evangelista Torricelli. ​ Su solución ahora se conoce como el punto de Fermat del triángulo formado por los tres puntos de la muestra. ​ La mediana geométrica a su vez puede ser generalizada al problema de minimizar la suma de distancias "ponderadas", conocido como el problema de Weber después de ser analizado por Alfred Weber sobre el problema introducido en su libro de 1909 sobre la ubicación de instalaciones.​ Algunas fuentes llaman al problema de Weber el problema de Fermat-Weber, ​ pero en otros casos se usa este nombre para el problema de la mediana geométrica no ponderada. ​

Wesolowsky (1993) proporciona un muestreo del problema de la mediana geométrica. Véase Fekete, Mitchell y Beurer (2005) para generalizaciones del problema a conjuntos de puntos no discretos.

Definición

Formalmente, para un conjunto dado de m puntos $x_{1},x_{2},\dots ,x_{m}\,$ con cada $x_{i}\in \mathbb {R} ^{n}$, la mediana geométrica se define como

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

Aquí, arg min significa el valor del argumento $y$ que minimiza la suma. En este caso, es el punto $y$ desde donde la suma de todas las distancias euclidianas a $x_{i}$ es mínima.

Propiedades

• Para el caso unidimensional, la mediana geométrica coincide con el concepto estadístico de mediana. Esto se debe a que la mediana para una sola variable también minimiza la suma de las distancias desde los puntos.​
• La mediana geométrica es única siempre que los puntos no sean colineales.​
• La mediana geométrica es equivariante para lastransformaciones de semejanza en el espacio euclideo, incluyendo traslaciones y rotaciones.​​ Esto significa que se obtendría el mismo resultado, ya sea mediante la transformación de la mediana geométrica, o mediante la aplicación de la misma transformación a los datos de la muestra y la búsqueda de la mediana geométrica de los datos transformados. Esta propiedad se desprende del hecho de que la mediana geométrica se define solo a partir de distancias entre pares, y no depende del sistema de Coordenadas cartesianas ortogonal mediante el cual se representan los datos de la muestra. Por el contrario, la mediana de los componentes para un conjunto de datos de variables múltiples no es invariante con respecto a la rotación general, ni es independiente de la elección de las coordenadas.​
• La mediana geométrica tiene una robustez estadística de 0,5.​. Es decir, hasta la mitad de los datos de muestra pueden estar corruptos arbitrariamente, y la mediana de las muestras aún proporcionará un resultado consistente para la ubicación de los datos no dañados.

Casos especiales

• Para 3 puntos no colineales, si cualquier ángulo del triángulo formado por esos puntos es 120° o más, entonces la mediana geométrica es el punto en el vértice de ese ángulo. Si todos los ángulos son menores a 120°, la mediana geométrica es el punto dentro del triángulo que subtiende un ángulo de 120° con los tres pares de vértices del triángulo.​ Esto también se conoce como el Punto de Fermat del triángulo formado por los tres vértices (si los tres puntos son colineales, la mediana geométrica es el punto entre los otros dos puntos, como es el caso con una mediana unidimensional).
• Para 4 puntos coplanarios, si uno de los cuatro puntos está dentro del triángulo formado por los otros tres puntos, entonces la mediana geométrica es ese punto. De lo contrario, los cuatro puntos forman un cuadrilátero convexo y la mediana geométrica es el punto de cruce de las diagonales del cuadrilátero. La mediana geométrica de cuatro puntos coplanarios es única y la misma que la deducida por el Lema de Radon aplicado a los cuatro puntos.​

Computación

A pesar de que la mediana geométrica es un concepto fácil de entender, computarlo plantea un desafío. El centroide o centro de masas, definido de forma similar a la mediana geométrica como la minimización de la suma de los "cuadrados" de las distancias a cada punto, se puede encontrar mediante una fórmula simple (sus coordenadas son los promedios de las coordenadas de los puntos) pero se ha demostrado que no puede existir una fórmula explícita, ni un algoritmo exacto que involucre solo operaciones aritméticas y raíces késimas, en general para la mediana geométrica. Por lo tanto, solo las aproximaciones numéricas o simbólicas a la solución de este problema son posibles bajo este modelo de computación.​

Sin embargo, es sencillo calcular una aproximación a la mediana geométrica utilizando un procedimiento iterativo en el que cada paso produce una aproximación más precisa. Los procedimientos de este tipo pueden derivarse del hecho de que la suma de distancias a los puntos de muestra es una función convexa, ya que la distancia a cada punto de la muestra es convexa y la suma de las funciones convexas permanece convexa. Por lo tanto, los procedimientos que disminuyen la suma de distancias en cada paso no pueden quedar atrapados en un óptimo local.

Un enfoque común de este tipo, llamado algoritmo de Weiszfeld en referencia al trabajo de Endre Weiszfeld,​ es una forma de cuadrados mínimos iterativos reponderados. Este algoritmo define un conjunto de pesos que son inversamente proporcionales a las distancias a las muestras desde la última estimación, y crea una nueva estimación que es el promedio ponderado de las muestras de acuerdo con estos pesos. Es decir,

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

Este método converge para casi todas las posiciones iniciales, pero puede no converger cuando una de sus estimaciones recae en uno de los puntos dados. Se puede modificar para manejar estos casos de modo que converja para todos los puntos iniciales.​

Bose, Maheshwari y Morin (2003) describe procedimientos de optimización geométrica más sofisticados para encontrar soluciones aproximadamente óptimas a este problema. Como demuestran Nie, Parrilo y Sturmfels (2008), el problema también se puede representar como un programa semidefinido.

Cohen et al. (2016) muestran cómo calcular la mediana geométrica con precisión arbitraria en tiempo casi lineal.

Caracterización de la mediana geométrica

Si y es distinto de todos los puntos dados, x_j, entonces y es la mediana geométrica si y solo si satisface:

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

Esto es equivalente a:

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

que está estrechamente relacionado con el algoritmo de Weiszfeld.

En general, y es la mediana geométrica si y solo si existen vectores u_j tales que:

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

donde para x_j ≠ y,

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

y para x_j = y,

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

Una formulación equivalente de esta condición es

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

Se puede ver como una generalización de la propiedad mediana, en el sentido de que cualquier partición de los puntos, en particular como inducida por cualquier hiperplano a través de y, tiene la misma suma opuesta a las direcciones positivas de y en cada lado. En el caso unidimensional, el hiperplano es el punto y en sí mismo, y la suma de direcciones se simplifica a la medida de conteo (dirigida).

Generalizaciones

La mediana geométrica se puede generalizar de espacios euclidianos a variedades de Riemann generales (e incluso al espacio métrico) usando la misma idea que se usa para definir la media de Fréchet en una variedad riemanniana. ​ Sea $M$ una variedad riemanniana con la función de distancia correspondiente $d(\cdot ,\cdot )$, y sean $w_{1},\ldots ,w_{n}$ y $n$ los pesos sumados a 1, y hágase que $x_{1},\ldots ,x_{n}$ sean $n$ observaciones de $M$. A continuación se define la mediana geométrica ponderada $m$ (o mediana de Fréchet ponderada) de los puntos de datos como

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

Si todos los pesos son iguales, se dice simplemente que $m$ es la mediana geométrica.

Bibliografía

• Bajaj, C. (1986). «Proving geometric algorithms nonsolvability: An application of factoring polynomials». Journal of Symbolic Computation 2: 99-102. doi:10.1016/S0747-7171(86)80015-3. 
• Bajaj, C. (1988). «The algebraic degree of geometric optimization problems». Discrete and Computational Geometry 3: 177-191. doi:10.1007/BF02187906. 
• Bose, Prosenjit; Maheshwari, Anil; Morin, Pat (2003). «Fast approximations for sums of distances, clustering and the Fermat–Weber problem». Computational Geometry: Theory and Applications 24 (3): 135-146. doi:10.1016/S0925-7721(02)00102-5. 
• Brimberg, J. (1995). «The Fermat–Weber location problem revisited». Mathematical Programming 71 (1, Ser. A): 71-76. MR 1362958. doi:10.1007/BF01592245. 
• Chandrasekaran, R.; Tamir, A. (1989). «Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem». Mathematical Programming. Series A 44: 293-295. doi:10.1007/BF01587094. 
• Cieslik, Dietmar (2006). Shortest Connectivity: An Introduction with Applications in Phylogeny. Combinatorial Optimization 17. Springer. p. 3. ISBN 9780387235394. 
• Cockayne, E. J.; Melzak, Z. A. (1969). «Euclidean constructability in graph minimization problems». Mathematics Magazine 42 (4): 206-208. JSTOR 2688541. doi:10.2307/2688541. 
• Cohen, Michael; Lee, Yin Tat; Miller, Gary; Pachocki, Jakub; Sidford, Aaron (2016). «Geometric median in nearly linear time». Proc. 48th Symposium on Theory of Computing (STOC 2016). Association for Computing Machinery. 
• Drezner, Zvi; Klamroth, Kathrin; Schöbel, Anita; Wesolowsky, George O. (2002). «The Weber problem». Facility Location: Applications and Theory. Springer, Berlin. pp. 1-36. MR 1933966. 
• Eiselt, H. A.; Marianov, Vladimir (2011). Foundations of Location Analysis. 155series=International Series in Operations Research & Management Science. Springer. p. 6. ISBN 9781441975720. 
• Fekete, Sándor P.; Mitchell, Joseph S. B.; Beurer, Karin (2005). «On the continuous Fermat-Weber problem». Operations Research 53 (1): 61-76. arXiv:cs.CG/0310027. doi:10.1287/opre.1040.0137. 
• Fletcher, P. Thomas; Venkatasubramanian, Suresh; Joshi, Sarang (2009). «The geometric median on Riemannian manifolds with application to robust atlas estimation». NeuroImage 45 (1 Suppl): s143-s152. PMC 2735114. PMID 19056498. doi:10.1016/j.neuroimage.2008.10.052. 
• Haldane, J. B. S. (1948). «Note on the median of a multivariate distribution». Biometrika 35 (3–4): 414-417. doi:10.1093/biomet/35.3-4.414. 
• Krarup, Jakob; Vajda, Steven (1997). «On Torricelli's geometrical solution to a problem of Fermat». IMA Journal of Mathematics Applied in Business and Industry 8 (3): 215-224. MR 1473041. doi:10.1093/imaman/8.3.215. 
• Kuhn, Harold W. (1973). «A note on Fermat's problem». Mathematical Programming 4 (1): 98-107. doi:10.1007/BF01584648. 
• Lawera, Martin; Thompson, James R. (1993). «Some problems of estimation and testing in multivariate statistical process control». Proceedings of the 38th Conference on the Design of Experiments. U.S. Army Research Office Report. 93-2. pp. 99-126. 
• Lopuhaä, Hendrick P.; Rousseeuw, Peter J. (1991). «Breakdown points of affine equivariant estimators of multivariate location and covariance matrices». Annals of Statistics 19 (1): 229-248. JSTOR 2241852. doi:10.1214/aos/1176347978. 
• Nie, Jiawang; Parrilo, Pablo A.; Sturmfels, Bernd (2008). «Semidefinite representation of the k-ellipse». En Dickenstein, A.; Schreyer, F.-O.; Sommese, A.J., eds. Algorithms in Algebraic Geometry. IMA Volumes in Mathematics and its Applications 146. Springer-Verlag. pp. 117-132. arXiv:math/0702005. 
• Ostresh, L. (1978). «Convergence of a Class of Iterative Methods for Solving Weber Location Problem». Operations Research 26 (4): 597-609. doi:10.1287/opre.26.4.597. 
• Plastria, Frank (2006). «Four-point Fermat location problems revisited. New proofs and extensions of old results». IMA Journal of Management Mathematics 17 (4): 387-396. Zbl 1126.90046. doi:10.1093/imaman/dpl007. .
• Spain, P. G. (1996). «The Fermat Point of a Triangle». Mathematics Magazine 69 (2): 131-133. JSTOR 2690672?origin=pubexport. MR 1573157. 
• Vardi, Yehuda; Zhang, Cun-Hui (2000). «The multivariate L₁-median and associated data depth». Proceedings of the National Academy of Sciences of the United States of America 97 (4): 1423-1426 (electronic). MR 1740461. PMC 26449. doi:10.1073/pnas.97.4.1423. 
• Weber, Alfred (1909). Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes. Tübingen: Mohr. 
• Wesolowsky, G. (1993). «The Weber problem: History and perspective». Location Science 1: 5-23. 
• Weiszfeld, E. (1937). «Sur le point pour lequel la somme des distances de n points donnes est minimum». Tohoku Mathematical Journal 43: 355-386. 

• Datos: Q5535496