Геометрическая медиана - Википедия - Geometric median

Пример геометрическая медиана (желтым цветом) серии точек. Синим цветом Центр массы.

В геометрическая медиана дискретного набора точек выборки в Евклидово пространство - точка, минимизирующая сумму расстояний до точек выборки. Это обобщает медиана, который имеет свойство минимизировать сумму расстояний для одномерных данных и обеспечивает основная тенденция в высших измерениях. Он также известен как 1-медиана,^[1] пространственная медиана,^[2] Евклидова точка минимума,^[2] или же Точка Торричелли.^[3]

Геометрическая медиана важна оценщик из место расположения в статистике,^[4] где он также известен как L₁ оценщик.^[5] Это также стандартная проблема в расположение объекта, где моделируется проблема размещения объекта для минимизации затрат на транспортировку.^[6]

Частный случай задачи для трех точек на плоскости (т. Е. м = 3 и п = 2 в определении ниже) иногда также называют проблемой Ферма; возникает при построении минимальных Деревья Штейнера, и изначально проблема была поставлена Пьер де Ферма и решено Евангелиста Торричелли.^[7] Его решение теперь известно как Точка Ферма треугольника, образованного тремя точками выборки.^[8] Геометрическая медиана, в свою очередь, может быть обобщена на задачу минимизации суммы взвешенный расстояния, известные как Проблема Вебера после Альфред Вебер Обсуждение проблемы в своей книге 1909 г. о местонахождении объекта.^[2] Некоторые источники вместо этого называют проблему Вебера проблемой Ферма – Вебера,^[9] но другие используют это название для невзвешенной задачи геометрической медианы.^[10]

Весоловский (1993) представляет собой обзор проблемы геометрической медианы. Видеть Фекете, Митчелл и Бурер (2005) для обобщений задачи на недискретные точечные множества.

Определение

Формально для данного набора м точки ${ 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}}$

Здесь, аргумент мин означает значение аргумента ${ displaystyle y}$ что минимизирует сумму. В данном случае это точка ${ displaystyle y}$ откуда сумма всех Евклидовы расстояния к ${ displaystyle x_ {i}}$минимально.

Характеристики

• Для одномерного случая геометрическая медиана совпадает с медиана. Это потому, что одномерный median также минимизирует сумму расстояний от точек.^[11]
• Геометрическая медиана уникальный всякий раз, когда точки не коллинеарен.^[12]
• Геометрическая медиана эквивариантный для евклидова преобразования подобия, включая перевод и вращение.^[5][11] Это означает, что можно получить тот же результат либо путем преобразования геометрической медианы, либо путем применения того же преобразования к выборочным данным и нахождения геометрической медианы преобразованных данных. Это свойство следует из того, что геометрическая медиана определяется только из попарных расстояний и не зависит от системы ортогональных Декартовы координаты которым представлены данные выборки. Напротив, покомпонентная медиана для многомерного набора данных, как правило, не инвариантна относительно вращения и не зависит от выбора координат.^[5]
• Геометрическая медиана имеет точка разрушения 0,5.^[5] То есть до половины данных выборки могут быть произвольно повреждены, и медиана выборок по-прежнему будет обеспечивать робастная оценка для расположения неповрежденных данных.

Особые случаи

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

Вычисление

Несмотря на то, что геометрическая медиана является простой для понимания концепцией, ее вычисление представляет собой проблему. В центроид или же центр массы, определяемая аналогично геометрической медиане как минимизация суммы квадраты расстояний до каждой точки можно найти по простой формуле - ее координаты - это средние значения координат точек - но было показано, что нет явная формула, ни точный алгоритм, включающий только арифметические операции и kth корни, вообще могут существовать для геометрической медианы. Следовательно, при этом возможны только численные или символьные приближения к решению этой задачи. модель вычисления.^[14]

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

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

${ Displaystyle left.y_ {я + 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). }$

Этот метод сходится почти для всех начальных позиций, но может не сойтись, когда одна из его оценок попадает в одну из заданных точек. Его можно изменить для обработки этих случаев, чтобы он сходился для всех начальных точек.^[12]

Бозе, Махешвари и Морин (2003) описать более сложные процедуры геометрической оптимизации для поиска приблизительно оптимальных решений этой проблемы. В качестве Не, Паррило и Штурмфельс (2008) показать, проблему также можно представить в виде полуопределенная программа.

Cohen et al. (2016) показать, как вычислить геометрическую медиану с произвольной точностью почти за линейное время.

Характеристика геометрической медианы

Если у отличен от всех данных точек, Икс_j, тогда у является геометрической медианой тогда и только тогда, когда она удовлетворяет:

${ 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),}$

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

В целом, у является геометрической медианой тогда и только тогда, когда существуют векторы ты_j такой, что:

${ Displaystyle 0 = сумма _ {j = 1} ^ {m} u_ {j}}$

где для Икс_j ≠ у,

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

и для Икс_j = у,

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

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

Обобщения

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

Смотрите также

• Медоид
• Абсолютное отклонение геометрической медианы

Примечания

Рекомендации