Русская Википедия:Геометрический центр

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

Определение

Формально, если задано множество, содержащее m точек <math>x_1, x_2, \dots, x_m\,</math>, где все <math>x_i \in \mathbb{R}^n</math>, геометрический центр определяется как

Геометрический центр <math>=\underset{y \in \mathbb{R}^n}{\operatorname{arg\,min}} \sum_{i=1}^m \left \| x_i-y \right \|_2</math>

Заметьте, что здесь arg min означает значение аргумента <math>y</math>, на котором достигается минимальная сумма. Это точка <math>y</math>, для которой сумма всех евклидовых расстояний до <math>x_i</math>, минимально.

Свойства

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

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

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

Вычисление

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

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

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

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

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

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

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

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

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

<math>0=\sum_{j=1}^m \frac {x_j - y} {\left \| x_j - y \right \|}.</math>

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

<math>\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),</math>

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

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

<math>0= \sum_{j=1}^m u_j </math>

где для xj ≠ y,

<math>u_j=\frac {x_j - y} {\left \| x_j - y \right \|}</math>

а для xj=y,

<math>\| u_j \| \leq 1 .</math>

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

<math>\sum _{1\le j\le m, x_j\ne y}

\frac {x_j - y} {\left \| x_j - y \right \|} \le \left|\{ \,j\mid 1\le j\le m, x_j= y\,\}\right|.</math>

Обобщения

Геометрический центр можно обобщить с евклидовых пространств до общих римановых многообразий (и даже метрических пространств), используя ту же идею, что используется для определения Шаблон:Не переведено 5 на римановых многообразияхШаблон:Sfn. Пусть <math>M</math> — риманово многообразие с функцией расстояния <math>d(\cdot, \cdot)</math>, пусть <math>w_1, \ldots, w_n</math> — <math>n</math> весов, в сумме дающих 1, и пусть <math>x_1, \ldots, x_n</math> — <math>n</math> наблюдений из <math>M</math>. Тогда мы определяем взвешенный геометрический центр <math>m</math> (или взвешенное среднее Фреше) точек данных

<math> m=\underset{x \in M}{\operatorname{arg\,min}} \sum_{i=1}^n w_i d(x,x_i) </math>.

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Шаблон:Среднее

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Более общая задача о k-медиане задаёт вопрос о положении k центров, минимизирующих сумму расстояний от каждой точки множества до ближайшего центра.
  2. ↑ Шаблон:Harvnb;Шаблон:Harvnb. Выпуклый случай первым доказал Шаблон:Не переведено 5.
  3. ↑ Шаблон:Harvnb; Шаблон:Harvnb. Ранее Кокейн и Мельцак Шаблон:Harvnb доказали, что точка Штейнера для 5 точек на плоскости не может быть построена с помощью циркуля и линейки
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Геометрический_центр&oldid=9530304