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

Формально, если задано множество, содержащее m точек ${\displaystyle 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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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, такие, что

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

где для x_j ≠ y,

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

а для x_j=y,

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

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

${\displaystyle \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|.}$

Геометрический центр можно обобщить с евклидовых пространств до общих римановых многообразий (и даже метрических пространств), используя ту же идею, что используется для определения среднего Фреше на римановых многообразиях[22]. Пусть ${\displaystyle M}$ — риманово многообразие с функцией расстояния ${\displaystyle d(\cdot ,\cdot )}$, пусть ${\displaystyle w_{1},\ldots ,w_{n}}$ — ${\displaystyle n}$ весов, в сумме дающих 1, и пусть ${\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})}$.

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