Mediana geométrica

Punto que minimiza la suma de distancias a puntos dados

Ejemplo de mediana geométrica (en amarillo) de una serie de puntos. En azul el centro de masas .

En geometría , la mediana geométrica de un conjunto de puntos discretos en un espacio euclidiano es el punto que minimiza la suma de las distancias a los puntos de muestra. Esto generaliza la mediana , que tiene la propiedad de minimizar la suma de las distancias o las diferencias absolutas para datos unidimensionales. También se conoce como mediana espacial , ^[1] punto de mínima suma euclidiana , ^[1] punto de Torricelli , ^[2] o 1-mediana . Proporciona una medida de tendencia central en dimensiones superiores y es un problema estándar en la ubicación de instalaciones , es decir, la ubicación de una instalación para minimizar el costo de transporte. ^[3]

La mediana geométrica es un estimador importante de la ubicación en estadística, ^[4] porque minimiza la suma de las distancias L 2 de las muestras. ^[5] Debe compararse con la media, que minimiza la suma de las distancias L ₂ al cuadrado ; y con la mediana por coordenadas que minimiza la suma de las distancias L 1 . El problema k -mediana más general solicita la ubicación de los centros de los conglomerados k minimizando la suma de las distancias L ₂ desde cada punto de muestra a su centro más cercano.

El caso especial del problema para tres puntos en el plano (es decir, m = 3 y n = 2 en la definición a continuación) a veces también se conoce como problema de Fermat ; surge en la construcción de árboles de Steiner mínimos , y fue planteado originalmente como un problema por Pierre de Fermat y resuelto por Evangelista Torricelli . ^[6] Su solución ahora se conoce como el punto de Fermat del triángulo formado por los tres puntos de muestra. ^[7] La ​​mediana geométrica puede a su vez generalizarse al problema de minimizar la suma de distancias ponderadas , conocido como el problema de Weber después de la discusión del problema por parte de Alfred Weber en su libro de 1909 sobre la ubicación de las instalaciones. ^[1] Algunas fuentes, en cambio, llaman al problema de Weber el problema de Fermat-Weber , ^[8] pero otras usan este nombre para el problema de la mediana geométrica no ponderada. ^[9]

Wesolowsky (1993) ofrece un estudio 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 con cada uno , la mediana geométrica se define como la suma del minimizador de distancias L ₂ ${\displaystyle \mathbb {X} ^{m}=x_{1},x_{2},\dots ,x_{m}\,}$ ${\displaystyle x_{i}\in \mathbb {R} ^{n}}$

${\displaystyle {\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 que minimiza la suma. En este caso, es el punto en el espacio euclidiano n -dimensional desde donde la suma de todas las distancias euclidianas hasta el s es mínima. ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x_{i}}$

Propiedades

• Para el caso unidimensional, la mediana geométrica coincide con la mediana . Esto se debe a que la mediana univariante también minimiza la suma de las distancias desde los puntos. (Más precisamente, si los puntos son p ₁ , ..., p _n , en ese orden, la mediana geométrica es el punto medio si n es impar, pero no está determinada de manera única si n es par, cuando puede ser cualquier punto en el segmento de línea entre los dos puntos medios y .) ^{[10] [11]} ${\displaystyle p_{(n+1)/2}}$ ${\displaystyle p_{n/2}}$ ${\displaystyle p_{(n/2)+1}}$
• La mediana geométrica es única siempre que los puntos no sean colineales . ^[12]
• La mediana geométrica es equivariante para las transformaciones de similitud euclidiana , incluidas la traslación y la rotación . ^{[13] [10]} Esto significa que se obtendría el mismo resultado ya sea transformando la mediana geométrica o aplicando la misma transformación a los datos de muestra y encontrando 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 por pares y no depende del sistema de coordenadas cartesianas ortogonales por el que se representan los datos de muestra. Por el contrario, la mediana por componentes para un conjunto de datos multivariados no es en general invariante a la rotación ni es independiente de la elección de coordenadas. ^[13]
• La mediana geométrica tiene un punto de ruptura de 0,5. ^[13] Es decir, hasta la mitad de los datos de muestra pueden estar corruptos arbitrariamente, y la mediana de las muestras seguirá proporcionando un estimador sólido para la ubicación de los datos no corruptos.

Casos especiales

• Para 3 puntos (no colineales ), si cualquier ángulo del triángulo formado por esos puntos es de 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 de 120°, la mediana geométrica es el punto dentro del triángulo que subtiende un ángulo de 120° a cada tres pares de vértices del triángulo. ^[10] 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, entonces la mediana geométrica es el punto entre los otros dos puntos, como es el caso de una mediana unidimensional).
• Para 4 puntos coplanares , 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. En caso 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 coplanares es la misma que el único punto de Radon de los cuatro puntos. ^[14]

Cálculo

A pesar de que la mediana geométrica es un concepto fácil de entender, calcularla plantea un desafío. El centroide o centro de masas , definido de manera 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 en general una fórmula explícita ni un algoritmo exacto que involucre solo operaciones aritméticas y raíces k -ésimas para la mediana geométrica. Por lo tanto, solo son posibles aproximaciones numéricas o simbólicas a la solución de este problema bajo este modelo de cálculo . ^[15]

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 se pueden derivar del hecho de que la suma de las distancias a los puntos de muestra es una función convexa , ya que la distancia a cada punto de muestra es convexa y la suma de las funciones convexas sigue siendo convexa. Por lo tanto, los procedimientos que disminuyen la suma de las distancias en cada paso no pueden quedar atrapados en un óptimo local .

Un enfoque común de este tipo, llamado algoritmo de Weiszfeld en honor al trabajo de Endre Weiszfeld ^[16], es una forma de mínimos cuadrados reponderados iterativamente . Este algoritmo define un conjunto de ponderaciones que son inversamente proporcionales a las distancias desde la estimación actual hasta los puntos de muestra, y crea una nueva estimación que es el promedio ponderado de la muestra según estas ponderaciones. Es decir,

${\displaystyle \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).}$

Este método converge para casi todas las posiciones iniciales, pero puede no lograrlo cuando una de sus estimaciones cae en uno de los puntos dados. Puede modificarse para manejar estos casos de modo que converja para todos los puntos iniciales. ^[12]

Bose, Maheshwari y Morin (2003) describen procedimientos de optimización geométrica más sofisticados para encontrar soluciones aproximadamente óptimas para este problema. Cohen et al. (2016) muestran cómo calcular la mediana geométrica con precisión arbitraria en un tiempo casi lineal . Nótese también que el problema puede formularse como el programa de cono de segundo orden.

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

que se puede resolver en tiempo polinomial utilizando solucionadores de optimización comunes .

Caracterización de la mediana geométrica

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

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

Esto es equivalente a:

${\displaystyle \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),}$

que está estrechamente relacionado con el algoritmo de Weiszfeld.

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

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

donde para x _i ≠ y ,

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

y para x _i = y ,

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

Una formulación equivalente de esta condición es

${\displaystyle \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|.}$

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

Generalizaciones

La mediana geométrica se puede generalizar a partir de espacios euclidianos a variedades riemannianas generales (e incluso espacios métricos ) utilizando la misma idea que se utiliza para definir la media de Fréchet en una variedad riemanniana. ^{[17] [18]} Sea una variedad riemanniana con función de distancia correspondiente , sean pesos que suman 1 y sean observaciones de . Luego definimos la mediana geométrica ponderada (o mediana ponderada de Fréchet) de los puntos de datos como ${\displaystyle M}$ ${\displaystyle d(\cdot ,\cdot )}$ ${\displaystyle w_{1},\ldots ,w_{n}}$ ${\displaystyle n}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle m}$

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

Si todos los pesos son iguales, decimos simplemente que es la mediana geométrica. ${\displaystyle m}$

Véase también

• medoide
• Desviación absoluta de la mediana geométrica

Notas

1. Drezner y otros (2002)
2. Cieslik (2006).
3. Eiselt y Marianov (2011).
4. Lawera y Thompson (1993).
5. Dodge y Rousson (1999).
6. Krarup y Vajda (1997).
7. España (1996).
8. Berlín (1995).
9. Bose, Maheshwari y Morin (2003).
10. Haldane (1948)
11. Reivindicación 18.10, Métodos geométricos y problemas de optimización , V. Boltyanski, H. Martini, V. Soltan, Springer, 1999.
12. Vardi y Zhang (2000)
13. Lopuhaä y Rousseeuw (1991)
14. Cieslik (2006), pág. 6; Plastria (2006). El caso convexo fue demostrado originalmente por Giovanni Fagnano .
15. Bajaj (1986); Bajaj (1988). Anteriormente, Cockayne y Melzak (1969) demostraron que el punto de Steiner para 5 puntos en el plano no se puede construir con regla y compás.
16. Weiszfeld (1937); Kuhn (1973); Chandrasekaran y Tamir (1989).
17. Fletcher, P. Thomas; Venkatasubramanian, Suresh; Joshi, Sarang (23 de junio de 2008). "Estadísticas robustas sobre variedades de Riemann a través de la mediana geométrica". Conferencia IEEE de 2008 sobre visión artificial y reconocimiento de patrones . Conferencia IEEE sobre visión artificial y reconocimiento de patrones. Anchorage, AK, EE. UU.: IEEE.
18. Fletcher, Venkatasubramanian y Joshi (2009).

Referencias

• Bajaj, Chanderjit (1986). "Demostración de la no solubilidad de algoritmos geométricos: una aplicación de la factorización de polinomios". Journal of Symbolic Computation . 2 : 99–102. doi : 10.1016/S0747-7171(86)80015-3 .
• Bajaj, Chanderjit (1988). "El grado algebraico de los problemas de optimización geométrica". Geometría discreta y computacional . 3 (2): 177–191. doi : 10.1007/BF02187906 .
• Bose, Prosenjit ; Maheshwari, Anil; Morin, Pat (2003). "Aproximaciones rápidas para sumas de distancias, agrupamiento y el problema de Fermat–Weber". Geometría computacional: teoría y aplicaciones . 24 (3): 135–146. doi : 10.1016/S0925-7721(02)00102-5 .
• Brimberg, J. (1995). "El problema de localización de Fermat-Weber revisitado". Programación matemática . 71 (1, Ser. A): 71–76. doi :10.1007/BF01592245. MR  1362958. S2CID  206800756.
• Chandrasekaran, R.; Tamir, A. (1989). "Preguntas abiertas sobre el algoritmo de Weiszfeld para el problema de localización de Fermat-Weber". Programación matemática . Serie A. 44 (1–3): 293–295. doi :10.1007/BF01587094. S2CID  43224801.
• Cieslik, Dietmar (2006). Conectividad más corta: una introducción con aplicaciones en filogenia. Optimización combinatoria. Vol. 17. Springer. p. 3. ISBN 9780387235394.
• Cockayne, EJ; Melzak, ZA (1969). "Constructibilidad euclidiana en problemas de minimización de grafos". Revista de Matemáticas . 42 (4): 206–208. doi :10.2307/2688541. JSTOR  2688541.
• Cohen, Michael; Lee, Yin Tat; Miller, Gary ; Pachocki, Jakub; Sidford, Aaron (2016). "Mediana geométrica en tiempo casi lineal" (PDF) . Proc. 48.º Simposio sobre teoría de la computación (STOC 2016) . Association for Computing Machinery . págs. 9–21. arXiv : 1606.05225 . doi :10.1145/2897518.2897647. ISBN 978-1-4503-4132-5.
• Dodge, Yadolah; Rousson, Valentin (septiembre de 1999). " Media L ₁ multivariada ". Metrika . 49 (2): 127–134. doi :10.1007/s001840050029.
• Drezner, Zvi; Klamroth, Kathrin ; Schöbel, Anita ; Wesolowsky, George O. (2002). "El problema de Weber". Ubicación de la instalación: Aplicaciones y teoría . Springer, Berlín. pp. 1–36. ISBN 9783540213451.Señor 1933966  .
• Eiselt, HA; Marianov, Vladimir (2011). Fundamentos del análisis de localización. Serie internacional en investigación de operaciones y ciencia de la gestión. Vol. 155. Springer. pág. 6. ISBN 9781441975720.
• Fekete, Sándor P.; Mitchell, Joseph SB ; Beurer, Karin (2005). "Sobre el continuo problema de Fermat-Weber". Investigación de Operaciones . 53 (1): 61–76. arXiv : cs.CG/0310027 . doi :10.1287/opre.1040.0137. S2CID  1121.
• Fletcher, P. Thomas; Venkatasubramanian, Suresh; Joshi, Sarang (2009). "La mediana geométrica en variedades de Riemann con aplicación a la estimación robusta de atlas". NeuroImage . 45 (1 Suppl): s143–s152. doi :10.1016/j.neuroimage.2008.10.052. PMC  2735114 . PMID  19056498.
• Haldane, JBS (1948). "Nota sobre la mediana de una distribución multivariante". Biometrika . 35 (3–4): 414–417. doi :10.1093/biomet/35.3-4.414.
• Krarup, Jakob; Vajda, Steven (1997). "Sobre la solución geométrica de Torricelli a un problema de Fermat". IMA Journal of Mathematics Applied in Business and Industry . 8 (3): 215–224. doi :10.1093/imaman/8.3.215. MR  1473041.
• Kuhn, Harold W. (1973). "Una nota sobre el problema de Fermat". Programación matemática . 4 (1): 98–107. doi :10.1007/BF01584648. S2CID  22534094.
• Lawera, Martin; Thompson, James R. (1993). "Algunos problemas de estimación y prueba en el control estadístico de procesos multivariados" (PDF) . Actas de la 38.ª Conferencia sobre el diseño de experimentos . Informe de la Oficina de Investigación del Ejército de los Estados Unidos. Vol. 93–2. págs. 99–126. Archivado desde el original el 17 de mayo de 2014.
• Lopuhaä, Hendrick P.; Rousseeuw, Peter J. (1991). "Puntos de ruptura de estimadores equivariantes afines de matrices de ubicación y covarianza multivariadas". Anales de Estadística . 19 (1): 229–248. doi : 10.1214/aos/1176347978 . JSTOR  2241852.
• Nie, Jiawang; Parrilo, Pablo A.; Sturmfels, Bernd (2008). "Representación semidefinida de la k -elipse". En Dickenstein, A.; Schreyer, F.-O.; Sommese, AJ (eds.). Algoritmos en geometría algebraica . Volúmenes IMA en Matemáticas y sus aplicaciones. Vol. 146. Springer-Verlag. págs. 117–132. arXiv : math/0702005 . Bibcode :2007math......2005N. doi :10.1007/978-0-387-75155-9_7. ISBN: 978-0-387-75154-2.S2CID16558095  .​
• Ostresh, L. (1978). "Convergencia de una clase de métodos iterativos para resolver el problema de localización de Weber". Investigación de operaciones . 26 (4): 597–609. doi :10.1287/opre.26.4.597.
• Plastria, Frank (2006). "Revisión de los problemas de localización de Fermat en cuatro puntos. Nuevas pruebas y extensiones de resultados antiguos" (PDF) . IMA Journal of Management Mathematics . 17 (4): 387–396. doi :10.1093/imaman/dpl007. Zbl  1126.90046. Archivado desde el original (PDF) el 2016-03-04 . Consultado el 2014-05-18 ..
• España, PG (1996). "El punto de Fermat de un triángulo". Revista de Matemáticas . 69 (2): 131–133. doi :10.1080/0025570X.1996.11996409. JSTOR  2690672?origin=pubexport. MR  1573157.
• Vardi, Yehuda; Zhang, Cun-Hui (2000). "La mediana L1 multivariada y la profundidad de datos asociada". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 97 (4): 1423–1426 (electrónico). Bibcode :2000PNAS...97.1423V. doi : 10.1073/pnas.97.4.1423 . MR  1740461. PMC  26449 . PMID  10677477.
• Weber, Alfred (1909). Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes (en alemán). Tubinga: Mohr.
• Wesolowsky, G. (1993). "El problema de Weber: Historia y perspectiva". Location Science . 1 : 5–23.
• Weiszfeld, E. (1937). "Sur le point pour lequel la somme des distancias de n puntos donnes est mínimo". Revista Matemática Tohoku (en francés). 43 : 355–386.Traducido al inglés como Weiszfeld, E.; Plastria, Frank (abril de 2008). "Sobre el punto para el cual la suma de las distancias a n puntos dados es mínima". Anales de investigación de operaciones . 167 (1): 7–41. doi :10.1007/s10479-008-0352-z. S2CID  21000317.