Перегляд вихідного коду сторінки Геометричний центр

{{Unibox}}
'''Геометричний центр''' дискретної множини точок [[Евклідів простір|евклідового простору]] (говорячи статистичною мовою&nbsp;— вибірки)&nbsp;— точка, в якій мінімізується сума відстаней до точок множини. Геометричний центр у математичній статистиці узагальнює [[Медіана (статистика)|медіану]], яка мінімізує відстань в одновимірній вибірці даних. Таким чином, геометричний центр відбиває [[Центральна тенденція|центральну тенденцію]] в просторах високої розмірності. Поняття відоме також за назвами '''1-медіана'''<ref>Загальніша задача про [[K-medians|''k''-медіану]] задає питання про положення ''k'' центрів, що мінімізують суму відстаней від кожної точки множини до найближчого центра.</ref>, '''просторова медіана'''{{Sfn|Drezner, Klamroth, Schöbel, Wesolowsky|2002}}, або '''[[точка Торрічеллі]]'''{{Sfn|Cieslik|2006}}.

Геометричний центр є важливою [[Статистична оцінка|оцінною функцією]] [[Коефіцієнт зсуву|зсуву]] в статистиці{{Sfn|Lawera, Thompson|1993}}, в якій це поняття відоме як '''оцінка ''L''<sub>1</sub>'''{{Sfn|Lopuhaä, Rousseeuw|1991}}. Пошук геометричного центра є також стандартною задачею при [[Задача про розміщення об'єктів|розміщенні об'єктів]], де моделюється розташування об'єктів (виробництва чи споживання) з метою мінімізації транспортних витрат{{Sfn|Eiselt, Marianov|2011}}.

Окремий випадок задачі для трьох точок на площині (тобто ''m'' = 3 і ''n'' = 2 в термінах, описаних нижче) іноді називають задачею Ферма. Вона виникає при побудові мінімальних [[Задача Штейнера|дерев Штейнера]]. Вперше як задачу її поставив [[П'єр Ферма]], а розв'язав [[Еванджеліста Торрічеллі]]{{Sfn|Krarup, Vajda|1997}}. Розв'язок цієї задачі нині відомий як [[точка Ферма]] трикутника{{Sfn|Spain|1996}}. У свою чергу, пошук геометричного центра можна узагальнити до задачі мінімізації суми ''зважених'' відстаней. Ця задача відома як [[задача Вебера]], оскільки [[Альфред Вебер]] обговорював її в книзі 1909 року з питань розміщення об'єктів{{Sfn|Drezner, Klamroth, Schöbel, Wesolowsky|2002}}. У деяких джерелах використано назву ''задача Ферма&nbsp;— Вебера''{{Sfn|Brimberg|1995}}, але деякі джерела використовують ту саму назву для незваженої задачі{{Sfn|Bose, Maheshwari, Morin|2003}}.

Весоловський{{Sfn|Wesolowsky|1993}} дав огляд задачі геометричного центра. Обговорення узагальнення задачі для випадку недискретних множин див. у статті Фекете, Мічела та Боєра{{Sfn|Fekete, Mitchell, Beurer|2005}}.

== Визначення ==
Формально, якщо дано множину, що містить ''m'' точок <math>x_1, x_2, \dots, x_m\,</math>, де всі <math>x_i \in \mathbb{R}^n</math>, геометричний центр визначають як: Геометричний центр <math>=\underset{y \in \mathbb{R}^n}{\operatorname{arg\,min}} \sum_{i=1}^m \left \| x_i-y \right \|_2</math>

Зауважте, що тут ''arg min'' означає значення аргументу <math>y</math>, за якого досягається мінімальна сума. Це точка <math>y</math>, для якої сума всіх [[Евклідова відстань|евклідових відстаней]] до <math>x_i</math>, мінімальна.

== Властивості ==

* Для випадку одновимірного простору [[Медіана (статистика)|медіана]] є геометричним центром (якщо точок парне число, геометричний центр може бути не єдиним). Це тому, що одновимірна медіана мінімізує суму відстаней до точок{{Sfn|Haldane|1948}}.
* Геометричний центр є '''єдиним''' для всіх випадків, коли точки не [[Колінеарність|колінеарні]]{{Sfn|Vardi, Zhang|2000}}.
* Геометричний центр {{Не перекладено|Еквіваріантне відображення|еквіваріантний|en|equivariant}} для евклідового [[Подібність (геометрія)|подібності]], [[Паралельне перенесення|паралельного перенесення]] та [[Обертання (математика)|обертання]]{{Sfn|Lopuhaä, Rousseeuw|1991}}{{Sfn|Haldane|1948}}. Це означає, що той самий результат вийде, якщо знайти образ центра, побудованого до перетворення, або, застосувавши те саме перетворення до всіх точок вибірки, потім знайти геометричний центр. Ця властивість випливає з факту, що геометричний центр визначається лише з попарних відстаней і не залежить від системи ортогональних [[Декартова система координат|декартових координат]]. Разом з тим, покомпонентна медіана для багатовимірних даних при обертанні, в загальному випадку, не є інваріантом і залежить від вибору координат{{Sfn|Lopuhaä, Rousseeuw|1991}}.
* Геометричний центр має {{Не перекладено|Точка зриву|точку зриву|en|Breakdown point}}<!-- Проблема вікіфікації: Сторінка [[:en:Breakdown point]] (→ [[:en:Robust statistics#Breakdown point]]) перекладена як [[Робастність у статистиці]], хоча хотіли [[Точка зриву]] (SashkoR0B0T)--> 0,5{{Sfn|Lopuhaä, Rousseeuw|1991}}. Тобто, до половини даних вибірки можуть бути ненадійними, але геометричний центр вибірки залишається [[Робастність у статистиці|стійкою оцінкою]] положення незіпсованих даних.

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

* '''Для 3 ([[Колінеарність|неколінеарних]]) точок''', якщо якийсь із кутів трикутника з вершинами в цих точках становить 120° або більше, то геометричний центр&nbsp;— це вершина цього кута. Якщо всі кути менші ніж 120 °, геометричний центр&nbsp;— це точка всередині трикутника, яка становить кут 120 ° із кожною парою вершин трикутника{{Sfn|Haldane|1948}}. Ця точка відома як [[точка Ферма]] трикутника (якщо три точки колінеарні, то геометричний центр збігається з точкою, що лежить між двома іншими).
* '''Для 4 [[Компланарність|компланарних]] точок''', якщо одна з чотирьох точок лежить усередині трикутника, утвореного трьома іншими точками, геометричним місцем буде ця внутрішня точка. В іншому випадку чотири точки утворюють опуклий [[чотирикутник]] і геометричним центром слугу точка перетину діагоналей чотирикутника. Геометричний центр чотирьох копланарних точок&nbsp;— це те саме, що і єдина [[Теорема Радона|точка Радона]] для чотирьох точок<ref>{{Harvnb|Cieslik|2006}};{{Harvnb|Plastria|2006}}. Опуклий випадок першим довів {{Не перекладено|Джованні Фаньяно||en|Giovanni Fagnano}}.</ref>.

== Обчислення ==
Попри простоту поняття геометричного центру для розуміння, його обчислення викликає труднощі. [[Центроїд трикутника]] (тобто його [[Центр інерції|центр мас]]), що визначається аналогічно геометричному центру як мінімізація суми ''квадратів'' відстаней до кожної точки, можна отримати за допомогою простих формул&nbsp;— його координати є середнім арифметичним координат точок. Однак така проста формула для геометричного центру невідома. Навіть було показано, що не існує ні [[Вираз замкненого вигляду|явної формули]], ні точного алгоритму, який використовує лише арифметичні операції та операції добування коренів. Таким чином, існують лише апроксимації для розв'язання цієї задачі<ref>{{Harvnb|Bajaj|1986}}; {{Harvnb|Bajaj|1988}}. Раніше Кокейн і Мельцак {{Harvnb|Cockayne, Melzak|1969}} довели, що точку Штейнера для 5 точок на площині не можна побудувати за допомогою [[Побудова за допомогою циркуля та лінійки|циркуля та лінійки]].</ref>.

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

Один із підходів такого роду&nbsp;— '''алгоритм Вайсфельда''' ({{Не перекладено|Андре Вайсфельд||en|Endre Weiszfeld}}){{Sfn|Weiszfeld|1937}}{{Sfn|Kuhn|1973}}{{Sfn|Chandrasekaran, Tamir|1989}} є видом {{Не перекладено|Ітераційний зважений метод найменших квадратів|ітераційного зваженого методу найменших квадратів|en|iteratively re-weighted least squares}} зі змінними вагами. Цей алгоритм задає множину ваг, які обернено пропорційні відстаням до поточного наближення, і обчислює нове наближення, що є середнім зваженим точок вибірки згідно з цими вагами. Тобто

: <math>\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).</math>

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

Бозе, Магешварі і Морін{{Sfn|Bose, Maheshwari, Morin|2003}} описали витонченішу процедуру оптимізації для пошуку оптимального приблизного розв'язку цієї задачі. Як показали Не, Парріло і Стармфілс{{Sfn|Nie, Parrilo, Sturmfels|2008}}, задачу можна подати як задачу {{Нп|Напіввизначене програмування|напіввизначеного програмування|en|Semidefinite programming}}.

Коен, Лі, Міллер і Пачоки{{Sfn|Cohen, Lee, Miller, Pachocki, Sidford|2016}} показали, як обчислити геометричний центр із довільною точністю за майже лінійний час.

== Опис геометричного центра ==
Якщо точка ''y'' відмінна від усіх заданих точок вибірки ''x''<sub>''j,''</sub> то ''y'' є геометричним центром [[тоді й лише тоді]], коли

: <math>0=\sum_{j=1}^m \frac {x_j - y} {\left \| x_j - y \right \|}.</math>

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

: <math>\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),</math>

що тісно пов'язане з алгоритмом Вайсфельда.

У загальному випадку ''y'' є геометричним центром тоді й лише тоді, коли існують вектори ''u''<sub>''j''</sub> такі, що

: <math>0= \sum_{j=1}^m u_j </math>

де для ''x'' <sub>''j''</sub> ≠ ''y'',

: <math>u_j=\frac {x_j - y} {\left \| x_j - y \right \|}</math>

а для ''x'' <sub>''j''</sub> = ''y'',

: <math>\| u_j \| \leq 1 .</math>

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

: <math>\sum _{1\le j\le m, x_j\ne y}
\frac {x_j - y} {\left \| x_j - y \right \|} \le \left|\{
\,j\mid 1\le j\le m, x_j= y\,\}\right|.</math>

== Узагальнення ==
Геометричний центр можна узагальнити з евклідових просторів до загальних [[Ріманів многовид|ріманових многовидів]] (і навіть [[Метричний простір|метричних просторів]]), використовуючи ту ж іде, що використовується для визначення {{Не перекладено|Середнє Фреше|середнього Фреше|en|Fréchet mean}} на ріманових многовидах{{Sfn|Fletcher, Venkatasubramanian, Joshi|2009}}. Нехай <math>M</math>&nbsp;— ріманів многовид із функцією відстані <math>d(\cdot, \cdot)</math>, нехай <math>w_1, \ldots, w_n</math>&nbsp;— <math>n</math> ваг, сума яких 1, і нехай <math>x_1, \ldots, x_n</math>&nbsp;— <math>n</math> спостережень з <math>M</math>. Тоді ми визначаємо зважений геометричний центр <math>m</math> (або зважене середнє Фреше) точок даних

: <math> m=\underset{x \in M}{\operatorname{arg\,min}} \sum_{i=1}^n w_i d(x,x_i) </math> .

Якщо всі ваги рівні, ми говоримо, що <math>m</math> є геометричним центром.

== Примітки ==
{{Reflist|2}}

== Література ==
{{Refbegin|colwidth=30em}}
* {{Стаття|author=Chandrajit Bajaj|title=Proving geometric algorithms nonsolvability: An application of factoring polynomials|видання=[[Journal of Symbolic Computation]]|рік=1986|том=2|pages=99–102|doi=10.1016/S0747-7171(86)80015-3|ref=Bajaj}}
* {{Стаття|last=Chandrajit Bajaj|title=The algebraic degree of geometric optimization problems|url=https://archive.org/details/sim_discrete-computational-geometry_1988_3_2/page/177|видання=[[Discrete and Computational Geometry]]|рік=1988|том=3|pages=177–191|doi=10.1007/BF02187906|ref=Bajaj}}
* {{Стаття|title=Fast approximations for sums of distances, clustering and the Fermat–Weber problem|видання=[[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]|том=24|issue=3|pages=135–146|рік=2003|doi=10.1016/S0925-7721(02)00102-5|url=http://www.scs.carleton.ca/~jit/publications/papers/bmm01.ps|ref=Bose, Maheshwari, Morin}}
* {{Стаття|author=J. Brimberg|doi=10.1007/BF01592245|issue=1, Ser. A|видання=[[Mathematical Programming]]|pages=71–76|title=The Fermat–Weber location problem revisited|том=71|рік=1995|ref=Brimberg}}
* {{Стаття|author=R. Chandrasekaran, A. Tamir|title=Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem|url=https://archive.org/details/sim_mathematical-programming_1989-11_44_3/page/293|видання=[[Mathematical Programming]]|том=44|рік=1989|pages=293–295|doi=10.1007/BF01587094|ref=Chandrasekaran, Tamir}}
* {{Книга
|заголовок = Shortest Connectivity: An Introduction with Applications in Phylogeny
|том = 17
|серія = Combinatorial Optimization
|автор = Dietmar Cieslik
|видавництво = Springer
|рік = 2006
|ISBN = 9780387235394
|посилання = https://books.google.com/books?id=4E0r3oWkn6AC&pg=PA3
|ref = Cieslik
}}
* {{Стаття|doi=10.2307/2688541|author=E. J. Cockayne, Z. A. Melzak|title=Euclidean constructability in graph minimization problems|url=https://archive.org/details/sim_mathematics-magazine_1969-09_42_4/page/206|видання=[[Mathematics Magazine]]|том=42|issue=4|pages=206–208|рік=1969|ref=Cockayne, Melzak}}
* {{Книга
|частина = Geometric median in nearly linear time
|автор = Michael Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, Aaron Sidford
|видавництво = [[Association for Computing Machinery]]
|заголовок = Proc. 48th [[Symposium on Theory of Computing]] (STOC 2016)
|рік = 2016
|ref = Cohen, Lee, Miller, Pachocki, Sidford
}}
* {{Книга
|автор = Zvi Drezner, Kathrin Klamroth, Anita Schöbel, George O. Wesolowsky
|частина = The Weber problem
|сторінки = 1–36
|видавництво = Springer, Berlin
|заголовок = Facility Location: Applications and Theory
|посилання = https://books.google.com/books?id=sxpcsGN7K1YC&pg=PA1
|рік = 2002
|ref = Drezner, Klamroth, Schöbel, Wesolowsky
}}
* {{Книга
|заголовок = Foundations of Location Analysis
|том = 155
|серія = International Series in Operations Research & Management Science
|автор = H. A. Eiselt, Vladimir Marianov
|видавництво = Springer
|рік = 2011
|ISBN = 9781441975720
|сторінки = 6
|посилання = https://books.google.com/books?id=6bQ8JJ_Rx6sC&pg=PA6
|ref = Eiselt, Marianov
}}
* {{Стаття|author=Sándor P. Fekete, Joseph S. B. Mitchell, Karin Beurer|title=On the continuous Fermat-Weber problem|видання=[[Operations Research (journal)|Operations Research]]|том=53|issue=1|pages=61–76|рік=2005|ref=Fekete, Mitchell, Beurer|arxiv=cs.CG/0310027|doi=10.1287/opre.1040.0137}}
* {{Стаття|author=P. Thomas Fletcher, Suresh Venkatasubramanian, Sarang Joshi|title=The geometric median on Riemannian manifolds with application to robust atlas estimation|видання=NeuroImage|том=45|рік=2009|pages=s143–s152|doi=10.1016/j.neuroimage.2008.10.052|pmid=19056498|issue=1 Suppl|ref=Fletcher, Venkatasubramanian, Joshi}}
* {{Стаття|author=J. B. S. Haldane|title=Note on the median of a multivariate distribution|видання=Biometrika|рік=1948|том=35|issue=3–4|pages=414–417|doi=10.1093/biomet/35.3-4.414|ref=Haldane}}
* {{Стаття|author=Jakob Krarup, Steven Vajda|doi=10.1093/imaman/8.3.215|issue=3|видання=IMA Journal of Mathematics Applied in Business and Industry|pages=215–224|title=On Torricelli's geometrical solution to a problem of Fermat|том=8|рік=1997|ref=Krarup, Vajda}}
* {{Стаття|author=Harold W. Kuhn|title=A note on Fermat's problem|видання=[[Mathematical Programming]]|рік=1973|том=4|issue=1|pages=98–107|doi=10.1007/BF01584648|ref=Kuhn}}
* {{Книга
|частина = Some problems of estimation and testing in multivariate statistical process control
|автор = Martin Lawera, James R. Thompson
|рік = 1993
|сторінки = 99–126
|посилання = http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA390709
|заголовок = Proceedings of the 38th Conference on the Design of Experiments
|серія = U.S. Army Research Office Report
|том = 93-2
|ref = Lawera, Thompson
}}
* {{Стаття|author=Hendrick P. Lopuhaä, Peter J. Rousseeuw|title=Breakdown points of affine equivariant estimators of multivariate location and covariance matrices|url=https://archive.org/details/sim_annals-of-statistics_1991-03_19_1/page/229|рік=1991|видання=[[Annals of Statistics]]|том=19|pages=229–248|issue=1|doi=10.1214/aos/1176347978|ref=Lopuhaä, Rousseeuw}}
* {{Книга
|автор = Jiawang Nie, Pablo A. Parrilo, Bernd Sturmfels
|серія = IMA Volumes in Mathematics and its Applications
|том = 146
|відповідальний = A. Dickenstein, F.-O. Schreyer, A.J. Sommese
|видавництво = Springer-Verlag
|сторінки = 117–132
|рік = 2008
|заголовок = Algorithms in Algebraic Geometry
|ref = Nie, Parrilo, Sturmfels
}}
* {{Стаття|author=L. Ostresh|title=Convergence of a Class of Iterative Methods for Solving Weber Location Problem|рік=1978|видання=[[Operations Research (journal)|Operations Research]]|том=26|pages=597–609|doi=10.1287/opre.26.4.597|ref=Ostresh|issue=4}}
* {{Стаття|title=Four-point Fermat location problems revisited. New proofs and extensions of old results|author=Frank Plastria|рік=2006|doi=10.1093/imaman/dpl007|видання=IMA Journal of Management Mathematics|url=http://mosi.vub.ac.be/papers/Plastria2005_Fegnano.pdf|ref=Plastria|том=17|issue=4|pages=387–396}}
* {{Стаття|author=P. G. Spain|issue=2|видання=Mathematics Magazine|pages=131–133|title=The Fermat Point of a Triangle|url=https://archive.org/details/sim_mathematics-magazine_1996-04_69_2/page/131|том=69|рік=1996|ref=Spain}}
* {{Стаття|author=Yehuda Vardi, Cun-Hui Zhang|doi=10.1073/pnas.97.4.1423|issue=4|видання=Proceedings of the National Academy of Sciences of the United States of America|pages=1423–1426 (electronic)|title=The multivariate ''L''<sub>1</sub>-median and associated data depth|том=97|рік=2000|ref=Vardi, Zhang}}
* {{Книга
|автор = Alfred Weber
|заголовок = Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes
|місце = Tübingen
|видавництво = Mohr
|рік = 1909
|ref = Weber
}}
* {{Стаття|author=G. Wesolowsky|title=The Weber problem: History and perspective|url=https://archive.org/details/sim_location-science_1993-05_1_1/page/5|видання=Location Science|том=1|pages=5–23|рік=1993|ref=Wesolowsky}}
* {{Стаття|author=E. Weiszfeld|title=Sur le point pour lequel la somme des distances de ''n'' points donnes est minimum|видання=[[Tohoku Mathematical Journal]]|том=43|рік=1937|pages=355–386|ref=Weiszfeld}}
{{Refend}}

{{Середні значення}}

[[Категорія:Геометричні алгоритми]]
[[Категорія:Дослідження операцій]]
[[Категорія:Теорія оптимізації]]
[[Категорія:Непараметрична статистика]]
[[Категорія:Багатовимірна статистика]]
[[Категорія:Середні величини]]