mediana geométrica

En geometría , la mediana geométrica de un conjunto discreto de puntos en un espacio euclidiano es el punto que minimiza la suma de las distancias a los puntos de la muestra. Esto generaliza la mediana , que tiene la propiedad de minimizar la suma de distancias o diferencias absolutas para datos unidimensionales. También se conoce como mediana espacial , ^{[ 1 ]} punto de minisuma 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 localización de instalaciones , es decir, localizar una instalación para minimizar el costo del 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 L2 de las muestras. ^{[ 5 ]} Se compara con la media, que minimiza la suma de las distancias L2 _al cuadrado ; y con la mediana por coordenadas, que minimiza la suma de las _distancias L1 . El problema más general de la k -mediana pide la ubicación de k centros de clúster que minimicen la suma de _las distancias L2 desde cada punto de muestra hasta 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 que sigue) también se conoce a veces como el 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 se conoce ahora 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 por la discusión de Alfred Weber sobre el problema en su libro de 1909 sobre la localización de instalaciones. ^{[ 1 ]} 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 una revisión del problema de la mediana geométrica. Véase Fekete, Mitchell y Beurer (2005) para generalizaciones del problema a conjuntos de puntos no discretos.

Formalmente, para un conjunto dado de m puntos${\displaystyle \mathbb {X} ^{m}=x_{1},x_{2},\dots ,x_{m}\,}$con cada${\displaystyle x_{i}\in \mathbb {R} ^{n}}$La mediana geométrica se define como el minimizador de la suma de las _distancias L2 :

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

• 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 las distancias a los puntos. (Más precisamente, si los puntos son p ₁ , ..., p _n , en ese orden, la mediana geométrica es el punto medio.${\displaystyle p_{(n+1)/2}}$si n es impar, pero no está determinado de forma única si n es par, cuando puede ser cualquier punto en el segmento de línea entre los dos puntos medios.${\displaystyle p_{n/2}}$y${\displaystyle p_{(n/2)+1}}$.) ^{[ 10 ] [ 11 ]}
• La mediana geométrica es única siempre que los puntos no sean colineales . ^{[ 12 ]}
• La mediana geométrica es equivariante para transformaciones de similitud euclidiana , incluyendo traslación y 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 calculando la mediana geométrica de los datos transformados. Esta propiedad se deriva del hecho de que la mediana geométrica se define únicamente a partir de distancias por pares y no depende del sistema de coordenadas cartesianas ortogonales con el que se representan los datos de muestra. En contraste, la mediana por componentes para un conjunto de datos multivariados no es, en general, invariante a la rotación ni 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 la muestra pueden estar corruptos arbitrariamente, y la mediana de las muestras seguirá proporcionando un estimador robusto para la ubicación de los datos no corruptos.

• Para tres puntos (no colineales ), si cualquier ángulo del triángulo formado por dichos puntos es de 120° o más, 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 uno de los tres pares de vértices del triángulo. ^{[ 10 ]} Este punto 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 intermedio entre los otros dos puntos, como en el caso de una mediana unidimensional).
• Para cuatro puntos coplanares , si uno de ellos se encuentra dentro del triángulo formado por los otros tres, 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 intersección de las diagonales del cuadrilátero. La mediana geométrica de cuatro puntos coplanares coincide con el único punto de Radon de los cuatro puntos. ^{[ 14 ]}

A pesar de que la mediana geométrica es un concepto fácil de entender, su cálculo presenta un desafío. El centroide o centro de masa , 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 hallar mediante una fórmula sencilla —sus coordenadas son el promedio de las coordenadas de los puntos—, pero se ha demostrado que, en general, no existe una fórmula explícita ni un algoritmo exacto que involucre únicamente operaciones aritméticas y raíces k -ésimas para la mediana geométrica. Por lo tanto, bajo este modelo de cálculo , solo 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. Los procedimientos de este tipo se derivan 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 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 a los puntos de la 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 fallar cuando una de sus estimaciones coincide con alguno de los puntos dados. Puede modificarse para manejar estos casos y así lograr la convergencia 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 et al. (2016) muestran cómo calcular la mediana geométrica con precisión arbitraria en tiempo casi lineal . Cabe señalar también que el problema puede formularse como el programa del cono de segundo orden.

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

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

El marco de Varignon es un dispositivo de computación analógica que (ignorando problemas del mundo real como la fricción) puede encontrar la mediana geométrica. ^{[ 17 ]}

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 considerarse 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 pase por y , tiene la misma suma de direcciones positivas desde y en sentido opuesto a cada lado. En el caso unidimensional, el hiperplano es el punto y mismo, y la suma de direcciones se simplifica a la medida de conteo (dirigida).

La mediana geométrica puede generalizarse de espacios euclidianos a variedades riemannianas generales (e incluso espacios métricos ) utilizando la misma idea que se usa para definir la media de Fréchet en una variedad riemanniana. ^{[ 18 ] [ 19 ]} Sea${\displaystyle M}$sea ​​una variedad riemanniana con función de distancia correspondiente${\displaystyle d(\cdot ,\cdot )}$, dejar${\displaystyle w_{1},\ldots,w_{n}}$ser${\displaystyle n}$pesos no negativos, y dejemos${\displaystyle x_{1},\ldots ,x_{n}}$ ser${\displaystyle n}$observaciones de${\displaystyle M}$. Luego definimos la mediana geométrica ponderada${\displaystyle m}$(o mediana de Fréchet ponderada) de los puntos de datos como cualquier solución de

${\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, simplemente decimos que${\displaystyle m}$es la mediana geométrica.

• Medoid
• desviación absoluta mediana geométrica
• Punto de Fermat-Torricelli
• Punto central (por ejemplo, la mediana de Tukey)