Геометрический центр

Не следует путать со средним геометрическим.

Геометрический центр дискретного множества точек евклидова пространства (говоря статистическим языком — выборки) — это точка, в которой минимизируется сумма расстояний до точек множества. Геометрический центр обобщает медиану в математической статистике, которая минимизирует расстояния в одномерной выборке данных. Таким образом, геометрический центр отражает центральную тенденцию в пространствах высокой размерности. Понятие известно также по названиям 1-медиана , пространственная медиана, или точка Торричелли.

Геометрический центр является важной оценочной функцией сдвига в статистике, в которой это понятие известно как оценка L₁. Поиск геометрического центра является также стандартной задачей при размещении объектов, где моделируется расположение объектов (производства или потребления) с целью минимизации транспортных расходов

Специальный случай задачи для трёх точек на плоскости (то есть m=3 и n=2 в терминах, описанных ниже) иногда описывается как задача Ферма. Она возникает при построении минимальных деревьев Штейнера и впервые была поставлена как задача Пьером Ферма, а решил её Эванджелиста Торричелли. Решение этой задачи известно теперь как точка Ферма треугольника. В свою очередь, поиск геометрического центра можно обобщить до задачи минимизации суммы взвешенных расстояний. Эта задача известна как задача Вебера, поскольку Альфред Вебер обсуждал эту задачу в книге 1909 года по вопросам размещения объектов. Некоторые источники вместо этого используют название задача Ферма – Вебера, но некоторые источники используют то же название для невзвешенной задачи

Весоловский дал обзор задачи геометрического центра. Смотрите статью Фекете, Мичела и Бойера с обсуждением обобщения задачи для случая недискретных множеств.

Определение

Формально, если задано множество, содержащее m точек $x_{1},x_{2},\dots ,x_{m}\,$, где все $x_{i}\in \mathbb {R} ^{n}$, геометрический центр определяется как

Геометрический центр $={\underset {y\in \mathbb {R} ^{n}}{\operatorname {arg\,min} }}\sum _{i=1}^{m}\left\|x_{i}-y\right\|_{2}$

Заметьте, что здесь arg min означает значение аргумента $y$, на котором достигается минимальная сумма. Это точка $y$, для которой сумма всех евклидовых расстояний до $x_{i}$, минимально.

Свойства

• Для случая одномерного пространства медиана является геометрическим центром (если точек чётное число, геометрический центр может быть не единственным). Это потому, что одномерная медиана минимизирует сумму расстояний до точек.
• Геометрический центр является единственным для всех случаев, когда точки не коллинеарны.
• Геометрический центр эквивариантен для евклидового подобия, параллельного переноса и поворота. Это означает, что получится один и тот же результат, если найти образ центра при преобразовании, либо, применив то же преобразование ко всем точкам выборки, а затем уже найдя геометрический центр. Это свойство вытекает из факта, что геометрический центр определяется лишь исходя из попарных расстояний и не зависит от системы ортогональных декартовых координат. Для контраста, покомпонентная медиана для многомерных данных при вращении, в общем случае, не является инвариантом и зависит от выбора координат.
• Геометрический центр имеет точку срыва 0,5. То есть до половины данных выборки могут быть недостоверными, но геометрический центр выборки остаётся устойчивой оценкой положения неиспорченных данных.

Специальные случаи

• Для 3 (неколлинеарных) точек, если какой-либо из углов треугольника с вершинами в этих точках составляет 120° или больше, то геометрический центр — это вершина этого угла. Если все углы меньше 120°, геометрический центр — это точка внутри треугольника, которая составляет угол 120° с любой парой вершин треугольника. Эта точка известна как точка Ферма треугольника (если три точки коллинеарны, то геометрический центр совпадает с точкой, которая лежит между двумя другими).
• Для 4 копланарных точек, если одна из четырёх точек лежит внутри треугольника, образованного тремя другими точками, геометрическим местом будет эта внутренняя точка. В противном случае четыре точки образуют выпуклый четырёхугольник, и геометрическим центром служит точка пересечения диагоналей четырёхугольника. Геометрический центр четырёх копланарных точек — это то же самое, что и единственная точка Радона для четырёх точек.

Вычисление

Несмотря на то, что понятие геометрического центра является простым для понимания, его вычисление вызывает трудности. Центроид треугольника (то есть его центр масс), определяемый аналогично геометрическому центру как минимизация суммы квадратов расстояний до каждой точки, может быть получен с помощью простых формул — его координаты являются средним арифметическим координат точек. Однако такой простой формулы для геометрического центра не известно. Даже было показано, что не существует ни явной формулы, ни точного алгоритма, использующего только арифметические операции и операции извлечения корней. Таким образом, существуют только аппроксимации для решения данной задачи.

Однако можно вычислить приближение к геометрическому центру, используя итеративную процедуру, в которой каждый шаг даёт более точное приближение. Процедуры этого типа могут получены из того факта, что сумма расстояний до точек выборки является выпуклой функцией, поскольку расстояние до каждой точки выборки является выпуклой функцией, а сумма выпуклых функций также является выпуклой функцией. Таким образом, процедура уменьшения суммы расстояний не может попасть в локальный оптимум.

Один из подходов такого рода — алгоритм Вайсфельда (Андре Вайсфельд) является видом итерационного взвешенного метода наименьших квадратов с меняющимися весами. Этот алгоритм задаёт множество весов, которые обратно пропорциональны расстояниям до текущего приближения, и вычисляет новое приближение, являющееся средним взвешенным точек выборки согласно этим весам. То есть

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

Метод сходится почти со всех начальных положений, но может завершиться неудачей, если приближение оказывается в одной из точек выборки. Алгоритм можно модифицировать таким образом, что он будет сходиться для всех начальных точек.

Бозе, Магешвари и Морин описали более изощрённую процедуру оптимизации для поиска приблизительного оптимального решения данной задачи. Как показали Не, Паррило и Стармфилс, задачу можно представить как задачу полуопределённого программирования.

Коэн, Ли, Миллер и Пачоки показали, как вычислить геометрический центр с произвольной точностью за почти линейное время.

Описание геометрического центра

Если точка y отлична от всех заданных точек выборки x_j, то y является геометрическим центром тогда и только тогда, когда

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

Это эквивалентно

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

что тесно связано с алгоритмом Вайсфельда.

В общем случае y является геометрическим центром тогда и только тогда, когда существуют вектора u_j, такие, что

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

где для x_j ≠ y,

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

а для x_j=y,

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

Эквивалентная формулировка этого условия

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

Обобщения

Геометрический центр можно обобщить с евклидовых пространств до общих римановых многообразий (и даже метрических пространств), используя ту же идею, что используется для определения среднего Фреше на римановых многообразиях. Пусть $M$ — риманово многообразие с функцией расстояния $d(\cdot ,\cdot )$, пусть $w_{1},\ldots ,w_{n}$ — $n$ весов, в сумме дающих 1, и пусть $x_{1},\ldots ,x_{n}$ — $n$ наблюдений из $M$. Тогда мы определяем взвешенный геометрический центр $m$ (или взвешенное среднее Фреше) точек данных

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

Если все веса равны, мы говорим, что $m$ является геометрическим центром.