Геометрическая медиана

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

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

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

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

Весоловский (1993) дает обзор проблемы геометрической медианы. См. Обобщения проблемы на недискретные точечные множества в Fekete, Mitchell & Beurer (2005) .

Определение [ править ]

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

Свойства [ править ]

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

Особые случаи [ править ]

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

Вычисление [ править ]

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

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

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

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

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

Bose, Maheshwari & Morin (2003) описывают более сложные процедуры геометрической оптимизации для поиска приблизительно оптимальных решений этой проблемы. Как показывают Nie, Parrilo & Sturmfels (2008) , проблема также может быть представлена ​​как полуопределенная программа .

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

Характеристика геометрической медианы [ править ]

Если 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|.}$

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

Обобщения [ править ]

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]