Centro geométrico

El centro geométrico de un conjunto discreto de puntos en el espacio euclidiano (en términos estadísticos - muestras) es el punto en el que se minimiza la suma de las distancias a los puntos del conjunto. El centro geométrico generaliza la mediana a una estadística matemática que minimiza las distancias en una muestra de datos unidimensional. Así, el centro geométrico refleja la tendencia central en los espacios de gran dimensión. El concepto también se conoce con los nombres 1-mediana [1] , espacial mediana [2] o punto Torricelli [3] .

El centro geométrico es un importante estimador de desplazamiento en estadística [4] , en el que este concepto se conoce como puntuación L 1 [5] . Encontrar el centro geométrico también es una tarea estándar al colocar objetos , donde se modela la ubicación de los objetos (producción o consumo) para minimizar los costos de transporte [6]

Un caso especial del problema de tres puntos en el plano (es decir, m = 3 y n = 2 en los términos que se describen a continuación) se describe a veces como el problema de Fermat. Surge en la construcción de árboles mínimos de Steiner y fue planteado por primera vez como un problema por Pierre de Fermat y resuelto por Evangelista Torricelli [7] . La solución a este problema ahora se conoce como el punto de Fermat del triángulo [8] . A su vez, la búsqueda del centro geométrico puede generalizarse al problema de minimizar la suma de distancias ponderadas . Este problema se conoce como el problema de Weber porque Alfred Weber discutió este problema en un libro de 1909 sobre la colocación de objetos [2] . Algunas fuentes usan el nombre de problema de Fermat-Weber [9] en su lugar , pero algunas fuentes usan el mismo nombre para el problema no ponderado [10]

Vesolovsky [11] hizo un estudio del problema del centro geométrico. Véase el artículo de Fekete, Michel y Boyer [12] para una discusión sobre la generalización del problema al caso de conjuntos no discretos.

Definición

Formalmente, dado un conjunto que contiene m puntos , donde todos , el centro geométrico se define como $x_{1},x_{2},\puntos,x_{m}\,$ $x_{i}\en \mathbb {R} ^{n}$

centro geométrico

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

Tenga en cuenta que aquí arg min significa el valor del argumento en el que se alcanza la suma mínima. Este es el punto para el cual la suma de todas las distancias euclidianas a , es mínima. $y$ $y$ $x_{yo}$

Propiedades

Para el caso de un espacio unidimensional, la mediana es el centro geométrico (si hay un número par de puntos, el centro geométrico puede no ser único). Esto se debe a que la mediana unidimensional minimiza la suma de las distancias a los puntos [13] .
El centro geométrico es el único para todos los casos donde los puntos no son colineales [14] .
El centro geométrico es equivariante para semejanza euclidiana , traslación y rotación [5] [13] . Esto significa que obtendrá el mismo resultado si encuentra la imagen del centro durante la transformación, o si aplica la misma transformación a todos los puntos de muestra y luego encuentra el centro geométrico. Esta propiedad se deriva del hecho de que el centro geométrico se determina únicamente sobre la base de distancias por pares y no depende del sistema de coordenadas cartesianas ortogonales . Por el contrario, la mediana por componentes para datos multivariados durante la rotación, en general, no es invariante y depende de la elección de las coordenadas [5] .
El centro geométrico tiene un punto de ruptura 0.5 [5] . Es decir, hasta la mitad de los datos de la muestra pueden no ser confiables, pero el centro geométrico de la muestra sigue siendo una estimación estable de la posición de los datos no corruptos.

Ocasiones especiales

Para 3 puntos ( no colineales ) , si alguna de las esquinas de un triángulo con vértices en esos puntos es de 120° o más, entonces el centro geométrico es el vértice de esa esquina. Si todos los ángulos miden menos de 120°, el centro geométrico es el punto dentro del triángulo que forma un ángulo de 120° con cualquier par de vértices del triángulo [13] . Este punto se conoce como el punto de Fermat del triángulo (si tres puntos son colineales, entonces el centro geométrico coincide con el punto que se encuentra entre los otros dos).
Para 4 puntos coplanares , si uno de los cuatro puntos está dentro del triángulo formado por los otros tres puntos, el lugar geométrico será ese punto interior. De lo contrario, cuatro puntos forman un cuadrilátero convexo , y el punto de intersección de las diagonales del cuadrilátero sirve como centro geométrico. El centro geométrico de cuatro puntos coplanares es el mismo que el único punto de Radon para cuatro puntos [15] .

Cálculo

Aunque el concepto de centro geométrico es fácil de entender, su cálculo es difícil. El centroide de un triángulo (es decir, su centro de masa ), definido de manera similar al centro geométrico como la minimización de la suma de las distancias al cuadrado a cada punto, se puede obtener utilizando fórmulas simples: sus coordenadas son la media aritmética de las coordenadas de los puntos. Sin embargo, no se conoce una fórmula tan simple para el centro geométrico. Incluso se ha demostrado que no existe una fórmula explícita ni un algoritmo exacto que utilice únicamente operaciones aritméticas y de base. Por lo tanto, solo hay aproximaciones para resolver este problema [16] .

Sin embargo, es posible calcular una aproximación al centro geométrico utilizando un procedimiento iterativo en el que cada paso da una aproximación más precisa. Procedimientos de este tipo pueden derivarse del hecho de que la suma de distancias a puntos de muestra es una función convexa , ya que la distancia a cada punto de muestra es una función convexa, y la suma de funciones convexas también es una función convexa. Por lo tanto, el procedimiento para reducir la suma de distancias no puede caer en el óptimo local .

Uno de estos enfoques es el algoritmo de Weisfeld ( André Weisfeld ) [17] [18] [19] que es un tipo de método iterativo de mínimos cuadrados ponderados con pesos variables. Este algoritmo establece un conjunto de pesos que son inversamente proporcionales a las distancias a la aproximación actual y calcula una nueva aproximación que es el promedio ponderado de los puntos de muestra de acuerdo con estos pesos. Eso es

\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).

El método converge desde casi todas las posiciones iniciales, pero puede fallar si la aproximación termina en uno de los puntos de muestra. El algoritmo se puede modificar de tal manera que converja para todos los puntos de partida [14] .

Bose, Mageshwari y Morin [10] describieron un procedimiento de optimización más sofisticado para encontrar una solución óptima aproximada a un problema dado. Como han demostrado Ne, Parrilo y Starmfils [20] , el problema puede considerarse como un problema de programación semidefinido .

Cohen, Lee, Miller y Pachoki [21] mostraron cómo calcular el centro geométrico con precisión arbitraria en un tiempo casi lineal.

Descripción del centro geométrico

Si el punto y es diferente de todos los puntos muestrales dados x j , entonces y es el centro geométrico si y solo si

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

En general, y es un centro geométrico si y sólo si existen vectores u j tales que

{\displaystyle 0=\sum_{j=1}^{m}u_{j))

donde para x j ≠ y ,

u_{j}={\frac {x_{j}-y}{\izquierda\|x_{j}-y\derecha\|}}

y para x j = y ,

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

Una formulación equivalente de esta condición

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

Generalizaciones

El centro geométrico se puede generalizar desde espacios euclidianos a variedades riemannianas generales (e incluso espacios métricos ) usando la misma idea que se usa para definir la media de Fréchet en variedades riemannianas [22] . Sea una variedad de Riemann con una función de distancia , sean pesos que suman 1 y sean observaciones de . Luego definimos el centro geométrico ponderado (o media ponderada de Fréchet) de los puntos de datos $METRO$ ${\ estilo de visualización d (\ cdot, \ cdot)}$ $w_{1},\ldots,w_{n}$ $norte$ $x_{1},\ldots,x_{n}$ $norte$ $METRO$ $metro$

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 cuál es el centro geométrico. $metro$

Notas

↑ El problema más general de la k -mediana pregunta sobre la posición de los k centros minimizando la suma de las distancias desde cada punto del conjunto hasta el centro más cercano.
↑ 1 2 Drezner, Klamroth, Schöbel, Wesolowsky, 2002 .
↑ Cieslik, 2006 .
↑ Lawera, Thompson, 1993 .
↑ 1 2 3 4 Lopuhaä, Rousseeuw, 1991 .
↑ Eiselt, Marianov, 2011 .
↑ Krarup, Vajda, 1997 .
↑ España, 1996 .
↑ Brimberg, 1995 .
↑ 1 2 Bose, Maheshwari, Morin, 2003 .
↑ Wesolowsky, 1993 .
↑ Fekete, Mitchell, Beurer, 2005 .
↑ 1 2 3 Haldane, 1948 .
↑ 12 Vardi, Zhang, 2000 .
↑ Cieslik, 2006 ; Plastería, 2006 . El caso convexo fue probado por primera vez por Giovanni Fagnano .
↑ Bajaj, 1986 ; Bajaj, 1988 . Anteriormente, Cockayne y Melzak Cockayne, Melzak, 1969 demostró que el punto de Steiner para 5 puntos en el plano no se puede construir utilizando un compás y una regla.
↑ Weiszfeld, 1937 .
↑ Kuhn, 1973 .
↑ Chandrasekaran, Tamir, 1989 .
↑ Nie, Parrilo, Sturmfels, 2008 .
↑ Cohen, Lee, Miller, Pachocki, Sidford, 2016 .
↑ Fletcher, Venkatasubramanian, Joshi, 2009 .

Literatura

Chandrajit Bajaj. Demostración de la no solucionabilidad de los algoritmos geométricos: una aplicación de polinomios de factorización // Journal of Symbolic Computation . - 1986. - T. 2 . — S. 99–102 . - doi : 10.1016/S0747-7171(86)80015-3 .
El grado algebraico de los problemas de optimización geométrica // Geometría Discreta y Computacional . - 1988. - T. 3 . — S. 177–191 . -doi : 10.1007/ BF02187906 .
Aproximaciones rápidas para sumas de distancias, agrupamiento y el problema de Fermat-Weber // Geometría Computacional: Teoría y Aplicaciones . - 2003. - T. 24 , núm. 3 . — S. 135–146 . - doi : 10.1016/S0925-7721(02)00102-5 .
J. Brimberg. Revisión del problema de ubicación de Fermat-Weber // Programación matemática . - 1995. - T. 71 , núm. 1 serie A._ _ — S. 71–76 . -doi : 10.1007/ BF01592245 .
R. Chandrasekaran, A. Tamir. Preguntas abiertas sobre el algoritmo de Weiszfeld para el problema de ubicación de Fermat-Weber // Programación matemática . - 1989. - T. 44 . — S. 293–295 . -doi : 10.1007/ BF01587094 .
Dietmar Cieslik. Conectividad más corta: una introducción a las aplicaciones en filogenia . - Springer, 2006. - Vol. 17. - ISBN 9780387235394 .
EJ Cockayne, ZA Melzak. Construibilidad euclidiana en problemas de minimización de grafos // Revista Matemáticas . - 1969. - T. 42 , núm. 4 . — S. 206–208 . -doi : 10.2307/ 2688541 . — .
Michael Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, Aaron Sidford. Mediana geométrica en tiempo casi lineal // Proc. 48º Simposio de Teoría de la Computación (STOC 2016). - Asociación de Maquinaria de Computación , 2016.
Zvi Drezner, Kathrin Klamroth, Anita Schöbel, George O. Wesolowsky. El problema de Weber // Ubicación de la instalación: aplicaciones y teoría . - Springer, Berlín, 2002. - S. 1-36.
HA Eiselt, Vladimir Marianov. Fundamentos del Análisis de Localización . - Springer, 2011. - T. 155. - P. 6. - (Serie Internacional en Investigación de Operaciones y Ciencias de la Gestión). — ISBN 9781441975720 .
Sandor P. Fekete, Joseph SB Mitchell, Karin Beurer. Sobre el problema continuo de Fermat-Weber // Investigación de Operaciones . - 2005. - T. 53 , núm. 1 . — S. 61–76 . -doi : 10.1287/ opre.1040.0137 . — arXiv : cs.CG/0310027 .
P. Thomas Fletcher, Suresh Venkatasubramanian, Sarang Joshi. La mediana geométrica en variedades de Riemann con aplicación a la estimación robusta de atlas // NeuroImage. - 2009. - T. 45 , núm. 1 suplemento — S. s143–s152 . -doi : 10.1016/ j.neuroimage.2008.10.052 . —PMID 19056498 .
JBS Haldane. Nota sobre la mediana de una distribución multivariante // Biometrika. - 1948. - T. 35 , núm. 3–4 . — S. 414–417 . -doi : 10.1093 / biomet/35.3-4.414 .
Jakob Krarup, Steven Vajda. Sobre la solución geométrica de Torricelli a un problema de Fermat // Revista IMA de Matemática Aplicada a la Empresa ya la Industria. - 1997. - T. 8 , núm. 3 . — S. 215–224 . -doi : 10.1093 / imaman/8.3.215 .
Harold W. Kuhn. Una nota sobre el problema de Fermat // Programación Matemática . - 1973. - T. 4 , núm. 1 . — P. 98–107 . -doi : 10.1007/ BF01584648 .
Martín Lawera, James R. Thompson. Algunos problemas de estimación y prueba en el control de procesos estadísticos multivariados // Actas de la 38ª Conferencia sobre el Diseño de Experimentos . - 1993. - T. 93-2. — págs. 99–126.
Hendrick P. Lopuhaä, Peter J. Rousseeuw. Puntos de ruptura de estimadores equivariantes afines de matrices de covarianza y ubicación multivariante // Annals of Statistics . - 1991. - T. 19 , núm. 1 . — S. 229–248 . -doi : 10.1214 / aos/1176347978 . — .
Jiawang Nie, Pablo A. Parrilo, Bernd Sturmfels. Algoritmos en Geometría Algebraica / A. Dickenstein, F.-O. Schreyer, AJ Sommese. - Springer-Verlag, 2008. - T. 146. - S. 117-132. - (Volúmenes IMA en Matemáticas y sus Aplicaciones).
L. Ostresh. Convergencia de una clase de métodos iterativos para resolver el problema de ubicación de Weber // Investigación de operaciones . - 1978. - T. 26 , núm. 4 . — S. 597–609 . doi : 10.1287 / opre.26.4.597 .
Plastilina Franca. Revisión de los problemas de ubicación de Fermat de cuatro puntos. Nuevas pruebas y extensiones de resultados antiguos // IMA Journal of Management Mathematics. - 2006. - T. 17 , núm. 4 . — S. 387–396 . -doi : 10.1093 / imaman/dpl007 .
PG España. El punto de Fermat de un triángulo // Revista de matemáticas. - 1996. - T. 69 , núm. 2 . — S. 131–133 . — .
Yehuda Vardi, Cun-Hui Zhang. La multivariante L 1 -mediana y profundidad de datos asociada // Actas de la Academia Nacional de Ciencias de los Estados Unidos de América. - 2000. - T. 97 , núm. 4 . — S. 1423–1426 (electrónico) . -doi : 10.1073/ pnas.97.4.1423 .
Alfredo Weber. Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes. — Tubinga: Mohr, 1909.
G. Wesolowsky. El problema de Weber: Historia y perspectiva // Ciencias de la localización. - 1993. - T. 1 . — Pág. 5–23 .
E. Weiszfeld. Sur le point pour lequel la somme des distancias de n puntos donnes est mínimo // Tohoku Mathematical Journal . - 1937. - T. 43 . — S. 355–386 .

Significar
Matemáticas	Potencia media ( ponderada ) Significado armonico ponderado significado geometrico ponderado Promedio ponderado media cuadrática cúbico promedio media móvil Media aritmético-geométrica Función Media media de Kolmogorov
Geometría	centro geométrico Baricentro
Teoría de la probabilidad y estadística matemática	Media Winsorizada muestra promedio Valor esperado Mediana Moda Desviación Estándar Media truncada expectativa condicional
Tecnologías de la información	medoide método de k-mediana
teoremas	Primer teorema de la media Segundo teorema de la media Desigualdad sobre la media aritmética, geométrica y armónica
Otro	Métricas del centro de distribución