Геометричний центр

Геометричний центр

Геометричний центр дискретної множини точок евклідового простору (говорячи статистичною мовою — вибірки) — точка, в якій мінімізується сума відстаней до точок множини. Геометричний центр у математичній статистиці узагальнює медіану, яка мінімізує відстань в одновимірній вибірці даних. Таким чином, геометричний центр відбиває центральну тенденцію в просторах високої розмірності. Поняття відоме також за назвами 1-медіана, просторова медіана, або точка Торрічеллі.

Геометричний центр є важливою оцінною функцією зсуву в статистиці, в якій це поняття відоме як оцінка L₁. Пошук геометричного центра є також стандартною задачею при розміщенні об'єктів, де моделюється розташування об'єктів (виробництва чи споживання) з метою мінімізації транспортних витрат.

Окремий випадок задачі для трьох точок на площині (тобто m = 3 і n = 2 в термінах, описаних нижче) іноді називають задачею Ферма. Вона виникає при побудові мінімальних дерев Штейнера. Вперше як задачу її поставив П'єр Ферма, а розв'язав Еванджеліста Торрічеллі. Розв'язок цієї задачі нині відомий як точка Ферма трикутника. У свою чергу, пошук геометричного центра можна узагальнити до задачі мінімізації суми зважених відстаней. Ця задача відома як задача Вебера, оскільки Альфред Вебер обговорював її в книзі 1909 року з питань розміщення об'єктів. У деяких джерелах використано назву задача Ферма — Вебера, але деякі джерела використовують ту саму назву для незваженої задачі.

Весоловський дав огляд задачі геометричного центра. Обговорення узагальнення задачі для випадку недискретних множин див. у статті Фекете, Мічела та Боєра.

Визначення

Формально, якщо дано множину, що містить m точок $x_{1},x_{2},\dots ,x_{m}\,$, де всі $x_{i}\in \mathbb {R} ^{n}$, геометричний центр визначають як: Геометричний центр $={\underset {y\in \mathbb {R} ^{n}}{\operatorname {arg\,min} }}\sum _{i=1}^{m}\left\|x_{i}-y\right\|_{2}$

Зауважте, що тут arg min означає значення аргументу $y$, за якого досягається мінімальна сума. Це точка $y$, для якої сума всіх евклідових відстаней до $x_{i}$, мінімальна.

Властивості

• Для випадку одновимірного простору медіана є геометричним центром (якщо точок парне число, геометричний центр може бути не єдиним). Це тому, що одновимірна медіана мінімізує суму відстаней до точок.
• Геометричний центр є єдиним для всіх випадків, коли точки не колінеарні.
• Геометричний центр еквіваріантний для евклідового подібності, паралельного перенесення та обертання. Це означає, що той самий результат вийде, якщо знайти образ центра, побудованого до перетворення, або, застосувавши те саме перетворення до всіх точок вибірки, потім знайти геометричний центр. Ця властивість випливає з факту, що геометричний центр визначається лише з попарних відстаней і не залежить від системи ортогональних декартових координат. Разом з тим, покомпонентна медіана для багатовимірних даних при обертанні, в загальному випадку, не є інваріантом і залежить від вибору координат.
• Геометричний центр має точку зриву 0,5. Тобто, до половини даних вибірки можуть бути ненадійними, але геометричний центр вибірки залишається стійкою оцінкою положення незіпсованих даних.

Окремі випадки

• Для 3 (неколінеарних) точок, якщо якийсь із кутів трикутника з вершинами в цих точках становить 120° або більше, то геометричний центр — це вершина цього кута. Якщо всі кути менші ніж 120 °, геометричний центр — це точка всередині трикутника, яка становить кут 120 ° із кожною парою вершин трикутника. Ця точка відома як точка Ферма трикутника (якщо три точки колінеарні, то геометричний центр збігається з точкою, що лежить між двома іншими).
• Для 4 компланарних точок, якщо одна з чотирьох точок лежить усередині трикутника, утвореного трьома іншими точками, геометричним місцем буде ця внутрішня точка. В іншому випадку чотири точки утворюють опуклий чотирикутник і геометричним центром слугу точка перетину діагоналей чотирикутника. Геометричний центр чотирьох копланарних точок — це те саме, що і єдина точка Радона для чотирьох точок.

Обчислення

Попри простоту поняття геометричного центру для розуміння, його обчислення викликає труднощі. Центроїд трикутника (тобто його центр мас), що визначається аналогічно геометричному центру як мінімізація суми квадратів відстаней до кожної точки, можна отримати за допомогою простих формул — його координати є середнім арифметичним координат точок. Однак така проста формула для геометричного центру невідома. Навіть було показано, що не існує ні явної формули, ні точного алгоритму, який використовує лише арифметичні операції та операції добування коренів. Таким чином, існують лише апроксимації для розв'язання цієї задачі.

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

Один із підходів такого роду — алгоритм Вайсфельда (Андре Вайсфельд) є видом ітераційного зваженого методу найменших квадратів зі змінними вагами. Цей алгоритм задає множину ваг, які обернено пропорційні відстаням до поточного наближення, і обчислює нове наближення, що є середнім зваженим точок вибірки згідно з цими вагами. Тобто

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

Метод збігається майже з усіх початкових положень, але може завершитися невдачею, якщо наближення виявляється в одній із точок вибірки. Алгоритм можна модифікувати так, що він збігатиметься для всіх початкових точок.

Бозе, Магешварі і Морін описали витонченішу процедуру оптимізації для пошуку оптимального приблизного розв'язку цієї задачі. Як показали Не, Парріло і Стармфілс, задачу можна подати як задачу напіввизначеного програмування.

Коен, Лі, Міллер і Пачоки показали, як обчислити геометричний центр із довільною точністю за майже лінійний час.

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

Якщо точка y відмінна від усіх заданих точок вибірки x_j, то y є геометричним центром тоді й лише тоді, коли

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

Це еквівалентно

$\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 такі, що

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

де для x _j ≠ y,

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

а для x _j = y,

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

Еквівалентне формулювання цієї умови

$\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|.$

Узагальнення

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

Література

• Chandrajit Bajaj. Proving geometric algorithms nonsolvability: An application of factoring polynomials // Journal of Symbolic Computation. — 1986. — Т. 2. — С. 99–102. — DOI:10.1016/S0747-7171(86)80015-3.
• Chandrajit Bajaj. The algebraic degree of geometric optimization problems // Discrete and Computational Geometry. — 1988. — Т. 3. — С. 177–191. — DOI:10.1007/BF02187906.
• Fast approximations for sums of distances, clustering and the Fermat–Weber problem // Computational Geometry: Theory and Applications. — 2003. — Т. 24, вип. 3. — С. 135–146. — DOI:10.1016/S0925-7721(02)00102-5.
• J. Brimberg. The Fermat–Weber location problem revisited // Mathematical Programming. — 1995. — Т. 71, вип. 1, Ser. A. — С. 71–76. — DOI:10.1007/BF01592245.
• R. Chandrasekaran, A. Tamir. Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem // Mathematical Programming. — 1989. — Т. 44. — С. 293–295. — DOI:10.1007/BF01587094.
• Dietmar Cieslik. Shortest Connectivity: An Introduction with Applications in Phylogeny. — Springer, 2006. — Т. 17. — (Combinatorial Optimization) — ISBN 9780387235394.
• E. J. Cockayne, Z. A. Melzak. Euclidean constructability in graph minimization problems // Mathematics Magazine. — 1969. — Т. 42, вип. 4. — С. 206–208. — DOI:10.2307/2688541.
• Michael Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, Aaron Sidford. Geometric median in nearly linear time // Proc. 48th Symposium on Theory of Computing (STOC 2016). — Association for Computing Machinery, 2016.
• Zvi Drezner, Kathrin Klamroth, Anita Schöbel, George O. Wesolowsky. The Weber problem // Facility Location: Applications and Theory. — Springer, Berlin, 2002. — С. 1–36.
• H. A. Eiselt, Vladimir Marianov. Foundations of Location Analysis. — Springer, 2011. — Т. 155. — С. 6. — (International Series in Operations Research & Management Science) — ISBN 9781441975720.
• Sándor P. Fekete, Joseph S. B. Mitchell, Karin Beurer. On the continuous Fermat-Weber problem // Operations Research. — 2005. — Т. 53, вип. 1. — С. 61–76. — arXiv:cs.CG/0310027. — DOI:10.1287/opre.1040.0137.
• P. Thomas Fletcher, Suresh Venkatasubramanian, Sarang Joshi. The geometric median on Riemannian manifolds with application to robust atlas estimation // NeuroImage. — 2009. — Т. 45, вип. 1 Suppl. — С. s143–s152. — DOI:10.1016/j.neuroimage.2008.10.052. — PMID 19056498 .
• J. B. S. Haldane. Note on the median of a multivariate distribution // Biometrika. — 1948. — Т. 35, вип. 3–4. — С. 414–417. — DOI:10.1093/biomet/35.3-4.414.
• Jakob Krarup, Steven Vajda. On Torricelli's geometrical solution to a problem of Fermat // IMA Journal of Mathematics Applied in Business and Industry. — 1997. — Т. 8, вип. 3. — С. 215–224. — DOI:10.1093/imaman/8.3.215.
• Harold W. Kuhn. A note on Fermat's problem // Mathematical Programming. — 1973. — Т. 4, вип. 1. — С. 98–107. — DOI:10.1007/BF01584648.
• Martin Lawera, James R. Thompson. Some problems of estimation and testing in multivariate statistical process control // Proceedings of the 38th Conference on the Design of Experiments. — 1993. — Т. 93-2. — С. 99–126. — (U.S. Army Research Office Report)
• Hendrick P. Lopuhaä, Peter J. Rousseeuw. Breakdown points of affine equivariant estimators of multivariate location and covariance matrices // Annals of Statistics. — 1991. — Т. 19, вип. 1. — С. 229–248. — DOI:10.1214/aos/1176347978.
• Jiawang Nie, Pablo A. Parrilo, Bernd Sturmfels. Algorithms in Algebraic Geometry / A. Dickenstein, F.-O. Schreyer, A.J. Sommese. — Springer-Verlag, 2008. — Т. 146. — С. 117–132. — (IMA Volumes in Mathematics and its Applications)
• L. Ostresh. Convergence of a Class of Iterative Methods for Solving Weber Location Problem // Operations Research. — 1978. — Т. 26, вип. 4. — С. 597–609. — DOI:10.1287/opre.26.4.597.
• Frank Plastria. Four-point Fermat location problems revisited. New proofs and extensions of old results // IMA Journal of Management Mathematics. — 2006. — Т. 17, вип. 4. — С. 387–396. — DOI:10.1093/imaman/dpl007.
• P. G. Spain. The Fermat Point of a Triangle // Mathematics Magazine. — 1996. — Т. 69, вип. 2. — С. 131–133.
• Yehuda Vardi, Cun-Hui Zhang. The multivariate L₁-median and associated data depth // Proceedings of the National Academy of Sciences of the United States of America. — 2000. — Т. 97, вип. 4. — С. 1423–1426 (electronic). — DOI:10.1073/pnas.97.4.1423.
• Alfred Weber. Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes. — Tübingen : Mohr, 1909.
• G. Wesolowsky. The Weber problem: History and perspective // Location Science. — 1993. — Т. 1. — С. 5–23.
• E. Weiszfeld. Sur le point pour lequel la somme des distances de n points donnes est minimum // Tohoku Mathematical Journal. — 1937. — Т. 43. — С. 355–386.