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 masa .

En geometría , la mediana geométrica de un conjunto discreto de puntos muestrales en un espacio euclidiano es el punto que minimiza la suma de distancias a los puntos muestrales. Esto generaliza la mediana , que tiene la propiedad de minimizar la suma de distancias para datos unidimensionales, y proporciona una tendencia central en dimensiones superiores. También se la conoce como mediana espacial , ^[1] punto minisum euclidiano , ^[1] punto de Torricelli , ^[2] o 1-mediana .

La mediana geométrica es un importante estimador de ubicación en estadística, ^[3] porque minimiza la suma de las distancias L 2 de las muestras. ^[4] 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 ₁ . También es un problema estándar en ubicación de instalaciones , donde modela el problema de ubicar una instalación para minimizar el costo de transporte. ^{[5] El} problema más general de k -mediana solicita la ubicación de k centros de conglomerados minimizando la suma de L ₂ distancias desde cada punto de muestra hasta su centro más cercano.

El caso especial del problema de tres puntos en el plano (es decir, m = 3 y n = 2 en la definición siguiente) a veces también se conoce como problema de Fermat ; surge en la construcción de árboles 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 muestrales. ^[7] La ​​mediana geométrica puede, a su vez, generalizarse al problema de minimizar la suma de distancias ponderadas , conocido como problema de Weber después de la discusión de Alfred Weber sobre el problema en su libro de 1909 sobre ubicación de instalaciones. ^[1] En cambio, algunas fuentes 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 de n dimensiones desde donde la suma de todas las distancias euclidianas a '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 univariada también minimiza la suma de 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 unívocamente 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 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 deriva del hecho de que la mediana geométrica se define sólo a partir de distancias por pares y no depende del sistema de coordenadas cartesianas ortogonales mediante el cual se representan los datos de muestra. Por el contrario, la mediana por componentes para un conjunto de datos multivariado no es, en general, invariante de rotación, ni es independiente de la elección de las coordenadas. ^[13]
• La mediana geométrica tiene un punto de ruptura de 0,5. ^[13] Es decir, hasta la mitad de los datos de la muestra pueden estar corruptos arbitrariamente, y la mediana de las muestras seguirá proporcionando un estimador sólido de la ubicación de los datos no corruptos.

Casos especiales

• Para 3 puntos (no colineales ), si algún á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] Este también se conoce como 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. 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 coplanares es la misma que el único punto de radón de los cuatro puntos. ^[14]

Cálculo

A pesar de que la mediana geométrica es un concepto fácil de entender, calcularlo plantea un desafío. El centroide o centro de masa , definido de manera similar a la mediana geométrica como minimizando 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 tiene Se ha demostrado que no puede existir en general ninguna fórmula explícita , ni un algoritmo exacto que incluya sólo operaciones aritméticas y k -ésimas raíces, para la mediana geométrica. Por lo tanto, bajo este modelo de cálculo sólo son posibles aproximaciones numéricas o simbólicas a la solución de este problema . ^[15]

Sin embargo, es sencillo calcular una aproximación a la mediana geométrica mediante un procedimiento iterativo en el que cada paso produce una aproximación más precisa. Procedimientos de este tipo se pueden derivar del hecho de que la suma de distancias a los puntos muestrales es una función convexa , ya que la distancia a cada punto muestral es convexa y la suma de 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 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. Eso es,

${\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 converger cuando una de sus estimaciones cae en uno de los puntos dados. Se puede modificar 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 a este problema. Cohen y cols. (2016) muestran cómo calcular la mediana geométrica con precisión arbitraria en un tiempo casi lineal . Tenga en cuenta también que el problema se puede formular 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 polinómico 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 sólo si satisface:

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

Esto equivale 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 sólo 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 de la mediana, en el sentido de que cualquier partición de los puntos, en particular la inducida por cualquier hiperplano que pasa por y , tiene la misma y opuesta suma 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 desde 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 de Riemann con la función de distancia correspondiente , sean pesos que sumen 1 y sean observaciones de . Luego definimos la mediana geométrica ponderada (o mediana de Fréchet ponderada) 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}$

Ver también

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

Notas

1. et al. (2002)
2. Cieslik (2006).
3. Lawera y Thompson (1993).
4. Esquivar y Rousson (1999).
5. Eiselt y Marianov (2011).
6. Krarup y Vajda (1997).
7. España (1996).
8. Brimberg (1995).
9. Bose, Maheshwari y Morin (2003).
10. Haldane (1948)
11. Reclamació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 probado originalmente por Giovanni Fagnano .
15. Bajaj (1986); Bajaj (1988). Anteriormente, Cockayne y Melzak (1969) demostraron que el punto 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 sólidas sobre variedades de Riemann a través de la mediana geométrica". Conferencia IEEE 2008 sobre visión por computadora y reconocimiento de patrones . Conferencia IEEE sobre visión por computadora y reconocimiento de patrones. Anchorage, Alaska, Estados Unidos: IEEE.
18. Fletcher, Venkatasubramanian y Joshi (2009).

Referencias

• Bajaj, Chanderjit (1986). "Demostración de la insolvencia de algoritmos geométricos: una aplicación de factorización de polinomios". Revista de Computación Simbólica . 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 .
• Bosé, 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). "Revisión del problema de ubicación de Fermat-Weber". Programación Matemática . 71 (1, Serie A): 71–76. doi :10.1007/BF01592245. SEÑOR  1362958. S2CID  206800756.
• Chandrasekaran, R.; Tamir, A. (1989). "Preguntas abiertas sobre el algoritmo de Weiszfeld para el problema de ubicació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. Saltador. pag. 3.ISBN​ 9780387235394.
• Cockayne, EJ; Melzak, ZA (1969). "Constructibilidad euclidiana en problemas de minimización de gráficos". Revista Matemáticas . 42 (4): 206–208. doi :10.2307/2688541. JSTOR  2688541.
• Cohen, Michael; Lee, Yin Tat; Molinero, Gary ; Pachocki, Jakub; Sidford, Aaron (2016). "Mediana geométrica en tiempo casi lineal" (PDF) . Proc. 48º Simposio de Teoría de la Computación (STOC 2016) . Asociación para Maquinaria de Computación . págs. 9-21. arXiv : 1606.05225 . doi :10.1145/2897518.2897647. ISBN 978-1-4503-4132-5.
• Esquivar, Yadolah; Rousson, Valentín (septiembre de 1999). "Media L ₁ multivariada ". Métrica . 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 las instalaciones: aplicaciones y teoría . Springer, Berlín. págs. 1–36. ISBN 9783540213451. SEÑOR  1933966.
• Eiselt, HA; Marianov, Vladimir (2011). Fundamentos del análisis de ubicación. Serie internacional en investigación de operaciones y ciencias de la gestión. vol. 155. Saltador. pag. 6.ISBN​ 9781441975720.
• Fekete, Sándor P.; Mitchell, Joseph SB ; Beurer, Karin (2005). "Sobre el continuo problema de Fermat-Weber". La 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 de las variedades de Riemann con aplicación a la estimación robusta de atlas". NeuroImagen . 45 (1 suplemento): 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 multivariada". 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". Revista IMA de Matemáticas Aplicadas en la Empresa y la Industria . 8 (3): 215–224. doi :10.1093/imaman/8.3.215. SEÑOR  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, Martín; Thompson, James R. (1993). «Algunos problemas de estimación y ensayo en control de procesos estadísticos multivariados» (PDF) . Actas de la 38ª Conferencia sobre Diseño de Experimentos . Informe de la Oficina de Investigación del Ejército de EE. UU. 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 covarianza y ubicación 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 : matemáticas/0702005 . Código Bib : 2007 matemáticas ...... 2005N. doi :10.1007/978-0-387-75155-9_7. ISBN 978-0-387-75154-2. S2CID  16558095.
• Ostresh, L. (1978). "Convergencia de una clase de métodos iterativos para resolver el problema de ubicación de Weber". La investigación de operaciones . 26 (4): 597–609. doi :10.1287/opre.26.4.597.
• Plastria, Frank (2006). "Revisión de los problemas de ubicación de Fermat de cuatro puntos. Nuevas pruebas y ampliaciones de resultados antiguos" (PDF) . Revista IMA de Matemáticas de Gestión . 17 (4): 387–396. doi :10.1093/imaman/dpl007. Zbl  1126.90046. Archivado desde el original (PDF) el 4 de marzo de 2016 . Consultado el 18 de mayo de 2014 ..
• España, PG (1996). "El punto de Fermat de un triángulo". Revista Matemáticas . 69 (2): 131-133. doi :10.1080/0025570X.1996.11996409. JSTOR  2690672?origin=pubexport. SEÑOR  1573157.
• Vardi, Yehuda; Zhang, Cun-Hui (2000). "La mediana L1 multivariante 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). Código Bib : 2000PNAS...97.1423V. doi : 10.1073/pnas.97.4.1423 . SEÑOR  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". Ciencia de la ubicación . 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.