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

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

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

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

Геометрическая медиана является важным показателем местоположения в статистике . поскольку это минимизирует сумму L ₂ расстояний образцов. Его следует сравнивать со средним значением, которое минимизирует сумму квадратов расстояний L2 _{медианой по координатам ,} которая минимизирует сумму расстояний L1 _{, и с} . Это также стандартная задача определения местоположения объекта , где моделируется задача определения местоположения объекта для минимизации затрат на транспортировку. Более общая k задача -медианы требует определения местоположения k центров кластеров, минимизирующих сумму расстояний L ₂ от каждой точки выборки до ее ближайшего центра.

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

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

Определение

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

${\underset {y\in \mathbb {R} ^{n}}{\operatorname {arg\,min} }}\sum _{i=1}^{m}\left\|x_{i}-y\right\|_{2}$

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

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

• Для одномерного случая геометрическая медиана совпадает с медианой . Это связано с тем, что одномерная медиана также минимизирует сумму расстояний от точек. (Точнее, если точки p ₁ , ..., p _n в таком порядке, геометрическая медиана является средней точкой $p_{(n+1)/2}$ если n нечетно, но не определено однозначно, если n четно, когда это может быть любая точка на отрезке между двумя средними точками $p_{n/2}$ и $p_{(n/2)+1}$.)
• Геометрическая медиана уникальна , если точки не лежат на одной прямой .
• Геометрическая медиана эквивариантна для евклидовых преобразований подобия , включая перемещение и вращение . Это означает, что можно получить один и тот же результат, либо преобразовав геометрическую медиану, либо применив то же преобразование к выборочным данным и найдя геометрическую медиану преобразованных данных. Это свойство следует из того, что геометрическая медиана определяется только по попарным расстояниям и не зависит от системы ортогональных декартовых координат , в которой представлены выборочные данные. Напротив, покомпонентная медиана для многомерного набора данных, как правило, не является инвариантом вращения и не зависит от выбора координат.
• Геометрическая медиана имеет точку пробоя 0,5. То есть до половины выборочных данных могут быть произвольно повреждены, а медиана выборок по-прежнему будет обеспечивать надежную оценку местоположения неповрежденных данных.

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

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

Вычисление

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

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

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

$\left.y_{k+1}=\left(\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y_{k}\|}}\right)\right/\left(\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y_{k}\|}}\right).$

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

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

${\underset {y\in \mathbb {R} ^{n},\ s\in \mathbb {R} ^{m}}{\min }}\ \sum _{i=1}^{m}s_{i}{\text{ subject to }}s_{i}\geq \left\|x_{i}-y\right\|_{2}{\text{ for }}i=1,\ldots ,m,$

которая может быть решена за полиномиальное время с использованием обычных решателей оптимизации .

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

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

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

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

$\left.y=\left(\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y\|}}\right)\right/\left(\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y\|}}\right),$

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

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

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

где для x _i ≠ y ,

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

и для x _i = y ,

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

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

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

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

Обобщения

Геометрическую медиану можно обобщить с евклидовых пространств на общие римановы многообразия (и даже на метрические пространства ), используя ту же идею, которая используется для определения среднего значения Фреше на римановом многообразии. Позволять $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$ является геометрической медианой.

См. также

• Медоид
• Геометрическое медианное абсолютное отклонение

Ссылки

• Баджадж, Чандерджит (1986). «Доказательство неразрешимости геометрических алгоритмов: применение факторизации полиномов» . Журнал символических вычислений . 2 : 99–102. дои : 10.1016/S0747-7171(86)80015-3 .
• Баджадж, Чандерджит (1988). «Алгебраическая степень задач геометрической оптимизации» . Дискретная и вычислительная геометрия . 3 (2): 177–191. дои : 10.1007/BF02187906 .
• Бозе, Просенджит ; Махешвари, Анил; Морен, Пэт (2003). «Быстрые приближения суммы расстояний, кластеризации и проблемы Ферма – Вебера» . Вычислительная геометрия: теория и приложения . 24 (3): 135–146. дои : 10.1016/S0925-7721(02)00102-5 .
• Бримберг, Дж. (1995). «Еще раз к проблеме местоположения Ферма-Вебера». Математическое программирование . 71 (1, Сер. А): 71–76. дои : 10.1007/BF01592245 . МР   1362958 . S2CID   206800756 .
• Чандрасекаран, Р.; Тамир, А. (1989). «Открытые вопросы, касающиеся алгоритма Вайсфельда для задачи размещения Ферма-Вебера». Математическое программирование . Серия А. 44 (1–3): 293–295. дои : 10.1007/BF01587094 . S2CID   43224801 .
• Чеслик, Дитмар (2006). Кратчайшая связность: введение с приложениями в филогении . Комбинаторная оптимизация. Том. 17. Спрингер. п. 3. ISBN  9780387235394 .
• Кокейн, Э.Дж.; Мельзак, ЗА (1969). «Евклидова конструктивность в задачах минимизации графа». Журнал «Математика» . 42 (4): 206–208. дои : 10.2307/2688541 . JSTOR   2688541 .
• Коэн, Майкл; Ли, Инь Тат; Миллер, Гэри ; Пачоцкий, Якуб; Сидфорд, Аарон (2016). «Геометрическая медиана почти за линейное время» (PDF) . Учеб. 48-й симпозиум по теории вычислений (STOC 2016) . Ассоциация вычислительной техники . стр. 9–21. arXiv : 1606.05225 . дои : 10.1145/2897518.2897647 . ISBN  978-1-4503-4132-5 .
• Додж, Ядола; Руссон, Валентин (сентябрь 1999 г.). «Многомерное значение L ₁ ». Метрика . 49 (2): 127–134. дои : 10.1007/s001840050029 .
• Дрезнер, Цви; Кламрот, Катрин ; Шёбель, Анита ; Весоловский, Джордж О. (2002). «Задача Вебера» . Расположение объекта: приложения и теория . Шпрингер, Берлин. стр. 1–36. ISBN  9783540213451 . МР   1933966 .
• Эйзельт, штат Ха; Марианов, Владимир (2011). Основы анализа местоположения . Международная серия по исследованию операций и науке управления. Том. 155. Спрингер. п. 6. ISBN  9781441975720 .
• Фекете, Шандор П.; Митчелл, Джозеф С.Б .; Бойрер, Карин (2005). «О непрерывной задаче Ферма-Вебера». Исследование операций . 53 (1): 61–76. arXiv : cs.CG/0310027 . дои : 10.1287/опре.1040.0137 . S2CID   1121 .
• Флетчер, П. Томас; Венкатасубраманиан, Суреш; Джоши, Саранг (2009). «Геометрическая медиана на римановых многообразиях с применением к надежной оценке атласа» . НейроИмидж . 45 (1 доп.): с143–с152. doi : 10.1016/j.neuroimage.2008.10.052 . ПМЦ   2735114 . ПМИД   19056498 .
• Холдейн, JBS (1948). «Примечание о медиане многомерного распределения». Биометрика . 35 (3–4): 414–417. дои : 10.1093/biomet/35.3-4.414 .
• Краруп, Якоб; Вайда, Стивен (1997). «О геометрическом решении Торричелли задачи Ферма». Журнал IMA по математике, применяемой в бизнесе и промышленности . 8 (3): 215–224. дои : 10.1093/имаман/8.3.215 . МР   1473041 .
• Кун, Гарольд В. (1973). «Заметка о проблеме Ферма». Математическое программирование . 4 (1): 98–107. дои : 10.1007/BF01584648 . S2CID   22534094 .
• Лавера, Мартин; Томпсон, Джеймс Р. (1993). «Некоторые проблемы оценки и тестирования при многомерном статистическом управлении процессами» (PDF) . Материалы 38-й конференции по планированию экспериментов . Отчет исследовательского управления армии США. Том. 93–2. стр. 99–126. Архивировано из оригинала 17 мая 2014 года.
• Лопухаа, Хендрик П.; Руссиу, Питер Дж. (1991). «Точки разрушения аффинных эквивариантных оценок многомерных матриц местоположения и ковариации» . Анналы статистики . 19 (1): 229–248. дои : 10.1214/aos/1176347978 . JSTOR   2241852 .
• Не, Цзяван; Паррило, Пабло А.; Штурмфельс, Бернд (2008). «Полуопределенное представление k -эллипса». В Дикенштейне, А.; Шрайер, Ф.-О.; Соммесе, Эй Джей (ред.). Алгоритмы в алгебраической геометрии . Тома IMA по математике и ее приложениям. Том. 146. Шпрингер-Верлаг. стр. 117–132. arXiv : математика/0702005 . Бибкод : 2007math......2005N . дои : 10.1007/978-0-387-75155-9_7 . ISBN  978-0-387-75154-2 . S2CID   16558095 .
• Остреш, Л. (1978). «Сходимость класса итерационных методов решения задачи локации Вебера». Исследование операций . 26 (4): 597–609. дои : 10.1287/опре.26.4.597 .
• Пластрия, Франк (2006). «Возвращение к четырехточечной проблеме размещения Ферма. Новые доказательства и расширение старых результатов» (PDF) . Журнал IMA по управленческой математике . 17 (4): 387–396. дои : 10.1093/imaman/dpl007 . Збл   1126.90046 . Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 18 мая 2014 г. .
• Испания, PG (1996). «Точка Ферма треугольника». Журнал «Математика» . 69 (2): 131–133. дои : 10.1080/0025570X.1996.11996409 . JSTOR   2690672?origin=pubexport . МР   1573157 .
• Варди, Иегуда; Чжан, Цунь-Хуэй (2000). «Многомерная L ₁ -медиана и связанная с ней глубина данных» . Труды Национальной академии наук Соединенных Штатов Америки . 97 (4): 1423–1426 (электронный). Бибкод : 2000PNAS...97.1423V . дои : 10.1073/pnas.97.4.1423 . МР   1740461 . ПМК   26449 . ПМИД   10677477 .
• Вебер, Альфред (1909). О размещении производств. Часть первая: Чистая теория размещения (на немецком языке). Тюбинген: Мор.
• Весоловский, Г. (1993). «Проблема Вебера: история и перспективы». Наука о местоположении . 1 :5–23.
• Вайсфельд, Э. (1937). «О той точке, для которой сумма расстояний n данных точек минимальна» . Математический журнал Тохоку (на французском языке). 43 : 355–386. В переводе на английский как Вайсфельд, Э.; Пластрия, Фрэнк (апрель 2008 г.). «О точке, для которой сумма расстояний до n заданных точек минимальна». Анналы исследования операций . 167 (1): 7–41. дои : 10.1007/s10479-008-0352-z . S2CID   21000317 .