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

Точка, минимизирующая сумму расстояний до заданных точек

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

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

Геометрическая медиана является важным оценщиком местоположения в статистике [3], где ^она также известна как оценка L ₁ ^[4] (поскольку она минимизирует норму L 1 вектора расстояний). ^[5] Это также стандартная задача определения местоположения объекта , где моделируется задача определения местоположения объекта для минимизации затрат на транспортировку. ^[6] Более общая задача k -медианы требует определения местоположения k центров кластеров, минимизирующих сумму расстояний от каждой точки выборки до ее ближайшего центра. Если точку обобщить в линию или кривую, наиболее подходящее решение находится по наименьшему абсолютному отклонению .

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

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

Определение

Формально для данного набора из m точек с каждым геометрическая медиана определяется как ${\displaystyle \mathbb {X} ^{m}=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 означает значение аргумента , который минимизирует сумму. В данном случае это точка в n-мерном евклидовом пространстве, откуда сумма всех евклидовых расстояний до 's минимальна. ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x_{i}}$

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

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

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

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

Вычисление

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

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

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

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

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

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

${\displaystyle {\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 является геометрической медианой тогда и только тогда, когда она удовлетворяет _:

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

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

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

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

где для x _i ≠ y ,

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

и для x _i = y ,

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

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

${\displaystyle \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 , а сумма направлений упрощается до (направленной) считающей меры.

Обобщения

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

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

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

Примечания

1. Drezner et al. (2002)
2. Чеслик (2006).
3. Лавера и Томпсон (1993).
4. Lopuhaä & Rousseeuw (1991)
5. Додж и Руссон (1999).
6. Эйзельт и Марианов (2011).
7. Краруп и Вайда (1997).
8. Испания (1996).
9. Бримберг (1995).
10. Бозе, Махешвари и Морин (2003).
11. Холдейн (1948)
12. Утверждение 18.10, Геометрические методы и задачи оптимизации , В. Болтянски, Х. Мартини, В. Солтан, Springer, 1999.
13. Варди и Чжан (2000)
14. Цеслик (2006), с. 6; Пластрия (2006). Выпуклый случай был первоначально доказан Джованни Фаньяно .
15. Баджадж (1986); Баджадж (1988). Ранее Кокейн и Мельзак (1969) доказали, что точку Штейнера для 5 точек на плоскости невозможно построить с помощью линейки и циркуля.
16. Вайсфельд (1937); Кун (1973); Чандрасекаран и Тамир (1989).
17. Флетчер, П. Томас; Венкатасубраманиан, Суреш; Джоши, Саранг (23 июня 2008 г.). «Надежная статистика римановых многообразий через геометрическую медиану». Конференция IEEE 2008 г. по компьютерному зрению и распознаванию образов . Конференция IEEE по компьютерному зрению и распознаванию образов. Анкоридж, штат Алабама, США: IEEE.
18. Флетчер, Венкатасубраманиан и Джоши (2009).

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

• Баджадж, Чандерджит (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. MR  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) . Ассоциация вычислительной техники . arXiv : 1606.05225 . дои : 10.1145/2897518.2897647.
• Додж, Ядола; Руссон, Валентин (сентябрь 1999 г.). «Многомерное значение L _{1 ».} Метрика . 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/opre.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 . Бибкод : 2007математика......2005Н. дои : 10.1007/978-0-387-75155-9_7. 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..
• Испания, PG (1996). «Точка Ферма треугольника». Журнал «Математика» . 69 (2): 131–133. дои : 10.1080/0025570X.1996.11996409. JSTOR  2690672?origin=pubexport. МР  1573157.
• Варди, Иегуда; Чжан, Цунь-Хуэй (2000). «Многомерная L1-медиана и связанная с ней глубина данных». Труды Национальной академии наук Соединенных Штатов Америки . 97 (4): 1423–1426 (электронный). Бибкод : 2000PNAS...97.1423V. дои : 10.1073/pnas.97.4.1423 . МР  1740461. ПМК  26449 . ПМИД  10677477.
• Вебер, Альфред (1909). Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes (на немецком языке). Тюбинген: Мор.
• Весоловский, Г. (1993). «Проблема Вебера: история и перспективы». Наука о местоположении . 1 :5–23.
• Вайсфельд, Э. (1937). «Sur le point pour lequel la some des Distances de n Points Donnes EST Minimal». Математический журнал Тохоку (на французском языке). 43 : 355–386.Переведено на английский как Вайсфельд, Э.; Пластрия, Фрэнк (апрель 2008 г.). «О точке, для которой сумма расстояний до n заданных точек минимальна». Анналы исследования операций . 167 (1): 7–41. doi : 10.1007/s10479-008-0352-z. S2CID  21000317.