Mediana geométrica

Punto que minimiza la distancia a otros puntos

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,[1]mediana espacial,[2]punto minisum euclidiano,[2]​ o punto de Torricelli.[3]

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

La mediana geométrica es un estimador importante de localización en estadística,[4]​ donde así mismo se la conoce como el estimador1.[5]​ 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.[6]

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.[7]​ Su solución ahora se conoce como el punto de Fermat del triángulo formado por los tres puntos de la muestra.[8]​ 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.[2]​ Algunas fuentes llaman al problema de Weber el problema de Fermat-Weber,[9]​ pero en otros casos se usa este nombre para el problema de la mediana geométrica no ponderada.[10]

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

editar

Formalmente, para un conjunto dado de m puntos   con cada  , la mediana geométrica se define como

 

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

Propiedades

editar
  • 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.[11]
  • La mediana geométrica es única siempre que los puntos no sean colineales.[12]
  • La mediana geométrica es equivariante para lastransformaciones de semejanza en el espacio euclideo, incluyendo traslaciones y rotaciones.[5][11]​ 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.[5]
  • La mediana geométrica tiene una robustez estadística de 0,5.[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

editar
  • 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.[11]​ 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.[13]

Computación

editar

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.[14]

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,[15]​ es una forma de mínimos cuadrados 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,

 

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.[12]

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

editar

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

 

Esto es equivalente a:

 

que está estrechamente relacionado con el algoritmo de Weiszfeld.

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

 

donde para xjy,

 

y para xj = y,

 

Una formulación equivalente de esta condición es

 

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

editar

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.[16]​ Sea   una variedad riemanniana con la función de distancia correspondiente  , y sean   y   los pesos sumados a 1, y hágase que   sean   observaciones de  . A continuación se define la mediana geométrica ponderada   (o mediana de Fréchet ponderada) de los puntos de datos como

 .

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

Referencias

editar
  1. El problema más general de la k-mediana pregunta por la ubicación de los centros de k agregados que minimizan la suma de distancias desde cada punto de muestra hasta su centro más cercano.
  2. a b c Drezner et al. (2002)
  3. Cieslik, 2006.
  4. Lawera y Thompson, 1993.
  5. a b c d Lopuhaä y Rousseeuw (1991)
  6. Eiselt y Marianov, 2011.
  7. Krarup y Vajda, 1997.
  8. Spain, 1996.
  9. Brimberg, 1995.
  10. Bose, Maheshwari y Morin, 2003.
  11. a b c Haldane (1948)
  12. a b Vardi y Zhang (2000)
  13. Cieslik (2006), p. 6;Plastria (2006). El caso convexo fue originalmente probado por Giovanni Fagnano.
  14. Bajaj (1986);Bajaj (1988). Earlier,Cockayne y Melzak (1969) probó que el punto de Steiner para 5 puntos en el plano no puede ser construido solo con regla y compás.
  15. Weiszfeld (1937);Kuhn (1973);Chandrasekaran y Tamir (1989).
  16. Fletcher, Venkatasubramanian y Joshi, 2009.

Bibliografía

editar